Vladan Majerech - NTIN060 Algoritmy a datové struktury 1

Last Modified: 12.10.2022

Valid HTML 4.01 Strict

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í 9+3/4, cvičení 10, cvičení 11, cvičení 12, cvičení 13

Cvičení by měly být současně přes zoom, uvidíme, jak bude fungovat technika. Včas byste měli dostat e-mailem odkaz na google doc. Pokud by k tomu z jakéhokoli důvodu nedošlo, kontaktujte mne mailem jmeno.prijmeni@mff.cuni.cz. V google doc by měly být odkazy na zoom i virtuální tabuli udržovány.

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 14:00 v datum čtvrtečního 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).

KódBodytermínZadání
indukce103.3.2022Dokažte matematickou indukcí případy rekurence $t(n)\le cn^\alpha+\sum_{i=1}^k t(a_in)$, kde $\forall i\,a_i<1$ (a pro $n\le n_0$, $t(n)\le C$) dle srovnání $S_\alpha=\sum a_i^\alpha$ s $1$, užitečné je dokazovat existenci konstant $c_1$, $c_2$ pro něž platí pro všechna $n$ vztah $t(n)\le c_1n^\alpha+c_2n^\beta$, kde $S_\beta=\sum a_i^\beta=1$ (případně $t(n)\le c_1n^\alpha+c_2n^\alpha\log n$). Vhodná $c_i$ zjistěte v průběhu důkazu. Hodí se za indukční předpoklad brát, že tvrzení platí pro všechna menší $n$.
mult1010.3.2022Ukažte, dva (velmi podobné) algoritmy, jak je možno násobit $n$ ciferná čísla v čase $O(n^{\log_23})$.
medián1017.3.2022Je dán „komprimovaný“ seznam čísel. Nalezněte jejich medián (prvek na pozici $m/2$ v seřazené posloupnosti všech $m$ prvků). Komprimace spočívá v tom, že místo čísel dostáváme dvojice čísel, kde první udává hodnotu a druhé počet výskytů dané hodnoty v nekomprimované posloupnosti (stejná hodnota může být ve více dvojicích, dokonce ani není zakázáno její použití v ihned následující dvojici). Můžete využívat algoritmus na nalezení mediánu v nekomprimovaném případě jako podprogram (a nemusíte o něm dokazovat, že pro $n$ prvků pracuje v čase $O(n)$).
řeka1024.3.2022Je dáno povodí řeky ve formě orientovaného stromu, v němž každý vrchol je buď soutok nebo molo (či současně obojí). Pro každý úsek mezi sousedícími vrcholy je dána jejich vzdálenost (malé přirozené číslo). Je dáno malé přirozené číslo $d$. Otázka je, zda v povodí existují dvě mola, kde jedno je dosažitelné po proudu od druhého a jejichž vdálenost je přesně $d$. Popište algoritmus, který na danou otázku odpoví.
řeka21031.3.2022Je dáno povodí řeky ve formě orientovaného stromu, v němž každý vrchol je buď soutok nebo molo (či současně obojí). Pro každý úsek mezi sousedícími vrcholy je dána jejich vzdálenost (malé přirozené číslo). Je dáno malé přirozené číslo $d$. Otázka je, zda v povodí existují dvě mola (mohou být na různých přítocích), jejichž (říční) vdálenost je přesně $d$. Popište algoritmus, který na danou otázku odpoví.
rekur107.4.2022Zjednodušte popis funkce $t$ (stačí $\Theta(t)$) dané následující rekurencí: $t(n)=t(\lceil\sqrt n\rceil)+c$, pro $n\ge 3$ a kde $t(n)=n$ pro $1\le n\le 2$.
bprav1014.4.2022Ukažte, že barvící algoritmus pro hledání minimální kostry nemůže žádnou hranu obarvit podruhé (v případě shodné ceny preferujeme neobarvenou hranu).
perm2n521.4.2022Pro danou permutaci čísel od $1$ do $K$ nalezněte její „abecední“ pořadí mezi všemi takovými permutacemi (předpokládejte, že máte aritmetiku s dostatečně velkými čísly).
n2perm521.4.2022Nalezněte permutaci která je mezi permutacemi čísel od $1$ do $K$ na daném $n$ tém „abecedním“ pořadí (předpokládejte, že máte aritmetiku s dostatečně velkými čísly).
permBi1028.4.2022Algoritmicky popište (co možná nejefektivnější) zobrazení a k němu inverzní zobrazení, mezi čísly od 1 do K! a permutacemi čísel od 1 do K (předpokládejte, že máte aritmetiku s dostatečně velkými čísly).
lavl105.5.2022Ukažte, jak je možno z libovolného binárního stromu vytvořit AVL strom (zachovávající inorder pořadí) v lineárním čase a ukažte, že rychleji to nejde.

