Differences

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

--- statnice:bakalar:b4b33alg [2025/06/08 12:28] – zapleka3
+++ statnice:bakalar:b4b33alg [2026/06/06 17:15] (current) – [Counting Sort] knedl1k
@@ Line 1: / Line 1: @@
-==== 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í. ====
+====== 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]]
@@ Line 420: / Line 420: @@
 ===== 4. Binární vyhledávací stromy =====
-  * AVL a B-stromy.
-==== AVL stromy ====
+==== Binární vyhledávací stromy (BST) ====
-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).
+Binární vyhledávací strom je binární strom, ve kterém jsou uzly uspořádány podle hodnoty klíčů:
-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ý podstrom obsahuje pouze uzly s menším klíčem než má uzel.
-  * Levá rotace
+  * Pravý podstrom obsahuje pouze uzly s větším klíčem.
-  * Pravá rotace
-  * Levá-pravá rotace
+Každý uzel může mít maximálně dva potomky. Díky tomuto uspořádání je možné rychle vyhledávat, vkládat nebo mazat prvky – pokud je strom vyvážený, mají operace časovou složitost $O(\log n)$.
-  * Pravá-levá rotace
+=== Vyhledávání v BST ===
+  * Začínáme v kořeni stromu.
+  * Pokud je hledaná hodnota menší než hodnota uzlu, pokračujeme do levého podstromu.
+  * Pokud je větší, pokračujeme do pravého.
+  * Pokud se rovná, našli jsme ji.
+  * Díky binární struktuře je cesta k hledanému uzlu jednoznačná a v ideálním případě logaritmicky dlouhá.
+=== Vkládání ===
+  * Postupujeme podobně jako u vyhledávání.
+  * Nový uzel vložíme tam, kde by se měl nacházet – vždy jako list (na konec větve).
+  * Pokud strom připouští duplicitní klíče, vloží se do levého nebo pravého podstromu podle pravidel.
+=== Mazání ===
+  * Pokud má uzel **žádné** potomky, prostě ho odstraníme.
+  * Pokud má **jeden** potomek, nahradíme jej tímto potomkem.
+  * Pokud má **dva** potomky:
+    * Najdeme jeho **in-order předchůdce nebo nástupce** – největší uzel v levém nebo nejmenší v pravém podstromu.
+    * Jeho hodnotou nahradíme hodnotu mazání, a odstraníme ho rekurzivně – bude mít nanejvýš jeden potomek.
+  * BST může snadno ztratit rovnováhu – pokud vkládáme vzestupně seřazená data, strom degeneruje do lineárního seznamu.
+==== AVL stromy ====
+AVL stromy jsou **samovyvažující** binární vyhledávací stromy. Zajišťují, že rozdíl výšky levého a pravého podstromu (tzv. **balance factor**) každého uzlu je maximálně 1.
+  * To zaručuje, že operace vyhledávání, vkládání a odstraňování mají časovou složitost O(log n).
+  * Díky tomu je výška stromu vždy $O(\log n)$ a operace jsou efektivní i v nejhorším případě.
+**Rotace** se používají k vyvážení stromu po vkládání nebo mazání:
+  * **Pravá rotace (LL)** – dvě levé hrany po sobě
+  * **Levá rotace (RR)** – dvě pravé hrany po sobě
+  * **Levá-pravá rotace (LR)** – levá, pak pravá
+  * **Pravá-levá rotace (RL)** – pravá, pak levá
 === 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)**.
+  * Probíhá stejně jako v BST – AVL zajišťuje jen lepší rovnováhu.
+  * Časová složitost zůstává $O(\log n)$.
 === Vkládání ===
-  - Vložíme klíč standardně do listu BST.
+  * Nový klíč vložíme jako v BST.
-  - Cestou zpět nahoru najdeme první uzel, jehož |balance| > 1.
+  * Při návratu zpět kontrolujeme výšky podstromů.
-  - Podle rozmístění uzlů zvolíme rotaci:
+  * Pokud je rozdíl > 1, provedeme vhodnou rotaci, podle tvaru nerovnováhy.
     * **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).
