..:: Martin Kot ::..
Theoretical computer science
General Actual Download Projects
 
General facts
Guarantee:  Doc. RNDr. Petr Jančar, CSc.
Number of credits:  8
Hours:  4/4/0/0 (In praxis: 4/2/0/2)
Completition:  Exam
Web page:  http://www.cs.vsb.cz/jancar/TEORET-INF/teoret-inf.htm
Lecturers:  ,
Exercisers:  ,
 
Division of points
Accreditation: 
  • 24pts - short written exams
  • 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 4 points from 6 from at least 2 taken written term exams
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í        
Všichni
C3
Jančar P.
           
úterý                            
středa
LN180
K309
Sawa Z.
           
LN177
D212
Sawa Z.
LN178
D210
Kot M.
   
LN181
K308
Kot M.
           
LN176
D210
Kot M.
LN179
D212
Sawa Z.
   
čtvrtek                            
pátek                            
 
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,...)
  • 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.