Algoritmy & programovací techniky 11. £ervna 2005
1
Sloºitost •
velikost vstup. dat, 1 krok algoritmu (op. v konst. £ase)
•
zrychlení výpo£tu v záv. na rychlosti HW
•
Asymptotická sloºitost -
2
f (n)=O(g(n)), f (n)=Ω(g(n)), f (n)= Θ(g(n)),
&
o, w.
Dyn. mnoºiny •
2.1
def. dyn. mnoºiny, operace - nd, insert, delete, min, max, succ, pred
Bin. vyhl. stromy
•
de nice bin. stromu, bin. vyhl. stromu
•
v²echny operace
•
nevýhoda: negarantuje vý²ku
2.2
erveno-£erné stromy
•
interní, externí uzly
•
4 vlastnosti:
•
1.
∀uzel
£ervený/£erný
2.
∀ext.
uzel £erný
3.
∀£ervený
4.
∀cesta
vrchol musí mít oba syny £erné
od lib. vrcholu x k listu v jeho podstrom¥ obs. stejný po£et £erných uzl·.
vý²ka uzlu, £erná vý²ka
• L1: Nech´ x je lib. uzel, pak jeho podstrom obs. aspo¬ 2bh(x) − 1interních uzl·. (indukcí podle h(x)) • L2: - strom s n interními uzly má vý²ku nejvý²e 2 log2 (n + 1).
(vl. 3, lemma 1).
•
garantovaná sloºitost
•
rotace - levá, pravá; ko°en vºdy £erný
•
vkládání - jako BVS, pak obarvit nový £erven¥ (kdyº je otec £ervený - err), upravit: 1. otec a strýc £ervený - p°ebarvit, p°enos chyby 2. strýc £erný - je pravým synem 3. strýc £erný, je levým synem
•
⇒L,
⇒P,
p°evést na 3.
p°ebarvit
delete - jako BVS, pak (vyhodím y - má max. 1 syna x, £erný) x:= dvojit¥ £erný, úpravy: 1. bratr x (w) je £ervený (má 2 £erné syny) - L, p°ebarvit, p°evést na 2,3,4 2. w má 2 £erné syny - odstranit £ernou z x, w
→£ervený,
A - £erný nebo 2x £erný (p°enos chyby)
3. levý syn w £ervený (B), pravý £erný - vym¥nit barvy B a w, P(w) p°evést na 4. 4. pravý syn w (C) je £ervený -L(w), p°ebarvit - C £erné, w(nový ko°en) bu¤ £erný nebo £ervený
1
2.3
•
AVL stromy de nice
• V1: Vý²ka AVL stromu s n vrcholy je O(log n). - nech´ lemma : AVL ≥ b, d·kaz indukcí, z toho pro obecný AVL.
3
minimální strom, velikost roste jako b. -
Dolní odhady sloºitosti problém· •
horní - jednodu²²í, t°eba dokázat neexistenci rychlej²ího alg.
•
triviální odhady - velikost vstupu, výstupu
• V1: Na ur£ení k-tého z n prvk· je t°eba aspo¬ (n-1) porovnání. • V2: Pro ∀ t°í¤ák zal. na porovnávání ex. vstupní posloupnost, t.º. alg. provede Ω(n log2 n)porovnání. n n p (rozhodovací strom, n! list·, n! ≤ 2 (p pater), odhad faktoriálu: ( ) 2 . 2
4
Alg. Rozd¥l a panuj •
fungování - rekurze: rozd¥l, vy°e² podúlohy, sjedno´
•
mergesort, binsearch
4.1
•
Analýza sloºitosti D(n) - rozd¥lení
n na a podúloh velikosti n b , T(n) - zprac. úlohy vel. n (pro n
sjednocení na °e². p·v. úlohy vel. n.
T (n)= D(n) + aT ( nb ) + S(n)
•
vzorec
•
metody °e²ení - substitu£ní, master theorem:
(pro n
T (n)= Θ(1)).
Substituce: uhodnout °e²ení (asymptotické), indukcí dokázat (zvlá²´ pro horní a dolní odhad). Master Theorem: nech´ a≥1, c>1, d≥0 k∈ N ) platí:
∈ R, nech´ T : N → N je nekl. fce, t.º. ∀n (n = ck ,
n T (n) = aT ( ) + F (n) c
kde
F (n) = Θ(nd ). Nech´ x:= logc a. Potom:
1. x < d: 2. x = d: 3. x > d:
4.2
T (n) = Θ(nd ). T (n) = Θ(nd log n) T (n) = Θ(nx ).
p°íklady :
•
násobení komplexních £ísel -
•
násobení matic (normální rekurzivní, Strassen·v algoritmus).
•
hledání k-tého z n prvk·
lze set°ídit -
((ac − bd), (ad + bc)i)
- c(b-a), a(d+c), d(a-b)
Θ(n log n)
rozd¥l &panuj - chceme lépe: z quicksortu: pivot, rozt°ídit na m prvk· men²ích neº pivot, pivot a (n-m-1) v¥t²ích. (p°i ²patném výb¥ru pivota - kvadratická sloºitost).
• Blum et al. -
dobrý výb¥r pivota:
1. rozd¥l posl. na 2.
∀
n 5 p¥tic
p¥tici najdi medián (7 porovnání: 4; vít¥zové ven, p°idám pátý, kaºdý s kaºdým)
3. rekurzivn¥ najdi medián z mn.
n 5 medián·
4. pouºij ho jako pivot k rozd¥lení posl. (ob¥ poloviny zaru£ený po£et prvk·
3 10 n.
5. pokud medián medián· není hledaný prvek, hledej rekurzivn¥ v mn. v¥t²ích / men²ích prvk·
2
d·kaz subst. metodou, T(n)
•
≤
12 5 n
+k·
9 10 n (a chci)
≤k·n
analýza sloºitosti Quicksortu
nejlep²í, nejhor²í, pr·m¥rný p°ípad: (intuitivn¥ - konst. pom¥r), korektn¥: p°edp. stejnou pravd¥podob-
Pn−1 ∀permutací, pivot první prvek úseku, d¥lení zachovává náhodnost. Z toho: T (n) = n1 i=0 (T (i) + T (n − 1 − i)) + (n − 1), se£íst vºdy 2 spolu, vyjád°it T(n-1) - T (n) · n & T (n − 1) · (n − 1) ode£íst; Pnpomocí j−1 A B vypsat rovnice pro n...1 a se£íst. Vyjde 2(n + 1) j=2 (j+1)j , rozepsat jako j + j+1 , spo£íst, rozepsat, P n 2 1 1 vyjde 2(n + 1) · [ j=3 j − 2 ] - harm. °ada ~ n · log n. n+1 + nost
5
T°íd¥ní v lin. £ase •
není zal. na porovnávání, zpravidla indexuje pole t°íd¥nými £ísly
• Counting sort
∈ [1..k],
- n £ísel
k =
#vstup. £ísel rovných i, 3. v C je #£ísel
• Radix sort
⇒omezení
hodnot t°íd¥ných £ísel
O(n). 2 pole A,B &1 pomocné - C, 1. init C (nulování), 2. do C dám ≤i, 4. do B (downto) vkládám na pozice ur£ené v C prvky A (stabilní).
- podle niº²ího, pak vy²²ích °ád·; stabilní pr·chody, 1 °ád - jakýkoliv alg. (£asto Counting - pak
lineární).
6
Zákl. grafové algoritmy •
graf, vrcholy (n), hrany (m), orientovaný graf
•
reprezentace: matice sousednosti, seznam soused· (spojáky)
6.1
Prohledávání do ²í°ky - BFS
•
po vrstvách podle vzdálenosti; pouºívá FIFO
•
za£ - obarví v²e bíle, p°edch. := NIL, vzdál. :=
•
dokud není prázdná fronta - vyberu vrchol, vezmu sousedy (bílé), p°ebarvím ²ed¥, dám jim vzdál. + 1, nast.
∞;
do fronty dá 1. vrchol (obarvený ²ed¥, vzdál. := 0).
p°edch·dce, dám je do fronty. Vrchol p°ebarvím na £erno a vyhodím z fronty.
• 6.2
•
uºití - Dijkstr, Prim, testování souvislosti, po£ítání komponent; b¥ºí v
Θ(m + n)
Prohl. do hloubky - DFS pouºívá zásobník/rekurzi
• ∀vrchol
- projdu sousedy, na nenav²tívené rekurzivn¥ volám nav²tiv; ukládám £as-nav²´ (d(i)).
• klasi kace hran:
stromová (j objeven z i - bílý), zpáte£ní (j p°edch·dce i - ²edý), dop°edná (i p°edch. j, ale
ne p°ímý rodi£ - j £erný, d(i)
d(j)).
• vlastnosti:
1. stromové hrany tvo°í orientovaný DFS les (ukázat ºe nemohou tvo°it orient. cyklus, orient.
vidli£ku); 2. j následník i v DFS strom¥
⇔v £ase d(i) ∃z i do j cesta z výlu£n¥ bílých vrchol· (⇒: indukcí; ⇐ex.
cesta - stane se cestou ze strom. hran), 3. intervaly ( d(i), f(i) ) tvo°í dobré uzávorkování (z rekurzivnosti)
6.3
Topologické £íslování
•
def. topolog. £ísl. (
•
hloupý alg. - najdi vrchol bez výst. hran, p°i°a¤ posl. volné £íslo; odstra¬ ho ze seznamu vrchol· a opakuj. (Θ(n(m
•
t : V → {1...n},
t.º.
∀(i, j) : t(i) < t(j).)
, pouze acyklické.
+ n)).
lep²í - modi kace DFS (lin.£as):
lemma - v G cyklus
⇔DFS
objeví zp¥t. hranu (⇒vezmu i z cyklu objevené jako první, j p°edch·dce i
v cyklu, (j,i) se stane zp¥t. hranou;
⇐z
def. zp¥t. hrany)
v¥ta: O£íslování vrchol· acyklického grafu podle klesajících £as· opu²t¥ní f(i) je topologické (sta£í dokázat: (i,j)
∈E ⇒
f(i)>f(j) - podle barvy j p°i prohlíºení (i,j) - j bílý - stromová hrana, j ²edý -
lemma, spor, j £erný - f(j) uº nastalo )
3
6.4
•
Transitivní uzáv¥r orient. grafu de nice: G' = (V,E') trans. uzáv¥r G = (V,E)
⇔∀i, j ∈ V, i 6= j :
z i do j vede v G orientovaná cesta
⇒ (i, j) ∈ E . •
reprezentace maticí sousednosti
•
lze získat v
6.5
•
Θ(n(m + n))
→
matice dosaºitelnosti
pomocí n-krát pouºitého DFS.
Siln¥ souviské komponenty orient. grafu def.
K ⊆V
je s.s.k. G, pokud (i.)
∀i, j ∈ K, i 6= j : ∃
orient. cesta z i do j i zp¥t, (ii.) neexistuje mnoºina
vrchol·, která by byla ostrou nadmnoºinou a spl¬ovala (i).
•
hloupý alg. - vytvo°it matici dosaºitelnosti a z ní v £ase
O(n2 )
p°e£íst s.s.k.. Sloºitost stejná jako transitivní
uzáv¥r.
• lineární alg.
- kondenzovaný graf - jeho vrcholy jsou souvislé komp. p·vodního; prakticky - posl. opu²t¥ný
vrchol DFS leºí v topolog. první komponent¥: 1. DFS(G), vytv. spojáku vrchol· podle klesajicích £as· f(i). 2. Vytvo°ení G
T
(G i G
T
vrcholy do spoják· G
mají stejné s.s.k., vytvo°ení v
T
O(m + n)-
procházím spojáky G a p°idávám zdroj.
).
T 3. DFS(G ), kdy vrcholy jsou hl. cyklem procházeny v po°adí podle fáze 1. (vºdy dostanu vrchol z topoT logicky první komp. G (topolog. poslední komp. v G )
•
celý b¥ºí v
•
d·kaz:
Θ(m + n)
lemma: nech´ K je s.s.k. v G, po DFS(G) platí: (i) K je podmn. jediného DFS stromu, (ii) v daném DFS tvo°í K podstrom ((i) -
Tj , Ti - nech´ Ti vybudován d°ív neº Tj , potom p°í£né hrany vedou jen z Tj do Ti . ∀vrchol· v K, který je z K - nem·ºe nastat, viz (i). b) musí tvo°it podstrom (
(ii) - a)neex. spol. p°edek
cesta za£. i kon£ící v K musí celá pat°it do K))
ve fázi 1 - n¥jaké DFS stromy. fáze 3 - dal²í DFS stromy:
T1 , T2 , .... Indukcí podle i - Ti tvo°í s.s.k.. Nech´ T1 , potom je posl. opu²t¥ný ve fázi1, ko°en posl. stromu z fáze1. y lib. ∈ T1 . Z x vede cesta do T y v G ⇒ z y vede cesta do x v G. y nem·ºe být v G v jiném DFS strom¥ neº x (z vl. DFS), z x musí vést cesta do y ⇒ x &y jsou ve stejné s.s.k.. Tato s.s.k. obsahuje celý T1 , ale nic jiného (prohledávám ∀ x ko°en
moºné cesty - z ost. vrchol· nevede cesta do x ). Dle lemmatu
T1
tvo°í ko°enový podstrom v posl. strom¥ z fáze1. Po jeho odstran¥ní se tento strom
rozpadne na mnoºinu strom·. Ko°en
7
T2
je nyní op¥t ko°en posl. stromu z fáze1
⇒
opak. pro
∀ Ti .
Extremální cesty v orient. grafu •
graf. bez ohodnocení - sta£í BFS.
•
def. ohodnoceného grafu -
•
def. váha nejkr. cesty -
•
nejkr. cesta; záporné cykly, dodef.
7.1
•
w: E→R
- váhová funkce.
δ(u, v) = min{w(p)| p
w(p) =
Pk
i=1
w(vi−1 , vi ),
je cesta z u do v } pokud
∃cesta,
jinak
δ(u, v) = ∞.
δ(u, v) := −∞.
Nejkr. cesty z jednoho zdroje úloha: spo£ítat pro dané s∈V
δ(s, v)
pro
∀v ∈ V \{s}.
• Vl.1.
je-li p nejkr. cesta z
• Vl.2.
je-li p nejkr. cesta a navíc lze p rozloºit na p' =
v0
do
vk ,
pak
∀i, j : 0 ≤ i, j ≤ k psu
je +
pij
nejkr. cesta (sporem - mohu nahr. krat²í)
(u, v),
pak
• Vl.3. (u, v) ∈ E ⇒ δ(s, v) ≤ δ(s, u) + w(u, v) •
kde p je orient. cesta
zp°es¬ování odhad· -
d(v), d(v) ≥ δ(s, v);
inicializace (+∞), Relax(u,v)
4
δ(s, v) = δ(s, u) + w(u, v).
• Vl.4. (u, v) ∈ E ⇒po
provedení Relax(u,v) platí
d(v) ≤ d(u) + w(u, v)
(z vl. Relax, neplatí-li, nastaví
rovnost)
• Vl.5.
Po Init je
d(v) ≥ δ(s, v),
w(u, v) = d(v) < δ(s, v) ≤(vl.3) δ(s, u) + w(u, v)
d(v) ≥ δ(s, v).
Pokud z s do v nevede orient. cesta, tak od Init platí, ºe
• Vl.7.
Nech´ nejkr. cesta z s do v kon£í hranou
δ(s, u)
•
(u, v).
d(v) = δ(s, v) = ∞
d(u) +
(z vl. 5)
Po provedení Init a sekvence Relax, obs. Relax(u,v),
δ(s, v) platí kdykoliv potom. d(v) ≤(vl.4)d(u) + w(u, v) = δ(s, u) + w(u, v) =(vl.2)δ(s, v).)
platí n¥kdy p°ed voláním Relax(u,v), tak d(v) =
- d(u)=δ(s, u) platí stále. Potom
7.2
tak uº se nem¥ní.
Pak po Relax(u,v) platí
- spor).
• Vl.6.
tak pokud d(u) =
δ(s, v),
platí stále po lib. posl. volání Relax. Pokud dosáhne
(vím ºe platí po Init, sporem - v 1., pro které Relax poru²í
(vl.5
DAG Directed Acyclic Graph, Alg. kritické cesty. (jen pro acyklické grafy) 1. topolog. set°i¤ vrcholy G 2. Inicializace 3.
∀(u ∈ V )
v topolog. po°adí ud¥lej pro
∀(v ∈ V ; (u, v) ∈ E)
Relax(u,v).
• V1: Alg. je korektní - v lib. a) nedosaºitelný - vl.6; b) nech´ p je nejkr. cesta t(vi+1 ), Relax topologicky - indukcí podle i: d(vi ) = δ(s, vi ) (ind. krok = vl.7). •
sloºitost
•
aplikace - plánování £inností - cesta: posl. provád¥ných jedna po druhé
7.3
•
Θ(n + m) topolog. t°íd¥ní, alg. trvá Θ(1) na vrchol
z s do v. Platí, ºe t(vi ) <
i hranu (p°edp. p°ístupu k vrcholu v konst. £ase).
Dijkstr·v alg. nezáp. váhy hran; vrcholy - 2 mnoºiny: vy°ízené S, nevy°ízené Q 1. Init 2. S:=∅, Q := V(G) 3. while (Q6=
∅)
do u:= Extract-Min(Q); S:= S∪{u};
• V2: ALg. je korektní
∀(v ∈ V, (u, v) ∈ E )
- sporem, nech´ u je 1. vrchol, t.º.
d(u) 6= δ(s, u)
do Relax(u,v).
v £ase p°e°azení z Q do S.
u 6= s
-
Init, u dosaºitelný (vl.6); nech´ p nejkr. cesta z s do u, y 1. vrchol na p mimo S, x jeho p°edch. Nezáp.hrany -
δ(s, y) ≤ δ(s, u).
nejkr. cesta -
d(y) = δ(s, y).
Podle výb¥ru -
d(u) ≤ d(y),
spor -
d(u) = δ(s, u)
(musí být
rovno).).
•
2
-
7.4
•
m, m < n2 . Θ((m + n) log n).
£as. sloºitost - Pole: Extract-Min (n ), Init (n), Relax (max. m-krát) -
n log n,
Extract-Min
n · log n,
Decrease-Key
m · log m,
Celkem
Celkem
Θ(n2 ).
Halda: Init
Bellman-Ford nejobecn¥j²í, nejpomalej²í, Relax i víckrát na 1 hranu, dovoluje záp. cykly (vrací false) 1. Init 2. for i:= 1 to (|V| - 1) do for 3. for
∀((u,v)∈E)
∀
((u,v)∈E) do Relax (u,v);
do if (d(v) > d(u) + w(u,v)) then return FALSE;
4. return TRUE;
•
sloºitost -
Θ(n · m)
• L1: Nech´ G, s. P°edp., ºe G neobs. záp. cykly dostupné z s. Pak v dob¥ ukon£ení práce Bellman-Ford platí d(v) = δ(s, v) pro ∀vrcholy dosaºitelné z s. - Nech´ v dosaºitelný, p = (v0 , ..., vk ) nejkr. cesta. Nezáp. cykly - p neobs. cyklus, proto k ≤ (n − 1). Indukcí podle k dokázat, ºe po k-té iteraci platí d(vk ) = δ(s, vk ). • V3: Nech´ G, s. Pak po ukon£ení B-F: a) pokud obs. záp. cyklus, vrátí FALSE. b) jinak alg. vrátí TRUE, ∀v : d(v) = δ(s, v). a) v0 , ..vk záp. cyklus, p°edp. TRUE - d(vi ) ≤ d(vi−1 ) + w(vi−1 , vi ) Pk Pk Pk ⇒ i=1 d(vi ) ≤ i=1 (d(vi−1 ) + w(vi−1 , vi )) ⇒ 0 ≤ i=1 w(vi−1 , vi ). b) dosaºitelné - L1, nedosaº. - Vl.6, kontrola na konci (Vl.3).
5
7.5
•
Nejkr. cesty pro v²echny páry vrchol· cykly, cíl - konstrukce
•
G Wuv =(0 pro Duv = δ(u, v).
p°edp. zadání maticí sousednosti
D
G
, kde
u=v) (w(u,v) pro (u,v)∈E) (∞ pro (u,v)∈ / E), p°edp. nezáp.
moºno n-krát spustit p°edch. alg.
• Alg. násobení matic indukcí podle po£tu hran na nejkr. cest¥. 1. k=1 ... 2. k-1
duv (1) =
G Wuv , matice
G
duv (k)
D (1) = W
G
- nejkr. cesta s max. k hranami
.
→k ... nejkr. cesta vede p°es mezivrchol (cesta z u do i & (i, v) - násobím vºdy DG (1)) - maticové
nás (s£ítání místo násobení, výb¥r minima místo s£ítání). (pokud je nejkr. krat²í neº k hran, z·stane zachována - i=v).
bez záp. cykl· - nejkr. cesta max. (n-1) - dal²í násobení nevadí. sloºitost - asociativn¥
Θ(n3 log2 n).
• Floyd-Warshall·v algoritmus podobn¥, ale indukce podle
du,v =
min. váha cesty z u do v s vnit°. vrcholy z mnoºiny
G
{1..k}
G
D =W . k-1 → k - duv = min{duv (k − 1), duk (k − 1) + dkv (k − 1)}
1. k=0 2.
mnoºiny povolených vrchol· jako mezivrcholy.
sloºitost -
- sta£í porovnání 2 £ísel.
3
Θ(n ), navíc malá konstanta (jen 3 for-cykly), rychlej²í neº B-F; pro záp. cykly se na diagonále
za £as objeví záp. £íslo - net°eba testovat p°edem.
8
Minimální kostra •
vstup - orientovaný G, váhová fce; úkol - nalézt kostru s min. celk. vahou; platí |T| = |V|-1, BÚNO nezáp. hrany (lze p°i£íst konstantu)
•
idea - post. p°idávat hrany, do mn. A, která je po°ád podmn. n¥jaké min. kostry.
•
bezpe£ná hrana (A ∪ {e}je taky podmn. kostry), °ez (rozklad V na 2 £ásti
S |=1),
S, V \S ),
hrana k°íºí °ez (|{(u, v) ∪
°ez respektuje mn. A (ºádná hran nek°íºí °ez), lehká hrana pro °ez (ze v²ech hran k°ících °ez má
nejmen²í váhu).
• V1: Nech´ G,w. Nech´ A⊆E podmn. min. kostry, (S, V \S) °ez resp. A. Potom pokud (u, v) ∈ E lehká pro °ez, pak bezpe£ná pro A. Nech´ T min. kostra, A ⊆ T , pokud (u, v) ∈ T - OK; jinak - p jediná cesta z u do v v T, (u, v) k°íºí °ez - na cest¥ je hrana (x, y) ∈ / A co k°íºí °ez. T' = {T \(x, y) ∪ (u, v)}; w(T)=w(T').
•
D·sledek - C souv. komp. podgrafu zadaného A. Potom pokud (u,v) je hrana min. váhy, spojující C s jinými komp. podgrafu zadaného A, pak je (u,v) bezpe£ná pro A. (ez (C,V\C) resp. A, (u,v) lehká).
8.1
•
Bor·vka - Kruskal vºdy hrana s nejm. váhou ze v²ech hran mezi stávajícími komp. podgrafu zadaného A; vºdy slou£í 2 komp. v 1 strom 1. set°i¤ hrany podle w; 2.
∀v ∈ V :Make-Set(v)
3.
∀(u, v) ∈ E :(v
A := ∅
{samost. komp.}
po°adí podle t°íd¥ní) if Find-Set(u)
6=Find-Set(v)
then A:=A
∪(u, v);
Union(u,v)
4. return A.
•
Sloºitost - Set°íd¥ní
Θ(m log m); Make-Set - Θ(n); Find-Set - konst. £as (pole pointr·, z n¥j p°es vrchol na hlavu Θ(m); Union - krat²í seznam za del²í, p°epsat aliasy, délku sezn. Max. p°ealiasování - O(n log n).
seznamu - £íslo mn.) -
log2 n
pro 1 vrchol
6
8.2
•
Jarník - Prim hrany A vºdy 1 strom, vºdy vybere hranu s nejm. vahou ze v²ech, které vedou mezi A a okolím 1. Q:= V(G); for 2. while (Q6=
∅)
∀v ∈ V
od klí£(v):=
∞;
klí£(r) := 0; (start. vrchol) p°edch(r):=NIL;
do
u:= Extract-Min(Q); for∀(v
∈ V : (u, v) ∈ E)
do if
(v ∈ Q
&& klí£(v)>
w(u, v))
then klí£(v):=w(u,v);
p°edch(v):=u;
•
Sloºitost - v poli
Θ(n2 ) - vybr. minima - n-krát n; v bin. hald¥: O(m log n); Celkem nejh·°e Θ(m log n).
Init -
Θ(n);
Extract-min -
n · log n;
Nejvý²e
m-krát decrease-key -
9
Hashování •
vhodné pro reprezentaci dyn. mnoºiny, kde pot°ebuji jen Insert, Delete, Search
•
p°ímo adresovatelná tabulka - pole - velikost: po£et moºných klí£·, p°edp. r·zných klí£· pro v²echny prvky; bu¤ celá data nebo pointry; neefektivní.
• •
hash-tabulka - men²í, úm¥rná skute£nému po£tu pouºitých klí£·, po£ítá se pomocí problém -
kolize - °e²ení: °et¥zení - ve spojáku. (Insert & Delete -
hashování (stejná pravd¥podobnost
• V1:
Neúsp. Search trvá pr·m¥rn¥
• V2:
Úsp. hledání trvá pr·m¥rn¥
∀adresu,
Search: jednoduché uniformní
nezáv. na ost. klí£ích) - faktor zapln¥ní tabulky -
Θ(1 + α).
Θ(1 + α)
Θ(1),
hashovací funkce.
- spo£ítám hash, projdu celý spoják (pr·m.
α
α=
n m .)
prvk·).
za p°edp. viz vý²e. - P°edp. ºe Insert strká v²e na konec spojáku,
ºe hledám od za£.; O£ekávaný po£et nav²tívených je o 1 v¥t²í neº p°i vloºení prvku. Pr·m¥r p°es v²ech n uloºených: (1 + o£ekávaná délka seznamu p°i vloºení i-tého):
• 9.1
•
D·sledek: Pokud
n = O(m),
tak
α = O(1)
n−1 α 1 (1+ i−1 m ). Pr·m¥r: 1+ 2m = 1+ 2 + 2m = Θ(1+α).
- Search je pr·m¥rn¥
Θ(1).
Hash-funkce Chceme co nejrovnom¥rn¥j²í rozd¥lení, p°edp. £íselné klí£e (stringy - konverze)
1. Hashování d¥lením
•
hash(k) = k mod m
•
nevhodné m=2
p
, 10p , 2p − 1,
vhodné - m prvo£íslo daleko od mocnin 2
2. Hashování násobením
•
volím
A ∈ (0, 1),
•
m v¥t²inou pouºitá mocnina 2 - jednou²í po£ítání - m=2 , k - w bit· - vynásobení k(A shl w), vezme se
Pro klí£ k spo£ítám
bm · (kA mod 1)c p
z dolní poloviny výsledku prvních p bit· (prvních p bit· desetiné £ásti kA).
√
•
vhodné A - nap°.
5−1 2 .
3. Univerzální hashování
•
ke kaºdé fci se dá zkonstruovat posloupnost, kde se n klí£· nahashuje do stejného místa (kdyº universum
≥ n2 ). •
Moºnost obejít - random vybrat z více hash-fcí - nelze vytvo°it ²patná data.
volíme náhodn¥ a nezávisle z vhodné mnoºiny fcí
• univerzální max.
•
mn. hash-fcí
H-
pokud
∀2
klí£e
x, y ∈ U
platí, ºe po£et hash-fcí, kde hash(x)=hash(y) je
H m.
P°ed hashováním zvolím náhodn¥ h:U
→ {1...m}z
jednoduché uniformní hashování.
• V1: Nech´ je
h
H
(univ.)
⇒pravd¥podobnost
kolize je
n x
1 m - to je
náh. vybraná z univ. mn. hash-fcí, nech´ je pouºitá k hashování klí£· do tabulky velikosti , kde n ≤ m, potom o£ekávaný po£et kolizí libovolného klí£e je men²í 1 neº 1. (def. cyz =(1 pro h(y)=h(z), 0 jinak; h z univ. mn. → E[cyz ] = m , cx :=celk. po£et kolizí x.
m
P P E[cx ] = E[ y6=x cxy ] = y6=x E[cxy ] = •
n−1 m .
D·sledek: pr·m. délka seznamu je < 1.
7
•
∀x rozd¥lit do (r + 1) £ástí (xi < m); a (r+1) a x ) mod m . H = ∪ {h } , |H| = m . i i a a i=0
Jak zkonstruovat univ. mnoºinu? - zvolit m prvo£íslo,
ha (x) = (
Pr
náh. klí£, potom
H
• V2: Taková je univ. mnoºina hash-fcí. ( Nech´ 2 r·zné klí£e x,y se li²í v k-tém podklí£i. Pro kaºdou P posl. a0 , ..., ak−1 , ak+1 , ..., ar ex. práv¥ 1 ak , t.º. ha (x) = ha (y) - ak (xk − yk ) ≡= (− i6=k ai (xi − yi )) mod m. r Moºných voleb posl. je m , ∀∃!ak , pro které nastává kolize. 9.2
•
Otev°ené adresování p°i kolizi se spo£ítá nová adresa - dal²í pokus o zápis do tabulky (∀ klí£e p°ímo v 1 tabulce). Hash-fce:
h : U × {0, .., m − 1} → {0, ..., m − 1}. permutací {0, ..., m − 1}. 1. Lineární zkou²ení -
Pro klí£ máme posloupnost
h(x, i) = (h0 (x) + i) mod m
{h(x, 0), h(x, 1) ... h(x, m − 1)}-
musí být
- problém - primární clusterování (jen m posloupností zk-
ou²ených pozic) 2. Kvadratické zkou²ení -
h(x, i) = (h0 (x) + c1 i + c2 i2 ) mod m
- musím vhodn¥ zvolit
c1 , c2 ,
(po°ád ale jen m
posloupností zkou²ených pozic). 3. Dvojité hashování -
h(x, i) = (h1 (x) + i · h2 (x)) mod m - nezávislé fce, pot°ebuji h2 nesoud¥lné s h1 (x) = h1 (y), pak v¥t²inou h2 (x) 6= h2 (y) - Θ(n2 ) posl. zkou²ených pozic.
vybraná funkce - je-li
8
m. Správn¥
