ADS

Cviko

• Vladan Majerech
• cvičení bude rychlé a náročné
• stránka předmětu – budou tam informace, možná i video
  • budou tam domácí úkoly!
  • termín je těsně před (dalším) cvičením
  • je to bez nápověd
  • po deadlinu max. poloviční počet
  • lze odevzdávat opakovaně
  • můžeme úkoly dělat napřed, většina bude stejná jako vloni
  • musíme mít dvě třetiny bodů
• 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)$
        • 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}$
• 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
• mějme rekurenci
  • $A_{n+3}=c_1A_{n+2}+c_2A_{n+1}+c_3A_n$
  • předpokládejme řešení $q^{n+3}=c_1q^{n+2}+c_2q^{n+1}+c_3q^n$
  • tedy $q^3=c_1q^2+c_2q^1+c_3q^0$
  • polynom třetího stupně má tři kořeny $q_1,q_2,q_3$
  • $\alpha_1q_1^n+\alpha_2q_2^n+\alpha_3q_3^n$
  • s komplexními kořeny není problém
  • je problém s dvojnásobnými kořeny
  • u vícenásobných kořenů hledáme kořeny stylem $q^n,q^n\cdot n,q^n{n\choose 2}$
  • rekurenci lze zapsat jinak – viz sešit
    • vlastní čísla
• 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/