456-0907/01 – Teorie algoritmů (TA)
Garantující katedra | Katedra informatiky | Kredity | 10 |
Garant předmětu | prof. RNDr. Petr Jančar, CSc. | Garant verze předmětu | prof. RNDr. Petr Jančar, CSc. |
Úroveň studia | postgraduální | Povinnost | povinně volitelný |
Ročník | | Semestr | zimní + letní |
| | Jazyk výuky | čeština |
Rok zavedení | 1997/1998 | Rok zrušení | 2009/2010 |
Určeno pro fakulty | FEI | Určeno pro typy studia | doktorské |
Cíle předmětu vyjádřené dosaženými dovednostmi a kompetencemi
Student po úspěšném absolvování předmětu:
- rozumí základním pojmům v oblasti algoritmické vyčíslitelnosti a výpočetní složitosti
- umí navrhovat vhodné algoritmy pro praktické problémy
- umí analyzovat složitost algoritmů a zařazovat problémy do tříd složitosti
- zvládá i návrh a analýzu aproximačních, pravděpodobnostních a paralelních algoritmů
- prokáže schopnost samostatně zvládnout a odprezentovat pokročilou partii v oblasti teorie algoritmů
Vyučovací metody
Přednášky
Individuální konzultace
Projekt
Anotace
Předmět poskytuje exaktní základ především pojmům algoritmické řešitelnosti
a algoritmické složitosti, se kterými se posluchači seznámili v průběhu
řádného studia na víceméně intuitivní úrovni. Je věnován některým pokročilým partiím vyčíslitelnosti a složitosti (jako rozhodování logických teorií, pravděpodobnostní algoritmy, paralelní výpočty, atd.)
Povinná literatura:
M.Sipser: Introduction to the Theory of Computation, PWS Publ. Comp. 1997
E.Borger: Computability, Complexity, Logic. North-Holland 1989
D.Harel: Algorithmics, The Spirit of Computing, Addison-Wesley1992
Hopcroft, Ullman: Introduction to Automata Theory, Languages and Computation,
Addison-Wesley 1979
Doporučená literatura:
M.Sipser: Introduction to the Theory of Computation, PWS Publ. Comp. 1997
Handbook of theoretical computer science (ed. Leeuwen J.);
Vol. A : Algorithms and complexity; North-Holland 1990,
Další studijní materiály
Forma způsobu ověření studijních výsledků a další požadavky na studenta
E-learning
Další požadavky na studenta
Prerekvizity
Předmět nemá žádné prerekvizity.
Korekvizity
Předmět nemá žádné korekvizity.
Osnova předmětu
Přednášky:
Intuitivní pojem algoritmu a efektivní vyčíslitelné funkce.
Různé matematické
formalizace těchto pojmů (především Turingovy stroje a částečně rekurzivní
funkce).
Idea univerzálního algoritmu. Hlavní myšlenky důkazu ekvivalence
uvedených matematických formalizací, Churchova teze.
Problém zastavení
(Halting problem), Postův korespondenční problém a další algoritmicky
nerozhodnutelné problémy.
Univerzální funkce, Kleeneho věta o normální formě.
Rekurzivní a rekurzivně spočetné množiny, Postova věta.
Věta o rekurzi, Riceova věta. Rekurzivní převeditelnost. Kreativní množiny.
Rozhodnutelnost logických teorií.
Časová a prostorová složitost algoritmů a problémů. P-NP problém.
NP-úplnost a PSPACE-úplnost.
EXPTIME, EXPSPACE, dokazatelně nezvládnutelné problémy.
Aproximační algoritmy, pravděpodobnostní algoritmy.
Paralelní a distribuované algoritmy.
Další témata (např. alternace, krypografie, ...)
Podmínky absolvování předmětu
Výskyt ve studijních plánech
Výskyt ve speciálních blocích
Hodnocení Výuky
Předmět neobsahuje žádné hodnocení.