http://forum.matfyz.info/viewforum.php?f=172 letošní ADSII na foru
Seznamy otázek z předchozích termínu přímo na web Martina Marešetermín v letním semetruJednič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é.
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ě.
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.
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.
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.
1. Goldberg
2. Navrhnete komparatorovou sit pro zatrideni jednoho cisla do utridene posloupnosti
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
3* Polynomialne v n???
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?
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
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