456-0907/01 – Theory of Computation (TA)
Gurantor department | Department of Computer Science | Credits | 10 |
Subject guarantor | prof. RNDr. Petr Jančar, CSc. | Subject version guarantor | prof. RNDr. Petr Jančar, CSc. |
Study level | postgraduate | Requirement | Choice-compulsory |
Year | | Semester | winter + summer |
| | Study language | Czech |
Year of introduction | 1997/1998 | Year of cancellation | 2009/2010 |
Intended for the faculties | FEI | Intended for study types | Doctoral |
Subject aims expressed by acquired skills and competences
On successful completion of the course, the student
- understands the notions from theory of computability and complexity
- is able to design algorithms suitable for practical problems
- is able to analyse complexity of algorithms and categorize problems
according to their complexity
- masters design and analysis of approximation, probabilistic and
parallel algorithms,
- is able by self-study to master and present an advanced topic
in theory of algorithms
Teaching methods
Lectures
Individual consultations
Project work
Summary
The course provides an exact basis for the notions of algorithmic computability nad complexity with which the students are familiar on a more or less intuitive level from their master studies. It is devoted to some advanced areas in computability and complexity (like decidability of logical theories, probabilistic algorithms, parallel computation, etc.)
Compulsory literature:
M.Sipser: Introduction to the Theory of Computation, PWS Publ. Comp. 1997
E.Borger: Computability, Complexity, Logic. North-Holland 1989
D.Harel: Algorithmics, The Spirit of Computing, Addison-Wesley1992
Hopcroft, Ullman: Introduction to Automata Theory, Languages and Computation,
Addison-Wesley 1979
Recommended literature:
M.Sipser: Introduction to the Theory of Computation, PWS Publ. Comp. 1997
Handbook of theoretical computer science (ed. Leeuwen J.);
Vol. A : Algorithms and complexity; North-Holland 1990,
Way of continuous check of knowledge in the course of semester
E-learning
Other requirements
Prerequisities
Subject has no prerequisities.
Co-requisities
Subject has no co-requisities.
Subject syllabus:
Přednášky:
Intuitivní pojem algoritmu a efektivní vyčíslitelné funkce.
Různé matematické
formalizace těchto pojmů (především Turingovy stroje a částečně rekurzivní
funkce).
Idea univerzálního algoritmu. Hlavní myšlenky důkazu ekvivalence
uvedených matematických formalizací, Churchova teze.
Problém zastavení
(Halting problem), Postův korespondenční problém a další algoritmicky
nerozhodnutelné problémy.
Univerzální funkce, Kleeneho věta o normální formě.
Rekurzivní a rekurzivně spočetné množiny, Postova věta.
Věta o rekurzi, Riceova věta. Rekurzivní převeditelnost. Kreativní množiny.
Rozhodnutelnost logických teorií.
Časová a prostorová složitost algoritmů a problémů. P-NP problém.
NP-úplnost a PSPACE-úplnost.
EXPTIME, EXPSPACE, dokazatelně nezvládnutelné problémy.
Aproximační algoritmy, pravděpodobnostní algoritmy.
Paralelní a distribuované algoritmy.
Další témata (např. alternace, krypografie, ...)
Conditions for subject completion
Occurrence in study plans
Occurrence in special blocks
Assessment of instruction
Předmět neobsahuje žádné hodnocení.