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/05/20 11:49] – [Kolize v hashovacích tabulkách] mistrjirkastatnice:bakalar:b4b33alg [2026/06/06 17:15] (current) – [Counting Sort] knedl1k
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 11: Line 11:
   * **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í 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í ===== +===== 1. Řád růstu funkcí ===== 
-  * asymptotická složitost algoritmu.+  * asymptotická složitost algoritmu 
 +  * slouží k odhadu doby běhu algoritmu vzhledem k velikosti vstupu
  
-===Asymptotická Složitost=== +=== Asymptotická složitost === 
- +Je způsob klasifikace algoritmů podle chování při rostoucím množství vstupních dat. Důležité pro srovnání algoritmů nezávisle na implementaci a výpočetní síle.
-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):**   **Horní asymptotický odhad (velké O):**  
-$f(n) \isin O(g(n))$   +$f(n) \in O(g(n))$   
-$f$ je shora asymptoticky ohraničená funkcí $g$ (až na konstantu).  +→ funkce $f$ je shora ohraničena funkcí $g$, až na konstantu.  
 Formálně:   Formálně:  
-$\exists c > 0, n_0 > 0: \forall n > n_0: f(n) \leq c \cdot g(n)$+$\exists c > 0, n_0 > 0 : \forall n > n_0 : f(n) \leq c \cdot g(n)$
  
 **Dolní asymptotický odhad (velká Ω):**   **Dolní asymptotický odhad (velká Ω):**  
-$f(n) \isin \Omega(g(n))$   +$f(n) \in \Omega(g(n))$   
-$f$ je zdola asymptoticky ohraničená funkcí $g$.  +→ funkce $f$ je zdola ohraničena funkcí $g$.  
 Formálně:   Formálně:  
-$\exists c > 0, n_0 > 0: \forall n > n_0: f(n) \geq c \cdot g(n)$+$\exists c > 0, n_0 > 0 : \forall n > n_0 : f(n) \geq c \cdot g(n)$
  
 **Těsný asymptotický odhad (velké Θ):**   **Těsný asymptotický odhad (velké Θ):**  
-$f(n) \isin \Theta(g(n))$   +$f(n) \in \Theta(g(n))$   
-$f$ je ohraničena funkcí $g$ **shora i zdola**.  +→ funkce $f$ je ohraničena funkcí $g$ shora i zdola.  
 Formálně:   Formálně:  
-$f(n) \isin O(g(n))$ a $f(n) \isin \Omega(g(n))$+$f(n) \in O(g(n))$ a zároveň $f(n) \in \Omega(g(n))$
  
-**Klasifikace dle složitosti**   +**Poznámka:**   
-Od nejmenší po největší složitost (k je konstanta):+Třída složitosti obsahuje všechny algoritmy s "podobným" chováním až na konstantu. 
 + 
 +→ Jinými slovy: asymptotická složitost nám říká, jak se bude algoritmus chovat pro opravdu velké vstupy. Nezáleží na detailech, implementaci nebo výkonu stroje – zajímá nás jen „trend“ růstu počtu operací. 
 + 
 +=== Klasifikace dle složitosti === 
 +Od nejmenší po největší:
   * $O(1)$ – konstantní   * $O(1)$ – konstantní
-  * $O(\log(n))$ – logaritmická+  * $O(\log n)$ – logaritmická
   * $O(n)$ – lineární   * $O(n)$ – lineární
 +  * $O(n \log n)$ – lineárně logaritmická
   * $O(n^2)$ – kvadratická   * $O(n^2)$ – kvadratická
   * $O(n^3)$ – kubická   * $O(n^3)$ – kubická
Line 47: Line 53:
   * $O(n!)$ – faktoriálová   * $O(n!)$ – faktoriálová
  
