Nejprve je potřeba si rozmyslet, zda přidání dalšího prvku na konec posloupnosti ovlivní dosavadní posloupnosti: Budu-li postupovat v posloupnosti od konce do začátku, mohu najít první číslo, jehož rozdíl s posledním číslem přesáhne toleranci ($k$). Pro další výpočty pak mi stačí uvažovat pouze úsek napravo od tohoto čísla. Zároveň je však potřeba si uvědomit, že i předposlední číslo již vyhradilo jakýsi úsek, ve kterém má smysl zkoumat podposloupnosti - budu se tak zabývat kratším z těchto úseků. Nyní vezmu následující situaci: mám posloupnost $P$ s finálním prvkem $P_{n+1}$, pro nějž je zarážka na pozici $s_1$. Jelikož se jedná o první zarážku, celá posloupnost od $0$ do $n$ je platná a tuto posloupnost nelze rozšířit zleva ani zprava. Označím tak $t_0=n$ a $s_0=0$, což znamená, že podposloupnost má délku $t_0 - s_0$. Dále, mezi $P_{s+1}$ a $P_{n+1}$ nevznikla žádná zarážka, a tak mohu postup opakovat (jako bych opět počítal od nuly), dokud nevznikne další zarážka.

Vím-li, jak efektivně uzávorkovat $n$ matic, pomůže mi to k tomu, abych věděl, jak uzávorkovat $n+1$ matic? Příklad: součin délky 4+1: $ABCDE=(ABCD)(E)=(ABC)(DE)=(AB)(CDE)=(A)(BCDE)$ Z něj je vidět, že nemohu postupovat tak, že zjistím uzávorkování pro první matice, přidám k nim další a pak provedu triviální výpočet. Musím postupovat slučováním - nejprve zjistím složitost pro všechny součiny délky 2, pak délky 3... Dále je vidět, že pro hledání složitosti násobení $n+1$ matic musím provést $n+1$ porovnání pro danou posloupnost. Vytvořím si tak následující tabulku: $\begin{pmatrix}A & B & C & D & E \ AB & BC & CD & DE \ ABC & BCD & CDE \ ABCD & BCDE \ ABCDE\end{pmatrix}$

Permutaci čísel zde budu označovat jako řetězec. Je-li na posledních $p$ pozicích řetězce rostoucí posloupnost, pak prvek těsně před touto posloupností se změní až v $p!$-té následující permutaci. Aby se totiž na pozicích od $n-p$ do $n-1$ (indexuji od nuly) změnila posloupnost na klesající, budou se muset vystřídat všechny permutace na těchto pozicích - od lexikograficky první do lexikograficky poslední. Jak toto pomůže při sestavování dané permutace? Příklad (pořadí, řetězec): $0: 123$ $1: 132$ $2: 213$ $3: 231$ $4: 312$

1. 1) Jedná se o zobrazení z $R^1$ do $R$. Linearita násobení: $(\alpha x * y)=(x * \alpha y)=(\alpha x y) = \alpha(x * y)$. Linearita sčítání: $((x+z)y)=(xy+zy)=(xy)+(zy)$ (a obdobně $(x(z+y))$). Matice zobrazení: $\begin{pmatrix} 1 \end{pmatrix}$ 2) Linearita násobení: Násobení $\alpha x$ (nebo $\alpha y$) vynásobí $\alpha$ každou složku vektoru $x$. Tím pádem $a(\alpha x,y)= \alpha x_1 y_1 + 2 \alpha x_2 y_1 + 3 \alpha x_2 y_2 = \alpha(x_1 y_1 + 2x_2 y_1 + 3 x_2 y_2) = \alpha a (x,y)$. Tentýž výsledek produkuje i $a(x,\alpha y)$, jelikož násobení je komutativní.

1. Pomocí obecného algoritmu vytvořím matici $L$: $l_{1,1}=\sqrt{a_{1,1}}$ $l_{1,2}=(a_{2,1})/l_{1,1}$ $l_{1,3}=(a_{3,1})/l_{1,1}$ $l_{2,2}=\sqrt{a_{2,2}-l_{2,1}^2}$ $l_{2,3}=(a_{3,2}-l_{3,1}l_{2,1})/l_{2,2}$

1. A) Elementárními úpravami (přičtení násobku řádku k rádku pod ním): $\begin{pmatrix} 4 & 1 & -1 \ 1 & 2 & 1 \ -1 & 1 & 2 \end{pmatrix} \sim \begin{pmatrix} 4 & 1 & -1 \ 0 & 7/4 & 5/4 \ 0 & 5/4 & 7/4 \end{pmatrix} \sim \begin{pmatrix} 4 & 1 & -1 \ 0 & 7/4 & 5/4 \ 0 & 0 & 7/4-25/28 \end{pmatrix}$ Všechny diagonální prvky jsou kladné, matice tedy je pozitivně definitní. Sylvesterovým pravidlem (podmatice prvních 1,2,3... sloupců*řádků mají všechny kladný determinant):