Id studentacelkemrozpad bodů
F35mult(10), medián(8), řeka(10), řeka2(7)
G48mult(10), medián(8), řeka(6), řeka2(4), rekur(10), bprav(2), n2perm(2+1/2), perm2n(2+1/2), permBi(3), lavl(?)
H36mult(10), medián(7), řeka(6), řeka2(7), n2perm(3), perm2n(3)
I6mult(4), medián(2)
M33,5řeka(5/2), řeka2(0/2), rekur(10), bprav(5), perm2n(3), n2perm(3), lavl(10)
A90indukce(10), mult(10), medián(10), řeka(10), řeka2(10), rekur(10), bprav(10), perm2n(5), n2perm(5), permBi(10)
B89indukce(9), mult(6), medián(10), řeka(9), rekur(10), řeka2(8), bprav(9), n2perm(5), perm2n(5), permBi(8), lavl(10)
C67indukce(1+9/2), mult(6+4/2), medián(10), řeka(6+2/2), bprav(9), perm2n(4), n2perm(3+2/2), permBi(1+9/2), lavl(10/2), rekur(10/2), řeka2(8/2)
E67mult(10), medián(8+2/2), rekur(10), bprav(4+0/2), perm2n(5), n2perm(5), perm2Bi(8), lavl(10), řeka(6/2), řeka2(6/2)
J67medián(7), řeka(8), řeka2(7), rekur(10), bprav(9), n2perm(3+2/2), perm2n(3+2/2), permBi(8), lavl(10)
K70medián(10), řeka(10), řeka2(7), rekur(10), n2perm(5), perm2n(5), permBi(8), indukce(10/2), mult(10/2), bprav(10/2)
D67,5indukce(2+3/2), mult(10), medián(7), řeka(1+7/2), řeka2(7), rekur(3+7/2), bprav(8), perm2n(1+4/2), n2perm(1+4/2), permBi(5), lavl(10)
L71medián(10), řeka(10), řeka2(7), rekur(10), bprav(9), n2perm(5), perm2n(5), lavl(10), permBi(10/2)

Odkazy na obdobné stránky

moje loňské cvičení, texty k cvičení Jana Hrice,


Cvičení 1

Na cvičení jsem oznámil podmínky zápočtu, chvíli jsme si povídali o rozměrech složitosti. Jinak jsem v podstatě celou hodinu budoval oslí můstek k zadání prvního domácího úkolu.

Nejprve jsme odhadovali hloubku AVL stromu. Brzy jsme odhalili, že lepší je počítat velikost nejmenšího stromu dosahujícího dané hloubky a vyšla nám rekurence velice podobná rekurenci Fibonacciho posloupnosti. To byl oslí můstek k řešení lineárních difernečních rovností. Ukázali jsme si, jak je možno v případě, kdy rozdíly v indexech jsou celá čísla popsat homogenní rekurenci v maticové formě. A jak pomocí toho počítat $n$-tý člen posloupnosti pomocí $O(\log n)$ sčítání a násobení (rychle rostoucích čísel). Naznačil jsem, že vlastní čísla matice můžou pomoci k analytickému vyjádření $n$-tého členu posloupnosti. Ve skutečnosti jsme s charakteristickým polynomem rekurence začínali, což jsme dostali z hypotézy, že homogenní řešení budeme hledat ve tvaru polynom krát geometrická posloupnost. Součástí hypotézy je, že je-li v řešení násobení polynomem řádu $k$, tak stejná geometrická posloupnost násobená polynomem menšího řádu je taky řešením, takže jsme goemetrické posloupnosti detekovali pro případ konstant(ních polynomů). Analytický tvar řešení naráží na reprezentaci algerbaických čísel, která nemusí být 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).

V případě, kdy rozdíly indexů nejsou celá čísla, nejde maticový tvar použít, a charakteristická rovnice (stále stejná hypotéza) není polynom. Nicméně v absolutní hodnotě největší (reálný) kořen charakteristické rovnice nám stále dává dobrou představu o chování řešení „diferenční rovnice“.

