Výuka - předmět Teorie algoritmů
Harmonogram:
| Výukové týdny: | 19.2. - 24.5.2024 |
Osnova:
- Algoritmus, asymptotický růst funkcí, časová a paměťová složitost, amortizovaná složitost.
- Správnost algoritmů, důkazy správnosti algoritmů, varianty a invarianty.
- Rozhodovací a optimalizační problémy a jejich vztah.
- Turingovy stroje a jejich varianty.
- Vztah Turingova stroje a RAM.
- Třída P a třída NP.
- Redukce a polynomiální redukce úloh.
- NP-úplné úlohy, Cookova věta.
- Třídy PSPACE a NPSPACE.
- Pravděpodobnostní algoritmy pracující v polynomiálním čase.
- Třídy RP a ZZP.
- Algoritmicky neřešitelné úlohy.
- 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.