Státnice - Hašování I2

Z ωικι.matfyz.cz
Přejít na: navigace, hledání

Založeno na Hašování I3, z různých zápisků k předmětu Datové struktury I, OZD I a výtahů k bakalářským státnicím

09/10: Hašování: rešení kolizí, univerzální hašování, perfektní hašování. Mapování datových struktur do stránek vnejší pameti pocítace.

14/15: Hašování: rešení kolizí, univerzální hašování, perfektní hašování.

Hašování - Operace: SEARCH, INSERT, DELETE
Univerzum klíčů U a K⊆ U je množina použitých klíčů |K| = n
Hašovací fce h: U→{0,1,..,m−1} mapuje univerzum U do(menší) tabulky T [0,..,m−1], |U| > m (pracuje v O(1))
Kolize je situace: h(ki) = h(kj), pro ki≠kj; ki,kj∈K
Faktor naplnění: α = n/m

Hašování: řešení kolizí (interní hashování) (7×🎓)[editovat | editovat zdroj]

Zážitky ze zkoušek  
  • Hašování (2013, Kolman) - Mal som rozprávať o hašování všeobecne, čo to je, prečo to riešime a pridať čo prináša univ. a perfektné hašovanie. Vydal som zo seba nejaký všeobecný úvod, spomenul som štandardné spôsoby riešenia kolízii a čím sa od seba odlišujú (bez presného popisu algoritmov), spomenul som univerzálne hašovanie a perfektné hašovanie. Spolu so zopár otázkami na univerzálne hašovanie (c-univerzálny systém) to bohato stačilo.
  • Hašování (2013, Majerech) - Vyjmenoval jsem předpoklady, základní typy hašování, očekávaná délka řetězce separovaných řetězců (kromě definice univerzálního hašování jediný vzoreček, který se po mně chtěl), základy univerzálního hašování, na perfektní už se nedostalo. Zkoušející byl Majerech - hodně šťoural, ale zajímaly ho praktické aspekty použití spíš než vzorečky (i když kolegu přede mnou dusili na definici nějakých vyhledávacích stromů).
  • Hashování, řešení kolizí, srovnání metod (2012, DB)
  • Reseni kolizi v hashovani a univerzalni hashovani (2012, Majerech) - Na uvod klasicky vycet ruznych reseni kolizi ("ten sklep v tom, jak ho popisujete, vam k nicemu nebude, podle me"), pak dlouhe paceni toho, ze se pri velkem load factoru da tabulka zvetsit (vubec me nenapadlo, ze je potreba to rict, ale M. byl chapavy a pockal si, az jsem se chytil za nos), pak povidani o rozdilu mezi randomizovanou slozitosti a ocekavanou slozitosti ("co kdyz budete mit robota nad pacientem, co z nej strika krev, bude vam tohle hashovani stacit?"), diskuse o doplneni RB stromu do jednotlivych bucketu a tak. Slabsi povahy by si mohly myslet, ze je to na vyhazov, ale to vubec neni pravda, M. je velmi inteligentni a korektni a i zkouseni je u nej prilezitost k vysvetleni zajimavosti. Bylo fajn, ze se neptal na algebraicke principy fungovani c-univerzalnich systemu, ale spis mu slo o porozumeni, jak to funguje a v cem je to dobre/spatne.
  • hashovanie a trie (2011, Dr. Zeman) - Nastastie taka prehladova otazka, kedze som ju odpovedal ako poslednu, tvoril som to pocas odpovedania, rozpisal som druhy hashovania, potom zmienil univerzalne (principy ~ ku kazdej S vyberieme nejaku fciu z H, H c-univerzalna, napisal som funkciu h_ab(x), a ze je c-univerzalna), perfektne hashovanie, opat som zacal ako to principialne funguje a v polovici som bol zastaveny a ze mam este o triach porozpravat, tak som opat vysvetlil princip, dalej ako sa to potom komprimuje (v style, potom vznechame tie uzly, kde nedochadza k plodnemu vetveniu, potom to mozeme zapisat do tabulky, tu do dvoch poli, etc), spokojnost
  • reseni kolizi v hashovani (2011, Koubek) - napsat vsechny algoritmy a porovnat je z hlediska pametove a casove narocnosti, prumerna delka retezcu, jak to ovlivni cachovani
  • přehled hašování (řešení kolizí) (2009)
  • Hashovani (2005,Kopecky) - Nahodil jsem ruzny strategie reseni kolizi (jen jak to funguje, zadny casy ani vypocty, ani to pak nechtel) + zvetsovani tabulky (takovyto prehashovani) - pak po me chtel jeste dynamizaci


v datovkách se bralo (a u státnic ze zkouší) hlavně In-memory hashování:

  • celá tabulka je v paměti
  • každý poličko obsahuje jeden záznam
  • limitovaný prostor

Řetězení (Chaining)[editovat | editovat zdroj]

Hašování separovanými řetězci (chaining) při kolizi vytvoříme v tabulce spojový seznam

Separované řetězce (separate chaining)[editovat | editovat zdroj]

Při kolizi vytvoříme v tabulce spojový seznam.

Paměťová náročnost je pro každý seznam O(1+l(i)), kde l(i) je délka toho seznamu.

Optimalizace: s uspořádanými separovanými řetězci - seznamy jsou uspořádány podle velikosti, rychlejší op.SEARCH (když dojdu v řetězci za místo, kde by byl hledaný prvek, můžu skončit).

Očekávaná délka řetězců:

  • stř.hodnota: E(l) = α = n / m
  • rozptyl: var(l) = n/m (1 - 1/m)
Dk (Očekávaná délka řetězců):  
Pro odhad složitosti alogritmů předpokládáme, že:
  • Hashovací funkce h rozděluje data rovnoměrně
  • Sama reprezentovaná množina S je náhodný výběr z U s rovnoměrným rozdělením

Tyto předpoklady v praxi ale splněny být nemusí.

Pro odhad složitosti se počítá očekávaná délka řetězců. Označme délku $ i\,\! $-tého řetězce jako $ \mathbf{l}(i)\,\! $. Potom pravděpodobnost, že tento řetězec má délku $ l\,\! $, odpovídá binomickému rozdělení:

$ P(\mathbf{l}(i) = l) = p_{n,l} = \mathbf{}\binom{n}{l}\left(\frac{1}{m}\right)^{l}\left(1-\frac{1}{m}\right)^{n-l}\,\! $

Toto je jen aproximace (pro nekonečnou velikost univerza i seznamů), pro případ, že $ N>>n^2 m\,\! $, ale lze použít. Očekávaná délka řetězce pak vychází jako (rozepíšu faktoriál a vytknu $ \frac{n}{m}\,\! $, pak změním rozsah sumace $ 1\dots n\,\! $ (protože násobení $ l=0 $ mi nic nedá), pak můžu z $ l-1 $ udělat $ l $ a sumovat $ 0\dots n-1\,\! $):

