Ahoj!
Zkouska dnes:
(1) Mame strom s alespon dvema vrcholy, kde kazdy vrchol ma stupen nejvyse tri. Dokazte, ze muzeme najit e takove, ktere tento strom rozdeli na dva podstromy, z nichz zadny neni vetsi nez (2n+1)/3. A navrhnete linearni algoritmus, ktery to udela.
(2) Zednicky metr. Mejme skladaci metr definovany posloupnosti segmentu \vec x, chceme zjistit, jestli jej dokazeme poskladat do pouzdra velikosti v (x_* a v jsou prirozena). Dokazte, ze je tento problem NP-uplny.
----
(1) Slo vymyslet celkem snadno, existenci e jsem dokazoval vzhledem ke korektnosti algoritmu, ktery ho hleda - ten muj pusti DFS, inkrementalne pocita pro kazdy uzel velikost jeho podstromu a jakmile je podstrom vetsi nez n - (2n+1)/3 (tzn. zbytek stromu je "dost maly"), vrati zpetnou hranu jako vysledek. Slozitost je O(2n+2m). Pri dokazovani je treba ukazat, ze
(i) nejaky uzel uz bude mit dost velky podstrom (trivialni, treba koren)
(ii) ze ten uzel nebude koren - tzn. ze budeme moci vratit nejakou zpetnou hranu (ja jsem rozebral pripady pro ruzne stupne korene a ukazal, ze nerovnosti sedi, tzn. nemuzou mit zaroven vsechny podstromy mene vrcholu, nez je potreba)
(iii) ze podstrom, ktery vracime, neni moc velky (tzn. ze jsme neskocili moc rychle z < n-(2n+1)/3 na > (2n+1)/3). To se nakonec taky ukazalo jit pomerne snadno zase nerovnicemi podle ruzneho poctu synu (nezapomente jako ja, ze pocet synu je O JEDNA MENSI nez stupen vrcholu ).
(2) Certifikat bude asi vektor s hodnot {-1,1} (podle toho, kterym smerem je slozeny ktery segment). Na polynomialni redukci vypada jako nejprirozenejsi kandidat LOUP. Nejak mi ale nedoslo, ze velikost pouzdra bude zdola omezena nejdelsim segmentem, takze nestaci se pokusit narvat metr z rozdelovanych veci do pouzdra nulove velikosti. Je to celkem trivialni thinko, ale bohuzel jsem nedostal sanci to predelat... (Pry se dodelaji nejake dalsi virtualni segmenty z nejvetsich rozdelovanych veci, asi je to pomerne technicky snadne.)
Tak se mne na usti zeptal na polynomialni prevod z VP na HK a za chvili jsem sel domu - jestli skutecne neexistuje snadnejsi zpusob, nez brutalni grafove gadgety, asi to ma sanci na miste vymyslet malokdo, a ja to bohuzel nikdy predtim nevidel - nenarazil jsem na to ani v zadnych zapiscich ci jinych materialech, tak si dejte bacha, jestli mate jasno ve vsech prevodech, ktere jsou na sladjech byt letmo zminene (a ja vul myslel, ze prevody jsou moje silna stranka ).
Jinak na ustnich padala "klasicka temata" (existence NP-uplneho problemu, UPAS, dvojsouvislost, definice #P, ...).
Mimochodem, dalsi zkousku uz pry nakonec v unoru nikdo provozovat nebude, tzn. dalsi sance v cervnu.
[Zk] 21.1.2011
-
- Matfyz(ák|ačka) level II
- Příspěvky: 89
- Registrován: 4. 1. 2005 22:57
- Typ studia: Informatika Bc.
- Kontaktovat uživatele:
[Zk] 21.1.2011
Next lecture on time travel will be held on previous Monday.
- mhb
- Matfyz(ák|ačka) level II
- Příspěvky: 50
- Registrován: 3. 2. 2008 03:38
- Typ studia: Informatika Ph.D.
- Kontaktovat uživatele:
Re: [Zk] 21.1.2011
Jo, souhlasim, prevody jsou tezke vymyslet bez toho, aby je clovek alespon jednou nevidel. Ty gadgety davaji docela smysl, ale bez "orakula" bych je nevymyslel. Nevim, jak je mozne, zes je nevidel -- doporucuji poznamky ze Studnice vedomosti jmenem "Complexity.pdf", tam jsou skoro vsechny celkem ctive. Ale ted je pozde radit...
-
- Matfyz(ák|ačka) level II
- Příspěvky: 89
- Registrován: 4. 1. 2005 22:57
- Typ studia: Informatika Bc.
- Kontaktovat uživatele:
Re: [Zk] 21.1.2011
Ha, diky! Zrovna tohle je snad jedine pdfko, ktere jsem pri prochazeni studnice z nejakeho duvodu preskocil. Vypada to skvele, na cerven se bude hodit.
Next lecture on time travel will be held on previous Monday.
Re: [Zk] 21.1.2011
Musim se pridat, potvrdit a zduraznit toto tvrzeni. Ja jsem zkousku nedal prave kvuli prevodum ... konkretne VP na SP a #3-SAT na #SAT ... Tak snad si je stihnu projit do cervna .mhb píše:Jo, souhlasim, prevody jsou tezke vymyslet bez toho, aby je clovek alespon jednou nevidel.