http://forum.matfyz.info/viewforum.php?f=172 letošní ADSII na foru
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, zkuste si to...
3. z přednášky...
3* nedělal jsem :-)
JM