[Zk] 21.1.2011

Základní přednáška o teorii složitosti algoritmů. Zhruba první polovina přednášky je věnována studiu složitosti konkrétních algoritmů různých typů (grafové, rozděl a panuj, hladové na matroidech) pracujících v polynomiálním čase. Složitost je zkoumána jak "klasicky" (složitost v nejhorším případě), tak amortizovaně. Druhá polovina přednášky je pak věnována studiu třídy NP, polynomiální převoditelnosti problémů a důkazům NP-úplnosti problémů. Závěr přednášky je věnován tématům souvisejícím se studiem NP-úplnosti: pseudopolynomiálním algoritmům a silné NP-úplnosti, početním úlohám a třídě #P.
pasky
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

Příspěvek od pasky »

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.
Next lecture on time travel will be held on previous Monday.
Uživatelský avatar
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

Příspěvek od mhb »

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...
pasky
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

Příspěvek od pasky »

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.
fox
Matfyz(ák|ačka) level I
Příspěvky: 5
Registrován: 6. 1. 2011 19:55
Typ studia: Informatika Mgr.

Re: [Zk] 21.1.2011

Příspěvek od fox »

mhb píše:Jo, souhlasim, prevody jsou tezke vymyslet bez toho, aby je clovek alespon jednou nevidel.
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 :).
Odpovědět

Zpět na „TIN062 Složitost I“