IB107 Vyčíslitelnost a složitost

Přednáška se koná v pátek od 10:00 do 11:40 každý týden během semestru v posluchárně D1. Cvičení se konají s dvoutýdenní frekvencí (vždy v sudé nebo liché týdny pro různé skupiny) počínaje druhým týdnem semestru, tj. celkem bude mít každá skupina šest cvičení během semestru. Další informace o předmětu lze nalézt na stránce předmětu v informačním systému MU.

Zkouška

Během zkouškového období jsou vypsány čtyři zkouškové termíny a to následovně: středa 2. ledna ve 13:00, pondělí 14. ledna ve 13:00, pátek 25. ledna ve 12:00 a pondělí 11. února ve 13:00. Počet studentů, kteří se mohou přihlásit na termín v pondělí je 11. února je omezený.

Splnění podmínek pro udělení zápočtu je nutnou podmínkou ke konání zkoušky a je nutné, aby toto bylo zaevidováno v ISu dva dny před zkouškou. Přihlašovat a odhlašovat se lze také do dvou dnů před zkouškou. Zkouška je písemná a trvá 90 minut; doplňující otázky v ústní části budou moci využít ti studenti, jejichž písemná část bude hodnocena stupňem B a rádi by si hodnocení zlepšili na A.

Podmínky pro udělení zápočtu

Zápočet uděluje cvičící příslušné skupiny. Pro jeho udělení je nutné získat 8 bodů z 15 bodů. Za účast na každém ze šesti cvičení lze získat jeden bod (tj. celkem 6 bodů za celý semestr). Ke konci semestru budou zveřejněny tři příklady k vyřešení formou domácích úkolů. Za úplné řešení každého z nich bude možné získat 3 body (a méně bodů za částečná řešení). Řešení příkladů bude možné odevzdávat do konce ledna 2019.

Obsah přenášek

Zde bude zveřejňován stručný obsah přednášek. Scan přednáškových materiálů lze nalézt v informačním systému MU.

Datum Obsah přednášky
21/9/2018 Definice while-programu, makropříkazy, Churchova teze, sémantická funkce while-programu
5/10/2018 Definice vyčíslitelné a totálně vyčíslitelné funkce, kódóvání while programů, věta o enumeraci, věta o parametrizaci, translační lemma, nerozhodnutelnost problému zastavení, neexistence efektivní enumrace totálně vyčíslitelných funkcí
12/10/2018 Definice rekurzivní a rekurzivně vyčíslitelné množiny, vlastnosti rekurzivních a rekurzivně vyčíslitelných množin
19/10/2018 Vlastnosti rekurzivních a rekurzivně vyčíslitelných podmnožin N a Nk, první Riceova věta
26/10/2018 Druhá a třetí Riceova věta, Turingův stroj a jeho varianty, časová a prostorová složitost programů
2/11/2018 Třídy časové a prostorové složitosti v deterministickém a nedeterministickém případě - L, P, PSPACE, EXPTIME, NL, NP a NPSPACE, TIME(f)⊆SPACE(f)⊆TIME(2O(f)), NTIME(f)⊆NSPACE(f)⊆NTIME(2O(f)) a NTIME(f)⊆SPACE(f)
9/11/2018 zájemci zváni na související přednášku prof. Dawara
16/11/2018 Polynomiálně verifikovatelné problémy, polynomiální redukce, NP-těžkost a NP-úplnost, NP-úplnost problémů SAT a CLIQUE, NSPACE(f)⊆TIME(2O(f))
23/11/2018 Ekvivalence, těžkost a úplnost množin vůči many-to-one redukcím, m-úplnost množiny K vůči rekurzivně vyčíslitelným množinám, 1-redukce, nerozhodnutelnost semi-Thueových systémů, Postova problému přiřazení a jednoznačnosti bezkontextových gramatik
30/11/2018 Savitchova věta, PSPACE=NPSPACE, PSPACE-úplnost problému QSAT
14/12/2018 Ukázka zkouškové písemky a jejího řešení

Příklady ze cvičení