Vladan Majerech - NTIN060 Algoritmy a datové struktury 1

Last Modified: 12.3.2026

Valid HTML 4.01 Strict

Index

zápočtové příklady, odkazy, cvičení 1, cvičení 2, cvičení 3, cvičení 4,

Zápočtové příklady

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

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 15:40 v datum cvičení (tedy čas začátku 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. Na domácí úkoly použijeme owl. Pokud jste ode mne nedostali e-mail s linkem, tak mne kontaktujte.

Odkazy na obdobné stránky

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

Cvičení 1

Na cvičení jsme většinu času budovali oslí můstek k zadání prvního domácího úkolu.

Zformulovali jsme rozumně obecnou formu rekurentního odhadu času algoritmu $t(n)\le cn^\alpha+\sum_{i=1}^k t(a_in)$, s počáteční podmínkou $t(n)\le C$, pro $n\le n_0$. Po chvilce seznamování se s rekurencí, jsme přešli k proslovu 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 efektivní organizaci zápisu) a rozdělili jsme výpočet na část s $cn^\alpha$ a na části s $t$, které je ještě potřeba rozepsat. Studenti krásně spolupracovali jak v tvorbě komprimované notace, tak v jejím použití. Homogenita zápisu v každé části nám umožnila nepsat zbytečně mnoho symbolů a věnovat se místo toho podstatě problému.

Ukázalo se, že stěžejní je hodnota $S(\alpha)=\sum a_i^\alpha$. Pokud je $S(\alpha)<1$, vyjde bez uvažování počáteční podmínky $t(n)=cn^\alpha/(1-S(\alpha))\in O(n^\alpha)$, pokud je $S(\alpha)=1$, tak s uvažováním počáteční podmínky, ale bez zohledňování konstanty $C$ v odhadu, 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, ale i kvůli zohlednění konstanty $C$ v počáteční podmínce je vhodné všechny odvozené výsledky zkontrolovat například „matematickou indukcí“. Můžeme to vnímat tak, že jsme nic nedokázali, ale získali jsme velmi dobrou představu o tom, jaké tvrzení bychom měli dokazovat.

Naznačil jsem, že matematickou indukci nemusíme dělat pro krok z $n$ na $n+1$, ale mnohdy se hodí předpokládat tvrzení „platí tvrzení pro všechna $n\le n_1-1$“ a dokázat jakožto indukční krok „platí tvrzení pro všechna $n\le n_1$“ (stačí se koncentrovat jen na $n_1$). V podstatě se jedná o formulaci neexistuje nejmenší $n$ pro nějž by tvrzení neplatilo. V našem případě je vhodné dokazovat tvrzení existují vhodné konstanty (nezávislé na $n$) pro které je $t(n)$ v daném tvaru a v průběhu důkazu zjistit omezení, které konstanty musí splňovat, aby to vyšlo.