$ E(l)=\sum_{l=0}^{n}lp_{n,l}=\frac{n}{m}\sum_{l=0}^{n-1}\mathbf{}\binom{n-1}{l}(\frac{1}{m})^l(1-\frac{1}{m})^{n-1-l}=\frac{n}{m}(\frac{1}{m}+1-\frac{1}{m})^{n-1}=\frac{n}{m}=\alpha\,\! $

Vlastně tu ale objevujeme Ameriku tím, že počítáme střední hodnotu binomicky rozdělené veličiny s parametrem $ \frac{1}{m} $ -- ze vzorce nám vyjde to samé. Stejně tak rozptyl ze vzorce vyjde $ \frac{n}{m}\left(1 - \frac{1}{m}\right) $.

Očekávaná délka nejdelšího řetězce (ocekávaný nejhorší případ):

E(NP) = O (log n / log log n)

Dk(Očekávaná délka nejdelšího řetězce):  

Tento údaj však sám o sobě nestačí, počítá se i očekávaný nejhorší případ (očekávaná délka nejdelšího řetězce). Ta se definuje následovně:

$ EMS = \sum_{j}j P(\max_{i} \mathbf{l}(i) = j) = \sum_{j} P(\max_{i}\mathbf{l}(i) \geq j )\,\! $

Z toho (pravděpodobnost disjunkce jevů je $ \leq\,\; $ součet jednotlivých pravděpodobností; vyčíslení: počet podmnožin správné velikosti a pravděpodobnost, že mají stejný hash):

$ P(\max_{i}\mathbf{l}(j)\geq j ) \leq \sum_{i}P(\mathbf{l}(i)\geq j) \leq m \mathbf{}\binom{n}{j}(\frac{1}{m})^j = \frac{\prod_{k=0}^{j-1}(n-k)}{j!}(\frac{1}{m})^{j-1} \leq n (\frac{n}{m})^{j-1}\frac{1}{j!}\,\! $

Najdeme mezní hodnotu $ j_0\,\! $, pro které $ n(\frac{n}{m})^{j-1}\frac{1}{j!}\leq 1\,\! $. Označme $ k_0 = \min\{k|n\leq k!\} \,\! $. Potom $ j_0 \leq k_0\,\! $. Ze Stirlingovy formule plyne, že $ \log x! = \Theta(x\log x)\,\! $. Z toho odvodíme (hodně neformálně, asymptoticky):

$ \log k_0! = k_0 \log k_0 = O(\log n)\,\; $
$ \log k_0 + \log\log k_0 \approx \log k_0 = O(\log\log n)\,\; $
$ k_0 = \frac{k_0 \log k_0}{\log k_0} = O(\frac{\log n}{\log\log n})\,\; $

A $ j_0 = O(k_0) $. Pro $ \alpha\leq 1\,\! $ platí, že $ EMS = O(j_0)\,\; $:

$ EMS=\sum_{j}P(\max_{i}\mathbf{l}(i)\geq j)\leq \sum_{j}\min\{1,n(\frac{n}{m})^{j-1}\frac{1}{j!}\} = \sum_{j=1}^{j_0}1 + \sum_{j=j_0+1}^{\infty}(n(\frac{n}{m})^{j-1}\frac{1}{j!}) \leq j_0 + \sum_{j=j_0+1}^{\infty}\frac{n}{j!} = \dots \leq j_0 + \frac{1}{j_0}\,\! $

A tedy očekávaná délka nejdelšího řetězce je $ O(\frac{\log n}{\log\log n})\,\; $.

Hašování s přemisťováním

S přemísťováním[editovat | editovat zdroj]

každé políčko má dva ukazatele (prev, next), s jejichž pomocí tvoří kolizní položky řetězec

  • INSERT - při kolizi je původní položka přemístěna
  • 💡 dá se říct že jde o implementaci separovaných řetězců v 1 tabulce
  • 💡nevýhoda: přemísťování při INSERTu zpomaluje

Se 2 ukazateli[editovat | editovat zdroj]

  • podobné předchozímu, políčko má ukazatele na začátek řetězce a následníka (begin, next)
  • prvky se nepřemisťují, místo toho může být začátek přesměrován pomocí prvního ukazatele
  • 💡 zrychlí INSERT a DELETE ale zpomalí SEARCH


standardní,bez pomocné paměti (LISCH, EISCH)
standardní,bez pomocné paměti (LISCH, EISCH)
s pomocnou pamětí (LICH, EICH, VICH)
s pomocnou pamětí (LICH, EICH, VICH)

Srůstající hashování (coalesced chaining)[editovat | editovat zdroj]

řetězce pomocí 1 ukazatele v hashovací tabulce navíc - odkaz na další prvek NEXT

💡 Nepodporují efektivní DELETE

💡 Očekávaná délka řetězce(poč.testů) při zaplněné tabulce: 3 a s pomocnou pamětí 2

Standardní, bez pomocné paměti -- "late insert standard" LISCH a "early insert standard" EISCH[editovat | editovat zdroj]

  • LISCH (late-insertion standard) přidává se za poslední prvek řetězce, projití celého řetězce s testy na přítomnost prvku, potom vložení na libovolné volné místo v tabulce a připojení na konec řetězce
  • EISCH (early-insertion standard) v případě neprázdného řetězce vždy za 1. prvek, vložení na nějaké volné místo v tabulce a jen přepojení ukazatelů NEXT

S pomocnou pamětí -- "late insert" LICH, "varied insert" VICH, "early insert" EICH[editovat | editovat zdroj]

paměť na dvě části:

  • (hash-funkcí) přímo adresovatelná
  • pomocná část (bez přístupu hash-funkcí)

Kolize ukládáme do pomocné části, pak teprve do přímo adresovatelné(oddalujeme srůstání řetězců). Chování se tak až dourčitého okamžiku podobá separovaným.

  • LICH(late-insertion) vždy přidává na konec řetězce
  • EICH(early-insertion) v případě neprázdného řetězce vždy za 1. prvek
  • VICH(varied-insertion) v pomocné paměti jako LICH, v přímo adresovatelné části jako EICH


Hašování s lineárním přidáváním (probing)
Hašování s lineárním přidáváním (probing)
Dvojité hašování
Dvojité hašování

Otevřené adresování (open addressing)[editovat | editovat zdroj]

Lineární zkoušení (přidávání, linear probing)[editovat | editovat zdroj]

