02.06. 2010 zkouska Cepek

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...

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.

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