Vladan Majerech - NTIN061 Algoritmy a datové struktury II

Last Modified: 29.7.2023

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 .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 úterních cvičeních.

KódBodyTermín odevzdáníZadání
interval1018.10.2022 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.2022 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.2022 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.2022 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.2022 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.
porovnání1022.11.2022 Vytvořte co nejmělčí hradlovou síť, která pro n-bitová čísla $a$, $b$ vydá $1$ právě když $a\le b$.
mult1029.11.2022 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}$).
souvislost106.12.2022 Vytvořte co nejmělčí hradlovou síť, která pro matici sousednosti neorientovaného grafu $G$ vydá true, právě, je-li graf $G$ souvislý.
cesty1013.12.2022 Pro dané vrcholy $u$, $v$ v orientovaném grafu nalezněte maximální počet vrcholově disjunktních cest z $u$ do $v$.
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. Řešte pomocí transformací (tedy nikoli voláním druhého programu polynomiální počet krát).

Id studentacelkemrozpad bodů
V52interval(10), jehly(10), podposloupnost(10), věže(10), kluby(10), hamilton(2)
W31interval(6), jehly(0), podposloupnost(5), věže(10), kluby(10), porovnání(3), souvislost(0)
b49interval(3), jehly(6), věže(2), kluby(10), porovnání(8), mult(7), souvislost(3), cesty(10)
e45interval(10), jehly(10), věže(10), kluby(10), mult(7), cesty(10/2)
h4interval(4)
w11interval(1), jehly(10)
y31interval(4), jehly(5), podposloupnost(2), porovnání(10), sousednost(0), cesty(10)
Č5jehly(5)
Í55jehly(6), podposloupnost(5), věže(2), kluby(10), porovnání(10), mult(10), souvislost(4), cesty(8)
A68interval(10), jehly(9), podposloupnost(9), věže(10), kluby(10), porovnání(10), souvislost(10)
B67interval(10), jehly(10), podposloupnost(7), věže(10), kluby(10)), porovnání(10), cesty(10)
C90interval(10), jehly(10), podposloupnost(10), věže(10), kluby(10), porovnání(10), mult(10), souvislost(10), cesty(10)
D62interval(10), jehly(6), podposloupnost(6), věže(10), kluby(10), porovnání(10), souvislost(?), cesty(10)
E60interval(10), jehly(10), věže(10), kluby(10), porovnání(10), souvislost(10)
F64interval(8), jehly(10), podposloupnost(9), kluby(10), porovnání(10), mult(7), cesty(10)
G67interval(10), jehly(10), podposloupnost(10), věže(10), kluby(10), porovnání(10), mult(7)
H67interval(10), jehly(6), podposloupnost(9), věže(10), kluby(10), porovnání(10), mult(4/2), souvislost(?), cesty(10)
I66interval(9), jehly(10), podposloupnost(7), věže(10), kluby(10), porovnání(10), mult(10)
J66.5interval(10), jehly(9), podposloupnost(9), věže(10), kluby(10), porovnání(9+1/2), souvislost(10)
K68interval(10), jehly(10), podposloupnost(8), věže(10), kluby(10), porovnání(10), souvislost(10)
M64interval(10), jehly(10), podposloupnost(10), věže(10), kluby(10), porovnání(10), souvislost(8/2)
N62interval(10), jehly(6), podposloupnost(6), věže(10), kluby(10), porovnání(10), souvislost(10)
O67interval(10), jehly(6), podposloupnost(6), věže(10/2), kluby(10), porovnání(0), mult(10), souvislost(10), cesty(10)
P68.5interval(2+3/2), jehly(6), podposloupnost(9+1/2), věže(1+9/2), kluby(10), porovnání(10), mult(6), souvislost(8), cesty(10)
Q90interval(10), jehly(10), podposloupnost(10), věže(10), kluby(10), porovnání(10), mult(10), souvislost(10), cesty(10)
R68interval(10), jehly(10), podposloupnost(8), věže(10), kluby(10), porovnání(10), hamilton(10)
S60interval(10), jehly(10), podposloupnost(9), věže(10), kluby(10), porovnání(5), souvislost(6)
T88interval(10), jehly(10), podposloupnost(9), věže(10), kluby(10), porovnání(10), mult(9), souvislost(10), cesty()
U75interval(10), jehly(10), podposloupnost(9), věže(10), kluby(10), porovnání(10), mult(7), souvislost(9)
X62interval(10), jehly(6), podposloupnost(6), věže(0), kluby(10), porovnání(10), mult(8), souvislost(2), cesty(10)
Y61interval(4), jehly(6), podposloupnost(10), věže(10), kluby(10), mult(10), cesty(10), hamilton(1)
Z76interval(10), jehly(6), podposloupnost(10), věže(10), kluby(10), porovnání(10), mult(10), souvislost(10)
a78interval(10), jehly(10), podposloupnost(10), věže(10), kluby(10), porovnání(10), mult(8), souvislost(10)
c64interval(10), jehly(10), podposloupnost(9), věže(10), kluby(10), porovnání(5), mult(10)
d60interval(10), jehly(6), podposloupnost(9), věže(10), kluby(10), porovnání(10), mult(5)
f60.5interval(10), jehly(6), podposloupnost(6), věže(10), kluby(10), porovnávání(10/2), mult(7/2), cesty(10/2), souvislost(4/2), hamilton(3)
g60.5interval(1), věže(10), kluby(10), porovnání(10), cesty(10), jehly(6/2), mult(9/2), hamilton(8), podposloupnost(8/2)
i61interval(1), jehly(10), podposloupnost(6+4/2), věže(10), kluby(10), porovnání(10), mult(10), souvislost(2)
j62interval(6), jehly(6), podposloupnost(7), věže(10), kluby(10), porovnání(10), mult(7), souvislost(6)
k75interval(10), jehly(10), podposloupnost(10), věže(10), kluby(10), porovnání(5), mult(10), cesty(10)
l71.5interval(10), jehly(10), podposloupnost(9), věže(10), kluby(10), porovnání(5/2), mult(10), cesty(10)
m66interval(10), jehly(6), podposloupnost(5), věže(0), kluby(10), porovnání(10), mult(10), souvislost(2+8/2), cesty(9)
n60.5interval(7), jehly(7+3/2), podposloupnost(8), věže(0), kluby(10), porovnání(10), mult(7), souvislost(0), cesty(10)
o60.5interval(1+3/2), jehly(6), podposloupnost(9), věže(10), kluby(10), porovnání(8), mult(10), souvislost(5)
p62interval(10), jehly(10), věže(10), kluby(10), porovnání(10/2), mult(7), souvislost(10)
q61interval(6), jehly(6), podposloupnost(9), věže(10), kluby(10), porovnání(10), mult(10)
r67interval(10), jehly(10), podposloupnost(7), věže(10), kluby(10), porovnání(10), souvislost(10)
s61interval(6), jehly(10), podposloupnost(9), věže(10), kluby(10), mult(10), souvislost(6)
t69interval(10), jehly(10), podposloupnost(9), věže(10), kluby(10), porovnání(10), mult(10)
u68interval(8), jehly(6), podposloupnost(7), věže(10), kluby(), cesty(10), porovnání(10), mult(7), Hamilton(10)
v70interval(10), jehly(10), podposloupnost(10), věže(10), kluby(10), porovnání(10), souvislost(10)
x63.5interval(5+5/2), jehly(6), podposloupnost(10/2), věže(10), kluby(10), porovnání(9), mult(10/2), souvislost(10)
z69interval(8/2), jehly(6), podposloupnost(10), věže(10), kluby(10), porovnání(10), mult(4+2/2), souvislost(4), cesty(10)
Ř67interval(10/2), jehly(10), podposloupnost(10), věže(10), kluby(10), porovnání(10), mult(8/2), souvislost(8)
Ž61interval(6/2), jehly(6/2), podposloupnost(6), věže(10), kluby(10), porovnání(5), mult(10), souvislost(1), cesty(10), hamilton(3)
Š60jehly(6), podposloupnost(5), věže(10), kluby(10), porovnání(10), mult(4), cesty(5), interval(10/2), souvislost(6/2), hamilton(2)
Á65podposloupnost(6), jehly(10/2), interval(10/2), věže(10), kluby(10), porovnání(10/2), mult(10/2), cesty(10), souvislost(4/2), hamilton(7)
Ě63interval(10), podposloupnost(10), věže(10), kluby(10), mult(7), souvislost(6), cesty(10)
É65interval(0/2), jehly(6/2), podposloupnost(6/2), věže(10), kluby(10), porovnání(10), mult(4), souvislost(7), cesty(10), hamilton(8)