tabulka má jen klíč, kolizní prvky se dávají na první volné místo

  • např: h(k, i) = (h'(k) + i) mod m
    • 💡 "cyklická" paměť, tj. když dojdeme na konec, vkládáme od začátku.
    • 💡 nepoužívá žádné dodatečné položky v hashovací tabulce (nalezení dalšího prvku z řetězce je přímo v algoritmu)
  • 💡 spec. případ dvojitého pro h2(x) = 1
  • použitelné do zaplnění 75% pak moc velké shluky
  • DELETE se řeší přehashováním celého "clusteru" dat

Dvojité hashování (double hashing)[editovat | editovat zdroj]

podobné, jakmile selže h1 použije se 0,1,... - násobek h2:

  • h(k, i) = (h1(k) + ih2(k)) mod m
Příklad kukaččího hašování. Šipky ukazují alternativní umístění pro každý klíč. Nová položka by byla vložena na pozici A tak, že A se přesune na svou alternativní pozici teď zabranou B. Proto se B přesune na svou alternativní pozici, která je teď prázdná. Vložení nového prvku na pozici H by se nepodařilo: protože H je částí cyklu (spolu v W), nový prvek bude zase přemísťován.

Kukaččí hashování (cuckoo)[editovat | editovat zdroj]

2 hashovací fce h₁ a h₂ :

  • INSERT - pokud je místo v tabulce určené h₁ plné, přehashujeme původní prvek pomocí h₂ (jako "kukačka")
    • 💡 "cyklická" paměť, tj. když dojdeme na konec, vkládáme od začátku
  • SEARCH pak projde max 2 pozice

Srovnání[editovat | editovat zdroj]

Podle počtu testů v SEARCH:

neúspěšné úspěšné
0. kukaččí kukaččí
1. separované uspořádané řetězce separované (usp. i neusp.) řetězce, přemísťování
2. separované řetězce, přemísťování dva ukazatele
3. dva ukazatele VICH
4. VICH, LICH LICH
5. EICH EICH
6. LISCH, EISCH EISCH
7. dvojité hashování LISCH
8. lineární přidávání dvojité hashování
9. lineární přidávání
  • VICH je při vhodném $ \alpha\,\! $ lepší než hashování se dvěma ukazateli.
  • Lineární přidávání se nedá použít pro $ \alpha > 0.7\,\! $, dvojité hashování pro $ \alpha > 0.9\,\! $.
  • Separované řetězce a obecné srůstající hashování používají víc paměti, přemísťování a dvojité hashování zas víc času, tj. nelze říct, které je jednoznačně lepší.

Implementační dodatky[editovat | editovat zdroj]

  • Pro hledání volných řádků se většinou používá seznam (zásobník).
  • Přeplnění se většinou řeší držením $ \alpha\,\! $ v rozumném intervalu ($ \langle 1/4, 1\rangle\,\! $) a přehashováním do jinak velké tabulky ($ 2^i\cdot m\,\! $) při pře- nebo podtečení
  • V praxi se doporučuje přehashování odkládat (např. pomocnými tabulkami) a provádět při nečinnosti systému.

DELETE se ve strukturách, které ho nepodporují, řeší označením políčka jako smazaného s možností využití při vkládání. V případě, že polovina polí je blokovaná tímto způsobem, se vše přehashuje. Pro srůstající hashování se toto používat nemusí, máme metody na zachování náhodnosti rozdělení dat.

V praxi je výhodné, známe-li něco o rozdělení vstupních dat, aby ho hashovací funkce kopírovala (většinou to ale nejde), jinak musíme předpokládat rovnoměrnost, což zaručeno zdaleka není. Nutnost rovnoměrného rozdělení vstupních dat lze obejít (viz níže).

Univerzální hashování (6×🎓)[editovat | editovat zdroj]

Zážitky ze zkoušek  
  • Reseni kolizi v hashovani a univerzalni hashovani (2012, Majerech) - Na uvod klasicky vycet ruznych reseni kolizi ("ten sklep v tom, jak ho popisujete, vam k nicemu nebude, podle me"), pak dlouhe paceni toho, ze se pri velkem load factoru da tabulka zvetsit (vubec me nenapadlo, ze je potreba to rict, ale M. byl chapavy a pockal si, az jsem se chytil za nos), pak povidani o rozdilu mezi randomizovanou slozitosti a ocekavanou slozitosti ("co kdyz budete mit robota nad pacientem, co z nej strika krev, bude vam tohle hashovani stacit?"), diskuse o doplneni RB stromu do jednotlivych bucketu a tak. Slabsi povahy by si mohly myslet, ze je to na vyhazov, ale to vubec neni pravda, M. je velmi inteligentni a korektni a i zkouseni je u nej prilezitost k vysvetleni zajimavosti. Bylo fajn, ze se neptal na algebraicke principy fungovani c-univerzalnich systemu, ale spis mu slo o porozumeni, jak to funguje a v cem je to dobre/spatne.
  • Hašování (2013, Kolman) - Mal som rozprávať o hašování všeobecne, čo to je, prečo to riešime a pridať čo prináša univ. a perfektné hašovanie. Vydal som zo seba nejaký všeobecný úvod, spomenul som štandardné spôsoby riešenia kolízii a čím sa od seba odlišujú (bez presného popisu algoritmov), spomenul som univerzálne hašovanie a perfektné hašovanie. Spolu so zopár otázkami na univerzálne hašovanie (c-univerzálny systém) to bohato stačilo.
  • univerzální hashování (2012, Grafika, Dvořák) - K tomu univ. hashování jsem napsal definici, definici c-univerzálního systému, konstrukci systému s důkazem c-univerzality (podle skript Koubka) a bez důkazu složitost operací. Tohle se mu sice líbilo, ale pak začal víc rozebírat tu složitost počtu operací a tam jsem už nic moc kloudnýho do kupy nedal. Nechtěl to dokázat, ale nějak interpretovat, a to se mi nedařilo. Zasekl jsem se u definice očekávané délky řetězce a snažil jsem se tu diskuzi stočit jinam, protože tady o tom jsem věděl kulový. :) Nakonec jsme to nechali být a ještě mě taky dostal otázkou, kdy se vybírá ten náhodnej index hashovací funkce. Já jsem si myslel, že se vybírá pro každý prvek nová, ale není to tak, protože bych pak nevěděl, kterou funkci jsem pro každej prvek použil. Prý se teda volí index jednou předtím, než přijdou data a pokud se ukáže, že vybraná funkce není dobrá, tak se potom může vybrat nová a tabulka celá přehashovat.
  • univerzalni a perfektni hasovani (2011 , postarsi pan, ktereho jsem nikdy predetim nevidel) - A hned po ranu...bum prask...univerzalni a perfektni hasovani, abychom se nenudili. Tady mi hodne pomohla prednaska z MIT http://videolectures.net/mit6046jf05_leiserson_lec08/ a to, ze neznal koubkovy definice a konstrukce. No, neco jsem tam tvoril, obcas vypadal zmatene, obcas ze to tak nejak zna taky...nakonec vypadal spokojene
  • Hašování (2013, Majerech) - Vyjmenoval jsem předpoklady, základní typy hašování, očekávaná délka řetězce separovaných řetězců (kromě definice univerzálního hašování jediný vzoreček, který se po mně chtěl), základy univerzálního hašování, na perfektní už se nedostalo. Zkoušející byl Majerech - hodně šťoural, ale zajímaly ho praktické aspekty použití spíš než vzorečky (i když kolegu přede mnou dusili na definici nějakých vyhledávacích stromů).
  • Univerzální hašování (2012, Čepek) - Definice (c)-univerzálního systému, potom jsem ukázal konstrukci 1-univerzálního podle MIT (na který jsem se koukal den předtím). Za deset minut bylo hotovo
  • Univerzální hašování (2004, Koubek) - Uplna katastrofa ovsem bylo univerzalni hashovani. Nejdriv jsem presvedcive dokazal, ze nevim co to je, pote jsem po nadhozeni napovedy (c-univerzalni posloupnost hashovacich funkci) dal s velkym usilim a dalsi pomoci dohromady definici a otazku jsem zakoncil marnym pokusem dokazat tvrzeni - nakonec mi to musel malem nadiktovat ...
