statnice:bakalar:b4b33alg

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
==== Základní algoritmy a datové struktury pro vyhledávání a řazení. Vyhledávací stromy, rozptylovací tabulky. Prohledávání grafu. Úlohy dynamického programování. Asymptotická složitost a její určová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]]

  * **Řád růstu funkcí** – asymptotická složitost algoritmu.
  * **Rekurze** – stromy, binární stromy, prohledávání s návratem.
  * **Fronta, zásobník** – průchod stromem/grafem do šířky/hloubky.
  * **Binární vyhledávací stromy** – AVL a B-stromy.
  * **Algoritmy řazení** – Insert Sort, Selection Sort, Bubble Sort, QuickSort, Merge Sort, Halda, Heap Sort, Radix Sort, Counting Sort.
  * **Dynamické programování** – struktura optimálního řešení, odstranění rekurze. Nejdelší společná podposloupnost, optimální násobení matic, problém batohu.
  * **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í.

===== Řád růstu funkcí =====
  * asymptotická složitost algoritmu.

===Asymptotická Složitost===

je způsob klasifikace počítačových algoritmů. Určuje operační náročnost algoritmu tak, že zjišťuje, jakým způsobem se bude chování algoritmu měnit v závislosti na změně velikosti (počtu) vstupních dat.

**Horní asymptotický odhad (velké O):**  
$f(n) \isin O(g(n))$  
$f$ je shora asymptoticky ohraničená funkcí $g$ (až na konstantu).  
Formálně:  
$\exists c > 0, n_0 > 0: \forall n > n_0: f(n) \leq c \cdot g(n)$

**Dolní asymptotický odhad (velká Ω):**  
$f(n) \isin \Omega(g(n))$  
$f$ je zdola asymptoticky ohraničená funkcí $g$.  
Formálně:  
$\exists c > 0, n_0 > 0: \forall n > n_0: f(n) \geq c \cdot g(n)$

**Těsný asymptotický odhad (velké Θ):**  
$f(n) \isin \Theta(g(n))$  
$f$ je ohraničena funkcí $g$ **shora i zdola**.  
Formálně:  
$f(n) \isin O(g(n))$ a $f(n) \isin \Omega(g(n))$

**Klasifikace dle složitosti**  
Od nejmenší po největší složitost (k je konstanta):
  * $O(1)$ – konstantní
  * $O(\log(n))$ – logaritmická
  * $O(n)$ – lineární
  * $O(n^2)$ – kvadratická
  * $O(n^3)$ – kubická
  * $O(n^k)$ – polynomiální
  * $O(k^n)$ – exponenciální
  * $O(n!)$ – faktoriálová

===Mistrovská Věta===
Používá se pro analýzu **rekurzivních algoritmů** typu **rozděl a panuj**.
  
Formát rekurze:  
$T(n) = a \cdot T\left(\frac{n}{b}\right) + f(n)$, kde:
  * $a \geq 1$ (počet podproblémů)
  * $b > 1$ (faktor zmenšení problému)
  * $f(n)$ – čas na rozdělení a složení řešení.

**Tři případy:**
  - Pokud $f(n) \isin O(n^{\log_b a - \epsilon})$ pro nějaké $\epsilon > 0$: $T(n) \isin \Theta(n^{\log_b a})$
  - Pokud $f(n) \isin \Theta(n^{\log_b a})$: $T(n) \isin \Theta(n^{\log_b a} \cdot \log n)$
  - Pokud $f(n) \isin \Omega(n^{\log_b a + \epsilon})$ a $a \cdot f\left(\frac{n}{b}\right) \leq c \cdot f(n)$ pro nějaké $c < 1$: $T(n) \isin \Theta(f(n))$

**Příklad:**  
Merge Sort: $T(n) = 2T\left(\frac{n}{2}\right) + \Theta(n)$  
  * $a = 2$, $b = 2$, $\log_b a = 1$  
  * $f(n) = \Theta(n^1)$ ⇒ **Případ 2** $\rightarrow$ $T(n) \isin \Theta(n \log n)$

===Substituční Metoda===
  - **Odhadněte tvar řešení** (např. $O(n \log n)$).
  - **Dokažte indukcí** správnost odhadu.

