Přehled studia | Přehled oborů | Všechny skupiny předmětů | Všechny předměty | Seznam rolí | Vysvětlivky               Návod

---

BE4M01TAL	Theory of Algorithms
Role:	P	Rozsah výuky:	3P+2S
Katedra:	13101	Jazyk výuky:	EN
Garanti:	Demlová M.	Zakončení:	Z,ZK
Přednášející:	Demlová M.	Kreditů:	6
Cvičící:	Demlová M.	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:

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

Plán	Obor	Role	Dop. semestr
MEOI7_2018	Artificial Intelligence	P	2
MEOI9_2018	Data Science	P	2
MEOI8_2018	Bioinformatics	P	2
MEOI4_2018	Computer Engineering	P	2
MEOI3_2018	Computer Graphics	P	2
MEOI2_2018	Cyber Security	P	2
MEOI1_2018	Human-Computer Interaction	P	2
MEOI6_2018	Software Engineering	P	2
MEOI5_2018	Computer Vision and Image Processing	P	2

---

Stránka vytvořena 13.10.2024 09:50:36, semestry: L/2023-4, L/2024-5, Z/2025-6, 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)