B4B33ALG Webové stránky předmětu

• Řád růstu funkcí – asymptotická složitost algoritmu.
• Rekurze – stromy, binární stromy, prohledávání s návratem.
• Fronta, zásobník – průchod stromem/grafem do šířky/hloubky.
• Binární vyhledávací stromy – AVL a B-stromy.
• Algoritmy řazení – Insert Sort, Selection Sort, Bubble Sort, QuickSort, Merge Sort, Halda, Heap Sort, Radix Sort, Counting Sort.
• Dynamické programování – struktura optimálního řešení, odstranění rekurze. Nejdelší společná podposloupnost, optimální násobení matic, problém batohu.
• Rozptylovací tabulky (Hashing) – hashovací funkce, řešení kolizí, otevřené a zřetězené tabulky, double hashing, srůstající tabulky, univerzální hashování.

• asymptotická složitost algoritmu.

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

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

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

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

Klasifikace dle složitosti Od nejmenší po největší složitost (k je konstanta):

• $O(1)$ – konstantní
• $O(\log(n))$ – logaritmická
• $O(n)$ – lineární
• $O(n^2)$ – kvadratická
• $O(n^3)$ – kubická
• $O(n^k)$ – polynomiální
• $O(k^n)$ – exponenciální
• $O(n!)$ – faktoriálová

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:

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

Příklad: Merge Sort: $T(n) = 2T\left(\frac{n}{2}\right) + \Theta(n)$

• $a = 2$, $b = 2$, $\log_b a = 1$
• $f(n) = \Theta(n^1)$ ⇒ Případ 2 $\rightarrow$ $T(n) \isin \Theta(n \log n)$

1. Odhadněte tvar řešení (např. $O(n \log n)$).
2. Dokažte indukcí správnost odhadu.

Příklad:

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

Dosadíme:

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

Nakreslete strom rekurz - e s náklady na každé úrovni.

1. Sečtěte náklady napříč úrovněmi.

Příklad: $T(n) = 3T\left(\frac{n}{4}\right) + n$

1. Kořen: $n$
2. 3 větve: $\frac{n}{4}$ každá
3. 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)$$

• stromy, binární stromy, prohledávání s návratem.

Datová struktura, která se skládá z kořene, uzlů a listů.

• Kořen je uzel, který nemá žádného rodiče.
• Uzel je prvek stromu, který může mít jeden nebo více potomků.
• List je uzel, který nemá žádné potomky.

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

Binární strom je strom, ve kterém každý uzel má maximálně dva potomky. Tyto potomky se nazývají levý a pravý potomek. Binární vyhledávací strom (BST) je binární strom, ve kterém pro každý uzel platí:

• hodnota levého potomka je menší než hodnota uzlu,
• hodnota pravého potomka je větší než hodnota uzlu.

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

Reprezentace v C:

typedef struct node {
    int data;
    struct node *left;
    struct node *right;
} Node;

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.

Většinou se používá rekurze (funkce volající sama sebe) k procházení stromem.

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

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

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

Backtracking 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í.

def candidates(solution):
  # Z předchozího řešení vygenerujeme další kandidáty, musí akceptovat i prázdné řešení
  ...
  return candidates
 
def add(candidate, solution):
  # Přidání kandidáta do řešení
  ...
  return new_solution
 
def remove(candidate, new_solution):
  # Odebrání kandidáta ze řešení
  ...
  return old_solution
 
def is_valid(solution):
  # Zkontroluje zda je řešení platné
  ...
  return True/False
 
def process(solution):
  # zpracování řešení
  print(solution)
 
def back_tracking(solution):
  if solution is complete:
    process(solution)
  else:
    for next in candidates(solution):
      if is_valid(next):
        solution = add(next, solution)
        backtracking(solution)
        solution = remove(next, solution)

• průchod stromem/grafem do šířky/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. Jakmile BFS najde cílový uzel, tak je nalezená cesta nejkratší. Nevýhodou je vysoká paměťová náročnost.

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

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

BFS a DFS průchody pro následující graf:

 
[1] bfs show
  class Graph:
    def __init__(self):
        self.graph = defaultdict(list)
 
    def addEdge(self, u, v):
        self.graph[u].append(v)
 
    def BFS(self, s):
        visited = [False] * (max(self.graph) + 1)
 
        queue = []
 
        queue.append(s)
        visited[s] = True
 
        while queue:
            s = queue.pop(0)
            print(s, end=“ ”)
 
            for i in self.graph[s]:
                if not visited[i]:
                    queue.append(i)
                    visited[i] = True
 
  if __name__ == '__main__':
    g = Graph()
    g.addEdge(0, 1)
    g.addEdge(0, 2)
    g.addEdge(1, 2)
    g.addEdge(2, 0)
    g.addEdge(2, 3)
    g.addEdge(3, 3)
 
    print(“Following is Breadth First Traversal” “ (starting from vertex 2)”)
    g.BFS(2)
 
    > 2 0 3 1
 
 

 


[2] dfs show
  class Graph:
 
    def __init__(self):
        self.graph = defaultdict(list)
 
    def addEdge(self, u, v):
        self.graph[u].append(v)
 
    def DFSUtil(self, v, visited):
        visited.add(v)
        print(v, end=' ')
 
        for neighbour in self.graph[v]:
            if neighbour not in visited:
                self.DFSUtil(neighbour, visited)
 
    def DFS(self, v):
        visited = set()
 
        self.DFSUtil(v, visited)
 
  if __name__ == “__main__”:
    g = Graph()
    g.addEdge(0, 1)
    g.addEdge(0, 2)
    g.addEdge(1, 2)
    g.addEdge(2, 0)
    g.addEdge(2, 3)
    g.addEdge(3, 3)
 
    print(“Following is Depth First Traversal (starting from vertex 2)”)
 
    g.DFS(2)
 
    > 2 0 1 3 
 

 