zkazky I1/4  
 
  • Univerzální hašování (2012, Koubek) - popsal jsem základní vlastnosti, odhad délky řetězců, minimální velikost a konstrukci 1-univerzálního hašování podle Leiserssona - doplňující dotazy na min. velikost c a ještě jestli lze zmenšit tu množinu funkcí
  • Univerzální Hashování (2014, Koubek) - MIT konstrukce bohatě stačila, padly nějaké dotazy na obecné vlastnosti, které chceme od univ. systému, proč to vůbec děláme, jak ˇje to ovlivněné pseudonáhodností místo náhodnosti.
  • Univerzální hashování (2014, Hladík) - Ukázal jsem tu konstrukci podle videa z MIT. Zajímaly ho jak je to obecněji pro c-univerzální systémy, měl doplňující otázky k velikosti množiny, něco jsem věděl něco ne.
  • Univerzální hashovaní (2013, Čepek) - Popsal jsem motivaci, pak konstrukci jak je v Koubkových skriptech. Pak očekávaný počet kolizí (takové to O(1+cα)). A pak dolní odhad na $ \|I\| $. Všechno jsem psal samozřejmě s důkazy. Stačilo to a nic víc doc. Čepek nechtěl. Padly ještě nějaké dotazy ohledně hašování obecně. Nicméně otázka byla nakonec jedna z příjemnějších.
  • Univerzální hašování (2014, Koubek) - Po chvíli psaní mi to vzal a nakoukl (má poslední otázka a zbývali jsme tam poslední dva). Měl jsem tam úvodní povídání, první univerzální systém ze skript, lepší univerzální systém ze skript (vše bez důkazů). Stačilo mu to, jen měl pár kontrolních otázek.
  • Univerzalni hashovani (2011, cepek) - U univerzalniho hashovani bohate stacilo povidani z MIT prednasky, mnohokrat diky cloveku, ktery to video objevil. Rychlemu nasobeni jsem se branil, ale neubranil, vedel jsem jenom, ze se to nejspis nejak prevede na DFT. Cekal jsem nejhorsi, ale chopil se toho Vladan Majerech a behem asi 40 minut mi celou zalezitost metodou navadejicich otazek pred komisi vysvetlil, respekt:))
  • Hashovanie, riešenie kolízií, univerzálne hashovanie (2012, Vladan Majerech) - Dr. Majerech sa párkrát počas celého skúšania chodil pýtať (nielen mňa), či už chceme uňho odpovedať a tváril sa sklamane, že nikto nechce. :) Ja som si ho nechal nakoniec, pretože som tušil, že to hashovanie nebude úplne ono. Keď som nakoniec začal spisovať všetky možné hashovania (separované reťazce, s premiestňovaním, zrastajúce reťazce, bla bla bla) a napísal som prvý riadok z univerzálneho hashovania, tak ma prerušil, že nejdime sa toľko rozpisovať a začal som mu rozprávať, čo som spísal. Po chvíľke predstavovania Yet Another™ hashovacieho variantu ma prerušil, že to nemusíme, hlavne sa sústreďme na to univerzálne hashovanie. Ešte sa teda spýtal na výhody a nevýhody rozličných hashovacích stratégií, v čom som úplne jasno nemal a niečo som vymyslel, k niečomu som bol s (výdatnou) Majerechovou pomocou dokopaný. Potom som nejako opísal univerzálne hashovanie, avšak už som príliš nevedel o detailoch, na ktoré sa ma pýtal, okrem všeobecnej výhody (možnosti prehashovať pri raste reťazcov). Nespomenul som si na to, že sa používa viac systémov c-univerzálnych funkcií a vôbec som nikdy predtým nezistil, že sa počas práce s hashtabuľkou vedľa stavia preventívne nová. Nakoniec som ešte, už pomaly nevediac, ako sa volám, načrtol ideu príkladu na c-univerzálny systém, ale tam ma rozbilo to, cez čo moduliť (ax+b mod N, mod m? mod N mod m!). Celkovo si ma tam dr. Majerech celkom smažil, pokúšajúc sa o vylámanie nejakej znalosti. Na vyhodenie sa síce asi netváril, ale ja by som si za takúto odpoveď asi nič lepšie než trojku nedal.
Hašování - Operace: SEARCH, INSERT, DELETE
Univerzum klíčů U a K⊆U je množina použitých klíčů |K| = n
Hašovací funkce h: U→{0,1,..,m−1} mapuje univerzum U do(menší) tabulky T [0,..,m−1], |U| > m
Kolize je situace: h(ki) = h(kj), pro ki≠kj; ki,kj∈K
Faktor naplnění: α = n/m

Založeno na MIT přednášce v AJ popisující princip universálního a perfektního hašování. Lepší pro pochopení základu, než se zmateně dívat na 10 stránek vzorečků :). slidy zapisky

abychom si vylepšili naše šance že fce h bude fungovat dobře, budeme jí brát náhodně z obecnější (konečné) množiny H fcí mapujících universum klíčů U do tabulky {0,1,..,m−1}

1-universalni system
  • tj. H ⊆ { h | h: U → {0,1,..,m−1} }
  • třída fcí H je c-univerzální - pokud má v tabulce velké m maximálně $ \frac{c |H|}{m} $ kolizních fcí ∀ dva různé prvky z univerza
    • tj. ∀xyU: |{hH: h(x)=h(y)}| ≤ $ \frac{c |H|}{m} $
    • 💡 tj. čím menší c tím méně kolizí a fce jsou "různorodější"

