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 20.3.2025 17:50:56, semestry: Z,L/2025-6, 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) |