Příklady ADS1
(LS 2023/24)
Podmínky zápočtu: každá DÚ je za obvykle 25-30 bodů, celkem 150 bodů. Na zápočet máte mít 2/3 bodů z možného počtu, tj. 100b.
Standardně máte 1 týden, tj. odevzdat před dalším cvičením pomocí Moodle.
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 a/nebo konstrukce, b) pseudokód algoritmu (u pseudokódu je
menší pravděpodobnost, že ho popíšete neúplně a/nebo s chybou), c) zdůvodnéní správnosti alg. a/nebo konstrukce,
d) rozbor složitosti alg.
verze 4.4.4
( 4.3: 1.3.2023, 3.3.2 , 16.5.2020; .. 2.14.3)
Domácí úlohy přes Moodle https://dl1.cuni.cz/course/view.php?id=9559.
(Cvičení přes Zoom, https://matfyz.zoom.us/j/... )
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. (Úvodní příklady) O-notace
Pokud je cvičení před přednáškou.
- úvod (kde jsou materiály, podmínky zápočtu)
- 1. (z knížky PLA) 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 délky $n$: 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
- 2.1 pozn.: Pro přímočarý/naivní algorimus, kolik je (asymptoticky) a) spojitých podposloupností,
b) vybraných podposloupností,
c) posloupností s jednou dírou? (Následně každou získanou posloupnost délky $k$ zpracujeme.)
- 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)$ (s využitím konvoluce),
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.
-- 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)$
90. Kandidát DÚ: Na vstupu je text složený z písmen české abecedy a mezer. Vymyslete algoritmus, který
najde nejdelší úsek textu, v němž se žádné písmeno neopakuje.
91. Kandidát DÚ: Na vstupu je text složený z písmen české abecedy a dalších znaků. Vymyslete algoritmus, který
najde nejkratší úsek textu, který obsahuje všechna písmena abecedy. (Malá a velká písmena se nerozlišují.)
80. Pro Bioinf. (používám zkratku BINF): ... TODO
Problémy a oblasti: ??Q
Podle: Neil C. Jones, Pavel A. Pevzner: An Introduction to Bioinformatic algorithms. 2004, MIT Press.
Mapování DNA: úplné prohledávání ; sekvenace DNA: grafové alg. ; porovnávání sekvencí: dynamické programování,
rozděl a panuj, kombinatorické porovnávání se vzorem (pattern matching) ; predikce genů: dynamické programování ;
hledání signálů: úplné prohledávání, hladové alg., HMM/Hidden Markov Models, randomizované alg. ;
identifikace proteinů: grafové alg. ; analýza opakování: kombinatorické porovnávání se vzorem ;
DNA Arrays: grafové alg. ; přeuspořádání genomu: hladové alg. ; molekulární evoluce: klastrování a stromy.
V opačném směru, kromě 1:1. Úplné prohledávání: mapování DNA, hledání signálů ; hladové alg.: hledání signálů,
přeuspořádání genomu ; dynamické programování: porovnávání sekvencí, predikce genů ; grafové alg.: sekvenace DNA,
identifikace proteinů, DNA Arrays ; kombinatorické porovnávání se vzorem: porovnávání sekvencí, analýza opakování.
Další:
- 30. V rostoucí posloupnosti přirozených čísel najít první číslo $n$, které tam chybí. (Uložené v poli, můžeme indexovat.)
-- naučit: "kapitánský krok", $O(\log n)$, kde $n$ je výsledek
- 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. PLA 1.4:5 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ů.
- 32.5a Chcete spočítat Fibonacciho čísla se stejným rekurzivním vztahem pro jiné počáteční hodnoty $f_0$ a $f_1$. Jaké máte možnosti?
- 32.5b To samé, ale máte v knihovně rychlý a optimalizovaný alg. na počítání "klasických" Fibonacciho čísel.
Jak ho použít, aby jste dostali alg. pro obecnou úlohu se stejnou složitosti?
- Aplikace převoditelnosti (bude i v ADS2) a lineární algebry.
- 33. Máme mrakodrap s $n$ patry a $ k$ "ideálních" 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ší
spojitou podposloupnost se součtem $k$. (Lehčí var.: nějakou/první)
- 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$.
- 34.4 (Druhotné kritérium) Posloupnost obsahuje i 0. Hledáme podp. s daným součtem $k$ a z nich co nejkratší.
- 34.5* Varianta: vybraná podposloupnost z kladných čísel se součtem $k$, b) A druhotně co nejdelší.
- 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$.
- 38. Rekurzivní hádanky. Co počítají jednotlivé funkce?:
f(x,y):
if x==0 => return y
else => return f((x&y) << 1, x^y)
g(x,y):
if y==0 => return 0
else if even(y) => return 2*g(x, y/2)
else => return 2*g(x, y/2) + x
h(x,y):
if x return (0,x)
else:
(a,b) <- 2*h(x/2, y)
if odd(x) => b <- b+1
if b>=y => a <- a+1, b <- b-y
return (a,b)
d(x,y):
if x==y => return x
if even(x) and even(y): return 2*d(x/2, y/2)
if even(x): return d(x/2, y)
if even(y): return d(x, y/2)
if x>y: return d(x-y, y)
else: return d(x, y-x)
- 39. (MM) Operace na dlouhých $n$-ciferných číslech a) sčítání, b) odečítání, c) přičítání jedničky,
d) $k$-krát opakované přičítání jedničky, e) odečítání jedničky, f) $k$-krát opakované odečítání jedničky, g)
násobení, h) (celočíselné) dělení, tj. div, i) mod, j) shifty, k) bitové operace and, or, not,
l) boolovský skalární součin a test na 0, m) obecný skalární součin (jinde).
- 40. Největší součet v matici. (Také DP.) Máte danou nezápornou matici m * n. (Pro experty: libovolnou, i se zápornými čísly.)
Sousedi jsou ve (max.) 4 směrech. (Pro experty, v 8 směrech).
Začínáte vlevo nahoře, končíte vpravo dole. Hledáte cestu (tj. bez opakování políček), která má největší součet.
Navrhněte algoritmus, určete jeho složitost, popište datové struktury. (Speciálně: Co jsou možné stavy prohledávání?)
- a) Smíte jít pouze doprava a dolů.
- b) Smíte jít pouze doprava, nahoru a dolů, ne doleva.
- c) Smíte jít libovolně, po sousedech. Ale bez opakování vrcholů, tj. po cestě.
- d) Pro poslední možnost, dá se použít reprezentace stavu, která si pamatuje poslední políčko a pro každý řádek nejpravější navštívené políčko? Jaké má výhody a nevýhody?
- e) V nové variantě se smí končit libovolně na pravém okraji. Nechce se vám měnit program. Jak získat
výsledky převedením na původní úlohu? (Změna programu vs. transformace dat, ještě bude.)
Cvičení 2. ($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$, $\log n^2$, $n\log \log n$, $n \log n$, $n^{0.5}$, n^2/\log n
- 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í.
- 8. Naprogramujte na RAM stroji: Najděte druhé nejmenší číslo z daného $n$-prvkového pole. Popište reprezentaci dat.
-- Rozbor: Nepřímé adresování a pointry.
90. DÚ kandidát: 35.1 tranzitivita "O"
91. DÚ kandidát: 35.3 oboustranné omezení: $f \in O(g) \land f \in \Omega(g) \leftrightarrow f \in \Theta(g)$
92. DÚ kandidát: $f \in O(h) \land g \in o(h) \to f+g \in O(h)$ -- je dál
Další:
- 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 (tj. tvrzení neplatí): "důkaz" indukcí: $n^2 \in O(n)$
-- Báze: pro $n=1$: $n^2 = 1^2 = 1 \in O(1)$, tj. taky $1 \in O(n)$.
-- Ind.krok z $n$ na $n+1$: $(n+1)^2= n^2 + 2n+1 \in O(n)$, protože $n^2 \in O(n)$ podle IP, platí $2n+1 \in O(n)$
a použijeme omezení součtu funkcí (příklad 5a).
- 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. ($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. (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$ souvislý,
-- 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^2)$ a $O(m.n)$, naivně $O(n^2)$,
líně - s low-link (možná bylo/bude na přednášce2018)
-- Pozn. Graf, který nemá most, je hranově 2-souvislý. Viz 4/30.
- 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ě.
-- naučit/Poučení: při průchodu grafem nemusíme počítat a vracet jen jedno číslo. Můžeme počítat najednou víc závislých informací,
případně sktrukturovaná data.
-- (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ě.)
- 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.
- 17.2 Programátorský. Vstup je řetězec $r$ a přirozené číslo $m$ (a abeceda $\Sigma$). Generujte postupně
všechny řetězce, které se od zadaného $r$
- a) liší v právě $m$ znacích, ideálně každý jednou,
- b) liší v nejvýš $m$ znacích,
- c) jako b), navíc generujete výstup lexikograficky uspořádaně,
- d) odvodí pomocí nejvýš $m$ operací vložení, vypuštění nebo nahrazení znaku, navíc uspořádaně,
- e) jako d), dovolíme ještě přehození znaků.
- 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. největší nebo nejmenší, 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 jako podgraf housenku s co největším počtem vrcholů?
- 91. DÚ k.: 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 nebo do druhého robota, příkaz ignorují (a zůstanou na místě). 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.
--(z) Úloha je řešitelná i v případě, že neznáme počáteční polohy robotů. Je to ale těžší a hledaná
"univerzální posloupnost příkazů" delší.
--(z1) Zjednodušení: najděte univerzální posloupnost $p$ pro jednoho robota. Víme tvar bludiště, ale nevíme
počáteční polohu robotů. Univerzální posloupnost $p$ vyvede robota z bludiště bez ohledu na jeho počáteční pozici.
--(z2) Totéž, pro $m$ robotů.
- 92. Totéž, ale nejkratší cesta počítá pouze vykonané kroky, bez "prázdných" kroků do zdi. TODO: přehodit
- 93. DÚ k.: 54 Linearizace paměti
- 94. (2023) DÚ k.: Máte strom s hranami ohodnocenými délkou. Spočítejte množinu délek všech cest ve stromě.
Odhadněte (shora) časovou a paměťovou složitost.
Další:
- 30. Hledání artikulací.
- Def: Artikulace je vrchol, jehož odstraněním se zvýší počet komponent souvislosti. Viz i 4/46
- Pozn.: Graf, který nemá artikulaci, je vrcholově 2-souvislý.
- Obecně, graf je vrcholově $k$-souvislý, pokud pro každé dva vrcholy existuje $k$ vrcholově disjunktních cest.
Podobně pro hranovou $k$-souvislost požadujeme $k$ hranově nezávislých cest pro každé dva vrcholy.
Pro $k>1$ se vrcholová a hranová k-souvislost liší.
- Vrcholy se dají rozdělit mosty do disjunktních komponent hranové 2-souvislosti. Pro vrcholovou 2-souvislost vrcholy
můžeme rozdělit na nedisjunktní komponenty 2-souvislosti, přičemž artikulace můžou náležet více komponentám. Proto se někdy
uvažuje rozklad $\it{hran}$ do komponent.
-
- 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. Navrhněte algoritmus.
-- b) Co kdybychom povolili rozdíl o 1 a nepotřebovali sudé stupně?
- 52. Je dán (souvislý) 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. (i DÚ k.) 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í okolí nebo testování existence hrany.
- Pozn.: Najít minimální vzdálenost dvou řetězců je typická úloha dynamického programování.
- Pozn.: Procházení (velkého) stavového prostoru je často na implicitních grafech.
- 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)
- 59. Máte dva genomy, v každém $n$ genů, které si odpovídají $1:1$. Na vstupu je zadáno pořadí a orientace
genů v obou genomech (v rámci jednoho chromozomu, tj. jedné posloupnosti). Elementární změna je genová inverze,
která vezme souvislý úsek genomu, otočí ho (tj. taky změní orientaci genů) a vloží na původní místo. Hledáme nejmenší
počet genových inverzí, které převedou jeden genom na druhý.
- (Orientace znamená, že rozlišujete C a N konec DNA. V naší abstrakci uvažujeme sousměrnou a protisměrnou
orientaci (vůči šipce zleva doprava).)
- Příklad: z genomu "1> 2> 3< 4>" vzniknou jednou inverzí genomy "1> 2>
3> 4>" a "1>
4< 3> 2<" (a další).
- a1) Jak budeme reprezentovat genom? a2) Kolik je možných genomů? a3) Proč chceme pracovat s implicitním
grafem? (Jaký je stavový prostor?)
- b) Lze úlohu zjednodušit, abychom pracovali s pevným vstupním genomem (nebo vstupním)? Jak zjednodušíte a jak
převedete zadání?
- c) Kolik vede hran z jednoho vrcholu/stavu? (asymptoticky nebo těsný horní odhad)
- d) Popište alg., který najde nejmenší potřebný počet inverzí pro převod genomů. d1) Dokážete odhadnout
minimání a maximální potřebný počet inverzí obecně a d2) pro konkrétní genomy?
- e) Optimalizace: Při DFS s implicitní reprezentací grafu dvě nezávislé inverze vedou na stejný stav, který
bychom následně prohledávali 2x. Navrhněte optimalizaci, která tomu zabrání. (Optimalizace se nazývá superpozice,
v kontextu dokazovačů.)
- z) Varianta: Analyzujte podúlohy, pokud neuvažujete orientaci genů.
Cvičení 5. (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?
a) při obecném ohodnocení hran, b) 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. (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ů)
Pozn. Podobným způsobem lze zpracovat i jiné dodatečné podmínky.
(!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)$?
(naučit/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.).
- 15. (na DÚ) Trasování pro konkrétní graf. Graf $G$, orientovaný: $(\{a,b,c,d\}, \{a-b-1,a-c-10,b-c-2, b-d-12, c-d-3,d-a-4,d-b-11 \})$
-- a) Reprezentujte $G$ v matici. Odtrasujte na $G$ "speciální násobení matic". Kolik násobení musíte provést?
-- b) Odtrasujte na $G$ Floydův-Warhsallův alg. pro všechny cesty v grafu. Kolik nových matic musíte vytvořit?
- 90. DÚ kand.
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? (Zdi a dveře jsou mezi políčky.)
Obecně, máme více klíčů stejné barvy a více dveří stejné barvy. Mapa bludiště
včetně rozmístění klíčů a dveří je známá, tu popisuje vstupní graf.
- 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? A jak, 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. (i DÚ) ^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. Přechod do sousední místnosti stojí 1
a prokopání zdi nas stojí $k$.
- 51. Některé úlohy, např. editační 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. (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áme graf a známe jeho MST, změnila se váha jedné hrany grafu. Jak se změní MST? Tj. popište alg.
pro (inkrementální) výpočet nové kostry.
Změna je zvětšení
nebo zmenšení ceny. Změněná hrana nemusí být v kostře. Rozeberte případy, potřebují různé přístupy a následně algoritmy.
- 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. Huffmanovo kódování jako jiný příklad hladového algoritmu. Máme zprávu se znaky $z_i, i=1..n$
o četnostech $c_i$. Přiřaďte jednotlivým znakům bitové kódy (z $\{0,1\}^{k_i}$) případně různé délky
tak, aby zakódovaná zpráva byla co nejkratší a přitom šla zprávně rozkódovat.
- (Návod: pro správné rozkódování potřebujete, aby kód jednoho znaku nebyl prefixem jiného.)
- 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ův alg.: 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.a 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.
- b) Odhadněte složitost vašeho algorimu.
- 41. Fylogenetický strom (podruhé)
Cvičení 8. (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 asymptotickou složitost jiných operací a musíme udržovat případně přidané informace.
(Dvě správné (a rychlé) možnosti a několik nesprávných (nebo pomalých).)
- 92.1 DÚ kandidát. Jak transformovat BVS na vyvážený BVS, v $O(n)$. a) Paměť $O(n)$. (b*) Paměť $O(\log n)$.
- 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.a Medián z posuvného okna. 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ů.) Impl: a/ Trie, b/ BVS.
- 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. Impl: a/ Trie, b/ hašování
- 42.1 Varianta: Ke každému slovu textu najděte všechna
jeho cyklická pootočení vyskytující se ve slovníku.
- 43. Amortizace. a) Přičítání jedničky v dvojkové soustavě: (Taky 12.Haš/39-41)
-- a1) Jaká je očekávaná (průměrná) složitost operace Přičtení jedničky (Inc)? (Rovnice pro střední hodnotu?)
-- a2) Jaká je nejhorší složitost posloupnosti $n$ přičtení k počáteční hodnotě 0? (Jaká
z toho vychází amortizovaná složitost na 1 operaci?)
-- a3) Stejná otázka pro počáteční hodnotu $p$.
- b) jak si lze 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 PLA).))
- (Jedno paměťově špatné řešení a dvě rozumná (založená na podobném principu).)
- 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) vyvážení stromu v 2D, c) intervalový dotaz v 2D...
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. MM 2021
- 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 Jaké jsou výhody a nevýhody odloženého vyvažování.
- 52.2 Vypustili jste celý podstrom v AVL nebo R-B stromě. Jak lze strom znovu vyvážit?
- 53. Jednotný popis AVL a R-B stromů: rank místo hloubky a povolené vztahy otec-syn. TODO
- 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)
- 58. Bellova čísla. TODO, jsou jinde.
- 59. BVS/AVL s provázanými vrcholy: paměť, trade-off: které operace se zrychlí a které spomalí, a o kolik?
Cvičení 9. (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$.
Určete, zda jde nebo nejde použít Master Theorem pro jednotlivé případy (případně jeho mírné zobecnění).
$${\rm 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), T(n) = \sqrt{n} T(\sqrt{n}) + O(n) $$
$$h) T(n) = T(3n/5) + T(4n/5) + O(n^2)$$
$$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*} %% OK
\)
- (+trik volby při vyvážení rekurze a režie)
- 4. Hledání $k$-tého nejmenšího prvku lineárně. Algoritmus s rozdělením na pětice. (Někdy se stihne na Př.)
-- 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 na Př.)
- 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ř.)
-- 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) Ukažte, Nějaký trade-off?
Pozn.: Zobecnění Master theoremu, když jsou podproblémy různě velké: Akra-Bazzi theorem, ve formě "kuchařky".
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, Spletitý kabel,
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 operace nezávisí na výsledcích předchozích měření?
- 37.2 Jak spočítat dolní odhad? (I jinde: 10. Třídění)
- 37.3 Jak upravit alg., pokud kabel má nějaké nepropojené dráty (vlevo nebo vpravo)
- 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. (Možná jste C.d. použili nebo použijete v mat. analýze.)
- 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$.
- 42. Dostanete neuspořádanou posloupnost $n$ čísel, bez omezení velikosti. (Tj. nejde použít lineární třídící algoritmus.)
Máte najít v lineárním čase $O(n)$ $k$ čísel, které jsou nejblíž mediánu celé posloupnosti. Vzdálenost čísel je, jako obvykle, absolutní
hodnota rozdílu čísel.
Cvičení 10 (Dynamické programování )
- 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 (i 1/32), 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 10/7), optimální vyhledávací strom (P2020 volitelně) - viz 10/9, ...
- 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 (BINF),
ii) pro víc než dvě vstupní posloupnosti. (BINF)
- 5.b.iii) s cenou za mezeru (tzv. "gap", BINF); 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.a Optimální (binární) vyhledávací strom. (P2022bude P2021/MM) Jsou dány prvky stromu $x_i, i=1...n$ a jejich frekvence $f_i$.
Označme $h_i$ hloubku prvku $x_i$ ve stromě T. Najděte takový binární vyhledávací strom T, aby $\sum_{i=1}^n h_i\cdot f_i$
byla co nejmenší.
- 9.b Upravte alg. pro situaci, kdy jsou kromě frekvencí prvků zadány i frekvence externích vrcholů stromu, tj. na
externí list mezi $x_i$ a $x_{i+1}$ se přistupuje s frekvencí $g_i, i=1..n-1$, a speciálně $g_0$ pro list menší než $x_1$ a
$g_n$ pro list větší než $x_n$.
- 9.1 (Knutova nerovnost(?)) Stejná úloha, rychlejší (speciální) algoritmus. Označme $k(i,j)$ index optimálního kořene
pro úsek prvků $x_i,...,x_j$. Zdůvodněte, že platí $k(i,j) \le k(i,j+1) \le k(i+1,j+1)$. Na základě toho odvoďte alg.
s časem $O(n^2)$ (místo $O(n^3)$).
- 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$.
- 12. Editační vzdálenost. (!P2022..)
- 12.1 Náhr.2021. Navrhněte algoritmus, který určí editační vzdálenost $k$
dvou řetězců délky $m$ a $n$ v čase $O((n+m)k)$ (místo $O(nm)$).
- 90. DÚ kandidát
Další:
- 31. Odvození slova v bezkontextové gramatice. Existence řešení: mít odvození
je lepší než nemít odvození. Optimalizujeme nad Boolovskými hodnotami.
- 32. Vyhrávající strategie ve hře dvou hráčů s úplnou informací (transpozice a transpoziční tabulky)
- 33. Nejdelší cesta $c$ v (nezáporně ohodnoceném) grafu. Navrhněte algoritmus, který pro daný graf $G$ najde cestu $c$.
Pokud v $G$ platí trojúhelníková nerovnost, (nějaká) nejdelší cesta nutně prochází všemi vrcholy.
Hint: opravdu cesta. Hint2: Stavový prostor
není polynomiální. ((Bellman-)Held-Karp alg.)
- 33.1 Nejkratší cesta $c$, která prochází všemi vrcholy.
- 33.2 Nejkratší kružnice $k$, která prochází všemi vrcholy. Úloha známá jako Problém obchodního cestujícího (POC), angl. Traveling Salesman Problem (TSP)
- Pozn. Pro 33.2 (a taky 33 a 33.1) není známý polynomiální algoritmus a neví se, zda existuje - bude v ADS2.
- 33.3 DP: Nejkratší kružnice v rovině, která prochází body jednou zleva doprava a pak zpět. (O předchozích úlohách z výsledku této nic neurčíme.)
- 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. Viz 9.1.
b) při hledání nejdelší rostoucí posloupnosti můžeme
použít jinou strukturu než pole.
c) Fibonacciho čísla viz 37.
- 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.
- 37. I pro Fibonacciho čísla existuje specializovaný alg. počítající $f_n$ v čase $O(\log n)$ (při
jednotkové ceně instrukce). Viz 1/32, pokud jsme nestihli.
- 38.a Floydův-Warshallův alg. pro hledání všech nejkratších cest je alg. DP.
- b) paměťové zlepšení na 2 matice, c) na 1 matici.
- 39. Zjistěte, zda jde posloupnost čísel rozložit na dvě posloupnosti, kde jedna je rostoucí a druhá klesající.
- 40. PLA: Knihovny. TODO
a) min. výška při pevné šířce, b) min. šířka při pevné výšce, ?
Cvičení 11. (Třídění)
- 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?
b2) Chceme lepší pseudomedián, v prostřední třetině. Kolik kroků v průměru potřebujeme na výběr a jaká bude
složitost Quicksortu v tomto případě.
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Ú kand. 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)?
- (Viz také 11/42.)
- 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.
- 39. PLA 11.1.3 Míchání karet. Napište algoritmus, který v lineárním čase vygeneruje náhodnou permutaci množiny $\{1,2,...,n\}$.
- 40. Jak získat rovnoměrné rozdělení 5 jevů s klasickou šestistrannou hrací kostkou?
- 41. PLA 11.1.5 Náhodná $k$-tice. Z velkého souboru, který se nevejde do paměti, chceme vybrat náhodnou $k$-tici řádků.
Navrhněte algoritmus, který ji vybere tak, aby každá $k$-tice měla stejnou pravděpodobnost. Velikost souboru předem neznáme, ale
vybraná $k$-tice se do paměti vejde. (Zvolíme si vhodné $k$.) Dokážete to na jeden průchod daty?
- 42. Pokračování 11/90. Podmíněná pravděpodobnost. (Jen její trénink, nevidím praktické aplikace.)
- a) Jaká je podmíněná pravděpodobnost, že medián ze tří je v prostřední třetině, pokud aspoň jeden prvek je
v prostřední třetině.
- b) Stejná otázka, za předpokladu, že aspoň jeden prvek není v prostřední třetině.
- c) Stejná otázka, za předpokladu, že aspoň dva prvky jsou v prostřední třetině.
- d) Stejná otázka, za předpokladu, že aspoň dva prvky nejsou v prostřední třetině.
- e) Podobné otázky pro prostřední dvě čtvrtiny.
Cvičení 12. (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. (i DÚ 2021) 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.)
--- Inkrementální přehašování.
--- Při změně velikosti tabulky (na $x$-násobek, často $x=2$) je nejjednodušší dávkové přehašování,
které ale trvá dlouho. Navrhněte, jak přehašovávat postupně tak, aby jednotlivé operace trvaly
nejvýš $k$-násobek času bez přehašovávání, kde $k$ je konstanta.
--- 1/ Chcete stihnout přehašování dřív, než začne další přehašování.
--- 2/ Chcete v průběhu přehašovávání správnou implementaci Insert, (Pseudo)Delete, Find. Popište.
--- 3/ Můžete nějakou dobu používat (tj. mít naalokované) dvě tabulky, starou a novou.
Po ukončení přehašování chceme starou tabulku uvolnit.
--- (4/ Metoda by měla fungovat i pro zmenšování tabulky, případně pro přehašování na stejnou velikost,
když odstraňujeme pseudovypuštěné prvky při otevřené adresaci.)
-- 9.4 Používáte hašování do tabulky prvočíselné velikosti (s modulo), přesto chcete tabulku zvětšovat
a zmenšovat. Jak přistoupíte k počítání prvočísel pro velikost tabulky?
- 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 (nebo slov, u plagiátů)? (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. Chcete zjišťovat, jestli je prvek v množině, napr. slovo v jazyce (spellchecker). Nechcete mít
v tab. reprezentaci původních dat (tj. stačí bitová tabulka) a dovolujete falešná pozitiva (s malou pravděpodobností:
spellchecker odpoví ANO, ale odpověď je špatně). Nepodporuje Delete, obvykle pro pevná data (kvůli návrhu parametrů).
- 31.1 (i DÚ) Bloomův filtr implementuje d.s. množina a je to pravděpodobnostní dat. struktura. Bloomův filtr používá
$k$ hašovacích funkcí a hašuje do bitové tabulky velikosti $m$. Předpokládame, že hašovací funkce jsou nezávislé a hašují
rovnoměrně. Tabulka má na začátku všechny bity nastavené na 0. INSERT($x$) spočítá všechny haš. funkce pro klíč $x$ a nastaví
všechny bity na vypočítaných indexech na 1. DELETE není podporované. FIND($x$) spočítá všechny haš. funkce a pokud
na všech spočítaných indexech je 1, odpoví ANO, jinak odpoví NE. Odpověď NE je vždycky správně, odpověď ANO může být
chybně (tj. falešně pozitivní), pokud klíč není v reprezentované množině, ale všechny haš. funkce ukážou na nastavený bit.
Nechť $\alpha$ je podíl nastavených bitů v tabulce. Části b) a c) jsou programátorské, tj. spočítejte programem.
- a) Pro známé naplnění tabulky α $\alpha$ a $k$ hašovacích funkcí, odvoďte pravděpodobnost chybné odpovědi.
(Kde/jak se používá nezávislost hašovacích funkcí?)
- b) Pro naplnění 0.7 a požadovanou chybu 0.1%, kolik hašovacích funkcí máme použít?
- c) Pro naplnění 0.6 a 16 funkcí, jaká je pravděpodobnost chyby?
- Pozn.:
- Odhad $\alpha$ lze spočítat z počtu funkcí $k$, velikosti tabuky $m$ a počtu zahašovaných prvků $n$. (
- $1-(1/e)=0.6321205588$
- (d) Co lze dělat, když se bitové naplnění příliš zvětší? Tj. pravděpodobnost chyby se zvětší.
- 32. a) Tabelační hašování: univerzální hašování založené na xor místo skalárního součinu
se sčítáním a modulo (z mojí přednášky), pro $m=2^l'$, $U=2^{lr}$.
b) Rychlé přepočítání haše při malé změně dat. (Hašování pozic her. Často se mění 1 figurka.)
c) Hašování řetězců: transformační funkci přiřazuji pouze platným hodnotám znaků v klíči. (i BINF)
- Idea: Každé možné hodnotě klíčku (tj. části klíče, do $2^l$) a pozici (do $r$) je přiřazena náhodná hodnota.
Hodnota klíče se rozdělí, po částech transformuje a xor-uje.
- Pozn.: Zobristovo hašování je implementace tabelačního hašování. Každý bit klíče má přiřazenou náhodnou
hodnotu a xor-ují se hodnoty
pro nastavené bity. ($l=1$) Bitová 0 se transformuje na 0.
- 32.1 Hledání podřetězce délky $l$ v okénku stejné délky v textu délky $n$. Přímočaře v $O(n.l)$.
Jak navrhnout celkový přístup, abychom dokázali rychle přepočítavat haš okénka? a) Pro haš skalárním součinem.
b) Pro haš tabelačním hašováním.
- 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í)
- 39. Amortizace. Účetní metoda, penízková/kreditová metoda, potenciálová metoda.
- 40. Binární počítadlo. a) Kolik stojí $n$-krát INC (inkrement) celkem, pokud začínáme z 0? b) A pokud začínáme
z nějakého $k>0$ ? (Taky 8/43)
- 40.1 Jaká je očekávaná složitost?
- 41. Navrhněte jinou reprezentaci čísel, která bude podporovat INC, DEC a TESTZERO (test na 0) v amortizovaně
konstantním čase. (Dvě možnosti, další nesprávná a jedna nevhodná) (Taky 8/43)
- 42. a) Střední hodnota pro nalezení volného místa. Máme hašování s otevřenou adresací s naplněním tabulky $\alpha$,
předpokládáme, že procházené přihrádky (tj. jejich indexy) jsou nezávislé. Kolik pokusů musíme průměrně vykonat pro nalezení
prvního volného místa? (Rovnice a řešení. Taky 8/43) (PLA: Lema o džbánu, z alg. Quickselect)
-- b) Používáme dvojité hašování (a předpokládáme nezávislost pokusů). Přidáte prvek. O kolik se průmerně prodlouží řetízek
příslušného prvku v tabulce? Tj. kdybychom řetízek procházeli při neúspěšném vyhledávání prvku.
- 43. Metody pro univerzální hašování (pro h.tab. s řetízky):
-- a) Skalární součin, nad ${\mathbf Z}_p$, ${\bf t}\in {\bf Z}_p^d$, 1-univerzální
-- b) Lineární kongruence, $p \ge |{\mathcal U}|$, $h_{a,b}(x) = ((ax+b) \bmod p) \bmod m$ pro lib. $m$, $a\not=0$, 1-univerzální
-- c) Z vyšších bitů součinu, ${\mathcal U} = [2^w]$, $m=2^l$, $h_a(x) = \lfloor(ax \bmod 2^w)/ 2^{w-l}\rfloor$, $a \in [2^w]$, $a$ liché, 2-univerzální
-- (Silná $c$-univerzalita:) PLA cv. 11.5.8** Varianta c) pro silnou 2-univerzalitu:
$h_{a,b}(x) = \lfloor((ax+b) \bmod 2^{w+l})/ 2^{w}\rfloor$, $a,b \in [2^{w+l}]$
(Vybíráme bity $w$ až $w+l-1$ místo bitů $w-l$ až $w-1$.)
- (44.) TODO: doplnit z ADS2, hasovani chem. vzorců
Cvičení 13. ( )
Virtual/nekoná se (2019)
todo
Další:
Cvičení 14. ( 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í:
- Někdy stačí optimální hodnota, nemusíme rekonstruovat řešení.
- Zapamatovat si celé řešení. Obvykle paměťově náročné.
- 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.
- 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í.
- 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.
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: ...
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:...
DÚ 20/21 Zoom+Moodle
Cv1 1/1, 2, 4Předn, 30 ; (32P), 34.1,2,3,4, 38.g
DU1 (4.3.2021) 1/91
Cv2 1/38.g, 1/3,3b, RAM 2/8, 2/3, 2/31
P3:grafy
Cv3 2/4,5,7 PLA:47 3/5 4/1.1c,3,5,(9),10,(18)
DU2 (18.3.2021) 4/90
Cv4 25.3. 4/12.2,18,(54) 5/4.1 6/2,4,5,6,(7p,13) ...
DU3 (25.3.2021) 6/90
Cv5 1.4. 6/13,13.1,7,8,10,10.1,10.3,14.1, 34+35, (55)
DU4 (1.4.2021) 6/14.1
Cv6 8.4. DU3, Dijkstra: rekonstrukce cesty, složitost ; 6/33, 7/4,4.1,(7),
Cv7 15.4. 7/1.1,1.1.1,2,(3.1),5,8,(33,39) 8/2,2.1,,3,5,(7)
DU5 (15.4.2021) 8/90 index(k) v BVS
Cv8 22.4. rotace,8/16,7,5,8.2,(12),13, 45.2
DU6 (22.4.) 8/94 D.s. pro výběr mediánů
Cv9 29.4. DU5 1.2,9,10/Ins, 37,(38), 52
Cv10 6.5. Rozbor DU6, AVL: 8/52 Trie: 8/40,42,39 Haš: 12/3,9,9.1
DU7 (6.5.) 12/9.3 Průběžné přehašování
Cv11 Haš: 12/2,4,5,6,7,8,11,(31) Rozděl a panuj: 9/1,7...
DU8 (13.5.) 9/90 Šroubky a matičky
Cv12 Rozděl a panuj
Cv13 DU8 Haš/E 12/40,42a,41 QSort 11/3,6,(7,90c) ...
Cv14 DynP 3.b,c, 4,5abd,(6),8,10a,11.1,11.2,(33)
Náhr., vyberte si 5/92a počet nejkratších cest v DAG,
7/40ab rekonstrukce metriky,
8/95a Medián z posuvného okna,
9/37 Úloha o telefonních kabelech,
10DP/12.1 lepší editační vzdálenost,
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
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?
--
Nástroje
Pro kopirovani;
-
-
z webu: ...
--------------------
test, $\tt OK$
HTML: • & < > ≤ ≥ ; / \
Příliš žluťoučký kůň úpěl ďábelské ódy. áäčďéěíĺľňóö_o_řŕšťúůýž