Deprecated: Function set_magic_quotes_runtime() is deprecated in /DISK2/WWW/lokiware.info/mff/wakka.php on line 35 Matfiz : AlgoritmyADatovéStruktury/ZkouškaZS2007

Matfiz: AlgoritmyADatovéStruktury/ZkouškaZS2007

Algoritmy a datové struktury II — zkouška ZS 2007

termín v letním semetru

Zkouška 14. 2. 2008 10:00

  1. Je dán orientovaný graf G a jeho dva vrcholy s, t. Najděte maximální množinu (nebo aspoň počet) cest z s do t vrcholově disjunktních až na s a t. Hledejte polynomiální algoritmus, nebo dokažte, že problém je NP-úplný.
  2. V lineárním čase zjistěte, zda je jeden řetězec rotací druhého.
  3. Popiště (vč. šložitosti a korektnosti) algoritmus Aho-Corasicková.
  4. (*) Navrhněte hradlovou síť pro výpočet transitivního uzávěru orientovaného grafu. (Na vstupu je matice sousednosti, na výstupu matice dostupnosti.)

Řešení

  1. Pomocí toků v sítích. Je třeba ošetřit vrcholovou disjunktnost (hranová nestačí) a vysvětlit, proč je při kapacitách c(*) = 1 velikost toku stejná jako počet hledaných cest, resp. jak odpovídají zlepšující cesty těm hledaným. Vrcholová disjunktnost se vyřeší nahrazením vrcholů dvěma (vstupním a výstupním) spojeným hranou (e o kapacitě c(e) = 1). Zbytek se mi úplně domyslet nepodařilo. (Co když zlepšující cesta využívá rezervy v protisměru? Co když takhle vede přes jednu hranu i více než dvě cesty, apod.? Intuitivně to vypadá, že to «půjde rozmotat», ale...)
  2. Pro řetězce α a β: &sigma := β&beta[:|β|-1], ι = α, KMP(ι,σ)
  3. Prošlo mi to i bez důkazu korektnosti.
  4. Lze v hloubce Θ(log2 n) a hradlech Θ(n3 log n). Matici n x n je třeba umocnit aspoň na n-1. A to tak, že sčítání se nahradí ORem a násobení ANDem. (Snad je jasné, jak to převést do hradel a proč to funguje.)

Jedničku šlo získat například za částečné řešení 1, úplné řešení 2 a 3 bez korektnosti (ani se neptal, něco bych snad vymyslel;)), a 4. Bonusovou čtyřku šlo použít tedy jako náhradu, pokud se vám nedařilo na něco přijít. Během zkoušky se postupně objevovaly nápovědy jako «na čtyřku lze použít maticové násobení», «trojka jde (alternativně) řešit výpočtem lexikograficky nejmenší rotace».

Jinak celkově je to IMO dost opruz, většině lidem tahle zkouška trvá déle než čtyři hodiny, což se mi zdá zbytečné.

Zkouška 17. 1. 2008 10:00

1. DFT(1,i,-1,i,1,i,-1,-i)

2. Jest dán slovník S a text T, spočtěte výskyt slov ze slovníku S v textu T. V čase nejvýše O(|S|+|T|).

3. Třídění pomocí komparátorové sítě.

Řešení

1. Nejlépe se to vyřeší jako součet geometrické řady. S rozborem případů. Neptejte se mě jak, ale když mi to ukazoval tak mu to trvalo asi půl minuty.

2. Přímé aplikaci Aho-Corasickové brání pouze požadavek, že časová složitost nesmí záviset na počtu výskytů. “Hrdlem lahve” je v tomto případě vypisování výskytů pomocí hran “out” při procházení automatem. Takže je potřeba algoritmus nějak poupravit, aby výskyty nevypisoval při průchodu textem, ale až na konci. Dá se to dělat více způsoby, ale drtivá většina z nich měla u stavů automatu nějaké čítače. Já to třeba dělal tak, že pokud jsem se dostal do nějakého stavu automatu dopřednou hranou, tak jsem buď inkrementoval jeho čítač (pokud ten stav byl slovem) a nebo jsem se podíval, jestli z něj nevede nějaká “out” hrana do jiného slova. Pokud ano, tak jsem zvýšil čítač u toho slova, do kterého vedla ta “out” hrana. Takže jsem na konci měl u všech stavů, které reprezentovaly slova, počet jejich výskytů. Mělo to ještě jeden háček – protože jsem se díval jenom na první hranu “out”, tak se mohlo stát, že jsem nepřipočítal výskyt ke slovům, která byla suffixem inkrementovaného slova. Proto bylo na konci ještě potřeba vzít postupně všechna slova, sestupně podle jejich délky, a zkompletovat jejich výskyty tak, že jsem k počtu jejich výskytů přičetl i počty výskytů slov, ze kterých do nich vedla hrana “out”. Protože jsem je bral od největšího, tak jsem měl počet výskytů delších slov spočítaný dřív, než jsem ho někam přičítal. Protože hran out je nejvýš O(počet slov), tak časová složitost vypisování byla O(počet slov), což je O(|S|). Čestmír