Odkazy na obdobné stránky

Cvičení či materiály k nim Petra Kučery, Jana Hrice, Martina Kouteckého, Pavla Veselého a 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 (kromě jiných) prioritní fronty, vyhledávací stromy, slovníky a struktura na spojování tříd ekvivalence. 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 střední hodnota (průměrná přes pravděpodobnosti vstupu) (php attack problém), randomizovaná (průměr pro jeden vstup 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í mohou mít výrazně větší čas než jiná). Padla zmínka o možnosti deamortizace hašování.


Cvičení 2

Věnovali jsme se vyhledávání v textu. Nejprve jsme si chvíli povídali o vyhledávání na internetu, tedy jak velmi zhruba funguje příprava podkladů pro vyhledávání na internetu a jak zhruba může být dotaz vyhodnocován. Pak jsem zmínil možnost obráceného přístupu, tedy předzpracování sena, což umožňuje následné efektivní vyhledávání libovolných předem neznámých jehel (Suffix trees). Předzpracování se dá udělat v čase $O(n)$ a vyžaduje $O(n)$ prostoru (s multiplikativní konstantou řekněme 20).

Nálsedně jsme se věnovali vyhledávání jehly(el) v seně metodou, kdy předzpracujeme jehlu(y). Nejprve jsem zmínil algoritmus s plovoucí hašovací funkcí (Robin Karp), který umí s velikou pravděpodobností vyloučit pozice, kde se jehla určitě nenachází, s tím, že pozici, kde se jehla nachází nikdy nevyloučí. Na první verzi cvičení zazněla hezká xorovací, shiftovací hashovací funkce, jejíž výpočet i aktualizace bude mít lepší multiplikativní konstantu než standardní modulo polynomiální funkce. Obě tyto funkce jsem pak uváděl i na zbylých cvičeních.

