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ů Rozsah výuky:3+2
Garanti:Demlová M. Role:P Jazyk výuky:CS
Vyučující:Demlová M. Zakončení:Z,ZK
Zodpovědná katedra:13101 Kreditů:6 Semestr:L

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:

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

Předmět je zahrnut do těchto studijních plánů:

Plán Obor Role Dop. semestr
MPOI1_2016 Interakce člověka s počítačem P 2
MPOI9_2016 Datové vědy P 2
MPOI8_2016 Bioinformatika P 2
MPOI7_2016 Umělá inteligence P 2
MPOI6_2016 Softwarové inženýrství P 2
MPOI5_2016 Počítačové vidění a digitální obraz P 2
MPOI4_2016 Počítačové inženýrství P 2
MPOI3_2016 Počítačová grafika P 2
MPOI2_2016 Kybernetická bezpečnost P 2
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 17.12.2018 17:48:15, semestry: Z,L/2020-1, L/2017-8, L/2019-20, Z,L/2018-9, Z/2019-20, 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)
Za obsah odpovídá: doc. Ing. Ivan Jelínek, CSc.