| Název předmětu | Vyčíslitelnost a složitost |
|---|---|
| Kód předmětu | KMI/VYSLO |
| Organizační forma výuky | Přednáška + Cvičení |
| Úroveň předmětu | Bakalářský |
| Rok studia | nespecifikován |
| Semestr | Zimní |
| Počet ECTS kreditů | 4 |
| Vyučovací jazyk | Čeština |
| Statut předmětu | Povinný |
| Způsob výuky | Kontaktní |
| Studijní praxe | Nejedná se o pracovní stáž |
| Doporučené volitelné součásti programu | Není |
| Vyučující |
|---|
|
| Obsah předmětu |
|
Úvod do teorie vyčíslitelnosti: Definice Turingova stroje (TS), formalizace pojmu výpočet (konfigurace, apod.), jazyk přijímaný TS, jazyk rozhodovaný TS, turingovsky vyčíslitelná funkce, Church-Turingova teze. Varianty TS: TS s oboustranně nekonečnou páskou, vícepáskový TS a jejich ekvivalence se základní verzí TS. Univerzální TS: Definice, popis činnosti. Jazyky a problémy: Částečně rekurzivní a rekurzivní jazyky, rozhodovací problémy, převeditelnost rozhodovacích problémů na jazyky, existence jazyků, které nejsou částečně rekurzivní. Jazyky, které nejsou rekurzivní, a problémy, které nejsou algoritmicky řešitelné: problém zastavení TS, redukce mezi problémy, ekvivalence bezkontextových gramatik, Riceova věta a její aplikace. Složitost: složitost algoritmů a problémů. Základní třídy složitosti: Třída PTIME, nedeterministické TS a třída NPTIME. NP-úplné problémy, vybrané NP-úplné problémy, dokazování NP-úplnosti. Prostorová složitost, třídy PSPACE a NPSPACE, Savitchova věta. PSPACE-úplné problémy. Úvod do problematiky aproximačních a pravděpodobnostních algoritmů.
|
| Studijní aktivity a metody výuky |
| Přednášení, Demonstrace |
| Výstupy z učení |
|
Studenti se seznámí se základními pojmy z vyčíslitelnosti a složitosti.
1. Znalost Rozpoznej neřešitelné a řešitelné problémy a jejich výpočetní složitost. |
| Předpoklady |
|
nespecifikováno
|
| Hodnoticí metody a kritéria |
|
Ústní zkouška, Písemná zkouška
Aktivní účast v hodině. Plnění zadaných úkolů. Složení ústní (příp. písemné) zkoušky. |
| Doporučená literatura |
|
| Studijní plány, ve kterých se předmět nachází |
| Fakulta | Studijní plán (Verze) | Kategorie studijního oboru/specializace | Doporučený semestr | |
|---|---|---|---|---|
| Fakulta: Přírodovědecká fakulta | Studijní plán (Verze): Informatika (2020) | Kategorie: Informatické obory | 3 | Doporučený ročník:3, Doporučený semestr: Zimní |
| Fakulta: Přírodovědecká fakulta | Studijní plán (Verze): Informatika pro vzdělávání maior (2024) | Kategorie: Informatické obory | 3 | Doporučený ročník:3, Doporučený semestr: Zimní |
| Fakulta: Přírodovědecká fakulta | Studijní plán (Verze): Bioinformatika (2021) | Kategorie: Informatické obory | 3 | Doporučený ročník:3, Doporučený semestr: Zimní |
| Fakulta: Přírodovědecká fakulta | Studijní plán (Verze): Informatika - specializace Programování a vývoj software (2021) | Kategorie: Informatické obory | 3 | Doporučený ročník:3, Doporučený semestr: Zimní |
| Fakulta: Přírodovědecká fakulta | Studijní plán (Verze): Informatika - specializace Obecná informatika (2021) | Kategorie: Informatické obory | 3 | Doporučený ročník:3, Doporučený semestr: Zimní |