02.06. 2010 zkouska Cepek

Úvodní přednáška o základních typech algoritmů a datových strukturách potřebných pro jejich implementaci.
Dworzaaa
Matfyz(ák|ačka) level I
Příspěvky: 8
Registrován: 11. 1. 2010 18:09
Typ studia: Informatika Bc.

02.06. 2010 zkouska Cepek

Příspěvek od Dworzaaa »

takze jako vzdy pisemna na 3 body - 1,5 bodu potreba pro to, aby clovek mohl postoupit k ustni.

1) dokazte/vyvratte: pokud vlozime do cerveno-cerneho stromu prvek a ihned jej zase odebereme, tak strom bude identicky s puvodnim stromem pred vlozenim prvku.
NEPLATI. Staci ukazat, ze po vlozeni prvku se strom zarotuje, prebarvi nebo oboje, to samy po deletu a strom uz neni identickej s puvodnim...
2) dokazte/vyvratte: mame orientovany graf,kde vede cesta mezi x a y. Pokud na to pustime DFS a na x narazime jako na prvni, pak y je jeho naslednikem (ne nutne primym).
NEPLATI. Zduvodneni nevim, pac sem to koumal na posledni minutu a snazil sem se dokazat, ze to plati :D
3) mame graf a v nem nejaky bod A, B a dalsi body. Pro kazdou hranu plati, ze je nejak spolehliva ( cislo x, pro ktere 0<=x<=1 , ktere udava s jakou pravdepodobnosti hrana neselze). Pri pruchodu se spolehlivost hran nasobi (jako pravdepodobnost...). Vymyslete a napiste algoritmus, ktery pobezi v co nejlepsim case a najde nejspolehlivejsi cestu mezi A a B.
Idealnim resenim byl modifikovany Dijkstr. Hrany je nejspis treba pred pouzitim zlogaritmovat, jinak by tam mohly vznikat zaporny cykly.. sel pouzit i Bellman-Ford, ale ten je casove narocnejsi..ale myslim, ze to proslo..

jinak u ustni sem dostal vsechno co vim o cerveno-cernych stromech..docela zalezi na vysledku pisemny casti..kdyz to mate nejak dobre, tak mate i narok na nejakou zachranou otazku, kdyby vam nesedlo tema...
jinak dalsi otazky, co sem slysel: AVL stromy, casova slozitost Quicksortu, hledani SSK, Kruskal a jako doplnujici nekdo dostal popsat, jak funguje Floyd-Warshall.
btw-za zneni druhy otazky nerucim...
Miso

Re: 02.06. 2010 zkouska Cepek

Příspěvek od Miso »

Dvojka by mala platit na zaklade tvrdenia, ktore nam Cepek dokazoval na prednaske: Y je naslednikom X v DFS strome <=> v case d(X) existovala cesta z X do Y po bielych vrcholoch. X bol objaveny skor, teda zjavne taka cesta musela vtedy existovat, kedze Y nemohol byt sedy ani cierny.

U trojky nevidim dovod na logaritmizaciu, kedze vsetky cisla su 0<=x<=1, a tak ked nasobime nejaku celkovu spolahlivost, nemoze sa tym zvysit. Spolahlivost sa bude iba znizovat a my pri Dijkstrovi vyberame vzdy nepreskumany vrchol s najvacsou spolahlivostou a Relax uskutocnime, ak je spolahlivost nejakeho vrcholu mensia, ako by sa dala dostat z aktualneho vrcholu cez nejaku hranu.
Miso

Re: 02.06. 2010 zkouska Cepek

Příspěvek od Miso »

Dvojka predsa neplati, tu je protipriklad: Y <--A <--> X, kde <--> je smycka. Ak DFS zacne v A, jedinym predchodcom Y bude A.
Odpovědět

Zpět na „TIN060 Algoritmy a datové struktury I“