http://forum.matfyz.info/viewforum.php?f=172 letošní ADSII na foru1. 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.
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