Příklady ADS1

(LS 2019/20)

Podmínky zápočtu: každá DÚ je za 5 bodů, na zápočet máte mít 2/3 bodů z možného počtu. Standardně máte 1 týden, tj. odevzdat na dalším cvičení nebo mailem.

Co má obsahovat DÚ: Popis souvislým textem, ze kterého je jasné, že jste úlohu vyřešili správně. V případě algoritmů typicky a) popis algoritmu, b) pseudokód algoritmu (u pseudokódu je menší pravděpodobnost, že ho popíšete neúplně a/nebo s chybou), c) rozbor složitosti.

verze 3.3 ; 16.5.2020 (.. 2.14.3)

Domácí úlohy přes Moodle https://dl1.cuni.cz/course/view.php?id=9559. Dotazy přes fórum tamtéž.
Přednášky přes Zoom, https://matfyz.zoom.us/j/524183465. Před přednáškou zveřejním slajdy.
Cvičení přes MS-teams/Office 365. Vytvořil jsem skupinu. https://www.mff.cuni.cz/cs/vnitrni-zalezitosti/it-a-sluzby/sluzby/office-365

DÚ 19/20

DÚ1 cv2/24.2.2020: 35.1 tranzitivita "O": $f \in O(g) \land g \in O(h) \to f \in O(h)$

DÚ2 cv3/2.3.2020: 4/54 Linearizace paměti, stačí a) nebo b).

DÚ3 cv4/9.3.2020: 4/91 Dva roboti v bludisti ; odevzdejte (znova) přes Moodle

cv5: samostudium 4/35, 4/42, 4/48

DÚ4 cv5x/16.3.: 5/94, přes Moodle

cv6: samostudium 6/4, 6/5, 6/7, 6/10, 6/13 (a 13.1)

DÚ5 cv6x/23.3.: 6/90, přes Moodle

cv7: samostudium 30.3. (dodatečně): 7/4+4.1, 7/5, 7/8+8.1

cv8: MS-Teams/Office 365/6.4.: 8/2,3,(5?),7,8+8.2,13,15rank(x),52

DÚ6 cv8x/6.4.: 8/90 (=15index(k))

cv9: MS-Teams/Office 365/20.4.: (Hašování): 12/3,4,8,9+9.3,11,32b,34,35

cv10: MS-Teams/Office 365/27.4.: (Rozděl a panuj 1/2): 9/2,3,4(slajdy OC)=35,7,10,12

DÚ7: 27.4.: 9/3h

cv11:MS-O365/4.5.: (rozdel a panuj) 9/1,6,(6a),(31),32,(33),37,(41)...

cv12:MS-O365/11.5.: (dyn.prog.) 10/(1), 3.a,a1,b 4, 5.a,d1, 7strucne/opak, 8

cv13:MS-O365/18.5.: (DP, třídění) 10/ 10a,b 11.1,11.2; 11/3b, (5), 6, 7, 37


readme:
Cvičíme příklady ze začátku, přizpůsobujeme se přednáškám (tj rozdělení je předběžné), příklady nad 30 (za "další") jsou pro vás na rozmyšlení, případně kdyby zbyl na cvičení čas.
"naučit": co se naučit, co si zapamatovat a co si odnést (z příkladu).
Slovníček je na konci.

Cvičení 1. (Po 17.2.2020) O-notace

Cvičení před přednáškou, 2020.

- úvod (kde jsou materiály, podmínky zápočtu)
- 1. (z knížky) Máme uspořádanou posloupnost. Hledáme dvě čísla, která mají daný součet $s$.
- $\to$ postupně kvadraticky $O(n^2)$, $O(n \log n)$ a lineárně $O(n)$ - dva způsoby,
-- závislost na d.s. (datových strukturách): pro $O(n \log n)$ potřebujeme posloupnost v poli, ne v spojáku.
-- naučit: při použití dvou cyklů pro lineární složitost: vnitřní sčítáme kumulativně, aby vyšla lineární složitost
- 2. Součet spojité podposloupnosti: hledáme součet rovný $s$.
-- předvýpočet: využití prefixových součtů (v 1D)
--- totéž v 2D: chceme počítat rychle součet náhodně vybraných obdélníků (např. všech)
---- předvýpočet v 2D ("prefixových", tj. levěhorních matic), pak pro jeden obd. sečtení (a odečtení) 4 čísel: vyjde to, s použitím principu inkluze a exkluze
- 3. složitosti závisí na kódování čísel (při neopatrném počítání): př. násobení matic
-- klasický alg. v $O(n^3)$
-- při kódování řádků a sloupců dlouhými čísly máme vlastní skalární násobení v $O(1)$, tj. celkem $O(n^2)$ - takovýto "trik" nechceme povolit (protože použitá dlouhá čísla jsou v bitovém zápisu $n$-krát delší, a v jejich operacích je schováno "chybějící" $n$)
- 3b. podobně: testování vektoru na nulový vektor: při (ne)vhodné reprezentaci čas $O(1)$ místo $O(n)$
- 4. na rozmyšlení 2018: (neodevzdávat)
-- největší součet (spojité) podposloupnosti, posl. obsahuje celá čísla (i záporná):
--- idea/hint: (lze se na to dívat jako na) dynamické programování
--- hint2: rozdělit vstup zápornými čísly na úseky nezáporných čísel není správné řešení
--- $\to$ chceme rychleji než $O(n^2)$

Další:
- 30. V rostoucí posloupnosti přirozených čísel najít první číslo $n$, které tam chybí.
-- naučit: "kapitánský krok", $O(\log n)$
- 31. V matici s \(n\) sloupci a \(m\) řádky najít co největší nulovou podmatici (s co největší plochou). ($O(nm^2)$ až $O(nm)$)
- 32. Fibonacciho čísla. Fibonacciho posloupnost \(\{f\}_i\) splňuje $f_0=0$, $f_1=1$ a $f_i=f_{i-1}+f_{i-2}$ pro i>1. Jak spočíst $f_n$ v $O(\log n)$.
- 32.1. Hint: matice pro spočítání další dvojice z předchozí dvojice. A rychlé umocňování matic.
- 32.2. Hint2: Vyjádřit $f_n=x_i f_{n-1-i}+y_i f_{n-2-i}$ pro $i\ge 0$ pro vhodné $x_i$ a $y_i$.
- 32.3. Explicitní výraz pro $f_n$ obsahuje $\sqrt{5}/2$ a $n$-tou mocninu. Jak ho počítat s malou zaokrouhlovací chybou?
- 32.4. Pozn.: Fibonacciho čísla se budou hodit u AVL stromů.
- 33. Máme mrakodrap s $n$ patry a $ k$ vajíček. Chceme zjistit, hodem z kterého patra už se vajíčko rozbije. Kolik potřebujete hodů pro různá $k$?
- 34.1 Máme danou posloupnost kladných čísel a číslo $k$. Chceme najít nejdelší posloupnost se součtem $k$.
- 34.2 Var: Stejné, ale se součtem nejvýš $k$.
- 34.3 Var: Stejné, ale připouštíme i záporná čísla a součet chceme rovný $k$.
- 35. Největší podmatice. Dostaneme matici přirozených čísel. Chceme najít největší obdélníkovou podmatici ze samých 0. Největší počtem prvků. (Lepší algoritmy díky preprocesingu.)
- 36. Pro danou posloupnost chceme najít co nejdelší úsek, aby rozdíl libovolných prvků v něm byl nejvýš $k$.
- 37. Máte několik setříděných posloupností $A$, $B$, $C$, $D$, ..., co nejrychleji najděte $a\in A$, $b\in B$, $c\in C$, $d\in D$, ..., takové, že $a+b+c+d+\cdots =n$.

Cvičení 2. (26.2.2019 $O$-notace)

- 1. podle čeho se porovnávají algoritmy? (čas, paměť/prostor, i méně používané míry: počet bajtů/paketů po síti, paralelní čas, počet diskových přístupů (protože jsou dražší než přístup do paměti), počet výpadků keše (protože přístup do paměti je dražší než do keše))
-- 1a. Co je ta podstatná míra, v praxi? ;-)
pozn.: u keše varianty: keš a velikost bloku známe velikosti nebo neznámé velikosti
-- Varianty měr: v nejhorším případě; v průměrném případě (z čeho se počítá průměr?); nejhorší případ pro sekvenci operací, tj. amortizovaná složitost.
- 2. definice $O$, $\Omega$, $\Theta$, ($o$, $\omega$)
- 3. seřadit funkce: $n$, $n^2$, $n^3$, $\log n$, $\log^2 n$, $\log n^2$, $n\log \log n$, $n \log n$, $n^{0.5}$
- 4. najděte $n_0$: $10 n$ a $n \log n$
- 5. aritmetika: sčítání, násobení, max
-- 5a. $f \in O(h) \land g \in O(h) \to f+g \in O(h)$
-- 5b. $f \in O(h) \land g \in O(h') \to f\cdot g \in O(h\cdot h')$
-- a použití aritmetiky při důkazech vlastností programů: sekvence příkazů, vnořené cykly, cyklus a jeho tělo, if příkaz ...
- 6. Které funkce $f$ zahrnují výrazy: $f \in O(1)$?
- 7. Nechť $n$ je velikost vstupu. Pro malé vstupy velikosti nejvýš $k$, tj. $n\lt k$, běží alg. v O(1).
-- 7a. Použití: při (např. rekurzivním) zpracování vstupu můžeme "malé" vstupy zpracovat lib. algoritmem bez změny složitosti. U třídění quicksortem se používá dotřiďování malých úseků (např.) insertsortem.
-- Můžeme kombinovat asymptoticky rychlý alg. s algoritmem s malou režií.

90. DÚ1: 35.1 tranzitivita "O"

Další: (neprobráno, možná příště:)
- 31. porovnat: $\log (n!)$ a $\log (n^n)$, $2^n$ a $2^{2n}$
- 32. které konstanty jsou významné: základ logaritmů, základ mocniny, ...
- 33. které funkce zahrnují výrazy: $O(1)$, $2^{O(\log n)}$, $2^{O(n)}$
- 34. najděte $n_0$: $10 n$ a $n \log n$, $10 n^{2.81}$ a $n^3$
- 35. aritmetika: sčítání, násobení, max, tranzitivita, vztahy $O$ a $\Omega$ a $\Theta$, ...
-- 35.1 tranzitivita $O$: $f \in O(g) \land g \in O(h) \to f \in O(h)$, taky pro $\Omega$ a $\Theta$
-- 35.2 vztahy: $f \in O(g) \leftrightarrow g \in \Omega(f)$
-- 35.3 $f \in O(g) \land f \in \Omega(g) \leftrightarrow f \in \Theta(g)$
- 36. Najděte funkci $f$, která pro lib. $k$ splňuje $f \in \omega(k^n)$ . (Vyjádřete slovně.)
- 37. najděte chybu: důkaz indukcí: $n^2 \in O(n)$
- 38. (MM/K) cv1, na rozmyšlení: a) Jsou dána čísla $s$, $x_i, i=1..n$ a $y_j, j=1..m$. Najděte $i,j$ tak, že $x_i+y_j=s$.
- b) totéž, ale posloupnosti $x_i$ a $y_j$ jsou uspořádané.

Cvičení 3. (5.3.2019 $O$-notace)

- 1. z (před)minula: úsek s největším součtem: $O(n^3)$, $O(n^2)$, $O(n)$ - inkrementální algoritmus - ze stavu pro $i$ počítá stav pro $i+1$
- 2. $x^n$ v $O(\log n)$, s jak velkými čísly pracujeme v lineárním a logaritmickém řešení, pokud $x$ je v 1 buňce?
-- 2a. $(x^n) \mod k$, s jak velkými čísly pracujeme, pokud modulíme až na konci? Jak to počítat s menšími čísly (tj. rychleji)?
- 3. RAM: dány hranice pole v buňkách 2 a 3. Hledáme největší součet (neprázdného) počátečního úseku, na výstup chceme součet a jeho index v buňkách 0 a 1, respektive. (args: číslo, [buňka], [[index]] pro nepřímou adresaci)
- 4. zopakování: malé $o$, $\omega$
- 5. najít neporovnatelné funkce
-- 5a. lze vhodně změnit kontext nahlížení, abychom je mohli porovnávat?

- 90. DÚ kandidát: $f \in o(g) \to f+g \in \Theta(g)$
-- Naučit: Pokud k funkci $g$ přičteme funkci $f$, která roste asymptoticky pomaleji než $g$, tak součet roste stejně rychle jako $g$

Další/příště:
- 31. Největší díra. Je dané pole $n$ čísel. Hledáme dva sousední prvky v uspořádání, které jsou nejvzdálenější. (Lineárně, čas i paměť.)
- 32. Grafy: pomocí DFS zjistit, že graf je souvislý; že graf neobsahuje cyklus. TODO: prehodit
- 33. Mosty v grafu, postupně zlepšující algoritmy
- 34. Překlad syntaktických konstrukcí z vyšších programovacích jazyků do RAMu, idey.

