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 4.12.2024 17:50:56, semestry: Z/2025-6, Z,L/2024-5, 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) |