Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2019/2020

Teorie algoritmů

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah Jazyk výuky
A4M01TAL Z,ZK 6 3P+1S česky
Přednášející:
Marie Demlová (gar.)
Cvičící:
Marie Demlová (gar.), Natalie Žukovec
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
Rozvrh na zimní semestr 2019/2020:
Rozvrh není připraven
Rozvrh na letní semestr 2019/2020:
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po
Út
místnost T2:D3-209
Demlová M.
08:15–10:45
(přednášková par. 1)
Dejvice
Posluchárna
St
místnost
Žukovec N.
14:30–16:00
(přednášková par. 1
paralelka 101)

Čt

Předmět je součástí následujících studijních plánů:
Platnost dat k 24. 2. 2020
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet12581704.html