Cvičení 4. (12.3.2019 Grafy: DFS, BFS)

Konvence: pro vstupní graf $G$, nechť $n=|V(G)|$ a $m=|E(G)|$
Reprezentace grafu a vliv na složitost: a) matice sousednosti, b) seznam sousedů, pro orientované grafy seznam následníků, případně seznam předchůdců, případně oba, c) výpočtovým interface (API), i ohodnocení hran grafu se dá počítat.

- 1. Určete spotřebu paměti pro DFS a BFS na daných grafech:
- 1.1a. úplný graf na $n$ vrcholech,
- 1.1b. strom hloubky $d$ a s větvením $b$, (Kolik má graf vrcholů? Jaký je poměr velikosti poslední vrstvy k celému grafu?)
- 1.1c. mřížka $n \times n$ s vodorovnými a svislými hranami (např. pixely na obrázku).
- 1.1d. (orientovaný) vrstvený graf, $k$ vrstev šířky $l$, hrany vedou pouze z vrstvy $i$ do vrstvy $i+1$. d1) Programátorsky, jak velkou frontu v BFS potřebujete?
- 2. Pomocí DFS a/nebo BFS zjistěte, zda
-- 2.1. je graf $G$ spojitý,
-- 2.2. je graf $G$ acyklický, tj. DAG (Directed Acyclic Graph),
-- 2.3. je graf $G$ stromem,
-- 3. je graf $G$ bipartitní, tj. obarvitelný 2 barvami,
---3a. je rozklad bipartitního grafu na komponenty jednoznačný (až na přehození komponent)?
---3b. Popište formulí: $G=(V,E)$ je bipartitní $\leftrightarrow$ ...; (iff).
--- Pozn.: Deklarativní vs. programátorský přístup: přímočaré ověřování podle definice je často neefektivní.
--- Pozn2.: Formální zápis potřebujete např. pokud chcete popsat invarianty, podmínky na vstupy a/nebo podmínky na výstupy, aby jste je pak mohli formálně, strojově a/nebo počítačově ověřovat. (Zatím aspoň trochu.)
-- 4. sestrojíte nějakou kostru grafu, případně maximální les pro nespojité grafy,
-- 5. můžete zorientovat hrany neorientovaného grafu $G$, aby jste dostali acyklický graf?
--- 5a. Zvládnete to bez prohledávání (po preprocesingu)?
- 6. Topologické uspořádání grafu vytvoříme tak, že pomocí DFS najdeme časy otevření a uzavření vrcholů a potom vrcholy (mergesortem) utřídíme podle času uzavření. Co je nevhodné na tomto postupu? (+varianta: jiné třídění). TODO:přesunout
- 7. Hledání mostů: velmi naivně $O(m.n)$, naivně $O(n^2)$, líně - s low-link (možná bylo/bude na přednášce2018)
- 8. Klasifikace hran: a) Jak charakterizovat hrany pomocí času otevření a uzavření. b) Jaké druhy hran se vyskytují v neorientovaném grafu?
- 9. Přebarvování plochy v obrázku (při 4-sousednosti, tj. sousednosti po hraně pixelů)
-- 9a. Jak bude probíhat přebarvování při průchodu do šířky? Jak velkou paměť potřebujeme?
-- 9b. A do hloubky? A paměť?
-- 9c. Chytřejší alg., chytřejší d.s. (datové struktury).
- 10. V (zakořeněném) stromě, najít nejdelší cestu. (tzv. průměr stromu)
-- 10.1. Co si potřebujeme pamatovat pro návrat?
-- 10.2. A pro nalezení centra (tj. vrcholu uprostřed nejdelší cesty)?
-- (10.3.) K vrcholu $u$ najdeme nejvzdálenější vrchol $v$ a z něho nejdelší cestu, do $z$. Je cesta mezi $v$ a $z$ nejdelší cesta grafu?
- 11. Převod (zakořeněného) stromu na binární strom.
-- 11.x (Proč?: binární strom má pevný počet položek.)
-- 11.1. Pomocí označení hran (v horních vrcholech).
-- 11.2. Minulou úlohu (nejdelší cestu) na upraveném stromě.
-- 11.3. Programátorský převod, do dvou pointrů, idea. (převod tam i zpátky)
- 12. Najít minimální vrcholové pokrytí stromu.
-- Def.: Vrcholové pokrytí (VP) je podmnožina vrcholů $P$, že každá hrana má aspoň jeden vrchol v $P$.
-- 12.1. Různé požadavky na výstup: a) pouze velikost, b) jedno pokrytí, c) jak pokrytí reprezentovat?
-- 12.2. Najít maximální nezávislou množinu ve stromě.
-- (12.3.) Hříčka: Jak najít v obecném grafu množinu vrcholů, která je současně nezávislá a vrcholové pokrytí? (+okrajové podmínky)
-- Pozn.: Pro obecné grafy není znám polynomiální algoritmus pro zjištění max. nezávislé množiny a min. vrcholového pokrytí. Stromy jsou speciální druh grafů, pro které máme polynomiální alg. pro tyto problémy. (Bude v ADS2.) TODO opakuje se.
- 13. Převod výpočtu na (stavový) graf. Např. fibonacciho čísla, fib(5). (Budou: hradlové sítě.) *Př2019/Cv4*
- 14. Porouchané autíčko. Na čtvercové síti může jet rovně nebo zatáčet doprava. Jak dojet z daného bodu do servisu (tj. do daného bodu)?
- 14.1. Navíc: některé ulice se opravují.
- 16. Mějme souvislý neorientovaný graf. V jakém pořadí odtrhávat vrcholy, aby přitom graf zůstával souvislý?
- 17. Příklad implicitního grafu: k danému řetězci (heslu) délky $k$ hledáme podobné, až do $m$ změn (vložení, vypuštěni nebo nahrazení znaku).
- 17.1. Když nevíme počet změn, postupně zvyšujeme $m$, tzv. iterativní prohlubování. Viz 1.1b.
- 18. Příklad acyklického grafu, který má mezi $s$ a $c$ exponenciální počet cest.
- 19. Kdy je topologické uspořádání grafu určeno jednoznačně? (TODO Víc dopředu!)
- Pozn. Některé úlohy (najít extrémní, tj. minimální nebo maximální, množinu daných vlastností, případně množinu dané velikosti) jsou pro obecné grafy těžké (klika, nezávislá množina, vrcholové pokrytí), tj. není známý polynomiální algoritmus, ale pro stromy jako speciální případ grafů polynomiální alg. známý je.

- 90. DÚ k.: Housenka (P-II-2 z 55. ročníku MO-P): Housenka je strom, který má páteř ve tvaru cesty, ke které jsou připojeny nožičky (listy). Jak v daném stromu najít housenku s co největším počtem vrcholů?
- 91. DÚ3: Dva roboti ve čtverečkovaném bludišti, které chceme vyvést ven. Dostávají stejnou posloupnost příkazů (S,V,J,Z). Když narazí do zdi, příkaz ignorují. Mimo bludiště taky příkazy ignorují. a) Chceme najít nejkratší cestu, tj. nejkratší posloupnost příkazů. (b) Zjednodušení: Chceme najít nějakou cestu.
- 92. Totéž, ale nejkratší cesta počítá pouze vykonané kroky, bez "prázdných" kroků do zdi. TODO" přehodit

