Vladan Majerech - NTIN060 Algoritmy a datové struktury

Last Modified: 28.9.2020

Index

zápočtové příklady, odkazy, cvičení 1, cvičení 2, cvičení 3, cvičení 4, cvičení 5, cvičení 6, cvičení 7, cvičení 8, cvičení 9, cvičení 10, cvičení 11, cvičení 12, cvičení 13, cvičení 14.

Pro získání zápočtu z NTIN060 je potřeba získat (2/3 z možných bodů za domácí úkoly zadávané v průběhu semestru).

Zápočtové příklady

Pokud není uvedeno jinak, počet přidělených bodů rychle klesá v případě použití časově neoptimálních algoritmů. Za úkoly odevzdané po termínu je možno získat jen poloviční počet bodů. Termínem je vždy 9:00 v datum cvičení, mezi dnem stanovení termínu a termínem je vždy přinejmenším jedno cvičení (výjimky obou pravidel možná budou na konci semestru). U některých úloh nemusí být nastaven termín, zvláště pokud navazují na dosud neprobranou látku. Dokud nacházíte lepší řešení, můžete úlohy odevzdávat opakovaně, o již získané body tím nepřijdete. Domácí úkoly odevzdávejte e-mailem ať ve formě fotografie/skenu rukou napsaného řešení, nebo přímo v nějakém jiném všeobecně rozšířeném formátu (např. pdf, či přímo v textu e-mailu).

Odkazy na obdobné stránky

moje loňské cvičení, texty k cvičení Jana Hrice, cvičení Michala Kouteckého, Michala Oplera, Jakuba Pekárka, Jirky Švancary

Cvičení 1

Na cvičení jsem oznámil podmínky zápočtu a v podstatě celou hodinu jsem budoval oslí můstek k zadání prvního domácího úkolu.

Nejprve jsme si připomenuli, jak se sčítají geometrické posloupnosti, pak jsme se věnovali Fibonacciho posloupnosti (a posloupnostem obdobného typu), ukázali jsme si jak vyjádřit n-tý člen nejen skalárním vzorečkem, ale i maticovým vzorečkem. Maticový tvar měl výhodu pro vyhodnocování, protože mohl pracovat s přesnými čísly, zatímco skalární tvar naráží na reprezentaci algerbaických čísel, které nejsou racionální, při vyhodnocování je pak potřeba velice přesně hlídat aby rozsah kumulované chyby nepřesáhl toleranci (v našem případě, abychom se nedostali blíže k nesprávnému přirozenému číslu).

Nebylo překvapivé, že maticový tvar vůči bázi vlastních vektorů matice velice přesně korespondoval skalárnímu tvaru.

Pak jsme se dostali k řešení rekurence $t(n)\in O(n^\alpha)+\sum_{i=1}^k t(a_in)$. Nejprve jsem se snažil poskytnout trochu času na seznámení se s rekurencí, pak jsem měl proslov o efektivitě zápisu. Odbočkou přes zapomínání neintegrovaných členů při několikanásobném integrování per partes a o správné organizaci zápisu jsme rozdělili výpočet na část s $cn^\alpha$ a na části s $t$, které je ještě potřeba rozepsat. Homogenita zápisu v každé části nám umožnila nepsat zbytečně mnoho symbolů a věnovat se místo toho podtatě problému. Ukázalo se, že stěžejní je hodnota $S(\alpha)=\sum a_i^\alpha$. Pokud je $S(\alpha)<1$, vyjde $t(n)\in O(n^\alpha)$, pokud je $S(\alpha)=1$, vyjde $t(n)\in O(n^\alpha\log n)$ a pokud je $S(\alpha)>1$, existuje $\beta>\alpha$ pro něž je $S(\beta)=1$ a $t(n)\in O(n^\beta)$. Zdůvodnění, pro případ $S(\alpha)>1$ se součtem geometrické posloupnosti chyb odhadu byla trochu magie. Takže všechny odvozené výsledky je lepší zkontrolovat například „matematickou indukcí“. Z povídání o lineárních rekurencích speciálně v souvislosti vícenásobnými kořeny se dá tušit, že řešení jsou v případě $S(\alpha)=1$. Je tvaru $c_1n^\alpha+c_2n^\alpha\log n$ a v opačném případě $c_1n^\alpha+c_2n^\beta$. Vzhledem k tomu, že v $O$ notaci můžeme součet funkcí odhadnout asymptoticky větší z nich, dostáváme tvrzení ve shodě s předchozími pozorováními.

