Teorie algoritmů
| 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 St Čt Pá - Předmět je součástí následujících studijních plánů:
-
- Otevřená informatika - Interakce člověka s počítačem 2018 (povinný předmět programu)
- Otevřená informatika - Kybernetická bezpečnost 2018 (povinný předmět programu)
- Otevřená informatika - Počítačová grafika 2018 (povinný předmět programu)
- Otevřená informatika - Počítačové inženýrství 2018 (povinný předmět programu)
- Otevřená informatika - Počítačové vidění a digitální obraz 2018 (povinný předmět programu)
- Otevřená informatika - Softwarové inženýrství 2018 (povinný předmět programu)
- Otevřená informatika - Umělá inteligence 2018 (povinný předmět programu)
- Otevřená informatika - Bioinformatika 2018 (povinný předmět programu)
- Otevřená informatika - Datové vědy 2018 (povinný předmět programu)