Zkouska - Hric 3.6.

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)

Muzete nekdo prosim napsat jak ma byt to 3a?

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?

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

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

Fermyn Romero de Torres wrote: 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