**Příklad:**  
  * Mějme $T(n) = 2T\left(\frac{n}{2}\right) + n$, odhadneme $T(n) \isin O(n \log n)$.  
  * **Indukční krok:** Předpokládejme, že $T\left(\frac{n}{2}\right) \leq c \cdot \frac{n}{2} \log \frac{n}{2}$.  
Dosadíme:  

$$T(n) \leq 2 \cdot c \cdot \frac{n}{2} \log \frac{n}{2} + n = c \cdot n (\log n - 1) + n \leq c \cdot n \log n$$ 
Volbou $c \geq 1$ platí nerovnost.

===Metoda Rekurzivního Stromu===
**Nakreslete strom rekurz  - e** s náklady na každé úrovni.
  - **Sečtěte náklady** napříč úrovněmi.

**Příklad:**   
$T(n) = 3T\left(\frac{n}{4}\right) + n$  
  - **Kořen:** $n$  
  - **3 větve:** $\frac{n}{4}$ každá  
  - **9 větví:** $\frac{n}{16}$ atd.  
**Součet úrovní:**  
$$n + \frac{3n}{4} + \frac{9n}{16} + \dots = n \cdot \sum_{i=0}^{\infty} \left(\frac{3}{4}\right)^i = n \cdot \frac{1}{1 - 3/4} = 4n \rightarrow T(n) \isin O(n)$$
===== Rekurze =====
  * stromy, binární stromy, prohledávání s návratem.
==== Stromy ====
Datová struktura, která se skládá z kořene, uzlů a listů.
  * Kořen je uzel, který nemá žádného rodiče.
  * Uzel je prvek stromu, který může mít jeden nebo více potomků.
  * List je uzel, který nemá žádné potomky.

Stromy jsou i typ grafů které jsou souvislé, neobsahují cykly a každé dva uzly jsou spojeny jednou cestou. Počet hran v n-uzlovém stromě je $n-1$. V computer science se většinou použivají kořenový strom, který je strom, jehož kořen nemá žádného rodiče. 


Binární strom je strom, ve kterém každý uzel má maximálně dva potomky. Tyto potomky se nazývají levý a pravý potomek.
Binární vyhledávací strom (BST) je binární strom, ve kterém pro každý uzel platí:
  * hodnota levého potomka je menší než hodnota uzlu,
  * hodnota pravého potomka je větší než hodnota uzlu.

Binární vyhledávací stromy se používají k efektivnímu vyhledávání, vkládání a odstraňování prvků. V praxi se často používají vyvážené binární vyhledávací stromy, jako jsou AVL stromy nebo červeno-černé stromy, které zajišťují, že výška stromu zůstává logaritmická vzhledem k počtu uzlů.

Reprezentace v C:
<markdown>
```c
typedef struct node {
    int data;
    struct node *left;
    struct node *right;
} Node;
```
</markdown>

=== Využití ===
Využívají se k reprezentaci hierarchických dat, jako jsou souborové systémy, organizační struktury nebo rodokmeny. Dají se také použít k implementaci různých algoritmů, jako jsou prohledávání do hloubky nebo do šířky. Jsou užitečné k řazení dat, jako je halda nebo binární vyhledávací stromy. Mohou se také použít k reprezentaci aritmetických výrazů, kde každý uzel představuje operaci a jeho potomci představují operandy.

==== Procházení stromem ====
Většinou se používá rekurze (funkce volající sama sebe) k procházení stromem.
=== Rekurze ===
Rekurze je technika, která umožňuje funkci volat sama sebe. Její součástí musí být podmínka pro ukončení rekurze, aby se zabránilo nekonečné smyčce. Rekurze se často používá k řešení problémů, které mají podobnou strukturu jako problém, který se snažíme vyřešit. Například při výpočtu faktoriálu čísla n můžeme použít rekurzi k výpočtu faktoriálu čísla n-1 a poté vynásobit výsledek číslem n.

Ideální pro techinku **Rozděl a panuj** - úlohy rozdělíme na menší podúlohy. 

V případě stromů se rekurze používá k procházení uzlů a provádění operací na každém uzlu. 
Existují tři základní způsoby procházení binárního stromu:
* Preorder (předřazení) – navštívíme uzel, poté levého potomka a nakonec pravého potomka.
* Inorder (meziřazení) – navštívíme levého potomka, poté uzel a nakonec pravého potomka.
* Postorder (pořadí) – navštívíme levého potomka, pravého potomka a nakonec uzel.

