Skúška Mareš

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ů.
jajaja
Matfyz(ák|ačka) level I
Příspěvky: 11
Registrován: 31. 1. 2019 20:17
Typ studia: Informatika Mgr.

Skúška Mareš

Příspěvek od jajaja »

1. linear probing - očakávaná dĺžka runu je ohraničené konštantou nezávislou na n,m a h.
Pýtal sa, kde je potrebný predpoklad úplne náhodnej hashovacej funkcie - na použitie Černovovej nerovnosti. V skutočnosti by to šlo zoslabiť, ale museli by sme použiť inú vetu a rátať momenty.

2. Ukažte, jak provádět 1-rozměrné intervalové dotazy na binárním vyhledávacím stromu.
Odpovědět

Zpět na „TIN066 Datové struktury I“