Suffix: Oprava lemmatu o vnorenych suffixech

[ga.git] / 7-ram / 7-ram.tex

diff --git a/7-ram/7-ram.tex b/7-ram/7-ram.tex
index 717add95bc4d3000adfccf6ec0b3b8ed4c5e89d9..7ad0c1c2c32eafc3c95dcbb719050d326ff4b190 100644 (file)
--- a/7-ram/7-ram.tex
+++ b/7-ram/7-ram.tex
@@ -114,7 +114,7 @@ Dijkstra    &$\O(m\log\log U)$      &$\O(m+n\log\log n)$ \cite{thorup:pq}, neorientovan
 }}$$
 My se pøidr¾íme ekvivalentní, ale jednodu¹¹í definice podle Erika Demaine~\cite{demaine}.
 
-\s{Definice:} VEBT($U$) pro universum velikosti $U$ (BÚNO $U=2^{2^k}$)
+\s{Definice:} VEBT($U$) pro universum velikosti $U$ (BÚNO $U=2^k=2^{2^\ell}$)
 obsahuje:
 
 \itemize\ibull
@@ -198,7 +198,7 @@ aby programy 
 ale je definováno, ¾e neinicializovanou buòku mù¾eme pøeèíst a dostaneme
 nìjakou korektní, i kdy¾ libovolnou, hodnotu. Tehdy nám pomù¾e:
 
-{\narrower
+%{\narrower\medskip
 
 \s{Vìta:} Buï $P$ program pro Word-RAM s~nulami inicializovanou
 pamìtí, bì¾ící v èase $T(n)$. Pak existuje program~$P'$ pro Word-RAM
@@ -227,7 +227,7 @@ jestli je $M[i]$ ji
 v~tém¾e èase udr¾ovat.
 \qed
 
-}
+%\medskip}
 
 \s{\uv{Minové pole}:} Neinicializované buòky není ani dovoleno èíst.
 V~tomto pøípadì nejsme schopni deterministické redukce, ale alespoò
@@ -254,6 +254,8 @@ po
 Libovolný $n$-slo¾kový vektor, jeho¾ slo¾ky jsou $b$-bitová èísla
 ($n(b+1)\le w$), zakódujeme poskládáním jednotlivých slo¾ek vektoru za~sebe,
 prolo¾enì nulovými bity:
+
+\nobreak
 \alik{\0 x_{n-1} \0 x_{n-2} \9\9\9 \0 x_1\0 x_0  \cr}
 
 \>S~vektory budeme provádìt následující operace: (latinkou znaèíme vektory,
@@ -324,13 +326,15 @@ existuj
 
 Nejdøíve èíslo~$\alpha$ replikujeme, pak andujeme vhodnou bitovou maskou,
 aby v~$i$-té slo¾ce zùstal pouze $i$-tý bit a ostatní se vynulovaly,
-a pak provedeme $\<Cmp>$ s~vektorem reprezentovaným touté¾ bitovou maskou.
+a pak provedeme $\<Cmp>$ s~vektorem samých nul.
 
 \:$\<Unpack>_\varphi(\alpha)$ -- podobnì jako pøedchozí operace, ale bity je¹tì
 prohází podle nìjaké pevné funkce $\varphi$:
 
 Staèí zvolit bitovou masku, která v~$i$-té slo¾ce ponechá právì $\varphi(i)$-tý bit.
 
+\finalfix{\goodbreak}
+
 \:$\<Pack>(x)$ -- dostane vektor nul a jednièek a vytvoøí èíslo, jeho¾ bity
 jsou právì slo¾ky vektoru (jinými slovy ¹krtne nuly mezi bity):
 
@@ -392,7 +396,7 @@ Z~\<LSB> pomoc
 
 \>Poslední dvì operace doká¾eme spoèítat i v~lineárním prostoru, napøíklad
 pro \<MSB> takto: Rozdìlíme èíslo na bloky velikosti $\lfloor\sqrt{w}\rfloor$.
-Pak pro ka¾dý blok zjistíme, zda v nìm je aspoò jedna jednièka, zavoláním
+Pak pro ka¾dý blok zjistíme, zda v~nìm je aspoò jedna jednièka, zavoláním
 $\<Cmp>(0,x)$. Pomocí \<Pack> z~toho dostaneme slovo~$y$ odmocninové
 délky, jeho¾ bity indikují neprázdné bloky. Na~toto èíslo zavoláme pøedchozí
 kvadratické \<MSB> a zjistíme index nejvy¹¹ího neprázdného bloku.