Teorie algoritmů

Předmět není vypsán Nerozvrhuje se

Kód	Zakončení	Kredity	Rozsah	Jazyk výuky
A4M01TAL	Z,ZK	6	3P+1S	česky

Garant předmětu:

Přednášející:

Cvičící:

Předmět zajišťuje:

katedra matematiky

Anotace:

Predmět se věnuje teoretickým základům teori algoritmů, důraz je kladen jak na analýzu časové a pměťové složitosti algoritmů a problémů, tak na ověření správnosti algoritmů. Dále jsou probrány základy teorie složitosti. Jedná se o třídy P, NP, NP-complete, PSPACE,

NPSPACE a vztah mezi těmito třídami. V předmětu se studenti seznámí také s pravděpodobnostními algoritmy a třidami RP a ZPP.

Výsledek studentské ankety předmětu je zde: http://www.fel.cvut.cz/anketa/aktualni/courses/AD4M01TAL

Výsledek studentské ankety předmětu je zde: http://www.fel.cvut.cz/anketa/aktualni/courses/A4M01TAL

Požadavky:

Logika a grafy, Diskrétní matematika

Osnova přednášek:

1. Algoritmus, asymptotický růst funkcí, časová a paměťová složitost.

2. Správnost algoritmu, 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.

Osnova cvičení:

1. Zjišťování časové a paměťové složitosti známých (např. grafových) algoritmů.

2. Ověřování správnosti jednoduchých algoritmů, hledání variantů a invariantů.

3. Turingovy stroje.

4. Příklady redukcí úloh.

5. Příklady pravděpodobnostních algoritmů.

6. Algoritmicky neřešitelné úlohy.

Cíle studia:

Studijní materiály:

[1] Kozen, D. C.: The design and Analysis of Algorithms, Springer-Vrelag, 1991

[2] Harel, D: Algorithmics: The Spirit of Computing, Addison-Wesleyt Inc., Reading MA 2002

[3] Hopcroft, J., Motwani, R., Ullman, J.: Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 2001

Poznámka:

Rozsah výuky v kombinované formě studia: 21p+3s

Další informace:

http://math.feld.cvut.cz/demlova/teaching/tal_vyuka.html

Pro tento předmět se rozvrh nepřipravuje

Předmět je součástí následujících studijních plánů: