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-04 18:40:41..

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


Zkouška 20.12.2007 17:00


1. Goldberg pro graf s kapacitami hran = 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???


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ář)]