Srovnání implementací DecreaseKey hald
| Název práce v češtině: | Srovnání implementací DecreaseKey hald |
|---|---|
| Název v anglickém jazyce: | Comparison of implementations of DecreaseKey Heaps |
| Klíčová slova: | Halda|Amortizovaná složitost|Složitost v nejhorším případě |
| Klíčová slova anglicky: | Heap|Arortized complexity|Worst case complexity |
| Akademický rok vypsání: | 2025/2026 |
| Typ práce: | bakalářská práce |
| Jazyk práce: | |
| Ústav: | Katedra teoretické informatiky a matematické logiky (32-KTIML) |
| Vedoucí / školitel: | Mgr. Vladan Majerech, Dr. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 05.07.2025 |
| Datum zadání: | 08.07.2025 |
| Datum potvrzení stud. oddělením: | 08.07.2025 |
| Zásady pro vypracování |
| Student implementuje několik variant DecreaseKey hald, přinejmenším Fibonacciho haldy a Haldy s globálně omezenými ztrátami a zásobníky nedokončených redukcí.
Cílem je srovnat efektivitu uvedených hald. Jako testovací případ je vybrán Fredman-Tarjan algoritmus na hledání minimální kostry v náhodných grafech. |
| Seznam odborné literatury |
| [1] Fibonacci heaps and their uses in improved network optimization algorithms; M. L. Fredman, R. E. Tarjan, J. ACM 34, 3, pages 596-615 (July 1987) issn 0004-5411
[2] Fast DecreaseKey Heaps with worst-case variants; V. Majerech, https://arxiv.org/abs/2010.02507 eprint 2010.02507 [3] Strict Fibonacci Heaps; G. S. Brodal, G. Lagogiannis, R. E. Tarjan, ACM Trans. Algorithms 21, 2, Article 15 (January 2025) issn 1549-6325 |