Deprecated: Function set_magic_quotes_runtime() is deprecated in /DISK2/WWW/lokiware.info/mff/wakka.php on line 35 Matfiz : Algoritmy A Datové Struktury / Zkouška ZS 2007
Přihlášení:  Heslo:  
Matfiz: AlgoritmyADatovéStruktury/ZkouškaZS2007 ...
Hlavní Stránka | Seznam Stránek | Poslední Změny | Poslední Komentované | Uživatelé | Registrace |
Toto je stará verze stránky AlgoritmyADatovéStruktury/ZkouškaZS2007 z 2008-01-11 20:27:47..

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


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, zkuste si to...
3. z přednášky...
3* nedělal jsem :-)


JM


 
Na stránce nejsou žádné soubory. [Zobrazit soubory (formulář)]
Na stránce nejsou žádné komentáře. [Zobrazit komentáře (formulář)]