Konstrukce 1-univerzálního H (MIT verze)[editovat | editovat zdroj]

  1. podmínka: mějme prvočíslo m
  2. pre-process: klíč k se rozdělí na r+1 číslic, tedy k = ⟨k₀,k₁,...,kᵣ⟩; kᵢ ∈ {0,1,...,m-1}.
    • 💡 tj. klic k zapíše v číselné soustavě o základu m
  3. náhodnost: vezmeme náhodně a = ⟨a₀,a₁,...,aᵣ⟩; aᵢ ∈ {0,1,...,m-1}
  4. hashovací fce: hₐ(k)=Σᵢ₌₀…ᵣ(akᵢ) mod m
    • 💡 tj. H = {hₐ}
Dk (zkonstruované H je univerzální):[editovat | editovat zdroj]

a) Celkový počet hashovacích fcí v třídě: | H |=mʳ⁺¹ protože každé z r+1 aᵢ může nabývat m možných hodnot

b) Počet hashovacích funkcí které pro různá x a y kolidují:

Buď x=⟨x₀,x₁,...,xᵣ

y=⟨y₀,y₁,...,yᵣ⟩ různé klíče (liší se aspoň v jedné číslici).

BÚNO, předpokládejme že x a y se liší v první číslici; na pozici 0.

Pokud x a y kolidují, pak: hₐ(x) = hₐ(y) ⇒ (Σ axᵢ) mod m = (Σ ayᵢ) mod m

upravíme na:  

⇒ Σ axᵢ ≡ Σayᵢ (mod m)

⇒ Σ aᵢ (xᵢ - yᵢ ) ≡ 0 (mod m)

a₀ ( x₀ - y₀ ) + Σ aᵢ (xᵢ - yᵢ ) ≡ 0 (mod m)

[Note: the above step applies because m is prime and x₀y₀, therefore ( x₀ - y₀ )⁻¹ exists]

a₀ = ( ( -Σ aᵢ (xᵢ - yᵢ )) ( x₀ - y₀ )⁻¹ ) mod m

Z předchozího vyplývá že jakmile jsou vybrány hodnoty a₁,...,aᵣ , přesně 1 hodnota a₀ způsobí kolizi x a y. Spočítáním možných hodnot a₀ způsobujících kolize x a y nám dává počet hₐ z H působících kolize x a y.

To se rovná počtu možných kombinací a₁,...,aᵣ což je mʳ protože každá z r číslic má m možných hodnot.

Část a) nám dala celkový počet hashovacích fcí: mʳ⁺¹

Část b) nám dala počet fcí způsobujících kolize mezi x a y: mʳ

Tedy počet fcí způsobujících kolize ve třídě je: mʳ = mʳ⁺¹/m = 1|H|/m , a tedy H je 1-univerzální.

Perfektní hashování (🎓)[editovat | editovat zdroj]

Zážitky ze zkoušek  
  • Hašování (2013, Kolman) - Mal som rozprávať o hašování všeobecne, čo to je, prečo to riešime a pridať čo prináša univ. a perfektné hašovanie. Vydal som zo seba nejaký všeobecný úvod, spomenul som štandardné spôsoby riešenia kolízii a čím sa od seba odlišujú (bez presného popisu algoritmov), spomenul som univerzálne hašovanie a perfektné hašovanie. Spolu so zopár otázkami na univerzálne hašovanie (c-univerzálny systém) to bohato stačilo.
  • Perfektni hashovani (2013, Hladik) - nejake odhady velikosti systemu (Koubkovi materialy), konstrukce a idee podle prednasky z MIT (tak jak tu nekde je zmineno v jinem vlakne)
  • univerzalni a perfektni hasovani (2011 , postarsi pan, ktereho jsem nikdy predetim nevidel) - A hned po ranu...bum prask...univerzalni a perfektni hasovani, abychom se nenudili. Tady mi hodne pomohla prednaska z MIT http://videolectures.net/mit6046jf05_leiserson_lec08/ a to, ze neznal koubkovy definice a konstrukce. No, neco jsem tam tvoril, obcas vypadal zmatene, obcas ze to tak nejak zna taky...nakonec vypadal spokojene


zkazky I1/4  
  • perfektní Hashování (2014, MJ) - popsal jsem 1-univerzální systém, jak se vytvoří a jak ho použiji na perfektní hashování. To jsem popsal a nastínil jak se to spočítá.
  • perfektní hashování (2011, Majerech) - Předvedl jsem konstrukci z Leisersonovy přednášky na MIT a spočetl jsem že očekávaná prostorová složitost je O(n), ještě jsem byl ochotný počítat horní mez pro pravděpodobnost kolize na druhé úrovni, ale Majerech chtěl, abych zkusil recyklovat výpočet z té první. Ukázalo se, že to moc nejde, ale o to bylo zkoušení zajímavější:). Do výpočtů lehce šťoural, ale ne nějak hnidopišsky, spíš asi šlo o to zjistit, jestli vím, co počítám.
perfektní hashování - pomocí 2 univerzálních, v 1.tabulce jsou parametry pro 2.univerzální hashovací funkci (z konstrukce univerzálního výše)

známe množinu klíčů předem ⇒ můžeme vytvořit hashování bez kolizí ( MEMBER v O(1) ), ale má to svojí cenu: tabulka bude statická (INSERT je velmi obtížný)

  • Idea: 2-úrovňové univerzální hashování, s kolizemi na 1. ale bez kolizí na 2.úrovni
  • hashovací funkce h je perfektní pro množinu S, pokud nemá kolize ∀ dva různé prvky z S
    • 💡 tj. ∀xyS: h(x) ≠ h(y)
    • Soubor funkcí H: U = {0,1,..,N−1} → {0,1,..,m−1} je (N,m,n)-perfektní, pokud ∀S U takové, že |S| = n existuje hH perfektní pro S (💡 tj. bez kolizí).

Konstrukce perfektního hashování (MIT verze)[editovat | editovat zdroj]

Velikost level-1 tabulky dáme na m = n a velikost level-2 tabulky mᵢ = nᵢ² . Celkem budeme potřebovat O(n) paměti.

