460-4065/01 – Theoretical Computer Science (TI)
Gurantor department | Department of Computer Science | Credits | 6 |
Subject guarantor | doc. Ing. Zdeněk Sawa, Ph.D. | Subject version guarantor | doc. Ing. Zdeněk Sawa, Ph.D. |
Study level | undergraduate or graduate | Requirement | Optional |
Year | 1 | Semester | winter |
| | Study language | Czech |
Year of introduction | 2015/2016 | Year of cancellation | 2022/2023 |
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
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:
[1] Michael Sipser: Introduction to the Theory of Computation, Thomson
2006
Recommended literature:
[2] Kozen, D.: Automata and Computability, Undergraduate Text in Computer Science, Springer-Verlag, 1997.
[3] Arora, S., Barak, B.: Computational Complexity: A Modern Approach, Cambridge University Press, 2009.
[4] Papadimitriou, C.: Computational Complexity, Addison Wesley, 1993.
[5] Kozen, D.: Theory of computation, Springer 2006.
[6] Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms, Second Edition, The MIT Press, 2001.
[7] Hromkovič, J.: Theoretical Computer Science: Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography, Springer, 2003.
[8] Hopcroft, J.E., Motwani, R., Ullman, J, D.: Introduction to Automata Theory, Languages, and Computation, (3rd edition), Addison Wesley, 2006.
Additional study materials
Way of continuous check of knowledge in the course of semester
E-learning
Other requirements
No additional requirements are placed on students.
Prerequisities
Subject has no prerequisities.
Co-requisities
Subject has no co-requisities.
Subject syllabus:
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.
Conditions for subject completion
Occurrence in study plans
Occurrence in special blocks
Assessment of instruction