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

Harmonogram:

Osnova:

1. Algoritmus, asymptotický růst funkcí, časová a paměťová 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.

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

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

  Pro studenty kombinované formy Kombinované studium.

  Zkoušky:

  Podmínkou ke zkoušce je zápočet. Zápočet se uděluje na základě aktivní účasti na cvičení. Upřesnění stanoví cvičící na prvním cvičení.

  Zkouška se skládá z písemné a ústní části. Písemná část trvá 90 minut a je možné za ni získat maximálně 80 bodů. Z ústní části je možné získat maximálně 30 bodů. K ústní zkoušce je student připuštěn pouze jestliže dosáhl alespoň 40 bodů z písemné části.

  Hodnocení zkoušky:

  součet	známka
  55-65	E (dostatečně)
  66-76	D (uspokojivě)
  77-88	C (dobře)
  89-99	B (velmi dobře)
  100-110	A (výborně)