Další:
- 30. Hledání artikulací.
- 31. Nejdelší společná podposloupnost, pomocí cesty v grafu.
- 32.. Jak spočítat, kolik graf obsahuje trojúhelníků?
-- 32.1. A čtyřcyklů?
-- 32.2. A pro shora omezený stupeň vrcholů?
- 33. Je dán strom. Chceme smazat jednu hranu a přidat jinou, abychom získali strom s co nejmenším průměrem. (KSP 21-3-4)
- 34. Je dán neorientovaný rovinný graf. Jak zorientovat jeho hrany tak, aby měl každý vrchol odchozí stupeň nejvýš 3?
- 35. (i DÚ) Jak pokrýt souvislý graf se sudým počtem hran "vidličkami" $K_{1,2}$? (Viz P-III-5 v 54. ročníku MO-P.)
-- 35.1. Zjednodušeně: pro strom.
-- 35.2. Navrhnout alg. založený na DFS.
- 36. Kreslení grafu jedním tahem, případně minimálním počtem tahů.
- 37. Nalezení vrcholu, ze kterého jsou dosažitelné všechny vrcholy.
- 38. Rozmísťování posádek (P-I-3 z 55. ročníku MO-P): Říše má tvar stromu, v každém vrcholu je město s daným počtem obyvatel. Král chce do měst rozmístit vojenské posádky tak, aby bylo celkem ochráněno co možná nejvíce obyvatel, ale nevznikla souvislá komponenta s více než třemi posádkami (vzbouřily by se).
-- 38.1. Pro jinou povolenou velikost komponenty.
-- 38.2. Var: 3-nezávislá množina. Vybrat co nejvíc vrcholů ze stromu, aby nejvýše 3 byly spojeny.
- 39. a) Dá se topologicky třídit odtrháváním zdrojových vrcholů. b) Jak zařídit, aby to běželo v lineárním čase?
- 40. (MM) Nabízí se svůdná myšlenka, že DFS vznikne z BFS nahrazením fronty zásobníkem. Rozmyslete si, zda je to pravda.
-- 40.1. Jak si pamatovat frontu a/nebo zásobník. Jak expandovat vrcholy?
- 41. (Asynchronní procházení grafu.) Vrcholy orientovaného grafu jsou označeny jako bílé, šedé nebo černé. Na začátku je vstupní vrchol $u$ (nebo vrcholy) označen šedě, ostatní vrcholy jsou bílé. Krok algoritmu spočívá ve vybrání šedého vrcholu, přebarvení bílých následníků na šedé a potom (*) přebarvení vybraného vrcholu na černo. Zdůvodněte, že a) až se alg. zastaví, tak vrcholy dosažitelné z $u$ jsou černé a ostatní bílé (částečná/parciální správnost), b) alg. se, na konečném grafu, zastaví (konečnost).
Pozn.: a) (*) Pořadí je důležité při paralelním zpracování, b) alg. se používá pro garbage collector (sbírání smetí, tj. uvolňování nedostupné paměti). c) Částečná správnost a konečnost dávají spolu totální správnost: alg. se zastaví a dá správné výsledky.
- 42. Lze všechna možná topologická uspořádání získat při standardním procházení grafu pomoci DFS vhodnou strategií výběru hran? Proč ano/ne?
- 43. Reprezentace stromu pomocí levých a pravých závorek. a) Které posloupnosti závorek odpovídají stromům? Př: "(()()())()" b) Jak to zjistit jednodušeji než pomocí DFS? c) Jak zrekonstruovat strom?
- 44. Známé čtverečkované bludiště (v 2D), v něm Theseus, pohyblivý Minotaurus a nepohyblivý poklad. Po 1 kroku Thesea se pohne 2x Minotaurus: pokusí se zmenšit rozdíl své a Theseovy $x$-ové souřadnice, pokud to nejde, tak $y$-ové, pokud to nejde, tak stojí. Poraďte Theseovy, jak dojít k pokladu a vyhnout se Minotaurovi.
- 44.1. Var: V obecném grafu, Minotaurus si může vybrat libovolnou nejkratší cestu. Existuje jednoduchá podmínka pro bezpečnost. Najít ji a navrhnout její ověření.
- 45. Dokažte, že pokud se v grafu na aspoň třech vrcholech nachází most, pak je v něm také artikulace. Ukažte, že opačná implikace neplatí.
- (46. Hm. Definujme relaci $\~$ na vrcholech tak, že $x \~ y$ právě tehdy, leží-li $x$ a $y$ na nějaké společné kružnici. Dokažte, že tato relace je ekvivalence. Jejím ekvivalenčním třídám se říká komponenty hranové 2-souvislosti, jednotlivé třídy jsou navzájem pospojovány mosty. c) Upravte algoritmus na hledání mostů, aby graf rozložil na tyto komponenty. a) Najděte protipříklad, že relace $\~$ je ekvivalence. b) Opravte to.) *TODO*
- 47. Prostor kružnic. TODO
- 48. V orientovaném grafu jsou některé vrcholy obarveny infračerveně. Jak zjistit, jestli existuje cyklus obsahující aspoň jeden infračervený vrchol?
- 49. V paměti máte matici sousednosti orientovaného grafu $G$. Najděte v tomto grafu šéfa. Šéf je vrchol, ze kterého vede hrana do všech ostatních vrcholů a do něj samotného nevede žádná hrana. Najděte v $G$ šéfa a nebo řekněte, že tam žádný šéf není.
- 50. (i DÚ) O grafu řekneme, že je $d$-degenerovaný, pokud existuje pořadí odtrhávání vrcholů takové, že každý odtrhávaný vrchol má aktuální stupeň maximálně $d$. Například stromy jsou $1$-degenerované (trháme od listů) a rovinné grafy jsou $5$-degenerované. Pro zadaný neorientovaný graf najděte nejmenší $d$ takové, že $G$ je $d$-degenerovaný. (~šířka grafu) Lze v čase $O(n+m)$.
- 51. a) Mějme graf, který má vrcholy se sudými stupni. Chceme každou hranu orientovat tak, aby platilo, že do každého vrcholu vchází i vychází stejný počet hran.
-- b) Co kdybychom povolili rozdíl o 1 a nepotřebovali sudé stupně?
- 52. Je dán (spojitý) neorientovaný graf. Určete pořadí vrcholů (s opakováním), abychom použili každou hranu dvakrát, jednou v každém směru. Čistící vůz má projet všechny silnice v obou směrech.
- 53. Popište rozdíl v chování DFS a BFS, když expandujete vrchol najednou a když hrany procházíte postupně.
- 53.1 Najděte v grafu nějaký cyklus liché délky, pokud existuje, a vypište ho.
- 54. Linearizace paměti. Jak zlinearizovat/serializovat (vypsat do souboru) stav operační paměti (dynamické, tj. haldy) s pointry (na objekty) tak, abyste byli schopni zrekonstruovat (tzv. deserializovat) stav paměti (obecně na jiných adresách). Předpokládejte, že jsou dány vstupní body, které vedou zvenku (nebo jeden vstupní bod). Nedostupné objekty se zahodí, tj. je to použitelné jako garbage collector. a) Přímočaré řešení potřebuje dva průchody při vypisování nebo b) při načítání. Co se předává mezi fázemi? c) Navrhněte algoritmus tak, aby mu stačil jeden průchod při vypisování a jeden při načítání. (Vhodné pro síťové aplikace.)
- 55. (Implicitní grafy.) a) Jak generovat postupně všechny řetězce, které se liší od daného $s$ na nejvýš $k$ znacích? b) Změny jsou v rozpětí $l$ znaků. c) Navíc bez opakování. c1) Navíc lexikograficky. d) Změny jsou na právě $k$ znacích. e) Připouštíme i Insert a Delete znaku. f) Připouštíme i eXchange (swap), tj. přehození sousedních znaků. g) Při porovnávání biologických sekvencí se používá i penalizace za souvislou chybu (za mezeru/"gap"). Ekvivalentně, první změna v souvislé chybě má jinou cenu než další změny (... a jiné doménové heuristiky). h) Pokud chcete pouze spočítat, kolik je řetězců daného druhu, nemusíte je jednotlivě generovat. (Např. pro odhad počtu hesel daného druhu.)
- Pozn.: Implicitní graf má okolí vrcholu a/nebo hrany zadány funkcí pro generování nebo testování.
- Pozn.: Najít minimální vzdálenost dvou řetězců je typická úloha dynamického programování.
- 56. (Implicitní graf) Jako graf zakreslete závislosti při počítání Fibonacciho čísla pro vstup 7.
- 57. (Implicitní graf, prohledávání stavového prostoru)
Dokázat, že na problém batohu hladový přístup nefunguje. Problém batohu (jedna z formulací: "Součet podmnožiny", optimalizační): Máme předměty o váhách $v_1, ... , v_n$ a batoh s nosností $b$. Chceme zaplnit batoh co nejvíc, ale přitom nepřevýšit povolenou nosnost.
-- 57.1. Předměty mají navíc cenu $c_i$. Chceme batoh s nejvyšší cenou. Funguje hladový přístup?
-- 57.2. Předměty mají cenu a jsou dělitelné. Funguje hladový přístup?
- 58.$\label{rovnosti}$ Odvozování rovností a nerovností (ze života softwarových dokazovačů). Máme $n$ proměnných $x_1 ... x_n$, pojmenovaných, tj. rozlišitelných.
Pozn.: Některé podúlohy se hodí pro procvičení technik z jiných kapitol (kostry/Kruskal, DP).
a) Je dána množina $T$ rovností těchto proměnných ve tvaru $y=z$. Úlohou je zjistit, zda z $T$ vyplývá určitá rovnost $x_i=x_j$.
b) Navrhněte lepší přístup pokud víte, že budete pro pevnou $T$ testovat rovnosti tvaru $x_i=x_j$ pro mnoho dvojic proměnných.
c) Množinu $T$ dostáváte postupně (tzv. inkrementálně), po jedné rovnosti. Mezitím můžou přicházet dotazy na rovnosti.
c1) Pro inkrementálně zadávanou $T$ dává smysl, že neznáte počet proměnných $n$ dopředu a v rovnicích se můžou objevovat nové proměnné.
d) Chcete, aby $T$ byla backtrakovatelná, tj. mohli jste přidané rovnosti také odebírat zásobníkovým způsobem, tj. poslední přidaná bude první odebraná.
e) Kromě rovností můžou být v $T$ zadány i nerovnosti tvaru $x_i\not=x_j$. Ptát je můžete i na nerovnosti.
Analogicky e+b), e+c), e+c1), e+d).
f) Chcete ověřit, že množina $T$ (po přidání poslední ne/rovnosti) není sporná. $T$ je sporná, pokud z ní plyne pro některé dvě proměnné současně $y=z$ a $y\not=z$.
Hint: (Také obecně:) Nemusíte řešit přesně ten problém, který vám zadal uživatel. Můžete řešit ekvivalentní (případně obecnější, tj. těžší) problém, ze kterého jste schopni dopočítat odpověď pro uživatele. (Př: místo hledání mediánu jsem hledali obecně $k$-tý prvek)
(g) Implementačně: Nerovnosti si chcete pamatovat jen jednou (u jedné proměnné, protože jsou symetrické). Jak to zařídit? (pro pevnou $T$, obecně tradeoff)
h.1) (Programátorský) Kolik existuje různých rozdělení do tříd ekvivalence pro $n$ rozlišitelných proměnných?
h.2) (Počítání) Napište pro to rekurzivní vztah. (Bellova čísla)

Cvičení 5. (19.3.2019 Grafy: SSK, DAG)

Terminologie: SSK - Silně Souvislé Komponenty
- 1. Je rozklad na SSK dán jednoznačně?
-- 1a. Můžou být v grafu i jiné silně souvislé (indukované) podgrafy než komponenty silné souvislosti?
-- 1b. Tvoří relace $R(x,y)$ s významem "$x$ a $y$ jsou ve stejné komponentě souvislosti" relaci ekvivalence (a následně definuje rozklad množiny vrcholů na třídy ekvivalence)?
-- 1.1. Dvouprůchodový alg. pro SSK.
-- 1.2. Jednoprůchodový alg. pro SSK.
- 2. Pro daný graf $G$, v klasickém dvouprůchodovém alg. pro SSK v druhé fázi procházíme vrcholy opačného grafu $G^T$ podle klesajících časů uzavření (tj. od největšího, naposled uzavřeného). Můžeme místo toho procházet $G$ podle rostoucích časů uzavření?
- 3. Kondenzovaný graf ke $G$: kdy vede hrana mezi reprezentanty komponent? Popište formálně kondenzovaný graf $G_{SSK}$, pokud
-- 3a) máte množinu $R$ komponent, každý prvek $X \in R$ je podmnožina $V(G)$,
-- 3b) máte ke každému vrcholu $v$ reprezentanta jeho SSK $r(v)$;
-- 3a.1) popište podmínky na $R$, aby vyjadřovaly správný rozklad na SSK.
- 4. Které hrany patří nějaké nejkratší cestě?
- 4.1. Hledání kritické cesty. Určování rezerv hran (pomocí obousměrného prohledání).
- 5. Které hrany patří všem nejkratším cestám, v DAGu?
- 6. Lze v DAG hledat nejdelší cestu?
- 7. Indukce podle topologického usp. (Bylo/P2018.)
-- 7.1. Reprezentace min. cesty, (zatím) v acyklickém grafu. (Opakování; nechceme každou cestu samostatně)
- 8. Proč vadí záporné cykly při hledání minimální cesty?
-- 8.1. Vadí nulové cykly?
-- 8.2. Vadí cykly z nulových hran?

- 90. DÚ kandidát. Počítání cest mezi zadanou dvojicí vrcholů, v DAGu.
-- 90.1. Samozřejmě, nechceme přičítat jedničku za každou cestu.
-- 90.2. Jakou by mělo složitost přičítání jedničky?
- 91 DÚ kandidát. (Napište alg., který určí) Kolik existuje mezi danými dvěma vrcholy nejkratších cest v acyklickém (orientovaném) grafu?
- 91.1 Kontrolní otázka: A v acyklickém neorientovaném?
- 92 DÚ kandidát. Kolik existuje v DAGu mezi danými dvěma vrcholy nejkratších cest? (v grafu s jednotkově ohodnocenými hranami)?
-- (92.1. Kolik existuje mezi danými dvěma vrcholy nejkratších cest, v nezáporně ohodnoceném grafu?)
-- (92.1.1. Musíme být opatrní, jaké grafy připouštíme?)
- 93. DÚx kandidát (po SSK): Orientovaný graf $G$ je polosouvislý, pokud pro každé dva vrcholy $u$ a $v$ existuje (orientovaná) cesta $u \to v$ nebo $v \to u$. a) Charakterizujte polosouvislé grafy. b) Navrhněte alg., který zjistí, zda graf polosouvislý. (Jde to lineárně.) (+hint)
- 94. DÚ kandidát. Je dána mapa městečka v podobě neorientovaného grafu. Chceme z co nejvíce ulic udělat jednosměrky, ale stále musí být možné dojet autem odkudkoliv kamkoliv bez porušení předpisů. Umíte charakterizovat hrany/ulice, které nesmíte zjednosměrnit?

Další:
- 31. Varianty SSK:
-- 31.1. Spočítat počet komponent.
-- 31.2. Najít reprezentanty při DFS: reprezentant je první navštívený vrchol z komponenty.
- 32. Schéma sítě tajných agentů má podobu orientovaného grafu, jehož vrcholu jsou agenti a hrana popisuje, že jeden agent velí druhému. Agent předáva rozkazy všem tém agentům, kterým přímo velí. Šéf sítě je libovolný agent, který i sprostředkovaně velí všem agentům. a) Popište algoritmus, který najde šéfa sítě agentů. b) Umíte najít všechny šéfy?
- 34. Nalezení všech zdrojů a stoků. (Do zdroje nevede žádná hrana, ze stoku nevede žádná hrana.)
- 35. Eulerovský tah. a) Zjistěte, zda v grafu existuje eulerovský tah. b) Vydejte nějaký v datové struktuře. c) Vydejte rozklad hran grafu na minimální počet tahů. Eulerovský tah $T=e_1, e_2, ... e_m$ je posloupnost hran (tj. tah), t.ž. $i\not= j \to e_i \not= e_j$, $|e_i \cap e_{i+1}|=1$ a $e\in E \leftrightarrow e \in T$, tj. všechny hrany grafu jsou v tahu a žádná se neopakuje.
- 36. Turnaj hrálo $n$ účastníků po dvojicích každý s každým. Výsledky máme v matici v paměti. Pro sponzora hledáme případného účastníka, který vyhrál všechny zápasy. V $O(n)$.
- 37. Konstrukce seznamu sousedů grafu $G^T$ ze zadaného $G$ ve tvaru seznamu sousedů.
- 38.a) Je dán graf $G=(V,E)$ s vrcholy $V=\{v_{i,j}|1\le i\le m, 1\le j \le n\}$ a hranami $E=\{(v_{i,j}, v_{i+1,j})\} \cup \{(v_{i,j}, v_{i,j+1})\} \cup \{(v_{i,j}, v_{i+1,j+1})\}$. Vykouzlete tři (různé) topologické uspořádání vrcholů grafu $G$.
-- b) (programátorský) Napište program, který vydá pro každé navržené topologické uspořádání dvojice $(i,j)$ indexů vrcholů v tomto uspořádání.
- 39. Kritické hrany v DAG, pomocí programování řízeného událostmi. (2020)
Chcete při jednom průchodu topologicky uspořádaným grafem určit délku nejdelší (tj. kritické) cesty a zároveň určit všechny kritické hrany, tj. hrany, které patří do některé kritické cesty. Navrhněte globální datové položky a položky pro jednotlivé vrcholy. Dále popište operace inicializace vrcholu $init(v)$, otevření vrcholu $open(v)$ před začátkem zpracování seznamu jeho hran, uzavření vrcholu $close(v)$ po dokončení zpracování jeho hran a $uvolnění'(u,v)$ pro uvolnění hrany.
Hint: rozlište 3 případy: když je uvolňovaná cesta do $v$ delší/stejná/kratší než aktuální nejdelší cesta do $v$.
-- b) zjednodušení: graf má jeden zdrojový vrchol $z$ a jeden cílový vrchol $c$.

Cvičení 6. (26.3.2019 Min. cesty)