Cvičení 2

Cvičení proběhlo nezvyklou formou při práci trojic u „tabulí“. Optimistickým plánem bylo procvičit následující:

1. Nalezněte co možná nejvíce asymptotických porovnání následujících funkcí: $n$, $\sqrt n$, $\ln n$, $\log_2 n$, $\log \log n$, $2^{\log_4 n}$, $n^{\log n}$, $n^{2/3}$, $n!$, $n^n$, $2^n$.
2. Nechť $f_1(n)\in O\bigl(f_2(n)\bigr)$, platí $f_1(n)+f_2(n)\in O\bigl(f_2(n)\bigr)$? Proč?
3. Platí $O\bigl(f_1(n)+f_2(n)\bigr)=O\bigl(\max\{f_1(n),f_2(n)\}\bigr)$? Proč?
4. $b$-algoritmus na hledání $k$-tého z $n$-prvků funguje následovně: Rozdělí prvky na $\lfloor n/(2b+1)\rfloor$ částí po $2b+1$ prvcích (nejvýš $2b$ jich zůstane stranou). Z každé části algoritmus najde zástupce jakožto $1+b$-tý (prostřední) prvek hrubou silou. Program najde pivota jakožto $\lfloor (2b+1+n)/(4b+2)\rfloor$-tý (prostřední) prvek mezi $\lfloor n/(2b+1)\rfloor$ zástupci rekurentním zavoláním sama sebe. Následně algoritmus mezi původními prvky zjistí, počet $s$ prvků menších než pivot a počet $\ell$ prvků větších než pivot. Je-li A) $s>k$, algoritmus je znovu spuštěn, bude hledat $k$-tý z $s$ prvků menších než pivot. Je-li B) $n-\ell\ge k\ge s$, je pivot hledaným prvkem. Je-li C) $n-\ell<k$, algoritmus je znovu spuštěn, bude hledat $k-n+\ell$-tý z $\ell$ prvků větších než pivot. Najděte asymptotickou složitost $b$-algoritmu na hledání $k$-tého z $n$-prvků. Jakou byste doporučili volbu $b$?
5. Mějme dva body konvexního obalu a polopřímku vycházející z jejich spojnice. Mějme $n$ bodů v polorovině rozseknuté touto polopřímkou. Naší snahou je nalézt bod či úsečku konvexního obalu dané množiny bodů, protnutý danou polopřímkou. Zkuste najít algoritmus, kterému se podaří v lineárním čase zmenšit konstanta krát (na $3n/4$) množinu relevantních bodů. Jak vyjde složitost algoritmu, který bude opakovat redukci relevantních bodů, dokud nenajde výsledek?
6. Jsme schopni použitím předchozího algoritmu najít konvexní obal skládající se z $h$ úseček pro množinu $n$ bodů v čase $O(n\log h)$? Jak?
7. Jak by vyšla složitost násobení matic (pro jednoduchost rozměru $2^k$), pokud bychom uměli násobení matice $2n\times 2n$ spočítat pomocí 7 násobení matic $n\times n$ a konstantního počtu sčítání matic $n\times n$?

Ukázalo se, že studenti nejsou v logaritmování zběhlí a zvláště $2^{\log_4 n}$ dělalo naprosté většině z nich problém a tak strávili nad prvním příkladem větší část hodiny. Všechny skupiny nakonec stihly první tři případy, kde druhý byl nejjednodušší. Třetí příklad byl zákeřný v tom, že platnost jedné implikace vyžaduje doplnit předpoklad nezápornosti obou funkcí. Některé skupiny si dále vybrali příklad 7 (a úspěšně jej vyřešily), jiné si vybrali příklad 4 a některé jej dořešily. Jedna skupina si vybrala příklad 5 a dořešení (s malou) nápovědou byla docela blízko.

Cvičení 3

Na začátku hodiny jsem konstatoval, že vynechání matematické analýzy v prvním semestu má velký vliv na početní dovednosti studentů. V předchozích letech byly s úkolem indukce mnohem menší problémy. Naznačil jsem proto v úvodu hodiny, jak důkaz matematickou indukcí probíhá.

