Deprecated: Function set_magic_quotes_runtime() is deprecated in /DISK2/WWW/lokiware.info/mff/wakka.php on line 35 Matfiz : AlgoritmyADatovéStruktury/ZkouškaLS2007

Matfiz : AlgoritmyADatovéStruktury/ZkouškaLS2007

Algoritmy a datové struktury — zkouška LS 2007

Zkouška 29.6.2007

1. Dokazte nebo vyvratte ze BVS s n uzly se da pomoci O(n) rotaci (definovanych u CC stromu, proste rotace bez prebarvovani) zdegenerovat na linearni seznam(t.j kazdy uzel ma maximalne jednoho syna).

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.

řešení

no dneska byla poměrně těžká písemná :( vyhazoval docela dost, 1,5bodu minimum pro postup (jestli nekdo budete mít náladu nechcete doplnit důkazy? :))
1) platí (dokázat)
2) Otevřené adresování – Kvadratické zkoušení (dokázat)

tuto dvojku staci dokazat matematickou indukciou, ktoru postavis z nasledujuceho:

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
h(x, 0) + 1 = h(x, 0) + 1/2 + 1/2 ... plati
2- nech plati pre 2, 3, ..., i – 1, dokazeme ze plati pre i
h(x, i – 1) + i =(ind. predp.) h(x, 0) + (1/2)(i – 1) + (1/2)(i – 1)^2 + i = h(x, 0) + (1/2)i + (1/2)i^2
ked to vsetko roznasbime tak sa to vsetko poodcitava a dostaneme 0 = 0, co je s velkou pravdepodobnostou vyrok pravdivy:)
takze sme dokazali, ze dane kvadraticke skusanie s koeficientami c = d = 1/2 rata tie iste adresy ako vztah v zadani. q.e.d — nardew

3) lehce modifikovaný Dijsktra, pomerne jednoduchy (nezapomente zminit proc ho muzete pouzit: pouzekladne hrany, proc se nezacykli atd...)

Zkouska 26.6.2007

pisomna

http://forum.matfyz.info/viewtopic.php?t=3425

ustna

na ustnej som dostal median, popis, dokaz, zratanie konstanty. dalej viem ze kolegovia mali kruskala a triedenie v O(n), potom som tam uz nebol — nardew

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.

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

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)