Věta (#kolizí n čísel pro tabulku velkou n²)H je třída univ.fcí pro tabulku velikosti m = n². Pak kdyz pouzijeme nahodnou funkci z H na zahasovani n cisel, tak očekávaný počet kolizí je menši nez 1/2.

Dk (přímo):

Z definice univerzálnosti, pravděpodobnost kolize 2 klíčů při fci h je $ \frac{1}{m} = \frac{1}{n²} $ .

Protože máme $ \binom{n}{2} $ párů klíčů co mohou kolidovat, předpokládaný počet kolizí je:

$ \binom{n}{2} \frac{1}{n²} = \frac{n(n-1)}{2} \frac{1}{n²} = \frac{n-1}{2n} = \frac{1-\frac{1}{n}}{2} < \frac{1}{2} $

Externí hashování (asi se už nezkouší?)[editovat | editovat zdroj]

hashovací struktura se nevejde do hlavní paměti (RAM), efektivnost se počítá podle počtu přístupů k blokům v externí paměti (HDD)

Statické hashovací metody[editovat | editovat zdroj]

  • hashovací fce mapuje klíče do fixního počtu adres/stránek
  • umožňují přidávat klíče ale neumožňují rozšiřovat adresní prostor bez přehashování celého indexu
  • vhodné pro statické databáze

Cormack (perfektní hashování)[editovat | editovat zdroj]

Pre pristup najprv vypocitame riadok s adresata funkciou h(k) = j . Adresa v hlavnom subore bude potom j.p + hⱼᵢ (k, j.r)

V vyzdvyhnutiu lubovolneho zaznamu su potrebne najviac dva pristupy na disk. Ak je adresar ulozeny v pamati tak potom jeden.

Potrebujeme:

  • Hlavnu hashovaciu funkciu h(k) ktora vracia [0...n] Pre pristup k riadku adresara
  • Pomocnu hashovaciu funkcia hᵢ(k, r) vracia hodnotu s ⟨0, r - 1⟩ napr hᵢ(k, r) = (k mod (2i + 100r + 1)) mod r
  • Adresar ( Velkost O(n) kde n je velkost suboru ) ktory obsahuje parametre druhej hashovacej funkcie ( p : index do primarneho adresara, i index hashovacej funcie , r pocet miest na kolko hashovacia funcia hᵢ prvky hashuje)
  • Primarny subor obsahuje data a je ulozeny na disku.

FIND: Pre pristup najprv vypocitame riadok s adresata funkciou h(k) = j . Adresa v hlavnom subore bude potom j.p + hⱼᵢ ( k, j.r )

INSERT: Vsetky hodnoty adresara su na zaciatku 0.

  • Zistime riadok adresara
    • Ak je prvy najdeme pre neho volne miesto , ulozime ho a zauktualizujeme adresar
    • Ak nieje prvy zobereme kolidujuce zaznamy a pozrieme ci nemame koliziu. Ak nie najdeme novu funciu ktora bude mat obor hodnot tak aby sme zaheshovali n + 1 prvkov , najdeme volne miesto a zaktualizujeme adresar.
Příklad  
Vysvetlivky:
  p ... pointer do primarniho souboru
  i ... index pouzite hashovaci funkce
  r ... pocet kolidujicich prvku/rozsah pro hi (velikost bloku v prim.
        souboru, jehoz zacatek dostanu pomoci has. fce h)

Hashovaci funkce:
  h(k) = k mod 7
  hi(k,r) = (k >> i) % r

Vkladane prvky:
  8, 9, 23, 5, 12, 22, 2

i(8):
   p    i   r
  ┌────┬───┬───┐    ┌────┐
0 │    │   │   │  0 │  8 │
1 │  0 │ 0 │ 1 │    └────┘
2 │    │   │   │      \
3 │    │   │   │       primarni soubor
4 │    │   │   │
5 │    │   │   │
6 │    │   │   │ - adresar
  └────┴───┴───┘
--------------------------------------------------------------------------
i(9):
   p    i   r
  ┌────┬───┬───┐    ┌────┐
0 │    │   │   │  0 │  8 │
1 │  0 │ 0 │ 1 │  1 │  9 │
2 │  1 │ 0 │ 1 │    └────┘
3 │    │   │   │
4 │    │   │   │
5 │    │   │   │
6 │    │   │   │
  └────┴───┴───┘
--------------------------------------------------------------------------
i(23):
23 % 7 = 2, dochazi ke kolizi. Najdeme nove misto v prim. souboru,
kam se vejdou oba kolidujici prvky (souvisly blok velikosti 2).
Prvni takovy existuje na pozici 2.
Zkusime pouzit fci h0:
  23 % 2 = 1, ale take 9 % 2 = 1.
Musime tedy zvolit jinou hasovaci funkci.
Pouzijeme h1, vypocitame nove pozice prvku 9 a 23 v ramci bloku
velikosti 2.
  (23 >> 1) % 2 = 11 % 2 = 1
  (9 >> 1) % 2 = 4 % 2 = 0
Vysly ruzne hodnoty, tedy lze h1 pouzit.
   p    i   r
  ┌────┬───┬───┐    ┌────┐
0 │    │   │   │  0 │  8 │
1 │  0 │ 0 │ 1 │  1 │    │
2 │  2 │ 1 │ 2 │  2 │  9 │
3 │    │   │   │  3 │ 23 │
4 │    │   │   │    └────┘
5 │    │   │   │
6 │    │   │   │
  └────┴───┴───┘
--------------------------------------------------------------------------
i(5):
   p    i   r
  ┌────┬───┬───┐    ┌────┐
0 │    │   │   │  0 │  8 │
1 │  0 │ 0 │ 1 │  1 │  5 │
2 │  2 │ 1 │ 2 │  2 │  9 │
3 │    │   │   │  3 │ 23 │
4 │    │   │   │    └────┘
5 │  1 │ 0 │ 1 │
6 │    │   │   │
  └────┴───┴───┘
--------------------------------------------------------------------------
i(12):
 Kolize s cislem 5. Zkusime pouzit hasovaci fci h0.
  5 % 2 = 1
  12 % 2 = 0
   p    i   r
  ┌────┬───┬───┐    ┌────┐
0 │    │   │   │  0 │  8 │
1 │  0 │ 0 │ 1 │  1 │    │
2 │  2 │ 1 │ 2 │  2 │  9 │
3 │    │   │   │  3 │ 23 │
4 │    │   │   │  4 │ 12 │
5 │  4 │ 0 │ 2 │  5 │  5 │
6 │    │   │   │    └────┘
  └────┴───┴───┘
--------------------------------------------------------------------------
i(22):
 Kolize s 8. Fci h0 nelze pouzit k rozliseni, zkusime h1.
  (8 >> 1) % 2 = 0
  (22 >> 1) % 2 = 1
   p    i   r
  ┌────┬───┬───┐    ┌────┐
0 │    │   │   │  0 │    │
1 │  6 │ 1 │ 2 │  1 │    │
2 │  2 │ 1 │ 2 │  2 │  9 │
3 │    │   │   │  3 │ 23 │
4 │    │   │   │  4 │ 12 │
5 │  4 │ 0 │ 2 │  5 │  5 │
6 │    │   │   │  6 │  8 │
  └────┴───┴───┘  7 │ 22 │
                    └────┘
--------------------------------------------------------------------------
i(2):
 Kolize s 9 a 23.
 Fce h0 selze, protoze 23 % 3 = 2 % 3 = 2.
 
 9 dec = 1001 bin
 23 dec = 10111 bin
 12 dec = 1100 bin

Zkusime h1:
  (9 >> 1) % 3 = 4 % 3 =1
  (23 >> 1) % 3 = 11 % 3 = 2
  (2 >> 1) % 3 = 1
Zkusime h2:
  (9 >> 2) % 3 = 2
  (23 >> 2) % 3 = 2
  (2 >> 2) % 3 = 0
Zkusime h3:
  (9 >> 3) % 3 = 1
  (23 >> 3) % 3 = 2
  (2 >> 3) % 3 = 0
   p    i   r
  ┌────┬───┬───┐    ┌────┐
0 │    │   │   │  0 │    │   8 │  2 │
1 │  6 │ 1 │ 2 │  1 │    │   9 │  9 │
2 │  8 │ 3 │ 3 │  2 │    │  10 │ 23 │
3 │    │   │   │  3 │    │     └────┘
4 │    │   │   │  4 │ 12 │
5 │  4 │ 0 │ 2 │  5 │  5 │
6 │    │   │   │  6 │  8 │
  └────┴───┴───┘  7 │ 22 │
--------------------------------------------------------------------------
d(23):
Postupujeme podobne jako u vkladani. Potrebujeme najit souvisly blok
velikosti 2. Takovy je na zacatku, nemusime zvetsovat velikost
prim. souboru. Zmenime tedy p na 0. Snizime r a prozkousime has. fce.
Zkusime h0:
  23 % 2 = 1
  2 % 2 = 0
   p    i   r
  ┌────┬───┬───┐    ┌────┐
0 │    │   │   │  0 │  2 │
1 │  6 │ 1 │ 2 │  1 │  9 │
2 │  0 │ 0 │ 2 │  2 │    │
3 │    │   │   │  3 │    │
4 │    │   │   │  4 │ 12 │
5 │  4 │ 0 │ 2 │  5 │  5 │
6 │    │   │   │  6 │  8 │
  └────┴───┴───┘  7 │ 22 │
                    └────┘
Faginovo hashovanie pre hlbku adresara 2

Dynamické hashovací metody[editovat | editovat zdroj]

  • umožňuje dynamický nárůst adresního prostoru pomocí dynamické hashovací fce
  • vhodné pro db s měnící se velikostí

Fagin (rozšiřitelné adresářové hashování, Koubkovo "externí hashování")[editovat | editovat zdroj]

Potrebujeme

  • Adresar ( Obsahuje ukazovatele / nie nutne unikatne / na stranky dat v na disku ; hlavicku v ktorej je ulozena hlbka adresara 0 < d < r) / aky pocet bitov sa bere s pseudokluca)
  • Hashovaciu funkciu pre pseodukluc h(k). Pseodukluce maju vsetky rovnaku dlzku r
  • Stranky na disku , stranka obsahuje lokalnu hlbku d`. Ak d` < d tak na jednu stranku vedie viac ukazovatelov

