Výuka - předmět Teorie algoritmů

Harmonogram:

Osnova:

1. Algoritmus, asymptotický růst funkcí, časová a paměťová složitost, amortizovaná složitost.
2. Správnost algoritmů, důkazy správnosti algoritmů, varianty a invarianty.
3. Rozhodovací a optimalizační problémy a jejich vztah.
4. Turingovy stroje a jejich varianty.
5. Vztah Turingova stroje a RAM.
6. Třída P a třída NP.
7. Redukce a polynomiální redukce úloh.
8. NP-úplné úlohy, Cookova věta.
9. Třídy PSPACE a NPSPACE.
10. Pravděpodobnostní algoritmy pracující v polynomiálním čase.
11. Třídy RP a ZZP.
12. Algoritmicky neřešitelné úlohy.
13. Rezerva.

Literatura:

• D. C. Kozen: The Design and Analysis of Algorithms, Springer-Verlag, 1991.
• J. Hopcroft, R. Motwani, J. Ullman: Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 2001.
• D. Harel: Algorithmics: The Spirit of Computing, Addison-Wesley, 2002.

  Konzultační hodiny po domluvě.

  Stručný obsah přednášek - Přednášky.

  Prezentace z přednášek - Prezentace.

  Cvičení a příklady na cvičení - Cvičení.

  Zkoušky - Organizace zkoušek.