..:: Martin Kot ::..
Theoretical computer science
General Actual Download Projects Combined studies
General facts
Guarantee:  Prof. RNDr. Petr Jančar, CSc.
Number of credits:  8
Hours:  4/2/0/0
Completition:  Exam
Web page:  http://www.cs.vsb.cz/jancar/TEORET-INF/teoret-inf.htm
Lecturers: 
Exercisers:  , ,
,
 
Division of points
Accreditation: 
  • 24pts - short written exam
  • 11pts - written solution of a given exercise and oral performance of this solution
  • Conditions for accreditation are presentation of solution of given exercise (accepted by teacher) and at least 8 points from written term exam
Exam: 
  • 65pts - written exam
  • 0pts - optional oral exam - consultation of written exam
 
Annotation
The course extends the theoretical background for computer science gained in bachelor studies, in particular in the areas of automata, languages, computability and complexity.
 
Time table
7:15
8:00
8:00
8:45
9:00
9:45
9:45
10:30
10:45
11:30
11:30
12:15
12:30
13:15
13:15
14:00
14:15
15:00
15:00
15:45
16:00
16:45
16:45
17:30
17:45
18:30
18:30
19:15
pondělí      
EC1
Jančar P.
EB130
Kot M.
EB130
Kot M.
EB130
Meca O.
EB130
Meca O.
úterý    
EB130
Sawa Z.
EB130
Šaloun P. (zrušeno)
               
středa                            
čtvrtek        
EB130
Kot M.
EC2 (sudý týden)
Jančar P.
EB130
Kot M.
       
pátek                            
sobota                            
 
Lectures
Languages and automata
  • Course introduction; overview and motivation. Basic notions from language theory. Finite automata.
  • Nondeterministic finite automata and their realtion to the deterministic ones.
  • Regular operations, regular languages. Closure properties of the class of regular languages.
  • Regular expressions, relation to finite automata.
  • Minimization of finite automata.
  • Pumping lemma for regular languages and its use.
  • Further variants of finite-state models (two-way finite automata, finite-state transducers,...)
Computability and complexity
  • Context-free grammars and languages. Reduced grammars. Chomsky normal form.
  • Pushdown automata. Relation between pushdown automata and context-free grammars.
  • Closure properties of the class of context-free languages. Deterministic pushdown automata.
  • Pumping lemma for context-free languages.
  • General generative grammars. Chomsky hierarchy. Turing machines. Recursive and recursively enumerable languages.
  • Complexity of algorithms. Random access machine (RAM). Asymptotic estimations, notation.
  • Complexity analysis for selected (polynomial) algorithms. The worst-case vs. the average case.
  • Problems, complexity classes, upper and lower bounds for problem complexity. Mutual polynomial simulation of reasonable computational models. Class PTIME, its robustness and significance.
  • Class NPTIME. The P-NP question. Polynomial reducidability between problems. NP-completeness. Further time and space complexity classes and their interrelations.
  • Provably intractable problems. Church-Turing thesis. Decidability and semi-decidability of problems.
  • Recursive and recursively enumerable sets (languages). Recursive and partially recursive functions. Universal Turing machine. The diagonalization method. Undecidability of the halting problem.
  • Recursive reducibility. Further undecidable problems. Rice's theorem.
  • Brief introduction to approximation algorithms, probabilistic algorithms, parallel and distributed algorithms.
 
Study literature
Basic
Other
  • T. Cormen, C. Leiserson, R. Rivest: Introduction to Algorithms. The MIT Press, 1990.
  • John E. Hopcroft a Jeffrey D. Ullman: Formálne jazyky a automaty. Alfa Bratislava 1978.
  • J. Gruska: Foundation of Computing, International Thomson Computer Press 1997.
  • D. Kozen: Automata and Computability, Undergraduate Text in Computer Science, Springer Verlag 1997.
  • M. Sipser: Introduction to the Theory of Computation. PWS Publishing Company 1997.