FIND:

  • Spocitame pseodukluc k` = h(k)
  • Vezmeme hlbku adresata (d) a precitame prvych d bitov s pseodokluca ( nazveme to p)
  • Zobereme ukazovatel, ktory je umieneny v p.v ( v je velkost kazdeho pointra v bytoch ) ⇒ vedie na hladanu stranku

INSERT: Když se stránka naplní, rozštěpím ji na 2 podle dalšího bitu hash-funkce. Pokud už stránka používá stejně bitů jako adresář, musím zvětšit o 1 bit i adresář.

Příklad  
 Predpokladejme, ze do stranky se vejdou 2 zaznamy

 h(k) = k mod 32 - hasovaci fce
  -Vzdy na klic pouzijeme h(k) a potom vezmeme horni bity z takto
   ziskaneho cisla.
  -Pocet bitu, ktere budeme brat mame v "ousku" adresare. Pritom vzdy uvazujeme
   vsech pet bitu z cisla, tj napr. 2 dec = 10 bin budeme uvazovat jako 00010

 Vkladane hodnoty:
   5, 20, 33, 28, 30, 8, 25

 i(5): // 5 dec = 00101
       "ousko" adresare - rika, kolik bitu ma adresar
   ┌─┐/          "ousko" u stranky - rika, kolik (hornich) bitu rozlisuje
   │1└─┐     ┌─┐/ hodnoty
 0 │   │─────│1└─┐
 1 │   │─┐   │ 5 │
   └───┘ │   │   │
         │   └───┘
         └┌─┐
          │1└─┐
          │   │
          │   │
          └───┘
 i(20): // 20 dec = 10100
   ┌─┐
   │1└─┐     ┌─┐
 0 │   │─────│1└─┐
 1 │   │─┐   │  5│
   └───┘ │   │   │
         │   └───┘
         └┌─┐
          │1└─┐
          │ 20│
          │   │
          └───┘
 i(33): // 33 mod 32 = 1 = 00001
   ┌─┐
   │1└─┐     ┌─┐
 0 │   │─────│1└─┐
 1 │   │─┐   │  5│
   └───┘ │   │ 33│
         │   └───┘
         └┌─┐
          │1└─┐
          │ 20│
          │   │
          └───┘
 i(28): // 28 = 11100
   ┌─┐
   │1└─┐     ┌─┐
 0 │   │─────│1└─┐
 1 │   │─┐   │  5│
   └───┘ │   │ 33│
         │   └───┘
         └┌─┐
          │1└─┐
          │ 20│
          │ 28│
          └───┘
 i(30): // 30 = 11110
   Chceme umistit hodnotu do stranky, ktera je plna. Zvetsime adresar, po zmene
   bude dvoubitovy. Strankam, ktere nepotrebujeme stepit jen zvetsime "rozsah",
   prvky ze stepenych stranek rozhazime podle hornich bitu do spravnych stranek.
   Take si do "ouska" stranek poznamename, ze rozlisujeme hodnoty podle dvou
   bitu.
    ┌─┐       ┌─┐
    │2└─┐     │1└─┐
 00 │   │─┬───│  5│
 01 │   │─┘   │ 33│
 10 │   │───┐ └───┘
 11 │   │─┐ └─────┌─┐
    └───┘ └┌─┐    │2└─┐
           │2└─┐  │ 20│
           │ 28│  │   │
           │ 30│  └───┘
           └───┘
 i(8): // 8 = 01000
   Vkladame do plne stranky, ta se ale da rozstepit, protoze rozlisuje
   hodnoty jen podle jednoho bitu.
         ┌──────────┌─┐
    ┌─┐  │    ┌─┐   │2└─┐
    │2└─┐│    │2└─┐ │  5│
 00 │   │┘┌───│  8│ │ 33│
 01 │   │─┘   │   │ └───┘
 10 │   │───┐ └───┘
 11 │   │─┐ └─────┌─┐
    └───┘ └┌─┐    │2└─┐
           │2└─┐  │ 20│
           │ 28│  │   │
           │ 30│  └───┘
           └───┘
 i(25): // 25 = 11001
   Vkladame do plne stranky, jeji "rozsah" nelze rozdelit (rozlisuje hodnoty
   podle dvou bitu) - musime zvetsit adresar a rozdelit prislusnou stranku a
   zmenit "rozsahy" jednotlivych stranek.
           ┌─────────┌─┐
     ┌─┐   │   ┌─┐   │2└─┐
     │3└─┐ │   │2└─┐ │  8│
 000 │   │─┤┌──│  5│ │   │
 001 │   │─┘│  │ 33│ └───┘
 010 │   │─┬┘  └───┘
 011 │   │─┘            ┌─┐
 100 │   │─┬────────────│2└─┐
 101 │   │─┘       ┌─┐  │ 20│
 110 │   │─────────│3└─┐│   │
 111 │   │──┌─┐    │ 25│└───┘
     └───┘  │3└─┐  │   │
            │ 28│  └───┘
            │ 30│
            └───┘
Schéma štěpení při lineárním hašování

Litwin (lineární bezadresářové hashování)[editovat | editovat zdroj]

Nevyužívá adresář, ale potřebuje oblast přetečení a tedy není zaručeno, že se ke všem datům dostaneme v 1 přístupu na disk. Data uložena ve stránkách.

Stránky jsou štěpeny nezávisle na tom, kde došlo ke kolizi, kruhovým schématem (viz obrázek). Po každých L (L je parametr metody) vloženích je rozštěpena 1 stránka. Když dochází ke štěpení stránky, přidáme 1 stránku na konec úložiště stránek . Záznamy ze štěpené stránky (a případné z oblasti přetečení, které by patřily do štěpené stránky) jsou potom rozděleny mezi novou a štěpenou stránku.

FIND: h(k) = k` (pseudoklíč má na rozdíl Fagina podle posledních bitů a jeho délku spočítá podle počtu všech stránek, pokud tam není hledáme v obl.přetečení)

