Popis předmětu - B4M01TAL
Přehled studia |
Přehled oborů |
Všechny skupiny předmětů |
Všechny předměty |
Seznam rolí |
Vysvětlivky
Návod
Webová stránka:
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
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.
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. |
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. |
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 |
Požadavky:
Předmět je zahrnut do těchto studijních plánů:
Stránka vytvořena 27.7.2024 17:50:58, semestry: L/2024-5, L/2023-4, Z/2024-5, Z/2023-4, připomínky k informační náplni zasílejte správci studijních plánů |
Návrh a realizace: I. Halaška (K336), J. Novák (K336) |