Datovou strukturou, která by data mohla uchovávat, může být úplný binární strom, kde všechny prvky budou na spodní hladině. Pro zjednodušení budu předpokládat, že počet těchto prvků je mocnina dvojky (strom pak mohu doplnit listy s hodnotami $+\infty$, velikost stromu se nejvýše zdvojnásobí). Zároveň mám také možnost přímého přístupu k listům (stále lineární prostor), a při pohybu ve stromu směrem nahoru vím, zdali se posouvám doleva nebo doprava. Nakonec také potřebuju možnost procházet jednotlivé hladiny postupně, zleva doprava (čili přeskakovat). K implementaci tak bude dobré použít pole, nikoli pointery. Operace jsou založeny na tom, že všechny vnitřní vrcholy uchovávají minimum ze svých synů, a také interval $[l,r]$, ve kterém se nacházejí listy. Algoritmus: Přičtení pak vypadá následovně: Vezmi levý/pravý prvek z intervalu a přičti k němu $\delta$.

František Mrkus 1. Plocha mezi dvěma křivkami je rovna (Newtonovu) integrálu rozdílu těchto křivek. Meze integrálu odpovídají bodům, ve kterých je funkční hodnota obou funkcí rovná. První křivka je spojením dvou funkcí: $y=\sqrt x$ a $y=-\sqrt x$. Spočítám nejprve rovnice pro průsečíky těchto funkcí: $\sqrt x = x-2$

1) Pravděpodobnosti zapíšu do matice následovně: 1. sloupec odpovídá "dnes slunečno", 1. řádek odpovídá "zítra slunečno", 2. sloupec odpovídá "dnes deštivo" a 2. řádek odpovídá "zítra deštivo": $P=\begin{pmatrix}0,8 & 0,6 \ 0,2 & 0,4 \end{pmatrix}$ Je-li dnes slunečno, pak vektor stavů je $s=(1;0)^T$(tedy 100% šance na slunečno v momentální okamžik). Za $n$ dní bude vektor stavů roven $P^ns$, což (z definice maticového násobení) v tomto případě odpovídá prvnímu řádku matice $P^n$. a) Pro data za dva dny (pozítří): $P^2 = \begin{pmatrix}0,76 & 0,72 \ 0,24 & 0,28 \end{pmatrix}$, tzn. pravděpodobnost na slunečno pozítří je $76,%$

Správná funkce $\pi$ umožňuje rekonstruovat nejkratší cesty bez znalosti jejich délky. Chci-li se tak dostat na vrchol $a$, musím projít vrcholy $s, \dots, \pi(\pi(a)), \pi(a)$. Označím $u=\pi(v)$. Ze třetí a čtvrté podmínky dostávám následující: $d(v)\leq d(u)+w(u,v)$ $d(v)=d(u)+w(u,v)$ $d(u)=d(v)-w(u,v)$ $w(u,v)\geq d(v)-d(u)$

Existuje-li majorita, pak bude v setříděné posloupnosti určitě tvořit souvislou řadu. Tedy např. v posloupnosti 7 prvků se musí majorita nacházet na těchto pozicích (od-do): $1-4$ $2-5$ $3-6$ $4-7$ a vždy prochází přes střed (medián). Dokázat neexistenci majority znamená vyvrátit všechny možnosti, kde se může majorita nacházet. V případě existence majority se navrhovaný algoritmus zastaví dříve. Pro sublineární řešení se nabízí použít binární vyhledávání: vyberu prostřední prvek (přičemž mohu vyloučit i krajní prvky) a zaznamenám si jeho hodnotu - to je kandidát na majoritu.

František Mrkus 1. Výchozí matice $A$: $\begin {pmatrix} 2 & 1 & 0 \ 1 & 2 & -1 \ 1 & 1 & 1\end{pmatrix}$ Matici převedu do Jordanova tvaru, který se dá snadno umocnit (převedení samo bude nepochybně složitější). Použiju postup, který je popsán v 1. úloze 10. cvičení.

1. Postup: Z původní matice vyjádřím vlastní čísla ( $\to$ čísla na diagonále matice $D$). Z vlastních čísel a původní matice vypočítám vlastní vektory; ty budou sloupci matice $S$ Matici $S^{-1}$ vypočítám pomocí Gaussovy-Jordanovy metody. Nelze-li matici $S$ invertovat, pak vlastní vektory jsou lineárně závislé a matici diagonalizovat nelze. Matice A: $A=\begin{pmatrix}0 & -3 & -3 \ -4 &-7&-7 \ 6 & 12 & 12\end{pmatrix}$ Charakteristický polynom: $\begin{vmatrix}0-\lambda & -3 & -3 \ -4 &-7-\lambda&-7 \ 6 & 12 & 12-\lambda\end{vmatrix}=-\lambda ^3 + 5 \lambda^2 -6 \lambda=-\lambda(\lambda ^2 - 5\lambda +6)$