Následně jsme Knut-Moris-Prat algoritmus odbyli tím, že předvedeme Aho-Corrasick algoritmus, jež je jeho zobecněním a zjednodušení datové struktury pro cestu místo stromu, kde stačí pole čísel je implementační detail. Věnovali jsme se tedy Aho-Corrasic algoritmu, a předvedli jsme si jej na příkladě. Nejprve jsme odbočili k datové struktuře (písmenkový strom) Trie a zařadili ji v kontextu tržnice datových struktur (paměťová hierarchie!). Řekli jsme si o možnosti reprezentace hran trie ve slovníku, ale i o tradičních metodách pole odkazů. Bavili jsme se o snížování prostorové náročnosti při reprezentaci statické množiny pomocí eliminace vrcholů stupně 1 i pomocí reprezentace ofsetů do jednoho pole s překrývajícími se intervaly hodnot (s nepřekrývajícími se nenilovými odkazy), rozmysleli jsme si, jak musíme modifikovat vyhledávání, abychom se nezacyklili a lokalizovali jen slova z množiny.

U AC algoritmu jsme se nevěnovali důkazům, toho, že postupujeme správně, nicméně jsme všechny jednotlivé kroky zdůvodnili. Implicitně jsme dokázali složitost vyhledávání i složitost vybudování fail podpůrných pointerů. Co se týče hlášení nalezených jehel, využil jsem příležitost k odbočce k funkcionálně persistentní datové struktuře srůstajících seznamů. Zmínil jsem se o tom, co to je částečná a plná persistence, a zmínil využití částečné persistence v úloze lokalizace bodů v rovině. Zmínil jsme prostorovou výhodu RB stromů před AVL v případě částečně persistentní verze struktury i to, že v případě plné persistence je potřeba reprezentaci barev zkomplikovat (implicitní evidencí pomocí rozkladů na cesty jednoduchých barevných vzorů).


Cvičení 3

Věnovali jsme se tokům v sítích. Popsali jsme dva 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, 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 jsem (nejlépe na třetím cvičení) ukázal, že vůbec nemusí skončit, přičemž konverguje k velmi špatnému řešení. 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 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é)).

K implementačním detailům druhého algoritmu jsme se nedostali. Na druhém cvičení jsme si ještě hráli s radioaktivitou.


Cvičení 4