Následně jsme se věnovali příkladům, které jsme nedořešili ve skupinkách minulou hodinu. Probrali jsme worst case algoritmus na hledání $k$-tého z $n$ prvků, hledání „horního mostu“ metodou prune and search, a celkově hledání konvexniho obalu pomocí Kirkpatrick-Seidel algoritmu. Ve všech třech případech jsme dostali zváštní variantu rekurence. V posledním případě nebylo možno použít vyřčenou větu ale bylo potřeba zopakovat její důkaz. Zajímavý byl trik s rozmísťováním mincí limitující velikost stromu rekurence na $h$ a to, že časově nejhorší průběh algoritmu byl pro vyvážený strom rekurence.

Poslední příklad z minulé hodiny vedl k odvození časové složitosti Strassenova algoritmu $O(n^{\log_27})$, pokud neměříme velikosti vstupu, ale rozměrem matice (vůči velikosti vstupu by šlo o $O(n^{(\log_27)/2})$). Jednu z možných variant algoritmu (snad i snadno zapamatovatelnou) jsme si ukázali včetně důkazu korektnosti. Hodilo se opět použít značení, kde minimalizujeme počet použitých písmen.

Na druhém cvičení nám zbyly ještě 4 minuty času, takže jsme si trošku popovídali o (ne)výhodách BFS a DFS při prohledávání implicitních grafů (zmínil jsem transpoziční tabulky na nespolehlivé značení vrcholů, kterými jsme prošli). Zazněla jejich kombinace IDA, která spojuje jejich výhody a téměř není nijak penalizována. Na grafu rubikovy kostky jsem ještě naznačil užitečnost heuristických dohadů dolního odhadu délky zbytku cesty na zrychlení IDA prohledávání. Užitečnost obdobné heuristiky u BFS jsme nezmiňoval.

Cvičení 4

Cvičení se kvůli epidemii Covid-19 v přítomnosti studentů nekonalo. Plánem bylo pracovat v malých skupinkách a věnovat se prohledávání grafů. Chtěl jsem v úvodních pár minutách na prvním cvičení říct něco o prohledávání implicitních (velkých grafů). Pak jsem chtěl přistoupit k druhé výhodě prohledávání do šířky a tou je lokalita prohledávání (prohledávání do šířky není vhodná technika pro pokus fyzicky opustit bludiště). Během prohledávání do hloubky si můžete globálně aktualizovat kontext prohledávaného místa, zatímco při prohledávání do šířky musíte všechny potřebné informace kopírovat do fronty a znovu obnovovat.

Měli jsme si nejprve připomenout pojmy jako jsou stromové hrany, zpětné hrany (a v případě orientovaných grafů dopředné a boční), navíc pojmy jako preorder, a postorder.

Měli jsme probrat příklady využívání kontextu v DFS. Na jednoduché úrovni to je počítání low funkce, tedy místa, kam je možno se z DFS podstromu dostat nejvýš jednou zpětnou hranou.

Využití low funkce pro detekci/vypisování komponent hranové/vrcholové dvousouvislosti měla být následná aplikace.

Další jednoduchou aplikací mělo být nalezení dvou stromově nejvzdálenějších vrcholů (neorientovaný strom s nezáporně ohodnocenými hranami).

Poslední, co jsem chtěl stihnout bylo hledání topologického uspořádání silně souvislých komponent orientovaného grafu. Postačilo by dvouprůchodové DFS prohledávání s využitím postorder.

Cvičení 5

Cvičení proběhlo formou videokonference pomocí sdíleného google docs. Věnovali jsme se Dijkstrovu algoritmu nalezení nejlacinějších cest(cesty) z daného vrcholu $s$ (do daného vrcholu $t$) v nezáporně ohodnoceném orientovaném grafu, hlavně jsme se soustředili na oddělení algoritmu a datových struktur. Vyšel nám následující algoritmus:

Dijkstra(s(,t)){
 for(v in V) v.stav=nenavštívený;
 s.stav=otevřený; s.dist=0; h=new Heap();
 a=s;
 while (a!=null) {
  for(v in a.successors) {
   d = a.dist+cost(a,v); // zbytečné pro hotové, ale nechci psát dvakrát
   if (v.stav==nenavštívený) {
    v.dist=d;v.prev=a;v.heap=h.Insert(d);
   } else if ((v.stav==rozpracovaný && v.dist>d) {
    v.dist=d;v.prev=a;h.Decrement(v.heap,d);
   }
  }
  a.stav=hotový;
  a=h.FindMin();h.DeleteMin();
  (if (a==t) break;)
 }
}

Spočetli jsme, že Insert je použit nejvýš $n=|V|$ krát, stejně tak FindMin a DeleteMin. Decrement je použit $m-n=|E|-|V|$ krát. Při implementaci s optimálním interface dostaneme celkový čas $n\cdot O(1)+n\cdot O(1)+n\cdot O(\log n)+(m-n)\cdot O(1)=O(m+n\log n)$.

Kromě toho jsme vyřešili dva příklady A) hledání nejpropustnější cesty (kde místo součtem byla celková váha určena součinem pravděpodobností), a B) případ kdy optimalizujeme současně podle dvou vlastností.