=== Backtracking (prohledávání s návratem) ===
Backtracking je technika, která se používá k prohledávání všech možných kombinací řešení problému. Nejznámnější problém který backtracking řeší je problém s n-dámskými šachovnicemi.
Jedná se o vylepšenou techniku řešení hrubou silout, která umí vyřadit mnoho možností, bez toho, aby je procházela všechny. 

**Předpoklady:**
  * Dá se zkontrolovat platnost nekompletního řešení:
    * Například u úlohy s n-queens se dá zkontrolovat, zda se královny navzájem neohrožují i když ještě nejsou všechny umístěny na šachovnici.
    * Kdybychom například bruteforcovali hash hesla tak nám backtracking nepomůže, protože neexistuje způsob jak zkontrolovat platnost nekompletního hesla.
  * Problém musí mít monotónní omezení: jakmile část řešení nevyhovuje, žádný další krok ji už nespraví.
    
**Jak funguje?**
Musíme mít způsob jak generovat částečná řešení. 

<markdown>
```python 

def candidates(solution):
  # Z předchozího řešení vygenerujeme další kandidáty, musí akceptovat i prázdné řešení
  ...
  return candidates

def add(candidate, solution):
  # Přidání kandidáta do řešení
  ...
  return new_solution

def remove(candidate, new_solution):
  # Odebrání kandidáta ze řešení
  ...
  return old_solution

def is_valid(solution):
  # Zkontroluje zda je řešení platné
  ...
  return True/False

def process(solution):
  # zpracování řešení
  print(solution)

def back_tracking(solution):
  if solution is complete:
    process(solution)
  else:
    for next in candidates(solution):
      if is_valid(next):
        solution = add(next, solution)
        backtracking(solution)
        solution = remove(next, solution)
```
</markdown>


===== Fronta, zásobník =====
  * průchod stromem/grafem do šířky/hloubky.

==== Průchod grafem do šířky ====
Začínáme v kořeni a jakmile nalezneme nějaký uzel, tak ho přidáme do fronty. Takto vždy nejdříve prohledáme vždy nejdřívě nově nalezené uzly.
Jakmile BFS najde cílový uzel, tak je nalezená cesta nejkratší. Nevýhodou je vysoká paměťová náročnost.

==== Průchod grafem do hloubky ====
Začínáme v kořeni který přidáme na vrchol stacku. Pro prohledání provedeme stack.pop() a přidáme všechny jeho potomky na vrchol stacku.
DFS nemusí najít nejkratší cestu, je ale méně paměťově náročný než BFS.

Jedno možné vylepšení ne například IDDFS, kdy iterativně zvětšujeme cutoff hranici pro maximální hloubku prohledávání. Tímto způsobem se snažíme najít nejkratší cestu, ale zároveň se vyhnout prohledávání celého grafu.


BFS a DFS průchody pro následující graf:
<tikzjax>
\usetikzlibrary{automata, positioning, arrows}

\begin{document}

\tikzset{
    ->, % makes the edges directed
    >=stealth', % makes the arrow heads bold
    node distance=3cm, % specifies the minimum distance between two nodes
    every state/.style={draw, circle, thick, fill=gray!10, minimum size=0.8cm}, % node style
}

\begin{tikzpicture}
    \node[state] (0) {0};
    \node[state, right of=0] (1) {1};
    \node[state, below of=0] (2) {2};
    \node[state, right of=2] (3) {3};
    
    \draw 
        (0) edge[bend left] (1)
        (0) edge (2)
        (1) edge (2)
        (2) edge[bend left] (0)
        (2) edge (3)
        (3) edge[loop right] ();
\end{tikzpicture}

\end{document}
</tikzjax>

