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.
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)
http://forum.matfyz.info/viewtopic.php?p=1773 Kdybych si to byl zkusil vyřešit, mohl jsem to odevzdat ještě dřív:). — Adamjinak po tehle pisemne casti nasledovala este ustni cast kde kazdemu zadal jiny problem