From 7bc212bd0b46248565a315b9043227cc3c0352f1 Mon Sep 17 00:00:00 2001
From: Martin Mares <mj@ucw.cz>
Date: Mon, 10 Sep 2007 14:49:17 +0200
Subject: [PATCH] Trochu vylepsena verze, jeste na ni budu pracovat.

---
 13-hash/13-hash.tex | 69 ++++++++++++++-------------------------------
 1 file changed, 21 insertions(+), 48 deletions(-)

diff --git a/13-hash/13-hash.tex b/13-hash/13-hash.tex
index 0609629..48a5682 100644
--- a/13-hash/13-hash.tex
+++ b/13-hash/13-hash.tex
@@ -1,62 +1,35 @@
 \input lecnotes.tex
 
-\prednaska{13}{Hashování}{(zapsal Martin Francù a Bohdan Maslowski)}
+\prednaska{13}{Hashování}{(zapsali Martin Francù a Bohdan Maslowski)}
 
+V~pøedchozích kapitolách jsme ukázali, ¾e aèkoliv v~obecném pøípadì
+nelze tøídit rychleji ne¾ v~èase $\Theta(n\log n)$, pro nìkteré speciální
+druhy hodnot (malá celá èísla, øetìzce apod.) existuje efektivnìj¹í lineární
+algoritmus. Nyní si podobným zpùsobem posvítíme na~reprezentaci mno¾in --
+navrhneme datovou strukturu, která bude umìt s~vhodnými typy prvkù provádìt
+základní mno¾inové operace (\<Insert>, \<Delete>, \<Find>) v~{\I prùmìrnì}
+konstantním èase (pomocí vyhledávacích stromù jsme to zatím umìli v~èase $\O(\log n)$
+na operaci).
 
-\h{Tøídìní}
+Jaké máme mo¾nosti? Zaènìme od~tìch nejjednodu¹¹ích a oznaème si~$n$ velikost
+mno¾iny a $U$ velikost univerza, z~nìj¾ prvky mno¾iny vybíráme.
 
-V kapitole 5 jsme si ukázali, ¾e tøídìní pomocí porovnávání se dá zvládnout nejlépe v èase $O(n)$. Víme-li v¹ak nìco o hodnotách, mù¾eme najít lep¹í tøídící algoritumus, který pracuje napø. v lineárním èase.
+\s{1. Pole indexované od $0$ do $U-1$}
 
-\>Na mno¾inì máme tyto operace:
+\indent \<Insert>, \<Delete> i \<Find> pracují v~èase $\O(1)$, ale platíme za~to
+pamì»ovou slo¾itostí $\Theta(U)$.
 
-\itemize\ibull
-\:Insert(x)
-\:Delete(x)
-\:Find(x)
-\endlist
-
-\>Víme-li, ¾e je mno¾ina uspoøádaná, mù¾eme pou¾ít vyhledávací strom, tedy $\Theta(\log n)$ na operaci.
-
-\medskip
-
-\>Znaèíme
-
-\itemize\ibull
-\:$n$ ... Poèet prvkù
-\:$U$ ... Velikost universa (mno¾ina ze které prvky vybíráme)
-\:$[U] = {0, 1, 2,\ldots,U-1}$
-\endlist
-
-
-\bigskip
-
-\h{1. Pole indexované $0$ a¾ $U-1$}
-
-Insert, Delete i Find pracují v èase $O(1)$, pamì»ová slo¾itost je $O(U)$.
-
-
-\h{2. Èíslicový strom (radix tree) }
+\s{2. Èíslicový strom (radix tree)}
 
 Zvolíme základ soustavy $b$, prvky universa zapisujeme jako $k$-tice èíslic. Èili:
+$$x\in U \mapsto [b]^{k}, k=\lceil\log_b U\rceil.$$
+Tím nám vznikne strom s~hloubkou $k$, na $k$-té úrovni se rozhodujeme podle $k$-té èíslice.
 
-$$x\in U \mapsto [b]^{k}, k=[\log_b U]$$
+Operace \<Find> bude trvat $O(\log_b U)$, operace \<Insert> a \<Delete> pak
+$O(b \log_b U)$. Strom zabere prostor velikosti $O(nb\log_b U)$.
 
-Tedy vznikne strom (s hloubkou $k$), na $k$-té úrovni podle $k$-té èíslice
-
-\medskip
-
-
-Find: $O(\log_b U)$
-
-Insert, Delete: $O(b \log_b U)$
-
-Pamì»ová nároènost: $O(nb\log_b U)$
-
-\medskip
-
-Èím bude základ $b$ men¹í, tím lep¹í pamì»ová a hor¹í èasová slo¾itost, a obrácenì. Èíslicový strom tedy vy¾aduje peèlivé nastavení parametrù.
-
-\bigskip
+Èím bude základ $b$ men¹í, tím lep¹í pamì»ová a hor¹í èasová slo¾itost,
+a obrácenì. Èíslicový strom tedy vy¾aduje peèlivé nastavení parametrù.
 
 \h{3. Písmenkový strom }
 
-- 
2.39.2