[Zk] 11.1.2011 - předtermín

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.
JiriD
Matfyz(ák|ačka) level I
Příspěvky: 44
Registrován: 2. 2. 2008 09:35
Typ studia: Informatika Bc.

[Zk] 11.1.2011 - předtermín

Příspěvek od JiriD »

Ahoj,
můžu poprosit o bilanci dnešního předtermínu a otázky, které padly?
Díky, Jirka
Wenn ich morgen meinem Gott gegenüberstehe, kann ich sagen:
Ich bin unschuldig,
ich habe niemanden betrogen,
ich habe niemandem weh getan,
ausser mir selbst.

Und das wird er mir wohl verzeihen!
Dr.Zlo

Re: [Zk] 11.1.2011 - předtermín

Příspěvek od Dr.Zlo »

Na zapoctu byly priklady:
- TSP bottleneck
- SAT rozhodujici Blackbox, vrat pomoci nej v polyn. case reseni
- izomorfismus podgrafu

(Info z druhe ruky)
Odpovědět

Zpět na „TIN062 Složitost I“