INSERT: najdi místo pomocí FIND a pak vložíme, pokud se nevejde tak nacpeme do oblasti přetečení, po L INSERTech štěpíme a podle posledních bitů rozdělíme záznamy

Růst primárního souboru je lineární ⇒ lineární hashování

Příklad  
Hasovaci fce - v nasem pripade pouze prevod z desitkove do dvojkove soustavy
Vysvetlivky:
b = 3 ...velikost bloku
l = 2 ...po kolika insertech se ma stepit stranka
Vkladane hodnoty:
12, 5, 4, 1, 3, 2, 7, 14

i(12):
┌────┐ Kdyz mame jedinou stranku (do 1. stepeni), vkladame do ni
│ 12 │ vsechny hodnoty (nezalezi na poslednim bitu).
│    │
│    │
└────┘
i(5):
┌────┐
│ 12 │
│  5 │
│    │
└────┘      "oznaceni stranky" - posledni bit(y) cisel ve strance maji
 ├──────┐ /                      tuto hodnotu
 │ 0    │ 1
┌────┐ ┌────┐  Protoze l=2 a vlozili jsme druhy prvek, dojde ke stepeni.
│ 12 │ │ 5  │  Podle posledniho bitu cisel se rozhodne, do
│    │ │    │  ktere pujdou stranky.
│    │ │    │
└────┘ └────┘
i(4):
    0      1
┌────┐ ┌────┐
│ 12 │ │  5 │
│  4 │ │    │
│    │ │    │
└────┘ └────┘
i(1): 
    0      1
┌────┐ ┌────┐
│ 12 │ │  5 │
│  4 │ │  1 │
│    │ │    │
└────┘ └────┘
 ├──────────────┐
 │ 00      1    │10
┌────┐ ┌────┐ ┌────┐ Vlozili jsme 4. prvek - dochazi ke stepeni.
│ 12 │ │  5 │ │    │ Hodnoty rozdelujeme podle poslednich dvou
│  4 │ │  1 │ │    │ bitu.
│    │ │    │ │    │
└────┘ └────┘ └────┘
i(3): 
   00      1     10
┌────┐ ┌────┐ ┌────┐
│ 12 │ │  5 │ │    │
│  4 │ │  1 │ │    │
│    │ │  3 │ │    │
└────┘ └────┘ └────┘
i(2): 
   00      1     10
┌────┐ ┌────┐ ┌────┐
│ 12 │ │  5 │ │  2 │
│  4 │ │  1 │ │    │
│    │ │  3 │ │    │
└────┘ └────┘ └────┘
        ├──────────────┐
   00   │ 01     10    │11
┌────┐ ┌────┐ ┌────┐ ┌────┐
│ 12 │ │  5 │ │  2 │ │  3 │
│  4 │ │  1 │ │    │ │    │
│    │ │    │ │    │ │    │
└────┘ └────┘ └────┘ └────┘
i(7): 
   00     01     10     11
┌────┐ ┌────┐ ┌────┐ ┌────┐
│ 12 │ │  5 │ │  2 │ │  3 │
│  4 │ │  1 │ │    │ │  7 │
│    │ │    │ │    │ │    │
└────┘ └────┘ └────┘ └────┘
i(14): 
   00     01     10     11
┌────┐ ┌────┐ ┌────┐ ┌────┐
│ 12 │ │  5 │ │  2 │ │  3 │
│  4 │ │  1 │ │ 14 │ │  7 │
│    │ │    │ │    │ │    │
└────┘ └────┘ └────┘ └────┘
 ├───────────────────────────┐
 │000     01     10     11   │100
┌────┐ ┌────┐ ┌────┐ ┌────┐ ┌────┐
│    │ │  5 │ │  2 │ │  3 │ │ 12 │
│    │ │  1 │ │ 14 │ │  7 │ │  4 │
│    │ │    │ │    │ │    │ │    │
└────┘ └────┘ └────┘ └────┘ └────┘
další zdroje  

https://is.cuni.cz/webapps/zzp/detail/46740/


Státnice -- Softwarové systémy
Složitost a vyčíslitelnost -- Tvorba algoritmů (10🎓), NP-úplnost (15🎓), Aproximační algoritmy (6🎓), Vyčíslitelné funkce a rekurzivní množiny (8🎓), Nerozhodnutelné problémy (9🎓), Věty o rekurzi (6🎓)
Datové struktury -- Stromy (32🎓), Hašování (13🎓), Třídění (10🎓)
Databázové systémy -- Formální základy: Relace (12🎓), Datalog (9🎓), Ostatní (0🎓)   Modely a jazyky: SQL (7🎓), DIS (7🎓), Odborné (3)   Implementace: Transakce (5🎓), Indexace (10🎓), Komprese (3)
Softwarové inženýrství -- Programovací jazyky a překladače, Objektově orientované a komponentové systémy, Analýza a návrh softwarových systémů
Systémové architektury -- Operační systémy, Distribuované systémy, Architektura počítačů a sítí
Počítačová grafika -- Geometrické modelování a výpočetní geometrie, Analýza a zpracování obrazu, počítačové vidění a robotika, 2D počítačová grafika, komprese obrazu a videa, Realistická syntéza obrazu, virtuální realita

🎓 - znamená kolikrát byla otázka u státnic