+  * 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).
+  * 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.
+  * Při návratu nahoru testujeme balance; pokud je mimo interval $<-1,1>$, rotacemi balance opravíme.
-  - V nejhorším provedeme logaritmický počet rotací.
+  * V nejhorším provedeme až $O(\log n)$ 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-stromy jsou **vyvážené vyhledávací stromy**, které **nejsou binární** – uzly mohou mít více klíčů i potomků
-B-strom je parametrizován **minimálním stupněm _t_ (t ≥ 2)**:
+  * prakticky používá v databázových systémech a souborových systémech.
-  * 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-strom je řízen parametrem **minimální stupeň $t$ ($t \ge 2$)**:
+  * Každý uzel (kromě kořene) má alespoň $\lfloor t/2 \rfloor$ a nejvýše $2t$ klíčů.
+  * 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íčů.
 B-stromy umožňují efektivní vyhledávání, vkládání a odstraňování uzlů. Mají tyto vlastnosti:
@@ Line 458: / Line 493: @@
   * 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.
+{{:statnice:bakalar:pasted:20250608-122910.png}}
 === 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ň).
+  * V každém uzlu binárně vyhledáme správný interval a pokračujeme do příslušného potomka.
+  * Díky větší větvenosti je výška malá – složitost $O(\log_t n)$.
 === Vkládání ===
-  - Vložíme klíč do příslušného listu.
+  * Klíč vkládáme do správné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 uzel překročí $2t$ klíčů:
-  - Pokud přeteče i rodič, postup opakujeme až ke kořeni; ten může vyrůst.
+    * Rozdělíme ho na dvě části.
+    * Prostřední klíč přesuneme do rodiče.
+    * Pokud přeteče i rodič, opakujeme postup až ke kořeni.
+→ Kořen se může rozdělit – tím se strom **zvýší o úroveň**.
 === Mazání ===
-  - Po odstranění klíče může uzel podteknout (< t-1 klíčů).
+  * Pokud uzel klesne pod $\lfloor t/2 \rfloor$ klíčů, musíme situaci opravit:
-  - **Borrow**: vypůjčíme klíč od sourozence se ≥ t klíči.
+    * **Borrow** – vypůjčíme si klíč od sourozence.
-  - **Merge**: jinak sloučíme uzel se sourozencem a stáhneme klíč z rodiče.
+    * **Merge** – sloučíme uzel se sourozencem a jeden klíč stáhneme z rodiče.
-  - Pokud kořen zůstane prázdný, strom se zmenší o úroveň.
+  * Pokud se vyprázdní kořen, strom se **zmenší o úroveň**.
-===== Algoritmy řazení =====
+→ Všechny listy B-stromu jsou vždy na stejné úrovni – struktura je přirozeně vyvážená.
+==== Srovnání stromů ====
+| Operace | BST (nevyvážený) | AVL | B-strom |
+|---------|------------------|-----|---------|
+| Vyhledávání | $O(n)$ | $O(\log n)$ | $O(\log n)$ |
+| Vkládání | $O(n)$ | $\Theta(\log n)$ | $\Theta(\log n)$ |
+| Mazání   | $O(n)$ | $\Theta(\log n)$ | $\Theta(\log n)$ |
+| Vyváženost | ne | ano | ano |
+===== 5. Algoritmy řazení =====
   * Insert Sort, Selection Sort, Bubble Sort, QuickSort, Merge Sort, Halda, Heap Sort, Radix Sort, Counting Sort.
 ==== Insert Sort ====
