[Zk] 20.1.2012

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.
strky
Matfyz(ák|ačka) level I
Příspěvky: 13
Registrován: 24. 1. 2006 15:15
Typ studia: Informatika Bc.
Kontaktovat uživatele:

[Zk] 20.1.2012

Příspěvek od strky »

1.
Problem: Hamiltonovska kruznice pro nadkubicke grafy (HM>3)
Instance: Neorientovany graf G ve ktorem ma kazdy vrchol stupen alespon 4.
Otazka: Existuje v G Hamiltonovska kruznice?

Navrhnete polynom.algoritmus (s co najlepsi casovou zlozitosti) resici problem(HM>3) nebo dokazte, ze je problem (HM>3) NP uplny

2.
P: Nezavisla mnozina pro acyklicke grafy (NMAG)
I: Acyklicky neorientovany graf G a cislo k patri N.
O: Existuje v G nezavisla mnozina velkosti k?

Navrhnete polynom.algoritmus (s co najlepsi casovou zlozitosti) resici problem(NMAG) nebo dokazte, ze je problem (NMAG) NP uplny.
HonzaK
Matfyz(ák|ačka) level II
Příspěvky: 71
Registrován: 28. 9. 2007 17:36
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: [Zk] 20.1.2012

Příspěvek od HonzaK »

Co se ustniho tyce, tak ja jsem dostal otazku, zda existuje nejaky problem, pro ktery neni aprox. algoritmus s konst. pomerovou chybou, uvedl jsem tedy obecnou variantu TSP s dukazem, ze pokud P =/= NP, tak nelze aproximovat s chybou <= pevne R. Jelikoz zkouseni probihalo v mirnem casovem skluzu, zeptal se me pak uz jen letmo na UPAS pro SP (jen co to je a vzhledem k cemu je polynomialni). U otatnich, kteri byli zkouseni se mnou, si pamatuji otazky: prevod VP na SP, aproximacni alg. pro TSP s trojuhelnikovou nerovnosti, definice grafoveho matroidu, dukaz Cook-Levinovy vety.

Obecne se da rict, ze pokud cloveku neco chybi v pisemce, tak se na ustnim obvykle zameri na otazky, ktere se toho tykaji - tzn. pokud v pisemce chybi dukaz NP-U nejakeho problemu, lze nejspis na ustnim ocekavat dukaz NP-uplnosti neceho z prednasky...

Preji hodne stesti vsem dalsim!
Kubees
Matfyz(ák|ačka) level II
Příspěvky: 65
Registrován: 12. 1. 2007 22:22
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: [Zk] 20.1.2012

Příspěvek od Kubees »

Ja mel:

1. Aproximacni algoritmus pro TSP - popsat, jaka je podminka (trojuhelnikova nerovnost), jaka je chyba, dukaz
2. Grafovy matroid - jen definice

tot vse
peci1
Matfyz(ák|ačka) level II
Příspěvky: 86
Registrován: 21. 1. 2009 20:08
Typ studia: Informatika Bc.

Re: [Zk] 20.1.2012

Příspěvek od peci1 »

Ustni:
1) Veta o planarnim separatoru (hezky celou; chybelo mi tam par detailu (nekde dopocitat nejakou nerovnost atd.), ale to s klidem presel, kdyz videl, ze hlavni myslenka je z textu zrejma; ocividne se mu to nechtelo cist cele dopodrobna :-D )
2) Jestli znam problem, ktery je v rozh. verzi lehky, ale #varianta je #P-uplna (falzifikace SATu).

Jinak teda na ustnim clovek dostane jednu vec, kterou ma ukazat poradne, tam i Cepek rejpe, jestli tomu clovek opravdu rozumi. Dalsi otazka (popr. otazky) jsou uz jen takove povrchove, aby videl, ze clovek ma tuseni tak nejak ve vsech oblastech.

Zajimavy mi prisel dotaz k 1) - po preprocessingu (vyreseni 2 jednoduchych pripadu) se dostanu vlastne do stejne situace, jako v zadani (rozdelit mnozinu na 2 skoro stejne velke kusy malym separatorem). Proc te teda delam? Co tim preprocessingem ziskam navic? Nebylo mi to jasne, z takoveho nadhledu me na ten dukaz koukat nenapadlo :-D Nicmene me navodnymi otazkami dovedl k tomu, ze ziskam takovy graf, jehoz kostra ma prumer <= 2*sqrt(n), coz v obecnem rovinnem grafu neni.
Odpovědět

Zpět na „TIN062 Složitost I“