V případě nalezení tolika nezávislých homogenních řešení, kolik je hodnot nutných k určení posloupnosti, nám soustava lineárních rovnic umožní najít lineární kombinaci homogenních řešení, která se shoduje s požadovanou posloupností. V případě nehomohenity ve tvaru polynom krát geometrická posloupnost hledáme jedno řešení ve tvaru polynom stupně o tolik většího, kolikanásobně se daná geometrická posloupnost vyskytuje v homogenních řešeních (1+maximální stupeň polynomu, jímž v homogenním řešení může být násobena daná geometrická posloupnost). V případě AVL rekurence konstantního polynomu s geometrickou posloupností $1^n$, která není řešením homogenní rovnice jsme tedy hledali konstantu, která je řešením. Matematickou indukcí jsme konstantu nalezli a ověřili, že v tomto případě konstanta stačí. Správně zazněl dotaz jak jsme věděli co máme matematickou indukcí dokazovat (ve skutečnosti jsem nejprve ukázal matematickou indukci a pak až zdůvodnění proč). Což je základní problém matematické indukce ... velice snadno se s ní dokazují pravdivá tvrzení, ale je potřeba "intuice" k tomu vědět co dokazovat. (Výsledek pro hloubku AVL byl logaritmus o základu zlatý řez plus zaokrouhlení.)

Pak jsme se dostali k řešení rekurence $t(n)\in O(n^\alpha)+\sum_{i=1}^k t(a_in)$, která poměrně přirozeně vzniká při analýzách chování algoritmů. 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í“.

Na druhém cvičení jsem naznačil, že substitucí $f(n)=t(e^n)$ (či $t(2^n)$) přechází rekurence do formy o níž jsme si povídali na začátku hodiny, proto 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 (pro $f(n)$ platí rekurence s odčítáním v argumentech, charakteristická rovnice přechází na tvar $1=\sum_i q^{\ln a_i}=\sum_i a_i^{\ln q}$ a z $n^kq^n$ dostáváme po převodu $\ln^k n\cdot n^{\ln q}$).

Na první verzi cvičení jsem špatně definoval dobře uspořádanou množinu. Správná formulace je, že v ní neexistuje nekonečná klesající posloupnost. (K ničemu jsme to nepotřebovali.)


Cvičení 2

Na druhém cvičení jsme probírali různé rekurentní algoritmy s ohledem na jejich složitost.

Začali jsme Kirkpatrick-Seidel algoritmem na hledání konvexního obalu. V něm se neobvyklé rekurence vyskytují ne několika místech. První byla rekurence, kde jsme k časovému odhadu potřebovali rekurenci závislou na dvou parametrech. Nemohli jsme tak použít výsledky z předchozího cvičení a mohli jsme se opřít jen o princip důkazu.

Abychom dosáhli správné rekurence potřebovali jsme hledat mediánovou polopřímku. Rekurence pro hledání worst case k-tého prvku dle uspořádání vedla v prvním případě ke složitosti $\Theta(n\log n)$, naštěstí šlo změnit parametry algoritmu tak, aby rekurence vedla ke složitosti $\Theta(n)$. (Potřebovali jsme rekurenci s nestejně velkými částmi.)

Pak jsme ještě potřebovali rekurencí typu prune and search, tedy případu rozděl a panuj, kdy dělíme na jedinou část. Použili jsme to v algoritmu hledání „horního mostu“, což je součást konvexního obalu množiny bodů jednoznačně určená protínající polopřímkou. Potřebovali jsme pro to medián směrů dvojic a jeho porovnání s neznámým směrem mostu. To nám umožnilo alespoň v polovině dvojic jeden z vrcholů zahodit. Počet bodů se nám tak podařilo v lineárním čase zredukovat z $n$ na nejvýš $1+3(n-1)/4$. To je od určitého $n_0$ určitě nejvýš $4n/5$, takže jsme dostali lineární algoritmus.

Pak jsme se zabývali efektivním násobením matic. Předvedl jsem zápisově efektivní značení, a ukázali jsme jak triviálně pomocí 8 násobení matic poloviční velikosti získat složitost $O(n^3)$ ... měřeno v rozměru matice, nikoli v ploše. Rozhodli jsme se nakombinovat stejný výsledek jen pomocí 7 násobení matic poloviční velikosti (a dostat tak složitost $O(n^{\log_27})$).

Ukázal jsem jak nakombinovat první tři součiny a jak jejich +- kombinací skoro získat čtvrtinu výsledné matice. Potřebovali jsme přidat ještě jeden součin, aby to vyšlo. Pak jsem nažnačil která +- kombinace je dobrý základ pro získání druhé a která třetí čtvrtiny výsledku. Součin který je potřeba odečíst jsme již snadno doplnili. Pro poslední čtvrtinu jste našli i mezivýsledek ze kterého je potřeba začít.