- 0. Opakování: Cesta, sled, tah. (Pro neorientované i orientované grafy.)
- 0.1 Liší se tyto pojmy v acyklickém grafu?
- 1. Dijkstrův alg. min. cesty pro různé struktury. (Bylo P.)
- 2. Hledání nejpropustnější cesty.
- 3. Var: Hledání cesty, kterou projede nejvyšší kamion.
- 4. Hledání nejspolehlivější cesty. Předpokládáme nezávislé pravděpodobnosti hran, které se po cestě násobí. (!Hledáme max.)
-- Impl: Trik s logaritmem, i kvůli podtečení.
- 5. Dijkstra: Můžu se zbavit negativních hran přičtením konstanty ke všem ohodnocením?
- 6. Dijkstra: Algoritmus funguje, pokud všechny negativní hrany sousedí s počátečním vrcholem.
-- 6.1. Dijkstra se zápornými hranami: nastavení potenciálu.
-- 6.2. Jak spočítat potenciál. (dvě možnosti)
- 7. Jak hledat nejkratší cesty v grafu, ve kterém mají ohodnocení i vrcholy?
- Pozn. Pro úlohy podobného typu, kdy máme nestandardní zadání, jsou dva možné přístupy. a) Buď upravíme (a naimplementujeme) algoritmus, aby počítal/ošetřoval navíc i nestandardní vstup, anebo b) převedeme rozšířené zadání (na grafu $G$) na standardní zadání (pro jiný graf $G'$) pouze s ohodnocenými hranami. Z výsledku pro graf $G'$ musíme být schopni zrekonstruovat řešení pro rozšířenou úlohu na grafu $G$. Přístup za b) má výhodu, že můžeme hned použít knihovny pro standardní úlohu a nemusíme programovat úlohu, pouze převod (i zadání i řešení). Při přístupu a) můžeme mít připraven algoritmus s API nebo s "hook", které dovolí doprogramovat výkonné části alg. vhodným způsobem. (Příklad takového postupu je 5/39.)
- 8. Bellmanův-Fordův alg.: Co platí po $i$-té fázi, tj. invariant hlavního cyklu.
- 9. Floydův-Warshallův alg. pro všechny cesty v grafu ($O(n^3)$).
-- 9.1. Invariant hlavního cyklu.
-- (9.2.) Hledání nejkratšího cyklu
- 10. (Dvě kriteria.) Hrany jsou ohodnoceny délkou a cenou. Hledáme nejlacinější z nejkratších cest.
-- 10.1. Délku přepočítáváme na cenu, lineárně. Hledáme nejlacinější cenu v kombinovaném ohodnocení.
-- (10.2.) Funguje to pro nelineární přepočet? (Za jakých podmínek? Jak to implementovat?)
-- (10.3.) Paretovo optimum. Obecně, pro dvě kriteria (nebo víc), co je optimum?
- 11. Optimalizujte relaxaci/expanzi vrcholů v Bellmanově algoritmu.
- 12. Lze v obecném grafu hledat nejdelší cestu? Je nejdelší cesta dobře definovaná? (P2019)
- 13. Superman prochází graf, i když o tom neví. Některé vrcholy dokáže projít, pouze pokud si dá povzbuzující nápoj z plechovky. Má k dispozici $n$ plechovek. a) Dokáže projít z $s$ do $c$? b) Jaká je nejkratší cesta? c) Kolik nejméně plechovek potřebuje, aby prošel? d) Superman hledá trade-off mezi počtem plechovek a délkou cesty. Dokážete mu spočítat informace pro rozhodování? (!Trade-off.)
-- 13.1. Bohužel, většina knihoven pro zpracování grafů nepočítá s použitím povzbuzujících látek a nedovoluje rozlišovat vrcholy a počítat plechovky. Dokážete převést tuto úlohu na klasickou úlohu na klasickém grafu? (Hint: expanze grafu/vrcholů)
(!Převod+filozofie: je mnohem lepší, když nemusíme upravovat kód, ale jen "převedeme" vstupní data. Ale pak musíme rekonstruovat (tj. být schopni rekonstruovat) řešení původní úlohy z výsledků výpočtu na převedeném grafu.)
Tradeoff. Z hlediska výkonu/času programátora je typicky lepší, pokud kód neupravujete. Z hlediska výkonu/času programu je typicky lepší, pokud (zdrojový) kód optimalizujete pro danou úlohu.
- 14. Haldy. (Využívá Dijkstra i heapsort, i min. kostry.) a) Reprezentace binární haldy v poli, opakování z programování (snad).
b) Jaká je cena jednotlivých operací?
-- 14.1. (i DÚ) a) Jak vybudovat haldu s $n$ prvky dávkově v poli v čase $O(n)$? (Poučení: líné vyhodnocení může ušetřit.) (Po vybudování v poli můžete haldu převést na pointry.) TODO
b) Ukažte, že když vkládáme prvky do haldy postupně a samostatně, tak celková cena je $\Theta(n \log n)$ (bez ohledu na to , že průběžně vkládáme do menší d.s.).

- 90. DÚ5/2020. Bludiště s dveřmi (P-I-2 z 58. ročníku MO-P): čtverečkové bludiště, jsou v něm čtyři typy zamčených dveří a klíče odpovídajících čtyř typů (Red, Green, Blue, White). Jakmile najdu klíč, mohu už libovolně procházet dveřmi příslušného typu. Jak najít nejkratší cestu?
- 91. DÚ kandidát:

Další:
- 31. Lze relaxační alg. použít pro hledání všech cest najednou? Jak?
- 32. Dokázat, že relaxační algoritmus se vždy zastaví, když v grafu nejsou záporné cykly. (Hint.)
--- 38. (i DÚ) Dokažte, že v grafu bez záporných cyklů se obecný relaxační algoritmus zastaví, ať už vrchol k uzavření vybíráme libovolně.
- 33. (i DÚ) Nejkratší cesty v grafu ohodnoceném hodnotami \(\{1,\dots,K\}\) (čas třeba $O(nK+m)$ úpravou Dijkstry, paměť $O(n+m+K)$).
- 34. Najít protipříklad na Dijkstru v grafech se zápornými hranami, ale bez záporných cyklů. (špatný výstup nebo horší složitost)
- 35. Sestrojte rodinu grafů, na kterých obecný relaxační algoritmus s nešikovným pořadím relaxací stráví exponenciální čas. (Mohlo by se to stát, kdybychom relaxovali vrchol s nejmenším ohodnocením? Čili jako u Dijkstry, ale se zápornými hranami.)
- 36. a) Jak poznáme, že je v grafu (dosažitelný) záporný cyklus? b) Jak nějaký vypsat?
- 37. Je dána matice kurzů měn. Jak najít ziskovou směnu (bez poplatků)
- 39. (i DÚ) a) Upravte BFS, aby spočítal (nějakou) nejkratší cestu mezi danými vrcholy $u$ a $v$. b) Vidíte nějakou souvislost s Floyd-Warshallovým algoritmem (pro hledání všech cest v grafu).
- 40. Jak se dá pro hledání min. cest použít speciální násobení matic (s min a +). Jakou má algoritmus složitost? (Možná bylo.)
- 41. (i DÚ) Floydův-Warshallův algorimus funguje v jednotlivých cyklech nad maticí vzdáleností $D$ a spočítá pro ohodnocený orientovaný graf $G$ matici délek nejkratších cest mezi každými dvěma vrcholy $u,v \in V(G)$. Za použití F-W algoritmu navrhněte algoritmus pro detekci záporných cyklů.
- 41.1. Reprezentace a rekonstrukce cest ve F-W alg.
- 42. Ve F-W algoritmu pracujeme s jedním polem a čísla si přepisujeme "pod rukama". Proto se nám můžou poplést hodnoty ze současné a z minulé fáze. Ve skutečnosti, hodnoty, pro které to může nastat, vyjdou vždy stejně. Proč?
- 42.1. Ve skutečnosti, ani to dokazovat nemusíme. I kdyby hodnoty v průběhu alg. byly rozsynchronizovány, na konci jsou správně. Proč?
- 43. Nalezení nejkratšího 4-cyklu ($O(n^3)$) Hm.
- 44. Máme čtverečkovou mapu se zdmi mezi čtverečky (jako obvykle). Přechod na volný sousední čtvereček stojí 1, prokopání zdi stojí $k$. a) Najděte nejkratší cestu mezi danými vrcholy, z $u$ do $v$. b) Využijte "malého" rozsahu cen pro lepší alg. (I analogický jiný příklad.)
- 45. Když $M$ je matice sousednosti grafu, co reprezentuje $M^k$?
- 47. (Reformulace) Ukažte, jak pro libovolné $n$ sestrojit graf na nejvýše $n$ vrcholech, v němž mezi nějakými dvěma vrcholy existuje $2^\Omega(n)$ nejkratších cest.
- 48. Mějme ohodnocený graf, někdo si vybral vrchol $v$ a potom pro každý vrchol $u$ prošel jednu nejkratší cestu $u \to v$. Jak vypadal graf, po němž někdo chodil? Co pokud neexistují dvě stejně dlouhé cesty?
- 49. Var: Máme bludiště zadané grafem, ve kterém je v různých vrcholech $k$ dveří, k nim ve vrcholech právě $k$ klíčů 1:1, které je otevírají a cíl. Najděte nejkratší cestu do cíle (nebo ven z bludiště).
- 50. ^a) Čtverečkované bludiště a v něm bílá paní, která prochází zdmi. Najděte cestu z $u$ do $v$, která minimalizuje počet průchodů zdmi.
- ^b) Stejné bludiště, ale procházíme jím my a prokopání zdi nas stojí $k$.
- 51. Některé úlohy, např. vzdálenost dvou řetězců, jdou převést na hledání cesty. Ale pokud je model chyb složitý (chyby navzájem závisí - jejich cena a/nebo pravděpodobnost), tak potřebujeme přidat do grafu další "rozměry" anebo se spokojit s aproximací. Př.: (BINF:) Souvislá změna (tzv. "gap") má penalizaci. (INF:) Chyby při přenosu jsou klastrovány a blízké chyby mají vyšší pravděpodobnost. (~při samoopravných kódech)
- 52. Tranzitivní uzávěr grafu. Optimalizace.
- 53. Viterbiho alg. Doplnit. TODO
- 54. Binomiální halda. Umožňuje rychlé ($O(\log n)$) slučování hald.
- 55. Diferenční logika: řešitelnost soustavy rovnic tvaru $x-y \le c$, kde $x$ a $y$ jsou proměnné a $c$ konstanta (celočíselná nebo reálná). (cv: asi cesty)

Cvičení 7. (2.4.2019 Min. kostry)

- MST: Minimal Spanning Tree, minimální kostra
- 1. Opakování: řezové lema, (příp. úprava lematu pro:) různé vs. stejné hrany
-- 1.1. Je min. kostra určena jednoznačně?
-- (1.1.1 Charakterizujte grafy, ve kterých je min. kostra jednoznačná.)
-- 1.2. Generický algoritmus. a) G.Algoritmus je popsán obecně, obvykle v něm můžeme zvolit nějakou konkrétní strategii pro potřebná rozhodnutí. b) Příklady: relaxační alg. pro min. cesty, "řezové" alg. pro min. kostry, b.1) Pro konkrétní algoritmy zreformulujte algoritmus tak, abyste oddělili generickou část a konkrétní strategii. c) přístup G.A. se používá, protože jeden důkaz správnosti zahrnuje mnoho různých strategií, d) strategie nemusí být popsány explicitně, např. Kruskalův alg. vybírá globálně minimální hranu a "použitý řez" je určen hranou, e) různé strategie můžou mít různé vlastnosti (konečnost, časovou složitost G.A. a trade-off s časovou složitostí výběru a použití strategie), případně pro různé třídy vstupů (zde grafů), f) pro řešení daného problému můžou existovat další algoritmy, které nejsou instance navrženého G.A. Např. bude u toků v sítích.
- 2. V Kruskalově alg. (výběr min. hrany) třídíme hrany líně, např. heapsortem. Když máme kostru, končíme. Ušetříme, případně kolik?
-- 2.1. Hladové alg.
- 3. Jarník: a) hrany v haldě: správnost a složitost, b) vrcholy v haldě
-- 3.1. pro b): Analogie s Dijkstrovým alg: vrcholy v haldě, ale s jinými přiřazenými hodnotami.
- 4. Borůvkův alg.: Protipříklad grafu se stejnými hranami, který může dát špatný výsledek.
-- 4.1. Jak to opravit? Jak můžu v grafu se stejně ohodnocenými hranami "rozrůznit" hrany? (Bylo Př2018)
- 5. Jak najít min. kostru, v níž vybrané vrcholy musí být listy?
- 7. Union-Find struktura, v Kruskalovi. Keříky: nejhorší případ. Spojování, aby vyšlo $O(\log n)$. (Proč Union-by-rank místo Union-by-size.)
- 8. Budujete minimální kostru. Příliš aktivní zákazník vždy ukáže na nějaký osamocený vrchol $u$ a požaduje, abyste $u$ v dalším kroku připojili k nějakému vrcholu. Dokážete (a dokážete, že dokážete) vybudovat min. kostru pro tohoto zákazníka?
- 8.1 Totéž, zákazník ukáže na nějaký souvislý podgraf.

