Zkouška - Čepek - 11.1.2011
Napsal: 11. 1. 2011 18:32
Písemka, 3 příklady, 2 hodiny:
1) Aho-Corasickova, slova {auto, automobil, automat, tomato}, grafem znazornit mnozitu stavu a prechodovou funkci, tabulkou zpetnou a vystupni funkci (takze vlastne presne tak, jak ukazoval na prednasce)
2) Dokazat ze problem batohu je NP-uplny. K dukazu NP-tezkosti vyuzit nejaky problem z prednasky
3) Zjistit hranovou souvislost grafu pomoci toku v sitich (algoritmus na tok v sitich nebylo potreba popisovat, stacilo rict, tady zavolam podprogram, ktery najde max tok), ukazat spravnost a casovou slozitost (tj. kolikrat potrebujeme hledat max tok)
Ustni zkouska: typicky jedna otazka, ptal se na Four. trasformaci, NP-uplnost, aproximacni algoritmy, toky v sitich..
_______________________________________________________
Poznamky k pisemce:
ad 2) Problem batohu je, ze mame n predmetu s velikosti v_i a cenami c_i, kapacitu batohu b a minimalni cenu k a ptame se, zda muzeme vybrat takovou mnozinu predmetu M, aby soucet velikosti byl max b a soucet cen min k.
NP-uplnost znamena, ze je v NP a NP-tezky
a) BAT je v NP: zrejme, mame certifikat (kdyz nam da nekdo M, lehce zjistime, zda jsou splneny podminky pro vyslednou velikost a cenu)
b) BAT je NP-tezky: ukazeme tak, ze na nej prevedeme nejaky NP-tezky problem z prednasky (ne naopak), zde se uplne nabizi soucet podmnoziny, ukazujeme tedy SP -> BAT.
SP: mame cisla x_1 az x_n a ptame se, zda z nich lze vybrat podmnozinu o souctu s
prevod: polozime v_i = c_i = x_i, b = k = s
ad 3) hranova souvislost je minimalni pocet hran, ktere musime z grafu odebrat, aby se stal nesouvislym
Da se rozmyslet, ze kazdou neorientovanou hranu nahradime dveme orientovanymi (tam a zpet) a priradime jim vahu 1. Jeden vrchol zvolime pevne jako zdroj a vsechny zbyvajici postupne volime jako stok (max tok tedy hledame (n-1)krat). Minimum ze vsech maximalnich toku se rovna hranove souvislosti (protoze je to vlastne nejmensi mozny rez v grafu).
1) Aho-Corasickova, slova {auto, automobil, automat, tomato}, grafem znazornit mnozitu stavu a prechodovou funkci, tabulkou zpetnou a vystupni funkci (takze vlastne presne tak, jak ukazoval na prednasce)
2) Dokazat ze problem batohu je NP-uplny. K dukazu NP-tezkosti vyuzit nejaky problem z prednasky
3) Zjistit hranovou souvislost grafu pomoci toku v sitich (algoritmus na tok v sitich nebylo potreba popisovat, stacilo rict, tady zavolam podprogram, ktery najde max tok), ukazat spravnost a casovou slozitost (tj. kolikrat potrebujeme hledat max tok)
Ustni zkouska: typicky jedna otazka, ptal se na Four. trasformaci, NP-uplnost, aproximacni algoritmy, toky v sitich..
_______________________________________________________
Poznamky k pisemce:
ad 2) Problem batohu je, ze mame n predmetu s velikosti v_i a cenami c_i, kapacitu batohu b a minimalni cenu k a ptame se, zda muzeme vybrat takovou mnozinu predmetu M, aby soucet velikosti byl max b a soucet cen min k.
NP-uplnost znamena, ze je v NP a NP-tezky
a) BAT je v NP: zrejme, mame certifikat (kdyz nam da nekdo M, lehce zjistime, zda jsou splneny podminky pro vyslednou velikost a cenu)
b) BAT je NP-tezky: ukazeme tak, ze na nej prevedeme nejaky NP-tezky problem z prednasky (ne naopak), zde se uplne nabizi soucet podmnoziny, ukazujeme tedy SP -> BAT.
SP: mame cisla x_1 az x_n a ptame se, zda z nich lze vybrat podmnozinu o souctu s
prevod: polozime v_i = c_i = x_i, b = k = s
ad 3) hranova souvislost je minimalni pocet hran, ktere musime z grafu odebrat, aby se stal nesouvislym
Da se rozmyslet, ze kazdou neorientovanou hranu nahradime dveme orientovanymi (tam a zpet) a priradime jim vahu 1. Jeden vrchol zvolime pevne jako zdroj a vsechny zbyvajici postupne volime jako stok (max tok tedy hledame (n-1)krat). Minimum ze vsech maximalnich toku se rovna hranove souvislosti (protoze je to vlastne nejmensi mozny rez v grafu).