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

[Zk] 5.2.2009

Příspěvek od Boris »

Dnes jsem úspěšně (JUCHŮŮŮŮŮ!!!!) zdolal zkoušku ze složitosti.

Otázky na písemku: 2R-SAT s co nejlepší složitostí (šlo lineárně vzhledem k počtu proměnných), dále SALBL \in co-NP úplné (převod ze SATu)
Ústní: Já měl Savičovu větu, zaslechl jsem ještě Cook Levina a SP pomocí VP.
K té savičově větě se ještě ptal, k čemu jsou potřeba ty předpoklady, což jsem přesně nevěděl. Takže tedy pro ostatní: Prostorová konstruovatelnost S(n) je potřeba na to, aby se všechny konfigurace daly procházet foreachem (kdybych nevěděl, že je to prostorově konstruovatelný, nevěděl bych, kolik prostoru to zabere aa tudíž bych si to pak nemoh hodit do nějakýho seznamu, kterej budu tim foreachem procházet). S(n) >= log(n) musí být proto, že by 2^dS(n) jinak mohlo být < n, tedy menší než zadání - což je nejmenší možná velikost konfigurací.


Dohromady sem řešil jen 3 otázky (2písemná + 1 ústní) => znamená to, že se složitost zkoušky ze složitosti snižuje?
(Pravda, měl jsem všechno +- dobře (=> 1 :D ), tak mi nedával žádný doplňující dotazy)

Jak dopadli ostatní?
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: [Zk] 5.2.2009

Příspěvek od Blaf »

Ahoj, jenom doplnim, ze se me zeptal na definici #P-uplnosti a priklad #P-uplneho problemu, jehoz rozhodovaci verze je jednoduse resitelna (perfektni parovani). Napsal jsem mu i definici transformacnich funkci a souvislost NP a #P. Byl spokojenej, dal mi jednicku :) Byla to prijemna zkouska.
Zaslechl jsem jeste zadani Veta o planarnim separatoru.
Uživatelský avatar
happy
Matfyz(ák|ačka) level I
Příspěvky: 43
Registrován: 31. 1. 2007 01:24
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Zkoušení

Příspěvek od happy »

Doc. Čepek dává tento rok (2009/10) na zkoušce dva příklady. Pro
připuštění ke zkoušce je potřeba mít aspoň jeden (případné
nesrovnalosti se doťuknou před zkouškou, ale není to časté). Jeden
příklad špatně znamená snížení o stupeň (tj. v úvahu pak připadá rozsah
známek 2-4 :))

Na ústní mu záleží na důkazech, třeba větu o separátoru bez jejího
důkazu nepovažuje za zodpovězenou. (Člověka se pak zeptá jinou otázku.)
Např. u matroidů ho zajímá algoritmus pro hledání optimální množiny,
nebo spíš jeho správnost (konkrétně - pokud ji chce člověk dokazovat
indukcí - ten indukční krok, viz "Lemma 3: existence optimální
podstruktury"). Ale i napsaný algoritmus a definice považuje za "něco".
Po případné třetí otázce se ukáže, jestli to je bod dolů, nebo dva.

Ještě přidám jeden názor (diskutovalo se to ve starším vlákně): Můj
postoj k používání zaběhaných příkladů je kladný. Když se pak má člověk
učit teorii, napadají ho konkrétní příklady a protipříklady k té
teorii. Zápočet a písemná zkouška se dá udělat naučením dobře známých
příkladů, ale mně to dává smysl. Doc. Čepek je schopný pedagog a ví, co
dělá. (I když ten zápočet je pro něj možná jen filtr - aby zbytečně
nezkoušel někoho, kdo neumí převést ani jeden problém na jiný problém
- bez toho zkoušku opravdu nikomu nedá.)
Odpovědět

Zpět na „TIN062 Složitost I“