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
B4M01TAL Teorie algoritmů
Role:P Rozsah výuky:3P+2S
Katedra:13101 Jazyk výuky:CS
Garanti:Demlová M. Zakončení:Z,ZK
Přednášející:Demlová M. Kreditů:6
Cvičící:Demlová M., Žukovec N. Semestr:L

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ů:

Plán Obor Role Dop. semestr
MPOI1_2018 Interakce člověka s počítačem P 2
MPOI9_2018 Datové vědy P 2
MPOI8_2018 Bioinformatika P 2
MPOI7_2018 Umělá inteligence P 2
MPOI6_2018 Softwarové inženýrství P 2
MPOI5_2018 Počítačové vidění a digitální obraz P 2
MPOI4_2018 Počítačové inženýrství P 2
MPOI3_2018 Počítačová grafika P 2
MPOI2_2018 Kybernetická bezpečnost P 2


Stránka vytvořena 28.3.2024 17:52:19, semestry: Z,L/2023-4, Z/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)