Zkouska - Hric 3.6.

Úvodní přednáška o základních typech algoritmů a datových strukturách potřebných pro jejich implementaci.
Fermyn Romero de Torres

Zkouska - Hric 3.6.

Příspěvek od Fermyn Romero de Torres »

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)
marion
Matfyz(ák|ačka) level II
Příspěvky: 69
Registrován: 4. 10. 2008 11:05
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: Zkouska - Hric 3.6.

Příspěvek od marion »

Muzete nekdo prosim napsat jak ma byt to 3a?
marion
Matfyz(ák|ačka) level II
Příspěvky: 69
Registrován: 4. 10. 2008 11:05
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: Zkouska - Hric 3.6.

Příspěvek od marion »

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

Re: Zkouska - Hric 3.6.

Příspěvek od Fermyn Romero de Torres »

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)).
vojta_vorel
Matfyz(ák|ačka) level I
Příspěvky: 49
Registrován: 14. 1. 2011 15:10
Typ studia: Informatika Ph.D.

Re: Zkouska - Hric 3.6.

Příspěvek od vojta_vorel »

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
Odpovědět

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