• AVL a B-stromy.

AVL stromy jsou vyvážené binární vyhledávací stromy, které zajišťují, že výška levého a pravého podstromu každého uzlu se liší maximálně o 1. To zaručuje, že operace vyhledávání, vkládání a odstraňování mají časovou složitost O(log n). AVL stromy se vyvažují pomocí rotací, které se provádějí při vkládání nebo odstraňování uzlů. Existují čtyři typy rotací:

• Levá rotace
• Pravá rotace
• Levá-pravá rotace
• Pravá-levá rotace

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

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

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

Není binární strom, ale je to vyvážený strom, který se prakticky používá v databázových systémech a souborových systémech. B-strom je parametrizován minimálním stupněm _t_ (t ≥ 2):

• každý uzel kromě kořene má alespoň $t - 1_ a nejvýše _2t - 1$ klíčů,
• z toho plyne, že vnitřní uzel má $t … 2t$ potomků.

B-stromy umožňují efektivní vyhledávání, vkládání a odstraňování uzlů. Mají tyto vlastnosti:

• Každý uzel může mít více než dva potomky.
• Všechny listy jsou na stejné úrovni.
• Každý uzel má minimální a maximální počet klíčů (viz definice $t$ výše).

Když uzel překročí maximální počet klíčů ($2t - 1$), rozdělí se na dva uzly a prostřední klíč se přesune do rodiče. Pokud rodič také překročí maximální počet klíčů, proces se opakuje až ke kořeni.

• 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ň).

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

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

• Insert Sort, Selection Sort, Bubble Sort, QuickSort, Merge Sort, Halda, Heap Sort, Radix Sort, Counting Sort.

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

def bubble_sort(arr):
  for n in range(len(arr) - 1, 0, -1):
    swapped = False  
 
    for i in range(n):
      if arr[i] > arr[i + 1]:
        arr[i], arr[i + 1] = arr[i + 1], arr[i]
 
        swapped = True
 
      if not swapped:
        break
  return arr

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

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

def countingSort(arr):
  max_val = max(arr)
  count = [0] * (max_val + 1)
 
  while len(arr) > 0:
    num = arr.pop(0)
    count[num] += 1
 
  arr = []
  for i in range(len(count)):
    arr += [i] * count[i]
 
  return arr

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

• hashovací funkce, řešení kolizí, otevřené a zřetězené tabulky, double hashing, srůstající tabulky, univerzální hashování.

• rozptylovací funkce = hashovací funkce
• Hashovací funkce přiřadí k potenciálně libovolnému množství dat hodnotu který má vždy kosntantní délku.
• Hashovací funkce v kontextu algoritmizace by měla být hlavně rychlá (narozdíl od kryptografie, kde pomalost je část bezpečnosti za hashovací funkcí) s co nejméně kolizemi (kolize - 2 různé vstupy mají stejný výstup)
• Umožňují vyhledávat v tabulkách s průměrnou časovou složitostí $O(1)$.

• Two Sum – O(n) hledání dvojice se zadaným součtem pomocí `set`.
• Dynamické programování s memoizací – ukládání $T(n)$ do hashe (Fibonacci, LCS…).
• Rolling hash (Rabin–Karp) – rychlé vyhledávání vzoru v textu.
• Longest Consecutive Sequence – O(n) řešení s `unordered_set`.
• Počty výskytů / anagramy – frekvenční slovník pro srovnání řetězců.

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

Kolize – situace, kdy dvěma různým vstupům hashovací funkce tabulky přiřadí stejný výstup.

Hashovací tabulky se používají k rychlému vyhledávání, ale protože hashovací funkce mohou mít kolize, tabulky musí umět tyto kolize řešit.

Tabulka je nejčastěji reprezentovaná polem s indexy $0 … n-1$, kde $n$ je délka pole.

Existují tři běžné způsoby řešení kolizí: zřetězený hashing, lineární sondování a double hashing.

Jak to funguje – z každého políčka vede spojený seznam (linked list).

• Vkládání – vypočítáme index $h(k)$.

Pokud políčko už obsahuje prvek, vložíme nový na *konec* jeho seznamu.

• Hledání – projdeme seznam, dokud klíč nenajdeme, nebo nedojdeme na jeho konec.
• Mazání – odstraníme uzel ze seznamu (klasická operace na linked-listu).

Výhody

• Jednoduchá implementace, žádný problém s přeplněním pole.
• Výkon se zhoršuje hladce – degraduje k $O(n)$ jen když se load-factor blíží ∞ a seznamy jsou dlouhé.

Nevýhody

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

Složitost Amortizovaně $O(1 + α)$, kde $α = m/n$ je load-factor ($m$ = počet prvků, $n$ = délka pole).

Jak to funguje – pokud je políčko z hashu obsazeno, posouváme se lineárně dál.

• Vkládání – vypočítáme index $h(k)$.

Kolize ⇒ zkusíme $(h(k)+1) \mod n$, pak $+1$… dokud nenajdeme prázdné místo.

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

Výhody

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

Nevýhody

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

Složitost Průměrně $O(1 + 1/(1-α))$; při $\alpha → 1$ roste geometricky.

Používáme dvě hashovací funkce:

• $h1(k)$ – primární index v rozsahu $0 … n-1$
• $h2(k)$ – krok (step) v rozsahu $1 … n-1$;

musí být nesoudělný s $n$, aby prohlídka pokryla celé pole.

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

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

Výhody

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

Nevýhody

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

Složitost Amortizovaně $O(1 + \alpha)$; růst počtu sond je pozvolnější než u linear probing, ale stále dramatický při $\alpha → 1$.