Název: Datové struktury pro různá rozdělení dat
Překlad názvu: Datové struktury pro různá rozdělení dat
Autoři: Čunát, Vladimír ; Koubek, Václav (vedoucí práce) ; Mareš, Martin (oponent)
Typ dokumentu: Diplomové práce
Rok: 2010
Jazyk: eng
Abstrakt: [eng] [cze]
In this thesis we study the predecessor problem, which consists of maintaining a dynamic ordered set of keys. After a survey of the most important published results, we provide a detailed description and analysis of a randomized variant of van Emde Boas tree structure. The variant achieves asymptotically optimal space usage, but the (log logN) time bounds are no longer worst-case but expected amortized. The best published expected amortized time bound that is achieved on the (s ; s1-d)-smooth class of distributions is equal to O(log log n). We combine the known techniques into a new structure that achieves the same time bound on a wider class of input distributions. Moreover, the new structure can utilize the optimal amortized structure proposed by Beame and Fich, which ensures that the amortized time complexity is also bound by the optimal p(log n/log log n). Práce se zabývá studiem problému predchudce, kde datová struktura udržuje dynamickou usporádanou množinu klícu. Krome prehledu nejduležitejších publikovaných výsledku ukazujeme podrobný popis konkrétní možnosti, jak lze docílit pravdepodobnostní úpravy van Emde Boasovy struktury. Tato úprava snižuje pametovou nárocnost na optimum, akorát stejné casové složitosti (log logN) již není dosahováno v nejhorším prípade, ale v amortizovaném ocekávaném prípade. Nejlepší ocekávaná amortizovaná složitost dosahovaná na tríde (s ; s1-d)-hladkých distribucí je rovna O(log log n). Kombinací známých technik dostáváme novou datovou strukturu, která dosahuje stejné složitosti, ale na širší tríde distribucí než bylo doposud možné. Navíc lze jako podstrukturu využít optimální amortizované rešení problému navržené Beamem a Fichem, což zarucí omezení amortizované složitosti nové struktury na asymptoticky optimální hodnotu rovnou p(log n/ log log n).

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/34197

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-494426


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Diplomové práce