Popis předmětu - AD4M01TAL

Přehled studia | Přehled oborů | Všechny skupiny předmětů | Všechny předměty | Seznam rolí | Vysvětlivky               Návod
AD4M01TAL Teorie algoritmů Rozsah výuky:21+3
Garanti:  Role:ZZ,P,V Jazyk výuky:CS
Vyučující:  Zakončení:Z,ZK
Zodpovědná katedra:13101 Kreditů:6 Semestr:L

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
MKEEM1 Technologické systémy V 2
MKEEM5 Ekonomika a řízení elektrotechniky V 2
MKEEM4 Ekonomika a řízení energetiky V 2
MKEEM3 Elektroenergetika V 2
MKEEM2 Elektrické stroje, přístroje a pohony V 2
MKKME1 Bezdrátové komunikace V 2
MKKME5 Komunikační systémy V 2
MKKME4 Sítě elektronických komunikací V 2
MKKME3 Elektronika V 2
MKKME2 Multimediální technika V 2
MKOI1 Umělá inteligence P 2
MKOI5 Softwarové inženýrství P 2
MKOI4 Počítačová grafika a interakce P 2
MKOI3 Počítačové vidění a digitální obraz P 2
MKOI2 Počítačové inženýrství P 2
MVT04N-D Výpočetní technika ZZ 2
MVT01N-D Výpočetní technika ZZ 2
MKKYR4 Letecké a kosmické systémy V 2
MKKYR1 Robotika V 2
MKKYR3 Systémy a řízení V 2
MKKYR2 Senzory a přístrojová technika V 2


Stránka vytvořena 22.7.2019 05:51:23, semestry: Z,L/2020-1, L/2018-9, Z,L/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.