-===Mistrovská Věta=== +→ Čí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.
-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:** +===== 2. Rekurze ===== 
-  - Pokud $f(n) \isin O(n^{\log_b a - \epsilon})$ pro nějaké $\epsilon > 0$: $T(n) \isin \Theta(n^{\log_b a})$ +  * Stromy, binární stromy, prohledávání s návratem
-  - 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:**   +==== Stromy ==== 
-Merge Sort: $T(n) = 2T\left(\frac{n}{2}\right) + \Theta(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.
-  * $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=== +  * Kořen je výchozí uzel stromu – ten, který nemá žádného rodiče. 
-  - **Odhadněte tvar řešení** (např. $O(n \log n)$). +  * Uzel je obecně jakýkoliv prvek stromu. Může mít žádného, jednoho nebo více potomků. 
-  - **Dokažte indukcí** správnost odhadu.+  * List je uzel, který nemá žádné potomky. Často představuje koncový bod datové struktury.
  
-**Příklad:**   +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.
-  * 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$$  +  * Vždy platí, že strom s $n$ uzly má přesně $n - 1$ hran. 
-Volbou $c \geq 1$ platí nerovnost.+  * Hloubka stromu je délka nejdelší cesty od kořene k některému listu. Ukazuje, jak „vysoký“ strom je.
  
-===Metoda Rekurzivního Stromu=== +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.
-**Nakreslete strom rekurz  - e** s náklady na každé úrovni. +
-  - **Sečtěte náklady** napříč úrovněmi.+
  
-**Příklad:**    +  * 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ů.
-$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í stromy ==== 
 +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á.
  
 +  * 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,
 +    * hodnota v pravém podstromu je větší než hodnota v uzlu.
  
-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. +  * 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í.
-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 jazyce C:** 
- +<code cpp>
-Reprezentace v C: +
-<markdown> +
-```c+
 typedef struct node { typedef struct node {
     int data;     int data;
Line 115: Line 90:
     struct node *right;     struct node *right;
 } Node; } Node;
-``` +</code> 
-</markdown>+ 
 +  * 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).
  
 === Využití === === 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.+Stromy se široce využívají k reprezentaci hierarchických informací: 
 +  * 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. 
 + 
 +Také se využívají k realizaci algoritmů, např. při prohledávání, řazení nebo optimalizaci.
  
 ==== Procházení stromem ==== ==== Procházení stromem ====
-Většinou se používá rekurze (funkce volající sama sebe) k 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 === +
-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. +Existují tři klasické způsoby průchodu binárního stromu:
  
-V případě stromů se rekurze používá k procházení uzlů a provádění operací na každém uzlu.  +  * Preorder (předřazení) – nejprve navštívíme samotný uzel, poté levý podstrom a nakonec pravý podstrom. 
-Existují tři základní způsoby procházení binárního stromu: +  * Inorder (meziřazení) – nejprve levý podstrom, pak uzel a nakonec pravý podstrom. 
-* Preorder (předřazení) – navštívíme uzel, poté levého potomka a nakonec pravého potomka. +  * Postorder (pořadí) – nejprve levý podstrom, potom pravý podstrom a až nakonec samotný uzel.
-* 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) === +  * 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.
-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:** +==== Rekurze ==== 
-  * Dá se zkontrolovat platnost nekompletního řešení: +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. 
-    * 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. +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. 
-  * Problém musí mít monotónní omezení: jakmile část řešení nevyhovuje, žádný další krok ji už nespraví. + 
-     +Rekurze se typicky používá v technice **rozděl a panuj**: 
-**Jak funguje?** +  * Problém se rozdělí na několik menších podobných částí. 
-Musíme mít způsob jak generovat částečná řešení. +  * Tyto části se řeší samostatně, opět rekurzivně. 
 +  * Výsledky se nakonec spojí do finálního řešení. 
 + 
 +**Příklady využití rekurze:** 
 +  * třídicí algoritmy: MergeSort, QuickSort, 
 +  * výpočty: faktoriál, Fibonacciho čísla, 
 +  * algoritmy nad stromy a grafy. 
 + 
 +==== Backtracking (prohledávání s návratem) ==== 
 +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. 
 + 
 +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. 
 + 
 +**Aby backtracking fungoval, musí být splněno:** 
 +  * Můžeme zkontrolovat, zda částečné řešení je zatím platné. 
 +    * Např. při $n$-queens lze i s neúplnou šachovnicí ověřit, jestli se královny neohrožují. 
 +    * Naproti tomu při hledání hashe hesla nemůžeme říct, že je „částečně správně“. 
 +  * Problém má **monotónní** strukturu – když už je část řešení špatně, další volby to nespraví.
  
