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 11:58] – [Řád růstu funkcí] 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 55: Line 55:
 → Čím „nižší“ složitost, tím lépe škáluje. Např. algoritmus s $O(n)$ zpracuje dvojnásobný vstup asi dvakrát pomaleji, ale $O(n^2)$ už čtyřikrát. → Čím „nižší“ složitost, tím lépe škáluje. Např. algoritmus s $O(n)$ zpracuje dvojnásobný vstup asi dvakrát pomaleji, ale $O(n^2)$ už čtyřikrát.
  
-=== Mistrovská věta === +===== 2. Rekurze ===== 
-Používá se pro řešení rekurentních rovnic u "rozděl a panuj" algoritmů.+  * Stromy, binární stromy, prohledávání s návratem
  
-Formát rekurze:   +==== Stromy ==== 
-$T(n) = a \cdot T(n / b) + f(n)$   +Strom je základní datová struktura, která se skládá z kořene, uzlů a listů. Používá se pro uchovávání hierarchických dat, jako jsou například složky v počítači nebo organizační struktury.
-  * kde: +
-    * $a \geq 1$ – počet podproblémů +
-    * $b > 1$ – zmenšovací faktor +
-    * $f(n)$ – čas potřebný mimo rekurzi+
  
-**Tři případy:** +  * Kořen je výchozí uzel stromu – ten, který nemá žádného rodiče. 
-  * $f(n) \in O(n^{\log_b a - \varepsilon})$ ⇒ $T(n) \in \Theta(n^{\log_b a})$ +  * Uzel je obecně jakýkoliv prvek stromu. Může mít žádného, jednoho nebo více potomků. 
-  * $f(n) \in \Theta(n^{\log_b a})$ ⇒ $T(n) \in \Theta(n^{\log_b a} \cdot \log n)$ +  * List je uzel, který nemá žádné potomky. Často představuje koncový bod datové struktury.
-  * $f(n) \in \Omega(n^{\log_b a + \varepsilon})$ a navíc $a \cdot f(n/b) \leq c \cdot f(n)$ pro $c < 1$ ⇒ $T(n) \in \Theta(f(n))$+
  
-→ Pomocí této věty umíme rychle určit časovou složitost některých rekurzivních algoritmů bez nutnosti řešit celou rekurentní rovnici ručně.+Strom je speciálním případem grafu – je to souvislý, neorientovaný graf bez cyklů, ve kterém mezi každými dvěma uzly existuje právě jedna cesta.
  
-**Příklad:**   +  * Vždy platí, že strom s $n$ uzly má přesně $n - 1$ hran. 
-  * MergeSort: $T(n) = 2T(n/2) + \Theta(n)$   +  * Hloubka stromu je délka nejdelší cesty od kořene k některému listu. Ukazuje, jak „vysoký“ strom je.
-  * $a = 2$, $b = 2$, $\log_b a = 1$  +
-  * druhý případ ⇒ $T(n) \in \Theta(n \log n)$+
  
-=== Substituční metoda === +V informatice se často používá tzv. kořenový strom, což je strom, kde začínáme právě od jednoho výchozího kořenového uzlu.
-Používá se k důkazu složitosti pomocí matematické indukce.+
  
-**Postup:** +  * Stromy tedy nejsou jen teoretická struktura – často se s nimi setkáváme i při běžné práci s daty nebo při návrhu algoritmů.
-  * odhadni tvar řešení $T(n) \in O(g(n))$ +
-  * dokaž indukcí+
  
-**Příklad:**   +==== Binární stromy ==== 
-$T(n) = 2T(n/2) + n$ → odhad $T(n) \in O(n \log n)$  +Binární strom je strom, kde každý uzel má maximálně dva potomky. Tito potomci se obvykle nazývají levý a pravý. Tato jednoduchá struktura je ale velmi výkonná a často používaná.
  
-**Indukční krok:** +  * Binární vyhledávací strom (BST) je binární strom s uspořádanými hodnotami – pro každý uzel platí: 
-$$ +    * hodnota v levém podstromu je menší než hodnota v uzlu, 
-T(n) \leq 2 \cdot c \cdot \frac{n}{2} \log \frac{n}{2} + n = c \cdot n \log n - c \cdot n + n +    * hodnota v pravém podstromu je větší než hodnota v uzlu.
-$$ +
-Volbou $c \geq 1$ dostáváme $T(n) \leq c \cdot n \log n$+
  