<codedoc code:python> 
  <codedoc toggle BFS> 
  class Graph:
    def __init__(self):
        self.graph = defaultdict(list)

    def addEdge(self, u, v):
        self.graph[u].append(v)

    def BFS(self, s):
        visited = [False] * (max(self.graph) + 1)

        queue = []

        queue.append(s)
        visited[s] = True

        while queue:
            s = queue.pop(0)
            print(s, end=" ")

            for i in self.graph[s]:
                if not visited[i]:
                    queue.append(i)
                    visited[i] = True

  if __name__ == '__main__':
    g = Graph()
    g.addEdge(0, 1)
    g.addEdge(0, 2)
    g.addEdge(1, 2)
    g.addEdge(2, 0)
    g.addEdge(2, 3)
    g.addEdge(3, 3)

    print("Following is Breadth First Traversal"
        " (starting from vertex 2)")
    g.BFS(2)

    > 2 0 3 1
        
  </codedoc>
  <codedoc toggle DFS> 
  class Graph:

    def __init__(self):
        self.graph = defaultdict(list)

    def addEdge(self, u, v):
        self.graph[u].append(v)

    def DFSUtil(self, v, visited):
        visited.add(v)
        print(v, end=' ')

        for neighbour in self.graph[v]:
            if neighbour not in visited:
                self.DFSUtil(neighbour, visited)

    def DFS(self, v):
        visited = set()

        self.DFSUtil(v, visited)

  if __name__ == "__main__":
    g = Graph()
    g.addEdge(0, 1)
    g.addEdge(0, 2)
    g.addEdge(1, 2)
    g.addEdge(2, 0)
    g.addEdge(2, 3)
    g.addEdge(3, 3)

    print("Following is Depth First Traversal (starting from vertex 2)")
    
    g.DFS(2)

    > 2 0 1 3 
  </codedoc>
</codedoc>

===== Binární vyhledávací stromy =====
  * AVL a B-stromy.

==== AVL stromy ==== 
AVL stromy jsou vyvážené binární vyhledávací stromy, které zajišťují, že výška levého a pravého podstromu každého uzlu se liší maximálně o 1. To zaručuje, že operace vyhledávání, vkládání a odstraňování mají časovou složitost O(log n).
AVL stromy se vyvažují pomocí rotací, které se provádějí při vkládání nebo odstraňování uzlů. Existují čtyři typy rotací:
  * Levá rotace
  * Pravá rotace
  * Levá-pravá rotace
  * Pravá-levá rotace
=== Vyhledávání ===
  * Stejný postup jako v běžném BST – sestupujeme vlevo/vpravo podle srovnání klíče. Výška stromu je logaritmická, takže i vyhledávání je **O(log n)**.

=== Vkládání ===
  - Vložíme klíč standardně do listu BST.
  - Cestou zpět nahoru najdeme první uzel, jehož |balance| > 1.
  - Podle rozmístění uzlů zvolíme rotaci:
    * **LL** – pravá rotace
    * **RR** – levá rotace
    * **LR** – levá rotace na dítěti, pak pravá rotace
    * **RL** – pravá rotace na dítěti, pak levá rotace
  - Po max. 1–2 rotacích je strom opět vyvážen. Vše proběhne v čase O(log n).

=== Mazání ===
  - Najdeme a odstraníme klíč (případně jej nahradíme in-order předchůdcem/nástupcem).
  - Při návratu nahoru testujeme balance; pokud je mimo intervál $<-1,1>$, rotacemi jej opravíme.
  - V nejhorším provedeme logaritmický počet rotací.

==== B-stromy ====
Není binární strom, ale je to vyvážený strom, který se prakticky používá v databázových systémech a souborových systémech. 
B-strom je parametrizován **minimálním stupněm _t_ (t ≥ 2)**:  
  * každý uzel kromě kořene má **alespoň $t - 1_ a nejvýše _2t - 1$ klíčů**,  
  * z toho plyne, že vnitřní uzel má **$t … 2t$ potomků**.  

B-stromy umožňují efektivní vyhledávání, vkládání a odstraňování uzlů. Mají tyto vlastnosti:
  * Každý uzel může mít více než dva potomky.
  * Všechny listy jsou na stejné úrovni.
  * 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. 
Pokud rodič také překročí maximální počet klíčů, proces se opakuje až ke kořeni.

=== Vyhledávání ===
  * V každém uzlu binárně vyhledáme interval a sestoupíme do potomka; operace je **O(log_t n)** (t … minimální stupeň).

=== Vkládání ===
  - Vložíme klíč do příslušného listu.
  - Přetečení (> 2t-1 klíčů) řešíme **dělením**: list rozdělíme, prostřední klíč povýšíme do rodiče.
  - Pokud přeteče i rodič, postup opakujeme až ke kořeni; ten může vyrůst.

