Vladan Majerech - NTIN061 Algoritmy a datové struktury II

Last Modified: 30.9.2022

Valid HTML 4.01 Strict ... vlastně už jen HTML, ale jaký obrázek?

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

Pro získání zápočtu z NTIN061 je potřeba získat (3/5 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 odevzdání po termínu je jen poloviční počet bodů. Termín je do počátku cvičení příslušného dne, odevzdáváme v běžném čitelném formátu (např v těle mailu či v příloze .txt,.pdf,.jpg,.png) e-mailem. Příklady s body uvedenými v závorce jsou bonusové, body je možno získat, ale nepočítají se do limitu požadovaných bodů. Domácí úlohy i souhrny cvičení budu nejspíš pravidelně publikovat až po pondělních cvičeních.

KódBodyTermín odevzdáníZadání
interval1018.10.2021 Je při vypisování intervalu hodnot v binárním vyhledávacím stromu délka absolvované cesty (nemáme explicitní next pointery) $\in O(h + r)$, kde $h$ je hloubka stromu a $r$ počet vypsaných hodnot? Přesvědčivě zdůvodněte!
jehly1025.10.2021 Spočtěte, kolikrát se dané jehly vyskytují v daném seně (podslova v textu). Zajímají mne počty každé jehly zvlášť.
podposloupnost101.11.2021 Spočtěte, kolikrát se daná jehla vyskytne v daném seně (dva řetězce, seno mnohem delší) jako podposloupnost (možnost proložení jinými znaky). Například v BARBARAR je BAR 9 krát.
věže108.11.2021 Máme šachovnici $m\times n$ a na některých políčkách stojí sloupy. Na políčka (bez sloupů) je možno umísťovat věže. Každá věž ohrožuje políčka ve stejné řadě a stejném sloupci, ale pouze k nejbližšímu sloupu v daném směru. Otázkou je, kolik věží je možno rozmístit tak, aby žádná nestála na políčku ohroženém jinou věží. No a na Vás je popsat, jak nalézt odpověď (můžete používat „známé“ algoritmy jako podprogramy).
kluby1015.11.2021 Na kolejích jsou různé kluby, koleják může být součástí libovolného počtu klubů. Jste postaveni před úlohu vybrat z každého klubu předsedu a místopředsedu a to tak, aby každý koleják byl vybrán za nejvýš jeden klub a pro něj do právě jedné funkce.
cesty1022.11.2021 Pro dané vrcholy $u$, $v$ v orientovaném grafu nalezněte maximální počet vrcholově disjunktních cest z $u$ do $v$.
střepy1029.11.2021 Pro ultimátní šifrovací hru je potřeba vyřešit $k$ z velkého počtu šifer. Výsledkem každé šifry bude „střípek“ informace. Autor šifrovací hry dostal předem $n$-bitový řetězec „výsledek“ ($n$ je mnohem větší než $k$, šifer je $2^{\Theta(n)}$). Navrhněte metodu, jak definovat střípky tak, aby nalezení libovolných $k-1$ střípků nestačilo k odhalení výsledku, zatímco nalezení libovolných $k$ střípků k odhalení výsledku stačilo. Vztah střípků k výsledku má být veřejnou informací (nenechte se zmást slovem střípek, ten může být ve skutečnosti větší než výsledek).
porovnání106.12.2021 Vytvořte co nejmělčí hradlovou síť, která pro n-bitová čísla $a$, $b$ vydá $1$ právě když $a\le b$.
mult1013.12.2021 Nastiňte konstrukci hradlové sítě, pro vynásobení dvou n-bitových čísel. Řešte nezávisle úlohu zaměřenou na minimalizaci hloubky od úlohy zaměřené na minimalizaci velikosti (odhadněte vždy oba rozměry). (Přesné rozměry nepožaduji, stačí „asymptotický odhad“, nicméně optimalizujte pro $n=2^{16}$).
Hamilton10 Hamiltonovská cesta v grafu, je cesta obsahující všechny vrcholy grafu (právě jednou). Hamiltonovská kružnice je Hamiltonovská cesta, kde navíc z koncového vrcholu vede hrana do počátečního vrcholu cesty. Ukažte, že jak v orientovaných, tak v neorientovaných grafech je (až na polynom) stejně náročné rozhodnout, zda v něm existuje Hamiltonovská cesta, jako to, že v něm existuje Hamiltonovská kružnice. Ukažte, že je stejně náročné (až na polynom) rozhodnout, zda existuje Hamiltonovská cesta, ve všech variantách v závislosti na tom, které koncové vrcholy cesty jsou zadány.

Id studentacelkemrozpad bodů
Z32interval(6), jehly(6), cesty(10), porovnání(10)
k6interval(0), jehly(6)
t49interval(2), jehly(6), věže(10), kluby(10), cesty(10), porovnání(4), mult(7)
É29.5interval(10), podposloupnost(7), kluby(10/2), cesty(5+5/2)
Ř51interval(10), jehly(6/2), podposloupnost(8), věže(10), kluby(10/2), cesty(0), porovnání(10), mult(5)
Š10interval(10)
á6jehly(6)
č6jehly(6)
ě6jehly(6)
A75interval(10), jehly(10), podposloupnost(10), věže(10), kluby(10), cesty(10), střepy(10), mult(5)
B80interval(10), jehly(10), podposloupnost(10), věže(10), kluby(10), cesty(10), střepy(10), porovnání(10)
C70interval(10), jehly(10), podposloupnost(10), věže(10), kluby(10), cesty(10), střepy(10)
D70interval(10), jehly(10), podposloupnost(10), věže(10), kluby(10), cesty(10), střepy(10)
E70interval(10), jehly(10), podposloupnost(10), věže(10), kluby(10), cesty(10), střepy(10)
F70interval(10), jehly(10), podposloupnost(10), věže(10), kluby(10), cesty(10), střepy(10)
G71interval(10), jehly(6), podposloupnost(10), věže(10), kluby(10), cesty(10), střepy(10), Hamilton(5)
H70interval(10), jehly(10), podposloupnost(10), věže(10), kluby(10), cesty(10), porovnání(10)
I71interval(10), jehly(6), podposloupnost(5), věže(10), kluby(10), cesty(10), střepy(10), porovnání(10)
J76interval(10), jehly(6), podposloupnost(10), věže(10), kluby(10), cesty(10), střepy(10), porovnání(10)
K76interval(10), jehly(6), podposloupnost(10), věže(10), kluby(10), cesty(10), střepy(10), porovnávání(10)
L71.5interval(10), jehly(10), podposloupnost(9+1/2), věže(10), kluby(10), cesty(10), mult(7), porovnání(10/2)
M78interval(10), jehly(10), podposloupnost(8), věže(10), kluby(10), cesty(10), střepy(10), porovnání(10)
N63interval(10), jehly(6/2), kluby(10), cesty(10/2), střepy(10), porovnání(10), mult(5), Hamilton(10)
O76interval(10), jehly(10), podposloupnost(5), věže(10), kluby(10), cesty(10), střepy(2), porovnání(10), mult(9)
P76interval(10), jehly(8), podposloupnost(8), věže(10), kluby(10), cesty(10), porovnání(10), Hamilton(10)
Q70interval(6), jehly(10), podposloupnost(10), věže(0+10/2), kluby(10), cesty(10), střepy(0), porovnání(10), mult(9)
R61interval(10), jehly(6), podposloupnost(10), věže(10), kluby(10), cesty(10), porovnání(10/2)
S73interval(6), jehly(6), podposloupnost(10), věže(10), kluby(10), cesty(10), porovnání(10), mult(5), Hamilton(6)
T71interval(8), jehly(6), podposloupnost(10), věže(10), kluby(10), cesty(10), střepy(10), Hamilton(7)
U73interval(8), jehly(10), podposloupnost(10), věže(10), kluby(10), střepy(10), porovnání(10), cesty(10/2)
V78interval(10), jehly(9), podposloupnost(9), věže(10), kluby(10), cesty(10), střepy(10), porovnání(10)
W75interval(10), jehly(9), podposloupnost(6), věže(10), kluby(10), cesty(10), střepy(10), porovnání(10)
X60interval(10), jehly(6), podposloupnost(2), věže(10), kluby(10), cesty(10/2), porovnání(10), Hamilton(7)
Y70interval(10), jehly(10), podposloupnost(10), věže(10), kluby(10), cesty(10), střepy(10)
a71interval(10), jehly(6), podposloupnost(10), věže(10), kluby(10), cesty(10), porovnání(10), mult(5)
b70interval(8), jehly(10), podposloupnost(7), věže(10), kluby(10), cesty(10), střepy(10/2), porovnání(10)
c70interval(10), jehly(6), podposloupnost(10), kluby(10), cesty(10), věže(10/2), porovnání(10), mult(9)
d71interval(6), jehly(10), podposloupnost(5), věže(10), kluby(10), cesty(10), střepy(10), porovnání(10)
e79interval(10), jehly(10), podposloupnost(9), věže(10), kluby(10), cesty(10), střepy(10), porovnávání(10)
f72interval(6), jehly(6), podposloupnost(6), věže(10), kluby(10), cesty(10), střepy(10), porovnávání(10), mult(4)
g70interval(10), jehly(10), podposloupnost(10), věže(10), kluby(10), cesty(10), střepy(10)
h71interval(10), jehly(6), podposloupnost(6), věže(10), kluby(10), cesty(10), střepy(9), porovnávání(10)
i64interval(4), jehly(6), podposloupnost(9), věže(10), kluby(10), cesty(10), porovnání(8), mult(7)
j73interval(10), jehly(6), podposloupnost(3), věže(10), kluby(10), cesty(10), střepy(10), porovnání(10), mult(4)
l70interval(8), jehly(6), podposloupnost(6), věže(10), kluby(10), cesty(10), střepy(10), porovnání(10)
m73interval(6), jehly(6), podposloupnost(7), věže(10/2), kluby(10), cesty(10), střepy(10), porovnání(10), mult(9)
n65interval(10), jehly(6), podposloupnost(5), věže(10), kluby(10), cesty(10), střepy(10), mult(4)
o72interval(8), jehly(6), podposloupnost(2), věže(4+6/2), kluby(10), cesty(10), střepy(10), porovnání(10), mult(9)
p79.5interval(10), jehly(10), podposloupnost(9+1/2), věže(10), kluby(10), cesty(10), střepy(10), porovnávání(10)
q72interval(8/2), jehly(10), podposloupnost(8), věže(10), kluby(10), cesty(10), střepy(10), porovnání(10)
r61interval(10/2), podposloupnost(10), kluby(10), cesty(10), porovnání(10/2), věže(10/2), jehly(6/2), mult,(8/2), Hamilton(9)
s70.5interval(4+2/2), jehly(6+2/2), podposloupnost(8+1/2), věže(10), kluby(10), cesty(10), střepy(10), porovnání(10)
u65interval(10), jehly(5), podposloupnost(5), věže(10), kluby(10), cesty(10), porovnání(10), mult(5)
v65interval(10), jehly(10), věže(10), kluby(10), cesty(10), porovnání(10), mult(5)
z67interval(10), jehly(6), podposloupnost(9), věže(0/2), kluby(10), cesty(10), střepy(7), porovnání(10), mult(5)
w71interval(10), jehly(6), podposloupnost(10), věže(10), kluby(10), cesty(10), střepy(10), porovnání(5)
x76interval(10), jehly(6), podposloupnost(10), věže(10), kluby(10), cesty(10), střepy(10), porovnání(10)
y80interval(10), jehly(10), podposloupnost(10), věže(10), kluby(10), cesty(10), střepy(10), porovnání(10)
Á61interval(4), jehly(6), podposloupnost(6), věže(10), kluby(10), cesty(10/2), střepy(10), porovnání(10), mult(0)
Č65interval(10), jehly(10), podposloupnost(10), věže(10), kluby(10), cesty(10), střepy(5)
Ě72interval(6), jehly(10), podposloupnost(6), věže(10), kluby(10), cesty(10), střepy(10), porovnání(10)
Í61interval(10), jehly(4), podposloupnost(0+6/2), kluby(10), cesty(0+10/2), střepy(10), porovnání(4), mult(5), Hamilton(10)
Ý72interval(10), podposloupnost(9), věže(10), kluby(10), střepy(10), cesty(10), porovnání(10), jehly(6/2)
Ž65interval(8/2), jehly(6/2), podposloupnost(8), věže(10), kluby(10), cesty(10), střípky(10), porovnání(10)
é62jehly(6), kluby(10), cesty(10), střepy(10), porovnání(10), mult(7), podposloupnost(8/2), Hamilton(5)

Odkazy na obdobné stránky

Cvičení Jirky Švancary, Miloše Chromého, Michala Oplera, Jakuba Pekárka a rozcestník Jana Hrice, zoom Po 12:20, zoom Pá 10:40, zoom Pá 12:20, moje loňská cvičení.


Cvičení 1

Na všech proběhlých cvičeních jsme prodávali datové struktury. Vždy zazněly haldy, vyhledávací stromy, hašovací tabulky. Na prvním a třetím cvičení bylo navíc trie, na druhém zásobník, na třetím seznam. Vždy byly první prezentované vyhledávací stromy neprodejné, a bylo potřeba vylepšit reklamní kampaň. Vždy jsme řešili možnosti optimalizace vyhodnocování SQL dotazů.

Vždy jsme zmínili rozměry složitosti průměrná přes pravděpodobnosti vstupu(php attack problém), randomizovaná (průměr přes chování náhodného generátoru) a pro datové struktury i amortizovaná (umožňující spočítat celkový čas za průběh algoritmu, ač některá zavolání moho mít výrazně větší čas než jiná). Vždy padla zmínka o možnosti deamortizace hašování.

Na prvním a třetím cvičení jsme se zabývali problémem paměťové náročnosti trie a jejich možných řešení, což v jednom případě vedlo k nutnosti pozměnit vyhledávací algoritmus. V úplném závěru prvního cvičení jsme dělali oslí můstek k budoucí přednášce týkající se vyhledávání jehly(jehel) v kupce sena (zmínil jsem existenci předzpracování ... indexaci google), naznačil jsem, že očekáváme-li víc dotazů, hodí se předzpracovat seno (zmínil jsem existenci suffix trees), nicméně zabývat se budeme hledáním jehly v nepředzpracovaném seně. Jo ještě jsme zmínil plovoucí hash algoritmus a jméno spoluautora obou základních algoritmů. Donald Ervin Knuth zazněl již dříve v souvislosti s použitím trie pro tabulky dělby slov v typografickém progremu TeX z 70-80 let minulého století.

Na všech cvičeních jsme zmínili i problémy paměťových hierarchií (trie trpí, na druhém trpěly splay trees). Co se týče statických stromů, zmínil jsem na všech Van Emde Boas layout, který se co se týče výpadků keší chová skvěle. Na druhém cvičení inspirován povídáním o „intervalových aktualizacích nad množinou reprezentovanou stromem s příznaky detekujícími neprázdnost podstromu“ jsem zmínil i existenci Van Emde Boas stromů (kde složitost základních uspořádaně množinových operací vychází $O(\log B)$, jsou-li prvky množiny $B$ bitová čísla.)

Na všech cvičeních jsme u hald zmínili i optimální Decreasekey interface, s tím že amortizovaně jej poskytují Fibonacci haldy od Fredmana s Tarjanem, ale dá se docílit i worst case. Na úplném závěru druhého cvičení jsem byl vyprovokován naznačit, jak jsou Fibonacciho haldy organizovány. Stihnul jsem je naznačit bez operace Decreasekey (tedy líné binomiální haldy s mimořádnými hranami). Snad bude příležitost někdy popis dokončit.

Třetí cvičení bylo nahráváno. Aby nahrávky nebyly zcela veřejné, dostali všichni studenti mých cvičení odkaz na google doc, v němž jsou odkazy na zveřejňovaná videa.


Cvičení 2

Věnovali jsme se vyhladávání jehly v kupě sena, případě ve více kupkách či více jehel. Nejprve jsme se chvíli zamýšleli nad tím, jak funguje internetový vyhledávač. Pak jsme si řekli, že pro opakované vyhledávání v seně se vyplatí seno předzpracovat a zmínil jsem sufix tree jako strukturu, která by se k něčemu takovému mohla hodit.

Pak jsme se věnovali Rabin Karp (rolling hash) algoritmu a vymysleli jsme použitelnou hash funkci.

Následně jsme se po zmínce o Knuth Morris Pratt algoritmu (pro jednu jehlu) věnovali jeho zobecnění Aho Corasic (pro více jehel). Popsali jsme si, jak (nekomprimované) trie dané množiny slov doplnit zpětnými odkazy, abychom mohli snadno evidovat nejdelší suffix projděné části sena, který je prefixem nějakého slova množiny. Pak jsme označili místa, kde máme hlásit výskyt nějakého slova množiny (nejen listy, ale i prefixy, které jsou současně v množině). Zpětné hrany nám umožnily snadno rozpoznat další místa, kde máme hlásit infixy, které jsou v reprezentované množině. Rozumná reprezentace je odkazovat ve vrcholu $V$ na vrchol reprezentující prefix nejdelšího vlastního sufixu prefixu reprezentovaného ve $V$. Tak nám přirozeně vzniká spojový seznam všech jehel které jsou sufixem prefixu reprezentovaného ve $V$. Trochu to souvisí s persistentní (dokonce funkcionální) implementací postupně se prodlužujících množin. Pak jsme si zkusili odtrasovat vyhledávání pomocí vzniklého automatu a uvědomili jsme si že čas bude $\Theta(s)$, kde $s$ je velikost sena. Jen na třetím cvičení jsme řešili čas vybudování Automatu a uvědomili jsme si, že ač worst case čas nalezení zpětné hrany z vrcholu trie odpovídá délce prefixu reprezentovaného vrcholem, tak součet časů pro vrcholy na jedné cestě v trie též odpovídá délce cesty. Nakonce bude celkový čas přípravy $\Theta()$ odpovídat celkovému součtu délek jehel.

V závěru hodiny jsme se věnovali možnostem urychlení vyhledávání. První variantou bylo místo zpětné hrany reprezentující jakýkoli znak, pro nějž nemáme pokračování v trie používat pro každé písmeno abecedy jemu odpovídající zpětnou/dopřednou hranu. Urychlení nemělo asymptotický vliv na celkový čas, protože nezlepšilo majoritní část času odpovídající tomu, že přečteme každý znak sena. Na druhou stranu urychlení typicky znamená výrazný nárůst prostorové náročnosti.

Druhou ideou urychlení bylo místo porovnávání jehly od jejího začátku, porovnávat od jejího konce. To by většinou umožnilo posouvat pozici porovnávání, aniž bychom četli všechna písmena sena. Určitě by bylo paměťově náročné (paměťové náročnosti by odpovídala i časová náročnost vybudování takového automatu) mít stavy odpovídající veškeré přečtené informaci pro úsek od první potenciální polohy, kde by nějaká nenalezená jehla mohla být. Rozumné je mít stavy jen pro sufixy odpovídající známým písmenkům sena na konci porovnávacího okénka. Takovýto algoritmus by mohl vyloučit výskyt $\Theta(\sqrt{s})$ dlouhé jehly i na základě pouze $\Theta(\sqrt{s})$ přečtených písmen sena. S ohledem na paměťovou hierarchii je ale nepravděpodobné, že by některý úsek sena nebyl z disku načten do paměti, načítání bloků paměti přitom bude na reálných počítačích časově nejnáročnější část výpočtu. Algoritmus má šanci přinést zlepšení jen v případě, pokud bude velikost jehel větší než velikost bloku vyrovnávací paměti.


Cvičení 3

Vzhledem k tomu, že vyhledávání jehel v seně již máme probrané, věnovali jsme se jinému programu než přednáška. Věnovali jsme se shazování vajíček z mrakodrapu. Nejdůležitější bylo dobře si rozmyslet funkci, kterou chceme počítat. Rekurence pak vyšla zcela přirozeně a silně připomínala Paskalův trojúhelník. Šikovnou hrou s inicializací rekurence se nám podařilo vyjádřit výsledek pomocí součtu správných hodnot tohoto trojúhelníku.

Následně jsme odhadovali maximální hloubku AVL stromu a RB stromu. U AVL se opět se ukázalo, že je rozumné rozmyslet si, jakou funkci chceme počítat. Následně jsme si hráli s lineárními diferenčními rovnicemi, jejich prostorem řešení a souvislostí s Jordánovým tvarem matice a efektivitou výpočtu vzdáleného člena posloupnosti. Co se týče RB stromu, tam jsme obdobnou funkci počítali bez použití rekurentního vztahu. V závěru hodiny jsme srovnávali efektivitu AVL a RB stromů. (V statické verzi vítězí AVL menší multiplikativní konstantou. RB stromy asymptoticky vítězí (kvůli Delete) až v případě persistentní varianty za předpokladu, že barvy jsou pamatovány implicitně. Zajímavé je, že existuje varianta weak AVL, kde je také možná implicitní evidence vyvažovací informace a stačí konstantní počet rotací pro vyvažování, takže dostaneme zcela kompatibilní složitost jako RB i v případě persistentní struktury. Nevýhodou weak AVL je, že se maximální možná hloubka zvětší na stejnou hodnotu, jakou mají RB stromy.)


Cvičení 4

Věnovali jsme se tokům v sítích. Na prvním cvičení jsem se nezeptal na to, co udělat v případě více zdrojů a více stoků. Popsali jsme oba algoritmy hledání toků v síti. (Jak ten, který se po tocích dostává k maximálnímu toku, tak ten, co se od maximálního netoku dostává k maximálnímu toku.)

V prvním případě jsme se postupně od Ford Fulkersona přes Edmons Karp (jméno nezaznělo), přes Dinicův algoritmus k bezejmenné implementaci hledání blokujícího toku ve vrstevnaté síti potřebné pro efektivní implementaci Dinicova algoritmu. U Ford Fulkersona jsme konstatovali, že vůbec nemusí skončit, přičemž konverguje k velmi špatnému řešení, ale důkaz necháme na příště. Dokázali jsme, že končí pro celočíslné (a tímpádem i racionální) kapacity, ale nezabývali jsme se extrémně pomalou konvergencí. Nadhodili jsme nadějnou heuristiku snažící se volit cestu s velkou kapacitou, ale rozhodli jsme se pro variantu heuristiky na kapacitách zcela nezávislé. Ukázali jsme složitost $O(m^2n)$ Edmons Karp varianty a (na druhém cvičení) i složitost $O(mn^2)$ téměř triviální varianty implementace Dinicova algoritmu (kde nepostupujeme po tokových cestách, ale po blokujících tocích vrstevnaté sítě). Pro efektivní implementaci Dinicova algoritmu jsem naznačil rozhraní k potřebné datové struktuře a ukázal složitost $O(mn\log n)$ za předpokladu, že rozhraní datové struktury má $O(\log n)$ implementaci. U nejsložitější operace jsem naznačil jak by ji mohla datová struktura podporovat, ale detaily jsem nechal na jiné přednášky (vhodné implementace jsou Sleator-Tarjanovy dekompozice, Fredericksonova clusterizace či Top Trees (pokud už jsou implementované)).

V druhém případě (Goldberg-Tarjan) jsme popsali trik s výškami, ale nestihli jsme analýzu konečnosti algoritmu (případně s odhadem času). Dokázali jsme jen to, že počet provedení operace Up je $O(n^2)$. Na druhém cvičení jsme ještě stihli rozlišit Push po hranách na saturující a nesaturující, s tím, že počet saturujících jsme též schopni odhadnou pomocí $O(mn)$. Na třetím jsme dokonce stihli odhadnout počet nesaturujících Push (pomocí nalezení šikovného „potenciálu“, který při každém takovém push klesá a je 0 jak na začátku, tak na konci algoritmu, navíc jej Up i saturující Push zvyšují „rouzmně“), takže na třetím cvičení máme konečnost dokázánu (i s časovým odhadem). Odhad počtu nesaturujících push zbyl na ostatních cvičeních na příště. Heuristiky, jak odhad počtu nesaturujích push snížit (a vylepšený časový odhad) zbyl na příště všude, stejně tak jako probírání příkladů, kde by se toky v sítích mohly hodit. Komentář k videu: používal jsem pojem nesaturovaná cesta (či hrana) a znamenalo to hrana s nenulovou kapacitou v reziduálním grafu.


Cvičení 5

Cvičení po zoom nepokračovala tak plynule, jak jsem očekával, účast byla výrazně nižší než na běžném cvičení. Dokončili jsme rozbor Goldberg Tarjanova algoritmu s tím, že jsme přidali rozbor pro případ heuristiky práce s nejvyšším vrcholem s přebytkem. K nalezení potenciálu pro dlouhé fáze nepomáhaly ani intenzivní nápovědy.

Následně jsem předvedl příklad grafu s jednou iracionální kapacitou vedoucí k nekonvergenci Ford Fulkersonova algoritmu (volíme-li zlepšující cesty tak, abychom nekonvergenci podpořili).

Pak jsme ještě řešili příklad se svišti a orly. Na druhém cvičení jsme po vyřešení orlů ještě řešili dominové kostičky na šachovnici s nepoužitelnými některými políčky. Na třetím cvičení jsme řešili ještě izolaci radioaktivních krychliček.


Cvičení 6

Řešili jsme příklady na toky v sítích. Otevírání dolů pro továrny (nedoděláno na prvním cvičení), izolování radioaktivních krychliček, paralelní pohyb dopředných králů po šachovnici s překážkama (na prvním cvičení jsme skončili s nekorektním řešením), dominové kostky na šachovnici s překážkama. Co se týče maximálního párování, doplnil jsem klíčové slovo poupátko/kvítek (blossom) pro vyhledávání algoritmu na obecných grafech.

Na třetím cvičení jsem zapoměl kvítek zmínit, zato jsme rozebrali algoritmus tří Indů a hledání blokujícího toku ve vrstevnaté síti v čase $O(n^2+m)$. (Najde se vrchol s nejmenší průtočností a pro něj tok, jenž jej v reziduálním grafu zneprůchodní. Trik je v tom, že při tom provedem nejvýš $n$ „nesaturujících push“, takže zneprůchodnění všech vrcholů provede $O(n^2)$ „nesaturujících push“. „Saturujících push“ provedeme dohromady $O(m)$.) Ke konci třetího cvičení jsem trochu hovořil o haldách.


Cvičení 7

Věnovali jsme se Fourierově transformaci. Začali jsme představou namotávání funkce různou rychlostí „na šroub“ těžištěm její projekce, detekcí period, souvislostí s osciloskopem.

Následně jsme se věnovali násobení polynomů. Trik s dosazením dostatečného počtu hodnot a následnou interpolací vypadal velice neefektivně, přesto jsme si dosazování popsali ve formě násobení maticí (Vandermondova).

Pak jsme našli tak šikovné hodnoty k dosazování (mocniny $\omega$, kde $\omega$ je primitivní odmocnina z jedné, řádu aspoň tak velkého, kolik potřebujeme dosazení), že matice byla „extrémně symetrická“ ($V_{\omega^j,2^k}$) takže násobení touto maticí bylo možno převést na násobení „stejně definovanou“ maticí čtvrtinové plochy ($V_{\omega^{2j},2^{k-1}}$) s tím, že plocha toho, co má být vynásobeno zůstává zachována (Cooley-Tukey, ale znal již Gauss, symetrie je možno využít i v případě jiných malých dělitelů rozměru matice). Kromě toho jsme museli udělat jen tolik práce, kolik je plocha toho, co mý být vynásobeno (mezivýsledky lichých sloupců je potřeba pronásobit diagonální maticí s $\omega^i$ na diagonále (na prvních dvou cvičeních jsem chybně povídal o násoberní řádkovým vektorem, to by nám ale spojilo všechny řádky do jejich součtu)). Po logaritmickém počtu zmenšování matice, dostáváme násobení jedničkou, tedy „dno“ od kterého se můžeme odrazit. Celkově pro polynom stupně $n$(plocha toho co máme vynásobit) nás to stálo $\Theta(n\log n)$ sčítání a násobení.

Abychom dokončili násobení polynomů, tak se po pronásobení dosazených hodnot musíme „interpolací“ dostat zpět do světa polynomů. Naštěstí zde je lepší trik. Když transformace ze světa polynomů do světa dosazení je násobení regulární čtvercovou maticí, bude transformace zpět násobení inverzní maticí. (Kontrolou polynomu by bylo dosazení, a protože složená transformace je identita ...)

No a ověřili jsme, že inverzní matice vypadá velice podobně jako matice původní. Jen by měla mít hodnoty vydělené rozměrem matice. Pro inverzní tranformaci je příjemnější použít matici ve stejném tvaru ($V_{\omega^{-j},2^k}$) a nakonec výsledek vydělit rozměrem matice.

Celý postup (až na urychlení násobení příslušnou maticí) jsme vyzkoušeli na vynásobení polynomu stupně 2 polynomem stupně 1 (s malými celočíselnými koeficienty). Stačily nám tedy 4 funkční hodnoty a vyzkoušeli jsme celý postup jak v komplexních číslech, tak modulo 17. V prvním případě bylo $\omega=i$, v druhém $\omega=4$. Pro polynomy nepatrně větších stupňů bychom museli pracovat v komplexních číslech s $\sqrt{2}/2$, zatímco takto nám stačili celočíselné koeficienty. Aritmetika mod 17 by fungovala s $\omega=2$, ale museli bychom si být jisti, že největší koeficienty v polynomu budou modulo 17 rozlišitelné. Jinak bychom museli najít jiné vhodné prvočíslo aby v odpovídajícím tělese byla příslušná primitivní odmocnina z jedničky (rozměr matice je dělitelem $p-1$, takže 65537 se hodí).


Cvičení 8

Násobili jsme dva polynomy stupně 3 s malými celými koeficienty pomocí Cooley-Tukey algoritmu (modulo 17 s $\omega=2$). Na druhém a třetím cvičení jsem měl čas hovořit o použití Fourierovy transformace v praxi. Při odbočce k waveletovému formátu jpeg2000 jsem se trošku na druhém cvičení ztratil, každopádně doufám, že jsem zájemce motivoval k tomu, aby se podívali jak daný formát funguje.


Cvičení 9

Věnovali jsme se hradlovým obvodům. Trošku jsme si povídali o univerzálních hradlech nor, nand, udělali jsme si „selektor“, tedy obvod na adresaci bitu, který se hodí pro komparátory. Povídali jsme si o sčítačce a triku se skládáním funkcí, který jsme aplikovali na testování, zda daný konečný automat přijme slovo na vstupu (dané délky). Pro konečný automat s $N$ stavy bylo možno jednotlivé mezivýsledky reprezentovat pomocí $N^2$ hodnot určujících zda z $i$-tého stavu je možno přejít do $j$-tého. Taková reprezentace umožňuje skládat sousední mezivýsledky. (Pokud udržujeme mezivýsledky v matici, odpovídá sloučením dvou matic jejich součin, kde násobení odpovídá $\wedge$ a sčítání $\vee$. První vrstva obvodu je selektor vybírající matici odpovídající písmenu na vstupu. Vyhodnocením je pak $\vee$ na řádku odpovídajícím vstupnímu stavu sloupců odpovídajících výstupnímu stavu ve výsledné matici.) Nakonec jsme se věnovali bitonickému slévání (a třídění), na druhém i třetím cvičení jsme stihli i mergesort.


Cvičení 10

Doufal jsem, že na přednáškách bude NP-úplnost a byly geometrické algoritmy. Připoměli jsme si lokalizaci průsečíků úseček (z přednášky) pomocí zametání roviny (s rostoucím $x$) s haldou událostí, kde události aktualizují vyhledávací/intervalový strom pořadí úseček (dle $y$). V událostech jsou začátky úseček, konce úseček a okamžiky změny pořadí $y$ souřadnic (sousedících) úseček. Netriviální aplikací zametacího algoritmu je struktura na lokalizaci stěny geometrické triangulace, do které padne zadaný bod. Přirozeně jsme se tak doslati k potřebě částečně persistentní struktury pro vyhledávací/intervalový strom.

Povídal jsem proto o druzích persistence, o komplikacích plné persistence a relativně jednoduchému schématu pro částečnou persistenci na datových strukturách orientovaných grafech s konstantou $I$ omezeným in-degree (v našem případě konstantou $1$). Široké vrcholy zajištěné stromem historií změn vrcholu znamenají logaritmické zpomalení dotazů, ale vrcholy s rezervou více pointerů než je maximální možný in-degree umožňují konstantní zpomalení dotazů a vůči potenciálu součtu zaplnění aktuálních verzí vrcholů znamená každá konstantní požadovaná změna pouze amortizovaně konstantní aktualizaci. (Na požadovanou změnu pánujeme $1+1/(2I)$ času v jednotkách potenciálu, kde čas na uložení odkazu při kterém nedojde k přetečení je nejvýš $1/(2I)$ a přetečení vrcholu vyvolá akci, která sníží potenciál aspoň o $I+1$ a vytvoří nejvýš $I$ nových požadavků, takže čas na danou akci můžeme zaplatit z úbytku potenciálu o $1/2$ a zbyde nám aspoň $1+1/(2I)$ na každou nově naplánovanou změnu.)

Připomněli jsme si diskuzi z první přednášky týkající se existence reprezentace červenočerných stromů, umožňující jen konstantně velké aktualizace, takže výsledná částečně persistentní struktura bude mít $n$ historíí a celkovou velikost $\Theta(n)$. Celé zametání bude stále v $\Theta(n\log n)$ čase.

Pak jsme se vrhli na problém nejmenšího kruhu obsahujícího danou množinu bodů. Popsal jsem randomizovaný lineární Welzlův algoritmus, upozornil jsem na problém pokud umožňujeme pokles poloměru aktuálního kruhu a naznačil jsem jenoduchou modifikaci řešící problém (Matoušek, Sharir, Welzl).

Následně jsem naznačil existenci deterministického lineárního algoritmu (Megiddo), který je stejně jako Kirkpatrick-Seidel algoritmus na hledání $h$ bodového konvexního obalu v čase $O(n\log h)$ založen na prune and search technice, kdy v lineárním čase zmenšíme zadání na konstantní část původního (rekurence vede k lineární složitosti). Technika je založená na „mediánovém testu“, kde podle výsledku testu jsme schopni na jedné straně od mediánu část zadání odstranit.

V případě hledání průsečíku polopřímky s konvexním obalem porovnáváme směr mediánové úsečky se směrem protnuté části konvexního obalu. Je-li stejná, snadno najdeme odpověď. Pokud víme kterým směrem od řešení je odkloněna, máme alespoň polovinu úseček odkloněných daným směrem a můžeme z každé jeden krajní bod zahodit (což je čtvrtina původního zadání).

V případě Megiddova algoritmu je testovací úlohou nalezení nejmenšího kruhu se středem na mediánové přímce. Pokud posunutí středu mimo mediánovou přímku nezlepšuje řešení, algoritmus končí. V opačném případě budeme zahazovat z druhé poloroviny. Tato polorovina nám určí druhou „skorokolmou“ mediánovou přímku a na ní test zopakujeme. Tím určíme „skorokvadrant“ v němž hledaný střed leží. Mediánové přímky jsou vybírány vůči průsečíkům párů os dvojic bodů. S tím že směry mediánových přímek a směry os se vždy střídají. To nám garantuje, že pro každý pár os dvojic bodů v kvadrantu proti kvadrantu s řešením máme jednu osu neprotínající kvadrant s řešením. To nám umožňuje pro tuto osu zahodit bod bližší ke kvadrantu s řešením. Zahodíme tak aspoň šestnáctinu zadání.

Úlohu se středem omezeným na danou přímku je možno opět vyřešit pomocí prune and search. Tentokrát porovnáváme polohu mediánového průsečíku os s danou přímkou s polohou řešení. V případě shody máme výsledek, jinak máme polovinu průsečíků známým směrem od řešení. Pro tyto osy můžeme bližší z bodů zahodit. Zmenšíme tak zadání o čtvrtinu.

Je vidět, že multiplikativní konstanty spojené s Megiddo algoritmem jsou mnohem větší než multiplikativní konstanta MSW algoritmu.


Cvičení 11

Nejprve jsme si chvíli povídali o zametání kuželů při tvorbě Voronoiova diagramu resp. Delaunay triangulace, pak jsme řešili dvě geometrické úlohy (nejmenší vzdálenost/největší oddělující pás). Kvůli nejmenší vzdálenosti jsme zabrousili do dolních odhadů pomocí rozhodovacích stromů. Zajímavé bylo, že nejmenší vzdálenost byla triviálním důsledkem netriviální Delaunay triangulace. Co se týče úlohy s minimálním pásem, užitečné by bylo kromě konvexních obalů jednotlivých množin spočítat i konvexní obal jejich sjednocení (stačí uvažovat jen body na konvexních obalech). Porovnání hran konvexního obalu sjednocení s hranami jednotlivých konvexních obalů je dobrý start (které hrany budou zachované a které ne ...)

Nakonec jsme se přece jen dostali k polynomiální transformaci, k NP, k těžkosti, k úplnosti a taky k jednomu zcela neužitečnému NP-úplnému problému.


Cvičení 12

Zabývali jsme se NP-úplností. Ukázali jsme si NP-těžkost úlohy SAT (jak přímo, tak přes KACHL), dělali jsme převody s deklarací proměnných a tvorbou klauzulí (k-NM(VP), 3-COLOR, (na druhé skupině rovinná HK s malými stupni vrcholů)) povídali jsme si o různých variantách kachlíčkování.


Cvičení 13

Věnovali jsme se převodům v NP-úplnosti (vektorový podsoučet, podsoučet čísel (batoh), 2 loupežníci, $k$ loupežníků, "1-in 3 SAT", kachličkování s určenou pozicí kachlíků, ale neurčenou orientací).