Státnice - Informatika - Datové struktury: Porovnání verzí

Z ωικι.matfyz.cz
Přejít na: navigace, hledání
(Univerzální Hašování)
(Univerzální Hašování)
Řádka 22: Řádka 22:
 
Pro kazdou vstupni mnozinu ex. "hodne" fci z H, ktere se chovaji dobre(malo kolizi).
 
Pro kazdou vstupni mnozinu ex. "hodne" fci z H, ktere se chovaji dobre(malo kolizi).
  
'''Def:''' Soubor fci z H (U -> {0, 1, ...m-1} se nazyva c-univerzalni, pokud <math>\forall x<>y \in U;\  |{h \in H; h(x) = h(y)}| \leq\ \cfrac{c*|H|}{m}</math>
+
'''Def:''' Soubor fci z H (U -> {0, 1, ...m-1} se nazyva c-univerzalni, pokud <math>\forall x<>y \in U;\  |{h \in H; h(x) = h(y)}| \leq\ \cfrac{c |H|}{m}</math>
  
 
'''Konstrukce H:''' Predpokladejme: U = (0, 1, ... N-1), N prvocislo (pro kazde prirozene cislo existuje prvocislo mezi tim cislem a dvounasobkem, takze prinejhorsim natahnem mnozinu na dvojnasobek, aby tohle platilo).
 
'''Konstrukce H:''' Predpokladejme: U = (0, 1, ... N-1), N prvocislo (pro kazde prirozene cislo existuje prvocislo mezi tim cislem a dvounasobkem, takze prinejhorsim natahnem mnozinu na dvojnasobek, aby tohle platilo).
Řádka 28: Řádka 28:
  
 
'''Tvrzeni:''' takto zkonstruovane H je<br />
 
'''Tvrzeni:''' takto zkonstruovane H je<br />
<center><math>\cfrac{\left\lceil\cfrac{N}{m}\right\rceil^2}{\left(\cfrac{N}{m}\right)^2}</math> - univerzalni system</center>
+
<center><math>\left\lceil\cfrac{N}{m}\right\rceil^2\Big /\left(\cfrac{N}{m}\right)^2</math> - univerzalni system</center>
  
 
...
 
...
  
 
'''Veta:''' necht H je c-univerzalni system, pak pro kazdou mnozinu <math>S \subset U,\ |S| = n</math> a pro kazde x je ocekavany cas operaci insert/member/delete(x) roven:<br />
 
'''Veta:''' necht H je c-univerzalni system, pak pro kazdou mnozinu <math>S \subset U,\ |S| = n</math> a pro kazde x je ocekavany cas operaci insert/member/delete(x) roven:<br />
<center><math>O\left(\cfrac{c*n} {m}\right)</math></center><br />
+
<center><math>O\left(\cfrac{c n} {m}\right)</math></center><br />
 
.. je to prumer pres vsechny fce z H, ne pres vsechny vstupy. Takze kdyz to pro jednu fci neni splneno, muzu nahodne vybrat jinou a mam slusnou sanci, ze pro ni to, na tom samem vstupu, splneno bude.
 
.. je to prumer pres vsechny fce z H, ne pres vsechny vstupy. Takze kdyz to pro jednu fci neni splneno, muzu nahodne vybrat jinou a mam slusnou sanci, ze pro ni to, na tom samem vstupu, splneno bude.
  
 
'''Veta:''' necht H je c-univerzalni system, pak pro kazdou mnozinu <math>S \subset U,\ |S| = n</math> a pro kazde x plati, pokud je <math>\mu</math> prumerna delka retezce pro prvky s hodnotou h(x), pak:<br />
 
'''Veta:''' necht H je c-univerzalni system, pak pro kazdou mnozinu <math>S \subset U,\ |S| = n</math> a pro kazde x plati, pokud je <math>\mu</math> prumerna delka retezce pro prvky s hodnotou h(x), pak:<br />
<center><math>\forall t>1</math> je pravdepodobnost, ze je retezec <math>\geq \mu*t</math> mensi nez <math>\cfrac{1}{t}</math></center>
+
<center><math>\forall t>1</math> je pravdepodobnost, ze je retezec <math>\geq \mu t</math> mensi nez <math>\cfrac{1}{t}</math></center>
  
 
'''Veta:''' kdyz H je c-univerzalni system na universu U = {0,1,...N-1} hashujici do tabulky velikosti m, pak:<br />
 
'''Veta:''' kdyz H je c-univerzalni system na universu U = {0,1,...N-1} hashujici do tabulky velikosti m, pak:<br />
<center><math>|H| > m * \cfrac{\lceil log_m(N-1)\rceil}{c}</math></center>
+
<center><math>|H| > m \cfrac{\lceil (log_mN)-1)\rceil}{c}</math></center>
  
 
=== Perfektní hašování ===
 
=== Perfektní hašování ===

Verze z 10. 5. 2007, 21:04

Zdroje

Jednotlivé otázky

Stromové vyhledávací struktury

Binární stromy a jejich vyvažování

Trie

B-stromy a jejich varianty

Hašování

Řešení kolizí

Univerzální Hašování

U normalnich hasovacich metod predpokladame rovnomerne rozdeleni vstupni mnoziny. To nejde zarucit a nerovnomernost a z ni vznikle zpozdeni by nam mohlo vadit. Proto pouzivame univerzalni hasovani jako rozsireni h. se separovanymi retezci. Pokud po insertu zjistime, ze je tabulka plna, tak prehasujem do dvojnasobne. Pokud po insertu zjistime, ze je delka retezce delsi nez nejaka konstanta d_i (kterou zatim neumime urcit optimalne), tak prehasujem jinou dostupnou fci.

H = soubor hasovacich fci (do tabulky vel. m)

Pro kazdou vstupni mnozinu ex. "hodne" fci z H, ktere se chovaji dobre(malo kolizi).

Def: Soubor fci z H (U -> {0, 1, ...m-1} se nazyva c-univerzalni, pokud $ \forall x<>y \in U;\ |{h \in H; h(x) = h(y)}| \leq\ \cfrac{c |H|}{m} $

Konstrukce H: Predpokladejme: U = (0, 1, ... N-1), N prvocislo (pro kazde prirozene cislo existuje prvocislo mezi tim cislem a dvounasobkem, takze prinejhorsim natahnem mnozinu na dvojnasobek, aby tohle platilo). $ H = {H_{a,b} (x) = ((ax + b)\ mod\ N)\ mod\ m: a,b = 0..N-1} $, tj. vsechny linearni fce.

Tvrzeni: takto zkonstruovane H je

$ \left\lceil\cfrac{N}{m}\right\rceil^2\Big /\left(\cfrac{N}{m}\right)^2 $ - univerzalni system

...

Veta: necht H je c-univerzalni system, pak pro kazdou mnozinu $ S \subset U,\ |S| = n $ a pro kazde x je ocekavany cas operaci insert/member/delete(x) roven:

$ O\left(\cfrac{c n} {m}\right) $

.. je to prumer pres vsechny fce z H, ne pres vsechny vstupy. Takze kdyz to pro jednu fci neni splneno, muzu nahodne vybrat jinou a mam slusnou sanci, ze pro ni to, na tom samem vstupu, splneno bude.

Veta: necht H je c-univerzalni system, pak pro kazdou mnozinu $ S \subset U,\ |S| = n $ a pro kazde x plati, pokud je $ \mu $ prumerna delka retezce pro prvky s hodnotou h(x), pak:

$ \forall t>1 $ je pravdepodobnost, ze je retezec $ \geq \mu t $ mensi nez $ \cfrac{1}{t} $

Veta: kdyz H je c-univerzalni system na universu U = {0,1,...N-1} hashujici do tabulky velikosti m, pak:

$ |H| > m \cfrac{\lceil (log_mN)-1)\rceil}{c} $

Perfektní hašování

  • Hasovani takove, kde nejsou kolize.
  • Operace insert je bud zakazana, nebo se resi bufferem obcasne zahesovavanym do hlavni tabulky.

Chceme pro danou mnozinu S \subset U nalezt fci h: U -> {0, 1, ..m-1} takovou, ze

  • 1) h je perfektni vuci S
  • 2) h(x) je rychle spocitatelna
  • 3) m je srovnatelne s n
  • 4) h nevyzaduje prilis pameti

