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 22.7.2024 17:51:06, semestry: Z,L/2023-4, 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) |