Pro otrlé: Schéma fungovalo tak, že v každém ze 7 vzorců součinů součin podmatice $A_{i,j}B_{k,l}$ buď vůbec nefiguroval, nebo tam byl s koeficientem 1 či -1, ale nenulové koeficienty u dané čtveřice indexů měly vždy stejné znaménko. Navíc měly různá znaménka vždy ty 2 pozice, které se vyskytují ve výsledných čtvrtinách součinu. Z hlediska kombinování mezivýsledků jsme se pak nemuseli starat o koeficienty, při odečítání dvou takových součinů se vynulovaly hodnoty v průniku nenulových, pouze symetrická diference nenulových koeficientů se projevila ve výsledku (jediná výjimka měla výsledný koeficient ve tvaru 2-1). Na schématu tedy bylo především důležité, které hodnoty koeficientů jsou nulové a které nenulové. V součinu jsme samozřejmě omezeni tím, že nenulovost koeficientu u $A_{i,j}B_{k,l}$ i $A_{m,n}B_{o,p}$ garantuje nenulovost u $A_{i,j}B_{o,p}$ i $A_{m,n}B_{k,l}$. Podmíku na stejnost znamének u příslušných koeficientů zajistíme jednoduše tak, že do činitele zahrnujeme $A_{i,j}$ pro dané $(i,j)$ vždy se stejným znaménkem (případně s nulou). Totéž pro $B_{i,j}$. K zajištění aby příslušné koeficienty měly v součinech různá znaménka zjistíme, že podmínka je, aby součin všech koeficientů, kterými jsou (v případě nenulovosti) násobeny $A_{i,j}$ musí být 1 a totéž platí pro koeficienty pro $B_{i,j}$. Navíc musí platit, že součin koeficientů jimiž je násobeno $A_{1,j}$ krát součin koeficientů, kterými je násobeno $B_{i,1}$ je -1. Máme tedy $2^{8-3}$ možností, jak si předvybrat znaménka, pro daný výběr nenulovostí koeficientů.


Cvičení 3

Pracovali jsme ve skupinkách, řešili jsme příklady s výpočtem binárních operací pomocí rekurentních vztahů (měli jsme zjistit, co který rekurzivní program počítá, popsat invarianty garantující korektnost a konečnost). Pak jsme asymptoticky porovnávali funkce. Na závěr jsme naznačili řešení třetiny prvního domácího úkolu.


Cvičení 4

Povídali jsme si o pohledávání grafů, jak explicitních, tak implicitních. Popsali jsme si prohledávání do šířky a prohledávání do hloubky. Uvědomili jsme si jejich nevýhody při prohledávání gigantických grafů. Přišli jsme jak s alternativou iterative deepening, tak se zavedením dolních odhadů vzdálenosti do cíle, může výrazně zúžit prostor prohedávání. Pak jsme se věnovali prohledávání explicitních grafů „bez cíle“. Srovnali jsme prohledávání ve smyslu lokality prohledávání a možnosti aktualizovat globální informace o stavu prohledávání. V tomto ohledu prohledávání má prohledávání do hloubky podstatné výhody.

Zavedli jsme terminologii prohledávání do hloubky ve smyslu stavu vrcholů v průběhu prohledávání, klasifikace hran (stromové a zpětné v neorientovaných a navíc dopředné a příčné v orientovaných), zavedli jsme si inorder, postorder (a prokládané) číslování vrcholů. Věnovali jsme se komponentám vrcholové a hranové dvousouvislosti a jejich lokalizaci, lokalizaci mostů a artikulací. Z toho důvodu jsme zavedli číslování low.

Na první verzi cvičení jsme řešili úlohu nejvzdálenějších bodů v grafu ve tvaru stromu. Stihli jsme definovat silně souvislé komponenty, ale již jsme se nedostali k žádnému algoritmu na jejich lokalizaci.

Na druhé verzi cvičení jsme si definovali jak silně souvislé komponenty, tak topologické uspořádání (silně souvislých komponent) a stihli jsme si uvědomit, jak souvisí postorder číslování s topologickým uspořádáním grafu s jednovrcholovými silně souvislými komponentami. K žádnému algoritmu na hledání silně souvislých komponent jsme se taky nedostali.


Cvičení 5

Na druhé verzi cvičení jsme udělali příklad s největší vzdáleností ve stromě. Na obou verzích jsme se věnovali algoritmům na topologické třídění silně souvislých komponent. Naznačili jsme jak dvojprůchodový (Kosaraju Sharir), tak jednoprůchodový (Tarjan). To co jsem povídal o Kosarju Sharir algoritmu bylo ve skutečnosti špatně. (Pokud porováme největší postorder čísla v silně souvislých komponentách, tak pokud vede cesta z $a$ do $b$, ale ne naopak, tak maximální postorder číslo vkomponentě s $a$ je větší než v komponentě s $b$. Stromová cesta z komponenty obsahující $a$ do $b$ nemusí procházet vrcholem $a$, takže postorder vrcholu $a$ může být menší než postorder vrcholu $b$.)

