..:: Martin Kot ::..
Theoretical computer science
General Actual Download Projects Combined studies
General facts
Guarantee:  Prof. RNDr. Petr Jančar, CSc.
Number of credits:  8
Completition:  Exam
Web page:  http://www.cs.vsb.cz/jancar/TEORET-INF/teoret-inf.htm
Lecturers: 
 
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
 
Notice
Also informations under tabs Actual, Projects and Download are valid for combined students.
Informations on official web page may be also useful.
 
Tutorials
  • Preliminary plan of tutorials, it will be updated according to reality.
1st tutorial 
  • Course introduction.
  • Formal languages.
  • Finite automata.
2nd tutorial 
  • Reduction of a finite automaton.
  • Regularity of languages.
  • Nondeterministic finite automata and their conversion to deterministic automata.
3rd tutorial 
  • Regular expressions
  • Context-free grammars.
4th tutorial 
  • Reduction of context-free gramars.
  • Pushdown automata.
  • Hierarchy of languages.
  • Demonstration of term test.
5th tutorial 
  • Term test.
  • Turing machines.
  • RAM machine.
6th tutorial 
  • Discussion about corrected tests.
  • Reduction between problems, complexity classes.
  • Algorithmically undecidable problems.
7th tutorial 
  • Informations about exam.
  • Student presentations.
 
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.