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

Z ωικι.matfyz.cz
Přejít na: navigace, hledání
(Semidynamizace: +spojový seznam)
(Semidynamizace)
 
(Není zobrazeno 149 mezilehlých verzí od 63 dalších uživatelů.)
Řádka 1: Řádka 1:
Zdroje:
+
''Tento souhrn slouží pro přípravu k magisterským [[Státnice|státnicím]]. Detailní informace o předmětu hledej na stránkách [[Datové struktury I]] a [[Datové struktury II]].''
* zaklad prebran z Majklovych [http://mff.modry.cz/statnice/ statnicovych vycucku]
+
* [http://techie.devnull.cz/skola/ds/ds.html skripta Vidner-Kotal] - obsahuji komplet zpracovani uciva z DS
+
  
== Stromové vyhledávací struktury ==
+
== Rozsah látky ==
 +
Seznam [http://www.mff.cuni.cz/studium/bcmgr/ok/i3b4.htm oficiálních] státnicových otázek:
 +
: Stromové vyhledávací struktury: binární stromy a jejich vyvažování, haldy, trie, B-stromy a jejich varianty. Hašování: řešení kolizí, univerzální hašování, perfektní hašování. Mapování datových struktur do stránek vnější paměti počítače. Třídění ve vnitřní a vnější paměti.
 +
 
 +
(Co ubylo a teď to na této stránce najdete "navíc": Možnosti dynamizace jednotlivých datových struktur. Časová složitost algoritmů vyjádřená v počtu I/O operací.)
 +
 
 +
== [[Státnice - Stromové vyhledávací struktury|Stromové vyhledávací struktury]] ==
 
=== Binární stromy a jejich vyvažování ===
 
=== Binární stromy a jejich vyvažování ===
 
* [[wen:Binary search tree]]
 
* [[wen:Binary search tree]]
 
* [[wen:Self-balancing binary search tree]] (AVL stromy, červenočerné stromy)
 
* [[wen:Self-balancing binary search tree]] (AVL stromy, červenočerné stromy)
 +
==== R-B stromy ====
 +
* nejefektivnější variantou vyvážených binárních stromů
 +
* narozdíl od AVL jim stačí pouze 1 bit na uložení stavu uzlu (červená/černá)
 +
* DELETE volá maximálně 2x rotaci nebo 1x rotaci a 1x dvojitou rotaci (AVL až log|S|) - při tom ale může projít celou cestu až ke kořeni!
 +
* INSERT = maximálně 1x rotaci nebo 1x dvojitou rotaci - při tom ale může projít celou cestu až ke kořeni!
 +
 +
R-B stromy lze obecně definovat různými ekvivalentními definicemi, jedna z nich je:
 +
* Barva vrcholu je buď červená, nebo černá
 +
* Cesta do všech vrcholů, které jsou buď listem a nebo mají jednoho potomka je stejně dlouhá (počtem přechodu přes černé vrcholy).
 +
* na cestě za sebou nesmí být dva červené vrcholy (černé ano)
 +
* vyska(T) <= 4 + 2 log |s|
 +
 +
 +
 +
*'''Insert''' - po vlozeni ''u'' a obarveni otce ''u'' na cerveno (syny cerne). pokud rotace, tak hrana R-R pokud ukazeje ven ze stromu, bude LL resp. RR rotace, pokud dovnitr tak LR resp. RL.
 +
*'''Delete''' - po odstraneni ''u'', nahrazeni synem a obarvenim na cerno. pokud rotace, tak cerveny uzel urcuje co. Pokud bratr, nebo vzdalenejsi synovec, tak LL resp. RR rotace, pokud blizsi synovec, tak LR resp. RL rotace. '''Pozn.''' -Detaily a ostani (napr. prebarveni) uz tu neni!
 +
 +
Pokud má R-B strom T na cestě z kořene do listu ''k'' černých vrcholů, pak platí k <= vyska(T) <= 2k.
 +
 +
===== Jednodussi verze =====
 +
* '''Robert Sedgewick''' - jeden z autoru puvodniho paperu o Red-Black trees se k teto strukture po 30 letech vratil a vytvoril Left-leaning Red-Black-Trees.
 +
  * Variantu vyzadujici k implementaci 1/4 zdrojaku
 +
  * Vyrazne zjednodusuje rotace a zachovava ty slozitosti, ktere nas zajimaji
 +
  * Pripomina myslenku stojici za vsemi "Red-black-trees" '''jsou zpusobem, jak zakodovat 2-3 nebo 2-3-4 strom do binarniho stromu'''.
 +
  * Primym dotazem na pana Koubka, zda je mohu pouzit u zkousky mi bylo receno, ze ano, ale musim o nich byt schopen dokazat a umet vse, co se uci/vyzaduje u Red Black Trees
 +
  * Paper vcetne slozitosti zde: [https://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf]
  
 
=== Haldy ===
 
=== Haldy ===
* [[wen:Heap (data structure)]]
+
d-regularni d=3-4: minimalizace porovnani, d=6: rychle
 +
* Lokální (otec reprezentuje prvek menší než syni) a strukturální kriterium (např. strom, kde každý vnitřní uzel má ''d'' synů, až na poslední v level-order (tj. jako BFS), který může mít pouze 1 &le; ''k'' &le; ''d'' synů).
 +
* d-regulární (snadný find min (vždy kořen), umim make heap v O(n), težký merge)
 +
:leftist(snadný find min (vždy kořen), umím merge)
 +
:binomiální(+líná) (lze merge, ale find min horší (mam víc stromů)) [http://ktiml.mff.cuni.cz/~cepek/Slozitost1.ppt Slajdy Složitost I]
 +
:fibonacciho (jako líná binomiální a navíc umím decrease key). [http://ktiml.mff.cuni.cz/~cepek/Slozitost1.ppt Slajdy Složitost I], [[wen:Fibonacci_heap]], [https://cw.felk.cvut.cz/lib/exe/fetch.php/courses/a4m33pal/pal05.pdf Fibonačiho haldy - slajdy ČVUT]
 +
* [[wen:Heap (data structure)]], [[wcs:Halda (datová struktura)]]
  
 
=== Trie ===
 
=== Trie ===
 +
* Pozn.: Jdou použít i ke zjišťování množiny slov s podobností určenou editační vzdáleností a omezenou prahem - jdu více větvemi, pokud jdu přes jiný znak, tak ++podobnost v podstromu.
 
* [[wen:Trie]]
 
* [[wen:Trie]]
  
 
=== B-stromy a jejich varianty ===
 
=== B-stromy a jejich varianty ===
* (a,b) - stromy - zakladni, pararelni INSERT/DELETE, A-Sort, hladinove propojene (a,b) s prstem
+
* (a,b)-stromy  
* B - stromy - (a,b) stromy s fixnim a=ceil(b/2)
+
** Základní
* B+ - stromy - B stromy s listy propojenymi obousmernym spojakem, umoznuje intervalove dotazy v DB, dalsi pouziti ve FS
+
*** INSERT: štěpí zdola nahoru příliš velké vnitřní uzly
* B* - stromy - varianta s podminkou, ze nekorenove nelistove uzly musi byt alespon 2/3 plne. Pri pridavani uzel sdili potomky se svym sousedem misto toho aby se delil. Az kdyz je i soused plny, tak se tyto dva uzly rozdeli na 3.
+
*** DELETE: postupně, zdola nahoru, slévá rodiče se sousedem, nebo (když je soused moc velký na slití) si z nej přesuneme krajní prvek.
 +
** Paralelní INSERT/DELETE &ndash; uzpůsobení operací, aby se nemusel zamykat celý strom. Štěpí/slučuje uzlu preventivně (proto se zde nevoli <math>2a>b</math> tj. napr. <math>2a-1=b</math>, ale treba <math>2a=b</math>) již při sestupu, aby nebylo potřeba se vracet.
 +
** A-Sort &ndash; třídící algoritmus, který naskládá posloupnost do (2,3)-stromu a pak přečte (listy jsou spojeny). Respektuje předtřídění. O(n*log(F/n)).
 +
** Hladinově propojené (a,b)-stromy s prstem (využívají zobecnění vyhledávání použitého v A-Sortu)
 +
* B-stromy &ndash; (a,b)-stromy s fixním <math>a=\lceil{}b/2\rceil</math>
 +
* (B+)-stromy &ndash; B stromy který má klíče ve vnitřních uzlech, ale taky poslední (vnitřní) hladina ukazuje na pozici ve spojovém seznamu se všemi klíči (a ty typicky mají asociovaná nějaká data). Umoznuje intervalove dotazy v DB, dalsi pouziti ve FS.
 +
* (B*)-stromy &ndash; varianta s podminkou, ze nekorenove nelistove uzly musi byt alespon 2/3 plne (<math>a\ge\lceil{}2/3\times{}b\rceil</math>). Pri pridavani uzel sdili potomky se svym sousedem misto toho aby se delil. Az kdyz je i soused plny, tak se tyto dva uzly rozdeli na 3. Lze take dovolit podteceni/preteceni. Prakticky B-strom ktery se chova k pameti trochu lepe - je z 2/3 zaplnena narozdil 1/2.
 +
* (Ne)redundantnost:
 +
** Redundantni &ndash; klice ve smerovacich zaznamech i v listech
 +
** Neredundantni &ndash; klic bud v smerovacim zaznamu, nebo v listu
  
== Hašování ==
+
== [[Státnice - Hašování|Hašování]] ==
 
* [[wen:Hash table]]
 
* [[wen:Hash table]]
  
 
=== Řešení kolizí ===
 
=== Řešení kolizí ===
* hašování s přemisťováním + metoda se dvěma ukazateli
 
* s separujícími řetězci -- při kolizi uložím do pole obě položky, oddělím nějakým separátorem
 
* s uspořádanými separujícími řetězci -- trochu lepší, protože když hledám v políčku prvek, nemusím jet až na konec ale stačí k první větší položce
 
* srůstající hašování
 
** s rozšířenou tabulkou (asi se to tak nejmenuje)
 
  
http://urtax.ms.mff.cuni.cz/~novap2am/poznamky/struktury.sxw
+
==== Hašování se separovanými řetězci ====
 +
* při kolizi uložím do pole tabluky obě položky, každé políčko má [separátní] seznam (řetězec) položek, které tam dle hašovací funkce patří
 +
* očekávaná délka řetězců = n/m
 +
* očekávaný počet testů v úspěšném případě = 1 + &alpha;/2
 +
* očekáváný počet testů v neúspěšném případě je 1,37 a 2,14 pro &alpha; = 1 resp. 2
 +
 
 +
==== Hašování s uspořádanými separovanými řetězci ====
 +
* trochu lepší, protože když hledám v políčku prvek, nemusím jet až na konec ale stačí k první větší položce
 +
* očekáváný počet testů v neúspěšném případě je 1,24 a 1,70 pro &alpha; = 1 resp. 2
 +
 
 +
==== Hašování s přemisťováním ====
 +
* každé políčko má dva ukazatele (''předchůdce, následník''), jejichž pomocí tvoří kolizní položky řetězec
 +
* pokud kolizní položka zabírá místo položce, co na místo dle haše patří, je přemístěna
 +
* nevýhoda: přemísťování při INSERTu zpomaluje
 +
 
 +
==== Metoda se dvěma ukazateli ====
 +
* podobné, políčko má ukazatele ''následník'' a ''začátek řetězce''
 +
* prvky se nepřemisťují, místo toho může být začátek přesměrován pomocí druhého ukazatele
 +
* očekávaný počet testů v úspěšném případě = 1 + &alpha;/2 + &alpha;^2/6
 +
* očekáváný počet testů v neúspěšném případě je 1,66 pro zaplněnou tabulku (&alpha; = 1)
 +
* nevýhoda: tři položky v paměti zabírají příliš paměti
 +
 
 +
==== (Standardní) srůstající hašování ====
 +
* Podobné jako předchozí, kolizní řetězce srůstají s prvky, co na zabraná políčka patří
 +
* Nelze jednoduše mazat položky
 +
* Varianty
 +
** LISCH (''Late Insertion Standard Coalescing Hashing'') &ndash; přidává na konec řetězce
 +
** EISCH (''Early Insertion Standard Coalescing Hashing'') &ndash; přidává na druhé místo řetězce
 +
Varianty se liší v očekávaném počtu testů při úspěšném vyhledávání, pro neúspěšné je odhad pro obě metody stejný, protože posloupnosti se liší jen pořadím prvků v jednotlivých řetězcích.
 +
 
 +
==== Obecné srůstající hašování ====
 +
* Tabulka má pomocnou část, jejíž políčka se přednostně používají pro kolizní řetězce
 +
* Varianty: LICH (''Late Insertion&hellip;''), EICH (''Early Insertion&hellip;''), VICH (''Variable Insertion&hellip;'')
 +
 
 +
==== Hašování s lineárním přidáváním ====
 +
* tabulka má jen klíč, kolizní prvky se dávají na první volné místo
 +
* použitelné do zaplnění 75%
 +
 
 +
==== Dvojité hašování ====
 +
* zobecnění předchozího, přidávám na první volné místo v posloupnosti h1(x) + k*h2(x) pro k = 0, 1, 2, ...
 +
 
 +
==== Pořadí ====
 +
pořadí metod dle počtu testů:
 +
# hašování s řetězci, hašování s přemísťováním
 +
# VICH/LICH, hašování se dvěma ukazateli
 +
# EICH
 +
# EISCH, LISCH
 +
# dvojité hašování
 +
# hašování s lineárním přidáváním
 +
 
 +
==== Zdroje ====
 +
* http://urtax.ms.mff.cuni.cz/~novap2am/poznamky/struktury.sxw
 +
* http://mff.modry.cz/datovky/zapisky/Lenka/
  
 
=== Univerzální Hašování ===
 
=== Univerzální Hašování ===
Řádka 37: Řádka 130:
 
* Zdroje
 
* Zdroje
 
** [http://techie.devnull.cz/skola/ds/ds.html skripta Vidner-Kotal], kapitola 4.1 (strana 26)
 
** [http://techie.devnull.cz/skola/ds/ds.html skripta Vidner-Kotal], kapitola 4.1 (strana 26)
 +
** [http://www.mff.cz/data/ADS_slidy.pdf skripta Petr Hošek (pro Jana Hrice)], kapitola 7.4 (strana 17)
  
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.
+
U normálních hašovacích metod předpokládáme rovnoměrné rozdělení vstupní množiny. To nejde zaručit a nerovnoměrnost a z ní vzniklé zpoždění by nám mohlo vadit. Proto používáme univerzální hašování jako rozšíření hašování se separovanými řetezci. Pokud po insertu zjistíme, že je tabulka plná, tak přehašujeme do tabulky o dvojnasobné velikosti. Pokud po insertu zjistíme, že je délka řetězce delší než nějaká konstanta <math>d_i</math> (kterou zatím neumíme určit optimálně), tak přehašujeme jinou dostupnou funkcí.
  
H = soubor hasovacich fci (do tabulky vel. m)
+
H = soubor hašovacích funkcí (do tabulky velikosti m)
  
Pro kazdou vstupni mnozinu ex. "hodne" fci z H, ktere se chovaji dobre(malo kolizi).
+
Pro každou vstupní množinu existuje "hodně" funkcí z H, které se chovají dobře (málo kolizí).
  
'''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 funkcí z H (U -> {0, 1, ...m-1}) se nazývá '''c-univerzální''', pokud <math>\forall x \neq 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:''' Předpokládejme: U = (0, 1, ... N-1), N prvočíslo (pro každé přirozené číslo existuje prvočíslo mezi tím číslem a dvojnásobkem, takže přinejhorším natáhnem množinu na dvojnasobek, aby tohle platilo).
<math>H = {H_{a,b} (x) = ((ax + b)\ mod\ N)\ mod\ m: a,b = 0..N-1}</math>, tj. vsechny linearni fce.
+
<math>H = {H_{a,b} (x) = ((ax + b)\ mod\ N)\ mod\ m: a,b = 0..N-1}</math>, tj. všechny lineární funkce.
  
'''Tvrzeni:''' takto zkonstruovane H je<br />
+
'''Tvrzení:''' takto zkonstruované H je c-univerzální systém pro<br />
<center><math>\left\lceil\cfrac{N}{m}\right\rceil^2\Big /\left(\cfrac{N}{m}\right)^2</math> - univerzalni system</center>
+
<center><math>c=\left(\left\lceil\cfrac{N}{m}\right\rceil\Big /\cfrac{N}{m}\right)^2</math></center>
  
.. tim jsme ukazali, ze nejake c-univerzalni systemy existuji
+
.. tím jsme ukázali, že nějaké c-univerzální systémy existují
  
'''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 />
+
'''Věta:''' Nechť H je c-univerzální systém, pak pro každou množinu <math>S \subset U,\ |S| = n</math> a pro každé x je očekávaný čas operací 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 průměr přes všechny funkce z H, ne přes všechny vstupy. Takže když to pro jednu funkci není splněno, můžu náhodně vybrat jinou a mám slušnou šanci, že pro ni to, na tom samem vstupu, splněno 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 />
+
'''Věta:''' Nechť H je c-univerzální systém, pak pro každou množinu <math>S \subset U,\ |S| = n</math> a pro každé x platí, pokud je <math>\mu</math> průměrná délka řetězce 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 pravděpodobnost, že je řetězec <math>\geq \mu t</math> menší než <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 />
+
'''Věta:''' Když H je c-univerzální systém na universu U = {0,1,...N-1} hašující do tabulky velikosti m, pak:<br />
<center><math>|H| > m \cfrac{\lceil (log_mN)-1)\rceil}{c}</math></center>
+
<center><math>|I| > m \cfrac{\lceil (log_mN)-1\rceil}{c}</math></center>
 +
 
 +
Mno, podle mne to ma byt takto:
 +
<center><math>|I| > m \cfrac{\lceil {log_mN} \rceil -1}{c}</math></center>
 +
 
 +
Mno, a podle mne je <math>\lceil X - 1 \rceil = \lceil X \rceil - 1</math> takze je to jedno.
  
 
=== Perfektní hašování ===
 
=== Perfektní hašování ===
 
:[[wen:Perfect hash function]]
 
:[[wen:Perfect hash function]]
  
* Hasovani takove, kde nejsou kolize.
+
* Hašování takové, kde nejsou kolize.
* Operace insert je bud zakazana, nebo se resi bufferem obcasne zahesovavanym do hlavni tabulky.
+
* Operace insert je buď zakazaná, nebo se řeší bufferem občasně zahašovávaným do hlavní tabulky.
  
Chceme pro danou mnozinu S \subset U nalezt fci h: U -> {0, 1, ..m-1} takovou, ze
+
Chceme pro danou množinu <math>S \subset U</math> nalézt funkci h: U -> {0, 1, ..m-1} takovou, že
* 1) h je perfektni vuci S
+
* 1) h je perfektní vůči S
* 2) h(x) je rychle spocitatelna
+
* 2) h(x) je rychle spočitatelná
* 3) m je srovnatelne s n
+
* 3) m je srovnatelné s n
* 4) h nevyzaduje prilis pameti
+
* 4) h nevyžaduje příliš paměti
  
 
Konstrukce:<br />
 
Konstrukce:<br />
Řádka 80: Řádka 179:
 
N = |U|<br />
 
N = |U|<br />
  
predpoklad:
+
předpoklad:
S pevne dana<br />
+
S pevně daná<br />
<math>b_k^i</math> je pocet <math>x \in S;\ h_k(x) = i</math><br />
+
<math>b_k^i</math> je počet <math>x \in S;\ h_k(x) = i</math><br />
pak existuje k takove, ze:<br />
+
 
 +
Význam <math>b_k^i</math>: Tyto hodnoty ukazují odchylku od perfektnosti.
 +
 
 +
pokud <math>b_k^i \geq 2 </math>, potom <math>(b_k^i)^2 - b_k^i \geq 2 </math>
 +
 
 +
naopak <math>b_k^i \leq 1 </math>, implikuje <math>(b_k^i)^2 - b_k^i = 0 </math>
 +
 
 +
'''Věta''': Funkce <math>h_k</math> je perfektní, právě když
 +
<center><math>\sum_{i=0}^{m-1} (b_k^i)^2 < n + 2</math><br /></center>
 +
 
 +
Existuje ''k'' takové, ze:<br />
 
<center><math>\sum_{i=0}^{m-1} (b_k^i)^2 \leq n + \cfrac{2n(n-1)}{m}</math><br /></center>
 
<center><math>\sum_{i=0}^{m-1} (b_k^i)^2 \leq n + \cfrac{2n(n-1)}{m}</math><br /></center>
.. zkousim jednotlive fce tak dlouho, nez najdu parametr k, pro ktery je suma druhych mocnin delek retezcu < ten vyraz.
+
.. zkouším jednotlivé funkce tak dlouho, než najdu parametr ''k'', pro který je suma druhých mocnin délek řetězců menší, než ten výraz. (to plyne nějak z vlastností univerzálního hešování!)
 +
 
 +
Důsledky:
 +
* 1) pokud m = n (my volíme m), pak:<br />
 +
<center><math>\exists k;\ \sum_{i=0}^{m-1} (b_k^i)^2 < 3n</math> a ''k'' nalezneme v <math>O(nN)</math></center>
 +
* 2) pokud <math>m = 1+n(n-1)</math>, pak <math>\exists k; h_k</math> je perfektní (suma vyjde < n+2 a pokud by nebyla perfektní, tak je tam alespoň jeden řetězec délky alespoň dva, jeho mocnina je 4 a <math>4 + (n-1)</math> jednoprvkových řetězců dává délku > <math>n+2</math>; spor). Tohle ale nevyhovuje požadavku 3).
 +
* 3) Konstrukce do prostoru < 3n. Vezmeme funkci z důsledku 1) a rozdělíme S do ''m'' množin podle <math>h_k(s)=i</math> (množiny kolidujících prvků pro každé ''i''). Pro tyto množiny nalezneme perfektní funkci podle důsledku dva. Tahle kombinace dvou funkcí pak tvoří výslednou perfektní funkci. Do <3n se to vleze, protože pro ty malé funkce mám k dispozici druhou mocninu prostoru (vzhledem k počtu prvků) a:<br />
 +
<center><math>\sum_{i=0}^{m-1} (b_k^i)^2 < 3n</math></center>
 +
(...kolizní řetězce se rozprostřou tak, že se najde perfektní hašovací funkce pro každý z nich, a díky tomu, že těch řetězců je málo, se to celé vedje do 3''n'' :-)
 +
 
 +
Stále to ještě nesplňuje podmínku 4). Další úprava se dělá pomocí magie.
 +
 
 +
==== Vysvětlení ====
 +
Myslím, že to co je výše jsou takové snippety z důkazu, ale vůbec v tom neni vidět jak to má fungovat. Idea je, že máme primární hashovací funkci <math>h_k(x) = (k*x\ mod\ N)\ mod\ m</math>, která není perfektní, a pak zkonstruujeme sadu sekundárních, už perfektních. Nakonec je složíme, že dostaneme perfektní funkci. Ve skriptech Koubka je tohle zahrabané až na úplném konci a vůbec to neni zdůrazněné, že vlastně kvůli tomuhle sme všechno dokazovali. Pokud si nejste jistí tak doporučuju přečíst originální článek od Cormacka <ref>Cormack, Gordon V., R. N. S. Horspool, and Matthias Kaiserswerth. "Practical perfect hashing." The Computer Journal 28.1 (1985): 54-58.</ref>.
 +
 
 +
'''Def.''' <math>b_k^i=\{x\in S|h_k(x)=i\}</math>
 +
 
 +
Takže jako shrnutí co umíme (viz. výše):
 +
* umíme najít docela dobrou hashovací funkci rychle O(n), nebo trochu lepší ale zas to stojí víc času O(nN)
 +
* umíme najít perfektní hashovací funkci do tabulky <math>m=n(n-1)+1</math> v čase O(nN) (projdeme všechny možnosti a počítáme <math>\sum (b_k^i)^2</math>)
 +
* umíme najít perfektní hashovací funkci do tabulky <math>m=2n(n-1)</math> v čase O(n) (náhodně procházíme možnosti)
 +
 
 +
Samozřejmě bychom mohli pustit rovnou hledání perfektní hash funkce v O(nN), ale tahle funkce by zabrala hodně paměti, takže to uděláme lépe. Takže konstrukce probíhá tak, že najdeme tu neperfektní, ale docela dobrou <math>h_k</math>. O ní platí, že <math>\sum_{i=0}^{m-1} (b_k^i)^2 < 3n</math>. Tuhle hashovací funkci pak použijeme k tomu, že rozhashujeme množinu S do disjunktních množin <math>S_i=\{s\in S|h_k(s)=i\}</math>. A teď pro každou z nich najdeme perfektní hashovací funkci <math>h_{k_i}</math>, do tabulky velké <math>c_i:=m=n(n-1)+1</math>.
  
Dusledky:
+
Teď už máme všechno, co potřebujeme. Vytvoříme si primární soubor a uděláme si v něm značky, kam budeme ukládat <math>S_i</math>. Řádek v primárním souboru kde začíná <math>S_i</math> bude <math>d_i:=\sum_{j=0}^{i-1} c_i</math>. Perfektní hashovací funkce pak bude: <math>h_k(x)=l; g(x)=d_l+h_{k_l}(x)</math>. Když sečteme jak dlouho nám vše trvalo dostaneme O(nN) za první hash funkci, pak zahashujem S do <math>S_i</math> v O(n) abychom spočítali kolik potřebujeme naalokovat na perfektní funkce. Perfektních funkcí bude m a každou budeme hledat v čase <math>O(|S_i|N)</math>, což po sečtení vyjde O(nN). Takže teď jen potřebujeme ukázat, že jsme skutečně spotřebovali méně jak <math>O(n^2)</math> paměti. Pamět můžeme omezit pomocí <math>d_m:=\sum_{j=0}^{m-1} c_i\leq \sum_{j=0}^{m-1} (b_k^i)^2<3n</math>, protože <math>|S_i|(|S_i|-1)+1\leq |S_i|^2=(b_i^k)^2</math>.
* 1) pokud m=n (my volime m), pak:<br />
+
<center><math>\exists k;\ \sum_{i=0}^{m-1} (b_k^i)^2 < 3n</math> a k nalezneme v <math>O(n*N)</math></center>
+
* 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:<br />
+
<center><math>\sum_{i=0}^{m-1} (b_k^i)^2 < 3n</math></center> :)
+
  
Stale to jeste nesplnuje podminku 4). Dalsi uprava se dela pomoci magie.
+
Tohle ještě není úplně stoprocentně perfektní hashovací funkce, ale už jsme dost blízko. Jeden z požadavků na perfektní funkci je, aby ji bylo jednoduché uložit (nejlépe analyticky), což zkonstruovaná funkce g(x) úplně není, což je asi dobré zmínit, i když se tohle hashování už označuje za perfektní. Alternativní metodu, která nám dá trochu hezčí analytickou hashovací funkci, popsali Fredman <ref>Fredman, Michael L., János Komlós, and Endre Szemerédi. "Storing a sparse table with 0 (1) worst case access time." Journal of the ACM (JACM) 31.3 (1984): 538-544</ref>.
  
== Možnosti dynamizace jednotlivých datových struktur ==
+
== [[Státnice - Dynamizace datových struktur|Možnosti dynamizace jednotlivých datových struktur (pouze I1,I4)]] ==
 
*[[wen:Dynamization]]
 
*[[wen:Dynamization]]
 +
*[http://wwwisg.cs.uni-magdeburg.de/ag/lehre/SS2009/GDS/slides/S12.pdf slajdy o semidynamizaci a dynamizaci]
 +
*[http://www.mpi-inf.mpg.de/~mehlhorn/ftp/EATCSmonograph/chapter7.ps Kurt Mehlhorn - zda se puvodni zdroj ]
  
 
Máme obecnou statickou strukturu (neumožňující INSERT a DELETE) a zkoumáme jak do ní toto přidat. Chceme, aby se f(x,A) (vyhledání a tak) v nové struktuře počítalo přibližně stejně rychle jako v té původní. Dále, když vytvoření původní struktury pro n-prvkovou množinu trvalo t, pak operace INSERT by měla vyžadovat čas t/n.
 
Máme obecnou statickou strukturu (neumožňující INSERT a DELETE) a zkoumáme jak do ní toto přidat. Chceme, aby se f(x,A) (vyhledání a tak) v nové struktuře počítalo přibližně stejně rychle jako v té původní. Dále, když vytvoření původní struktury pro n-prvkovou množinu trvalo t, pak operace INSERT by měla vyžadovat čas t/n.
Řádka 111: Řádka 239:
 
;rozložitelnost problému
 
;rozložitelnost problému
 
:Vyhledávací problém je rozložitelný, když existuje operace <math>\oplus</math> spočitatelná v konstantním čase, a platí: když <math>x \in U_1</math> a A a B jsou disjunktní podmnožiny <math>U_2</math>, pak <math>f(x, A \cup B) = f(x,A) \oplus f(x,B)</math>
 
:Vyhledávací problém je rozložitelný, když existuje operace <math>\oplus</math> spočitatelná v konstantním čase, a platí: když <math>x \in U_1</math> a A a B jsou disjunktní podmnožiny <math>U_2</math>, pak <math>f(x, A \cup B) = f(x,A) \oplus f(x,B)</math>
 +
 +
*'''Pozn.:''' ''Vyhledávací problém'' není chápán jen jako dotaz MEMBER(x)! Ale jako hledání řešení nějaké obecné úlohy, kterou lze řešit pouze (nebo dostatečně efektivně) nad statickou strukturou, resp. pro ''rozložitelný problém'' i nad její parcelací.
  
 
=== Semidynamizace ===
 
=== Semidynamizace ===
Máme rozložitelný vyhledávací problém f a pro něj statickou struturu, která ho řeší v čase Q(n), vyžaduje S(n) paměti a vytvoří se v čase P(n), kde Q(n), P(n)/n a S(n)/n jsou neklesající funkce. Pak existuje semidynamická datová struktura D, řešící f v čase O(Q(n) log n), vyžadující O(S(n)) paměti a umožňující INSERT s amortizovanou složitostí O(P(n)/n * log n).
+
Máme rozložitelný vyhledávací problém f a pro něj statickou strukturu, která ho řeší v čase Q(n), vyžaduje S(n) paměti a vytvoří se v čase P(n), kde Q(n), P(n)/n a S(n)/n jsou neklesající funkce. Pak existuje semidynamická datová struktura D, řešící f v čase O(Q(n) log n), vyžadující O(S(n)) paměti a umožňující INSERT s amortizovanou složitostí O(P(n)/n * log n).
  
Postup: A si rozdělíme na sadu disjunktních množin <math>A_i</math>, pro které platí buď <math>A_i = \emptyset</math> nebo <math>|A_i| = 2^i</math>. Nová struktura reprezentující A je potom dynamická struktura reprezentující A (třeba AVL strom), pro každé <math>A_i \neq \emptyset</math> máme S strukturu propojenou s odpovídajícím prvkem ve stromě.
+
Postup:  
 +
* A si rozdělíme na sadu disjunktních množin <math>A_i</math>, pro které platí buď <math>A_i = \emptyset</math> nebo <math>|A_i| = 2^i</math>.  
 +
* Nová pomocná struktura T reprezentující A, kterou použijeme pro test <math>x \in A</math> před libovolnou operací (může to být třeba AVL strom, pro rychlé operace MEMBER a INSERT). Tady je důležité si uvědomit, že vyhledávací problém nemusí být MEMBER, pro INSERT ale potřebujeme pustit nejdřív MEMBER a proto máme tuhle pomocnou strukturu.
 +
* Pro každé <math>A_i \neq \emptyset</math> máme S statickou strukturu. Zároveň si pro každou <math>A_i</math> pamatuji spojový seznam jejích prvků, protože při vkládání nového vyrábím novou statickou strukturu z menších <math>A_i</math>, a dostávat seznamy prvků ze statických struktur by mohlo trvat.
  
Zároveň si pro každou <math>A_i</math> pamatuji spojový seznam jejích prvků, protože při vkládání nového vyrábím novou statickou strukturu z menších <math>A_i</math>, a dostávat seznamy prvků ze statických struktur by mohlo trvat.
+
Vyčíslení f(x,A):
 +
f(x,A) se počítá pro každou množinu <math>A_i</math> zvlášt a pak se výsledky v konstantním čase spojí pomocí operace <math>\oplus</math>.
  
f(x,A) se počítá pro každou menší množinu zvlášt a pak se výsledky v konstantním čase spojí pomocí operace <math>\oplus</math>.
+
INSERT:
 +
Zkontrolujeme pomocí pomocné struktury MEMBER(x,T), dál postupujeme jen pokud prvek ve struktuře není. Vložíme prvek x do pomocné struktury (INSERT(x,T)). Najdeme nejmenší i, pro které <math>A_i=\emptyset</math> do téhle zkolapsujeme všechny <math>A_j, j<i</math>. Spojíme jejich spojové seznamy, přidáme x a vytvoříme novou statickou strukturu S která bude reprezentovat <math>A_i</math>. Zároveň zapomeneme použité <math>A_j</math>.
  
Pak existuje ještě varianta optimalizující INSERT v nejhorším případě.
+
Pak existuje ještě varianta optimalizující INSERT v nejhorším případě. V něm se budují množiny velikosti <math>2^i</math> postupně. Po vložení prvních dvou prvků x,y učiním polovinu kroků stavby {x,y} atd.
  
 
=== Dynamizace ===
 
=== Dynamizace ===
 
Ještě přidáme falešný DELETE (škrtnutí prvku v čase O(n)).
 
Ještě přidáme falešný DELETE (škrtnutí prvku v čase O(n)).
 +
* '''Pozn.''': Falešný DELETE je nový požadavek! Statická struktura ho musí podporovat.
  
 
A rozložíme na disjunktní množiny <math>A_j, j = 0, 1, ..., \log {|A|+3}</math> takové, že buď <math>A_j = \emptyset</math> nebo <math>2^{j-3} < |A_j| \leq 2^j</math>. Každá množina <math>A_j</math> je reprezentována strukturou, která před škrtáním měla velikost <math>\leq 2^j</math>. Pak máme pro každou neprázdnou <math>A_j</math> spojový seznam prvků v ní, provázaný se strukturou reprezentující <math>A_j</math>.
 
A rozložíme na disjunktní množiny <math>A_j, j = 0, 1, ..., \log {|A|+3}</math> takové, že buď <math>A_j = \emptyset</math> nebo <math>2^{j-3} < |A_j| \leq 2^j</math>. Každá množina <math>A_j</math> je reprezentována strukturou, která před škrtáním měla velikost <math>\leq 2^j</math>. Pak máme pro každou neprázdnou <math>A_j</math> spojový seznam prvků v ní, provázaný se strukturou reprezentující <math>A_j</math>.
{{TODO|co přesně bude jako pak reprezentovat A? sada spojových seznamů?}}
+
Amortizovaně INSERT v O(log(n)*P(n)/n), DELETE v O(D_s(n) + log n + P(n)/n)), pokud P(n) je <math>n^{\epsilon}</math>, tak to vychází O(P(n)/n). DELETE naplní A_j jen do půlky, takže to sice stačí, ale nekazí to složitost INSERTu získanou v semidynamické kapitole.
 +
 
 +
*INSERT
 +
:<math>|\bigcup_{i=0}^{j}A_i|<2^j</math>
 +
:<math>A_j</math>='''build'''(<math>\bigcup_{i=0}^{j}A_i|\cup\{x\}</math>)
 +
:'''destroy'''(0,j-1,<math>A_i</math>)
 +
:Když insertbuduje <math>A_j</math>, platí potom <math>2^{j-1}<=|A_j|<=2^{j}</math>
 +
 
 +
*DELETE
 +
:<math>|A_j|=1</math>…'''destroj'''(<math>A_j</math>)
 +
:<math>|A_j|>2^{j-3}+1</math>…'''fake_delete'''(x)
 +
:<math>|A_j|=2^{j-3}+1</math>
 +
::|<math>A_{j-1}|=0</math>…<math>A_{j-1}</math>='''build'''(<math>A_j\smallsetminus\{x\}</math>), '''destroy'''(<math>A_j</math>)
 +
::<math>|A_{j-1}|>=2^{j-2}</math>…'''swap'''(<math>A_{j-1}</math>, <math>A_j</math>), <math>A_{j-1}</math>='''build'''(<math>A_{j-1}\smallsetminus\{x\}</math>) //po swapu
 +
::<math>|A_{j-1}|<2^{j-2}</math>
 +
:::'''if''' <math>|A_j|-1+| A_{j-1}|>2^{j-2}</math> '''then'''
 +
::::<math>A_j</math>='''build'''(<math>(A_j\smallsetminus\{x\})\cup A_{j-1}</math>), '''destroy'''(<math>A_{j-1}</math>)
 +
:::'''else'''
 +
::::<math>A_{j-1}</math>='''build'''(<math>(A_j\smallsetminus\{x\})\cup A_{j-1}</math>), '''destroy'''(<math>A_j</math>)
 +
:Když delete buduje strukturu <math>A_j</math>, platí potom <math>2^{j-2}<=|A_j|<=2^{j-1}</math>
 +
 
 +
A je opět reprezentována nějakou dynamickou strukturou T, která umožňuje operace MEMBER, INSERT a DELETE v <math>O(\log n)</math>.
 +
 
 +
== [[Státnice - Datové struktury ve vnější paměti|Mapování datových struktur do stránek vnější paměti počítače & Časová složitost algoritmů vyjádřená v počtu I/O operací (pouze I1,I4)]] ==
 +
 
 +
=== Schéma organizace souborů (SOS) ===
 +
 
 +
* fyzické soubory
 +
** délka fyzického záznamu ''R'', délka stránky ''B'', blokovací faktor ''B/R=b''
 +
** blokované, neblokované, přerostlé záznamy
 +
* logické soubory
 +
** logické stránky (bloky) konstantní délky
 +
** primární soubor (velikosti ''N'')
 +
* dotazy nad soubory
 +
** dotaz na úplnou shodu, na částečnou shodu, dotaz na úplnou intervalovou shodu, dotaz na částečnou intervalovou shodu
 +
** vyváženost struktury (rozlišují se podle ní ''statické'' a ''dynamické'' SOS
 +
**# omezení délky cesty v datové struktuře
 +
**# naplněnost logických stránek (faktor naplnění stránky &lambda;), štěpení stránky, slévání stránky
 +
* fyzické nosiče souborů
 +
; magentická páska: sekvenční čtení, využívá se buffer (velikosti jedné stránky), páska obsahuje meziblokové mezery
 +
; magnetický disk: ''stopy'', ''cylindry'', ''bloky'', parametry: ''s'' - seek, ''r'' - rotation (rovno '''polovině''') doby otáčky, ''btt'' - block transfer time,
 +
 
 +
=== Statické metody organizace souborů ===
 +
 
 +
==== Počty I/O operací - základní přehled ====
 +
 
 +
Rozhoduje kolik se přečte stránek z disku, kolik se jich zapíše a jak dlouho to trvá
 +
 
 +
; Fetch: čas pro načtení jedné stránky <math> T_F = s+r+btt</math>, pro další stránky na stejném cylindru se nemusí hlavičky přesouvat (<math> T_F = r+btt</math>)
 +
; Rewrite: přepsání stránky na disku (tj. přenos stránky do vnější paměti, změnu ve vnější paměti a přenos zpět na disk), lze vyřešit v době, než se plotna disku jednou otočí, tedy <math>T_RW = 2r - btt + btt = 2r </math>
 +
; Insert: vložení zánamu (je nejprve zapotřebí načíst stránku, do které se bude zapisovat, do paměti) <math>T_I</math>
 +
; Delete: smazání stráky (obvykle prohlášení za neplatnou) <math>T_D</math>
 +
; Update: změna záznamu ve stránce <math>T_U</math>
 +
; Reorganizace: <math>T_Y</math>
 +
 
 +
Pro jednotlivé typy organizace souborů bude úvaha nad jejich počty IO operací uvedena u jejich popisu.
 +
 
 +
==== Sekvenční soubor ====
 +
 
 +
* neuspořádaný - oproti hromadě záznamy pevné délky
 +
* uspořádaný - podle jednoho klíče
 +
 
 +
Odhady pro uspořádaný sekvenční soubor:
 +
* <math>T_F = log_{2} (N/\lfloor b \rfloor)(s+r+btt)</math> - nalezení záznamu metodou půlení intervalů
 +
* <math>T_I = s+r+btt + T_RW + T_Y/o</math> - načte se stránka kam se bude vkládat, přepíše se a připočte se poměrný čas potřebný pro reorganizaci souboru (až k ní dojde).
 +
* update
 +
: {{TODO|Dopsat, doporučuju skripta Pokorný-Žemlička - Základy implementace souborů a databází}}
  
== Mapování datových struktur do stránek vnější paměti počítače ==
 
 
(prosim doplnujte co si myslite ze sem patri nebo primo vite ze se zkouselo, nejlepe i s info kde to najit)
 
(prosim doplnujte co si myslite ze sem patri nebo primo vite ze se zkouselo, nejlepe i s info kde to najit)
 
* schema organizace souboru (hromada, sekv, index-sekv.) - zkouselo se (Zemlicka), skripta Zaklady implementace souboru a databazi (stare vydani str. 15-30) (viz též [http://student.cvut.cz/cwut/index.php/Datov%C3%A9_modely#Fyzick.C3.BD_pohled_na_data:_z.C3.A1znam.2C_soubor.2C_tabulka.2C_index  ČVUT wiki]
 
* schema organizace souboru (hromada, sekv, index-sekv.) - zkouselo se (Zemlicka), skripta Zaklady implementace souboru a databazi (stare vydani str. 15-30) (viz též [http://student.cvut.cz/cwut/index.php/Datov%C3%A9_modely#Fyzick.C3.BD_pohled_na_data:_z.C3.A1znam.2C_soubor.2C_tabulka.2C_index  ČVUT wiki]
Řádka 135: Řádka 336:
 
* staticke hasovani - Cormack, Larson+Kalja (Pok97 31-35)
 
* staticke hasovani - Cormack, Larson+Kalja (Pok97 31-35)
 
* dynamicke hasovani - Fagin, Litwin, skupinova stepeni stranek (Pok97 41-47)
 
* dynamicke hasovani - Fagin, Litwin, skupinova stepeni stranek (Pok97 41-47)
 +
* [http://en.wikipedia.org/wiki/External_sorting Externy mergesort]? Je to sice uz v triedeni vo vonkajsej pamati, ale ked je tu aj ext. hashovanie...
 +
* Majerech akceptoval rozpravanie o externom MergeSorte, B+ stromoch.
  
== Časová složitost algoritmů vyjádřená v počtu I/O operací ==
+
== Dolní odhady pro uspořádání (rozhodovací stromy) ==
- IMHO patri pod predchozi otazku
+
:''podle http://ksvi.mff.cuni.cz/~topfer/ppt/Progr-11.pdf''
  
== Vícerozměrné datové struktury ==
+
Třídíme-li s pomocí porovnávání, můžeme si výpočet znázornit binárním stromem. Začínáme v kořeni, v uzlech porovnáváme a větvíme, v listech máme setříděno. Pro každá vstupní data se výpočet někde odliší od ostatních, strom má <math>n!</math> listů (tolik je možných uspořádání množiny s <math>n</math> prvky.) Výška stromu je počet provedených porovnání při nejdelším výpočtu (v nejhorším případě) je alespoň <math>\log_2(n!)</math>. (Úplný binární strom s <math>k</math> listy má výšku <math>\log_2 k</math>, neúplný je vyšší.) Časová složitost třídícího algoritmu založeného na porovnávání proto nemůže být lepší než <math>O(\log_2(n!)) = O(n\ \log n)</math>.
=== Dotazy na částečnou shodu a jejich optimalizace ===
+
* v hasovacich schematech - Pokorny 35-40 (stare vydani) - optimalizace prumerneho poctu I/O operaci pro specialni variantu dotazu na 1 atribut ze znamych pravdepodobnosti atributu; deskriptory stranek a 2urovnove vrstvene kodovani; Grayovy kody
+
* ve vicerozmernych B-stromech - Pok. 71-73
+
* vicerozmerna mrizka - Pok. 73-75
+
  
=== Signaturové metody ===
+
Podle Stirlingovy formule:
Rozdělím si text na logické bloky, ty nějak zakóduju do signatur (řetězce bitů). Dotaz (konjunkci termů) pak taky zakóduju si signatury, a porovnáním se signaturami jednotlivých bloků vyloučím část dokumentů, které dotazu určitě nevyhovují.
+
:<math>n! \approx \sqrt{2\pi n}\, \left(\frac{n}{e}\right)^{n}</math> (to je ona)
 +
:<math>O(\log_2 n!) = O(\log_2{\sqrt{2\pi n}\, \left(\frac{n}{e}\right)^{n}}) = O(n \log n)</math> (Logaritmus odmocniny bude asymptoticky <math>O(\log n)</math>, <math>(n/e)^n</math> bude <math>O(n \log n)</math>, a požere to.)
  
* máme funkci h, která zobrazuje termy na bitové řetězce; OR binárních reprezentací termů je signatura dokumentu
+
*Pro mne snazší odhad: n<sup>n</sup> &ge; n! &ge; n<sup>n/2</sup>
* signatura bloku SD vyhovuje signatuře dotazu SQ, pokud SQ & SD == SQ (nebo taky SQ & ~SD == 0)
+
*k-tý prvek nelze s porovnanim ziskat driv nez v O(n): musim mit alespon retizek s n-1 hranami.
 +
*konvexni obal nelze lepe nez O(n*log(n)): pro [x,x<sup>2</sup>] umim tridit
  
http://kocour.ms.mff.cuni.cz/~pokorny/vyuka/pokorny6/
 
 
http://www.ms.mff.cuni.cz/~kopecky/vyuka/dis/07/dis07_v1.html
 
  
== Třídění ve vnitřní a vnější paměti ==
+
== [[Státnice - Třídění|Třídění ve vnitřní a vnější paměti]] ==
 
=== Vnejsi pamet ===
 
=== Vnejsi pamet ===
 +
*[[wen:External sorting]]
 +
* Celkem pěkně popsané ve skriptech Pokorný, Žemlička k OZD (jsou dostupné na Studnici)
  
 
Merge sort jak je popsan v pokornem:
 
Merge sort jak je popsan v pokornem:
Řádka 167: Řádka 367:
 
Tak ziskam setrizenou skupinu bloku m nasobne velikosti. a opakuju.
 
Tak ziskam setrizenou skupinu bloku m nasobne velikosti. a opakuju.
 
Pokud se mi do pameti vejde vice nez odmocnina z celkoveho poctu bloku, tak lze provest na dva pruchody (obecne M - pocet bloku, co se vejdou do OP, N pocet vsech bloku zabranych mnozinou, tak to setridim na log_M N pruchodu)
 
Pokud se mi do pameti vejde vice nez odmocnina z celkoveho poctu bloku, tak lze provest na dva pruchody (obecne M - pocet bloku, co se vejdou do OP, N pocet vsech bloku zabranych mnozinou, tak to setridim na log_M N pruchodu)
 +
 +
* Behy pro trideni (resp. externi trideni) lze delat pomoci 2 hald. Udelam jednu pres celou pamet. Trham minimum a novy nacitany prvek: pokud je vetsi nez odeslane min tak zatridim do haldy, jinak ulozim do pameti na volne misto (stavim 2. haldu)
  
 
=== Vnitrni pamet ===
 
=== Vnitrni pamet ===
Řádka 175: Řádka 377:
  
 
insert sort - pri nacteni noveho prvku jej zatridi do mnoziny jiz setrizenych porovnavanim se sousedem. Worst: O(n2), Avg O(n2), O (n+ počet transpozic), ale lepsi konstanta nez bubblesort  
 
insert sort - pri nacteni noveho prvku jej zatridi do mnoziny jiz setrizenych porovnavanim se sousedem. Worst: O(n2), Avg O(n2), O (n+ počet transpozic), ale lepsi konstanta nez bubblesort  
 +
 +
A-sort - ma podobonou vlastnost jako insert sort: pri malem poctu transpozic je rychly. I jeho myslenka je podobna. Pouze pri zatrizovani ma misto jednoducheho pole setrizenych prvku nejaky stromecek (napr. 2,3-strom nebo AVL strom), do ktereho nove prvky vklada. Takto je mozne opravit k transpozic na pouhych log(k) kroku.
  
 
selection sort - najde nejmensi prvek, vynda ho a da na vystup (v in-place verzi vymeni s prvnim v posl.), opakuje se zbytkem - O(n2) nejhorsi i ocekavany
 
selection sort - najde nejmensi prvek, vynda ho a da na vystup (v in-place verzi vymeni s prvnim v posl.), opakuje se zbytkem - O(n2) nejhorsi i ocekavany
Řádka 199: Řádka 403:
  
 
Dlhsi seznam viz [http://en.wikipedia.org/wiki/Sorting_algorithm#List_of_sorting_algorithms wikipedia]
 
Dlhsi seznam viz [http://en.wikipedia.org/wiki/Sorting_algorithm#List_of_sorting_algorithms wikipedia]
 +
 +
== Samoupravující datové struktury (pouze I1,I4) ==
 +
:''[https://en.wikipedia.org/wiki/Self-organizing_list Wiki(en) - samoorganizujici seznamy]''
 +
:''[http://en.wikipedia.org/wiki/Splay_tree Wiki(en) - Splay stromy(samoorganizujici stromy)]''
 +
:''[http://cs.indstate.edu/~rcheruku/presentation.pdf Splay stromy(samoorganizujici stromy) - Cheruku Ravi Teja]''
 +
:''[http://wiki.algoviz.org/search/node/splay Pointers to splay tree visualizations]''
 +
 +
=== Samoupravující seznamy ===
 +
 +
Zdroj: [http://ktiml.mff.cuni.cz/teaching/files/materials/KoubekVaclav_BINVYHST.pdf  http://ktiml.mff.cuni.cz/teaching/files/materials/KoubekVaclav_BINVYHST.pdf str. 36 podkapitola 6]
 +
 +
 +
Předpoklady:
 +
*Prvky jsou uložené ve spojovém seznamu.
 +
*Vyhledává se lineárním průchodem.
 +
 +
Při vyhledávání se prvky přemísťují k začátku seznamu tak, aby se nejčastěji vyhledávané prvky byly na začátku. Nejlepší čas na vyhledání
 +
prvku se pak blíží konstatnímu. V nejhorším případě(hledaný prvek je na konci) ovšem stále <math>O(n)</math> jako u klasického spojáku.
 +
 +
Metody organizace(podrobněji viz wiki):
 +
#Move To Front(MTF) - vyhledaný prvek se prostě přepojí na začátek. Reaguje velmi rychle na změny ve vyhledávacích vzorů. Až moc rychle - občasné vyhledání jinak nepoužívaného prvku rozbije optimální strukturu seznamu.
 +
#Počítací metoda - každý uzel má počítadlo na počet vyhledávání. Uzly se udržují setřízené podle počtu vyhledání.Potřebuje navíc pamět pro počítadla. Reaguje pomaleji na změnu vyhledávacích vzorů, ale někdy zase až moc pomalu(viz příklad na wiki).
 +
#Transpoziční metoda - přehazuje prvek s předchůdcem, pokud existuje. Opět se přizpůsobuje vyhledávacím vzorům pomaleji než MTF.
 +
 +
Aplikace: V překladačích a interpretech se používají k uložení tabulky symbolů během kompilace/interpretace zdrojáku.
 +
 +
=== Splay stromy ===
 +
Binární vyhledávací stromy. Při vyhledání prvku X se strom přeorganizuje tak, aby X byl v kořeni stromu.
 +
 +
Algoritmus operace splay pro uzel N [http://www.ibr.cs.tu-bs.de/courses/ss98/audii/applets/BST/Splay-Algorithm.html]:
 +
 +
while N není kořen do
 +
  1.Pokud rodič N(dále R) není kořen, proveď rotaci tak, aby N byl kořen a R jeho potomek.
 +
  2.Pokud N a R mají stejnou orientaci(oba jsou levé nebo pravé děti). Rotuj R a potom N.
 +
  3.Pokud N a R mají různou orientaci, rotuj dvakrát N.
 +
wend
 +
 +
Insert N:
 +
1.Vlož N stejně jako v binárním stromě
 +
2.Splay(N)
 +
 +
Delete N:
 +
1.Stejně jako v binárním stromě
 +
2.Splay(rodič N).
 +
 +
====Amortizovaný odhad ceny splay operace====
 +
[http://www.cs.cornell.edu/courses/cs3110/2011sp/recitations/rec25-splay/splay.htm]
 +
 +
Výhody:
 +
*Jednoduchá implementace.
 +
*V průměrném případě stejně efektivní jako ostatní stromy.
 +
*Nepotřebují paměť navíc.
 +
 +
Nevýhody:
 +
*Může zdegenerovat na obyčený seznam, tj. hloubka stromu je lineární. Operace mají "dobrou" složitost amortizovanou.
 +
*Problematické použití ve vícevláknovém prostředí. Vyhledání prvku(typická read-only operace) mění strom.
 +
 +
== Relaxované vyhledávací stromy ==
 +
 +
[http://ktiml.mff.cuni.cz/teaching/files/materials/binvyhst.pdf Skripta Koubek str 16. podkapitola 3], [http://www.dmi.unict.it/~faro/algocom/prova01/paper16.pdf Článek "Relaxed Balanced Red-Black Trees"]
 +
 +
Co se stane se stromy, kde po přidání/odebrání nevyvažujeme. Rychlejší operace, více uživatelů zároveň, vyvažování necháme na později. Tyto stromy nazýváme relaxované.
 +
* Možná degenerace stromu - delší vyhledávání
 +
* Lze jednoduše nevyvážený strom vyvážit bez přebudování celé struktury?
 +
 +
Požadavek
 +
* v - vrchol černý a v podstromu vrcholu chybí jeden černý uzel
 +
* b - vrchol i jeho otec červené, exkluzivní, s vrcholem nesmí být svázán žádný jiný požadavek
 +
 +
Příklad na RB stromech, lze analogicky pro ostatní. Máme frontu vyvažovacích požadavků, pokud prázdná, strom je vyvážený.
 +
Nad daty pracuje několik procesů najednou:
 +
* uživatelský - provádí vyhledávání, přidávání a odebírání. Pokud po aktualizaci vznikne požadavek na vyvážení, přidá ho do fronty
 +
* správcovký - bere vhodné požadavky z fronty a provádí je. Požadavky mohou být buď zcela ošetřeny nebo transformovány v jiný požadavek blíže kořeni.
 +
 +
== <strike>Vícerozměrné datové struktury</strike> (asi zrušeno) ==
 +
=== Dotazy na částečnou shodu a jejich optimalizace ===
 +
:''see http://ksi.mff.cuni.cz/~pokorny/vyuka/pokorny/''
 +
* v hasovacich schematech - Pokorny 35-40 (stare vydani) - optimalizace prumerneho poctu I/O operaci pro specialni variantu dotazu na 1 atribut ze znamych pravdepodobnosti atributu; deskriptory stranek a 2urovnove vrstvene kodovani; Grayovy kody
 +
* ve vicerozmernych B-stromech - Pok. 71-73
 +
* vicerozmerna mrizka - Pok. 73-75
 +
 +
=== Signaturové metody ===
 +
Rozdělím si text na logické bloky, ty nějak zakóduju do signatur (řetězce bitů). Dotaz (konjunkci termů) pak taky zakóduju si signatury, a porovnáním se signaturami jednotlivých bloků vyloučím část dokumentů, které dotazu určitě nevyhovují.
 +
 +
* máme funkci h, která zobrazuje termy na bitové řetězce; OR binárních reprezentací termů je signatura dokumentu
 +
* signatura bloku SD vyhovuje signatuře dotazu SQ, pokud SQ & SD == SQ (nebo taky SQ & ~SD == 0)
 +
 +
http://kocour.ms.mff.cuni.cz/~pokorny/vyuka/pokorny6/
 +
 +
http://www.ms.mff.cuni.cz/~kopecky/vyuka/dis/07/dis07_v1.html
 +
 +
 +
== Další materiály ==
 +
* Základ přebrán z Majklových [http://mff.modry.cz/statnice/ státnicových výcucků]
 +
* [[TIN066_Skripta_Vidner-Kotal|Skripta Vidner-Kotal]] &ndash; neoficiální skripta
 +
* Václav Koubek, Alena Koubková: <em>Datové struktury I, II</em> ([http://ktiml.mff.cuni.cz/index.php?select=teaching&section=sources&lang=czech ktiml]) &ndash; dost obsáhlé
 +
* Melhorn K., <em>Data Structures and Algorithms</em>: [http://www.mpi-inf.mpg.de/~mehlhorn/DatAlgbooks.html]
 +
* Mareš M. a kol. <em>Algoritmy a Datové struktury I a II</em>: [http://mj.ucw.cz/vyuka/]
 +
* Pokorny. Slajdy k prednasce <em>Organizace a zpracovani dat</em>: [http://www.ksi.mff.cuni.cz/~pokorny/vyuka/pokorny/]
 +
* Vizualizace datových struktur: [https://www.cs.usfca.edu/~galles/visualization/Algorithms.html]
 +
 +
[[Category: Státnice Informatika Mgr.]]

Aktuální verze z 31. 8. 2016, 14:14

Tento souhrn slouží pro přípravu k magisterským státnicím. Detailní informace o předmětu hledej na stránkách Datové struktury I a Datové struktury II.

Obsah

Rozsah látky[editovat | editovat zdroj]

Seznam oficiálních státnicových otázek:

Stromové vyhledávací struktury: binární stromy a jejich vyvažování, haldy, trie, B-stromy a jejich varianty. Hašování: řešení kolizí, univerzální hašování, perfektní hašování. Mapování datových struktur do stránek vnější paměti počítače. Třídění ve vnitřní a vnější paměti.

(Co ubylo a teď to na této stránce najdete "navíc": Možnosti dynamizace jednotlivých datových struktur. Časová složitost algoritmů vyjádřená v počtu I/O operací.)

Stromové vyhledávací struktury[editovat | editovat zdroj]

Binární stromy a jejich vyvažování[editovat | editovat zdroj]

R-B stromy[editovat | editovat zdroj]

  • nejefektivnější variantou vyvážených binárních stromů
  • narozdíl od AVL jim stačí pouze 1 bit na uložení stavu uzlu (červená/černá)
  • DELETE volá maximálně 2x rotaci nebo 1x rotaci a 1x dvojitou rotaci (AVL až log|S|) - při tom ale může projít celou cestu až ke kořeni!
  • INSERT = maximálně 1x rotaci nebo 1x dvojitou rotaci - při tom ale může projít celou cestu až ke kořeni!

R-B stromy lze obecně definovat různými ekvivalentními definicemi, jedna z nich je:

  • Barva vrcholu je buď červená, nebo černá
  • Cesta do všech vrcholů, které jsou buď listem a nebo mají jednoho potomka je stejně dlouhá (počtem přechodu přes černé vrcholy).
  • na cestě za sebou nesmí být dva červené vrcholy (černé ano)
  • vyska(T) <= 4 + 2 log |s|


  • Insert - po vlozeni u a obarveni otce u na cerveno (syny cerne). pokud rotace, tak hrana R-R pokud ukazeje ven ze stromu, bude LL resp. RR rotace, pokud dovnitr tak LR resp. RL.
  • Delete - po odstraneni u, nahrazeni synem a obarvenim na cerno. pokud rotace, tak cerveny uzel urcuje co. Pokud bratr, nebo vzdalenejsi synovec, tak LL resp. RR rotace, pokud blizsi synovec, tak LR resp. RL rotace. Pozn. -Detaily a ostani (napr. prebarveni) uz tu neni!

Pokud má R-B strom T na cestě z kořene do listu k černých vrcholů, pak platí k <= vyska(T) <= 2k.

Jednodussi verze[editovat | editovat zdroj]
  • Robert Sedgewick - jeden z autoru puvodniho paperu o Red-Black trees se k teto strukture po 30 letech vratil a vytvoril Left-leaning Red-Black-Trees.
 * Variantu vyzadujici k implementaci 1/4 zdrojaku
 * Vyrazne zjednodusuje rotace a zachovava ty slozitosti, ktere nas zajimaji
 * Pripomina myslenku stojici za vsemi "Red-black-trees" jsou zpusobem, jak zakodovat 2-3 nebo 2-3-4 strom do binarniho stromu. 
 * Primym dotazem na pana Koubka, zda je mohu pouzit u zkousky mi bylo receno, ze ano, ale musim o nich byt schopen dokazat a umet vse, co se uci/vyzaduje u Red Black Trees
 * Paper vcetne slozitosti zde: [1]

Haldy[editovat | editovat zdroj]

d-regularni d=3-4: minimalizace porovnani, d=6: rychle

  • Lokální (otec reprezentuje prvek menší než syni) a strukturální kriterium (např. strom, kde každý vnitřní uzel má d synů, až na poslední v level-order (tj. jako BFS), který může mít pouze 1 ≤ kd synů).
  • d-regulární (snadný find min (vždy kořen), umim make heap v O(n), težký merge)
leftist(snadný find min (vždy kořen), umím merge)
binomiální(+líná) (lze merge, ale find min horší (mam víc stromů)) Slajdy Složitost I
fibonacciho (jako líná binomiální a navíc umím decrease key). Slajdy Složitost I, wen:Fibonacci_heap, Fibonačiho haldy - slajdy ČVUT

Trie[editovat | editovat zdroj]

  • Pozn.: Jdou použít i ke zjišťování množiny slov s podobností určenou editační vzdáleností a omezenou prahem - jdu více větvemi, pokud jdu přes jiný znak, tak ++podobnost v podstromu.
  • wen:Trie

B-stromy a jejich varianty[editovat | editovat zdroj]

  • (a,b)-stromy
    • Základní
      • INSERT: štěpí zdola nahoru příliš velké vnitřní uzly
      • DELETE: postupně, zdola nahoru, slévá rodiče se sousedem, nebo (když je soused moc velký na slití) si z nej přesuneme krajní prvek.
    • Paralelní INSERT/DELETE – uzpůsobení operací, aby se nemusel zamykat celý strom. Štěpí/slučuje uzlu preventivně (proto se zde nevoli $ 2a>b $ tj. napr. $ 2a-1=b $, ale treba $ 2a=b $) již při sestupu, aby nebylo potřeba se vracet.
    • A-Sort – třídící algoritmus, který naskládá posloupnost do (2,3)-stromu a pak přečte (listy jsou spojeny). Respektuje předtřídění. O(n*log(F/n)).
    • Hladinově propojené (a,b)-stromy s prstem (využívají zobecnění vyhledávání použitého v A-Sortu)
  • B-stromy – (a,b)-stromy s fixním $ a=\lceil{}b/2\rceil $
  • (B+)-stromy – B stromy který má klíče ve vnitřních uzlech, ale taky poslední (vnitřní) hladina ukazuje na pozici ve spojovém seznamu se všemi klíči (a ty typicky mají asociovaná nějaká data). Umoznuje intervalove dotazy v DB, dalsi pouziti ve FS.
  • (B*)-stromy – varianta s podminkou, ze nekorenove nelistove uzly musi byt alespon 2/3 plne ($ a\ge\lceil{}2/3\times{}b\rceil $). Pri pridavani uzel sdili potomky se svym sousedem misto toho aby se delil. Az kdyz je i soused plny, tak se tyto dva uzly rozdeli na 3. Lze take dovolit podteceni/preteceni. Prakticky B-strom ktery se chova k pameti trochu lepe - je z 2/3 zaplnena narozdil 1/2.
  • (Ne)redundantnost:
    • Redundantni – klice ve smerovacich zaznamech i v listech
    • Neredundantni – klic bud v smerovacim zaznamu, nebo v listu

Hašování[editovat | editovat zdroj]

Řešení kolizí[editovat | editovat zdroj]

Hašování se separovanými řetězci[editovat | editovat zdroj]

  • při kolizi uložím do pole tabluky obě položky, každé políčko má [separátní] seznam (řetězec) položek, které tam dle hašovací funkce patří
  • očekávaná délka řetězců = n/m
  • očekávaný počet testů v úspěšném případě = 1 + α/2
  • očekáváný počet testů v neúspěšném případě je 1,37 a 2,14 pro α = 1 resp. 2

Hašování s uspořádanými separovanými řetězci[editovat | editovat zdroj]

  • trochu lepší, protože když hledám v políčku prvek, nemusím jet až na konec ale stačí k první větší položce
  • očekáváný počet testů v neúspěšném případě je 1,24 a 1,70 pro α = 1 resp. 2

Hašování s přemisťováním[editovat | editovat zdroj]

  • každé políčko má dva ukazatele (předchůdce, následník), jejichž pomocí tvoří kolizní položky řetězec
  • pokud kolizní položka zabírá místo položce, co na místo dle haše patří, je přemístěna
  • nevýhoda: přemísťování při INSERTu zpomaluje

Metoda se dvěma ukazateli[editovat | editovat zdroj]

  • podobné, políčko má ukazatele následník a začátek řetězce
  • prvky se nepřemisťují, místo toho může být začátek přesměrován pomocí druhého ukazatele
  • očekávaný počet testů v úspěšném případě = 1 + α/2 + α^2/6
  • očekáváný počet testů v neúspěšném případě je 1,66 pro zaplněnou tabulku (α = 1)
  • nevýhoda: tři položky v paměti zabírají příliš paměti

(Standardní) srůstající hašování[editovat | editovat zdroj]

  • Podobné jako předchozí, kolizní řetězce srůstají s prvky, co na zabraná políčka patří
  • Nelze jednoduše mazat položky
  • Varianty
    • LISCH (Late Insertion Standard Coalescing Hashing) – přidává na konec řetězce
    • EISCH (Early Insertion Standard Coalescing Hashing) – přidává na druhé místo řetězce

Varianty se liší v očekávaném počtu testů při úspěšném vyhledávání, pro neúspěšné je odhad pro obě metody stejný, protože posloupnosti se liší jen pořadím prvků v jednotlivých řetězcích.

Obecné srůstající hašování[editovat | editovat zdroj]

  • Tabulka má pomocnou část, jejíž políčka se přednostně používají pro kolizní řetězce
  • Varianty: LICH (Late Insertion…), EICH (Early Insertion…), VICH (Variable Insertion…)

Hašování s lineárním přidáváním[editovat | editovat zdroj]

  • tabulka má jen klíč, kolizní prvky se dávají na první volné místo
  • použitelné do zaplnění 75%

Dvojité hašování[editovat | editovat zdroj]

  • zobecnění předchozího, přidávám na první volné místo v posloupnosti h1(x) + k*h2(x) pro k = 0, 1, 2, ...

Pořadí[editovat | editovat zdroj]

pořadí metod dle počtu testů:

  1. hašování s řetězci, hašování s přemísťováním
  2. VICH/LICH, hašování se dvěma ukazateli
  3. EICH
  4. EISCH, LISCH
  5. dvojité hašování
  6. hašování s lineárním přidáváním

Zdroje[editovat | editovat zdroj]

Univerzální Hašování[editovat | editovat zdroj]

wen:Universal hashing

U normálních hašovacích metod předpokládáme rovnoměrné rozdělení vstupní množiny. To nejde zaručit a nerovnoměrnost a z ní vzniklé zpoždění by nám mohlo vadit. Proto používáme univerzální hašování jako rozšíření hašování se separovanými řetezci. Pokud po insertu zjistíme, že je tabulka plná, tak přehašujeme do tabulky o dvojnasobné velikosti. Pokud po insertu zjistíme, že je délka řetězce delší než nějaká konstanta $ d_i $ (kterou zatím neumíme určit optimálně), tak přehašujeme jinou dostupnou funkcí.

H = soubor hašovacích funkcí (do tabulky velikosti m)

Pro každou vstupní množinu existuje "hodně" funkcí z H, které se chovají dobře (málo kolizí).

Def: Soubor funkcí z H (U -> {0, 1, ...m-1}) se nazývá c-univerzální, pokud $ \forall x \neq y \in U;\ | \{ h \in H: h(x) = h(y) \}| \leq\ \cfrac{c |H|}{m} $

Konstrukce H: Předpokládejme: U = (0, 1, ... N-1), N prvočíslo (pro každé přirozené číslo existuje prvočíslo mezi tím číslem a dvojnásobkem, takže přinejhorším natáhnem množinu na dvojnasobek, aby tohle platilo). $ H = {H_{a,b} (x) = ((ax + b)\ mod\ N)\ mod\ m: a,b = 0..N-1} $, tj. všechny lineární funkce.

Tvrzení: takto zkonstruované H je c-univerzální systém pro

$ c=\left(\left\lceil\cfrac{N}{m}\right\rceil\Big /\cfrac{N}{m}\right)^2 $

.. tím jsme ukázali, že nějaké c-univerzální systémy existují

Věta: Nechť H je c-univerzální systém, pak pro každou množinu $ S \subset U,\ |S| = n $ a pro každé x je očekávaný čas operací insert/member/delete(x) roven:

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

.. je to průměr přes všechny funkce z H, ne přes všechny vstupy. Takže když to pro jednu funkci není splněno, můžu náhodně vybrat jinou a mám slušnou šanci, že pro ni to, na tom samem vstupu, splněno bude.

Věta: Nechť H je c-univerzální systém, pak pro každou množinu $ S \subset U,\ |S| = n $ a pro každé x platí, pokud je $ \mu $ průměrná délka řetězce pro prvky s hodnotou h(x), pak:

$ \forall t>1 $ je pravděpodobnost, že je řetězec $ \geq \mu t $ menší než $ \cfrac{1}{t} $

Věta: Když H je c-univerzální systém na universu U = {0,1,...N-1} hašující do tabulky velikosti m, pak:

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

Mno, podle mne to ma byt takto:

$ |I| > m \cfrac{\lceil {log_mN} \rceil -1}{c} $

Mno, a podle mne je $ \lceil X - 1 \rceil = \lceil X \rceil - 1 $ takze je to jedno.

Perfektní hašování[editovat | editovat zdroj]

wen:Perfect hash function
  • Hašování takové, kde nejsou kolize.
  • Operace insert je buď zakazaná, nebo se řeší bufferem občasně zahašovávaným do hlavní tabulky.

Chceme pro danou množinu $ S \subset U $ nalézt funkci h: U -> {0, 1, ..m-1} takovou, že

  • 1) h je perfektní vůči S
  • 2) h(x) je rychle spočitatelná
  • 3) m je srovnatelné s n
  • 4) h nevyžaduje příliš paměti

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

předpoklad: S pevně daná
$ b_k^i $ je počet $ x \in S;\ h_k(x) = i $

Význam $ b_k^i $: Tyto hodnoty ukazují odchylku od perfektnosti.

pokud $ b_k^i \geq 2 $, potom $ (b_k^i)^2 - b_k^i \geq 2 $

naopak $ b_k^i \leq 1 $, implikuje $ (b_k^i)^2 - b_k^i = 0 $

Věta: Funkce $ h_k $ je perfektní, právě když

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

Existuje k takové, ze:

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

.. zkouším jednotlivé funkce tak dlouho, než najdu parametr k, pro který je suma druhých mocnin délek řetězců menší, než ten výraz. (to plyne nějak z vlastností univerzálního hešování!)

Důsledky:

  • 1) pokud m = n (my volíme m), pak:
$ \exists k;\ \sum_{i=0}^{m-1} (b_k^i)^2 < 3n $ a k nalezneme v $ O(nN) $
  • 2) pokud $ m = 1+n(n-1) $, pak $ \exists k; h_k $ je perfektní (suma vyjde < n+2 a pokud by nebyla perfektní, tak je tam alespoň jeden řetězec délky alespoň dva, jeho mocnina je 4 a $ 4 + (n-1) $ jednoprvkových řetězců dává délku > $ n+2 $; spor). Tohle ale nevyhovuje požadavku 3).
  • 3) Konstrukce do prostoru < 3n. Vezmeme funkci z důsledku 1) a rozdělíme S do m množin podle $ h_k(s)=i $ (množiny kolidujících prvků pro každé i). Pro tyto množiny nalezneme perfektní funkci podle důsledku dva. Tahle kombinace dvou funkcí pak tvoří výslednou perfektní funkci. Do <3n se to vleze, protože pro ty malé funkce mám k dispozici druhou mocninu prostoru (vzhledem k počtu prvků) a:
$ \sum_{i=0}^{m-1} (b_k^i)^2 < 3n $

(...kolizní řetězce se rozprostřou tak, že se najde perfektní hašovací funkce pro každý z nich, a díky tomu, že těch řetězců je málo, se to celé vedje do 3n :-)

Stále to ještě nesplňuje podmínku 4). Další úprava se dělá pomocí magie.

Vysvětlení[editovat | editovat zdroj]

Myslím, že to co je výše jsou takové snippety z důkazu, ale vůbec v tom neni vidět jak to má fungovat. Idea je, že máme primární hashovací funkci $ h_k(x) = (k*x\ mod\ N)\ mod\ m $, která není perfektní, a pak zkonstruujeme sadu sekundárních, už perfektních. Nakonec je složíme, že dostaneme perfektní funkci. Ve skriptech Koubka je tohle zahrabané až na úplném konci a vůbec to neni zdůrazněné, že vlastně kvůli tomuhle sme všechno dokazovali. Pokud si nejste jistí tak doporučuju přečíst originální článek od Cormacka [1].

Def. $ b_k^i=\{x\in S|h_k(x)=i\} $

Takže jako shrnutí co umíme (viz. výše):

  • umíme najít docela dobrou hashovací funkci rychle O(n), nebo trochu lepší ale zas to stojí víc času O(nN)
  • umíme najít perfektní hashovací funkci do tabulky $ m=n(n-1)+1 $ v čase O(nN) (projdeme všechny možnosti a počítáme $ \sum (b_k^i)^2 $)
  • umíme najít perfektní hashovací funkci do tabulky $ m=2n(n-1) $ v čase O(n) (náhodně procházíme možnosti)

Samozřejmě bychom mohli pustit rovnou hledání perfektní hash funkce v O(nN), ale tahle funkce by zabrala hodně paměti, takže to uděláme lépe. Takže konstrukce probíhá tak, že najdeme tu neperfektní, ale docela dobrou $ h_k $. O ní platí, že $ \sum_{i=0}^{m-1} (b_k^i)^2 < 3n $. Tuhle hashovací funkci pak použijeme k tomu, že rozhashujeme množinu S do disjunktních množin $ S_i=\{s\in S|h_k(s)=i\} $. A teď pro každou z nich najdeme perfektní hashovací funkci $ h_{k_i} $, do tabulky velké $ c_i:=m=n(n-1)+1 $.

Teď už máme všechno, co potřebujeme. Vytvoříme si primární soubor a uděláme si v něm značky, kam budeme ukládat $ S_i $. Řádek v primárním souboru kde začíná $ S_i $ bude $ d_i:=\sum_{j=0}^{i-1} c_i $. Perfektní hashovací funkce pak bude: $ h_k(x)=l; g(x)=d_l+h_{k_l}(x) $. Když sečteme jak dlouho nám vše trvalo dostaneme O(nN) za první hash funkci, pak zahashujem S do $ S_i $ v O(n) abychom spočítali kolik potřebujeme naalokovat na perfektní funkce. Perfektních funkcí bude m a každou budeme hledat v čase $ O(|S_i|N) $, což po sečtení vyjde O(nN). Takže teď jen potřebujeme ukázat, že jsme skutečně spotřebovali méně jak $ O(n^2) $ paměti. Pamět můžeme omezit pomocí $ d_m:=\sum_{j=0}^{m-1} c_i\leq \sum_{j=0}^{m-1} (b_k^i)^2<3n $, protože $ |S_i|(|S_i|-1)+1\leq |S_i|^2=(b_i^k)^2 $.

Tohle ještě není úplně stoprocentně perfektní hashovací funkce, ale už jsme dost blízko. Jeden z požadavků na perfektní funkci je, aby ji bylo jednoduché uložit (nejlépe analyticky), což zkonstruovaná funkce g(x) úplně není, což je asi dobré zmínit, i když se tohle hashování už označuje za perfektní. Alternativní metodu, která nám dá trochu hezčí analytickou hashovací funkci, popsali Fredman [2].

Možnosti dynamizace jednotlivých datových struktur (pouze I1,I4)[editovat | editovat zdroj]

Máme obecnou statickou strukturu (neumožňující INSERT a DELETE) a zkoumáme jak do ní toto přidat. Chceme, aby se f(x,A) (vyhledání a tak) v nové struktuře počítalo přibližně stejně rychle jako v té původní. Dále, když vytvoření původní struktury pro n-prvkovou množinu trvalo t, pak operace INSERT by měla vyžadovat čas t/n.

vyhledávací problém
je funkce $ f : U_1 \times 2^{U_2} \to U_3 $, kde $ U_1 $, $ U_2 $ a $ U_3 $ jsou univerza.
řešení vyhledávacího problému
pro $ x \in U_1, A \subseteq U_2 $ je nalezení hodnoty f(x,A).

Klasický vyhledávací problém má $ U_1 = U_2 = U $ (univerzum prvků), $ U_3 = \{0,1\} $, $ A \subseteq U_2 $. f(x,A) pak vrací 0/1 podle toho, je-li $ x \in A $.

rozložitelnost problému
Vyhledávací problém je rozložitelný, když existuje operace $ \oplus $ spočitatelná v konstantním čase, a platí: když $ x \in U_1 $ a A a B jsou disjunktní podmnožiny $ U_2 $, pak $ f(x, A \cup B) = f(x,A) \oplus f(x,B) $
  • Pozn.: Vyhledávací problém není chápán jen jako dotaz MEMBER(x)! Ale jako hledání řešení nějaké obecné úlohy, kterou lze řešit pouze (nebo dostatečně efektivně) nad statickou strukturou, resp. pro rozložitelný problém i nad její parcelací.

Semidynamizace[editovat | editovat zdroj]

Máme rozložitelný vyhledávací problém f a pro něj statickou strukturu, která ho řeší v čase Q(n), vyžaduje S(n) paměti a vytvoří se v čase P(n), kde Q(n), P(n)/n a S(n)/n jsou neklesající funkce. Pak existuje semidynamická datová struktura D, řešící f v čase O(Q(n) log n), vyžadující O(S(n)) paměti a umožňující INSERT s amortizovanou složitostí O(P(n)/n * log n).

Postup:

  • A si rozdělíme na sadu disjunktních množin $ A_i $, pro které platí buď $ A_i = \emptyset $ nebo $ |A_i| = 2^i $.
  • Nová pomocná struktura T reprezentující A, kterou použijeme pro test $ x \in A $ před libovolnou operací (může to být třeba AVL strom, pro rychlé operace MEMBER a INSERT). Tady je důležité si uvědomit, že vyhledávací problém nemusí být MEMBER, pro INSERT ale potřebujeme pustit nejdřív MEMBER a proto máme tuhle pomocnou strukturu.
  • Pro každé $ A_i \neq \emptyset $ máme S statickou strukturu. Zároveň si pro každou $ A_i $ pamatuji spojový seznam jejích prvků, protože při vkládání nového vyrábím novou statickou strukturu z menších $ A_i $, a dostávat seznamy prvků ze statických struktur by mohlo trvat.

Vyčíslení f(x,A): f(x,A) se počítá pro každou množinu $ A_i $ zvlášt a pak se výsledky v konstantním čase spojí pomocí operace $ \oplus $.

INSERT: Zkontrolujeme pomocí pomocné struktury MEMBER(x,T), dál postupujeme jen pokud prvek ve struktuře není. Vložíme prvek x do pomocné struktury (INSERT(x,T)). Najdeme nejmenší i, pro které $ A_i=\emptyset $ do téhle zkolapsujeme všechny $ A_j, j<i $. Spojíme jejich spojové seznamy, přidáme x a vytvoříme novou statickou strukturu S která bude reprezentovat $ A_i $. Zároveň zapomeneme použité $ A_j $.

Pak existuje ještě varianta optimalizující INSERT v nejhorším případě. V něm se budují množiny velikosti $ 2^i $ postupně. Po vložení prvních dvou prvků x,y učiním polovinu kroků stavby {x,y} atd.

Dynamizace[editovat | editovat zdroj]

Ještě přidáme falešný DELETE (škrtnutí prvku v čase O(n)).

  • Pozn.: Falešný DELETE je nový požadavek! Statická struktura ho musí podporovat.

A rozložíme na disjunktní množiny $ A_j, j = 0, 1, ..., \log {|A|+3} $ takové, že buď $ A_j = \emptyset $ nebo $ 2^{j-3} < |A_j| \leq 2^j $. Každá množina $ A_j $ je reprezentována strukturou, která před škrtáním měla velikost $ \leq 2^j $. Pak máme pro každou neprázdnou $ A_j $ spojový seznam prvků v ní, provázaný se strukturou reprezentující $ A_j $. Amortizovaně INSERT v O(log(n)*P(n)/n), DELETE v O(D_s(n) + log n + P(n)/n)), pokud P(n) je $ n^{\epsilon} $, tak to vychází O(P(n)/n). DELETE naplní A_j jen do půlky, takže to sice stačí, ale nekazí to složitost INSERTu získanou v semidynamické kapitole.

  • INSERT
$ |\bigcup_{i=0}^{j}A_i|<2^j $
$ A_j $=build($ \bigcup_{i=0}^{j}A_i|\cup\{x\} $)
destroy(0,j-1,$ A_i $)
Když insertbuduje $ A_j $, platí potom $ 2^{j-1}<=|A_j|<=2^{j} $
  • DELETE
$ |A_j|=1 $destroj($ A_j $)
$ |A_j|>2^{j-3}+1 $fake_delete(x)
$ |A_j|=2^{j-3}+1 $
|$ A_{j-1}|=0 $$ A_{j-1} $=build($ A_j\smallsetminus\{x\} $), destroy($ A_j $)
$ |A_{j-1}|>=2^{j-2} $swap($ A_{j-1} $, $ A_j $), $ A_{j-1} $=build($ A_{j-1}\smallsetminus\{x\} $) //po swapu
$ |A_{j-1}|<2^{j-2} $
if $ |A_j|-1+| A_{j-1}|>2^{j-2} $ then
$ A_j $=build($ (A_j\smallsetminus\{x\})\cup A_{j-1} $), destroy($ A_{j-1} $)
else
$ A_{j-1} $=build($ (A_j\smallsetminus\{x\})\cup A_{j-1} $), destroy($ A_j $)
Když delete buduje strukturu $ A_j $, platí potom $ 2^{j-2}<=|A_j|<=2^{j-1} $

A je opět reprezentována nějakou dynamickou strukturou T, která umožňuje operace MEMBER, INSERT a DELETE v $ O(\log n) $.

Mapování datových struktur do stránek vnější paměti počítače & Časová složitost algoritmů vyjádřená v počtu I/O operací (pouze I1,I4)[editovat | editovat zdroj]

Schéma organizace souborů (SOS)[editovat | editovat zdroj]

  • fyzické soubory
    • délka fyzického záznamu R, délka stránky B, blokovací faktor B/R=b
    • blokované, neblokované, přerostlé záznamy
  • logické soubory
    • logické stránky (bloky) konstantní délky
    • primární soubor (velikosti N)
  • dotazy nad soubory
    • dotaz na úplnou shodu, na částečnou shodu, dotaz na úplnou intervalovou shodu, dotaz na částečnou intervalovou shodu
    • vyváženost struktury (rozlišují se podle ní statické a dynamické SOS
      1. omezení délky cesty v datové struktuře
      2. naplněnost logických stránek (faktor naplnění stránky λ), štěpení stránky, slévání stránky
  • fyzické nosiče souborů
magentická páska
sekvenční čtení, využívá se buffer (velikosti jedné stránky), páska obsahuje meziblokové mezery
magnetický disk
stopy, cylindry, bloky, parametry: s - seek, r - rotation (rovno polovině) doby otáčky, btt - block transfer time,

Statické metody organizace souborů[editovat | editovat zdroj]

Počty I/O operací - základní přehled[editovat | editovat zdroj]

Rozhoduje kolik se přečte stránek z disku, kolik se jich zapíše a jak dlouho to trvá

Fetch
čas pro načtení jedné stránky $ T_F = s+r+btt $, pro další stránky na stejném cylindru se nemusí hlavičky přesouvat ($ T_F = r+btt $)
Rewrite
přepsání stránky na disku (tj. přenos stránky do vnější paměti, změnu ve vnější paměti a přenos zpět na disk), lze vyřešit v době, než se plotna disku jednou otočí, tedy $ T_RW = 2r - btt + btt = 2r $
Insert
vložení zánamu (je nejprve zapotřebí načíst stránku, do které se bude zapisovat, do paměti) $ T_I $
Delete
smazání stráky (obvykle prohlášení za neplatnou) $ T_D $
Update
změna záznamu ve stránce $ T_U $
Reorganizace
$ T_Y $

Pro jednotlivé typy organizace souborů bude úvaha nad jejich počty IO operací uvedena u jejich popisu.

Sekvenční soubor[editovat | editovat zdroj]

  • neuspořádaný - oproti hromadě záznamy pevné délky
  • uspořádaný - podle jednoho klíče

Odhady pro uspořádaný sekvenční soubor:

  • $ T_F = log_{2} (N/\lfloor b \rfloor)(s+r+btt) $ - nalezení záznamu metodou půlení intervalů
  • $ T_I = s+r+btt + T_RW + T_Y/o $ - načte se stránka kam se bude vkládat, přepíše se a připočte se poměrný čas potřebný pro reorganizaci souboru (až k ní dojde).
  • update
Tato část je neúplná a potřebuje rozšířit. Dopsat, doporučuju skripta Pokorný-Žemlička - Základy implementace souborů a databází

(prosim doplnujte co si myslite ze sem patri nebo primo vite ze se zkouselo, nejlepe i s info kde to najit)

  • schema organizace souboru (hromada, sekv, index-sekv.) - zkouselo se (Zemlicka), skripta Zaklady implementace souboru a databazi (stare vydani str. 15-30) (viz též ČVUT wiki
  • ja myslim ze sem patri aj Externe hashovanie (skripta na DS) - je to asi totez co Fagin z OZD, ale sloziteji popsany :)
  • staticke hasovani - Cormack, Larson+Kalja (Pok97 31-35)
  • dynamicke hasovani - Fagin, Litwin, skupinova stepeni stranek (Pok97 41-47)
  • Externy mergesort? Je to sice uz v triedeni vo vonkajsej pamati, ale ked je tu aj ext. hashovanie...
  • Majerech akceptoval rozpravanie o externom MergeSorte, B+ stromoch.

Dolní odhady pro uspořádání (rozhodovací stromy)[editovat | editovat zdroj]

podle http://ksvi.mff.cuni.cz/~topfer/ppt/Progr-11.pdf

Třídíme-li s pomocí porovnávání, můžeme si výpočet znázornit binárním stromem. Začínáme v kořeni, v uzlech porovnáváme a větvíme, v listech máme setříděno. Pro každá vstupní data se výpočet někde odliší od ostatních, strom má $ n! $ listů (tolik je možných uspořádání množiny s $ n $ prvky.) Výška stromu je počet provedených porovnání při nejdelším výpočtu (v nejhorším případě) je alespoň $ \log_2(n!) $. (Úplný binární strom s $ k $ listy má výšku $ \log_2 k $, neúplný je vyšší.) Časová složitost třídícího algoritmu založeného na porovnávání proto nemůže být lepší než $ O(\log_2(n!)) = O(n\ \log n) $.

Podle Stirlingovy formule:

$ n! \approx \sqrt{2\pi n}\, \left(\frac{n}{e}\right)^{n} $ (to je ona)
$ O(\log_2 n!) = O(\log_2{\sqrt{2\pi n}\, \left(\frac{n}{e}\right)^{n}}) = O(n \log n) $ (Logaritmus odmocniny bude asymptoticky $ O(\log n) $, $ (n/e)^n $ bude $ O(n \log n) $, a požere to.)
  • Pro mne snazší odhad: nn ≥ n! ≥ nn/2
  • k-tý prvek nelze s porovnanim ziskat driv nez v O(n): musim mit alespon retizek s n-1 hranami.
  • konvexni obal nelze lepe nez O(n*log(n)): pro [x,x2] umim tridit


Třídění ve vnitřní a vnější paměti[editovat | editovat zdroj]

Vnejsi pamet[editovat | editovat zdroj]

  • wen:External sorting
  • Celkem pěkně popsané ve skriptech Pokorný, Žemlička k OZD (jsou dostupné na Studnici)

Merge sort jak je popsan v pokornem: Hlavni rozdil je nacitani po blocich (obsahuje typicky vice zaznamu najednou) a pomalost disku, takze optimalizace na co nejmensi pocet nacteni.

1. nactu a setridim skupiny bloku, ktere se mi vlezou do operacni pameti (OP)

2. nactu z m setrizenych skupinbloku 1. blok do OP, tridim do bloku m+1. Kdyz je m+1 plny, tak ho zapisu a uvolnim, kdyz se nejaky vstupni blok vyprazdni, tak nactu dalsi blok te skupiny (pokud existuje).

Tak ziskam setrizenou skupinu bloku m nasobne velikosti. a opakuju. Pokud se mi do pameti vejde vice nez odmocnina z celkoveho poctu bloku, tak lze provest na dva pruchody (obecne M - pocet bloku, co se vejdou do OP, N pocet vsech bloku zabranych mnozinou, tak to setridim na log_M N pruchodu)

  • Behy pro trideni (resp. externi trideni) lze delat pomoci 2 hald. Udelam jednu pres celou pamet. Trham minimum a novy nacitany prvek: pokud je vetsi nez odeslane min tak zatridim do haldy, jinak ulozim do pameti na volne misto (stavim 2. haldu)

Vnitrni pamet[editovat | editovat zdroj]

Porovnavaci[editovat | editovat zdroj]

buble sort - prochazim seznamem a kdyz najdu dva sousedni prvky, ktere jsou v opacnem poradi nez maji byt, tak je prehodim. Pruchody zacinam do doby, nez jsem pri pruchodu nic nezmenil - je setrizeno. O(n2), nejhorsi

insert sort - pri nacteni noveho prvku jej zatridi do mnoziny jiz setrizenych porovnavanim se sousedem. Worst: O(n2), Avg O(n2), O (n+ počet transpozic), ale lepsi konstanta nez bubblesort

A-sort - ma podobonou vlastnost jako insert sort: pri malem poctu transpozic je rychly. I jeho myslenka je podobna. Pouze pri zatrizovani ma misto jednoducheho pole setrizenych prvku nejaky stromecek (napr. 2,3-strom nebo AVL strom), do ktereho nove prvky vklada. Takto je mozne opravit k transpozic na pouhych log(k) kroku.

selection sort - najde nejmensi prvek, vynda ho a da na vystup (v in-place verzi vymeni s prvnim v posl.), opakuje se zbytkem - O(n2) nejhorsi i ocekavany

shell sort - zdokonaleny insert sort. Pri zatrizovani neporovnavam se sousedem, ale s nekym o vice indexu vzdalenym - treba 5. Pote, co skoncim, tak opakuju se skakanim o 3 a naposledy skacu o 1 (=insert sort). Pri dobre k - vzdalenosti dvou porovnavanych prvku, lze slozitost stlacit (v soucasnosti, zlepseni je otevreny problem) az na O(n log^2(n))

merge sort - rozdelim posloupnost na pulky rekurzivne az na jednotlive prvky. Pak skladam vzdy dve setrizene casti (pocinaje dvema samostatnymi prvky a konce polovinami posloupnosti) - O(n logn) best, worst i avg; jina verze - "prirozeny merge" nejdriv projde posl. O(n) a najde rostouci behy, nahaze je do fronty; pak dokud ve fronte vic jak 1 posl. zmerguje prvni dve a vysledek hodi na konec fronty - tato verze je optimalni vzhledem k poctu porovnani, adaptuje se na predtridene posloupnosti; pokud je pocet behu konstatni tak bezi v O(n)

quicksort(+vyber dobreho pivota) - zvolim pivota a prvky mensi nez on dam do jedne casti, prvky vetsi nez on do druhe. Rekurzivne az po trivialni ulohy a pak zpetne skladam jiz setrizenou posloupnost. Avg O(n logn), Worst O(n2), O (n log n , i kdybych pivota vybral vzdycky tak blbe, ze 1% bude mensi a 99% vetsi nez on).

heap sort - postavim d-regularni haldu (jde O(n)), n krat extractmin - O(n logn) celkem; da se delat in-place (primo v poli s tridenymi prvky) - ulozeni haldy v poli jasne; pouzijeme dualni podminku (otec > syn) a DELETEMAX misto DELETEMIN - DELETEMAX vymeni koren s poslednim v halde (a DOWN na koren) + zmensi haldu o 1 - tim MAX vypadne, vpravo od haldy se vytvari setridena posloupnost

Neporovnavaci[editovat | editovat zdroj]

bogo sort - srovnej vstupni posloupnost nahodne a zkus, jestli je setrizena :))

radix sort - rozdelim do kastliku 0-9 (a-z, ..., podle abecedy v klicich) podle nejmene duleziteho znaku. Znovu postavim celou posloupnost serazenim kastliku za sebe dle jejich (znameho) poradi. Udelam to same pro 2. nejmene dulezity znak a dokola az po nejdulezitejsi.

hybrid sort - trideni n realnych cisel v rozsahu (0-1] - k=alfa*n prihradek, prvek a_i zatridim do prihradky ceil(k*a_i) , kolize sortuju heap sortem (misto "separovanych retezcu" ma kazda prihradka svuj heap) -> slozitost nejhur O(nlogn), za predpokladu nezavisleho rovnomerneho rozlozeni vstupu O(n)

bucket sort, counting sort ..

Stabilni trizeni - pokud zachova poradi prvku se stejnym klicem takove, jake bylo na vstupu

Dlhsi seznam viz wikipedia

Samoupravující datové struktury (pouze I1,I4)[editovat | editovat zdroj]

Wiki(en) - samoorganizujici seznamy
Wiki(en) - Splay stromy(samoorganizujici stromy)
Splay stromy(samoorganizujici stromy) - Cheruku Ravi Teja
Pointers to splay tree visualizations

Samoupravující seznamy[editovat | editovat zdroj]

Zdroj: http://ktiml.mff.cuni.cz/teaching/files/materials/KoubekVaclav_BINVYHST.pdf str. 36 podkapitola 6


Předpoklady:

  • Prvky jsou uložené ve spojovém seznamu.
  • Vyhledává se lineárním průchodem.

Při vyhledávání se prvky přemísťují k začátku seznamu tak, aby se nejčastěji vyhledávané prvky byly na začátku. Nejlepší čas na vyhledání prvku se pak blíží konstatnímu. V nejhorším případě(hledaný prvek je na konci) ovšem stále $ O(n) $ jako u klasického spojáku.

Metody organizace(podrobněji viz wiki):

  1. Move To Front(MTF) - vyhledaný prvek se prostě přepojí na začátek. Reaguje velmi rychle na změny ve vyhledávacích vzorů. Až moc rychle - občasné vyhledání jinak nepoužívaného prvku rozbije optimální strukturu seznamu.
  2. Počítací metoda - každý uzel má počítadlo na počet vyhledávání. Uzly se udržují setřízené podle počtu vyhledání.Potřebuje navíc pamět pro počítadla. Reaguje pomaleji na změnu vyhledávacích vzorů, ale někdy zase až moc pomalu(viz příklad na wiki).
  3. Transpoziční metoda - přehazuje prvek s předchůdcem, pokud existuje. Opět se přizpůsobuje vyhledávacím vzorům pomaleji než MTF.

Aplikace: V překladačích a interpretech se používají k uložení tabulky symbolů během kompilace/interpretace zdrojáku.

Splay stromy[editovat | editovat zdroj]

Binární vyhledávací stromy. Při vyhledání prvku X se strom přeorganizuje tak, aby X byl v kořeni stromu.

Algoritmus operace splay pro uzel N [2]:

while N není kořen do
 1.Pokud rodič N(dále R) není kořen, proveď rotaci tak, aby N byl kořen a R jeho potomek.
 2.Pokud N a R mají stejnou orientaci(oba jsou levé nebo pravé děti). Rotuj R a potom N.
 3.Pokud N a R mají různou orientaci, rotuj dvakrát N. 
wend

Insert N:

1.Vlož N stejně jako v binárním stromě
2.Splay(N)

Delete N:

1.Stejně jako v binárním stromě
2.Splay(rodič N).

Amortizovaný odhad ceny splay operace[editovat | editovat zdroj]

[3]

Výhody:

  • Jednoduchá implementace.
  • V průměrném případě stejně efektivní jako ostatní stromy.
  • Nepotřebují paměť navíc.

Nevýhody:

  • Může zdegenerovat na obyčený seznam, tj. hloubka stromu je lineární. Operace mají "dobrou" složitost amortizovanou.
  • Problematické použití ve vícevláknovém prostředí. Vyhledání prvku(typická read-only operace) mění strom.

Relaxované vyhledávací stromy[editovat | editovat zdroj]

Skripta Koubek str 16. podkapitola 3, Článek "Relaxed Balanced Red-Black Trees"

Co se stane se stromy, kde po přidání/odebrání nevyvažujeme. Rychlejší operace, více uživatelů zároveň, vyvažování necháme na později. Tyto stromy nazýváme relaxované.

  • Možná degenerace stromu - delší vyhledávání
  • Lze jednoduše nevyvážený strom vyvážit bez přebudování celé struktury?

Požadavek

  • v - vrchol černý a v podstromu vrcholu chybí jeden černý uzel
  • b - vrchol i jeho otec červené, exkluzivní, s vrcholem nesmí být svázán žádný jiný požadavek

Příklad na RB stromech, lze analogicky pro ostatní. Máme frontu vyvažovacích požadavků, pokud prázdná, strom je vyvážený. Nad daty pracuje několik procesů najednou:

  • uživatelský - provádí vyhledávání, přidávání a odebírání. Pokud po aktualizaci vznikne požadavek na vyvážení, přidá ho do fronty
  • správcovký - bere vhodné požadavky z fronty a provádí je. Požadavky mohou být buď zcela ošetřeny nebo transformovány v jiný požadavek blíže kořeni.

Vícerozměrné datové struktury (asi zrušeno)[editovat | editovat zdroj]

Dotazy na částečnou shodu a jejich optimalizace[editovat | editovat zdroj]

see http://ksi.mff.cuni.cz/~pokorny/vyuka/pokorny/
  • v hasovacich schematech - Pokorny 35-40 (stare vydani) - optimalizace prumerneho poctu I/O operaci pro specialni variantu dotazu na 1 atribut ze znamych pravdepodobnosti atributu; deskriptory stranek a 2urovnove vrstvene kodovani; Grayovy kody
  • ve vicerozmernych B-stromech - Pok. 71-73
  • vicerozmerna mrizka - Pok. 73-75

Signaturové metody[editovat | editovat zdroj]

Rozdělím si text na logické bloky, ty nějak zakóduju do signatur (řetězce bitů). Dotaz (konjunkci termů) pak taky zakóduju si signatury, a porovnáním se signaturami jednotlivých bloků vyloučím část dokumentů, které dotazu určitě nevyhovují.

  • máme funkci h, která zobrazuje termy na bitové řetězce; OR binárních reprezentací termů je signatura dokumentu
  • signatura bloku SD vyhovuje signatuře dotazu SQ, pokud SQ & SD == SQ (nebo taky SQ & ~SD == 0)

http://kocour.ms.mff.cuni.cz/~pokorny/vyuka/pokorny6/

http://www.ms.mff.cuni.cz/~kopecky/vyuka/dis/07/dis07_v1.html


Další materiály[editovat | editovat zdroj]

  • Základ přebrán z Majklových státnicových výcucků
  • Skripta Vidner-Kotal – neoficiální skripta
  • Václav Koubek, Alena Koubková: Datové struktury I, II (ktiml) – dost obsáhlé
  • Melhorn K., Data Structures and Algorithms: [4]
  • Mareš M. a kol. Algoritmy a Datové struktury I a II: [5]
  • Pokorny. Slajdy k prednasce Organizace a zpracovani dat: [6]
  • Vizualizace datových struktur: [7]
  • Cormack, Gordon V., R. N. S. Horspool, and Matthias Kaiserswerth. "Practical perfect hashing." The Computer Journal 28.1 (1985): 54-58.
  • Fredman, Michael L., János Komlós, and Endre Szemerédi. "Storing a sparse table with 0 (1) worst case access time." Journal of the ACM (JACM) 31.3 (1984): 538-544