Vladan Majerech - NTIN060 Algoritmy a datové struktury 1

Last Modified: 3.4.2024

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

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 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 letos vyzkouším 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í jsem oznámil podmínky zápočtu, pak jsem v podstatě celou hodinu budoval oslí můstek k zadání prvního domácího úkolu.

Začali jsme skokem do hluboké vody ř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 podstatě 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í“.

Ve zbylé půlhodině jsme aplikovali naše pozorování na rozbor Kirkpatrick-Seidel algoritmu na hledání konvexního obalu. Jednalo se o nestandardní použití rekurence, kdy jsme nemohli použít výsledné tvrzení, ale museli jsme se znovu podívat dovnitř důkazu (případ $S_\alpha=1$) abychom mohli zohlednit vliv hodnoty $h$ (velikosti výstupu algoritmu). Kromě toho se v algoritmu vyskytuje jak rekurence s $a_1\not=a_2$, tak rekurence s $k=1$.

Příště si řekneme 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 (a někteří i problém s otráveným vínem) 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 1 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.

Plánoval jsem taky řešit rekurenci $t(n)=t(n/2)+t(n/4)+1$, ale časově se tento oslí můstek zařadit nepodařilo. Místo toho jsme v poslední necelé půlhodině probrali Strassenův algoritmus využívající toho, že pomocí odčítání (potřebujeme aby bylo definované) a sčítání vhodných podmatic jsme schopni zredukovat počet násobení podmatic poloviční velikosti z 8 na 7, takže místo rekurence $t(n)=8t(n/2)+cn^2$ s řešením $O(n^{\log_2 8})$ dostáváme rekurenci $t(n)=7t(n/2)+cn^2$ s řešením $O(n^{\log_2 7})$ (Hledali jsme $\beta$, pro které je $S_\beta=1$.). Součiny v algoritmu měly u každého $A_{i,j}\cdot B_{k,\ell}$ (indexujeme poloviny matice, tedy $i,j,k,\ell\in \{0,1\}$) vždy stejný reálný koeficient s absolutní hodnotou $1$, který mohl případně být nahrazen 0. Dva potřebné součiny jsme vždy dostali jako rozdíl takovýchto koeficientů, kde díky pečlivému plánování „stínové magii“ se koeficienty všech ostatních součinů vyrušily. Z toho dostáváme podmínku na opačná znaménka čtyř dvojic součinů. (Pro otrlé: Což znamená, že koeficienty násobení řádku matice A a sloupců matice B musí vždy v součinu být -1. Protože to platí pro každou kombinaci výběru řádků a sloupců, musí být součin koeficientů násobení matice A roven 1, stejně tak součin koeficientů násobení matice B. Správnost znaménka čtvrtého součinu je tím vynucena. Máme tedy $2^8/2^3=32$ možností jak zvolit koeficienty, kterými budou které části matic násobeny (pokud budou zastoupeny). Nejspíš bychom mohli rozmístit nenulové hodnoty součinů jinak (triviálně prohozením řádků či sloupců), čímž bychom se dostali na $2^2\cdot 32=128$ variant algoritmu. Vždy bychom měli jeden „řádkový“, jeden „sloupcový“, jeden „řádko-sloupcový“ a dopočítali bychom potřebu jednoho „$A$-čtvercového“ součinu, „$B$-čtvercového“ a dvou „bodových“ součinů.) Celý algoritmus by nešlo prezentovat pomocí klasického zápisu součtu podmatic s indexy násobených koeficienty. Opět bylo jedinou šancí extrahovat jen to podstatné díky vlastní komprimované symbolice s „polohovým“ značením. (BTW: Nedávno jsem se dozvěděl, že ji Albert Einstein v jiném kontextu taky používal (tenzory).) Jedná se pravděpodobně o Winograd variantu Strassenova algoritmu.

Cvičení 3

Řešili jsme problém hledání $n$ tého podle velikosti v implicitně zadané množině $n^2$ čísel. Šikovnou dekompozicí množiny kandidátů do skupin se nám problém podařilo redukovat na problém váženého mediánu. Výsledný algoritmus měl složitost $O(\sqrt{n}\log^2 n)$, což vzhledem k velikosti $\Theta(n)$ implicitního zadání šlo realizovat jen za předpokladu, že parametry jsou předané odkazem na pole, kde vytvoření pole není započítáno do složitosti algoritmu.

Ke konci hodiny jsme začali řešit prohledávání grafů.

Cvičení 4

