[NTIN090] Základy složitosti a vyč. - Zk 18.1.2010

Zkouška má dvě části - písemka a ústní:

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 $A=\{x | W_{x}=W_{e}\}$ je rekurzivní, své rozhodnutí zdůvodněte.

2. Nechť A je rekurzivní množina a nechť B je množina, pro kterou platí, že $$B,\bar{B} eq \emptyset$$. Ukažte, že potom $A{\leq}_{m}B$.

3. Ukažte, že existuje primitivně rekurzivní funkce f(x, y), pro kterou platí, že ${\varphi}_{f(x,y)}(u) \cong max\{{\varphi}_{x}(u), {\varphi}_{y}(u)\}$.

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.

Ja sem na ustnim dostal:

1. definovat PRF, vypsat vlastnosti

2. dokazat Savicovu vetu

• Nějak obkecat, co dělá UTS (tzn. jak zkonstruovat kód TS, že je to tím pádem nejednoznačné, a popsat, jakým stylem funguje).

• Dvě definice třídy NP (přes polynomiální složitost, pokud máme certifikát, a přes NTS)

Byl hodný, měl jsem z něj pocit, že už ho to zkoušení fakt nebaví a tak se mu ani nechce mi do toho šťourat, když jsem v tom měl formální chyby (ale věděl jsem, o co go).
Jinak bacha na tu 3. úlohu na písemce - není to jenom o tom rozepsat to na signum(fi_x(u) - fi_y(u))*fi_x(u) + signum(fi_y(u) - fi_x(u))*fi_y(u) + ==(fi_x(u) - fi_y(u))*fi_x(u), jde mu o to, jak vlastně vypadá ta funkce f(x, y).

Já jsem dostal:

1. definovat K a K₀, dokázat jak to vlastně je s jejich rekurzivitou, resp. spočetností

2. převod 3SAT na vrcholové pokrytí

takže z těch jednodušších otázek..

Byl jsem tak na půlce přednášek a na všech cvikách. Na zkoušku jsem se učil o víkendu - v neděli dlouho do noci. Takže v pondělí ráno jsem byl na písemce vyplesklej a totálně ji po**al -> měl jsem ty dva minimální příklady. Na ústní jsem šel jako jeden z posledních a Kučera opravdu vypadal, že už ho to moc nebaví. Já po menším výpotu všechno popsal a dokázal. On se v tom moc nerýpal (ani nebylo proč), řekl, že je škoda, že jsem tu písemku pokazil, a dal mi trojku. Celkově mi přišel v pohodě a myslím, že ten termín dopadl docela dobře - většinou jedničky a dvojky..

Nemohol by sem niekto hodit riesenia prikladov ? .. Zasekol som sa uz na prvom. Diky

Nema, prosim, nekdo sesit z cviceni na pujceni ci zaslani v el. podobe za bonbonieru? Prijedu si pro nej