-<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 161: 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 183: 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. 
 + 
 +==== Mistrovská věta ==== 
 +Když máme rekurzivní algoritmus, chceme často zjistit jeho časovou složitost. Pokud má tvar: 
 + 
 +$T(n) = a \cdot T(n / b) + f(n)$   
 +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ě. 
 + 
 +  * $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ů.
  
-===== Fronta, zásobník ===== +==== Průchod stromem do hloubky (DFS) ==== 
-  * průchod stromem/grafem do šířky/hloubky.+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.
  
-==== Průchod grafem do šířky ==== +==== IDDFS – iterativní prohledávání do hloubky ==== 
-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. +IDDFS (Iterative Deepening DFS) kombinuje výhody BFS a DFS. 
-Jakmile BFS najde cílový uzel, tak je nalezená cesta nejkratší. Nevýhodou je vysoká paměťová náročnost.+  * 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 313: 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 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 ==== ==== 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: B-stromy umožňují efektivní vyhledávání, vkládání a odstraňování uzlů. Mají tyto vlastnosti:
Line 352: 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 $\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ň**. 
 + 
 +→ 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 | 
  
-===== Algoritmy řazení =====+===== 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. 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}} {{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:
 +  * 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ů.
  
 +===== Dynamické programování pro Nejdelší Společnou Posloupnost (LCS) =====
 +  * Mějme dvě posloupnosti písmen a chceme najít nejdelší společnou podposloupnost.
 +  * Například u posloupností {BDCABA} a {ABCBDAB} je řešení {BCBA}.
 +  * Časová složitost: $O(m \cdot n)$, kde $m$ a $n$ jsou délky řetězců.
  
 +  * **Myšlenka algoritmu:**
 +    * 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).
  
-===== Rozptylovací tabulky (Hashing) =====+  * **Pseudokód v Pythonu:** 
 +<code python> 
 +def lcs(X, Y): 
 +    m = len(X) 
 +    n = len(Y) 
 +    # 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): 
 +        for j in range(1, n+1): 
 +            if X[i-1] == Y[j-1]: 
 +                dp[i][j] = dp[i-1][j-1] + 1 
 +            else: 
 +                dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 
 + 
 +    # Rekonstrukce LCS z tabulky 
 +    i, j = m, n 
 +    result = [] 
 +    while i > 0 and j > 0: 
 +        if X[i-1] == Y[j-1]: 
 +            result.append(X[i-1]) 
 +            i -= 1 
 +            j -= 1 
 +        elif dp[i-1][j] > dp[i][j-1]: 
 +            i -= 1 
 +        else: 
 +            j -= 1 
 +    return ''.join(reversed(result)) 
 +</code> 
 + 
 +**Příklad tabulky pro `X = "BDCABA"`, `Y = "ABCBDAB"`:** 
 + 
 +Řešení: **"BCBA"** (délka 4). 
 + 
 +**Tabulka:** 
 +|   |   | A | B | C | B | D | A | B | 
 +|---|---|---|---|---|---|---|---|---| 
 +|   | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 
 +| B | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 
 +| D | 0 | 0 | 1 | 1 | 1 | 2 | 2 | 2 | 
 +| C | 0 | 0 | 1 | 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 | 
 + 
 +  * **Vysvětlení tabulky:** 
 +    * 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 postup diagonální (při shodě znaků) nebo výběr větší hodnoty z okolních buněk. 
 + 
 +  * **Složitost:** 
 +    * Naplnění tabulky: $O(m \cdot n)$ 
 +    * Rekonstrukce: $O(m + n)$ 
 +    * Celkem: $O(m \cdot n)$ 
 + 
 + 
 + 
 +===== 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 458: 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 516: 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 537: 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 560: 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 571: 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: • start • prednasky • exportbox • b4b33alg • navigation

Navigation

Playground

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