-→ Vhodné, když máme dobrý odhad složitosti a chceme ho formálně dokázat.+  * Vyvážené BST (např. AVL stromy nebo červeno-černé stromy) udržují výšku stromu malou, obvykle logaritmickou, což zajišťuje rychlé operace jako vyhledávání, vkládání a mazání.
  
-=== Rekurzivní strom === +**Reprezentace v jazyce C:** 
-Nakreslíme strom rekurzí a spočítáme náklady na každé úrovni.+<code cpp> 
 +typedef struct node { 
 +    int data; 
 +    struct node *left; 
 +    struct node *right; 
 +} Node; 
 +</code>
  
-**Příklad:**   +  * Ve většině případů se binární stromy implementují pomocí dynamických struktur – tedy uzly spojované pomocí ukazatelů. Alternativně lze binární strom uložit i jako pole (například v algoritmu heapsort).
-$T(n) = 3T(n/4) + n$+
  
-První úroveň: $n$   +=== Využití === 
-Druhá: $3 \cdot (n/4) = 3n/4$   +Stromy se široce využívají k reprezentaci hierarchických informací: 
-Třetí: $9 \cdot (n/16) = 9n/16$  +  * souborové systémy (adresáře a soubory), 
 +  * organizační struktury firem, 
 +  * výrazy v programovacích jazycích (každý uzel je operace, potomci jsou operandy), 
 +  * datové struktury jako haldy, binární vyhledávací stromy a rozhodovací stromy.
  
-Součet geometrické řady:   +Také se využívají k realizaci algoritmů, např. při prohledávání, řazení nebo optimalizaci.
-$$ +
-T(n) = n \cdot \left(1 + \frac{3}{4} + \left(\frac{3}{4}\right)^2 + \dots \right) = n \cdot \frac{1}{1 - 3/4} = 4n +
-$$   +
-⇒ $T(n) \in O(n)$+
  
-→ Metoda užitečná pro vizuální intuici. Lze jednoduše pochopit, jak přispívají jednotlivé úrovně rekurze k celkové složitosti.+==== Procházení stromem ==== 
 +Jednou z nejčastějších operací nad stromy je jejich průchod – tedy návštěva všech uzlů. Nejčastěji se k tomu používá rekurze.
  
-===== Rekurze ===== +Existují tři klasické způsoby průchodu binárního stromu:
-  * 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. +  * Preorder (předřazení) – nejprve navštívíme samotný uzel, poté levý podstrom a nakonec pravý podstrom. 
 +  * Inorder (meziřazení) – nejprve levý podstrom, pak uzel a nakonec pravý podstrom. 
 +  * Postorder (pořadí) – nejprve levý podstrom, potom pravý podstrom a až nakonec samotný uzel.
  
 +  * Především inorder je velmi důležitý pro binární vyhledávací stromy – tento způsob průchodu totiž dává prvky seřazené podle velikosti.
  
-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. +==== Rekurze ==== 
-Binární vyhledávací strom (BST) je binární strom, ve kterém pro každý uzel platí: +Rekurze je programovací technika, kdy funkce volá sama sebe, aby vyřešila menší instanci téhož problému. Je velmi vhodná pro strukturované problémy – jako jsou stromy nebo dělení na menší části.
-  * 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ů.+Důležitou podmínkou každé rekurze je tzv. **ukončovací podmínka**, která zabrání nekonečnému volání – tedy přetečení zásobníku.
  
-Reprezentace v C: +Rekurze se typicky používá v technice **rozděl a panuj**: 
-<markdown> +  * Problém se rozdělí na několik menších podobných částí. 
-```c +  * Tyto části se řeší samostatně, opět rekurzivně. 
-typedef struct node { +  * Výsledky se nakonec spojí do finálního řešení.
-    int data; +
-    struct node *left; +
-    struct node *right; +
-} Node; +
-``` +
-</markdown>+
  
-=== Využití === +**Příklady využití rekurze:** 
-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.+  * třídicí algoritmy: MergeSort, QuickSort, 
 +  * výpočty: faktoriál, Fibonacciho čísla, 
 +  * algoritmy nad stromy a grafy.
  
-==== Procházení stromem ==== +==== Backtracking (prohledávání s návratem) ==== 
-Většinou se používá rekurze (funkce volající sama sebe) k procházení stromem. +Backtracking je technika, která prochází všechny možné kombinace, ale inteligentně vynechává ty, které už zjevně nevedou ke správnému řešení. Zkoušíme řešení krok za krokem a když zjistíme, že už nemůže být platné, vracíme se zpět a zkusíme jinou větev.
-=== 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. +Tato metoda je známá z problémů jako jsou $n$-dámy nebo sudoku. Umí ušetřit obrovské množství času oproti čistému brute-force.
  