- 90. DÚ k. Mám graf a jeho MST, změnila se váha jedné hrany. Jak se změní MST?
- 90.1 Je aplikovatelná metoda superlíného programátora. Jakou má složitost (pro jednotlivé alg.)?
- 91. DÚ kandidát. Jak najít druhou nejlepší kostru?
- 91.a) V průběhu konstrukce min. kostry zjišťujeme i druhou nejmenší.
- 91.b) Známe min. kostru a chceme najít druhou nejmenší.

Další:
- 32. Pro graf s cykly, můžete zahazovat hrany, abyste dostali minimální kostru? (... důkaz, efektivní implementace)
- 33. (i DÚ) Minimální kostra v grafu s váhami {1,...,K}.
-- 33.1. Rozeberte jednotlivé algoritmy.
- 34. Jak se chová minimální kostra v multigrafech? Jak v lineárním čase odstranit všechny násobné hrany?
- 35. Jiný příklad hladového algoritmu: Huffmanovo kódování. Přiřadit písmenům binární kódy (různé délky), tak aby daná zpráva (se známou frekvencí/četností písmen) měla co nejkratší kód.
- 36. Borůvkův algoritmus s kontrakcemi: když hranu přidám do kostry, tak ji rovnou zkontrahuji. Pokud přitom odstraňuji multihrany, dostanu algoritmus, který je pro rovinné grafy lineární (kontrakce zachovává rovinnost, počet vrcholů i počet hran tudíž klesá exponenciálně).
- 37. Při hledání min. kostry spojujeme pouze dané vrcholy. Obecnější úloha je, když chceme propojit všechny dané vrcholy celkově co nejkratšími spojnicemi, ale můžeme přidávat další vrcholy z nějakého metrického prostoru. a) Propojení v rovině, b) fylogenetický strom. (BINF)
Tato optimalizační úloha je v obecnosti těžší. V kontextu probíraných hladových algoritmů, při hledání optima můžeme použít hladovou heuristiku pro lokální zlepšování. (Shlukování jako další zobecnění.)
- 38. Kruskal: dynamické keříky: optimalizace.
- 39. Hladová heuristika. a) Máme množinu klíčů se známými frekvencemi hledání (nebo pravděpodobnostmi). Chceme sestrojit optimální binární vyhledávací strom, tj. takový, že celkový součet součinů hloubky vrcholu a jeho frekvence je co nejmenší. Tato úloha se řeší dynamickým programováním. Zde navrhněte hladovou heuristiku, která zvolí za kořen rozumný vrchol. b) Chceme, aby heuristika byla rychlá. Nechceme v rámci předvýpočtu spočítat optimální řešení a jako heuristiku ho jen rekonstruovat.
- 40. Rekonstrukce metriky: Mějme strom na množině $\{1,...,n\}$ s ohodnocenými hranami. Metrika stromu je matice, která na pozici $i,j$ udává vzdálenost mezi vrcholy $i$ a $j$. Vymyslete algoritmus, jenž sestrojí strom se zadanou metrikou, případně odpoví, že takový strom neexistuje.

Cvičení 8. (9.4.2019 Stromy, BVS)

Slovníček: BVS: Binární Vyhledávací Strom
Slovníček: BÚNO: Bez újmy na obecnosti
- 0. Opakování, Big picture: (Vyhledávací struktura pro) množiny (jen klíče) vs. slovníky (klíče s hodnotou). Neopakující se klíče (BÚNO) vs. opakující se. Stromy ve vnitřní paměti vs. ve vnější (paměť vs. disk; cache vs. mimo cache). BVS ($O(\log n)$, lin. uspořádání, intervalové dotazy) vs. hašování ($O(1)$, jen rovnost, bodové dotazy).
- 1.1. Reprezentace stromů. Rotace. (Reprezentace pomocí termů.) Externí listy. Základní operace.
- 1.1.1 Jak implementovat rotace (aby jste v kódu skoro určitě neudělali chybu)? *Př2019
- 1.1.2 a) Proč se v AVL stromech používají dvojité rotace? b) Lze dvojitou rotaci implementovat pomocí dvou jednoduchých rotací anebo musíme navrhnout samostatnou nezávislou proceduru?
- 1.1.3 Rezerva v AVL, propagace informací nahoru.
- 1.2. (a,b)-stromy (= #synů) nebo B-stromy. Operace. Varianty: s externími nil-vrcholy vs. klíče v listech; zpětné úpravy ($b=2a-1$) vs. preventivní úpravy (pro paralelizmus). (Štěpení a slučování $2\leftrightarrow 3$ pro lepší využití paměti - tradeoff.)
- 2. Jak se v BVS hledá následník? Jak dlouho trvá, když začneme v minimu a budeme celý strom procházet opakovaným hledáním následníků?
-- 2.1. a) Chceme najít prvky v intervalu $\langle c,d\rangle$. Jaká bude složitost, v závislosti na velikosti struktury $n$ a velikosti výstupu $k$? b) Hodila by se nám nějaká elementární operace, pomocí které bychom intervalové vyhledávání mohli implementovat?
-- 2.2. Vkládání hodnot $1..n$, do různých stromů. (Převažování AVL, R-B.)
- 3. Počítání inverzí v permutaci. Lépe než přímočaře v $O(n^2)$
- 5. Amortizovaně efektivní BVS pomoci rebuildu: v každém vrcholu si budeme udržovat velikost podstromu, jakmile bude v nějakém vrcholu poměr mezi velikosti levého a pravého podstromu příliš vychýlený (řekněme mimo interval $\langle 0.5,2\rangle$), celý podstrom rozebereme a předěláme na dokonale vyvážený. Strom je hluboký $O(\log n)$, Insert a Delete mají v nejhorším případě lineární složitost, ale amortizovaně $O(\log n)$. (Poměr můžeme kontrolovat i vůči otci: v intervalu $\langle 1/3,2/3 \rangle$, což v okrajových případech zjednoduší popis.)
- 6.
- 7. Pokud si pamatujeme explicitně (odkaz na) minimum, jak rychlé bude a) vrácení minima, b) odstranění minima? (v nejhorším, průměrném a amortizovaném případě; pro různé druhy stromů)
- 8. Programátorsky: sloučení dvou stromů BVS. (Dvě možnosti. Rekurzivní i nerekurzivní.)
-- 8.1. Var.: Vkládání uspořádané posloupnosti do stromu.
-- 8.2. Ořezání BVStromu do daného intervalu. (Správnost. Složitost, i v porovnání s postupným vypouštěním prvků.)
-- (8.3.) Aplikace: udržování stromu distribuovaně, výměna prvků, dávkově.
- 9. Strom dané hloubky s nejméně vrcholy a) BVS, b) AVL, c) R-B (Č-Č)
- 9.1 Minimální AVL-strom hloubky $n$ má $T(n)=fib_{n+c}-1$ vrcholů, pro vhodné $c$. Dokažte indukcí.
- 10. Korespondence R-B a (2,4)-stromů.
- 10.1 Operace Insert a Delete na (2,4)-stromě.
- 10.2 Operace Insert a Delete na (2,3)-stromě.
- 11. (i DÚ) Sloučení dvou (a,b)-stromů, když v jednom jsou menší prvky než ve druhém.
- 12. Jak zjistit, jestli jsou v posloupnosti všechny hodnoty navzájem různé?
- 13. Najděte v posloupnosti nejdelší úsek, v němž se žádná hodnota neopakuje.
-- 13.1. Totéž, ale $k$-tice za sebou jdoucích hodnot se nesmí opakovat (nad pevnou abecedou).
-- 13.2. Varianty: a) pevný známý rozsah čísel (nebo znaků), b) čísla bez omezení.
- 14. Je dáno $x$ a $d$. Chceme najít ve stromě všechny prvky, které se od $x$ liší nejvíc o $d$. (Zajímavé je to ve více dimenzích.)
- 15. (i DÚ, MM 4.1.4, i jinde) Operace index($k$) najde $k$-tý nejmenší prvek na uspořádané množině, inverzní operace je rank($x$), která pro dané $x$ spočte počet prvků menších než $x$. Rozmyslete si, jakou složitost mají tyto dvě operace v různých reprezentacích množin.
- 15.1 Úloha zahrnuje i hledání mediánu.
- 16. Varianty operace Find/Successor: FindUp($x$) - najdi $x$ nebo nejbližší větší. Pro inicializaci intervalového prohledávání.
- 17/Náhradní2018. Jak BVS upravit, aby uměly říct, jaké pořadí odpovídá danému prvku $x$? (operace rank($x$)) Přitom nechceme zhoršit složitost jiných operací a musíme udržovat případně přidané informace (i pro rotace).

- 90. DÚ k. Jak BVS upravit, aby uměly hledat $k$-tý nejmenší prvek? (operace index($k$)) Přitom nechceme zhoršit složitost jiných operací a musíme udržovat případně přidané informace. (Dvě možnosti.)
- 91. DÚ kandidát. a) Jak v lepším než lineárním čase najít medián sjednocení dvou setříděných posloupností? (Vstup je zadán "v poli", tj. jako orákulum, které umí vrátit $k$-tý prvek z dané vstupní posloupnosti.)
-- b) Pokud jsou posloupnosti řádově různé délky, jaký preprocesing doporučíte? (Např. 1001 a 101 prvků.)
- 92. DÚ kandidát. Transformovat jeden tvar BVS na jiný, v $O(n)$.
- 93. (na rozmyšlení 2018) DÚ kandidát. Jak vyrobit datovou strukturu, která si bude pamatovat dvojice (klíč,hodnota) a bude umět odpovídat na dotazy typu "Jaké je minimum z hodnot, jejichž klíče leží v intervalu $\langle a,b \rangle$?".
- 94. (i DÚ kandidát/náhradní příklad) Navrhněte datovou strukturu, která bude umět efektivně i) vložit prvek ii) odebrat medián. (+doménová heuristika, +líné operace: mnoho vložení a pak medián)
- 95. Na vstupu postupně přicházejí čísla. Kdykoliv přijde další, vypište medián z posledních $k$ čísel. Dosáhněte časové složitosti $O(\log k)$ na operaci. b) Dokažte, že čas $Θ(\log k)$ je nejlepší možný, pokud umíme čísla pouze porovnávat. (Reformulace/varianta předchozího.)

