od pasky » 21. 1. 2011 12:56
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.
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 [url=http://docs.google.com/viewer?a=v&q=cache:niGEVDuRPw0J:www.cs.unm.edu/~saia/362-spring2006/lec/ho-lec24.pdf+vertex+cover+hamiltonian+cycle&hl=cs&gl=cz&pid=bl&srcid=ADGEESi4A9fAuvfTInJjQdsVZmhHUNF9HPf0rEnprq_lxB1JR1kRUBaS2Np3japPf0W1JtSgMwS6dGlJfJITuH0nlOquPuGCpzxBt2itiAe7AVvGH7dK3F03iUuB0Hlrb_Tw5OqOx29W&sig=AHIEtbRCU0ABhJ7fcUiOEUzhEt_P_S8yOw]brutalni grafove gadgety[/url], 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.