Cvičení 6

Na cvičení bylo velkou většinou odhlasováno probrat Fibonacciho haldy. Takže jsem technikou extrémně drahého porovnávání předvedl techniku zavedení 4 potenciálů, a jednoho invariantu, abychom dostali strukturu s dvěmi typy hran a vrcholů a deklarovanými složitostmi operací. Princip decrement byl udržování lokální podmínky na ztrátu nejvýš jedna v každém černě připojeném potomkovi (vrcholy mají tedy buď ztrátu 0 nebo 1).

Zmínil jsem jen ideově, že existují varianty s worst case časovou složitostí jednotlivých operací, kde je místo lokálního globální omezení na ztrátu. Vrcholy bez černé hrany do rodiče jsou uchovávány ve struktůře na detekování stejných řádů, stejně tak vrcholy se ztrátou. Navíc tam jsou keše každé z těchto struktur, abychom rozložili časově náročné operace v čase. Celkovou veliost keší a struktur udržujeme v mezích. Kvůli worstcase jsme nuceni každou operaci končit pomocí FindMin.

Na konci hodiny jsme probrali ještě Bellman Ford. Analýza, nad finálním stromem nejlacinějších cest (vybíráme si v případě víceznačnosti stejnou cestu) je velice jednoduchá.

Na druhém cvičení jsme si ještě předtím stihli zopakovat Floyd Warshal. (Psal jsem to úmyslně tak, že jsem popsal postupně vzorec pro množinu sledů a minium z nich.)

Cvičení 7

Věnovali jsme se hledáním minimální kostry (v neorientovaných ohodnocených ne nutně souvislých grafech). Ukázali jsme si obecný nedeterministický barvící algoritmus. Ukázali jsme si Kruskalův algoritmus, Jarníkův (Prim, Dijkstra) algoritmus a naznačili Borůvkův. Ukázali jsme si, proč je můžeme interpretovat jako barvící algotimy a zamysleli jsme se nad jejich časovou složitostí a použitím vhodných datových struktur. V případě Jarníkova algoritmu jsme recyklovali implementaci Dijkstrova algoritmu pro najlacinější cesty (jen není podmínka na nezápornost a nepřičítáme cesty do a). V případě Kruskalova algoritmu by se nám hodila struktura na spojování tříd ekvivalence, kam patří pěstované modré komponenty. Disjoint Find Union jsme neprobírali, jen jsme si řekli, že bude zvládat jednotlivé operace amortizovaně v čase $O(\alpha(n))$, kde $\alpha$ je inverzní funkce k $A(n,n)$ pro Ackermanovu velice rychle rostoucí funkci $A(m,n)$. Vzhledem k velikosti vesmíru se nedá očekávat, že bychom pracovali s grafy, kde $\alpha(n)>5$.

Následně jsme srovnali algoritmy na základě toho, zda je lehké setřídit hrany podle velikosti. Pokud ano, vítězí Kruskalův, pokud ne, je lepší algoritmus založený na Jarnikově algoritmu. Nicméně místo $O(m+n\log n)$, kde $\log n$ je způsobeno maximální možnou velikostí haldy se nabízí pěstovat haldy jen do omezené velikosti. Výsledný algoritmus Fredman Tarjan pracuje následovně: Zastropuje velikost hald na $t=2^{2m/n}$, pak budování modrých stromů bude trvat jen $O(m)$. Pokud přidáme kontrakční fázi, která zredukuje vícenásobné mezistromové hrany a odstraní hrany uvnitř stromů (zvládneme s přihrádkovým tříděním v O(m)), pak můžeme celý postup zopakovat. Ukazuje se ale, že $n_{i+1}t_i\le 2m$, takže $t_{i+1}=2^{2m/n_{i+1}}\ge 2^{t_i}$, takže fází nemůže být mnoho ($O(\log^{*}n)$), časem nikdy nedojde k tomu, že bychom přestali pěstovat strom kvůli velikosti haldy. Taková fáze ale výpočet minimální kostry dokončí.

