''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]].''
== 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í.)
== Stromové vyhledávací struktury ==
=== Binární stromy a jejich vyvažování ===
* [[wen:Binary search tree]]
* [[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.
=== Haldy ===
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 ≤ ''k'' ≤ ''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 ===
* 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 ===
* (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 <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 – 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 <math>a=\lceil{}b/2\rceil</math>
* (B+)-stromy – B stromy s listy propojenymi obousmernym spojakem, umoznuje intervalove dotazy v DB, dalsi pouziti ve FS
* (B*)-stromy – 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.
* (Ne)redundantnost:
** Redundantni – klice ve smerovacich zaznamech i v listech
** Neredundantni – klic bud v smerovacim zaznamu, nebo v listu
== Hašování ==
* [[wen:Hash table]]
=== Řešení kolizí ===
==== 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 + α/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 ====
* 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 ====
* 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 + α/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í ====
* 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í ====
* 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 ====
* 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í ===
:[[wen:Universal hashing]]
* Zdroje
** [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 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 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 <math>\forall x \neq y \in U;\ | \{ h \in H: h(x) = h(y) \}| \leq\ \cfrac{c |H|}{m}</math>
'''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. všechny lineární funkce.
'''Tvrzení:''' takto zkonstruované H je c-univerzální systém pro<br />
<center><math>c=\left(\left\lceil\cfrac{N}{m}\right\rceil\Big /\cfrac{N}{m}\right)^2</math></center>
.. 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 <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 />
.. 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 <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 pravděpodobnost, že je řetězec <math>\geq \mu t</math> menší než <math>\cfrac{1}{t}</math></center>
'''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>|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>
=== Perfektní hašování ===
:[[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 <math>S \subset U</math> 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:<br />
<math>h_k(x) = (k*x\ mod\ N)\ mod\ m</math><br />
N = |U|<br />
předpoklad:
S pevně daná<br />
<math>b_k^i</math> je počet <math>x \in S;\ h_k(x) = i</math><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>
.. 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.
== Možnosti dynamizace jednotlivých datových struktur ==
*[[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 - hned na zacatku ]
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 <math>f : U_1 \times 2^{U_2} \to U_3</math>, kde <math>U_1</math>, <math>U_2</math> a <math>U_3</math> jsou univerza.
;řešení vyhledávacího problému
:pro <math>x \in U_1, A \subseteq U_2</math> je nalezení hodnoty f(x,A).
Klasický vyhledávací problém má <math>U_1 = U_2 = U</math> (univerzum prvků), <math>U_3 = \{0,1\}</math>, <math>A \subseteq U_2</math>. f(x,A) pak vrací 0/1 podle toho, je-li <math>x \in A</math>.
;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>
*'''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 ===
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 rychlé operace MEMBER), pro každé <math>A_i \neq \emptyset</math> máme S strukturu propojenou s odpovídajícím prvkem ve stromě.
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.
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>.
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 ===
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>.
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>
{{TODO|co přesně bude jako pak reprezentovat A? sada spojových seznamů?}}
== 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í ==
=== 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 λ), š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.
Dlouhodobe9 půjčky, americke9 hypote9ky a psaeikdtnloke9 favěry se ze1stavou nemovitosti v cele9 ČR. Nabedzedme konsolidace, oddlužened a refinance s nebankovnedch sektoru. Vyple1cedme nevfdhodne9 ze1stavy, dražby, exekuce a vyčistedme LV s veškerfdm pre1vnedm servisem. Finance jsou u ne1s poskytove1ny od 1 30 let a kdykoliv můžete půjčku předčasně splatit. Bez zkoume1ned předjmů a registrů. Bez poplatků předem! Milan Karička608192902
==== 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í}}
(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]
* 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)
* [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.
== Vícerozměrné datové struktury ==
=== 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
== Třídění ve vnitřní a vnější paměti ==
=== 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:
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 ===
==== Porovnavaci ====
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 ====
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 [http://en.wikipedia.org/wiki/Sorting_algorithm#List_of_sorting_algorithms wikipedia]
== Relaxované vyhledávací stromy ==
[http://ktiml.mff.cuni.cz/teaching/files/materials/binvyhst.pdf Skripta Koubek]
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.
== 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]] – neoficiální skripta
* Václav Koubek, Alena Koubková: <em>Datové struktury I, II</em> ([http://ktiml.mff.cuni.cz/index.php?select=teaching§ion=sources&lang=czech ktiml]) – 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/]
[[Category: Státnice Informatika Mgr.]]
