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 je rekurzivní, své rozhodnutí zdůvodněte.
2) Nechť A je rekurzivní množina a nechť B je množina, pro kterou platí, že . Ukažte, že potom .
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.
[NTIN090] Základy složitosti a vyč. - Zk 18.1.2010
Re: [NTIN090] Základy složitosti a vyč. - Zk 18.1.2010
Ja sem na ustnim dostal:
1) definovat PRF, vypsat vlastnosti
2) dokazat Savicovu vetu
1) definovat PRF, vypsat vlastnosti
2) dokazat Savicovu vetu
Re: [NTIN090] Základy složitosti a vyč. - Zk 18.1.2010
- 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).
- 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).
Re: [NTIN090] Základy složitosti a vyč. - Zk 18.1.2010
Já jsem dostal:
1) definovat K a K0, 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..
1) definovat K a K0, 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..
- Lucas
- Matfyz(ák|ačka) level I
- Příspěvky: 15
- Registrován: 15. 1. 2007 20:34
- Typ studia: Informatika Mgr.
Re: [NTIN090] Základy složitosti a vyč. - Zk 18.1.2010
Nemohol by sem niekto hodit riesenia prikladov ? .. Zasekol som sa uz na prvom. Diky
Hele mozku, nemáš rád mně a ja zas tebe. Ale tohle musíme udělat a pak tě vyřídim jedním pivem.
- random
- Matfyz(ák|ačka) level II
- Příspěvky: 63
- Registrován: 30. 5. 2005 11:40
- Typ studia: Informatika Mgr.
- Kontaktovat uživatele:
Re: [NTIN090] Základy složitosti a vyč. - Zk 18.1.2010
Nema, prosim, nekdo sesit z cviceni na pujceni ci zaslani v el. podobe za bonbonieru? Prijedu si pro nej