Zkouška - Čepek - 11.1.2011

Pokračování přednášky TIN060 Algoritmy a datové struktury I
istien

Zkouška - Čepek - 11.1.2011

Příspěvek od istien »

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).
Uživatelský avatar
DocX
Matfyz(ák|ačka) level I
Příspěvky: 6
Registrován: 1. 2. 2010 18:52
Typ studia: Informatika Bc.
Bydliště: A611

Re: Zkouška - Čepek - 11.1.2011

Příspěvek od DocX »

Hm :) Nějak jsem si nevšiml kategorie ZS a bylo mi divné, že by zde nebyla kategorie pro ADS2.. Takže tady je moje, ale je to to samé :D

Zkouška 11.1.2011

1) Aho-Corasick:

Slova: {auto, automobil, automat, tomato}
Nakreslete graf znázorňující stavy a přechodovou funkci. Zpětnou a výstupní fci zapište tabulkou.

2) Problém batohu

v1, ..., vn velikosti předmětů
c1, ..., cn ceny předmětů
k kapacita batohu
r požadovaná cena

Problém BAT: Existuje podmnožina předmětů, jejíž celková cena je alespoň r a vejdou se do batohu?

Otázka: Je tato úloha NP-úplná? Dokažte pomocí nějaké úlohy, kterou jsme brali na přednášce (KLIKA, SP, ROZ, ....)

3) Hranová souvislost

Označme HS(G) hranovou souvislost grafu G. HS(G) je minimální počet hran, po jejichž odebrání bude graf G nesouvislý.
Napište algoritmus hledající HS(G) v polynomiálním čase vzhledem k velikosti dat takový, že jako podprogram bude využívat nějaký algoritmus hledání maximálního toku v síti (nezajímá nás jaký konkrétní). Zdůvodněte korektnost.
Napište časovou složitost vlastních operací algoritmu a počet, kolikrát se spustí podprogram hledání maximálního toku.

Poznámky
- Aho-Corasick je celkem jednoduché, ale pozor na výstupní a zpětnou funkci :)
- U batohu pozor na to, že je třeba převádět z něčeho na batoh, opačně to jde dost špatně ;)
Odpovědět

Zpět na „TIN061 Algoritmy a datové struktury II“