Probraná látka 09/10

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.
Boris
Matfyz(ák|ačka) level I
Příspěvky: 10
Registrován: 14. 1. 2005 23:48

Probraná látka 09/10

Příspěvek od Boris »

Čau,
učím se na páteční zkoušku ze složitosti a nevím přesně co se ještě mám učit a co ne, tak prosím poraďte někdo, kdo jste chodili na přednášky :)
Z minulých let ze slajdů i ze sylabu vypadly různé haldy (fibonacciho, binomiální ..) a operace s nima, zato přibyly v sylabu pravděpodobnostní algoritmy, které ve slajdech nejsou (a možná ještě něco..). Znamená to, ze Čepek zanevřel na haldy aj. a dává větší přednost teoretické stránce věci? (Ve slajdech taky není strassen - rozděl a panuj..)
Mám se učit i pravděpodobnostní algoritmy?

Díky za odpověď
Uživatelský avatar
Blaf
Matfyz(ák|ačka) level I
Příspěvky: 12
Registrován: 28. 1. 2008 12:13
Typ studia: Informatika Bc.

Re: Probraná látka 09/10

Příspěvek od Blaf »

Ahoj, myslim, ze slajdy pokryvaji prave to, co se probralo. Pravdepodobnostni algoritmy se neprobiraly.
Boris
Matfyz(ák|ačka) level I
Příspěvky: 10
Registrován: 14. 1. 2005 23:48

Re: Probraná látka 09/10

Příspěvek od Boris »

Díky. Ještě jeden dotaz, jaká asi ttak otázka by mohla být na slajdy 29-36 = definice úlohy, optimalizační úlohy, rozhodovací problémy, DTS, NTS, prostorová složitost?
Je to samostatná otázka, nebo se to využije spíš až třeba v savičově a liven-cookově větě?
Uživatelský avatar
Blaf
Matfyz(ák|ačka) level I
Příspěvky: 12
Registrován: 28. 1. 2008 12:13
Typ studia: Informatika Bc.

Re: Probraná látka 09/10

Příspěvek od Blaf »

Tezko rict, ale ty definice jsou kazdopadne potreba k tomu ostatnimu (k tem vetam a taky treba k pseudopolynomialnim alg.) a navic on se jiste muze zeptat na cokoliv.

Ja teda na zkousce jeste nebyl, potkame se tam v patek :)
Boris
Matfyz(ák|ačka) level I
Příspěvky: 10
Registrován: 14. 1. 2005 23:48

Re: Probraná látka 09/10

Příspěvek od Boris »

Hmmm. Ještě mě napadnul jeden dotaz takhle večer před zkouškou - když ze slajdů vypadnul algoritmus na hledání SSK, vypadnou i příklady z písemné části, které se na něj odkazovaly? (Zweistein a úkol 1 ze 14.1.2004)
Já doufám, že jo.

Na zítřek všem štěstí!
Odpovědět

Zpět na „TIN062 Složitost I“