Složitost I Čepek 23. 1. 2014

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.
mathemage
Matfyz(ák|ačka) level III
Příspěvky: 130
Registrován: 14. 1. 2011 10:03
Typ studia: Informatika Ph.D.
Kontaktovat uživatele:

Složitost I Čepek 23. 1. 2014

Příspěvek od mathemage »

Písemná
Poly algoritmus na záporný cyklus ohodnoceného digrafu - viz 13. zadání zkouškových příkladů do tramvaje (na studnici)
[Bellman-Ford s 1 iterací navíc]
NP-úplnost záporné cesty ohodnoceného digrafu - viz 14. zadání zkouškových příkladů do tramvaje
[např. z Hamilt. kruž.:
1. graf (na n vrcholech) -> digraf (s obousměrnými původními hrany)
2. nějaký vrchol s si zduplikuju na s a s'
3. ohodnotím hrany na -1
4. přidám nový vrchol t a orient. hranu s' \rightarrow t o váze n-1]

Ústní
Dneska neslyšel alg. na 2-souvislost, takže ten jsem dostal (možná strategie na učení, vylučovací metodou zjistit, jaká témata si těsně před tím zopakovat :D ). Pak ještě definice silné NP-úplnosti

Nestihl jsem přečíst všechny příklady do tramvaje, takže písemná docela chuťovka - 2. úlohu jsem vymyslel až 5 min před koncem :shock: Doporučuju si je aspoň 1 přečíst :wink:
Carpe Diem!
Odpovědět

Zpět na „TIN062 Složitost I“