Fórum studentů MFF UK

Jsem možná mimo, ale kdyby mi někdo chtěl stručně pomoct..

Fermyn Romero de Torres píše: 2)a)dokazte nebo vyvratte "f(h) je elementem omega(h(n)) &
g(n) je elementem THETA(h(n)) => f(n) + g(n) je elementem
omega(h(n))"

Přijde mi to podezřele lehký! Když snad f je v omega(h), tak f + cokoliv je v omega(h).. důkaz z definice..
(předpokládám že to háčko v "f(h)" je překlep..)
Je to tak?

Dík, vojta

Co ja vim, tak u 3a by nemelo chybet, ze tento algoritmus probiha tak ze |V|krat projede vsechny hrany a zkusi na ne releaseEdge (zkusi zlepsit danou hranou cestu z pocatku). A podle me, ukolem bylo rici, ze kdyz pouziju pro ulozeni matici sousednosti, pak casova slozitost je O(|V|^3), kdyz pouziju seznam sousedu pak O(|V|*|E|) (ikdyz |E| se mi muze zvhnout v |V|^2, |E| je preci trochu vic presnejsi) a kdyz pouziju matici incidence, pak bude slozitost O(|V|*|V|*|E|) (v krajnim pripade O(|V|^4)).

Co všechno se NEzkouší z tohoto materiálu http://www.mff.cz/data/ADS_slidy.pdf ? Vzpomínám si, že jsme nestihli LUP dekompozici. Je tam ještě něco, třeba Huffmanův kód, násobení matic, nebo tak?

Muzete nekdo prosim napsat jak ma byt to 3a?

Otazky na dnesni zkousce:

1)a) Popiste (presne) vypousteni z B-stromu
1)b) kolik nejmene vrcholu muze mit AVL-strom danne hloubky

2)a)dokazte nebo vyvratte "f(h) je elementem omega(h(n)) &
g(n) je elementem THETA(h(n)) => f(n) + g(n) je elementem
omega(h(n))"
2)b)substitucni metodou dokazte ze slozitost T(n)=3T(n/3)+T(2n/3)+bn
je O(N^2)

3)a)urcete casovou slozitost bellman-fordova algoritmu v zavislosti
na ulozeni grafu
3)b)dokazte ze lehka hrana rezu je zaroven bezpecna hrana pro nejakou
podmnozinu minimalni kostry (rez respektuje dannou mnozinu)