460-4005/01 – Theoretical Computer Science (TI)
Gurantor department | Department of Computer Science | Credits | 8 |
Subject guarantor | prof. RNDr. Petr Jančar, CSc. | Subject version guarantor | prof. RNDr. Petr Jančar, CSc. |
Study level | undergraduate or graduate | Requirement | Choice-compulsory |
Year | 1 | Semester | summer |
| | Study language | Czech |
Year of introduction | 2010/2011 | Year of cancellation | 2014/2015 |
Intended for the faculties | FEI | Intended for study types | Follow-up Master |
Subject aims expressed by acquired skills and competences
On successful completion of the course, the student
- is able to evaluate the possible extent of using the methods of
finite automata, context-free grammars etc. by solving concrete
practical problems, and is able to design, analyse and compare the
respective solutions
- is able to analyse computational complexity of practical problems,
and to design algorithms for their solution
- understands the notions like approximation algorithms, probabilistic
algorithms, etc. and can evaluate the possibilities of their use in
concrete practical situations
Teaching methods
Lectures
Tutorials
Project work
Summary
The course extends the theoretical background for computer science
gained in bachelor studies, in particular in the areas of automata,
languages, computability and complexity.
Compulsory literature:
Michael Sipser: Introduction to the Theory of Computation, Thomson
2006
Recommended literature:
Michael Sipser: Introduction to the Theory of Computation, Thomson
2006
Way of continuous check of knowledge in the course of semester
E-learning
Other requirements
No additional requirements are placed on the student.
Prerequisities
Subject has no prerequisities.
Co-requisities
Subject has no co-requisities.
Subject syllabus:
Lectures:
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.
Exercises:
Basic language operations, in particular the quotient operations.
Design of finite automata for simple languages. Construction of more
complex automata from simpler ones.
Algorithms for transforming into the normal form and for checking the
isomorphism of finite automata. Algorithm of minimalization. Proofs of
nonregularity of concrete languages.
Design of nondeterministic finite automata; their transforming to
deterministic ones.
Regular expressions as a means for description of regular languages.
Transformations among finite automata, regular expressions and regular
grammars. Closure properties of the class of regular languages.
Design of concrete context-free grammars.
Examples of transforming ambiguous grammars to nonambiguous ones.
Algorithms for reduction and epsilon-rules removing.
Design of pushdown automata. Transformations between context-free
grammars and pushdown automata.
Design of deterministic pushdown automata.
Closure properties of the class of context-free languages.
Transformation into Chomsky normal form.
Proofs of non-context-freeness by help of pumping lemma.
Construction of Turing machines.
Asymptotic growth of concrete functions.
Design and analysis of complexity of concrete (polynomial) algorithms.
Some concrete applications of general methods for design of polynomial
algorithms.
Mutual simulation between concrete computational models.
Design of nondeterministic (polynomial) algorithms.
Polynomial reducibility among concrete problems.
Showing membership of concrete problems in
PTIME, NPTIME, PSPACE, NPSPACE; demonstrating NP- and PSPACE-hardness.
Construction of the universal Turing machine.
Proofs of undecidability of concrete problems. Applications of Rice's
Theorem.
Selected exercises in the area of approximation and probabilistic
algorithms.
Projects:
Each student will be assigned a selected topic related to the contents
of the course (at the beginning of semester).
The student will study the topic from the recommended or freely
chosen sources. He/she will then elaborate his/her own text which will
consicely explain the main ideas, within the given deadline and in (at
least) the minimal given extent.
The author will personally present the topic at some exercise session
or in another way determined by the lecturer.
Conditions for subject completion
Occurrence in study plans
Occurrence in special blocks
Assessment of instruction