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.
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.