..:: Martin Kot ::..
Theoretical computer science
General Actual Download Projects Combined studies
General facts
Guarantee:  Prof. RNDr. Petr Jančar, CSc.
Number of credits:  6
Completition:  Exam
Web page:  http://www.cs.vsb.cz/jancar/TEORET-INF/teoret-inf.htm
Lecturers: 
 
Division of points
Accreditation: 
  • 21pts - short written exam
  • 10pts - written solution of a given exercise and oral performance of this solution
  • 7pts - activity during seminars
  • Conditions for accreditation are presentation of solution of given exercise (accepted by teacher) and at least 7 points from written term exam
Exam: 
  • 62 pts - 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.
  • Finite automata and regular languages.
2nd tutorial 
  • Context-free languages and grammars.
  • Pushdown automata.
3rd tutorial 
  • Turing machines, RAM machines.
  • Algorithmic complexity.
4th tutorial 
  • General design methods for algorithms and complexity analysis of algorithms.
  • Complexity classes of problems, especially PTIME, NPTIME, PSPACE.
5th tutorial 
  • Demonstration of term test.
  • Polynomial reductions between problems, NP-completness.
6th tutorial 
  • Term test.
  • Undecidability of 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.