Na čtvrtém cvičení jsme se zabývali tím druhým algoritmem, tedy tím, kde nejprve nasytíme všechny hrany ze zdroje, načež se snažíme zajistit, abychom dostali tok. Chtěli bychom přetlak posílat po hranách směrem do stoku $t$, dokud to jde a až už není šance, začít je posílat zpět do zdroje $s$. Abychom věděli, co znamená směrem do stoku, je vhodné si pomocí zpětného BFS spočítat vzdálenosti do stoku. S takto předpočítanými hodnotami se snažíme posílat přetlak do vrcholů s menší vzdáleností. Pokud z vrcholu není stok dosažitelný, rádi bychom přeposílali přetlak směrem ke zdroji. Vhodné je udržovat i vzdálenosti do zdroje v reziduálním grafu. V případě nekonečné vzdálenosti do stoku (neexistence cesty) budeme přeposílat do vrcholu s nižší vzdáleností do zdroje. Pokud zvolíme vhodnou konstantu $N$, takovou aby vzdálenost do stoku nemohla být větší než $N$, můžeme k navigaci používat jedinou proměnnou, kde bude v případě konečné vzdálenosti do stoku tato vzdálenost a v opačném případě použijeme $N$ plus vzdálenost do zdroje. Nechť $N'$ je vhodná konstanta taková, že vzdálenost do zdroje nemůže být větší než $N'$ (přirozeně ze symetrie můžeme volit $N'=N$). Pro vrcholy, z nichž není dosažitelný ani zdroj, ani stok můžeme použít jako navigační hodnotu konstantu $N+N'$.

Ze stoku ani zdroje po inicializaci žádný přetlak neposíláme. Chtěli bychom konsistentně používat pravidlo, že smíme posílat přetlak pouze do vrcholu s o jedna menší navigační hodnotou, proto navigační hodnotu pro zdroj změníme na $N$ nezávisle na jeho vzdálenosti do stoku. V každém kroku vybereme jeden vrchol s přetlakem a zkontrolujeme, zda z něj vede hrana do vrcholu s o jedna nižší navigační hodnotou. Pokud tomu tak není, nemáme aktualizovanou evidenci příslušných vzdáleností a musíme provést aktualizaci na o 1 víc než nejmenší navigační hodnota mezi sousedy, kam vede hrana (Ve skutečnosti i to je jen dolním odhadem, neb mohla zmizet hrana dále na cestě. Přepočítávat vzdálenosti přesně při odstranění každé hrany by bylo neefektivní.). Následně vybereme jednu hranu navigující o jedna směrem k cíli, zvolíme množství odpovídající minimu z přetlaku a kapacity hrany a toto množství protlačíme hranou. Protlačení hranou znamená, že přetlak startovacího vrcholu snížíme o danou hodnotu a přetlak cílového o stejnou hodnotu zvýšíme. Zároveň snížíme kapacitu hrany a zvýšíme kapacitu hrany opačné o příslušnou hodnotu. Hrany s nulovou kapacitou odstraňujeme (zneviditelňujeme). Největší možná délka cesty z $v$ to $t$, nepoužívající $s$ může obsahovat jen $n-2$ hran, přehozením $s$ a $t$ dostáváme stejný odhad. Proto můžeme použít $N'=N=n-2$.

Je dobré si uvědomit, že pro vrchol s přetlakem (kromě $s$ a $t$) je vzdálenost do zdroje nejvýš $n-2$ (v reziduálním grafu je cesta (s nenulovou kapacitou) vedoucí do zdroje, neb někudy přetlak doputovat musel), má tedy souseda s navigační konstantou o jedna nižší. Takže vždy je možno najít hranu, po které je možno tlačit.

Algoritmus Goldberg-Tarjan používá tuto strategii, až na to, že navigační vzdálenosti nepředpočítává, ale používá jejich dolní odhady inicializované nulou. Když v průběhu algoritmu zjistí, že je dolní odhad příliš nízký, tak jej zvýší (buď o 1 nebo na lepší dolní odhad ... dle dolních odhadů sousedů). I při takovýchto dolních odhadech dostaneme stejné asymptotické odhady chování algoritmu (pokud bychom začínali s grafem, kde jsou navíc hrany do zdroje a stoku s nulovou kapacitou, dostali bychom odhady vzdáleností $1$, takže bychom si předvýpočtem moc nepomohli).

Při rozboru složitosti (a tedy i konečnosti) algoritmu odhadneme počet aktualizací navigačních konstant, počet tlačení hranou, kdy byla hrana saturována (použita celá kapacita) a počet tlačení hranou, kdy byl vynulován přetlak startovacího vrcholu (tlačení můžeme započítat dvakrát, pokud se kapacita hrany shodovala s přetlakem).

Hrubý odhad je, že počet přepočítávání navigačních hodnot nemůže překročit součet navigačních hodnot, což nepřekročí $n(N+N')\in O(n^2)$. Každou hranou pro danou hodnotu navigační konstanty (výšku) tlačíme saturovaně nejvýš jednou, celkem tedy nejvýš $m(N+N')\in O(mn)$. Zbývá odhadnout počet tlačení, kdy byl vynulován přetlak zdrojového vrcholu hrany. Pokud zavedeme pro vrcholy nějakou statistiku $s(v)$ a sečteme statistiky přes vrcholy s přetlakem, pak takové tlačení hranou $(u,v)$ snižuje součet o $s(u)$ a možná zvyšuje o $s(v)$. Pokud za $s$ zvolíme navigační hodnotu, tak každé takovéto tlačení snižuje součet o $1$. Přepočítávání navigačních konstant dostává nezáporný počáteční součet na nejvýš $n(N+N')\in O(n^2)$ postupným zvyšováním o $1$. Každé saturující tlačení může zvýšit součet o výšku cílového vrcholu, tedy nejvýš o $N+N'-1\in O(n)$. Dohromady tedy tento součet (potenciál vzroste o $O(mn^2$), tady celkově může klesnout nejvýš o $O(mn^2$) a to omezuje počet tlačení vyprazdňujících přetlak i celkovou složitost algoritmu.

Na cvičení jsme se dále zabývali strategií maximalizující počet tlačení vyprazdňujících přetlak. To vedlo k heuristice dávající naději takovýchto tlačení provádět méně. Když jsme pak na základě strategie rozdělili algoritmus do $O(n^2)$ fází a pro vhodné $K$ fáze rozdělili na ty s počtem tlačení vyprazdňujících přetlak nejvýš resp. aspoň $K$, dostali jsme odhad počtu takovýchto tlačení $O(n^2(K+m/K))$, takže celková složitost algoritmu při správné volbě $K$ vyšla $O(n^2\sqrt{m})$. (Bylo potřeba vymyslet potenciál (resp. $s(v)$), který celekm vyroste nejvýš o $O(mn^2)$, ale tlačení vyprazdňující vrchol jej snižuje aspoň o $K$).

Na druhém cvičení jsme si ještě hráli s dominem.


Cvičení 5

Kromě algoritmu tří indů jsme řešili příklady, kde se toky v sítích hodí (svišti a orel, domino z děravé šachovnice, dopravní problém, izolace radioaktivity, dopřední králové, otevírání dolů). Nejspíš jsem se měl zmínit ještě o maximálním párování v obecných grafech.


Cvičení 6

Na šestém cvičení jsme dokončili (pokud bylo potřeba) tématiku toků v sítích a pustili se do hradlových sítí. Rozmysleli jsme si proč existují jen 2 univerzální hradla, rozmysleli jsme si, jak pomocí nich udělat selector resp. (s pomocí domácího úkolu) komparátor a použili jsme trik s mezivýsledky v podobě funkcí umožňující pomocí skládání funkcí přenášet informaci v logaritmické hloubce místo přirozeného řešení vyžadujícího lineární hloubku. Obvod pro násobení bude za domácí úkol. Řadící obvody jsme (na prvním cvičení) nestihli, to bude příště.


Cvičení 7

Na sedmém cvičení jsme se věnovali Fourierově transformaci (především diskrétní).


Cvičení 8

Na osmém cvičení jsme si Fourierovu transformaci pro $2^3$ zkusili upočítat ručně. Mám pocit, že konvoluci dvou polynomů nikdo dobře nedopočítal.


Cvičení 9

Na devátém cvičení jsme se věnovali NP-úplnosti. Začali jsme ukázkou zcela nepraktického, zato triviálně problému z NP. Pokračovali jsme kachlíčkováním a probrali jsme spoustu katalogových variant (na posledním cvičení i seznamovou variantu, a zmínil jsem i NP-úplnost varianty, kdy máme kachlíčky na místě, a máme zjistit, zda je můžeme správně pootáčet). Následně jsme ukázali vyjadřovací užitečnost SAT a to, jak s ním řešit kachlíčkování. V další části jsme ukázali, jak je SAT jednoduchý ve smyslu, že stačí umět kódovat booleovské proměnné, jejich nonekvivalenci (literály) a nezávisle na sobě klauzule. Využili jsme to v důkazu NP-těžkosti testování tripartitnosti grafu i zjišťování existence hamiltonovské kružnice v orientovaném bipartitním grafu s minimálními možnými stupni vrcholů (in1,out2/in2,out1). Na lichých cvičeních jsem využil toho, že neorientovaná varianta hamiltonovské kružnice se stupni vrcholů nejvýš 3 vlastně znamená, že místo podmínky na "cestu" máme podmínku na "tah" (rozhodnutí, kudy se s hadem vydat, aby přežil co nejdéle).


Cvičení 10

Na desátém cvičení jsme se věnovali dalším NP-úplným problémům. (k-VP/k-NM/k-klika), (batoh/podsoučet/loupežníci), (1 in 3 SAT/celočíselné programování), rovinná 3-barevnost, otáčecí kachličkování se seznamem, otáčecí kachličkování s umístěnými kachlíky. Na druhém cvičení jsme vynechali převod na loupežníky, na třetím jsme navíc stihli rovinnou tříbarevnost se stupni vrcholů nejvýš 4.


Cvičení 11

Na jedenáctém cvičení jsme se nejprve věnovali aproximacím optimalizačních úloh jejichž ověřovací verze jsou NP-úplné problémy (x-VP, x-OC, x-Součet podmnožiny). U Součtu podmnožiny se optimalizační úloha spíš podobala batohu, ale s tím, že měrná užitečnost všech předmětů byla jedna. Kapacita byla pevná a maximalizovali jsme užitečnost. Naše úplné polynomiální aproximační schéma dokázalo najít $(1-\varepsilon)\hbox{Součet podmnožiny}*$ řešení (v čase polynomiálním v $n$, $\ln t$ i $1/\varepsilon$). Ve zbytku hodiny jsme si hráli s NP-úplnými problémy. (Omezení stupně vrcholů v rovinné tříbarevnosti, existence jiného rozdělení do partit u tříbarevnosti, jiná HK).


Cvičení 12

Na posledním cvičení jsme se věnovali testování prvočíselnosti a faktorizaci. Od čínské věty o zbytku přes malou Fermatovu větu a Euler-Fermatovu větu (Carmichaelovu větu jsme nepoužili), test Carmichaelovskosti, rozlišení Carmichaelovských čísel od prvočísel pomocí výběru náhodné odmocniny z 1 (Rabin-Miller). Co se týče faktorizace $n$, tak jsme si ukázali útok na $p-1$ hladkost pro $p|n$, následně jsme princip pomocí eliptických křivek zobecnili na útok na hladkost náhodného čísla v intervalu $(p-\sqrt{p},p+\sqrt{p})$ (Lenstra). Útok na $x^2\equiv y^2\pmod n$ vedoucí k faktorizaci dostatečně velkého výběru z čísel z posloupnosti $A_i$ zazněl nakonec. (Ve variantě kvadratického síta, kde v posloupnosti jsou čísla velká řádově $\sqrt n$ a $A_i$ je možno popsat kvadratickým polynomem nad $i$. Trik je v tom, že pokud $p|A_i$, pak $p|A_{i+p})$, takže je možno použít síto na detekci členů posloupnosti, které jsou pravděpodobně hladké. Faktorizace takto vytipovaných členů posloupnosti je efektivní. Zmínil jsem trik s dvojicí polohladkých čísel, nehladkých přes stejné prvočíslo.) Zmínil jsem, že existuje i faktorizace, kde se obdobně pracuje s dvěmi posloupnostmi „čísel“ řádově menších, takže je efektivnější najít dostatečně dlouhou hladkou podposloupnost. Podrobnosti "Number Field sieve" ale neznám.


Cvičení 13

Na extra cvičení, které měla jen jedna skupina jsme si hráli s hádankou "n vězňů a 2 stavový přepínač".