Lectures:
1. Introduction. What are the main topics of theoretical computer science (algorithms, algorithmic problems, formal languages, ...).
2. Formal languages - basic notions (alphabet, word, language). Operations on languages. Regular expressions.
3. Deterministic finite automata (DFA). Construction of DFA. Some language operations on DFA.
4. Nondeterministic finite automata (NFA). Transformation of NFA to DFA. Language operations on NFA. Relation between regular expressions and finite automata.
5. Context-free grammars and languages.
6. Pushdown automata and their relation to context-free grammars. Chomsky hierarchy.
7. Algorithmic problems. Models of computation (Turing machines and RAM machines). Church-Turing thesis.
8. Correctness of algorithms. Methods for proving correctness of algorithms.
9. Computational complexity of algorithms. Asymptotic notation. Analysis of computational complexity of algorithms (iterative and recursive).
10. General techniques used in design of algorithms - brute-force solution, divide-and-conquer, backtracking, greedy algorithms, dynamic programming.
11. Complexity of problems. Complexity classes (in particular classes P and NP). Reductions between problems. NP-complete problems.
12. Examples of NP-complete problems and reductions between problems.
13. Undecidable problems (e.g., halting problem).
Tutorials:
(Remark: The topics of tutorials correspond to the topics of lectures.)
1. Recalling basics of logic, set theory, relations, functions, and graph theory.
2. Operations on languages. Regular expressions.
3. Construction of deterministic finite automata (DFA). Operation on these automata.
4. Construction of nondeterministic finite automata (NFA). Transformation of NFA to DFA. Transformations between regular expressions and finite automata.
5. Construction of context-free grammars. Operations on these grammars.
6. Pushdown automata.
7. Algorithmic problems. Turing machines and RAM machines.
8. Proving correctness of algorithms.
9. Asymptotic notation. Analysis of computational complexity of algorithms.
10. Techniques of design of algorithms.
11. Complexity of problems. Complexity classes. Reductions between problems.
12. Proving NP-completeness of problems.
13. Proving undecidability of problems.
1. Introduction. What are the main topics of theoretical computer science (algorithms, algorithmic problems, formal languages, ...).
2. Formal languages - basic notions (alphabet, word, language). Operations on languages. Regular expressions.
3. Deterministic finite automata (DFA). Construction of DFA. Some language operations on DFA.
4. Nondeterministic finite automata (NFA). Transformation of NFA to DFA. Language operations on NFA. Relation between regular expressions and finite automata.
5. Context-free grammars and languages.
6. Pushdown automata and their relation to context-free grammars. Chomsky hierarchy.
7. Algorithmic problems. Models of computation (Turing machines and RAM machines). Church-Turing thesis.
8. Correctness of algorithms. Methods for proving correctness of algorithms.
9. Computational complexity of algorithms. Asymptotic notation. Analysis of computational complexity of algorithms (iterative and recursive).
10. General techniques used in design of algorithms - brute-force solution, divide-and-conquer, backtracking, greedy algorithms, dynamic programming.
11. Complexity of problems. Complexity classes (in particular classes P and NP). Reductions between problems. NP-complete problems.
12. Examples of NP-complete problems and reductions between problems.
13. Undecidable problems (e.g., halting problem).
Tutorials:
(Remark: The topics of tutorials correspond to the topics of lectures.)
1. Recalling basics of logic, set theory, relations, functions, and graph theory.
2. Operations on languages. Regular expressions.
3. Construction of deterministic finite automata (DFA). Operation on these automata.
4. Construction of nondeterministic finite automata (NFA). Transformation of NFA to DFA. Transformations between regular expressions and finite automata.
5. Construction of context-free grammars. Operations on these grammars.
6. Pushdown automata.
7. Algorithmic problems. Turing machines and RAM machines.
8. Proving correctness of algorithms.
9. Asymptotic notation. Analysis of computational complexity of algorithms.
10. Techniques of design of algorithms.
11. Complexity of problems. Complexity classes. Reductions between problems.
12. Proving NP-completeness of problems.
13. Proving undecidability of problems.