1. (Vyhodnocování polynomu)
    V sekci o výpočtu hodnoty na základě předchozí jsme si ukázali, jak rychle spočítat hodnoty polynomu $P(x)=ax^2+bx+c$ ve všech bodech $x\in\{1,\dots, n\}$. Potřebovali jsme je znát například proto, abychom si nakreslili graf funkce. Ale co kdybychom si chtěli nakreslit přesnější graf funkce $P(x)$? Co kdybychom chtěli znát hodnotu $P(x)$ ve všech bodech $0, 0.1, 0.2, 0.3, \dots, n$? Jak to co nejrychleji spočítat?

  2. (Výpočet hodnoty na základě předchozí)
    Je dána posloupnost celých čísel. Délka posloupnosti není známa. Posloupnost může být i tak dlouhá, že se nevejde do paměti, ale jen na pevný disk.

    1. (Úsek posloupnosti s největším součtem)
      Nalezněte v posloupnosti souvislý úsek s největším součtem. Výstupem algoritmu bude jen hodnota největšího součtu. Například pro posloupnost $1$, $3$, $-1$, $1$, $-5$, $8$, $2$, $-3$, $4$, $-8$ bude výsledkem $11$ (to je délka úseku $8$, $2$, $-3$, $4$).

    2. (Nejdelší hladký úsek posloupnosti)
      Určete délku nejdelšího souvislého úseku, v němž se libovolná dvě čísla liší pouze o $1$. Například pro posloupnost $5$ $7$ $6$ $7$ $7$ $8$ $8$ $7$ $9$ $9$ $9$ bude výsledkem $5$ (to je délka úseku $7$ $7$ $8$ $8$ $7$).

    3. (Nejdelší $D$-hladký úsek posloupnosti)
      Určete délku nejdelšího souvislého úseku, v němž se libovolná dvě čísla liší pouze o $D$.

    Nápověda: existuje řešení s časovou složitostí $\OO(n)$.

  3. (Přímé generování výsledku)
    Množina $Q$ obsahuje pouze taková přirozená čísla, která nejsou dělitelná ani jedním z prvočísel $2$, $3$ a $5$.1 Vypište co nejrychleji $n$-té nejmenší číslo množiny $Q$.

    1. Zkusme si to nejprve zjednodušit. Co kdybychom chtěli vypsat $n$-té nejmenší přirozené číslo, které není dělitelné $2$? Je to moc jednoduché? Tak jak co nejrychleji vypsat $n$-té nejmenší přirozené číslo, které není dělitelné $2$ ani $3$?
    2. Vyřešte úlohu pro zadaná prvočísla $2$, $3$ a $5$. Umíte odpovědět v čase $\OO(1)$? Pokud ano, tak ještě dokažte, že je odpověď správně. To je, že jste žádné číslo množiny $Q$ nevynechali.
    3. Zobecněte řešení úlohy pro $k$ různých prvočísel.
  4. (Rozklad čísla na součet třetích mocnin)
    Rozložte číslo $n\in \NN$ na součet dvou třetích mocnin přirozených čísel. Jinými slovy najděte $a, b\in \NN$ splňující $n=a^3 + b^3$. Vypište všechna řešení.

    1. Někdo by mohl najít následující řešení. Procházíme všechna možná $a\in \{0,1,\dots, \lfloor\sqrt[3]{n}\rfloor\}$ a pro každé $a$ spočteme $\sqrt[3]{n-a^3}$. Pokud bude výsledek celočíselný, tak jsme nalezli řešení. Toto řešení je samozřejmě správně a má časovou složitost $\OO(\sqrt[3]{n})$.

      Zkuste ale vymyslet řešení, ve kterém budeme počítat pouze s celočíselnými proměnnými a vystačíme si se sčítáním a násobením. Dá se vymyslet řešení s časovou složitostí $\OO(\sqrt[3]{n})$.

    2. Obě řešení naprogramuje a porovnejte, jak rychle počítají pro konkrétní $n$. Vyvoďte z toho závěr, jestli je opravdu výhodnější počítat v celočíselných proměnných, nebo jestli to vyjde stejně, jako když počítáme v plovoucí čárce a navíc počítáme funkce jako je odmocnina.
  5. (Kružnice)
    Na kružnici je rozmístěno $n$ bodů. Vzdálenost dvou bodů budeme měřit po obvodu kružnice. Vzdálenosti libovolných dvou bodů jsou celočíselné. Začneme v nejvyšším bodě a body si očíslujeme čísly $1$ až $n$ po směru hodinových ručiček. Pro každé dva sousední body (v pořadí podle očíslování) dostanete jejich vzájemnou vzdálenost. Například pro kružnici s $5$ body, můžete dostat vzdálenosti $d(1,2)=1$, $d(2,3)=4$, $d(3,4)=2$, $d(4,5)=5$, $d(5,1)=2$.

    1. Rozhodněte, jestli na kružnici existují dva body takové, že jejich spojnice prochází středem kružnice. Pokud ano, tak takovou dvojici bodů vypište. V příkladu kružnice s $5$ body bychom mohli odpovědět $(1,4)$, ale také $(3,5)$, protože jejich spojnice prochází středem kružnice.
    2. Rozhodněte, jestli na kružnici existují čtyři body takové, že tvoří čtverec. Pokud ano, tak takové $4$ body vypište.

    Nápověda: Existuje řešení s časovou složitostí $\OO(n)$.

  6. (Fibonacciho čísla přes mocnění matic)
    Fibonacciho čísla jsou $0$, $1$, $1$, $2$, $3$, $5$, $8$, \dots Jsou definovány rekurencí $F_0=0$, $F_1=1$ a $F_n = F_{n-1} + F_{n-2}$ pro $n \geq 2$. Rovnost $F_1 = F_1$ a $F_2 := F_1 + F_0$ můžeme zapsat i pomocí matice:

    $$ \left(\begin{matrix}
    F_1\\
    F_2
    \end{matrix}\right) = \left(\begin{matrix}
    0 & 1 \\
    1 & 1
    \end{matrix}\right) \cdot
    \left(\begin{matrix}
    F_0 \\
    F_1
    \end{matrix}\right) .$$ Podobně

    $$ \left(\begin{matrix}
    F_2\\
    F_3
    \end{matrix}\right) = \left(\begin{matrix}
    0 & 1 \\
    1 & 1
    \end{matrix}\right) \cdot
    \left(\begin{matrix}
    F_1 \\
    F_2
    \end{matrix}\right) = \left(\begin{matrix}
    0 & 1 \\
    1 & 1
    \end{matrix}\right)^2 \cdot
    \left(\begin{matrix}
    F_0 \\
    F_1
    \end{matrix}\right)$$

    až zobecněním dostaneme $$ \left(\begin{matrix}
    F_n\\
    F_{n+1}
    \end{matrix}\right) = \left(\begin{matrix}
    0 & 1 \\
    1 & 1
    \end{matrix}\right)^n \cdot
    \left(\begin{matrix}
    F_0 \\
    F_1
    \end{matrix}\right) .$$

    Označme tuto matici tvaru $2 \times 2$ jako $A$. Pro výpočet $n$-tého Fibonacciho čísla tedy stačí vymyslet, jak se dá rychle spočítat $n$-tá mocnina matice $A$.

    1. Ukažte, že $n$-tá mocnina libovolné matice $B$ velikosti $2\times 2$ se dá spočítat v čase $\OO(\log n)$.

      Nápověda: Zamyslete se nad tím, jak byste počítali $B^2$, $B^4$, $B^8$.

    2. Jak rychle dokážete spočítat číslo $X_n$, které je určeno následující rekurencí: $X_0 = a$, $X_1 = b$, $X_2 = c$ a $X_n = dX_{n-1} + eX_{n-2} + fX_{n-3}$ pro $n\geq 3$. Čísla $a$, $b$, $c$, $d$, $e$, $f$ jsou pevně dané konstanty.
    3. Fibonacciho čísla se dají spočítat i podle následujícího vzorce: $$ F_n = \frac{1}{\sqrt{5}} \left( \frac{1+\sqrt{5}}{2} \right)^n – \frac{1}{\sqrt{5}} \left( \frac{1-\sqrt{5}}{2} \right)^n$$ Ukažte, jak tento vzorec souvisí s vlastními čísly matice $A$.

      Nebylo by rychlejší počítat Fibonacciho čísla přímo z tohoto vzorce než přes mocnění matic? Nebylo. Čísla ve vzorci jsou iracionální a jejich výpočet s dostatečnou přesností by byl stejně pracný jako mocnění matic. Vyzkoušejte si to naprogramovat.2

      Nápověda: Jaká jsou vlastní čísla matice $A$?

      Poznámka: Když si vzorec vyčíslíte, tak zjistíte, že $F_n$ je přibližně $ 0,44 \cdot (1,61^n+(-0,61)^n)$. Proto můžeme $F_n$ počítat jen jako $0,44 \cdot 1,61^n$ a výsledek zaokrouhlit na nejbližší celé číslo.

  7. (Počítání prvních $n$ prvočísel)
    Napište program, který vypíše na obrazovku prvních $N:=1000$ prvočísel. U každého přístupu odhadněte časovou složitost.

    1. Procházejte postupně čísla $1$, $2$, $3$,\dots (procházení kandidátů) a aktuálně testované číslo $k$ zkoušejte dělit všemi čísly $2$,$3$,\dots,$\sqrt k$ (testování prvočíselnosti).
    2. Jak můžeme předchozí výpočet zrychlit? Ukládejte si nalezená prvočísla do paměti a při testování prvočíselnosti zkoušejte dělit testované číslo $k$ pouze dosud nalezenými prvočísly.
    3. Jak to urychlit ještě více? Můžeme předem zamítnout některé kandidáty. Například všechna sudá čísla kromě $2$ určitě nebudou prvočísly. Jak se dají rychle generovat kandidáti, kteří nejsou dělitelní $2$ ani $3$?

    Pro odhad časové složitosti se vám bude hodit vědět, že počet prvočísel menších než $n$ je $\pi(n) \approx n/\ln n$.

  8. (Největší společná podmatice)
    Dostaneme dvě matice $A$ a $B$ obsahující přirozená čísla.

    1. (největší společná podmatice ležící na stejné pozici) Předpokládejte, že obě matice mají stejnou velikost $n\times m$. Najděte největší obdélník určený levým horním a pravým dolním rohem takový, aby podmatice matic $A$ a $B$ určené tímto obdélníkem obsahovaly stejná čísla.
    2. (největší společná podmatice ležící na libovolných pozicích)
      Tentokrát mohou mít matice $A$ a $B$ různé velikosti. Najděte rozměry obdélníka s největším možným obsahem takové, aby matice $A$, $B$ obsahovaly podmatice těchto rozměrů, které jsou stejné.

      Rozmyslete si, o kolik složitější by bylo zároveň vypsat i polohy společných podmatic.

  9. (Podmatice s největším součtem)
    Dostanete matici $A$ velikosti $n\times m$ obsahující přirozená čísla. Najděte podmatici s největším součtem.