2. Mame hashovaci funkci z U do (0,1,...,m-1),kde m je mocnina 2, ktera resi kolize otevrenou adresaci, vyhledavani probiha nasledovne:
a) i:=h(k); j:=0
b) over pozici i jestli tam je hledany klic nebo jestli je prazdna(v obou pripadech konci, jinak pokracuje)
c) j:=(j+1)mod m; i:=(i+j) mod m; goto b
overte ze adresace je spravna teda ze nebudu kontrolovat nakou pozici podruhe driv nez byx skontroloval vsechny ostatni pozice
urcete o jaky typ adresace se jedna. dokazte dopocitanim prislusnych koeficientu
3. Mame dan orientovany graf a vahovou funkci ktera kazde hrane prirazuje maximalni vysku vozidla ktere po dane ceste projde bez toho aby narazila na nake prekazky. Popiste co nejefektivnejsi algoritmus, ktery pro dany vrchol s urci pro vsechny ostatni vrcholy ake maximalne vysoke vozidlo sa do daneho vrxolu moze dostat.
1) platí (dokázat)
2) Otevřené adresování – Kvadratické zkoušení (dokázat)
takze indukcia bude podla i a dokazujes h(x, i – 1) + i = h(x, 0) + (1/2)i + (1/2)i^2
1- i = 1
ked to vsetko roznasbime tak sa to vsetko poodcitava a dostaneme 0 = 0, co je s velkou pravdepodobnostou vyrok pravdivy:)
3) lehce modifikovaný Dijsktra, pomerne jednoduchy (nezapomente zminit proc ho muzete pouzit: pouzekladne hrany, proc se nezacykli atd...)
http://forum.matfyz.info/viewtopic.php?t=3425 (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.
Musim potrdit z vlastní zkušenosti. Ne že bych to neuměl nebo nebyl připravenej, ale dostal jsem důkaz Euklidova algoritmu, kterej jsem se vůbec neučil, protože jsem se učil podle slajdů a v nich o něm neni ani zmínka. Tak jsem to tam skoro půl hodiny smolil a Čepek mi pokaždý řekl, že ne, že to neni ono, ať se ještě zamyslím. Až po chvíli prohlásil, že je vidět, že jsem ten důkaz neviděl a teď z voleje ho nedám, protože je netriviální. Tak se mě ještě zeptal na Univerzální hašování, a to jsem uměl dobře, jenom mě v něčem doplnil. Dostal jsem trojku. Ale je vidět, že i poté, co jsem naprosto selhal u jednoho důkazu, neměl chuť mě vyrazit. Prý kvůli písemce (měl jsem 2 body). Takže je celkem přísnej, ale vyhazuje asi nerad, když nemusí.
Jo a ještě jedna věc – když se bavil s Pepou Moudříkem, tak výslovně prohlásil, že není potřeba si pamatovat způsob konstrukce matic u Strassena nebo postup při vyvažování R-B nebo AVL stromů, to ať si v případě potřeby vygooglíme. Takže budiž to jako rada těm, kdo by měli nutkání se to učit nazpaměť. Čestmír
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)
Pak uz staci pro kazdej prvek kouknout do hashovaci tabulky na jeho osm potencialnich sousedu jestli tam jsou.
KF
http://forum.matfyz.info/viewtopic.php?p=1773 Kdybych si to byl zkusil vyřešit, mohl jsem to odevzdat ještě dřív:). — Adam
(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)