Řešili jsme prohledávání grafů. Věnovali jsme se nejprve problémům spojeným s prohledáváním implicitních grafů. (Nemůžeme značkovat vrcholy, nemusíme mít dost paměti pro celý graf, takže prohledávání do šířky krachuje na paměť, zatímco prohledávání do hloubky na čas při zabloudění. Navrhli jsme postupné prohlubování, přidali transpoziční tabulky pro (negarantované) urychlení, přidali heuristické dolní odhady kvůli směřování prohledávání. Velikosti tabulek pro rohy rubikovy kostky jsou $8!\cdot 3^7=5160960$ a pro hrany $12!\cdot 2^{11}=980995276800$ na cvičení jsem zapomněl započítat otáčení kostiček. Při uvažování jen 6 hran velikost druhé tabulky klasá na $12!/6!\cdot 2^6=42577920$.

Při popisu transpozičních tabulek jsme se dostali k hešovacím tabulkám (a univerzálnímu hešování). V dalším můžeme předpokládat, že máme datovou strukturu implicitného pole, kde adresujeme pomocí poměrně obecných klíčů a randomizovaná složitost jednotlivých přístupů je $O(1)$. Většina operačních systémů nám nedovolí alokovat neinicializované pole velikosti $n$ v konstantním čase, takže ta složitost je nejspíš amortizovaně randomizovaná, ale vzhledem k přepínání tásků operačním systémem nás stejně většinou zajímá jen amortizovaná složitost.

Pak jsme se věnovali prohledávání explicitních grafů a srovnávali výhody/nevýhody BFS a DFS. Zmínil jsem využití BFS (spolu se dvěmi DFS) při hledání planárního separátoru, i to, že vzhledem ke ztrátě kontextu se BFS málokdy hodí ke zjišťování informací o grafu.

Pak jsme se věnovali DFS. Klasifikovali jsme hrany dle prohledávání jak neorientovaného, tak orientovaného grafu (zavedli kvůli tomu preorder a postorder číslování). Pak jsme si definovali komponenty, komponenty hranové dvousouvislosti a komponenty vrcholové dvousouvislosti, ukázali jsme, jak je možné najít mosty a artikulace i jednotlivé třídy rozkladů na příslušné komponenty. Pro ty třídy rozkladů jsme potřebovali samostatný zásobník. Pro detekci jsme potřebovali definovat funkci low, která eviduje jak blízko ke kořeni (minimální preorder) je možno dojít pomocí orientovaných stromových hran a jedné zpětné hrany. Funkci low je pomocí DFS snadné aktualizovat v postorder pořadí.

Cvičení 5

Věnovali jsme se prohledávání do hloubky za účelem zjišťování informací o grafu (dvousouvislosti).

Cvičení 6

Věnovali jsme se prohledávání do hloubky za účelem zjišťování informací o grafu (topologické uspořádán slně souvislých komponent). Následně jsme se věnovali Dijkstrově (Jarníkově) algoritmu.

Cvičení 7

Věnovali jsme se krátce hledání nejlacinějších sledů v grafu, kde mohou být i záporné ceny (Bellman Ford, Floyd Warshal), následně jsme rozebírali, k jaké struktuře vede lenost s extrémně drahým porovnáváním pokud chceme datovou strukuru podporující Diskstrův algoritmus (mimo jiné jsme řešili úlohu s čokoládou). Popsali jsme jaká porovnávání provádíme a zachycovali jsme to haldovitě uspořádaným orientovaným lesem. Zadefinovali jsme si několik složek potenciálu (kde si spoříme čas na budoucí práci), popsali jsme jak zajistit, aby stromy nebyly příliš široké.

Ke konci hodiny jsme se věnovali tomu, jaké změny je potřeba udělat, chceme-li příslušné operace provádět ve worst case časech. To neumožnilo udržovat lokální podmínku úzkosti (dítě smí ztratit nejvýš jedno své dítě, aby garantovalo dostatečnou velikost - Fibnacciho poslopnost). Místo toho jsme schopni udržovat podmínku na celkový součet ztrát (odpovídající počtu různých řádů vrcholů, buď máme od každého řádu nejvýš jeden a prázdnou vyrovnávací paměť ztrátových konfliktů, nebo máme nějaké ztrátové konflikty ve vyrovnávací paměti, pak je ale celková ztráta menší. Neprázdná vyrovnávací paměť odpovídá situaci, kdy máme příležitost výrazně snížit celkovou ztrátu, ale worst case omezení nás nutí nechat část práce na později. Pokud bychom se tomu věnovali, dá se upočítat, že v každém kroku, dokud nevyprázdníme vyrovnávací paměť, tak máme čas snížit celkovou ztrátu. Obdobně co se týče „mimořádných“ hran dokážeme jejich počet udržovat na počtu různých řádů. Buď máme nejvýš jeden podstrom od každého řádu připojený mimořádnou hranou, nebo máme celkový počet podstromů připojených mimořádnou hranou menší a nepráznou vyrovnávací paměť. Opět v každém kroku, dokud máme neprázdnou vyrovnávací paměť tak máme čas snížit počet podstromů připojených mimořádnou hranou. Potenciály se k takovému rozboru hodí.) Dá se upočítat, že maxální řád pro haldu vekosti $n$ při takovémto omezení na celkovou ztrátu vede k logaritmické funkci o větším základu než zlatý řez ke kterému vede lokální pomínka na ztráty.

((Pokud bychom potřebovali worst case datovou strukturu podporující zároveň operaci Meld(slučování hald), tak struturálně stačí připojit druhou haldu mimořádnou hranou. Působí to ale problém s udržováním úzkosti stromů a speciálně s postupně se měnícím omezením worst case času způsobeným snižování velikosti haldy pomocí ExtractMin. Dá se udělat trik s udržováním uzlů haldy v seznamu, kde omezení na úzkost je určeno pozicí v seznamu. Místo aby snížení $n$ o 1 znamenalo změnu podmínek na všechny uzly, přemístěním konstantního počtu uzlů v seznamu docílíme toho, že podmínky na úzkost se změní jen konstantnímu počtu uzlů a to není problém ošetřit. Bez operace Meld nevznikají poruchy v úzkosti, které by bylo potřeba individuálně řešit.))

Nezmínil jsem nutnou podmínku na různost klíčů ve worst case varinatě (dodatečný rozlišující index), jinak by mohl být z lesa vytržen věneček uzlů se stejným klíčem, pod nimiž by byly haldově připojené podstromy.

Určitě by stálo za to rozmyslet si, jak haldovité stromy reprezentovat.

Cvičení 8

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ů).