Další:
- 32. Je dán strom s ohodnocenými hranami a číslo $K$. Existuje ve stromu cesta, na které by byl součet ohodnocení právě $K$? (Příklad i na hašování.)
- 36. Pokud do (a,b)-stromu pouze insertujeme, tak pokaždé provedeme amortizovaně $O(1)$ změn stromu. Pro $b>=2a$ to platí i s delety, ale to už není úplně snadné vymyslet. Můžete zkusit rozebrat, jak se chová insert hodnot $1..n$ po sobě.
- 37. Dávková stavba (a,b)-stromu z uspořádané posloupnosti. (Ale: Typicky se stromy používají pro vytvoření uspořádání, např. indexy v db.)
- 38. Sloučení dvou (a,b)-stromů. (Víc možností popisu.)
- 39. Je dán text rozdělený na slova. Jak zjistit, kolikrát se které slovo vyskytuje?
- 39.1. (Z praxe.) Ke každému slovu seznam pozic, kde se vyskytuje. (... a/nebo dokumentů.)
- 40. Je dán slovník. Sestrojte datovou strukturu, pomocí níž půjde k danému řetězci najít ve slovníku nejlepší rým (s nejdelším společným suffixem). Co kdybychom chtěli najít lexikograficky nejmenší z nejlepších rýmů?
- 41. Problém tiskařského šotka (KSP 9-2-2): mějme slovník známých slov a text. Pro každé slovo textu chce tiskařský šotek zjistit, jestli je možné ho jedním překlepem (vložení/smazání/změna znaku) převést na jiné slovo ze slovníku.
- 42. Opět slovník a text. Ke každému slovu textu najděte všechny jeho přesmyčky vyskytující se ve slovníku.
- 43. Amortizace. a) Přičítání jedničky v dvojkové soustavě je klasika, b) ale jak si třeba pořídit čítač, který umí v amortizovaně konstantním čase Inc, Dec a test na nulu? (+Hint: Která situace dělá v a/ "paseku"? Tak jí zabraňte. (De fakto analogické řešení použité i jinde (v knížce).))
- 43.1. Různé způsoby počítání. (Potenciál, účetní metoda, kreditová metoda, ...)
- 43.2. Jaký je rozdíl mezi pojmy průměrná složitost a amortizovaná složitost (a složitost v nejhorším případě, tzv. worst-case).
- 44. Hledání následníků v BVS je vlastně taky amortizace, až na úvodní hledání a prohlubování, tj. hloubku stromu.
- 44.1. Stromy s prstem. Vkládaná/dotazovaná data jsou klastrována. Jak to využít? Taky viz. 8.
- 45. (i DÚ) Navrhněte algoritmus, který v lineárním čase zadaný BVS dokonale vyváží. (Jednodušší to zvládne v čase $O(n)$ a s pamětí $O(n)$, lepší je v čase stále lineární, ale (kromě zadaného stromu) bude potřebovat pouze $O(\log n)$ paměti navíc.)
- 45.1 Samostatně a) linearizace (tj. serializace) stromu, b) rekonstrukce z uspořádaného pole, c) rekonstrukce z uspořádaného seznamu.
- 45.2 Reprezentace stromů (nejen BVS) pomocí závorek '(' a ')'. (I jinde.)
- 45.3 Dokonale vyvážený strom (kde se počet listů v podstromech liší nejvýš o 1) můžeme prohlásit za a) AVL i b) R-B strom. Je to pravda? Jak nastavit další informace ve vrcholech?
- 46. (i DÚ) Obvyklá reprezentace BVS v paměti potřebuje v každém vrcholu 3 ukazatele: na levého syna, na pravého syna a na otce. Ukažte, jak si vystačit se dvěma ukazateli. Původní 3 ukazatele by z těch vašich mělo jít spočítat v konstantním čase. (Co nás to stojí navíc v paměti? Nízkoúrovňové triky/"hacky".)
- 47. Vícedimenzionální stromy, vícedimenzionální klíče: a) strom pro bodový dotaz ve 2D, b) ...
Pozn.: Stromy jsme zavedli a používáme pro 1D data. Používají se i pro vícerozměrná data. Používané dotazy jsou m.j. přesné hledání, intervalové hledání, podobnostní hledání.
- 48. Je zadána množina intervalů na přímce. Spočítejte, kolik je dvojic protínajících se intervalů.
- 49. (Jednodušší) Strom je cesta.
- 50. Písmenové stromy - trie.
- 51. Průměrný případ BVS. (Možná bude)
- 52. (Líné vyvažování, u AVL a R-B.) Vyvažování běží v samostatném vláknu dodatečně. Jaká data si potřebujete pamatovat, aby vyvažování mohlo proběhnout správně? Tj. pokud by se zastavili další změny prvků (Insert, Delete), tak vyvažování upraví strom do přípustného tvaru.
- 52.1. Vypustili jste celý podstrom v AVL nebo R-B stromě. Jak lze strom znovu vyvážit?
- 53. (Jednotný popis AVL a R-B stromů)
- 54. $a-b$-stromy, varianty. Redundantní vs. neredundantní, externí listy, přípravné štěpení a slučování, $B^*$ skupinové štěpení (2 na 3, 3 na 4), $B^+$ provázané.
- 55. Některé úlohy a jejich řešení pomocí stromů (např. počet inverzí v permutaci) jsou analogické metodě Rozděl a panuj řízené daty.
- 56. Komprimovaný medián. (VM) Posloupnost čísel máte zadanou jako seznam dvojic hodnota a počet opakování. Najděte medián. Hodnoty v posloupnosti se nemusí lišit.
- 57. Pro danou posloupnost chceme najít co nejdelší úsek, aby rozdíl libovolných prvků v něm byl nejvýš $k$. (Zopakovany 1/36)

Cvičení 9. (16.4.2019 Rozděl a panuj)

- 1. Jak vynásobit 2 komplexní čísla pomocí 3 reálných násobení (a dalších sčítání).
- Kromě metody analogické násobení dlouhých čísel (ale bez rekurze) se dají použít obdélníky 2x1 a 1x2. Najděte víc a/nebo všechny možnosti.
- 2. Opakování (až synchronizace): Klasické algoritmy a z nich odvozené vztahy. (A další jednoduché alg.) a) binární vyhledávání v uspořádaném poli, b) mergesort, c) stavba vyváženého stromu z uspořádané posloupnosti, d) stavba haldy, shora, e) převod absolutně vyváženého BVS do pole, f) převod např. AVL stromu do pole, strom je s ozdobením, (anebo alg. si předává stav), g) rekurzivní násobení dlouhých čísel, pomocí násobení dvouciferných čísel, h) rekurzivní násobení čtvercových matic, založené na násobení matic $2 \times 2$, i) ...
- 3. Řešení rekurentních rovnic (substituční metodou). Všude $T(1)=1$. $$a) T(n) = 2T(n/2) + O(n^2)$$ $$b) T(n) = 2T(n/3) + O(n)$$ $$c) T(n) = T(n/2) + O(1)$$ $$d) T(n) = T(n/2) + T(n/3) + O(n)$$ $$e) T(n) = T(n/5) + T(7n/10) + O(n)$$ $$f) T(n) = 2T(n/2) + O(n \log n)$$ $$g) T(n) = n^{1/2} T(n^{1/2}) + O(n)$$ $$h) T(n) = T(3n/5) + T(4n/5) + O(n^2)$$ Rozmyslet na příště (23.4.) $$h1) T(n) = T(3n/5) + T(4n/5) + O(n)$$ $$i) T(n) = 3T(n/2) + 4T(n/4) + O(n)$$ $$j) T(n) = T(n/3) + T(2n/3) + O(n)$$ \( % \begin{equation}T(n) = 3T(n/2) + 4T(n/4) + O(n)\end{equation}\) (+trik volby při vyvážení rekurze a režie)
- 4. Hledání $k$-tého nejmenšího prvku lineárně. (možná bylo)
-- 4.1. Co z toho plyne pro quicksort teoreticky a prakticky.
-- 4.2. Lze použít trojice? Lze použít sedmice? Jaké vyjdou rekurence?
- 5. V průměru lineární (randomizované) hledání $k$-tého prvku. (Možná bylo P2018.)
- 6. Počítání inverzí v permutaci (adaptace MergeSortu).
- 6.a Počítání inverzí v permutaci. Jde algoritmus založit na quicksortu?
- 7. Je dáno pole A[1..n] obsahující ostře rostoucí posloupnost celých čísel. Jak v čase $O(\log n)$ zjistit, jestli existuje $i$: $A[i]=i$?
-- 7.1. Totéž pro matici s rostoucími řádky i sloupci, v níž hledáme $i$, $j$ takové, že $A[i,j] = i+j$.
- 8. Násobení dlouhých čísel (?Př2018)
-- 8.1. Při násobení dlouhých čísel jeden z podproblémů není $N/2$-ciferný, ale $(N/2+1)$-ciferný.
-- 8.1a. Vymyslet, jak algoritmus upravit, aby generoval pouze $N/2$-ciferné podproblémy.
-- (8.1b) Dokázat, že to složitost neovlivní.
- 9. Upravit Strassenův alg. pro dosažitelnost v grafech, tj. tranzitivní uzávěr. (+rychlé umocňování)
-- 9.1. Proč nejde přímo použít pro počítání s boolovskými hodnotami?
- 10. Uveďte algoritmy, které odpovídají jednotlivým případům z master teorému
- 11.a) Kolik je tvarů binárních stromů (zakořeněných, nevyhledávacích) s $n$ vnitřními vrcholy? Napište rekurzivní vztah. b) Kolik je formulí s $n$ výskyty binární spojky $and$ nad pevnou proměnnou $z$ v listech. c) Totéž, nad konstantami $True$ a $False$. d) Totéž, celkem $n$ výskytů binárních spojek $and$ a $ or $ a unární $not$ nad $k$ různými proměnnými. e) Dokážete spočítat počet neizomorfních stromů? Když strom získám výměnou levého a pravého podstromu v libovolných vrcholech, tak je izomorfní. (f) Uměli by jste vygenerovat všechny stromy z a), v nějaké vhodné reprezentaci?
-- Pozn. Výpočet konkrétních hodnot zdola pomocí dynamického programování.
- 12. Umíte zdůvodnit, že problém násobení matic je $\Omega(n^2)$. Tj. dolní odhad. (P2020)

- 90. DÚ kandidát. Šroubečky a matičky: máme $N$ různých šroubečků a $N$ odpovídajících matiček. Umíme pro dvojici (šroubeček, matička) rozlišit stavy "pasují", "šroub moc velký", "šroub moc malý". Vymyslete, jak šrouby s matičkami co nejrychleji spárovat. (Randomizovaně vs. deterministicky.)
- 90.1. DÚ kandidát, varianta. Může se stát, že některé šroubky a/nebo matičky nemají pasující protikus. Chcete utřídit podle velikosti kromě nalezení párů.
- 91. DÚ kandidát. Násobení dlouhých čísel $X=A.p+B$ a $Y=C.p+D$. a) Navrhněte vztahy a algoritmus, který využije $(A-B)(C-D)$ pro rekurzivní volání místo $(A+B)(C+D)$.
b) Nějaký trade-off?

Další:
- 31. Jak implementovat MergeSort bez rekurze?
- 32. Může být umocnění čísla na druhou efektivnější než násobení?
- 33. Jak vypadá strom rekurze při dělení na různě velké podproblémy?
- 34. Napište odhad velikosti matice, pro které se vyplatí použít Strassenovo násobení matic místo počítání podle definice. (Odhad můžete spočítat nebo algoritmy naprogramovat a prakticky vyzkoušet.) Pro jednoduchost uvažujte pouze čtvercové matice.
- 35.^ Lineární alg. pro medián. a) Lze dělit posl. na trojice, sedmice? b) Jak vyjde rekurzivní vztah?
- 36. Hledání nejbližší dvojice bodů v rovině (viz http://ksp.mff.cuni.cz/tasks/19/solution2.html#task5)
- 37. Úloha o telefonních kabelech (PLA 10.9.cv1/257, KSP 8-5-2, "Telefon do pekla", viz http://ksp.mff.cuni.cz/tasks/8/tasks5.html#task2) Máme kabel, který obsahuje $n$ drátů. (Update: dnes už i optických.) Víme, že levé a pravé konce jsou spárovány 1:1. Povolené operace jsou: 1) přivést napětí na konkrétní drát na levém konci, 2) odpojit napětí z konkrétního drátu na levém konci, 3) změřit napětí na pravém konci. Navrhněte algoritmus, který zjistí propojení drátů vlevo a vpravo. Snažte se o efektivitu, tj. minimalizovat počet operací.
- 37.1 Existuje neadaptivní řešení? Tj. postup, kdy měření nezávisí na výsledcích předchozích měření?
- 37.2 Jak spočítat dolní odhad? (I jinde: 10. Třídění)
- 38. Rychlé násobení matic s jinou strukturou mezivýsledků. Znaménka můžeme volit pro jednotlivá místa zčásti nezávisle, asi 32 možností, z $2^8$. Ale na jednom místě používáme vždy stejné znaménko. Reprezentace: první matice: velká 2x2, druhá matice: malé 2x2. (Reprezentace: obě matice po řádcích, jinak než na předn.)

++++  =  ++ * ++   M1
-.-.     +.   -.
++..
-...

....  =  .. * .+   M4
....     +.   ..
.+..
....

++++  =  ++ * ++   M2
....     ..   ..
....
....

+...  =  +. * +.   M3
-...     +.   -.
+...
-...

....  =  ++ * ..   M5
+.+.     ++   +.
....
+.+.

..++  =  .+ * ++   M6
..--     ..   --
....
....

....  =  .. * ..   M7
....     .+   .+
....
...+


V1= (-1)*(M1-M4)-M2-M3 ;V11+V23 
V2= (M1-M4)-M2+M5 ; V31+V43
V3= (M1-M4)-M3-M6 ; V12+V24
V4=  M4+M7        ; V32+V44
Společný podvýraz M1-M4 počítáme jen jednou. Alg. používá méně "režijních" sčítání a odčítání (16?) než Strassenův alg. z přednášky.
- 39. a) Klasický Strassenův alg.
- b) Proč nejde (přímočaře) použít na hledání dosažitelnosti?
- c) Jak docílit toho, aby použít šel?
- d) formule: $\left( \begin{array}{ c c } A & B \\ C & D \end{array} \right) \cdot \left( \begin{array}{ c c } I & J \\ K & L \end{array} \right) = \left( \begin{array}{ c c } V_1 & V_2 \\ V_3 & V_4 \end{array} \right) $, kde
$V_1 = M1+M2-M4+M6$,
$V_2 = M4+M5$,
$V_3=M6+M7 $,
$V_4=M2-M3+M5-M7$, a dále
$M1=(B-D)\cdot(K+L)$ = T7,
$M2=(A+D)\cdot(I+L)$ = T1,
$M3=(A-C)\cdot(I+J)$ = -T6,
$M4=(A+B)\cdot L$ = T5,
$M5=A\cdot(J-L) $ = T3,
$M6=D\cdot(K-I)$ = T4,
$M7 = (C+D)\cdot I$ = T2
Platí $V_1 = AI+BK$, $V_2 = AJ+BL$, $V_3= CI+DK$, $V_4=CJ+DL$.

