Písemka
Jsou na ni 2 hodiny (možná na to nechal ještě o trochu víc), je to 5 příkladů a pro postup na ústní je potřeba mít aspoň 2. Počet správně vyřešených příkladů pak taky do jisté míry určuje, o jakou známku budete hrát na ústním.
Zadání (verze A):
1) Nechť e je libovolné přirozené číslo. Rozhodněte, zda množina
2) Nechť A je rekurzivní množina a nechť B je množina, pro kterou platí, že
3) Ukažte, že existuje primitivně rekurzivní funkce f(x, y), pro kterou platí, že
4) S pomocí některého problému probíraného na přednášce ukažte, že problém "Součet podmnožiny" je NP-úplný:
Instance: Množina A n prvků, každý má váhu s(a), a přirozené číslo T.
Otázka: Existuje nějaká podmnožina A se součtem vah jejích prvků rovným T?
5) Ukažte, že úloha hranového pokrytí je polynomiálně řešitelná:
Instance: graf G=(V,E)
Cíl: Najít množinu hran takovou, že pokrývá všechny vrcholy a má minimální velikost (co do počtu hran).
Hint: V grafu lze v polynomiálním čase najít maximální párování co největší velikosti.
Ústní
2 otázky, jedna z vyčíslitelnosti a druhá ze složitosti. V naprosté většině se jednalo o větu s důkazem.
Já jsem dostal:
1) f je ČRF, právě když graf f je rekurzivně spočetná množina.
2) Dokázat, že kachlíkování je NP-úplný problém.
Postřehy
Písemka celkem lehká, u ústní je spousta času na přípravu, ale pak se v tom celkem dost šťourá a chce vysvětlit a definovat všechno možný okolo.
