Zápočet 10. 1. 2013

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.
Krakonoš
Matfyz(ák|ačka) level I
Příspěvky: 14
Registrován: 29. 1. 2009 11:31
Typ studia: Informatika Mgr.

Zápočet 10. 1. 2013

Příspěvek od Krakonoš »

Ahoj,

tak dnes to bylo lehoučké, že už to lehčí být nemohlo. Čepek prohlásil, že seznam na webu není asi aktuální a tak zvolil něco, co tam určitě je a dělalo se to na cvičení :-)

a) Mějme množiny S_i, i = 1..n po dvou disjunktní, S a množinu I=\{A \subseteq S : \forall i |A\cup S_i|\leq 1\}. Dokažte, že (S,I) je matroid. (Takový ten středně těžký matroidový jako má na webu.
b) Najděte stok v grafu zadaném maticí sousednosti na \matcal{O}(n) přístupů do paměti.
c) Zkonstruujte optimální VP pomocí blackoboxu řešícího rozhodovací verzi.
Odpovědět

Zpět na „TIN062 Složitost I“