Konstrukce:
$ h_k(x) = (k*x\ mod\ N)\ mod\ m $
N = |U|

predpoklad: S pevne dana
$ b_k^i $ je pocet $ x \in S;\ h_k(x) = i $
pak existuje k takove, ze:

$ \sum_{i=0}^{m-1} (b_k^i)^2 \leq n + \cfrac{2n(n-1)}{m} $

.. zkousim jednotlive fce tak dlouho, nez najdu parametr k, pro ktery je suma druhych mocnin delek retezcu < ten vyraz.

Dusledky:

  • 1) pokud m=n (my volime m), pak:
$ \exists k;\ \sum_{i=0}^{m-1} (b_k^i)^2 < 3n $ a k nalezneme v $ O(n*N) $
  • 2) pokud m= 1+n(n-1), pak exists k; h_k je perfektni (suma vyjde < n+2 a pokud by nebyla perfektni, tak je tam alespon jeden retez delky aspon dva, jeho mocnina je 4 a 4 + (n-1) jednoprvkovych retezu dava delku > n+2; spor). Tohle ale nevyhovuje pozadavku 3).
  • 3) Konstrukce do prostoru <3n. Vezmeme fci z dusledku 1) a rozdelime S do m mnozin podle h_k(s). Pro tyto mnoziny nalezneme perfektni fci podle dusledku dva. Tahle kombinace dvou fci pak tvori vyslednou perfektni fci. do <3n se to vleze, protoze pro ty male fce mam k dispozici druhou mocninu prostoru (vzhledem k poctu prvku) a:
$ \sum_{i=0}^{m-1} (b_k^i)^2 < 3n $
 :)

Stale to jeste nesplnuje podminku 4). Dalsi uprava se dela pomoci magie.

Možnosti dynamizace jednotlivých datových struktur

Mapování datových struktur do stránek vnější paměti počítače

Časová složitost alogritmů vyjádřená v počtu I/O operací

Vícerozměrné datové struktury

Dotazy na částečnou shodu a jejich optimalizace

Signaturové metody

Třídění ve vnitřní a vnější paměti