IB107 Vyčíslitelnost a složitost

Přednáška se koná ve středu od 12:00 do 13: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 a konče 13. prosince 2019, 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í bude vypsáno pět zkouškových termínů a to následovně: pátek 3. ledna v 9:15, pondělí 27. ledna v 10:15, čtvrtek 30. ledna v 13:15, pondělí 3. února v 9:15 a čtvrtek 6. února v 14:15. Na zkoušku přijďte 10 minut před jejím začátkem; kapacita všech termínů bude omezena z důvodu kapacity posluchárny, kde se zkouška koná.

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 stupněm B a rádi by si hodnocení zlepšili na A.

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

Pro udělení zápočtu 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) a dále lze získat tři body (méně bodů za částečná řešení) každého z tří zápočtových příkladů. Řešení příkladů je možné odevzdávat do konce ledna 2020 pomocí odevzdáváren v informačním systému MU

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.

Příklady ze cvičení

• Nechť CLIQUE je problém, zda pro dané číslo k, daný graf G obsahuje k vrcholů navzájem spojených hranami. Ukažte, že CLIQUE patří do třídy NP.
• Nechť VCOVER je problém, zda pro dané číslo k, daný graf G obsahuje k vrcholů takových, že každá hrana je incidentní s jedním z těchto k vrcholů. Ukažte, že VCOVER patří do třídy NP. Dokážete nalézt algoritmus řešící tento problém v čase O(cⁿ) pro c<2?
• Edit-vzdálenost dvou slov je minimální počet operací vložení a smazání písmene, který převede jedno slovo na druhé. Nalezněte nedeterministický algoritmus, který pro dané číslo k a dvě slova délky n v čase O(n+k) rozhodne, zda jejich edit-vzdálenost je nejvýše k. Nalezněte deterministický algoritmus pro tento problém pracující v čase O(nk).
• Nechť INDSET je problém, zda pro dané číslo k, daný graf G obsahuje k vrcholů, z nichž žádná dvojice není spojena hranou. Ukažte, že problém INDSET je NP-úplný.
• Nechť 3-SAT je problém, zda zadaná formule v CNF formě, kde každá klauzule obsahuje právě tři (různé) literály, je splnitelná. Ukažte, že problém 3-SAT je NP-úplný.
• Nechť K3COVER je problém, zda daný graf G s 3n vrcholy obsahuje n vrcholově disjunktních trojúhelníků. Ukažte, že problém K3COVER je NP-úplný.
• Nechť CONN je problém, zda daný graf G obsahuje cestu mezi danými dvěma vrcholy. Ukažte, že CONN patří do třídy NL.
• Navrhněte makropříkazy pro následující: x_i=x_j+x_k, x_i=x_j*x_k, x_i=x_j div x_k a for x_i=0 upto x_j do PŘÍKAZ.
• Navrhněte, jak lze ve while-programech implementovat pole libovolné délky.
• Ukažte, že existuje totálně vyčíslitelná funkce g, t.ž. φ_g(i,j)(x,y)=φ_i(x,y)+φ_j(x,y).
• Dokažte, že sjednocení a průnik dvou rekurzivně spočetných množin je rekurzivně spočetná množina.
• Ukažte, že neexistuje vyčíslitelná funkce enumerující totálně vyčíslitelné funkce arity dva, tj., neexistuje vyčíslitelná funkce F(i,x,y), t.ž. funkce f(x,y):=F(i,x,y) je totálně vyčíslitelná pro každé i a pro každou totálně vyčíslitelnou funkci f(x,y), existuje i, t.ž. f(x,y)=F(i,x,y).
• Rozhodněte, zda platí následující: pokud A a B jsou rekurzivní množiny, pak symetrický rozdíl A a B je také rekurzivní množina.
• Rozhodněte, zda platí následující: pokud A je rekurzivní a B je rekurzivně spočetná množina, pak symetrický rozdíl A a B je rekurzivně spočetná množina.
• Rozhodněte, zda platí následující: pokud A a B jsou rekurzivně spočetné množiny, pak symetrický rozdíl A a B je také rekurzivně spočetná množina.
• Dokažte, že každá nekonečená rekurzivní množina má podmnožinu, která je rekurzivně spočetná, ale není rekurzivní.
• Dokažte bez použití Riceových vět, že množina těch i, že se i-tý while-program na vstupu 1 zacyklí, není rekurzivně spočetná.
• Nechť A je množina těch i, že φ_i je prostá funkce. Je množina A rekurzivně spočetná? Je její doplněk rekurzivně spočetný?
• Nechť A je množina těch i, že φ_i je bijekce N na N. Je množina A rekurzivně spočetná? Je její doplněk rekurzivně spočetný?
• Dokažte, že pokud A≤_mK, pak A≤₁K.