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 LS 2007
Přihlášení:  Heslo:  
Matfiz: AlgoritmyADatovéStruktury/ZkouškaLS2007 ...
Hlavní Stránka | Seznam Stránek | Poslední Změny | Poslední Komentované | Uživatelé | Registrace |
Toto je stará verze stránky AlgoritmyADatovéStruktury/ZkouškaLS2007 z 2007-06-01 18:12:16..

Algoritmy a datové struktury — zkouška LS 2007

Zkouska 1.6.2007

pisemna

1. PRAVDEPODOBNOSTNI k-TY PRVEK
(takhle nejak – moc nevim)
mate randomizovany algoritmus pr vybrani k-teho nejmensiho rpvku, ktery pracuje takhle
– krok 1 – vybere nahodne pivota
– krok 2 – pokud je pivot to co hledame vrat ; konec
– krok 3 – podle pivota rozdeli vstup na A a B ; plati, ze |A|+|B|=n-1
– krok 4 – pokud jsou A nebo B |vetsi| nez C; zahodi pivota; opakuj krok1
– krok 5 – rekurzivne pokracuj do te casti A nebo B kde je hledany prvek a posun jeho poradi
jasne mame horni odhad pro slozitost
T(n) = Theta(n) * S(n) + T(c * n)
kde Theta(n) je za prerozdeleni a S(n) je prumerny pocet pokusu na vybrani jednoho pivota.
UKOL: dejte horni, asymptoticky tesne odhady pro T(n), pokud a) c=1/2 b) c=3/4


2. TRIATLON
mate orientovany nevazeny graf, kde kazda hrana muze byt plavaci, na kolo, nebo behaci, nebo lib. kombinace. Naleznete v case O(n+m) veschny vrcholy, ktere jsou ze zadaneho startovniho vrcholu dostupne “triatlonove”. Tzn. nejdriv plavete 0,1,... hran, pote 0,1,... hran jedete na kole, a nakonec 0,1,... hran bezite.


3. (zadani bylo dost nesikovne)
Dokaz, ci vyvrat: G=(V,E); W: E-> N (hrany maji vahy); mnozina hran e, ktere jsou pro nejaky rez s=(V\S, S) grafu G lehke, tvori kostru.
Lehka hrana je hrana ktera vede z S do V\S a ma nejmensi vahu...
--ví někdo vůbec, jak to zadání bylo myšlený? já dostal 1/4 bodu asi za snahu. tk.

Skuska 30.5.2007

písemná


Na písemnou je jedna hodina. Když odevzdáte dřív, můžete hned pokračovat ústní.


1.
MFFSORT(A,i,j)
{
if (A[i] > A[j]) swap (A[i], A[j]);
if (i + 1 < j)
{
k = spodna_cela_cast(j – i + 1); //Na tom threadu, co je na nej odkaz dole bylo spodna_cela_cast( (j – i + 1) / 3 ), tak predpokladam, ze to bylo i tady – Martin?
MFFSORT(A, i, j – k);
MFFSORT(A, i + k, j);
MFFSORT(A, i, j – k);
}
}
Dokazte alebo vyvratte: alg. utriedi dane pole A


2.
Urcte zlozitost alg. z (1.)


3.
na vstupe [x_i, y_i],(i = 1..n) su bunky gridu p x p
2 bunky su susedne, ak |x_1 – x_2| <= 1 && |y_1 – y_2| <=1
Napiste alg, ktory uci v O(n) ci vstup obsahuje susedne bunky.
Mozte si alokovat pole velkosti O(n)


Tady u toho tretiho prikladu bylo v pohode pouzit hashovani podle obou souradnic (bez blizsiho urceni hashovaci funkce)
Pak uz staci pro kazdej prvek kouknout do hashovaci tabulky na jeho osm potencialnich sousedu jestli tam jsou.
KF

ústní

jinak po tehle pisemne casti nasledovala este ustni cast kde kazdemu zadal jiny problem

(ja jsem mel dokazat slozitost quicksortu v prumernem pripade a kdyz zjistil ze vubec netusim tak rek ze pisemec mam peknej tak at mu este reknu jak funguje floyd-warsall)
(dalsi lidi co tam byli se mnou meli povidat o hashovani, rict jak funguje a okecat dukaz strasena a neco s radixsortem, to sem moc nepobral o cem vsem mluvil)

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