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-02 22:04:52..

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.


Zadaní jsi napsal dobře, stačilo říct, že pro nějaký řez může existovat více lehkých hran (když mají stejnou váhu), a pak třeba najít nějaký protipříklad.
Nejjednodušší je vzít trojúhelník, jehož strany mají stejnou váhu, tj. jsou všechny lehké pro nějaký řez, ale všechny dohromady netvoří kostru.


Taky jsem to nějak nepochopil, ale pak jsem tam sesmolil nějakej extra (poměrně velkej) graf, který měl pár hran se stejnou váhou, který dohromady se zbytkem grafu tvořily cyklus. No až na ústní části mi ten týpek co to zkoušel s Čepkem ukázal ten jednoduchej trojúhelník, tak jsem jenom přikývl hlavou. Ale uznal mi to.
Ústní byla na pohodu. Byl jsem až skoro poslední, Čepek docela pospíchal, tak mi dal jenom ukázat a dokázat Jarníka. Když jsem mu to ukázal, tak řek, že když mám 2 body z písemné a tohle jsem věděl, tak mi dá za 1. Tak jsem spokojeně odešel ;-) Jinak když jsem tam seděl a připravoval toho Jarníka, tak se bavili kolik lidí vyrazili, prý jenom 4. Takže si myslím, že se to snaží dát fakt každému. Když aspoň něco člověk ví, tak tam něco vymyslí a nevyrazí ho. MCh.

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