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

Teorie algoritmů

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah Jazyk výuky
B4M01TAL Z,ZK 6 3P+2S česky
Garant předmětu:
Marie Demlová
Přednášející:
Marie Demlová
Cvičící:
Marie Demlová, Natalie Žukovec
Předmět zajišťuje:
katedra matematiky
Anotace:

Předmět seznamuje se základními pojmy a postupy teorie složitosti. Důraz je kladen na časovou složitost,ale studenti se seznámí i paměťovou složitostí a amortizovanou složitostí. Studenti se seznámí s Turingovými stroji a to jak s jednou, tak i více páskami. Je uveden pojem redukce úlohy/jazyka a polynomiální redukce jazyka/úlohy. Předmět se věnuje třídám složitosti P, NP, NPC, co-NP, a třídám PSPACE a NPSPACE založeným na paměťové složitosti. Je uvedena Savitchova věta. Dále se předmět věnuje pravděpodobnostním algoritmům a třídám RP a ZPP. Na závěr se studenti seznámí s teorií nerozhodnutelnosti. K pochopení látky se též používají konkrétní algoritmy, jedná se hlavně o algoritmy z teorie grafů a kryptografie.

Požadavky:
Osnova přednášek:

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

2. Amortizovaná složitost. Správnost algoritmů, variant a invariant.

3. Příklady důkazů správnosti.

4. Turingův stroj, základní model, Turingův stroj s více páskami, nedeterministický Turingův stroj.

5. Churchova a Turingova teze. Vztah Turingova stroje a RAM.

6. Jazyky a úlohy. Třídy P a NP.

7. Polynomiální redukce úloh. Třída NPC. NP těžké úlohy.

8. Cookova věta. Příklady NP-úplných úloh (problém klik, nezávislých množin, vrcholového pokrytí, 3-barevnost).

9. Další příklady NP-úplných úloh (existence hamiltonovské kružnice, problém obchodního cestujícího, celočíselné lineární programování, problém batohu).

10. Heuristiky a aproximační algoritmy pro NP-úplné úlohy.

11. Třídy PSPACE a NPSPACE. Savitchova věta.

12. Pravděpodobnostní algoritmy, třídy RP a ZPP. Miller-Rabinův algoritmus pro prvočíselnost.

13. Rekursivní a rekursivně spočetné jazyky. Algoritmicky neřešitelné úlohy.

Osnova cvičení:

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

2. Amortizovaná složitost. Správnost algoritmů, variant a invariant.

3. Příklady důkazů správnosti.

4. Turingův stroj, základní model, Turingův stroj s více páskami, nedeterministický Turingův stroj.

5. Churchova a Turingova teze. Vztah Turingova stroje a RAM.

6. Jazyky a úlohy. Třídy P a NP.

7. Polynomiální redukce úloh. Třída NPC. NP těžké úlohy.

8. Cookova věta. Příklady NP-úplných úloh (problém klik, nezávislých množin, vrcholového pokrytí, 3-barevnost).

9. Další příklady NP-úplných úloh (existence hamiltonovské kružnice, problém obchodního cestujícího, celočíselné lineární programování, problém batohu).

10. Heuristiky a aproximační algoritmy pro NP-úplné úlohy.

11. Třídy PSPACE a NPSPACE. Savitchova věta.

12. Pravděpodobnostní algoritmy, třídy RP a ZPP. Miller-Rabinův algoritmus pro prvočíselnost.

13. Rekursivní a rekursivně spočetné jazyky. 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] Talbot, J., Welsh, D.: Complexity and Cryptography, Cambridge University Press, 2006

Poznámka:
Další informace:
http://math.feld.cvut.cz/demlova/teaching/tal_vyuka.html pro ceskou verzi, https://math.feld.cvut.cz/demlova/teaching/e-tal_vyuka.html for english version
Rozvrh na zimní semestr 2024/2025:
Rozvrh není připraven
Rozvrh na letní semestr 2024/2025:
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
T2:D3-209
St
místnost T2:C3-52
Žukovec N.
09:15–10:45
(přednášková par. 1
paralelka 104)

Dejvice
T2:C3-52
místnost T2:C3-52
Demlová M.
14:30–16:00
(přednášková par. 1
paralelka 101)

Dejvice
T2:C3-52
místnost T2:C3-52

16:15–17:45
(přednášková par. 1
paralelka 106)

Dejvice
T2:C3-52
místnost T2:C3-51
Demlová M.
11:00–12:30
(přednášková par. 1
paralelka 102)

Dejvice
T2:C3-51
místnost T2:C3-52
Žukovec N.
12:45–14:15
(přednášková par. 1
paralelka 105)

Dejvice
T2:C3-52
místnost T2:C3-52
Žukovec N.
11:00–12:30
(přednášková par. 1
paralelka 108)

Dejvice
T2:C3-52
Čt

Předmět je součástí následujících studijních plánů:
Platnost dat k 14. 12. 2024
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/cs/predmet4695106.html