Posledni kousky Q-Heapu a jejich aplikace na kostry.

[ga.git] / 8-qheap / 8-qheap.tex

diff --git a/8-qheap/8-qheap.tex b/8-qheap/8-qheap.tex
index 4c0a6dbc4f19eef427e9a47c0982d8b8c787b964..8d62eb076791d0b693870c3ea8221294e005b4f9 100644 (file)
--- a/8-qheap/8-qheap.tex
+++ b/8-qheap/8-qheap.tex
@@ -4,12 +4,9 @@
 \def\pnromanp{(\nroman)}
 \def\pnromanap{(\nroman ')}
 
-% Vlozeni obrazku {obrazek}{popisek}
-\def\nosizefigure#1#2{\bigskip\vbox{\centerline{\epsfbox{#1}}\smallskip\centerline{#2}}\bigskip}
-
 \input ../sgr.tex
 
-\prednaska{8}{Q-Heaps}{zapsal Cyril Strejc}
+\prednaska{8}{Q-Heaps}{}
 
 V~minulé kapitole jsme zavedli výpoèetní model RAM a nahlédli jsme,
 ¾e na~nìm mù¾eme snadno simulovat vektorový poèítaè s~vektorovými operacemi pracujícími v~konstantním èase.
@@ -95,8 +92,8 @@ p
 prvku a z~rankù u¾ odvodíme i ostatní operace.
 
 \s{Pøíklad:}
-\nosizefigure{trie.eps}{Trie. Ohodnocení hran je pouze pro názornost -- není
-souèástí trie.}
+\figure{trie.eps}{Trie. Ohodnocení hran je pouze pro názornost -- není
+souèástí trie.}{\epsfxsize}
 
 \s{Lemma 1:} $\rank_X(x)$ je urèen jednoznaènì:
 \numlist\pnromanp
@@ -208,11 +205,32 @@ po
 \:Pøepoèítáme $c_{i-1}$ a $c_i$ a upravíme $B$ a $C$ jako pøi Insertu.
 \endalgo
 
-\todo{Popsat, jak se poèítá $x[B]$.}
+\s{Èasová slo¾itost:} V¹echny kroky operací po~výpoètu ranku trvají konstantní èas, rank
+samotný zvládneme spoèítat v~$\O(1)$ pomocí tabulek, pokud známe $x[B]$. Zde je ov¹em
+nalíèen háèek -- tuto operaci nelze na~Word-RAMu konstantním poètem instrukcí spoèítat.
+Jak si pomù¾eme:
+
+\itemize\ibull
+\:Vyu¾ijeme toho, ¾e operace $x[B]$ je v~${\rm AC}^0$ a vystaèíme si se strukturou pro ${\rm AC}^0$-RAM.
+Zde dokonce mù¾eme vytváøet haldy velikosti a¾ $w\log w$. Také pøi praktické implementaci mù¾eme vyu¾ít
+toho, ¾e souèasné procesory mají instrukce na~spoustu zajímavých ${\rm AC}^0$-operací, viz napø. pìkný
+rozbor v \cite{thorup:ac0}.
+\:Jeliko¾ $B$ se pøi jedné Q-Heapové operaci mìní pouze o~konstantní poèet prvkù, mù¾eme
+si udr¾ovat pomocné struktury, které budeme umìt pøi lokální zmìnì~$B$ v~lineárním èase
+pøepoèítat a pak pomocí nich indexovat. To pomocí Word-RAMu lze zaøídit, ale je to technicky
+dosti nároèné, tak¾e ètenáøe odkazujeme na~Fredmanùv a Willardùv èlánek \cite{fw90trans}.
+\endlist
 
-\todo{Na $AC^0$-RAMu staèí $k=\O(w/\log w)$.}
+\h{Aplikace Q-Heapù}
 
-\todo{Aplikace na~kostry.}
+Jedním velice pìkným dùsledkem existence Q-Heapù je lineární algoritmus na~nalezení
+minimální kostry grafu ohodnoceného celými èísly. Získáme ho z~Fredmanovy a Tarjanovy
+varianty Jarníkova algoritmu (viz kapitoly o~kostrách) tak, ¾e v~první iteraci pou¾ijeme
+jako haldu Q-Heap velikosti $\log^{1/4} n$ a pak u¾ budeme pokraèovat s~Fibonacciho
+haldou. Tak provedeme tolik prùchodù, kolikrát je potøeba zlogaritmovat $n$,
+aby výsledek klesl pod~$\log^{1/4} n$, a~to je konstanta. V¹imnìte si, ¾e by nám
+dokonce staèila halda velikosti $\O(\log^{(k)} n)$ a~operacemi v~konstantím èase
+pro nìjaké libovolné~$k$.
 
 \references
 \bye