[Skuska] 10.2.2009

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.
Tresko
Matfyz(ák|ačka) level I
Příspěvky: 28
Registrován: 9. 6. 2005 22:19

[Skuska] 10.2.2009

Příspěvek od Tresko »

Pisomka:
(v zatvorke je cislo zo zoznamu skuskovych prikladov, podrobnejsie na http://forum.matfyz.info/viewtopic.php?f=203&t=5021)

(6) 1. Dokazte nebo vyvratte: Mejme orientovany graf, ve kterem $ orientovana cesta mezi vrcholy U→V, pricemz pri prochazeni grafem narazilo DFS jako prvni na U. Pak V je v nejakem DFS stromu potomkem (ne nutne primym) U.
(7) 2. Mejme formuli F v CNF, kde se kazda promenna (ne literal!) vyskytuje nejvyse dvakrat. Otazka: Je formule F splnitelna? Vyreste 2R-SAT v polynomialnim case, uvedte asymptotickou slozitost.
(8) 3. Sablony

Ustna (co som pocul):
- planarny separator, #P, UPAS, algoritmus na 2-suvislost, prevod VP na HK, pseudopolynomialne algoritmy
Uživatelský avatar
strevlik
Matfyz(ák|ačka) level I
Příspěvky: 49
Registrován: 7. 3. 2006 10:56
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Re: [Skuska] 10.2.2009

Příspěvek od strevlik »

Ustni co jsem zase dostal ja - prevod 3 SAT - 3 BAREVNOST, silna NPU, slaba NPU.
Prevod v pohode, v ty silny jsme mu rikal vsechno kolem pseudopolynomialnich alg a ciselnych problemu, ale chtel slyset slovicka UPAS (proste jen to, dost mne to dostalo po delsi debate). Jednoho cloveka vyhodil na Cook-Levin vete (rekl jen tohle, clovek rekl ze nevi co to je a tak sel, mozna stacilo rict ze jde o kachlikovani). Pak jsem jeste slysel konsolidaci na Fib. halde.

Vsechno Kucera, co jsme pak debatovali, tak mi prijde Cepek na zkouseni lepsi.
Odpovědět

Zpět na „TIN062 Složitost I“