1) Charakteristický polynom matice ($A$) vypočítám jako $det (A-\lambda I_n)$ - tvrzení 10.7. Determinanty budu počítat podle definice (příklad 9.2). Vlastní čísla jsou kořeny tohoto polynomu ($det (A-\lambda I_n) = 0$) - věta 10.3.1. Vlastní vektor je jádro matice ($A-\lambda I_n$) pro jednotlivá vlastní čísla $\lambda_1,\lambda_2,\lambda_3...$ s výjimkou nulového vektoru - věta 10.3.2. Matice A $det(A-\lambda I_n)=\begin{vmatrix}4-\lambda & -3 \ -6 & 1-\lambda \end{vmatrix}=(4-\lambda)(1-\lambda)-(-6)(-3)=4-5\lambda+\lambda^2-18=$$=\lambda^2-5\lambda-14$ $\lambda^2-5\lambda-14 = 0$;$\lambda_1 = -2, \lambda_2 = 7;$ vlastní čísla jsou $-2$ a $7$

Nejprve vezmu případ, kdy jsou oba stromy stejně velké ($|A|=|B|$) a dokonale vyvážené ($A$ obsahuje menší prvky). Mohu najít nejmenší prvek z $B$ (nebo největší z $A$) a pod něj zavěsit oba stromy (kořen $A$ nalevo, kořen $B$ napravo). Tím mi v nejlevějším vrcholu v $B$ vznikne "jen" $+1$ nevyváženost, která nevadí. Pokud by mi na začátku v poslední hladině v $B$ chyběl ještě jeden vrchol, musel bych po odstranění nejmenšího vrcholu provádět operace jako např. změna syna, rotace... Všechny tyto operace však pro AVL strom dokážu dělat v logaritmickém čase. Jsou-li stromy různě velké, budu menší strom (vzhledem k počtu hladin) zapojovat do většího. Dále již budu předpokládat, že menší strom obsahuje i menší prvky.

Předpokládám, že o stromu nevím nic, měl bych jej tak nejprve redukovat a nikoli přestavovat za běhu. Tedy: Strom přeměním na spojový seznam Ze spojového seznamu udělám vyvážený vyhledávací strom. Jak na to, mám-li omezenou paměť? Pravděpodobně budu muset při každém kroku prvky umazávat. 1. Plánuju-li udělat spojový seznam, pak by umazání šlo provést v konstantním (a celkově lineárním) čase; jdu-li doleva (hledám nejmenší vrchol), ten bude určitě list. Druhý nejmenší vrchol bude jeho otec, a zde již mohou nastávat problémy. Předpokládám-li však, že se nějak chytře dokážu dostat "nahoru", mohu se pouze vrátit do otce a přepojit jej.

Strom mohu nakreslit tak, že jeho "projekcí" na jeden řádek bude vstupní posloupnost. Proto mně napadl tento postup (jako online algoritmus): Vstupní řadu budu interpretovat jako neorientovaný graf; hrana vede vždy mezi předchozím a následujícím prvkem. Každému prvku také přiřadím vlastnost "hladina". Je-li předchozí prvek větší, pak nově přidaný prvek bude mít hladinu o 1 menší, v opačném případě o 1 větší. Tímto postupem by vznikl jakýsi cik-cak graf, který strukturu stromu samozřejmě nepřipomíná. Proto je potřeba takovou konfiguraci upravit - a nejlépe při přidávání nového prvku.

František Mrkus 1) Vzhledem k normalitě ne (a asi bych ani nenašel příklad, kde to platí) - protipříkladem buď např. $P = \begin{pmatrix} 0 & 1 \ 1 & 0\end{pmatrix}, Q = \begin{pmatrix} 1 & 0 \ 0 & 1\end{pmatrix}$ 2) Součet druhých mocnin prvků v každém řádku/sloupci musí být roven $1$. Jelikož tomuto součtu může přispívat vždy právě jeden prvek (na diagonále), musí být roven $+1$ nebo $-1$. Skalární součin každých dvou řádků bude také nula (každý prvek násobím s nulou), což jsou dvě postačjící podmínky pro ortogonalitu matice.

Přezdívka: FM a) $f(x)=\sqrt{\frac{x-1}{x^2+1}}$ Definiční obor: $\frac{x-1}{x^2+1}\geq 0$, tzn. $x \in \langle1,+\infty)$ Derivace: $f_1(x)=\sqrt{x},f_2(x)=\frac{x-1}{x^2+1}$

1) 1. Jedná se o diagonální matici ($1\times1$), takže determinantem je součin prvků na diagonále (tvrzení 9.3) $det(-4)=4$. 2. Také se jedná o diagonální matici; na diagonále se nachází $n$ prvků o hodnotě $-2$, a tak jejich součin je roven $(-2)^n$ (tvrzení 9.3). $det(-2I_n)=(-2)^n$. 3.