- 40. Tvorba fraktálů. a) (TODO: jmého křivky) Fraktál tvoříme tak, že z úsečky délky $x$ odebereme prostřední třetinu, nahradíme ji ostatními dvěma stranami rovnostranného trojúhelníka (směrem lokálně nahoru) a na vzniklé 4 úsečky třetinové délky použijeme tvorbu fraktálu rekurzivně. a1) Napište rekurentní vzorec pro složitost tvorby fraktálu (např. jakoby jste fraktál kreslili pomocí želví grafiky) a2) Vyřešte vzorec pomocí Master Theoremu. Exponent ve výsledku odpovídá (neceločíselné) dimenzi fraktálu.
- b) Cantorovo diskontinuum. Z úsečky zahodíme (vnitřek) prostřední třetiny a na zbylé dvě třetiny opakujeme postup rekurzivně. Stejné otázky, i dále.
- c) Plochu čtverce rozdělíme pravidelně na 2x2, dolní pravou čtvrtinu zahodíme a na ostatních 3 částech postupujeme rekurzivně. To odpovídá rychlému násobení dlouhých čísel.
- 41. (PLA 10.3.cv5/244) Násobení dlouhých čísel, dělení na 3 části a 5 součinů. Platí $\log_3 5 \approx 1,465$.
- 41.1 Varianta: místo W3 nebo W4 máme součin $X_2 Y_2$
- 41.2 (PLA 10.3.cv6/244) Zobecnění: dělení čísel na $r+1$ částí a rekurzivní počítání $2r+1$ součinů, pro $r\ge 1$.

Cvičení 10 (Dynamické programování, 11.5.2020 cv. 13)

- 1. Opakování pojmů: Stavový prostor, optimální podstruktura, společné podproblémy (překrývající se podproblémy), tabelace - pamatuju si optimální hodnoty (a rozhodnutí/optimální řešení (kompaktně)), počítání shora dolů a zdola nahoru (a trade-off), ...
- 1.1 A techniky: graf závislostí na stavovém prostoru (DAG), rekonstrukce optimálního řešení z tabulky, šetření paměti (někdy, podle grafu závislostí), pro postup zdola nahoru může být víc možností, ...
- 2. Známé příklady: Fibonacciho čísla, Floydův-Warshallův alg. (počítá všechny min. cesty v grafu), rychlá Diskrétní Fourierova Transformace (bude v ADS2), násobení matic (viz), optimální vyhledávací strom (P2020 volitelně), ...
- 2.1 Popište pojmy a techniky pro známé příklady.
- 3.a (knížka PLA) Nejdelší rostoucí podposloupnost. (Lze i $O(n \log n)$.) Je dána posloupnost $x_1, \dots, x_n$ celých čísel. Chceme najít posloupnost indexů $i_1, i_2, \dots, i_k$ takovou , že $1\le i_1 \lt i_2 \lt \dots \lt i_k \le n$ a $x_{i_1} \le x_{i_2} \le \dots \le x_{i_k} $.
- 3.a1 Co je optimální podposloupnost, od začátku do $x_i$? (Nápověda: co je neoptimální posloupnost?). Dvě kriteria: Paretovo optimum.
- 3.b Nejdelší "kopec": rostoucí a potom klesající podposloupnost. Některá z částí může být "jednoprvková". Jaký je stavový prostor?
- 3.c Nejdelší podposloupnost s daným profilem: maximální počet stoupání a klesání.
- 4. Počet nejdelších rostoucích podposloupností.
- 5.a Nejdelší společná (pod)posloupnost pro dvě vstupní posloupnosti.
- 5.b Varianty: i) s cenou za výměnu (BIOINF), ii) pro víc než dvě vstupní posloupnosti. (BIOINF)
- 5.b.iii) s cenou za mezeru (tzv. "gap", BIOINF); dva způsoby popisu: 1. První vložený nebo vypuštený znak má jinou cenu než další stejné operace. 2. Každý vložený nebo vypuštěný znak má stejnou cenu, ale je penalizace za celou skupinu stejných operací INS a DEL.
- (5.c) Lze základní úlohu popsat jako úlohu editační vzdálenosti s jinou množinou operací?
- 5.d Zahrnutí dalších operací: 1) SWAP: výměna dvou sousedních znaků, 2) SUPERSWAP: "abc" na "cba".
- 6. Nejkratší společná nadposloupnost (také zvaná superposloupnost).
- 7. (v Progr.) Nejlepší násobení matic. Je dána posloupnost matic a máme zjistit jejich součin. Chceme najít uzávorkování matic tak, aby celková složitost násobení byla co nejmenší.
- 8. Nejkratší triangulace $n$-úhelníka. Je dán konvexní $n$-úhelník. Máme najít neprotínající se úhlopříčky s co nejkratším součtem délek, které rozdělí $n$-úhelník na trojúhelníky.
- 9. Optimální (binární) vyhledávací strom. (P2020možná)
- 10.a Máme posloupnost ohodnocených položek. Chceme vybrat co podposloupnost s co největším součtem tak, že žádné dvě vybrané položky nejsou vedle sebe. Jaký je stavový prostor?
- 10.b Varianta: Vybíráme podposloupnost, která má nejvýš dvě položky vedle sebe.
- 11.1 Součet podmnožiny. Optimalizační verze. Je dána množina $n$ předmětů s celočíselnými hmotnostmi $h_1, \dots, h_n$ a přirozené číslo $b$ jako nosnost batohu. Hledáme $P\subseteq \{1,\dots,n\}$ takovou, že $S=\sum_{i\in P} h_i \le b$ a přitom $S$ je největší možný součet.
- 11.2 Součet podmnožiny. Rozhodovací verze. Stejná vstupní data a chceme zjistit, zda existuje $P$, pro které $\sum_{i\in P} h_i = b$.

- 90. DÚ kandidát

Další:
- 31. Odvození slova v bezkontextové gramatice. Existence řešení: mít odvození je lepší než nemít odvození.
- 32. Vyhrávající strategie ve hře dvou hráčů s úplnou informací (transpozice a transpoziční tabulky)
- 33. Nejdelší cesta v (nezáporně ohodnoceném) grafu. Hint: opravdu cesta. Hint2: Stavový prostor není polynomiální. ((Bellman-)Held-Karp alg.)
- 34. Druhy úloh: a) Nalezení ceny optimálního řešení, b) Nalezení/rekonstrukce optimálního řešení, trade-off: pamatujeme si optimální rozhodnutí (lokálně a kompaktně) nebo rekonstruujeme ze zapamatovaných cen, c) existence řešení (vs. neexistence), d) počet optimálních řešení.
- 34.1 Optimalizace paměti: (trade-off čas vs. paměť) Zapamatování řešení (optimálních rozhodnutí) vs. rekonstrukce (když potřebujeme) vs. pouze hodnota opt. řešení (můžeme zapomínat, podle závislostí ve stavovém prostoru)
- 34.2 Stavový prostor nemusí být polynomiální. Diskrétní vs. spojité DP, deterministické vs. pravděpodobnostní DP.
- 34.3 S hladovými algoritmy sdílí DP vlastnost optimální podstruktury. S metodou rozděl a panuj sdílí DP rozdělení na podproblémy a skládání výsledku. Jednotlivé konkrétní úlohy můžou mít efektivnější algoritmus než "generické" procházení stavového prostoru. Např. a) při stavbě optimálního BVStromu pro dané frekvence nemusíme procházet všechny volby. b) při hledání nejdelší rostoucí posloupnosti můžeme použít jinou strukturu než pole.
- 35. Optimální dělení na úseky v QR kódech.
- 36*. Bellova čísla. Viz 4/58h (a 8/58?)
Jaký je počet rozkladů $n$-prvkové množiny na třídy ekvivalence. Napište rekurzivní vztah.

Cvičení 11. (Třídění 18.5.2020 cv14)

- 1. Radix sort, příklad. Utřiďte: 112, 311, 412, 232, 322, 144, 132, 231
- 2. Counting sort. Proč kopírujeme data ze vstupu, když hodnoty můžeme zrekonstruovat z pomocného pole?
- 3.a) Průměrný případ Quicksortu. Vybíráme vždy pseudomedián (prvek v prostředních dvou čtvrtinách), nejhorší případ. Jaké bude chování alg. b) Kolik kroků potřebujeme v průměru na výběr pseudomediánu? c) Pivot rozdělí posloupnost vždy 1:99. Jaká bude asymptotická složitost?
- 4. Lexikografické třídění nestejně dlouhých a) čísel a b) řetězců. Jak je doplnit?
- 5. (Rozhodovací stromy.) a) Jak se ve stromě projeví, pokud algoritmus zopakuje porovnání některé dvojice prvků? b) Jak se ve stromě projeví, pokud výsledek některého porovnání je vynucený? (Uveďte příklady, kdy to může nastat.) c) Jsou všechny listy rozhodovacího stromu dosažitelné?
- Pozn.: Pojem "rozhodovací strom" se v umělé inteligenci obvykle používá pro jinou strukturu a jinou úlohu.
- 6. Jako pivota v quicksortu vybíráme prostřední prvek ze tří (vybraných rovnoměrně náhodně), deterministicky. Jak se změní pravděpodobnost výberu pivota (vůči rovnoměrnému náhodnému výběru) pro prvek a) krajní, b) druhý krajní, c) medián?
- 7. Stabilní třídění. Jak zajistit pro nestabilní algoritmus, aby třídil stabilně? (Ne nutně na místě.) *P2019*
- 7.1 Pozn. Stabilní třídění zachovává u stejných prvků pořadí ze vstupu na výstupu.
- 7.2 Pozn. Třídění "na místě" používá pouze O(1) pomocné paměti. Které třídící algoritmy (založené na porovnávání) třídí na místě?

- 90. DÚ/2019 a,b) Jako pivota vybíráme prostřední prvek ze tří.
- a) S jakou pravděpodobností se trefíme pivotem mimo prostřední třetinu?
- b) A mimo dvě prostřední čtvrtiny?
- c) Za předpokladu, že pivot vyšel v dolní třetině, jaká bude jeho střední hodnota (tj. průměr)?
- 91. DÚ kandidát. Counting sort, sousměrně. Upravte Countingsort (ve variante s kopírováním), aby v posledním průchodu procházel vstupní data v pořadí zvyšujících se indexů. (Motivace: čísla přicházejí po síti, z komprimovaného archivu, z magnetické pásky; prostě pořadí určuje dodavatel) ! Pozn. MM v knížce (PLA) tuto verzi Counting sortu nemá.

Další:
- 31. Pole vzniklo náhodným rovnoměrným výběrem každého prvku z {1,...,k} a následným utříděním. Jak tuto informaci využít pro rychlejší vyhledávání, v průměru?
- 32. Quicksort s náhodnou volbou: Střední hodnota časové složitosti je $\Theta(n \log n)$. (Možná bylo.) (Pomocí linearity střední hodnoty.) Počítání, kolika podproblémů se jednotlivý prvek zúčastní.
- 33. Quicksort, lokalita přístupu do paměti. (Využití keše. Cache-oblivious algoritmy: využívají keš, u které nevíme, jak je velká.)
- 33.1 Porovnání s jinými třídicími algoritmy. (mergesort, heapsort, zatřiďování, ...)
- 34. Lokalita přístupu do paměti, jiné třídící algoritmy.
-- 34.1. Při rekurzivním dělení se malé podproblémy vejdou do keše $\to$ zrychlení.
- 35. (z PLA) Zdůvodněte, že libovolný deterministický algoritmus pro vyhledávání v $n$-prvkovém uspořádaném poli potřebuje v porovnávacím modelu v nejhorším případě $\Omega(n)$ porovnání.
- 36. Terminologie/jiná, z knižky MM (PLA): a) Countingsort: třídění klíčů bez dodatečné informace (a bez kopírovacího průchodu :-( ), b) Bucketsort: s přihrádkami a pointry, i stabilní verze, c) Lexikografický bucketsort, d) Radixsort, číslicové třídění: polynomiálně velká čísla (k počtu $n$) třídí lineárně, při základu $n$, e) Třídění řetězců, s dynamickým přidáváním podle délky
- 37. Jak dopadne složitost mergesortu při dělení na víc než dvě části? (I rozděl a panuj)
- (37.1) Externí třídění (dříve: na magnetických páskách), (dnes:) data se nevejdou do operační paměti (na disku, často sekvenční). Běhy; předzpracování v paměti, trik: průběžný flush, desynchronizované pásky.
- 38. PLA 10.9.cv3, Viz 9.37 (Spletitý kabel, Telefon do pekla) Dolní odhad složitosti.

Cvičení 12. (7.5.2019 Hašování)