Ve zbytku hodiny jsme se věnovali intarface vyhledávacích stromů, rozmysleli jsme si, co by se nám hodilo, abychom mohli v databázi (rozumně efektivně) vyhodnocovat obdélníkové dotazy.

Cvičení 8

Věnovali jsme se především hashování, jeho randomizaci, hlídání faktoru naplnění a amortizované i deamortizované verze reakcí na neefektivní naplnění. Ke konci hodiny jsme se chvíli věnovali „high-level“ porovnání AVL a RB stromů.

Cvičení 9

Povídali jsme si o vyvažování $a,b$ stromů a jeho složitosti (částečně v závislosti na $a$, $b$). Na prvním cvičení jsme si ještě stihli říct, jak se provádí insert v AVL, na druhém jsme si místo toho povídali o interface vyhledávacích stromů (který je činí prodejnými v konkurenci hashovacích tabulek)

Cvičení 10

Bavili jsme se na první skupině o DFU a na druhé skupině primárně o Delete v AVL, kromě toho jsme na obou skupinách mírně diskutovali o zadání domácích úloh. A probrali jsme efektivní vyhodnocování velkého MaserMind.

Cvičení 11

Řešili jsme různé hádanky které mají vzdáleně něco společného s programováním. Lámání čokolády, řezání kvádru, házení vajíček, vězni v zástupu tipující svoje číslo na jarmulce. Vězni na „úplném grafu“ viditelnosti, nezávisle tipující své číslo, kde úkolem je aby se aspoň jeden trefil.

Poslední úlohu jsme nedodělali, ale nápověda již byla dostatečná na vyřešení za neodevzdávaný nebodovaný domácí úkol (domácí úkoly už další zadávány nebudou).

Cvičení 12

Dořešili jsme hádanku s čepičkama na úplném grafu viditelnosti. Pak jsme řešili hádanku s nalezením $n$ tého součtu dvojic hodnot z dvou uspořádaných polí velikosti $n$. Výsledná sublineární složitost algoritmu $\Theta(\sqrt{n}\log^2n)$ je na první pohled překvapivá.

Na konci hodiny jsem dával poměrně silné nápovědy k domácím úlohám.

Cvičení 13

Na předposledním cvičení (prvním) jsem částečně odpověděl na otázku „optimality“ algoritmů. (Blumova věta říká, že optimální algoritmus nemusí obecně existovat, umíme argumentiovat (někdy) tím, že celý vstup je potřeba ... linearita, že v daném výpočetním modelu nejde řešit rychleji ... jen pro rozhodovací stromy, ale například zjištění unikátnosti čísel na vstupu vyžaduje v tomto modelu $\log n!$, přičemž hashovací tabulky to řeší randomizovaně lineárně. Další možností je transformace problémů/úloh, dokážeme-li pomocí naší úlohy vyřešit něco „náročné“, musí být „náročná“ (je-li překlad nenáročný).)

Na druhém jsem se věnoval úloze hledání nejmenšího opsaného kruhu dané množině bodů. Popisoval jsem randomizovaně lineární Welzelův algoritmus, naznačil jsem ale, že je v něm chyba a jak ji opravit. Blíže jsem odkázal na wiki Smallest-circle_problem, kde je navíc i popis deterministického algoritmu (Megiddo ... několikrát zanořené prune and search) s mnohem horší multiplikativní konstantou. (Stránku jsem podstatně upravoval).

Pak jsem se věnovali dvojici úloh na dynamické programování úloh na infima a suprema dvou prvků ve svazu dle relace možnosti vyškrtávání v binárním zápise čísel. Po odvození rekurentních vzorečků jsme měli možnost vyplňování tabulky pro všechny binární prefixy obou vstupů (přepisováním hodnot je možno místo 2D recyklovat 1D tabulku), alternativou je jako v případě funkcionálních jazyků vyhodnocovat jen potřebné hodnoty, ale „hashovat“ si spočtené mezivýsledky, aby mezivýsledky nebyly počítány opakovaně. Je-li potřebných mezivýsledků $o(d^2)$, vychází funkcionální přístup efektivněji časově, než vyplňování tabulky. Naopak, je-li potřebných výsledků $\omega(d)$, je metoda přepisování 1D tabulky prostorově efektivnější. Kde $d$ je celková délka binárních zápisů parametrů.

