Lectures:
1. Course overview.
Recalling basic set theory notions, equivalence relations and orders,
graphs, formalisms of propositional and predicate logics, proofs by
induction and by contradiction.
(All these notions and methods will be used during the whole course.)
2. Formal languages, operations on languages,
regular expressions as language representations,
a pattern-search algorithm presented as (deterministic) finite
automaton. Modular design of finite automata (FA).
3. Deterministic and nondeterministic
finite automata, operations with finite automata,
transforming nondeterministic FA to deterministic ones,
constructing an FA to a given regular expression (RE).
4. Minimization of DFA, the canonical form, automata isomorphism.
FA and RE define the same class, so called regular languages.
Characterizations of regular languages enabling to show
non-regularity.
5. Context-free grammars, their (un)ambiguity, using for
specifications of (fragments of) programming languages.
(Nondeterministic) pushdown automata (PDA).
Syntactic analysis (by recursive descent).
6. Context-free languages and their subclass defined by deterministic
PDA. A basic compiler (constructing an FA to a given RE).
7. Non-context-free languages, Chomsky hierarchy.
Formal languages as computational problems.
The notion of algorithms, computational models
(Turing machine, RAM).
8. Church-Turing thesis. Universal machine.
(Algorithmic) undecidability, the halting problem,
reductions among problems.
Rice's Theorem (each nontrivial input/output property of programs is
undecidable).
9. Computational complexity of algorithms,
general methods of designing polynomial algorithms: "clever" search,
the "divide-and-conquer" method, greedy algorithms for optimization
problems, dynamic programming.
10. Computational complexity of problems, complexity classes,
polynomial reducibility.
Problem SAT (satisfiability of boolean formulas) and nondeterministic
polynomial algorithms. Class NPTIME. NP-completeness.
11. Class PSPACE=NPSPACE, PSPACE-complete problems, higher complexity
classes.
12. Approximation algorithms, i.e., polynomial algorithms
approximating optimal solutions of optimization problems.
(Non)approximability of concrete problems.
13. Randomized algorithms, e.g. for primality, which is a basis of
cryptographic algorithms.
14. Examples of parallel algorithms and of
non-parallelizable (inherently sequential) problems.
Exercises:
The topics of relevant lectures are subjecy of concrete exercises.
1. Course overview.
Recalling basic set theory notions, equivalence relations and orders,
graphs, formalisms of propositional and predicate logics, proofs by
induction and by contradiction.
(All these notions and methods will be used during the whole course.)
2. Formal languages, operations on languages,
regular expressions as language representations,
a pattern-search algorithm presented as (deterministic) finite
automaton. Modular design of finite automata (FA).
3. Deterministic and nondeterministic
finite automata, operations with finite automata,
transforming nondeterministic FA to deterministic ones,
constructing an FA to a given regular expression (RE).
4. Minimization of DFA, the canonical form, automata isomorphism.
FA and RE define the same class, so called regular languages.
Characterizations of regular languages enabling to show
non-regularity.
5. Context-free grammars, their (un)ambiguity, using for
specifications of (fragments of) programming languages.
(Nondeterministic) pushdown automata (PDA).
Syntactic analysis (by recursive descent).
6. Context-free languages and their subclass defined by deterministic
PDA. A basic compiler (constructing an FA to a given RE).
7. Non-context-free languages, Chomsky hierarchy.
Formal languages as computational problems.
The notion of algorithms, computational models
(Turing machine, RAM).
8. Church-Turing thesis. Universal machine.
(Algorithmic) undecidability, the halting problem,
reductions among problems.
Rice's Theorem (each nontrivial input/output property of programs is
undecidable).
9. Computational complexity of algorithms,
general methods of designing polynomial algorithms: "clever" search,
the "divide-and-conquer" method, greedy algorithms for optimization
problems, dynamic programming.
10. Computational complexity of problems, complexity classes,
polynomial reducibility.
Problem SAT (satisfiability of boolean formulas) and nondeterministic
polynomial algorithms. Class NPTIME. NP-completeness.
11. Class PSPACE=NPSPACE, PSPACE-complete problems, higher complexity
classes.
12. Approximation algorithms, i.e., polynomial algorithms
approximating optimal solutions of optimization problems.
(Non)approximability of concrete problems.
13. Randomized algorithms, e.g. for primality, which is a basis of
cryptographic algorithms.
14. Examples of parallel algorithms and of
non-parallelizable (inherently sequential) problems.
Exercises:
The topics of relevant lectures are subjecy of concrete exercises.