Hric 23.6

Úvodní přednáška o základních typech algoritmů a datových strukturách potřebných pro jejich implementaci.
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:

Hric 23.6

Příspěvek od marion »

1a. Popište rozhodovací strom u třídích algoritmů a dokažte že složitost třídicích algoritmů založených na porovnávání prvků je THETA(N*log N)
1b. Přihrádkové třídění + jeho složitost
2a. Popiště Floyd-Warshallův algoritmus včetně rekonstrukce cesty
2b. Vyslovte invariant FW algoritmu a na pomocí něj zdůvodněte správnost
3a. Dokažte nebo vyvraťte (už nevím přesně, f je elementem něčeho & g je elementem něčeho => ...)
3b. Dokažte substituční metodou že T(n)=2T(n/3)+2T(n/6)+bn je T(n) = THETA(N*log N)

Na ústní jsem dostala očekávaná doba vyhledávání pro hešování se zřetězením při úspěchu a neúspěchu, pak se mě ještě ptal na dvojité hešování. Další otázky byly na topologické uspořádání, Primův algoritmus, randomizovaný quicksort.
Odpovědět

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