-V případě stromů se rekurze používá k procházení uzlů a provádění operací na každém uzlu.  +**Aby backtracking fungoval, musí být splněno:** 
-Existují tři základní způsoby procházení binárního stromu: +  * Můžeme zkontrolovat, zda částečné řešení je zatím platné. 
-* Preorder (předřazení) – navštívíme uzel, poté levého potomka a nakonec pravého potomka. +    * Např. při $n$-queens lze i s neúplnou šachovnicí ověřit, jestli se královny neohrožují. 
-* Inorder (meziřazení) – navštívíme levého potomka, poté uzel a nakonec pravého potomka. +    * Naproti tomu při hledání hashe hesla nemůžeme říct, že je „částečně správně“. 
-* Postorder (pořadí) – navštívíme levého potomka, pravého potomka a nakonec uzel. +  * Problém má **monotónní** strukturu – když už je část řešení špatně, další volby to nespraví.
- +
-=== 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> +**Jak takový algoritmus vypadá?**
-```python +
  
 +<code python>
 def candidates(solution): def candidates(solution):
-  # Z předchozího řešení vygenerujeme další kandidáty, musí akceptovat i prázdné řešení+  # Z předchozího řešení vygenerujeme další možné volby
   ...   ...
   return candidates   return candidates
Line 185: Line 154:
  
 def remove(candidate, new_solution): def remove(candidate, new_solution):
-  # Odebrání kandidáta ze řešení+  # Odebrání kandidáta, krok zpět
   ...   ...
   return old_solution   return old_solution
  
 def is_valid(solution): def is_valid(solution):
-  # Zkontroluje zda je řešení platné+  # Ověříme platnost řešení
   ...   ...
   return True/False   return True/False
  
 def process(solution): def process(solution):
-  # zpracování řešení+  # Hotové řešení nějak zpracujeme
   print(solution)   print(solution)
  
-def back_tracking(solution):+def backtracking(solution):
   if solution is complete:   if solution is complete:
     process(solution)     process(solution)
Line 207: Line 176:
         backtracking(solution)         backtracking(solution)
         solution = remove(next, solution)         solution = remove(next, solution)
-``` +</code>
-</markdown>+
  
 +  * Použití: n-queens, sudoku, kombinatorické generování, obchodní cestující, a mnoho dalších úloh.
  
-===== Fronta, zásobník ===== +==== Mistrovská věta ==== 
-  * průchod stromem/grafem do šířky/hloubky.+Když máme rekurzivní algoritmus, chceme často zjistit jeho časovou složitost. Pokud má tvar:
  