Pak jsme ukázali použití obdobných rekurencí v praxi ve formě Kirkpatrick-Seidel algoritmu na hledání konvexního obalu. Jednalo se o nestandardní použití rekurence, kterou neumíme napasovat na plánované tvrzení, ale jsme schopni vyřešit technikou použitou v důkazu tvrzení. Kromě hlavní rekurence poskytuje algoritmus i vedlejší rekurenci zvláštní tím, že jde o rozklad na jediný podproblém (technika prune and search na hledání průniku konvexního obalu s předem zvolenou polopřímkou) a dvakrát rekurenci, kde je problém pouštěn na dvě různě velké části (hledání mediánu). Ukázali jsme si dvě téměř stejné implementace algoritmu na hledání mediánu ($k$-tého z $n>k$ prvků) pomocí volby pivota jakožto aproximace mediánu na základě vhodně zvolené podmnožiny zadání. Vhodnou volbu parametrizace jsme byli schopni zvolit na základě znalosti tvrzení (v prvním případě by vyšlo $\Theta(n\log n)$, ale v druhém případě stačilo $\Theta(n)$.

Příště budeme řešit nějakou hádanku, řekneme si něco o lineárních rekurenčních (ne)rovnicích a ukážeme další aplikace výše uvedené rekurence.

Cvičení 2

Nejprve jsme řešili vajíčkový problém. Na něm se ukázalo, že u pomalu rostoucích funkcí je mnohem efektivnější kódovat relaci „jsem nejvýš hodnota funkce“ pomocí funkce vyjadřující závislost minimálního parametru, pro nějž se daná hodnota nabývá. Pro takový komprimovaný popis je mnohdy mnohem jednodušší najít rekurentní vztah. V našem případě šlo o rekurenci známou z Pascalova trojúhelníku, jen jsme si museli uvědomit odlišnost v počátečních podmínkách, ale i to, jak se projeví změna o jedna v počátečních podmínkách. Výsledný vzorec pak už nebylo těžké odvodit. Jakýkoli algoritmus prohledávání stavu úlohy s touto abslutně přesnou heuristikou pak dává optimální řešení úlohy (heuristiky bývají nepřesné, ale to asi není definiční vlastnost, takže absolutně přesná haeristika snad není protimluv).

Následně jsme stejnou techniku použili na odhad hloubky AVL stromu. 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. K hledání vlastních čísel matice se často používá charakteristický polynom, který v našem případě můžeme získat nezávisle na maticovém řešení rekurence přímo z předpokladu, že řešením rekurence je geometrická posloupnost krát polynom. 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). (Matice můžeme použít k přesné realizaci v rekurenci potřebných algebraických čísel, čímž bychom se jinou cestou dostali k maticové formě řešení rekurence).

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 řešení ve tvaru, kde stupeň příslušného polynomu homogenního řešení stoupne o 1+stupeň polynomu řešení nehomogenního.

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“. Což po substituci argumentu funkce (exponenciální resp. logaritmická) vede k jinému náhledu na řešení rekurence z minulé hodiny.

Na konci hodiny jsem rychle probral Strassenův algoritmus.

Cvičení 3

Povídali jsme si o prohledávání grafů. Připomněli jsme si prohledávání do šířky i do hloubky, uvědomili jsme si jejich problémy při prohledávání velkých (implicitních) grafů. Ukázalo se, že mnohdy je nejlepší kombinovat je pomocí iterativního prohlubování. Taky se hodí heuristický (dolní) odhad zbývající vzdálenosti. V kontextu implicitních grafů (s heuristickými odhady) jsem zmínil i algoritmus beam search, který se hodí v případech, kdy je paměťově náročná evidence implicitního vrcholu, takže nám musí stačit jich uchovávat pouze malý počet.

Pak jsme se více zaměřili na prohledávání do hloubky. Zavedli jsme číslování vrcholů, klasifikaci hran (jak v neorientovaném, tak orientovaném případě) a rozmysleli jsme si co jsou komponenty hranové či vrcholové 2 souvislosti a jak je detekovat.

Cvičení 4

Nejprve jsme prošli jednoprůchdový algoritmus na topologicé uspořádání a detekci silně souvislých komponent. V jednu chvíli jsem opravil v rekurentním vztahu $in$ na $esc$. Ve skutečnosti to mělo být $in$ pro nestromovou a $esc$ pro stromovou hranou připojené sousedy. (Alternatvně definujeme $esc$ pro hrany odlišně pro stromové (hodnota z koncového vrcholu) a nestromové (in koncového vrcholu) ... používáme $esc$ hrany) Pak jsme ukazovali užitečnost zpracování informace z podstromů v postorder pořadí DFS. Bylo to na příkladě určování extrémní vzdálenosti v podstromě s cenami vah obsahujícími jak kladná tak záporná čísla.

Pak jsme si připomněli algoritmy pro vyhledávání nejlacinějších sledů Dijstra (nezáporné hrany z jednoho zdroje), Bellman Ford (bez záporných cyklů standardně z jednho zdroje) a Floyd-Warshal (pro všechny dvojce záčátek a konec, včetně záporných cyklů).

Ve variantě nejkratších cest v implicitním nekonečném grafu s neznámou předperiodou, ale známou „periodickou hranou“ by při použití Dijkstrova algoritmu bylo potřeba při zvětšení grafu začít počítat od začátku (ke zlepšení (v předperiodě) může dojít přes vrchol, který v menším grafu nebyl), zatímco u Bellman Ford algoritmu můžeme pokračovat s dosavadními mezivýsledky.

K vhodným datovým strukturám jsme se nestihli dostat.