[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.

[Zk] 11.1.2011 - předtermín

Příspěvekod JiriD » 11. 1. 2011 14:02

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

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

Příspěvekod Dr.Zlo » 11. 1. 2011 22:28

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

(Info z druhe ruky)
Dr.Zlo
 


Zpět na TIN062 Složitost I

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 1 návštěvník

cron