Cepek 25.5.2018

Úvodní přednáška o základních typech algoritmů a datových strukturách potřebných pro jejich implementaci.
Joffrey
Matfyz(ák|ačka) level I
Příspěvky: 11
Registrován: 26. 5. 2018 14:00
Typ studia: Informatika Bc.

Cepek 25.5.2018

Příspěvek od Joffrey »

Zadani vypadalo priblizne takhle:
1) Dokazte nebo vyvratte: pokud do cerveno-cerneho stromu pridame prvek a vzapeti na to je jej zase vymazeme, vysledny strom bude shodny s puvodnim.
2) Dokazte nebo vyvratte: Mame orientovany graf G a na nem orientovanou cestu z x do y, potom pokud pokud spustime libovolne DFS pak pokud DFS nalezne vrchol x drive nez y pak y bude v danem DFS strome (ne nutne primym) naslednikem x.
3)Nalezeni nejspolehlivejsi cesty: Mame orientovany graf G a jeho hrany jsou ohodnocene 0<=s(u,v)<=1, kde s(u,v) je pravdepodobnost spolehlivosti hrany. Tyto pravdepodobnosti hran jsou na sobe nezavisle, tedy pravdepodobnost, ze dve libovolne hrany s(x,y) a s (u,v) budou spolehlive je rovna s(u,v) * s(x,y). Vymyslete co nejefektivnejsi algoritmus, ktery nalezne nejspolehlivejsi cestu. Urcete a dokazte slozitost+spravnost.

U ustni jsem dostal minimalni kostry(definice + dokazat vetu ze slajdu + Jarnik-Prim, Boruvka-Kruskal; zkousejiciho muze zajimat i detailnejsi rozebrani casove slozitosti, popripade proc je algoritmus korektni)


RESENI(ten kdo si chce zapocitat necht uz dal necte):
1) Neplati, existuje protipriklad na trech vrcholech, ktery bude mit po dane uprave stejny tvar ale ruznou barevnost.
2) Neplati, protipriklad x<=>z=>y, pokud bychom spustili DFS z bodu 'z', potom nalezneme nalezneme prvni x a potom y ale y nebude naslednikem x.
3) Upraveny Dijkstra
Odpovědět

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