The wiki page is under active construction, expect bugs.

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
statnice:bakalar:b4b33alg [2025/06/08 13:36] – zapleka3statnice:bakalar:b4b33alg [2025/06/13 10:41] (current) – [B-stromy] prokop
Line 1: Line 1:
-==== Základní algoritmy a datové struktury pro vyhledávání a řazení. Vyhledávací stromy, rozptylovací tabulky. Prohledávání grafu. Úlohy dynamického programování. Asymptotická složitost a její určování. ====+====== Základní algoritmy a datové struktury pro vyhledávání a řazení. Vyhledávací stromy, rozptylovací tabulky. Prohledávání grafu. Úlohy dynamického programování. Asymptotická složitost a její určování. ======
  
 [[https://fel.cvut.cz/cz/education/bk/predmety/46/82/p4682306.html|B4B33ALG]] [[https://cw.fel.cvut.cz/b211/courses/b4b33alg/start|Webové stránky předmětu]] [[https://fel.cvut.cz/cz/education/bk/predmety/46/82/p4682306.html|B4B33ALG]] [[https://cw.fel.cvut.cz/b211/courses/b4b33alg/start|Webové stránky předmětu]]
Line 484: Line 484:
  
 B-strom je řízen parametrem **minimální stupeň _t_ (t ≥ 2)**: B-strom je řízen parametrem **minimální stupeň _t_ (t ≥ 2)**:
-  * Každý uzel (kromě kořene) má alespoň $t - 1$ a nejvýše $2t - 1$ klíčů.+  * Každý uzel (kromě kořene) má alespoň $floor(t/2)$ a nejvýše $2t$ klíčů.
   * Z toho plyne, že každý vnitřní uzel má mezi $t$ až $2t$ potomků.   * Z toho plyne, že každý vnitřní uzel má mezi $t$ až $2t$ potomků.
   * Kořen může mít méně než $t - 1$ klíčů.   * Kořen může mít méně než $t - 1$ klíčů.
Line 493: Line 493:
   * Každý uzel má minimální a maximální počet klíčů (viz definice $t$ výše).   * Každý uzel má minimální a maximální počet klíčů (viz definice $t$ výše).
  
-  * Když uzel překročí maximální počet klíčů ($2t - 1$), rozdělí se na dva uzly a prostřední klíč se přesune do rodiče. +  * Když uzel překročí maximální počet klíčů ($2t$), rozdělí se na dva uzly a prostřední klíč se přesune do rodiče. 
   * Pokud rodič také překročí maximální počet klíčů, proces se opakuje až ke kořeni.   * Pokud rodič také překročí maximální počet klíčů, proces se opakuje až ke kořeni.
  
Line 504: Line 504:
 === Vkládání === === Vkládání ===
   * Klíč vkládáme do správného listu.   * Klíč vkládáme do správného listu.
-  * Pokud uzel překročí $2t - 1$ klíčů:+  * Pokud uzel překročí $2t$ klíčů:
     * Rozdělíme ho na dvě části.     * Rozdělíme ho na dvě části.
     * Prostřední klíč přesuneme do rodiče.     * Prostřední klíč přesuneme do rodiče.
Line 512: Line 512:
  
 === Mazání === === Mazání ===
-  * Pokud uzel klesne pod $t - 1$ klíčů, musíme situaci opravit:+  * Pokud uzel klesne pod $floor(t/2)$ klíčů, musíme situaci opravit:
     * **Borrow** – vypůjčíme si klíč od sourozence.     * **Borrow** – vypůjčíme si klíč od sourozence.
     * **Merge** – sloučíme uzel se sourozencem a jeden klíč stáhneme z rodiče.     * **Merge** – sloučíme uzel se sourozencem a jeden klíč stáhneme z rodiče.
Line 766: Line 766:
 Je to všeobecná strategie pro řešení optimalizačních úloh. Významné vlastnosti: Je to všeobecná strategie pro řešení optimalizačních úloh. Významné vlastnosti:
   * Hledané optimální řešení lze sestavit z vhodně volených optimálních řešení téže úlohy nad redukovanými daty.   * Hledané optimální řešení lze sestavit z vhodně volených optimálních řešení téže úlohy nad redukovanými daty.
-  * V rekurzivně formulovaném postupu řešení se opakovaně objevují stejné menší podproblémy. DP umožňuje obejít opakovaný výpočet většinou jednoduchou tabelací výsledků menších podproblémů, tedy volně řečeno, přepočítáním menších výsledků+  * V rekurzivně formulovaném postupu řešení se opakovaně objevují stejné menší podproblémy. DP umožňuje obejít opakovaný výpočet většinou jednoduchou tabelací výsledků menších podproblémů, tedy volně řečeno, přepočítáním menších výsledků.
  
 ===== Dynamické programování pro Nejdelší Společnou Posloupnost (LCS) ===== ===== Dynamické programování pro Nejdelší Společnou Posloupnost (LCS) =====
-<markdown> +  * Mějme dvě posloupnosti písmen a chceme najít nejdelší společnou podposloupnost. 
-**Myšlenka algoritmu:** +  * Například u posloupností {BDCABA} a {ABCBDAB} je řešení {BCBA}. 
-  * Cíl: Najít nejdelší posloupnost znaků, která se vyskytuje ve stejném pořadí v obou vstupních řetězcích (ne nutně souvisle). +  * Časová složitost: $O(m \cdot n)$, kde $m$ a $n$ jsou délky řetězců.
-  * Dynamické programování (DP) využívá 2D tabulku pro ukládání dílčích výsledků. Buňka `dp[i][j]` udává délku LCS pro první `i` znaků řetězce `X` a první `j` znaků řetězce `Y`. +
-  * Pokud `X[i-1] == Y[j-1]`, přidáme tento znak k LCS a přičteme 1 k `dp[i-1][j-1]`. +
-  * Pokud se znaky liší, vezmeme maximum z `dp[i-1][j]` (horní buňka) a `dp[i][j-1]` (levá buňka).+
  
-**Pseudokód v Pythonu:** +  * **Myšlenka algoritmu:** 
-```python+    * Cíl: Najít nejdelší posloupnost znaků, která se vyskytuje ve stejném pořadí v obou vstupních řetězcích (ne nutně souvisle). 
 +    * Dynamické programování (DP) využívá 2D tabulku pro ukládání dílčích výsledků. 
 +    * Buňka `dp[i][j]` udává délku LCS pro první `i` znaků řetězce `X` a první `j` znaků řetězce `Y`. 
 +    * Pokud `X[i-1] == Y[j-1]`, přidáme tento znak k LCS a přičteme 1 k `dp[i-1][j-1]`. 
 +    * Pokud se znaky liší, vezmeme maximum z `dp[i-1][j]` (horní buňka) a `dp[i][j-1]` (levá buňka). 
 + 
 +  * **Pseudokód v Pythonu:** 
 +<code python>
 def lcs(X, Y): def lcs(X, Y):
     m = len(X)     m = len(X)
Line 783: Line 787:
     # Vytvoření DP tabulky s nulami (m+1 x n+1)     # Vytvoření DP tabulky s nulami (m+1 x n+1)
     dp = [[0]*(n+1) for _ in range(m+1)]     dp = [[0]*(n+1) for _ in range(m+1)]
-    +
     # Naplnění tabulky     # Naplnění tabulky
     for i in range(1, m+1):     for i in range(1, m+1):
Line 791: Line 795:
             else:             else:
                 dp[i][j] = max(dp[i-1][j], dp[i][j-1])                 dp[i][j] = max(dp[i-1][j], dp[i][j-1])
-    +
     # Rekonstrukce LCS z tabulky     # Rekonstrukce LCS z tabulky
     i, j = m, n     i, j = m, n
Line 805: Line 809:
             j -= 1             j -= 1
     return ''.join(reversed(result))     return ''.join(reversed(result))
-```+</code>
  
 **Příklad tabulky pro `X = "BDCABA"`, `Y = "ABCBDAB"`:** **Příklad tabulky pro `X = "BDCABA"`, `Y = "ABCBDAB"`:**
-  - Řešení: **"BCBA"** (délka 4). 
  
 +Řešení: **"BCBA"** (délka 4).
 +
 +**Tabulka:**
 |   |   | A | B | C | B | D | A | B | |   |   | A | B | C | B | D | A | B |
 |---|---|---|---|---|---|---|---|---| |---|---|---|---|---|---|---|---|---|
Line 820: Line 826:
 | A | 0 | 1 | 2 | 2 | 3 | 3 | 4 | 4 | | A | 0 | 1 | 2 | 2 | 3 | 3 | 4 | 4 |
  
-**Vysvětlení tabulky:** +  * **Vysvětlení tabulky:** 
-  * První řádek a sloupec jsou inicializovány na 0 (prázdné podřetězce). +    * První řádek a sloupec jsou inicializovány na 0 (prázdné podřetězce). 
-  * Buňka `dp[5][7]` (hodnota 4) ukazuje délku LCS. Cesta pro rekonstrukci je vyznačena šipkami: +    * Buňka `dp[5][7]` (hodnota 4) ukazuje délku LCS. 
-    - Začínáme od `dp[6][7]` (4), postupujeme diagonálně při shodě znaků.+    * Cesta pro rekonstrukci je postup diagonální (při shodě znaků) nebo výběr větší hodnoty z okolních buněk.
  
-**Časová složitost:**  +  * **Složitost:** 
-  * Naplnění tabulky: $O(m \cdot n)$, rekonstrukce: $O(m + n)$. +    * Naplnění tabulky: $O(m \cdot n)$ 
-  * Celkem: $O(m \cdot n)$. +    * Rekonstrukce: $O(m + n)$ 
-</markdown> +    * Celkem: $O(m \cdot n)$ 
-===== Rozptylovací tabulky (Hashing) =====+ 
 + 
 + 
 +===== 7. Rozptylovací tabulky (Hashing) =====
   * hashovací funkce, řešení kolizí, otevřené a zřetězené tabulky, double hashing, srůstající tabulky, univerzální hashování.   * hashovací funkce, řešení kolizí, otevřené a zřetězené tabulky, double hashing, srůstající tabulky, univerzální hashování.
  
-  * rozptylovací funkce = hashovací funkce +  * Rozptylovací tabulky – tabulka, určená k redukování dat na menší data, která budou jednoznačná. 
-  * Hashovací funkce přiřadí k potenciálně libovolnému množství dat hodnotu který má vždy kosntantní délku. +  * Základ datové struktury slovníku, kde operace search a insert mají konstantní složitost. 
-  * Hashovací funkce v kontextu algoritmizace by měla být hlavně rychlá (narozdíl od kryptografie, kde pomalost je část bezpečnosti za hashovací funkcí) s co nejméně kolizemi (kolize - 2 různé vstupy mají stejný výstup)+  * Hashovací funkce – funkce která datům přiřadí nějakou hodnotu konstantní délky, která se výrazně liší pro podobná data a není z ní možné rekonstruovat originální data – hash. 
 +  * Hashovací funkce přiřadí k potenciálně libovolnému množství dat hodnotu, která má vždy konstantní délku. 
 +  * V kontextu algoritmizace by měla být hlavně rychlá (na rozdíl od kryptografie, kde pomalost je část bezpečnosti). 
 +   
 +  * Cíl je generovat minimum kolizí. 
 +  * Kolize – situace, kdy dvěma různým datům přiřadíme stejný hash – řešíme pomocí zřetězeného rozptylování, nebo otevřeného rozptylování.
   * Umožňují vyhledávat v tabulkách s průměrnou časovou složitostí $O(1)$.   * Umožňují vyhledávat v tabulkách s průměrnou časovou složitostí $O(1)$.
 +
 ==== Algoritmické úlohy (soutěžní) ==== ==== Algoritmické úlohy (soutěžní) ====
-  * Two Sum – O(n) hledání dvojice se zadaným součtem pomocí `set`.+  * Two Sum – $O(n)$ hledání dvojice se zadaným součtem pomocí `set`.
   * Dynamické programování s memoizací – ukládání $T(n)$ do hashe (Fibonacci, LCS…).   * Dynamické programování s memoizací – ukládání $T(n)$ do hashe (Fibonacci, LCS…).
   * Rolling hash (Rabin–Karp) – rychlé vyhledávání vzoru v textu.   * Rolling hash (Rabin–Karp) – rychlé vyhledávání vzoru v textu.
-  * Longest Consecutive Sequence – O(n) řešení s `unordered_set`.+  * Longest Consecutive Sequence – $O(n)$ řešení s `unordered_set`.
   * Počty výskytů / anagramy – frekvenční slovník pro srovnání řetězců.   * Počty výskytů / anagramy – frekvenční slovník pro srovnání řetězců.
  
Line 847: Line 862:
   * Hash join v relačních databázích při spojování tabulek.   * Hash join v relačních databázích při spojování tabulek.
   * In-memory cache (DNS, LRU) pro konstantní přístup.   * In-memory cache (DNS, LRU) pro konstantní přístup.
-  * Deduplicace a kontrola integrity souborů (git objekty, zálohy).+  * Deduplikace a kontrola integrity souborů (git objekty, zálohy).
   * Bloom filter – pravděpodobnostní test příslušnosti s malou pamětí.   * Bloom filter – pravděpodobnostní test příslušnosti s malou pamětí.
  
 ==== Kolize v hashovacích tabulkách ==== ==== Kolize v hashovacích tabulkách ====
-Kolize  – situace, kdy dvěma různým vstupům hashovací funkce tabulky přiřadí stejný výstup.+  * Kolize nastávají, protože zobrazení z klíčů do adres hashovací funkce není prosté. 
 +  * Hashovací tabulky se používají k rychlému vyhledávání, ale protože hashovací funkce mohou mít kolize, tabulky musí umět tyto kolize řešit. 
 +  * Tabulka je nejčastěji reprezentovaná polem s indexy $0 … n-1$, kde $n$ je délka pole.
  
-Hashovací tabulky se používají k rychlému vyhledávání, ale protože hashovací funkce mohou mít kolize, tabulky musí umět tyto kolize řešit. +Existují tři běžné způsoby řešení kolizí:   
- +  * zřetězený hashing   
-Tabulka je nejčastěji reprezentovaná polem s indexy $0 … n-1$, kde $n$ je délka pole. +  * lineární sondování   
- +  * double hashing  
-Existují tři běžné způsoby řešení kolizí: zřetězený hashing, lineární sondování a double hashing.+
  
 === Zřetězený hashing === === Zřetězený hashing ===
-Jak to funguje  – z každého políčka vede spojený seznam (linked list).+  * Každá adresa si zachovává spojový seznam všech hodnot, které se namapují na danou adresu. 
 +  * Vkládání – vypočítáme index $h(k)$. Pokud políčko už obsahuje prvek, vložíme nový na konec jeho seznamu. 
 +  * Hledání – projdeme seznam, dokud klíč nenajdeme, nebo nedojdeme na jeho konec. 
 +  * Mazání – odstraníme uzel ze seznamu (klasická operace na linked-listu).
  
-  * **Vkládání** – vypočítáme index $h(k)$.   +Výhody:
-    Pokud políčko už obsahuje prvek, vložíme nový na *konec* jeho seznamu. +
-  * **Hledání** – projdeme seznam, dokud klíč nenajdeme, nebo nedojdeme na jeho konec. +
-  * **Mazání** – odstraníme uzel ze seznamu (klasická operace na linked-listu). +
- +
-Výhody+
   * Jednoduchá implementace, žádný problém s přeplněním pole.   * Jednoduchá implementace, žádný problém s přeplněním pole.
-  * Výkon se zhoršuje hladce – degraduje k $O(n)$ jen když se load-factor blíží ∞ a seznamy jsou dlouhé.+  * Výkon se zhoršuje hladce – degraduje k $O(n)$ jen když se load-factor blíží ∞.
  
-Nevýhody+Nevýhody:
   * Vícenásobné alokace a ukazatele → ztráta cache-locality.   * Vícenásobné alokace a ukazatele → ztráta cache-locality.
   * Potenciálně vyšší režie alokátorů při častém vkládání.   * Potenciálně vyšší režie alokátorů při častém vkládání.
  
-Složitost  +Složitost:
   * Average-case: $O(1)$   * Average-case: $O(1)$
   * Worst-case: $O(n)$   * Worst-case: $O(n)$
  
 === Otevřené rozptylování – Linear probing === === Otevřené rozptylování – Linear probing ===
-Jak to funguje  – pokud je políčko z hashu obsazeno, posouváme se lineárně dál.+Jak to funguje  – pokud je políčko z hashu obsazeno, posouváme se lineárně dál (modulo n).
  
-  * **Vkládání** – vypočítáme index $h(k)$.   +  * **Vkládání** – vypočítáme index $h(k)$. Kolize ⇒ zkusíme $(h(k)+1) \mod n$, pak $+1$… dokud nenajdeme prázdné místo.
-    Kolize ⇒ zkusíme $(h(k)+1) \mod n$, pak $+1$… dokud nenajdeme prázdné místo.+
   * **Hledání** – stejně sondujeme, dokud   * **Hledání** – stejně sondujeme, dokud
     * nenajdeme klíč  (nalezen) nebo nenarazíme na prázdné políčko  (klíč tam není).     * nenajdeme klíč  (nalezen) nebo nenarazíme na prázdné políčko  (klíč tam není).
Line 905: Line 918:
   * $h1(k)$ – primární index v rozsahu $0 … n-1$   * $h1(k)$ – primární index v rozsahu $0 … n-1$
   * $h2(k)$ – **krok (step)** v rozsahu $1 … n-1$;     * $h2(k)$ – **krok (step)** v rozsahu $1 … n-1$;  
-    musí být nesoudělný s $n$, aby prohlídka pokryla celé pole.+    * musí být nesoudělný s $n$, aby prohlídka pokryla celé pole.
  
 Algoritmus sondování   Algoritmus sondování  
Line 926: Line 939:
   * Average-case: $O(1)$   * Average-case: $O(1)$
   * Worst-case: $O(n)$   * Worst-case: $O(n)$
 +
 +
 === Srůstající (coalesced) hashing === === Srůstající (coalesced) hashing ===
 Kombinuje výhody otevřeného rozptylování a zřetězení: Kombinuje výhody otevřeného rozptylování a zřetězení:
  
   * Tabulka má vyhrazenou „sklepní“ část (**cellar**) – např. posledních 10–20 % buněk.   * Tabulka má vyhrazenou „sklepní“ část (**cellar**) – např. posledních 10–20 % buněk.
-  * Při kolizi prvek uložíme do **prvního volného** místa hledaného lineárně *odspodu* tabulky +  * Při kolizi prvek uložíme do **prvního volného** místa hledaného lineárně *odspodu* tabulky (tj. v cellar-zóně) a pomocí ukazatele jej připojíme k řetězci své původní bucket-pozice. 
-    (tj. v cellar-zóně) a pomocí ukazatele jej připojíme k řetězci své původní bucket-pozice. +  * Vyhledávání prochází ukazatele stejně jako u zřetězení, ale všechny uzly sedí přímo v poli, takže nedochází k fragmentaci paměti a cache-missům. 
-  * Vyhledávání prochází ukazatele stejně jako u zřetězení, ale všechny uzly sedí přímo v poli, + 
-    takže nedochází k fragmentaci paměti a cache-missům.+Různé varianty: 
 +  * LISCH (late insert standard coalesced hashing) – přidáváme na konec řetězce. 
 +  * EISCH (early insert…) – přidáváme na začátek řetězce. 
 +  * LICH, EICH – jako výše, ale se sklepem. 
 +  * VICH – kombinuje, kam přidat podle toho, kde řetězec končí.
  
 Složitost   Složitost  
Line 949: Line 968:
  
 === Univerzální hashování === === Univerzální hashování ===
-Myšlenka: místo jediné pevné hash-funkce zvolíme při inicializaci **náhodně** $h$   +Myšlenka: místo jediné pevné hash-funkce zvolíme při inicializaci **náhodně** $h$ z rodiny $ℋ$, která splňuje podmínku univerzality:
-z rodiny $ℋ$, která splňuje podmínku univerzality:+
  
 $$ $$
Line 960: Line 978:
 Důsledky Důsledky
  
-  * **Očekávaná** délka řetězce (nebo počet sond) je $\le α$, takže vkládání, +  * **Očekávaná** délka řetězce (nebo počet sond) je $\le α$, takže vkládání, vyhledávání i mazání běží v $O(1)$ očekávaném čase, bez ohledu na rozdělení klíčů. 
-    vyhledávání i mazání běží v $O(1)$ očekávaném čase, bez ohledu na rozdělení klíčů. +  * Adversář, který nezná zvolenou $h$, neumí zkonstruovat mnoho kolizí (→ odolnost proti útokům na hash-tabulky např. v webových serverech).
-  * Adversář, který nezná zvolenou $h$, neumí zkonstruovat mnoho kolizí +
-    (→ odolnost proti útokům na hash-tabulky např. v webových serverech).+
  
  
 Složitost   Složitost  
   * Best / Average (v oč.) $O(1)$, protože $\mathbb{E}[\text{kolize}] \le α$.     * Best / Average (v oč.) $O(1)$, protože $\mathbb{E}[\text{kolize}] \le α$.  
-  * Worst-case: stále $O(n)$ (kdybychom si vybrali „špatnou“ funkci), ale pravděpodobnost, +  * Worst-case: stále $O(n)$ (kdybychom si vybrali „špatnou“ funkci), ale pravděpodobnost, že se to stane, je $\le 1/m$ a můžeme $h$ jednoduše přelosovat.
-    že se to stane, je $\le 1/m$ a můžeme $h$ jednoduše přelosovat.+
  
  
    

Trace:

Navigation

Playground

QR Code
QR Code statnice:bakalar:b4b33alg (generated for current page)