FPF:UIDI011 Teorie vyčíslitelnosti a složi - Informace o předmětu
UIDI011 Teorie vyčíslitelnosti a složitosti
Filozoficko-přírodovědecká fakulta v Opavěléto 2007
- Rozsah
- 0/0. 0 kr. Ukončení: dzk.
- Garance
- doc. Ing. Petr Sosík, Dr.
Ústav informatiky – Filozoficko-přírodovědecká fakulta v Opavě - Omezení zápisu do předmětu
- Předmět je nabízen i studentům mimo mateřské obory.
- Mateřské obory/plány
- Autonomní systémy (program FPF, P1801 Inf)
- Cíle předmětu
- Abstraktní počítač a Entscheidungsproblem, modely abstraktního počítače, Turingova - Churchova teze. Turingův stroj (TS), vyčíslení funkcí pomocí TS, rekurzívní a částečně rekurzívní funkce. While programy, jejich výpočetní ekvivalence s Turingovým strojem. Primitivní rekurzívní funkce: charakterizace vyčíslitelných funkcí nezávislá na výpočetním modelu. Rekurzívní a rekurzívně spočetné množiny, Riceova věta. Rozhodnutelné a nerozhodnutelné problémy, problém zastavení. Metoda diagonalizace a metoda redukce. Příklady nerozhodnutelných problémů: problém dláždění, Postův korespondenční problém, desátý Hilbertův problém. Rozhodnutelné a nerozhodnutelné vlastnosti jazyků, Chomského hierarchie. Problémy a algoritmy. Turingův stroj, míry složitosti Turingova stroje, věta o urychlení, věta o kompresi. RAM a míry složitosti stroje. Ekvivalence Turingových strojů a RAM. Složitost jejich vzájemné simulace. Vícepáskové Turingovy stroje, redukce počtu pásek, nedeterministické TS a složitost vzájemné simulace. Třídy P a NP. NP úplné problémy. Paralelní výpočty a jejich složitost.
- Další komentáře
- Předmět je dovoleno ukončit i mimo zkouškové období.
- Statistika zápisu (léto 2007, nejnovější)
- Permalink: https://is.slu.cz/predmet/fpf/leto2007/UIDI011