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.

Podmínky pro získání 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.

Zkouška

Během zkouškového semestru budou vypsány čtyři zkouškové termíny a to v následujících dnech: středa 2. ledna, pondělí 14. ledna, pátek 25. ledna a pondělí 11. února. Udělení zápočtu je nutnou podmínkou ke konání zkoušky.

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

Příklady ze cvičení