+Řadíme postupně – začínáme druhým prvkem v poli a vkládáme ho na správné místo do již seřazené části vlevo. Tímto způsobem postupně "rozšiřujeme" seřazenou oblast.
+  * Jednoduchý, intuitivní a stabilní algoritmus.
+  * Vhodný pro malá pole nebo téměř seřazené vstupy.
+  * Nejlepší případ (již seřazeno): $O(n)$, jinak $O(n^2)$
+  * In-place (nepotřebuje další paměť)
 {{https://upload.wikimedia.org/wikipedia/commons/2/24/Sorting_insertion_sort_anim.gif?200}}
+<code python>
+# Insertion Sort
+def insertion_sort(arr):
+    for i in range(1, len(arr)):
+        key = arr[i]
+        j = i - 1
+        while j >= 0 and arr[j] > key:
+            arr[j + 1] = arr[j]
+            j -= 1
+        arr[j + 1] = key
+    return arr
+</code>
 ==== Selection Sort ====
+V každé iteraci najdeme nejmenší prvek z neseřazené části a vyměníme ho s prvkem na aktuální pozici. Tímto způsobem posunujeme nejmenší prvky na začátek.
+  * Snadná implementace, ale **nestabilní**.
+  * Malý počet přepisů (výměn).
+  * Vždy $O(n^2)$, nezávisle na vstupu.
+  * In-place, ale obecně neefektivní.
 {{https://upload.wikimedia.org/wikipedia/commons/3/3e/Sorting_selection_sort_anim.gif?200}}
+<code python>
+# Selection Sort
+def selection_sort(arr):
+    for i in range(len(arr)):
+        min_idx = i
+        for j in range(i + 1, len(arr)):
+            if arr[j] < arr[min_idx]:
+                min_idx = j
+        arr[i], arr[min_idx] = arr[min_idx], arr[i]
+    return arr
+</code>
 ==== Bubble Sort ====
-Bubble sort postupně prohazuje prvky sousedních dvojic, dokud není pole seřazeno.
+Postupně procházíme pole a porovnáváme sousední prvky. Pokud jsou v nesprávném pořadí, prohodíme je. Největší prvek tak "bublá" směrem doprava.
-Asymptotická složitost je $O(n^2)$.
+  * Stabilní a velmi jednoduchý algoritmus.
+  * Nevhodný pro velké množiny – vždy $O(n^2)$.
+  * In-place; snadná optimalizace pomocí flagu "swapped".
 {{https://upload.wikimedia.org/wikipedia/commons/5/54/Sorting_bubblesort_anim.gif?200}}
-<codedoc code:python>
+<code python>
+# Bubble Sort
 def bubble_sort(arr):
-  for n in range(len(arr) - 1, 0, -1):
+    for n in range(len(arr) - 1, 0, -1):
-    swapped = False
+        swapped = False
+        for i in range(n):
-    for i in range(n):
+            if arr[i] > arr[i + 1]:
-      if arr[i] > arr[i + 1]:
+                arr[i], arr[i + 1] = arr[i + 1], arr[i]
-        arr[i], arr[i + 1] = arr[i + 1], arr[i]
+                swapped = True
+        if not swapped:
-        swapped = True
+            break
+    return arr
-      if not swapped:
+</code>
-        break
-  return arr
-</codedoc>
 ==== QuickSort ====
+Vysoce efektivní algoritmus typu "rozděl a panuj". Vybereme prvek jako pivot, rozdělíme pole na dvě části (menší a větší než pivot) a rekurzivně řadíme každou část.
+  * Průměrně $O(n \log n)$, ale nejhorší případ $O(n^2)$ (např. již seřazené pole a špatně zvolený pivot).
+  * Nestabilní, ale rychlý v praxi.
+  * In-place, obvykle používá rekurzi.
 {{https://upload.wikimedia.org/wikipedia/commons/6/6a/Sorting_quicksort_anim.gif?200}}
+<code python>
+# QuickSort
+def quicksort(arr):
+    if len(arr) <= 1:
+        return arr
+    pivot = arr[0]
+    less = [x for x in arr[1:] if x < pivot]
+    greater_eq = [x for x in arr[1:] if x >= pivot]
+    return quicksort(less) + [pivot] + quicksort(greater_eq)
+</code>
 ==== Merge Sort ====
+Rozdělíme pole na poloviny, každou rekurzivně seřadíme a pak sloučíme do jednoho seřazeného celku. Při slévání porovnáváme vždy první prvek obou podpolí.
+  * Stabilní algoritmus s garantovanou složitostí $O(n \log n)$.
+  * Vyžaduje pomocnou paměť pro slévání (není in-place).
+  * Vhodný i pro externí řazení (např. řazení souborů na disku).
 {{https://upload.wikimedia.org/wikipedia/commons/c/c5/Merge_sort_animation2.gif?200}}
+<code python>
+# Merge Sort
+def merge_sort(arr):
+    if len(arr) <= 1:
+        return arr
+    mid = len(arr) // 2
+    left = merge_sort(arr[:mid])
+    right = merge_sort(arr[mid:])
+    return merge(left, right)
+def merge(left, right):
+    result = []
+    i = j = 0
+    while i < len(left) and j < len(right):
+        if left[i] <= right[j]:
+            result.append(left[i])
+            i += 1
+        else:
+            result.append(right[j])
+            j += 1
+    result.extend(left[i:])
+    result.extend(right[j:])
+    return result
+</code>
 ==== Heap Sort ====
+Vytvoříme haldu z pole (max-heap nebo min-heap), a opakovaně vyjímáme kořen (největší/nejmenší) a přesouváme ho na konec pole. Po každém vyjmutí haldu opravíme.
+  * Nestabilní, ale garantuje $O(n \log n)$ složitost.
+  * In-place – nepotřebuje pomocnou paměť.
+  * Využívá binární haldu; není tak rychlý jako QuickSort, ale má konzistentní výkon.
 {{https://upload.wikimedia.org/wikipedia/commons/1/1b/Sorting_heapsort_anim.gif?200}}
+<code python>
+# Heap Sort
+def heapify(arr, n, i):
+    largest = i
+    l = 2 * i + 1
+    r = 2 * i + 2
+    if l < n and arr[l] > arr[largest]:
+        largest = l
+    if r < n and arr[r] > arr[largest]:
+        largest = r
+    if largest != i:
+        arr[i], arr[largest] = arr[largest], arr[i]
+        heapify(arr, n, largest)
+def heap_sort(arr):
+    n = len(arr)
+    for i in range(n // 2 - 1, -1, -1):
+        heapify(arr, n, i)
+    for i in range(n - 1, 0, -1):
+        arr[0], arr[i] = arr[i], arr[0]
+        heapify(arr, i, 0)
+    return arr
+</code>
 ==== Radix Sort ====
+Řadí čísla nebo řetězce po cifrách (např. nejprve podle jednotek, pak desítek…). Používá stabilní řadicí algoritmus jako Counting Sort pro každou cifru.
+  * Stabilní, lineární: $O(n \cdot k)$, kde $k$ je počet číslic/znaků.
+  * Vhodný pro řetězce nebo celá čísla s pevnou délkou.
+  * Používá se např. u PSČ, osobních čísel apod.
+<code python>
+# Radix Sort
+def counting_sort_by_digit(arr, exp):
+    n = len(arr)
+    output = [0] * n
+    count = [0] * 10
+    for i in range(n):
+        index = (arr[i] // exp) % 10
+        count[index] += 1
+    for i in range(1, 10):
+        count[i] += count[i - 1]
+    for i in reversed(range(n)):
+        index = (arr[i] // exp) % 10
+        output[count[index] - 1] = arr[i]
+        count[index] -= 1
+    return output
+def radix_sort(arr):
+    if not arr:
+        return []
+    max_val = max(arr)
+    exp = 1
+    while max_val // exp > 0:
+        arr = counting_sort_by_digit(arr, exp)
+        exp *= 10
+    return arr
+</code>
 ==== 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í.
+Nevyužívá porovnávání, ale frekvenční pole. Nejdříve určíme maximální hodnotu v poli. Tu použijeme pro inicializaci pomocného pole, které bude mít velikost max + 1. Po té na každý index pomocného pole uložíme počet výskytu jednotlivých hodnot (postupně procházímme původní pole a přičteme 1). Pak kumulativně přičteme ke každé hodnotě hodnotu zprava. Výsledek nám dává počáteční index, odkud začíná číslo. https://www.youtube.com/watch?v=OKd534EWcdk. Funguje pouze pro celočíselné hodnoty v omezeném rozsahu.
-Funguje pouze pro malý počet řazených symbolů.
+  * Stabilní, velmi rychlý: $O(n + k)$ (k … rozsah hodnot)
+  * Není in-place, vyžaduje pomocná pole.
+  * Vhodný pro velké vstupy s malým rozptylem hodnot.
 {{https://upload.wikimedia.org/wikipedia/commons/6/60/Counting_Sort_Animation.gif?200}}
-<codedoc code:python>
+<code python>
-def countingSort(arr):
+# Counting Sort
-  max_val = max(arr)
+def counting_sort(arr):
-  count = [0] * (max_val + 1)
+    if not arr:
+        return []
+    max_val = max(arr)
+    count = [0] * (max_val + 1)
+    for num in arr:
+        count[num] += 1
+    output = []
+    for i in range(len(count)):
+        output.extend([i] * count[i])
+    return output
+</code>
-  while len(arr) > 0:
+==== Shrnutí složitostí a vlastností ====
-    num = arr.pop(0)
-    count[num] += 1
-  arr = []
+| Algoritmus      | Průměrná složitost | Stabilní | In-place | Vhodné použití                  |
-  for i in range(len(count)):
+|------------------|--------------------|----------|----------|---------------------------------|
-    arr += [i] * count[i]
+| Insert Sort      | $O(n^2)$           | Ano      | Ano      | Malé nebo téměř seřazené pole   |
+| Selection Sort   | $O(n^2)$           | Ne       | Ano      | Výuka, málo pohybů              |
+| Bubble Sort      | $O(n^2)$           | Ano      | Ano      | Jednoduchá implementace         |
+| QuickSort        | $O(n \log n)$      | Ne       | Ano      | Prakticky nejrychlejší          |
+| Merge Sort       | $O(n \log n)$      | Ano      | Ne       | Stabilita, externí řazení       |
+| Heap Sort        | $O(n \log n)$      | Ne       | Ano      | Stabilní výkon, bez rekurze     |
+| Counting Sort    | $O(n + k)$         | Ano      | Ne       | Hodně opakujících se čísel      |
+| Radix Sort       | $O(n \cdot k)$     | Ano      | Ne       | Řetězce/čísla s omezenou délkou |
-  return arr
+→ **Stabilita** znamená, že prvky se stejnou hodnotou zůstávají ve stejném pořadí jako na vstupu.
-</codedoc>
+===== 6. Dynamické programování =====
-===== 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ů
+  * 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) =====
-<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):
     m = len(X)
@@ Line 562: / Line 787: @@
     # Vytvoření DP tabulky s nulami (m+1 x n+1)
     dp = [[0]*(n+1) for _ in range(m+1)]
     # Naplnění tabulky
     for i in range(1, m+1):
@@ Line 570: / Line 795: @@
             else:
                 dp[i][j] = max(dp[i-1][j], dp[i][j-1])
     # Rekonstrukce LCS z tabulky
     i, j = m, n
@@ Line 584: / Line 809: @@
             j -= 1
     return ''.join(reversed(result))
-```
+</code>
 **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 |
 |---|---|---|---|---|---|---|---|---|
@@ Line 599: / Line 826: @@
 | 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í.
-  * 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)$.
 ==== 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…).
   * 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ů.
@@ Line 626: / Line 862: @@
   * 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).
+  * Deduplikace 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.
+  * 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 ===
-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.
-  * 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.
   * Potenciálně vyšší režie alokátorů při častém vkládání.
-Složitost
+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.
+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
     * nenajdeme klíč  (nalezen) nebo nenarazíme na prázdné políčko  (klíč tam není).
@@ Line 684: / Line 918: @@
   * $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.
+    * musí být nesoudělný s $n$, aby prohlídka pokryla celé pole.
 Algoritmus sondování
@@ Line 705: / Line 939: @@
   * 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
+  * 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
@@ Line 728: / Line 968: @@
 === 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 739: / Line 978: @@
 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
   * 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:

Differences

Search

Navigation

Print/export

Tools

QR Code