-==== Průchod grafem do šířky ==== +$T(n) = a \cdot T(n / b) + f(n)$   
-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. +můžeme použít tzv. **mistrovskou větu**, která nám umožní složitost určit rychle – bez nutnosti řešit rekurentní rovnici ručně. 
-Jakmile BFS najde cílový uzel, tak je nalezená cesta nejkratší. Nevýhodou je vysoká paměťová náročnost.+ 
 +  * $a$ – kolik podproblémů vznikne 
 +  * $b$ – jak moc se velikost zmenší 
 +  * $f(n)$ – jak náročné je zpracování mimo rekurzi 
 + 
 +**Možnosti:** 
 +  * Pokud $f(n)$ roste pomaleji než $n^{\log_b a}$ ⇒ první případ ⇒ $T(n) \in \Theta(n^{\log_b a})$ 
 +  * Pokud $f(n) \sim n^{\log_b a}$ ⇒ druhý případ ⇒ $T(n) \in \Theta(n^{\log_b a} \cdot \log n)$ 
 +  * Pokud $f(n)$ roste rychleji a splní se ještě další podmínka ⇒ třetí případ ⇒ $T(n) \in \Theta(f(n))$ 
 + 
 +**Příklad:** 
 +  * MergeSort: $T(n) = 2T(n/2) + n$ 
 +  * $a = 2$, $b = 2$, $\log_b a = 1$ 
 +  * $f(n) = n \in \Theta(n)$ ⇒ druhý případ 
 +  * ⇒ Složitost: $T(n) \in \Theta(n \log n)$ 
 + 
 +==== Substituční metoda ==== 
 +Další způsob, jak určit časovou složitost, je tzv. substituční metoda. Používá se k **důkazu** pomocí matematické indukce. 
 + 
 +**Jak postupovat:** 
 +  * Odhadneme složitost $T(n) \in O(g(n))$ 
 +  * A pak to dokážeme indukcí 
 + 
 +**Příklad:** 
 + 
 +Odhad: $T(n) = 2T(n/2) + n \in O(n \log n)$ 
 + 
 +Pak dokážeme, že: 
 +$$ 
 +T(n) \leq 2 \cdot c \cdot \frac{n}{2} \log \frac{n}{2} + n = c \cdot n \log n - c \cdot n + n 
 +$$ 
 +Stačí zvolit vhodnou konstantu $c$ a dostaneme požadovanou nerovnost. 
 + 
 +  * Tato metoda je užitečná, když máme podezření na složitost, ale chceme ji formálně potvrdit. 
 + 
 +==== Rekurzivní strom ==== 
 +Tato metoda spočívá v tom, že si celý průběh rekurze nakreslíme jako strom a sečteme náklady na všech úrovních. 
 + 
 +**Příklad:** 
 +$T(n) = 3T(n/4) + n$ 
 + 
 +  * První úroveň: $n$ 
 +  * Druhá úroveň: $3 \cdot (n/4) = 3n/4$ 
 +  * Třetí úroveň: $9 \cdot (n/16) = 9n/16$ 
 + 
 +To je geometrická řada: 
 +$$ 
 +T(n) = n \cdot \left(1 + \frac{3}{4} + \left(\frac{3}{4}\right)^2 + \dots \right) = n \cdot \frac{1}{1 - 3/4} = 4n 
 +$$ 
 + 
 +⇒ Celková složitost $T(n) \in O(n)$ 
 + 
 +  * Tato metoda dává pěknou vizuální představu o tom, kde se v rekurzivním algoritmu dělá nejvíc práce. 
 + 
 +==== Shrnutí ==== 
 +  * Stromy jsou skvělým nástrojem pro reprezentaci strukturovaných dat – ať už jde o soubory, výrazy nebo organizační grafy. 
 +  * Rekurze nám umožňuje přirozeně řešit problémy, které se skládají ze stejných menších částí. 
 +  * Backtracking umí efektivně procházet kombinace a omezit výpočet jen na ty smysluplné. 
 +  * Mistrovská věta a ostatní metody (substituce, rekurzivní strom) nám pomáhají pochopit složitost rekurzivních algoritmů bez zdlouhavých výpočtů. 
 + 
 + 
 +===== 3. Fronta, zásobník ===== 
 +  * Průchod stromem/grafem do šířky a do hloubky, využití fronty a zásobníku. 
 + 
 +==== Fronta ==== 
 +Fronta je abstraktní datová struktura, která funguje na principu **FIFO** (First In, First Out). 
 +  * Prvky se vkládají na konec a odebírají se z čela. 
 +  * Lze ji implementovat např. pomocí cyklického pole. 
 +  * Typicky se používá při procházení stromů nebo grafů do **šířky** (BFS). 
 +  * Implementace obvykle obsahuje dva ukazatele – `head` a `tail`. 
 + 
 +==== Zásobník ==== 
 +Zásobník je datová struktura s pořadím **LIFO** (Last In, First Out). 
 +  * Prvky se vkládají i odebírají z jednoho konce – z vrcholu zásobníku. 
 +  * Snadno se implementuje pomocí pole. 
 +  * Používá se např. při **rekurzi** nebo při průchodu grafu/stromu do **hloubky** (DFS). 
 + 
 +==== Průchod stromem do šířky (BFS) ==== 
 +BFS (Breadth-First Search) prochází graf po vrstvách. 
 +  * Vytvoříme prázdnou frontu a vložíme do ní kořen. 
 +  * Dokud není fronta prázdná: 
 +    * odebereme prvek z čela, 
 +    * zpracujeme ho, 
 +    * a vložíme do fronty všechny jeho potomky. 
 +  * BFS vždy najde **nejkratší cestu**, pokud existuje (počítá se počet hran). 
 +  * Nevýhodou je větší paměťová náročnost – musí uchovávat celou "vrstvu" uzlů. 
 + 
 +==== Průchod stromem do hloubky (DFS) ==== 
 +DFS (Depth-First Search) se snaží jít co nejhlouběji, než se vrátí zpět. 
 +  * Na začátku vložíme kořen na vrchol zásobníku. 
 +  * Poté opakujeme: 
 +    * odebereme vrchol, 
 +    * zpracujeme ho, 
 +    * a vložíme jeho potomky (typicky v určitém pořadí). 
 +  * DFS **nemusí najít nejkratší cestu**, ale často je **úspornější na paměť** než BFS. 
 + 
 +==== IDDFS – iterativní prohledávání do hloubky ==== 
 +IDDFS (Iterative Deepening DFS) kombinuje výhody BFS a DFS. 
 +  * Spouštíme DFS s omezením hloubky, které postupně zvyšujeme. 
 +  * Tak najdeme nejkratší řešení (jako BFS), ale spotřebujeme méně paměti (jako DFS).
  