Nakonec jsme se věnovali hádance hledající optimální komunikační strategii $n$ vězňů s $k$-stavovým ($k=2$) přepínačem a počítadlem návštěv. (Po dohodnutí strategie budou vězni na samotkách, jedinou možností komunikace bude poloha přepínače v místnosti, do které bude dozorce přivádět jako $i$-tou návštěvu vězně $k$ s pravděpodobností $1/n$. Strategie nastavování přepínače má být zvolena tak, aby byl průměrný počet návštěv, než bude mít některý vězeň důkaz, že v místnosti byli všichni, co možná nejmenší.)

Začali jsme se strategií s konečným průměrným počtem. Následně jsem naznačil možná zrychlení:

1. Více podúkolů ... je potřeba střídat fáze plnění podúkolů a zjišťování splnění všech podúkolů.
2. Zrušení asymetrie a zrychlená inicializace podúkolů pomocí nabalovacích podfází první fáze.
3. Alternativou rozdělení úkolu na podúkoly je symetrizace „binárním spojováním“, potíž je ale
s velkým počtem fází (druhů signalizace), které je potřeba střídat (u přepínače od začátku leží počet tokenů doplňující do mocniny dvou, na začátku prvních fází příslušných bitů jsou příslušné části odebrány).
4. V binárním spojování je velice efektivní role pozorovatelů, kteří mohou zjistit, že úkol je splněn ještě před tím, než se shromáždí „rozhodující počet virtuálních tokenů“ na jednom místě.

1. Při binárním spojování s pozorovateli, je pro rozšíření „pozorovatných“ informací optimální zařadit jednu „sestupnou“ sekvenci fází, signalizace jsou tak /\///.. ($X,1,2,4,8,\dots,2^k,\dots,8,4,2,1,X,1,2,4,8,\dots,2^k,X,1,2,4,8\dots$)
(kde $X$ v čistě binárním signalizování chybí).
2. Ukazuje se, že binární /\///.. spojování s pozorovateli je efektivnější, je-li potřeba nasbírat $3\cdot 2^k$ virtuálních tokenů (takže ukončování je jedině na základě pozorování).
3. Mnohem efektivnější je zredukovat počet binárních fází tak, že binární fáze jsou určeny pouze k zjišťování splnění všech podúkolů. Díky tomu je možno využít efektivitu nabalovacích podfází.
4. Nabalovací podfáze umožňují drobné optimalizace, například signalizace druhou noc první nabalovací fáze může znamenat 2 či 1 virtuální token v místnosti, místo klasického 2 či 0. U dalších nabalovacích fází může vězeň, který nešťastně přišel k vícenásobnému podúkolu restartovat nabalování zanecháním správného počtu virtuálních tokenů v místnosti, aby se jednoho podúkolu zbavil (nevadí když mu zbyde záporný počet virtuálních tokenů ostatně místo pamatování si velikosti podúkolů si múže pamatovat, kolik mu chybí tokenů ke splnění všech podúkolů, a splnění kolika podúkolů garantuje. Navíc při signalizování splněných podúkolů může všechny kromě posledního beztrestně signalizovat). Může se vyplatit zavést u pozdějších nabalovacích podfází posledních pár (nikdy nevyšlo víc než 1) dní, kdy vězeň bez podúkolu preventivně podúkol vezme, aby nevznikl vícenásobný podúkol, pokud by následující den ...
5. Zajímavé je, že varianta, kdy první vstupující vězeň zahodí svůj token a je potřeba sbírat $n-1$ tokenů může vyjít efektivněji než sbírání $n$ tokenů. (pro $n\in\{3, 4\}$ (jednofázové binary)) u více vězňů to nemá vliv, pro 5-15 je lepší jeden úkol, pro 16-43 3 binární podúkoly, 44-65 6 binárních podúkolů, 66-80 8 binárních podúkolů, dále 12 binárních podúkolů. Pro hodnoty od 16 dál jde jen o výsledky simulací, více simulací a zpřesňování parametrů by možná mírně upravilo rozhraní mezi optimálními (meta)metodami.
6. Stanovení délek fází a podfází, rozdělení úkolu na podúkoly je „alchymie“. Pokud do stavu počítáme i pozorované informace, je počet možných stavů extrémně velký, aby bylo možno počítat pravděpodobnosti (všech stavů pro jednotlivé dny) exaktně.

Cvičení 14

Na posledním cvičení jsme se věnovali narozeninovému paradoxu, Splay stromům a Blumovým filtrům. Pak jsme ještě chtěli řešit úlohu dynamického programování související s QR kódy, ale nezbyl na to čas.