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

<{ForumPost(poster="macekt", timestamp=2010-01-18 16:17:20)}>
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.
<{/ForumPost}>

<{ForumPost(poster="hardwire", timestamp=2010-01-18 16:33:27)}>
Ja sem na ustnim dostal:  
1) definovat PRF, vypsat vlastnosti  
2) dokazat Savicovu vetu
<{/ForumPost}>

<{ForumPost(poster="Flavius", timestamp=2010-01-19 11:23:08)}>
- 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).
<{/ForumPost}>

<{ForumPost(poster="Bizon", timestamp=2010-01-20 14:13:24)}>
Já jsem dostal:  
1) definovat K a K<sub>0</sub>, 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..
<{/ForumPost}>

<{ForumPost(poster="Lucas", timestamp=2010-01-25 16:51:30)}>
Nemohol by sem niekto hodit riesenia prikladov ? .. Zasekol som sa uz na prvom. Diky
<{/ForumPost}>

<{ForumPost(poster="random", timestamp=2010-01-27 11:09:44)}>
Nema, prosim, nekdo sesit z cviceni na pujceni ci zaslani v el. podobe za bonbonieru? Prijedu si pro nej
<{/ForumPost}>