Zkouska 4.6.2012, Cepek

Úvodní přednáška o základních typech algoritmů a datových strukturách potřebných pro jejich implementaci.
k21
Matfyz(ák|ačka) level I
Příspěvky: 3
Registrován: 17. 1. 2012 14:57
Typ studia: Informatika Bc.

Zkouska 4.6.2012, Cepek

Příspěvek od k21 »

Pisemna cast:
1. Je dan vztah T(n) = 2T(n/2+1)+n2. Pro vhodne zvolene n0 plati, ze pro vsechna n mensi nez n0 T(n) = 1. Odhadnete funkci f, pro kterou plati T(n) = theta(f(n)) a svuj odhad dokazte substitucni metodou.
2. Popiste a napiste v "Pascalu" algoritmus, ktery na vstupu dostane dve setrizene posloupnosti X a Y (kazda z nich ma delku N) a ma v case O(log N) najit jeden z medianu vsech 2N cisel z X i Y.
3. Vymyslete algoritmus na nasobeni matic velikosti n x kn a kn x n, ktery pouziva jako podprogram Strassenuv algoritmus. Pro obe mozna poradi soucinu zjistete casovou slozitost a porovnejte ji se slozitosti klasickeho nasobiciho algoritmu.

U ustni casti jsem mel definici AVL stromu, dukaz jeho logaritmicke vysky a diskuzi o Kruskalovu algoritmu na hledani minimalni kostry grafu a jeho casove slozitosti.
Odpovědět

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