Fórum studentů MFF UK

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 )
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 Nicmene me navodnymi otazkami dovedl k tomu, ze ziskam takovy graf, jehoz kostra ma prumer <= 2*sqrt(n), coz v obecnem rovinnem grafu neni.

Ja mel:

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

tot vse

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!

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.