ADS: kartičky | algoritmy-datove-struktury1

Cviko

stránka předmětu – budou tam informace, možná i video

Cviko

otázka

máme vajíčko, které se z nějaké výšky rozbije, z menší ne
máme diskrétní výšky, máme k vajíček, chceme minimalizovat počet pokusů
nerozbitá vajíčka umíme sbírat
řešíme pro k vajíček
hledáme minimální počet pokusů – nevadí, že rozbijeme všechna vajíčka, pokud známe řešení
odpověď
- s jedním vajíčkem musíme postupně zespodu
- hledáme f(v,h) … počet pokusů
  - kde v je počet vajíček
  - h je počet různých výšek
  - to je špatné řešení, funkce by se snadno komprimovala
- správné f(v,p) … # výšek
  - hledáme rekurenci
  - $f(v,p)=f(v,p-1)+f(v-1,p-1)$ $f (v, p) = f (v, p - 1) + f (v - 1, p - 1)$
    - buď se vajíčko rozbilo, nebo se nerozbilo
  - $f(v,0)=1$
  - $f(0,p)=1$
  - Pascalův trojúhelník
  - tabulka, jednička podél obou okrajů, takže to není přímo Pascalův trojúhelník
  - $f=\sum_{i=0}^v{p\choose i}$

Cviko

AVL strom

pro každý vrchol: maximální hloubka pravého podstromu se od levého liší o jedna
n je počet vrcholů, jaká je nejvyšší hloubka? (nejhorší strom)
budeme počítat obráceně
hledáme minimální počet vrcholů pro danou výšku
- $A(h)$ … minimální počet vrcholů
původní funkce je schodovitá
- nová funkce nám vyjadřuje, kde jsou ty schody
když chceme co nejhlubší, tak bude jeden podstrom o jedna menší
$A(h)=A(n-1)+A(n-2)+1$
$F(h)=F(h-1)+F(h-2)$ … Fibonacciho posloupnost
$B(h)=A(h)+1=A(h-1)+A(h-2)+1+1=B(h-1)+B(h-2)$
$A(h)=B(h)-1$
je to posunutá Fibonacciho posloupnost

Cviko

mějme rekurenci

Cviko

obecnější master theorem

napsali jsme program, n je velikost vstupu
$t(n)=cn^\alpha\log^\beta n+t(a_1n)+t(a_2n)+\dots+t(a_kn)$
$\forall i:a_i\lt 1; a_1\geq a_2\geq \dots\geq a_k$
$n\leq n_0\quad t(n)\leq C$
rozepíšeme příklad bez logaritmu
za domácí úkol indukcí dokázat ty tři varianty https://mj.ucw.cz/vyuka/2021/ads1/