[ZK] 13.6.2011 (posledni termin pro opozdilce)

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

[ZK] 13.6.2011 (posledni termin pro opozdilce)

Příspěvek od fox »

Zdravim,

nekdo kdo se chysta na zkousku 13.6.2011 a ma zajem o nejake spolecne opakovani/uceni?
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] 13.6.2011 (posledni termin pro opozdilce)

Příspěvek od pasky »

Tahle pisemka byla snadna, pokud jste meli jeden napad, nebo se aspon chytli a stihli zuzitkovat Cepkuv hint ve 2/3 zkousky ("uvedomte si, ze takovehle grafove veci se casto dokuzuji nejdriv zvlast pro SS komponenty, pak pro acyklicke grafy, pak pro obecne grafy (ty dva pripady dohromady)"). Jinak to bylo neprijemne, protoze oba priklady byly skoro to same. Kazdopadne jednomu cloveku rikal, ze se s nim da domluvit na dalsim opravnem terminu, bude tu do konce cervna...

O co slo:

1. Je dan orientovany graf G=(V,E). Jeho tranzitivni redukce se definuje jako graf G'=(V,E'), aby G a G' mely shodny tranzitivni uzaver a E' byla minimalni. Navrhnete a dokazte polynomialni algoritmus vyrabejici redukci.

2. Je dan orientovany graf G=(V,E). Jeho tranzitivni podredukce se definuje jako podgraf G'=(V,E'), kde E' \subset E a plati, ze G a G' maji shodny tranzitivni uzaver a E' je minimalni. Dokazte, ze toto je NP-uplny problem. Tedy NP-uplnost nasledujiciho problemu:

Instance: orientovany graf G=(V,E), cislo k \in N
Otazka: existuje tranzitivni redukce grafu G s nejvyse k hranami? (|E'| <= k)


Jen velmi heslovite (jak jsem zhruba tapal)... ano, je to to same, ale uz ze zadani vime, ze pokud musime v redukci pouzivat pouze stavajici hrany, je to NP-tezke, pokud si muzeme hrany ponapajet sami, uz to lze resit rychle. Nejprve je treba si uvedomit, ze graf je orientovany, takze nestaci postavit kostru. ;-) No jo, tak jake mohou byt problemy... jednak hrany, ktere preskakuji v tranzitivnich retizcich nejake vrcholy, druhak hrany navic uvnitr cyklu.

Takhle jsem se placal, az hint mne konecne nakopl. Rozeberu-li pripady, s SS komponentami si mohu poradit tak, ze je pretransformuji na cyklus prochazejici vsehny vrcholu uvnitr a v puvodnim grafu je pro dalsi ucely zkontrahuji do jedineho vrcholu. Zbyde mi usmerneny acyklicky graf, musim si ale rozmyslet, jak ho prochazet, abych nepropasl zadnou zbytecnou hranu. Cepek pak ukazal trivialni zpusob - proste v tomhle grafu beru kazdou hranu, zkusim ji odebrat a testuji, zda se zmenil tranzitivni uzaver. Ja vymyslel slozitejsi, ale trochu rychlejsi - pro kazdy vrchol si spocitam rank: velikost tranzitivniho uzaveru vrcholu, tedy pocet vrcholu, do kterych z nej dokazu dojit. Rank nam pak jednoznacne urci poradi vrcholu - staci opakovane poustet DFS z vrcholu s nejvetsim rankem a deti take brat sestupne dle ranku; ignorovat budu pouze dopredne hrany, zbytek opisu do redukce. Je celkem videt, ze hrany navic jsou prave jen ty dopredne, vsechny ostatni prinaseji oproti konkurentum nejaky vrchol navic.

Co se tyce NP-uplnosti, uvedomi-li si clovek, jak nalozit s SS komponentami, muze to uz byt nasnade - nemusim-li vyuzivat existujici hrany, staci postavit cyklus naprosto arbitrarne hned; pokud ale musim vyuzivat existujici hrany, je postaveni cyklu pres vsechny vrcholy doslova Hamiltonovska kruznice! Tedy muzu (neorientovanou) HK prevest na TpU; neorientovane hrany nahradim dvojicemi opacne jdoucich orientovanych, pokud byla HK v puvodnim grafu, je tohle SS graf. Najdu TpU, pokud pokyrva vysledny uzaver vsechny vrcholy a ma prave |V| hran, musi to byt hledana HK. (A naopak HK v puvodnim grafu dava TpU v tom orientovanem.)


Na ustni ulohy jsme prezili z prvni pulky jen dva, kolega dostal pseudopolynomialni algoritmy (co to je a priklad) a NP-tezkost, ja jsem mel za ukol popsat nejakou ulohu, ktera nelze resit s konstantni pomerovou chybou (nakonec jsme dokongvergovali k prikladu z prednasky na TSP, umime-li resit s pomerovou chybou r, muzeme pomoci toho resit HK tak, ze graf HK zuplnime a stare/nove hrany vhodne ohodnotime podle r,n, aby TSP byl nucen vybrat HK; potreboval jsem par hintu, takze za dva).
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] 13.6.2011 (posledni termin pro opozdilce)

Příspěvek od fox »

Zbývá jen dodat, že podle všeho bude ještě vypsán jeden termín.
Monty
Matfyz(ák|ačka) level I
Příspěvky: 12
Registrován: 19. 1. 2009 00:36
Typ studia: Informatika Bc.

Re: [ZK] 13.6.2011 (posledni termin pro opozdilce)

Příspěvek od Monty »

Nevite nekdo, jestli termin vypise do SISu nebo se musi termin domluvit s nim podle poctu zajemcu?
Odpovědět

Zpět na „TIN062 Složitost I“