Následně jsme se věnovali hledání minimálních cen sledů v orientovaných ohodnocených grafech. Prolétli jsme algoritmy postupného zvětšování množiny přípustných vnitřních vrcholů sledů (Floyd Warshall), algoritmus opakované relaxace hran (Bellman Ford) a algoritmus pěstování „stromu“ ze zdroje (Dijkstra). (uvědomili jsme si, kdy je možno který algoritmus použít). Pouze poslední algoritmus přinášel zajímavá implementační rozhodnutí, takže jsme si na konci hodiny povídali a vhodné datové struktuře pro implementaci (interface a částečný popis).


Cvičení 6

Řešili jsme úlohy, kde se hodilo prohledávání do hloubky buď přímo, nebo se hodily pojmy, které jsme prohledáváním do hloubky dokázali spočítat.


Cvičení 7

Zabývali jsme se algoritmy pro hledání minimální kostry. Začali jsme popisem nedeterministického barvícího algoritmu (barvení minimální hrany řezu bez modré hrany modře, případně maximální červené hrany v cyklu bez červené hrany červeně), následně jsme popisovali konkretizace tohoto algoritmu (Kruskal, Jarník-Prim-Dijkstra, Borůvka(tam to komplikuje paralelismus), Fredman-Tarjan). U Kruskalova algoritmu jsme se věnovali implementaci pomocí disjoint find union a proto jsme si povídali o příslušné datové struktuře. Zmínil jsem i variantu struktury s baktrackingem (bez implementačních detailů). Fredman-Tarjan algoritmus by si zasloužil popis hald s $O(1)$ DecreaseKey, ale nějak to letos nevyšlo.


Cvičení 8

Věnovali jsme se vyhledávacím stromům obecně (interface pro intervalové dotazy), následně jsem se věnovali binárním vyhledávacím stromům. Povídali jsme si o invariantech vyvažování AVL a čeveno-černých stromů. Porovnali jsme asymptotické chování těchto způsobů vyvažování (worstcase odhad hloubky, počty rotací, počty změn vyvažovací informace, velikost změny vyvažovací informace při komprimované reprezentaci, důsledky na persistentní verze struktury). Pak jsme probrali jak v binárních stromech proběhne insert a delete až do fáze začátku vyvažování. Na první verzi cvičení jsme stihli probrat jak AVL vyvažování po insert, tak po delete. Na druhé verzi cvičení jsme nestihli ani jedno z nich.


Cvičení 9

Povídali jsme si o hashování a probrali jsme příklad s $n$-tým součtem dvojic, kde oba sčítance jsou vybírány z uspořádaných $n$-prvkových polí.


Cvičení 9+3/4

Na čtvrtečním (nadbytečném) cvičení jsme si povídali o haldách.


Cvičení 10

Na desátém cvičení jsme si chvilku připomínali rozděl a panuj a chvilku zkoušeli vyvažovat červeno-černé stromy.


Cvičení 11

Na jedenáctém cvičení jsme si hráli s geometrickým problémem nalezení nejmenšího kruhu obsahujícího danou množinu bodů v rovině. Jenalo se o civčení na prune and search. Postupně jsme odvodili Megiddův algoritmus. (Na čtvrteční verzi jsem špatně popsal, jak z nejmenšího kruhu jehož střed je omezen na danou přímku určit, v které polorovině se střed nachází. Chybně jsem označil že již máme úlohu vyřešenu i v některých případech, kdy střed na přímce neležel.) Na konci hodiny jsem ještě hovořil o Welzlově randomizovaném algoritmu, jeho chybě v abstraktní verzi, možnosti opravy, neprojevení se v doporučené implementaci a korekci publikované trojicí Matoušek, Welzl, Sharir (kde ale chyba abstraktní verze není explicitně zmíněna).


Cvičení 12

Na předposledním cvičení jsme se bavili o dynamickém programování. Začali jsme úlohou „z praxe“ - rozdělením ascii zprávy na úseky numerické, alfanumerické a ascii tak, aby bitová délka zprávy byla co nejmenší (podúloha při vytváření QR kódů).

Následně jsme se bavili o nejmenším společném předku či největším společném potomkovi čísel vůči relaci „být obsažen v“.

Do konce hodiny jsme stihli ještě lokalizaci největšího čtverce rovnoměžného se souřadnými osami v černobílé bitmapě.


Cvičení 13

Na posledním cvičení jsme řešili hádanky (související s informatikou).