[Zk] 13.02.2014

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.

[Zk] 13.02.2014

Příspěvekod Davpe » 14. 2. 2014 17:44

1) Strom s vrcholy stupně <=3. Nalézt hranu rozdělující strom na dva, že každý je <= (2n+1)/3 (úloha č. 10)
2) Zednický metr (úloha č. 11)

Oba příklady jsem měl správně.

Řešení jedničky:
DFS na graf (je to binární strom), počítám od zdola velikosti podstromů určené vrcholem v jako W(v).
Tedy W(list) = 1 a W(v) = W(levy syn vrcholu v) + 1 + W(pravy syn vrcholu v).
Najdu vrchol v, takový že W(levy syn vrcholu v) <= (n-1)/3 a W(pravý syn vrcholu v) <= (n-1)/3. Pak hrana (v, otec(v)) oddělí podstrom v velikosti <= (n-1)/3 + 1 + (n-1)/3 = (2n+1)/3

Ústní:
Příklad ÚPASu a znění těch tří lemmat. A prohlásil, že nic technického (tj. technické části důkazů) po mně nebude chtít.
Chtěl: Definici ÚPASu, zadání součtu podmnožiny a algoritmus ÚPAS pro něj. Dále ta tři lemmata. První dva dokazovat vyloženě nechtěl (moc technické), třetí už ano. Stačilo říct, že prvky seznamu tvoří geometrickou posloupnost s kvocientem 1/(1 - e/n) a že |L_i| <= log t o základu 1/(1 - e/n).

Protože jsem pokazil znění prvních dvou lemmat tak za 2.

Otázky:
První člověk co odevzdal dostal Kachlíkování a další, který neměl zednický metr dostal převod VP -> SP (tady pozor, že se to nedělá jako implikace, někdo se snažil to dělat tak, že začal: "Najdeme vrcholové pokrytí..." a Čepek na to vždycky naštvaně odpovídal že to je nemožné (čímž asi myslel najít ho polynomiálně rychle)).
Uživatelský avatar
Davpe
Matfyz(ák|ačka) level II
 
Příspěvky: 98
Registrován: 22. 9. 2010 15:07
Typ studia: Informatika Bc.
Login do SIS: pegrimed

Zpět na TIN062 Složitost I

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 1 návštěvník