Popis předmětu - A4M01TAL

Přehled studia | Přehled oborů | Všechny skupiny předmětů | Všechny předměty | Seznam rolí | Vysvětlivky               Návod
A4M01TAL Teorie algoritmů
Role:  Rozsah výuky:3P+1S
Katedra:13101 Jazyk výuky:CS
Garanti:  Zakončení:Z,ZK
Přednášející:  Kreditů:6
Cvičící:  Semestr:L

Webová stránka:

http://math.feld.cvut.cz/demlova/teaching/tal_vyuka.html

Anotace:

Predmět se věnuje teoretickým základům teori algoritmů, důraz je kladen jak na analýzu časové a pměťové složitosti algoritmů a problémů, tak na ověření správnosti algoritmů. Dále jsou probrány základy teorie složitosti. Jedná se o třídy P, NP, NP-complete, PSPACE, NPSPACE a vztah mezi těmito třídami. V předmětu se studenti seznámí také s pravděpodobnostními algoritmy a třidami RP a ZPP.

Výsledek studentské ankety předmětu je zde: AD4M01TAL

Výsledek studentské ankety předmětu je zde: A4M01TAL

Osnovy přednášek:

1. Algoritmus, asymptotický růst funkcí, časová a paměťová složitost.
2. Správnost algoritmu, důkazy správnosti algoritmů, varianty a invarianty-
3. Rozhodovací a optimalizační problémy a jejich vztah.
4. Turingovy stroje a jejich varianty.
5. Vztah Turingova stroje a RAM.
6. Třída P a třída NP.
7. Redukce a polynomiální redukce úloh.
8. NP-úplné úlohy, Cookova věta.
9. Třídy PSPACE a NPSPACE.
10. Pravděpodobnostní algoritmy pracující v polynomiálním čase.
11. Třídy RP a ZZP.
12. Algoritmicky neřešitelné úlohy.
13. Rezerva.

Osnovy cvičení:

1. Zjišťování časové a paměťové složitosti známých (např. grafových) algoritmů.
2. Ověřování správnosti jednoduchých algoritmů, hledání variantů a invariantů.
3. Turingovy stroje.
4. Příklady redukcí úloh.
5. Příklady pravděpodobnostních algoritmů.
6. 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] Hopcroft, J., Motwani, R., Ullman, J.: Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 2001

Požadavky:

Logika a grafy, Diskrétní matematika

Poznámka:

Rozsah výuky v kombinované formě studia: 21p+3s

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

Plán Obor Role Dop. semestr


Stránka vytvořena 28.3.2024 09:53:46, 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)