..:: Martin Kot ::..
Theoretical computer science
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í    
J360
Šaloun P.
C3
Jančar P.
     
D209
Šaloun P.
   
úterý                            
středa
D210
Šaloun P.
D210
Šaloun P.
J358
Kot M.
       
B5 (lichý týden)
Jančar P.
   
D209
Kot M.
                       
čtvrtek            
J360
Sawa Z.
J360
Sawa Z.
       
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.
 
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.