-==== Průchod grafem do hloubky ==== +==== Průchody grafem (BFS/DFS) ==== 
-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. +Přístupy platí nejen pro stromy, ale i pro obecné grafy. 
-DFS nemusí najít nejkratší cestu, je ale méně paměťově náročný než BFS.+  * Graf můžeme reprezentovat maticí sousednosti nebo seznamem sousedů. 
 +  * Oba algoritmy mají složitost $O(|V| + |E|)$ – tj. závisí na počtu vrcholů a hran.
  
-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.+**Využití v grafech:** 
 +  * detekce souvislých komponent, 
 +  * detekce cyklů, 
 +  * hledání minimální kostry (spanning tree), 
 +  * hledání nejkratší cesty (BFS), 
 +  * topologické uspořádání (DFS).
  
 +==== Průchody binárním stromem ====
 +  * DFS (do hloubky) má několik variant, které se liší v pořadí operací:
 +    * **PreOrder** – operaci provádíme při první návštěvě uzlu.
 +    * **InOrder** – operaci provádíme po návratu z levého podstromu.
 +    * **PostOrder** – operaci provádíme po návratu z pravého podstromu.
 +  * BFS (do šířky) – prochází úrovně stromu pomocí fronty.
  
 BFS a DFS průchody pro následující graf: BFS a DFS průchody pro následující graf:
Line 337: Line 417:
 </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). +===== 4. Binární vyhledávací stromy ===== 
-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 +==== Binární vyhledávací stromy (BST) ==== 
-  * Pravá rotace +Binární vyhledávací strom je binární strom, ve kterém jsou uzly uspořádány podle hodnoty klíčů: 
-  * Levá-pravá rotace +  * Levý podstrom obsahuje pouze uzly s menším klíčem než má uzel. 
-  * Pravá-levá rotace+  * Pravý podstrom obsahuje pouze uzly s větším klíčem. 
 + 
 +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)$. 
 + 
 +=== 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í === === 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í === === 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     * **LL** – pravá rotace
     * **RR** – levá rotace     * **RR** – levá rotace
     * **LR** – levá rotace na dítěti, pak pravá rotace     * **LR** – levá rotace na dítěti, pak pravá rotace
     * **RL** – pravá rotace na dítěti, pak levá 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í === === 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 intervál $<-1,1>$, rotacemi jej opravíme. 
-  - V nejhorším provedeme logaritmický počet rotací.+  * V nejhorším provedeme až $O(\log n)$ rotací
  
 ==== B-stromy ==== ==== 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 ≥ 2)**: 
 +  * 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ů. 
 +  * 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: B-stromy umožňují efektivní vyhledávání, vkládání a odstraňování uzlů. Mají tyto vlastnosti:
Line 376: 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. 
 + 
 +{{:statnice:bakalar:pasted:20250608-122910.png}}
  
 === Vyhledávání === === 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í === === 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í === === Mazání ===
-  - Po odstranění klíče může uzel podteknout (< t-1 klíčů). +  * Pokud uzel klesne pod $floor(t/2)$ 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, Selection Sort, Bubble Sort, QuickSort, Merge Sort, Halda, Heap Sort, Radix Sort, Counting Sort.
  
 ==== Insert 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}} {{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 ==== ==== 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}} {{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 ====
-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}} {{https://upload.wikimedia.org/wikipedia/commons/5/54/Sorting_bubblesort_anim.gif?200}}
-<codedoc code:python>+ 
 +<code python> 
 +# Bubble Sort
 def bubble_sort(arr): 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 ==== ==== 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}} {{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 ==== ==== 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}} {{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 ==== ==== 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}} {{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 ==== ==== 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 ====
-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. Nejprve spočítáme výskyty všech hodnot, pak je seřadíme podle počtu. 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}} {{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.   * 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: 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 480: 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 488: 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 502: 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 517: 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 544: 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 602: 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 623: 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 646: 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 657: 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)