- 1. Opakování hašovacích funkcí.
- 2. Jiné použití hašovacích funkcí než hašovací tabulka.
- 3. U řetízků jsme špatně odhadli velikost tabulky a vyšla nám velká zaplněnost a dlouhé řetízky. Má smysl kombinovat hašování s vyhledávacími stromy jako prevenci proti tomuto případu?
- 4. U otevřené adresace, s lineární funkcí, a) má význam použít jiný krok $k$ než $1$? Výhody, nevýhody. b) Jsou všechny hodnoty $k$ vhodné?
- 5.a) Vysvětlit primární klastrování (u lineární adresace). b) Máme z poloviny zaplněnou tabulku ($\alpha=0.5$). Jaké jsou extrémní případy klastrování. Jaká pro ně vyjde průměrná složitost vkládání? c) Vysvětlit druhotné klastrování (u kvadratické adresace). d) Jaká je očekávaná délka řetízku při otevřené adresaci při naplnění $\alpha$ (při ignorování klastrování)?
- 6. Jaká je paměťová režie jednotlivých metod? (Hlavně řetízky vs. otevřená adresace.) Máme $l$ buněk na režii - jak velkou tabulku si můžeme dovolit? (Data jsou obvykle stejně mimo tabulku.)
- 7. Paradox narozenin. Hašujeme do tabulky velikosti 366 podle data narození. Při kolika lidech pravděpodobnost nějaké kolize převýší 0.5? ($\to$ první konflikty vznikají brzo) (Měli jste indikátorovou metodu na diskrétní matematice?)
- 8. Implementace pseudodelete.
- 9. Zvětšování tabulky, např. na dvojnásobek (s vhodnou volbou haš. fce). Celkový čas přehašování?
-- 9.1. Zmenšování tabulky. Jak se vyhnout opakovanému přehašovávání na hranici?
-- 9.2. V tabulce je mnoho neplatných prvků (po pseudodelete). Co s tím?
-- 9.3. Implementačně: Přehašování dávkové ("zastav svět") vs. inkrementální. Porovnání? (Pro analýzu dávkového přehašování se používá amortizovaná složitost.)
- 10.a) Vysvětlete "konkurenční" výhodu univerzálního hašování. b) Přes co se počítá průměr u klasického hašování a u univerzálního hašování?
- 11. Porovnávání podobných sekvencí. a) Navrhnout metodu. b) Jak maskovat (aspoň trochu) přehození písmen? (Apl: BINF, plagiáty)

- 90. DÚ kandidát. Vypouštění při otevřeném adresování s lineární adresací. Implementovat skutečné Delete místo Pseudodelete. (Rychle a správně.)

Další:
- ad 90. DÚ (Která vlastnost lineární adresace umožňuje implementaci Delete?)
- 31. Bloomův filtr.
- 32. a) Univerzální hašování: xor místo sčítání a modulo. b) Rychlé přepočítání haše při malé změně dat. (Hašování pozic her.)
- 33. (Dva způsoby počítání ceny za vložení při přehašování, které vyjdou různě. Vysvětlete.)
- 34. Jak navrhnout dokonalé/perfektní hašování, pro pevná data (dříve: index na CD/DVD).
- 35. Máme dvě množiny přirozených čísel $S = \{s_1, ..., s_m\}$ a $T = \{t_1, ..., t_n\}$. Navrhněte algoritmus, který zjistí, zda je $S$ podmnožinou $T$. Řešte v lineárním čase.
- 36. Uvažujte dvojité hešování ($f(x) = (h(x) + i*g(x)) \mod m$) bez funkce Delete. Každá přihrádka $j$ má navíc počítadlo $c_j$, které určuje počet prvků v tabulce, pro které platí $h(x) = j$. Jak toto počítadlo využít pro zrychlení neúspěšných vyhledávání v tabulce? Napište příklad, kdy je toto zrychlení veliké.
- 37. Jak a kdy přesouvat při otevřeném adresování prvky blíž k počátku řetízku, tj. k správné pozici?
- 38. Hledání podobných promotorů. (BINF, apl. hašování)

Cvičení 13. (14.5.2019 )

Virtual/nekoná se (2019)

todo

Další:

Cvičení 14. (21.5.2019 Algo. lin. alge.)

- 1. Euklidův alg., s dělením 2 pro sudá čísla. Dokažte, že následující algoritmus je kompletní a korektní. (zastaví se a vrátí největšího společného dělitele čísel $a$ a $b$)

nsd(a,b)
if (a==b) --> return a
else if (a mod 2 == b mod 2 == 0) --> return 2*nsd(a/2,b/2)
else if (a mod 2 == 0) --> return nsd(a/2,b)
else if (b mod 2 == 0) --> return nsd(a,b/2)
else if (a>b) --> return nsd(a-b,b)
else --> return nsd(a,b-a) 

- 2. (úvodní) Počítání největšího společného dělitele. (Velikost vstupu potřebujeme měřit jinak než počtem vstupních čísel.) ; (+varianta algoritmu) ; (Nejhorší případ? - bude)

- 90. DÚ kandidát.

Další:


Poznámky k přednášce 5.5.

- Získání a rekonstrukce řešení:

  1. Někdy stačí optimální hodnota, nemusíme rekonstruovat řešení.
  2. Zapamatovat si celé řešení. Obvykle paměťově náročné.
  3. Zapamatovat si optimální lokální rozhodnutí. Na celé řešení doplníme ze stavu, kam vede lokální rozhodnutí. Př.: Ve F.-W. alg. bychom si pamatovali nejvyšší číslo vrcholu na optimální cestě nebo "escape"-hodnotu (0, -1, NIL) pro přímou hranu. Použitý způsob zapamatování předchozího vrcholu na cestě byl varianta tohoto přístupu.
  4. Dopočítat lokální optimální rozhodnutí z optimálních hodnot pomocí Bellmanovych rovnic. Potřebujeme si pamatovat potřebné (až všechny) optimální hodnoty. Tento způsob dovoluje získat víc nebo všechny optimální řešení. případně spočítat počet optimálních řešení.
  5. Pokud potřebujeme počty optimálních řešení, můžeme je počítat průběžně jako další složku výsledků nebo dopočítat z Bellmanovych rovnic.

Hladové alg. (min. kostra) a dynamické programování. ; Počítání zdola a zhora.


Změny a volitelné 2020: TODO \\+ Detekce mostů, (bez artikulací) \\? SSK, asi ano \\? Floydův-Warshallův alg., příp. u DP ANO2020, u DP \\+ Borůvkův alg. \\? Kruskalův alg. a Union-Find NE2020 \\+ a-b stromy, varianta \\? Červeno-černé stromy NE2020 \\+ Dynamické programování \\- Lin. alg. na medián cvic2020 \\(Lineární třídění, v Progr.2) \\

Pořadí témat 2020, předběžné, nový sylabus:
\\- Prostředky pro popis složitosti 1: 1
\\- Základní grafové alg. 1: 2-3
\\- Min. cesty 2: 4-5
\\- Min. kostry 1: 6
\\- Stromové struktury 1,5: 7-8
\\- Hašování 1: 9
\\- Rozděl a panuj 2,5 :10-11
\\- Dynamické programování 1: 12+
\\- Třídění 1: 13+
\\- - Celkem: 12P:...

Pořadí témat 2019:
\\- Prostředky pro popis složitosti 0,5:1
\\- Základní grafové alg. 2:2-3
\\- Min. cesty 2:4-5
\\- Min. kostry 1,5: 6
\\- Stromové struktury 1,5:7
\\- Rozděl a panuj 2:8-9
\\- Třídění 1,5:10+
\\- Hašování 1:11+
\\- Lin. Alg. 1:12+
\\- - Celkem: 13P:...

Minulé DÚ 18/19

DÚ1 cv1/19.2.: tranzitivita O: $f \in O(g) \land g \in O(h) \to f \in O(h)$
cv1, na rozmyšlení: 2/38a)
DÚ2 26.2.: cv4/10 Nejdelší cesta ve stromě
DÚ3 5.3.: cv4/90 Největší housenka ve stromě
cv3, na rozmyšlení: cv5/93 Polosouvislý graf
DÚ4 19.3.: cv6/90 Cesta ve čtverečkovaném bludišti s klíči
DÚ5 2.4.: cv7/90 Úprava min. kostry po změně hrany
DÚ6 9.4.: cv8/90 $k$-tý prvek v BVS (index($k$))
DÚ7 30.4.: cv10/90a,b Při výběru pivota jako mediánu ze tří, s jakou pstí bude mimo a) prostřední třetinu, b) prostřední dvě čtvrtiny?
DÚ8 .7.5.: cv12/90 poslat/písemně

DÚ pro externisty/2019: 1/35.1 tranzitivita "O" ; 4/90 Housenka; 4/91a robůtci v bludišti; 4/51a orientace hran ; 5/92 #nejkr. cest v DAGu; 6/13a,b,c;ideu pro d; superman v grafu; 7/90 změna hrany v kostře; 8/90 k-tý v BVS; 9/3e,h1, e-lineární, h1-kvadratické; 9/91 násobení dl.č. s rozdílem, 10/90 pseudomedián ze tří; 12/90 Delete při lineární adresaci
OPAK
tranzitivita O: $f \in O(g) \land g \in O(h) \to f \in O(h)$
cv1, na rozmyšlení: 2/38a)
DÚ2 2.3.2020: cv4/10 Nejdelší cesta ve stromě
DÚ3 5.3.: cv4/90 Největší housenka ve stromě
cv3, na rozmyšlení: cv5/93 Polosouvislý graf
DÚ4 19.3.: cv6/90 Cesta ve čtverečkovaném bludišti s klíči
DÚ5 2.4.: cv7/90 Úprava min. kostry po změně hrany
DÚ6 9.4.: cv8/90 $k$-tý prvek v BVS (index($k$))
DÚ7 30.4.: cv10/90a,b Při výběru pivota jako mediánu ze tří, s jakou pstí bude mimo a) prostřední třetinu, b) prostřední dvě čtvrtiny?
DÚ8 .7.5.: cv12/90 poslat/písemně

DÚ pro externisty/2019: 1/35.1 tranzitivita "O" ; 4/90 Housenka; 4/91a robůtci v bludišti; 4/51a orientace hran ; 5/92 #nejkr. cest v DAGu; 6/13a,b,c;ideu pro d; superman v grafu; 7/90 změna hrany v kostře; 8/90 k-tý v BVS; 9/3e,h1, e-lineární, h1-kvadratické; 9/91 násobení dl.č. s rozdílem, 10/90 pseudomedián ze tří; 12/90 Delete při lineární adresaci
(LS 2018: Pokud nemáte dost bodů, vyřešte jako náhradní příklady kandidáty na DÚ, ty od cv. 4 dále, které jsme neprobírali. Každý (správně vyřešený) příklad je za 2 body, které vám chybí.)

Dynamické programování: TODO zapojit do cviceni
- 1. Nejdelší rostoucí podposloupnost. (Varianta: jen její délka.)
-- 1.1 Jak si průběžně pamatovat možné výsledky? (Technika i jinde.)
- 2. Nejdelší rostoucí a pak klesající podposloupnost. (tzv. kopec) Části můžou být prázdné.
-- 2.1 Nejdelší kopec nebo údolí.
-- 2.2 Nejdelší podposloupnost s daným profilem.
- 3. Nejdelší podposloupnost s povolenou diferencí a) obousměrně, b) jednosměrně.
-- (3.1 ... s povoleným profilem diferencí.)
- 4. Posloupnost dané délky s největším rozpětím.
- 5. Podposloupnost s největším součtem, přičemž nesmíme vybrat dvě sousední čísla. (Motivace?)
- 6. Nejdelší společná podposloupnost (i přednáška?)
-- 6.1 Varianty pro různé druhy povolených odchylek/chyb.
- 7. Nejkratší společná nadposloupnost. a) Dány dva řetězce $x$ a $y$, hledáme co nejkratší řetězec $s$, aby oba $x$ a $y$ byly vybranými podřetězci $s$. b) I pro víc vstupních řetězců.
- 8. Klasické příklady: Fibonacciho čísla, Problém batohu, ...
- 9. Klasické techniky: rekurze vs. převod na iteraci - tj. počítání zdola, tabelace, boolovské výsledky - tj. existence řešení, rekonstrukce řešení a Bellmanovy podmínky optimality.
- 10. (Implicitní graf, prohledávání stavového prostoru) Také ^cv4/57
Dokázat, že na problém batohu hladový přístup nefunguje. Problém batohu (jedna z formulací: "Součet podmnožiny", optimalizační): Máme předměty o váhách $v_1, ... , v_n$ a batoh s nosností $b$. Chceme zaplnit batoh co nejvíc.
-- 10.1. Předměty mají navíc cenu $c_i$. Chceme batoh s nejvyšší cenou. Funguje hladový přístup?
-- 10.2. Předměty mají cenu a jsou dělitelné. Funguje hladový přístup?
--

Slovníček
d.s.: datová struktura
BÚNO: Bez újmy na obecnosti
SSK: Silně Souvislé Komponenty
MST: Minimal Spanning Tree, minimální kostra
DAG: Directed Acyclic Graph, orientovaný acyklický graf
BVS: Binární Vyhledávací Strom
Řecká písmena: ...


Nástroje

    Pro kopirovani;
  1. z webu: ... -------------------- test, $\tt OK$ HTML: •   & < > ≤ ≥ ; / \ Příliš žluťoučký kůň úpěl ďábelské ódy. áäčďéěíĺľňóö_o_řŕšťúůýž