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

http://forum.matfyz.info/viewforum.php?f=172 letošní ADSII na foru

Zkouška 20.12.2007 17:00

1. Goldberg pro graf s kapacitami hran = 1

- 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???

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 :-)