[zk] 16.2.09

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.
Uživatelský avatar
Myshaak
Matfyz(ák|ačka) level III
Příspěvky: 161
Registrován: 18. 1. 2006 22:29
Typ studia: Informatika Mgr.
Bydliště: Tanvald / Troja A820

[zk] 16.2.09

Příspěvek od Myshaak »

Tak pro ucely statistiky, dneska zadani bylo:

1) ze soucet prvku matice (B*BT) (B je matice incidence) je sude cislo
2) graf G, vrcholy s != t, napsat alg. na najiti k hranove disj. cest (pokud existuji)
3) priklad s tranzitivni redukci (ukazat, ze je NPU)

zacalo se v 9, ja blbec to odevzdal za hodinu, ze pak do odpoledne, nez bude vyhlaseni, se stihnu jeste neco naucit (asi tak posl. 2 prednasky jsem moc neumel). Jenze pry ze to opravi a vezme nas (byli jsme 3 takovi statecni) hned! A sakra!!! :D Ale Cepek je u ustni casti v pohode. Dostal jsem nejprve jak je to s aprox. alg pro TSP (v obec. pripade, tj. mel jsem ukazat, ze neni Aprox. Alg. s konst. pomerovou chybou). Pak se jeste zeptal na zneni vety o planarnim separatoru (bez dukazu, ale zato se slozitosti) - a pak konec. Fuuu, trochu se stestim, ale to preci preje odvaznym! :)

Jinak pro ty, co zkousku nestihli/nedali - zrejme vypise jeste termin v lete.
"Go for the eyes Boo, go for the eyes! Yeahh!!"
Uživatelský avatar
Isidor
Adoptoval Tutcheka
Adoptoval Tutcheka
Příspěvky: 247
Registrován: 8. 12. 2004 23:22
Typ studia: Informatika Mgr.
Bydliště: mám
Kontaktovat uživatele:

Re: [zk] 16.2.09

Příspěvek od Isidor »

skusal ma Kucera - Cook-Levinovu vetu
tak som popisal definicie DTS, NTS, tried NP/NP-tazke/NP-uplne, KACHL, vetu z prednasky ("to i rok si pamatujete, jo?" :D) + prevod na kachlicky...trochu som domotal posledny typ, resp. spodnu hranu siete, ale to sme si rychlo ujasnili. Potom sa este opytal na to, preco mozme predpokladat prazdne znaky na paske na konci. Celkovo pohoda (+ pisomka) = 1, uff
dalsi termin - "mozna, v lete nebo zari"
Inteligentních lidí je menšina. Demokracie je vláda většiny.
Odpovědět

Zpět na „TIN062 Složitost I“