Název: Fibonacciho haldy - jejich varianty a alternativní datové struktury
Překlad názvu: Fibonacci heaps - their variations and alternative data structures
Autoři: Melka, Jakub ; Koubková, Alena (vedoucí práce) ; Koubek, Václav (oponent)
Typ dokumentu: Diplomové práce
Rok: 2012
Jazyk: cze
Abstrakt: [cze] [eng]
V této práci budeme zkoumat Fibonacciho haldy a jejich varianty. Alternativní verze Fibonacciho hald, tzv. thin a thick haldu zavedli H. Kaplan a R. E. Tarjan v roce 2008. Srovnáme tyto haldy jak z experimentálního, tak z teoretického hlediska a do tohoto srovnání zahrneme i některé klasické druhy hald, jmenovitě párovací a regulární haldu. Při experimentech nás bude nejvíce zajímat celkový čas nutný pro běh algoritmu, který pracuje s haldou. Na výsledcích ukážeme, že thin a thick haldy jsou obvykle rychlejší, než Fibonacciho halda a pomalejší, než regulární haldy. Na závěr shrneme poznatky získané experimenty. In this paper we explore Fibonacci heaps and their variants. The alternative versions of the Fibonacci heap, the thin and thick heaps, were introduced by H. Kaplan and R. E. Tarjan in 2008. We compare these heaps from both experimental and theoretical point of view and we also include some classic types of heaps, namely regular and pairing heap. In our experiments we will be most interested in the total time required to run an algorithm that works with heap. The results show that thin and thick heaps are usually faster than the Fibonacci heap and slower than the regular heap. In conclusion, we summarize the knowledge gained from experiments.
Klíčová slova: Fibonacciho halda; halda; thick halda; thin halda; Fibonacci heap; heap; thick heap; thin heap

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/44740

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


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