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

Harmonogram:

Výukové týdny: 20.2. - 28.5.2017

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: