[Zk] 05.02.2014

Přednáška navazuje na přednášky Algoritmy a datové struktury I a II a Programování I a II bakalářského studia. Bude věnována dvěma základním datovým strukturám, hašování a $(a,b)$-stromům (tato struktura se také nazývá $B$-stromy). Popisují se zde základní vlastnosti těchto struktur a jejich složitost. Na závěr přednášky se provede stručné zhodnocení třídicích algoritmů.
Uživatelský avatar
Davpe
Matfyz(ák|ačka) level II
Příspěvky: 98
Registrován: 22. 9. 2010 16:07
Typ studia: Informatika Bc.
Kontaktovat uživatele:

[Zk] 05.02.2014

Příspěvek od Davpe »

Dostal jsem c-univerzalni hashování (seděl jsem ve třetí řadě). Upozornil mě, že mi tam chybí jeden předpoklad (že N (velikost univerza U) je prvočíslo), což jsem mu řekl. Pak se mě ptal na stejné věci jako zde (kromě markovovy nerovnosti jsem tam napsal všechno co deusex), ale navíc se ještě zeptal co vím o malých univerzálních systémech. Já na to že nic, on že to bych měl, ale vzal si index a za jedna.

Tady je seznam otázek i s pořadím (první řada je nekompletní a neručím za správnost).
první řada (zprava): (a,b)-stromy, leftist haldy, ? , nějaké hashování?
druhá řada (zleva): fibonacciho haldy, kukaččí hashování, huffmanův kód, A-sort
třetí řada (zprava): červenočerné stromy, c-univerzální hashování, vyhledávání v uspořádaném poli, rozhodovací stromy, hybrid sort

U A-sortu se ptal co to znamená přetříděná posloupnost, u vyhledávání v uspořádaném poli se ptal na rozdíl mezi nejhorší časovou složitostí a očekávanou (u té očekávané to není nic s průměrem, ale je to při rovnoměrném rozdělení vstupních dat).

Vyhodil člověka s hybrid sortem a fibonnaciho haldou, jeden člověk odešel po zadání (co měl za otázku nevím).

Na jiném termínu byla (prý) posloupnost otázek v první řadě zprava: fibonacciho haldy, c-univerzální hashování a relaxované stromy.
Odpovědět

Zpět na „TIN066 Datové struktury I“