# 02.06. 2010 zkouska Cepek

<{ForumPost(poster="Dworzaaa", timestamp=2010-06-03 22:54:08)}>
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...
<{/ForumPost}>

<{ForumPost(poster="Miso", timestamp=2012-06-06 13:13:44)}>
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.
<{/ForumPost}>

<{ForumPost(poster="Miso", timestamp=2012-06-08 20:48:58)}>
Dvojka predsa neplati, tu je protipriklad:  Y <--A <--> X, kde <--> je smycka. Ak DFS zacne v A, jedinym predchodcom Y bude A.
<{/ForumPost}>