=== Mazání ===
  - Po odstranění klíče může uzel podteknout (< t-1 klíčů).
  - **Borrow**: vypůjčíme klíč od sourozence se ≥ t klíči.
  - **Merge**: jinak sloučíme uzel se sourozencem a stáhneme klíč z rodiče.
  - Pokud kořen zůstane prázdný, strom se zmenší o úroveň.

===== Algoritmy řazení =====
  * Insert Sort, Selection Sort, Bubble Sort, QuickSort, Merge Sort, Halda, Heap Sort, Radix Sort, Counting Sort.

==== Insert Sort ====
{{https://upload.wikimedia.org/wikipedia/commons/2/24/Sorting_insertion_sort_anim.gif?200}}

==== Selection Sort ====
{{https://upload.wikimedia.org/wikipedia/commons/3/3e/Sorting_selection_sort_anim.gif?200}}

==== Bubble Sort ====
Bubble sort postupně prohazuje prvky sousedních dvojic, dokud není pole seřazeno.
Asymptotická složitost je $O(n^2)$.

{{https://upload.wikimedia.org/wikipedia/commons/5/54/Sorting_bubblesort_anim.gif?200}}
<codedoc code:python>
def bubble_sort(arr):
  for n in range(len(arr) - 1, 0, -1):
    swapped = False  

    for i in range(n):
      if arr[i] > arr[i + 1]:
        arr[i], arr[i + 1] = arr[i + 1], arr[i]
                
        swapped = True
        
      if not swapped:
        break
  return arr
</codedoc>

==== QuickSort ====
{{https://upload.wikimedia.org/wikipedia/commons/6/6a/Sorting_quicksort_anim.gif?200}}

==== Merge Sort ====
{{https://upload.wikimedia.org/wikipedia/commons/c/c5/Merge_sort_animation2.gif?200}}

==== Heap Sort ====
{{https://upload.wikimedia.org/wikipedia/commons/1/1b/Sorting_heapsort_anim.gif?200}}

==== Radix Sort ====

==== Counting Sort ====
Counting sort řadí prvky podle počtu výskytů jednotlivých hodnot. Nejdříve spočítá počet všechn výskytů jednotlivých hodnot a poté je všechny vrátí v seřazeném pořadí.

Funguje pouze pro malý počet řazených symbolů.

{{https://upload.wikimedia.org/wikipedia/commons/6/60/Counting_Sort_Animation.gif?200}}

<codedoc code:python>
def countingSort(arr):
  max_val = max(arr)
  count = [0] * (max_val + 1)

  while len(arr) > 0:
    num = arr.pop(0)
    count[num] += 1

  arr = []
  for i in range(len(count)):
    arr += [i] * count[i]

  return arr
</codedoc>


===== Dynamické programování =====
  * struktura optimálního řešení, odstranění rekurze. Nejdelší společná podposloupnost, optimální násobení matic, problém batohu.

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.
  * 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ů




==== Nejdelší společná posloupnost (LCS) ====
Mějme dvě posloupnosti písmen, např.: **X = {BDCABA}**, **Y = {ABCBDAB}**.  
Výsledná nejdelší společná posloupnost je **BCBA**. Časová složitost algoritmu je $O(mn)$, kde $m$ a $n$ jsou délky řetězců.
=== Intuice algoritmu ===
* **Optimalní podstruktura** – délka LCS pro prefixy X[0..i) a Y[0..j) buď:
  * přidá 1 k délce LCS pro X[0..i-1) a Y[0..j-1), **pokud** X[i-1] == Y[j-1]  
    (znak je tedy součástí společné posloupnosti), nebo
  * zdědí „lepší“ délku ze dvou menších podproblémů:
    * X[0..i-1) × Y[0..j)  (ignorujeme poslední znak X)
    * X[0..i)   × Y[0..j-1) (ignorujeme poslední znak Y)

* **Překryv podproblémů** – stejné dvojice prefixů se v rekurzi objevují pořád dokola.  
  Uložením jejich hodnot do tabulky `L` (tzv. memoizace/tabelace) zabráníme opakovanému přepočítávání.

* **Tabulka**: rozměr (m+1) × (n+1).  
  Řádek 0 a sloupec 0 = prázdný řetězec ⇒ délka 0.  
  Vyplňujeme zleva-shora doprava-dolů, takže v okamžiku, kdy vypočítáváme `L[i][j]`, hodnoty všech nutných menších podproblémů už leží v tabulce.

* **Backtracking** – po naplnění tabulky jdeme z pravého dolního rohu nahoru/doleva/diagonálně.  
  Když se znaky rovnají a zároveň je `L[i][j] == L[i-1][j-1] + 1`, víme, že znak patří do výsledku a posuneme se diagonálně.  
  Jinak jdeme tam, kde je větší hodnota (nahoru nebo vlevo).  
  Posloupnost sestavujeme pozpátku, takže ji nakonec otočíme.

=== Okomentovaný kód (Python-like) ===
<code python>
def lcs_table(X: str, Y: str) -> list[list[int]]:
    """Postaví tabulku délek LCS pro všechny prefixy X a Y."""
    m, n = len(X), len(Y)
    # +1 kvůli nulovému řádku/sloupci (prefix délky 0)
    L = [[0] * (n + 1) for _ in range(m + 1)]

    # Projdeme všechny neprazdné prefixy
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:
                # Znaky se rovnají → prodloužíme předchozí LCS o 1
                L[i][j] = L[i - 1][j - 1] + 1
            else:
                # Nejsou stejné → vezmeme delší ze dvou možností
                L[i][j] = max(L[i - 1][j], L[i][j - 1])
    return L


def reconstruct_lcs(X: str, Y: str) -> str:
    """Z už sestavené tabulky vyčte jednu optimální společnou posloupnost."""
    L = lcs_table(X, Y)
    i, j = len(X), len(Y)
    seq = []

    # Jdeme z pravého dolního rohu, dokud nespadneme na okraj tabulky
    while i > 0 and j > 0:
        if X[i - 1] == Y[j - 1]:
            # Tento znak je součástí LCS
            seq.append(X[i - 1])
            i -= 1
            j -= 1
        # Posuneme se k sousední buňce s vyšší hodnotou (ignorujeme znak X nebo Y)
        elif L[i - 1][j] >= L[i][j - 1]:
            i -= 1
        else:
            j -= 1

    # Posloupnost jsme skládali odzadu, tak ji otočíme
    return ''.join(reversed(seq))
</code>
=== Ukázková tabulka LCS délek ===
První řádek/sloupec reprezentují prázdné podřetězce (nulové délky), proto ta úvodní nula.

^     ^   ^ A ^ B ^ C ^ B ^ D ^ A ^ B ^
|     | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| **B** | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| **D** | 0 | 1 | 1 | 1 | 2 | 2 | 2 | 2 |
| **C** | 0 | 1 | 2 | 2 | 2 | 2 | 2 | 2 |
| **A** | 0 | 1 | 1 | 2 | 2 | 2 | 3 | 3 |
| **B** | 0 | 1 | 2 | 2 | 3 | 3 | 3 | 4 |
| **A** | 0 | 1 | 2 | 2 | 3 | 3 | 4 | 4 |

*Interpretace:* Hodnota v pravém dolním rohu (4) je délka LCS. Postupným „cestováním“ zpět po rovných hodnotách a diagonálách, kde se znaky shodují, získáme konkrétní posloupnost **BCBA**.
===== 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í.

  * rozptylovací funkce = hashovací funkce
  * Hashovací funkce přiřadí k potenciálně libovolnému množství dat hodnotu který má vždy kosntantní délku.
  * 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)
  * Umožňují vyhledávat v tabulkách s průměrnou časovou složitostí $O(1)$.
==== Algoritmické úlohy (soutěžní) ====
  * 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…).
  * Rolling hash (Rabin–Karp) – rychlé vyhledávání vzoru v textu.
  * Longest Consecutive Sequence – O(n) řešení s `unordered_set`.
  * Počty výskytů / anagramy – frekvenční slovník pro srovnání řetězců.

==== Praktické použití ====
  * Symbol table v překladači (identifikátor → metadata).
  * Hash join v relačních databázích při spojování tabulek.
  * In-memory cache (DNS, LRU) pro konstantní přístup.
  * Deduplicace a kontrola integrity souborů (git objekty, zálohy).
  * Bloom filter – pravděpodobnostní test příslušnosti s malou pamětí.

==== 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.

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.

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 ===
Jak to funguje  – z každého políčka vede spojený seznam (linked list).

  * **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).

Výhody
  * 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é.

Nevýhody
  * Vícenásobné alokace a ukazatele → ztráta cache-locality.
  * Potenciálně vyšší režie alokátorů při častém vkládání.

Složitost  
  * Average-case: $O(1)$
  * Worst-case: $O(n)$

=== Otevřené rozptylování – Linear probing ===
Jak to funguje  – pokud je políčko z hashu obsazeno, posouváme se lineárně dál.

  * **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.
  * **Hledání** – stejně sondujeme, dokud
    * nenajdeme klíč  (nalezen) nebo nenarazíme na prázdné políčko  (klíč tam není).
  * **Mazání** – prvek nelze jen tak fyzicky odstranit, musíme použít **deleted marker** nebo re-hash kolem.

Výhody
  * Minimum ukazatelů → skvěle využívá cache.
  * Jednoduchá implementace (jedna hash funkce, žádné seznamy).

Nevýhody
  * **Primární shlukování (primary clustering)** – sousední obsazená místa tvoří dlouhé bloky a dramaticky zvyšují počet sond.
  * Vyšší load-factor (> 0.7) vede k prudkému zhoršení výkonu.

Složitost  
  * Average-case: $O(1)$
  * Worst-case: $O(n)$

=== Otevřené rozptylování – Double hashing ===
Používáme dvě hashovací funkce:

  * $h1(k)$ – primární index v rozsahu $0 … n-1$
  * $h2(k)$ – **krok (step)** v rozsahu $1 … n-1$;  
    musí být nesoudělný s $n$, aby prohlídka pokryla celé pole.

Algoritmus sondování  
$index(i) = (h1(k) + i * h2(k)) \mod n$, $i = 0,1,2,…$

  * **Vkládání** – sondujeme, dokud nenajdeme prázdné políčko.
  * **Hledání** – sondujeme, dokud  
    * nenajdeme klíč, nebo nenarazíme na prázdné políčko → klíč tam není.
  * **Mazání** – opět potřebujeme *deleted marker*.

Výhody
  * Menší shlukování než u lineárního i kvadratického sondování.
  * Při správné volbě $h2$ projde celou tabulku bez opakování indexů.

Nevýhody
  * Dvě hash funkce a nutnost hlídat nesoudělnost ➜ o chlup složitější implementace.
  * Více vypočtů hashů (na CPU to bývá zanedbatelné, ale přesto).

Složitost  
  * Average-case: $O(1)$
  * Worst-case: $O(n)$
=== Srůstající (coalesced) hashing ===
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.
  * 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.
  * 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.

Složitost  
  * Best-case: $O(1)$  
  * Average-case (při load-faktoru $α<0{.}8$): $O(1)$  
  * Worst-case: $O(n)$

Výhody  
  * Lepší cache-localita než externí seznamy.  
  * Umožní load-faktor $α$ blízký 1, protože cellar oddálí „srůstání“ řetězců.

Nevýhody  
  * Složitější správa ukazatelů a mazání.  
  * Není-li cellar správně dimenzován, výkon degraduje na $O(n)$ podobně jako otevřené sondování.

=== Univerzální hashování ===
Myšlenka: místo jediné pevné hash-funkce zvolíme při inicializaci **náhodně** $h$  
z rodiny $ℋ$, která splňuje podmínku univerzality:

$$
\forall x\neq y \quad \Pr_{h\inℋ}[\,h(x)=h(y)\,] \le \frac1m ,
$$

kde $m$ je počet bucketů.

Důsledky

  * **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íčů.
  * Adversář, který nezná zvolenou $h$, neumí zkonstruovat mnoho kolizí
    (→ odolnost proti útokům na hash-tabulky např. v webových serverech).


Složitost  
  * 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,
    že se to stane, je $\le 1/m$ a můžeme $h$ jednoduše přelosovat.
Trace: • b4b35psr • b4b01jag • exams • b4b38nvs • b0b39pgr • b0b33opt • b4b38psia • playground • b4b01num • b0b01ma1
Search

Navigation

Print/export

Tools

QR Code
