Moodle FEL ČVUT
Teorie algoritmů
B241 - Zimní 24/25
Teorie algoritmů - B4M01TAL
| Kredity | 6 |
| Semestry | letní |
| Zakončení | zápočet a zkouška |
| Jazyk výuky | čeština |
| Rozsah výuky | 3P+2S |
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.
Cíle studia
None
Osnovy 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.
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.
Osnovy 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.
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.
Literatura
[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
[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
Požadavky
None