3. Z přednášky.

PS : Rozhodně je mírnější než doc. Čepek

P. M.

Zkouška 11. 1. 2008 10:00

1. Najděte algoritmus na spočítání obsahu mnohoúhelníka, který má pouze svislé a vodorovné hrany. Máme zadán seznam vrcholů «tak jak jdou po sobě kolem dokola».

2. Navrhněte hradlovou síť, která zjistí, zda je dané číslo (v binární soustavě) dělitelné třemi.

3. Popište a dokažte Dinicův algoritmus na hledání maximálního toku v síti.

Řesení

1. Projdu seznam vrcholů a v lineárním čase z něho vyrobím seznam svislých hran, hrany po kterých “jdu” zdola nahoru označím. V čase O(n log n) seřadím seznam hran podle x-ové souřadnice. Zametám rovinu zleva doprava svislou přímkou. Pokud je první hrana označená, pak označené hrany jsou «ziskové», ostatní «ztrátové», jinak je tomu naopak. Pamatuji si aktuální výšku (inicializovanou první hranou) a jak postupně procházím hrany, počítám obsah – ziskové hrany mi výšku pro další úsek zvětšují, ztrátové zmenšují.

2. Pro vyreseni ulohy v nejakem rozumnem case O(log n) je treba nejdriv zjistit, ze lze spocitat zbytek cisla po deleni tremi tak, ze cislo rozsekneme na pulky (doplnime zepredu potrebny pocet nul tak, aby v kazde pulce byl sudy pocet cifer) a spocitame zbytky po deleni tremi techto pulek. To lze ukazat celkem jednoduse, pak uz staci sestavit hradlo, ktere secte zbytky po deleni tremi (2 dvojciferna cisla) modulo 3. (Nad vyresenim tohodle “pak uz staci” kroku jsem stravil asi 45 minut ;)).

3. Podle přednášky.

h.

Zkouška 4. 1. 2008 14:00

1. Goldberg

formulace, korektnost, implementace, slozitost (pro c = 1)
2. Navrhnete komparatorovou sit pro zatrideni jednoho cisla do utridene posloupnosti

vstup = (a_1,a_2,...,a_n-1,x)

vystup = (setridena posloupnost)

n je vhodne (jake chcete – mocnina dvojky :), trojky, prvocislo ... )

2* jde to lepe? (ukaz ze ne)

3. mame seznam n predmetu s velikostma x_1 az x_n, taky mame tri krabicky, kazda znich ma velikost K

Existuje vhodne rozmisteni veci do krabicek tak aby se tam vesly, tzn. suma velikosti veci v kazde piksle je <=K

v polynomialnim case vzhledem ke K a n.

3* Polynomialne v n???

Riesenie

1. Ak viete to co je v skriptach, tak viete dost. Zlozitost je myslim O(nm), podla lemmy o nasytenych prevedeniach, kedze pre c=1 su vsetky prevedenia nasytene.

2. Porovnat x <> a_n/2, potom x <> a_3n/4 a a_n/2 <> a_n/4, ... kedze vzdy delime data na polovice, bude to v O(log n) case a O(n) hradlach.

2*. Kedze x treba porovnat so vsetkymi ostatnymi vstupmi, dokaz postavime na tom, ze v kazdej hladine ide porovnat len obmedzene mnozstvo vstupov, a to v k-tej hladine porovname 2^k vstupov, k=0..(log n-1).

3. Nikto nespravil podla Maresovych predstav, ale za odmenu nam poslednym povedal, ako by to malo ist (po 4h na skuske). Staci si precitat problem batohu zo skript, ale namiesto dvojic (a,b) pre aproximacny alg budeme robit 3ice (a,b,c). Eventualne, kedze c je komplementarna mnozina k a a b, zase sa to zmensi len na (a,b), a zlozitost je teda myslim O(n . k^2). Toto niekto mozno viac obkecajte, ja si to uz pametam len matne. — Pepe

Zkouška 20.12.2007 17:00

1. Spočítejte DFT(1,-1,1,-1,1,-1,1,-1)

2. Navrhněte booleovský obvod, který bude porovnávat dvě čísla v čase log(n), kde n je počet bitů většího čísla

3. Redukce z 3-SATu na hledání nezávislých množin

3* (bonusová úloha pro rychlé) jako 3, ale v grafu bude mít každý vrchol stupeň max. 4

řešení

1. čistá aplikace FFT (samozřejmě by to šlo i přímo podle vzorce DFT, ale takhle je to rychlejší a omegy se krásně nulují), výsledek byl tuším (0,0,0,0,8,0,0,0)

2. je to jednodušší obměna sčítačky (předpočítávání přenosu), zkuste si to...

3. z přednášky...

3* Jednoduse 3-sat prevedeme na 3,3-sat, tim eliminujeme moznost, aby z jednoho vrcholu vedly vice jak 4 hrany.

JM