Cvičení z algoritmů a datových struktur, TIN061

Podmínky k získání zápočtu

1. Poslat do Vánoc mail, že budete chtít zápočet. (Objevíte se v seznamu.)
2. Domluvit se se mnou do konce semestru, tj. do 11. 1. 2008 mailem na tématu zápočtové práce. Inspirace například v seznamu Martina Mareše. Pokud jsme nějaké téma dopodrobna rozebrali na cvičení, tak se mi nejspíš nebude líbit.
3. Vytvořit zápočtové práce včetně dokumentace.
4. Poslat mi hotový zápočťák a domluvit se na termínu osobního předvedení.

Seznam přidělených zápočtových prací.

Obsah cvičení (10. 01. 2008)

Datum	Obsah
< 18. říjen 2007	Tato cvičení jsem necvičil já.
18. říjen 2007	Dinicův algoritmus na toky v sítích, jeho složitost v případě jednotkových kapacit a v případě jednotkových kapacit za podmínky, že vstupní či výstupní stupně všech vrcholů jsou jedna. Aplikace jako párování v bipartitních grafech. Řešené příklady: Určete složitost obecného Dinicova algoritmu [O(N2M)]. Určete složitost Dinicova algoritmu na grafech s jednotkovými kapacitami [O(NM)]. Určete složitost Dinicova algoritmu na grafech s jednotkovými kapacitami, pokud je ještě vstupní nebo výstupní stupeň každého vrcholu nejvýš jedna [O(N1/2M)]. Vyřešte problém maximálního párování v bipartitních grafech pomocí Dinicova algoritmu a určete výslednou složitost [O(N1/2M)]. Zjistěte, zda lze daná šachovnice NxN, která má nějaká políčka vykousnutá, pokrýt dominovými kostkami 1x2. [O(N3)]. Zjistěte, kolik nejvíc věží můžete umístit na šachovnici NxN s vykousnutými políčky tak, aby se žádné dvě věže neohrožovaly [O(N3)].
25. říjen 2007	Zamotávání se do úloh o policajtech, goldbergův algoritmus na toky v sítích, jeho složitost, a vylepšení spočívající ve zpracovávání vrcholu největší výšky. Řešené příklady: Město je bipartitní graf [vrcholy jsou křižovatky, hrany silnice]. Zjistěte, kolik nejméně policajtů potřebujete umístit na křižovatky, aby byla každá ulice hlídaná alespoň jedním policistou [O(N1/2M)]. Město je bipartitní graf [vrcholy jsou křižovatky, hrany silnice]. Zjistěte, kolik nejméně policajtů potřebujete umístit na křižovatky, aby byla každá ulice hlídaná právě jedním policistou (aby na sebe v noci náhodou nezaútočili) [O(M)]. Určete složitost obecného Goldbergova algoritmu [O(N2M)]. Určete složitost Goldbergova algoritmu při zvedání nejvyššího vrcholu s přebytkem [O(N2M0.5)].
01. listopad 2007	Rozmotávání úloh o policajtech a třídící sítě – pár příkladů, zero-one theorem. Řešené příklady: Vytvořte třídící síť, která najde minimum a maximum [O(log2N) vrstev, O(N) komparátorů]. Vytvořte třídící síť, která zatřídí N-tý prvek do setříděné posloupnosti prvků 1..N-1 [O(log2N) vrstev, O(N) komparátorů]. Vytvořte třídící síť, která setřídí zadanou permutaci [O(log2N) vrstev, O(N) komparátorů]. Dokažte 0-1 theorem: Pokud třídící síť korektně setřídí každou permutaci 0 a 1, tak už korektně setřídí posloupnost libovolných čísel (pomocí lematu o nerostoucích zobrazeních).
08. listopad 2007	Vyřešení úlohy s projekty a zdroji pomocí minimálního řezu. Hledání jehly v kupce sena – triviální algoritmus, Rabin-Karp, zopakování konstrukce KPM z přednášky. Řešené příklady: Máte N projektů, za vyřešení každého dostanete sumu ci. Dále máte M zdrojů, každý vás stojí rj. Na každý projekt i potřebujete nějakou podmnožinu zdrojů si1,...,sini. Pokud zakoupíte nějaký zdroj, tak ho můžete použít ve všech projektech. Rozhodněte, jaké projekty vybrat a jaké zdroje zakoupit, abyste pro vybrané projekty měli všechny zdroje a abyste maximalizovali zist, tj. sumu zisků vybraných projektů - sumu cen vybraných zdrojů. Úlohy na rozmyšlenou: Najít nejdelší společné podslovo dvou daných řetězců [O((N+M)log(N+M)) v průměru, O(N+M) se sufixovými stromy]. Najít nejčastější podslovo zadané délky K daného řetězce [O(N) v průměru bez sufixových stromů, O(N) v nejhorším případě s nimi]. Najít lexikograficky nejmenší rotaci daného řetězce [O(N) s i bez sufixových stromů]. Najít nejdelší palindromické podslovo daného řetězce [O(N) s i bez sufixových stromů].
15. listopad 2007	Prohrabali jsme se v Aho-Corasick, jak ukládat výsledky u stavů. Řešili jsme počítání výskytů slov ve slovníku a cenzurování v KMP a v Aho-Corasick. Setřídili jsme slova o P písmenech. Z minula jsme vyřešili první domácí úkol c čase O(N log M) pro N >= M; ostatní domácí úkoly ještě čekají na lineární řešení. Řešené příklady: Máme daný slovník K slov a řetězec délky N. Zjistěte pro každé slovo kolikrát se z daném řetězci vyskytovalo [O(N + velikostSlovníku + velikostVýstupu), pozor, není to triviální]. Máte dané jedno zakázané slovo a řetězec délky N. Vyškrtejte z toho řetězce všechny výskyty zakázaného slova [O(N)]. Nyní je zakázaných slov více, řekněme K. Vyškrtejte všechny výskyty všech zakázaných slov (v libovolném pořadí) [O(N * velikostZakázanýchSlov) nebo O(velikostAbecedy*N + velikostZakázanýchSlov), O(N + velikostZakázanýchSlov) neumím]. Dostanete několik slov, součet jejich délek je P, vaším úkolem je setřídit je. [O(P + velikostAbecedy), pozor, ať neuděláte O(P * velikostAbecedy)].
22. listopad 2007	Dodělali jsme všechny nevyřešené úkoly z 8. listopadu v lineárním čase. Pak jsme si řekli o suffixových stromech, naznačili jejich konstrukci v lineárním čase a ukázali, jak všechny čtyři úkoly z 8. listopadu vyřešit v lineárním čase pomocí suffixových stromů. Nakonec jsme načali DFT.
29. listopad 2007	Pořádně jsme se pohrabali v DFT, víme, na co se zobrazí vektory (ωjk)j=0..n-1, (cos(2πjk/n))j=0..n-1, (sin(2πjk/n))j=0..n-1. Obraz reálného vektoru je antisymetrický, antisymetrického reálný a víme, jak "předělat" DFT na DCT, která dělá z reálného vektoru reálný. Využití DFT v kompresi obrázků a rychlého násobení čísel. Nakonec jsme ukázali, že pomocí konvexního obalu umíme třídit reálná čísla. Řešené příklady: DFT obraz vektorů (ωjk)j=0..n-1 pro libovolné k [(δj,n-k)j=0..n-1]. DFT obraz vektorů (cos(2πjk/n))j=0..n-1 pro k < n/2 [(δj,k/2+δj,n-k/2)j=0..n-1]. DFT obraz vektorů (sin(2πjk/n))j=0..n-1 pro k < n/2 [(iδj,k/2-iδj,n-k/2)j=0..n-1]. DFT obraz reálného vektoru je antisymetrický (yk = konjugace yn-k). DFT obraz antisymetrického vektoru je reálný. "Upravte" DFT pomocí dvou předchozích případů, aby fungovala z Rn do Rn. Vynásobte dvě zadaná N-bitová čísla v lineárním čase, pokud víte, že čísla o log2N bitech umíte násobit v O(1). Ukažte, že složitost nalezení konvexního obalu je alespoň složitost setřídění reálných čísel.
6. prosinec 2007	Nejdřív jsme se zaobírali geometrickými algoritmy, opakovali konvexní obal a řešili jeho obsah. Dále jsme počítali obsah poházeného stolu. Pak jsme si osvěžili Voroneho diagramy, zjistili, že mají nejvýš 2N-5 vrcholů a 3N-6 hran, rozmysleli si, jaké vlastnosti má jeho duál a dokázali, že minimální kostra grafu zadaného pomocí bodů v rovině je vždy podmnožina tohoto duálu. Řešené příklady: Nalezněte konvexní obal v čase O(NK), kde N je počet daných bodů a K počet bodů na obalu. Spočtěte obsah daného (i nekonvexního) mnohoúhelníka [O(N)]. Stůl jste poházeli N papíry, jsou obdélníkové a rovnoběžné s osami. Spočtěte obsah pokryté části stolu [O(N log N)]. Ukažte, že Voroneho diagramy mají nejvýš 2N-5 vrcholů a 3N-6 hran. Ukažte, že duál Voroneho diagramu je triangulace, pokud jsou zadané body v obecné poloze (žádné tři neleží na jedné přímce, žádné čtyři na jedné kružnici). Ukažte, že v duálu Voroneho diagramu jsou dva body spojeny hranou právě tehdy, když existuje kruh, která má tyto body na hranici a uvnitř tohoto kruhu žádné jiné body nejsou. Ukažte, že minimální kostra grafu zadaného pomocí bodů v rovině (je úplný, váha hrany je vzdálenost jejích vrcholů v rovině) je podmnožina duálu Voroneho diagramů a vytvořte algoritmus pro nalezení minimální kostry takového grafu [O(N log N)].
13. prosinec 2007	Dnešek byl ve znamení P, NP a převodů. Zopakovali jsme definice P a NP (polynomiální algoritmy s polynomiálně dlouhou nápovědou) a redukce. Celou dobu jsme zkoumali následující tabulku: NP úplné P SAT, 3-SAT, 3,3-SAT 2-SAT, HORN-SAT, (E3,E3)-SAT 3D párování bipartitní párování Nezávislá množina, klika Nezávislá množina v bipartitním grafu Vrcholové pokrytí Vrcholové pokrytí v bipartitním grafu Hamiltonovská kružnice Eulerovský tah Problém obchodního cestujícího Minimální kostra Nejdelší cesta Nejkratší cesta ZOE Soustava lineárních rovic SSUM SSUM v unární soustavě Batoh Batoh v unární soustavě Celočíselné lineární programování Lineární programování kde o problémech vlevo potřebujeme nějakou redukcí dokázat, že jsou NP-úplné, a na problémy vpravo chceme najít polynomiální algoritmus. Iitalikou psané položky jste dělali na přednášce a tučné jsme udělali na cvičení. Zadání jednotlivých problému, které neznáte z přednášky: 2-SAT: SAT, ale každá klauzule má nejvýš dva literály>. HORN-SAT: SAT, ale v každé klauzuli je nejvýš jeden gativní literál. (E3,E3)-SAT: SAT, ale každá klazule obsahuje právě tři literály a každá proměnná je právě ve třech klauzulích. Navíc žádná proměnná není v jedné klauzuli více než jednou. Vrcholové pokrytí: Minimální podmožina vrcholů taková, že každá hrana v ní má alespoň jeden konec. Hamiltonovská kružnice: Kružnice procházející každým vrcholem grafu právě jednou. Eulerovský tah: Tah, který prochází každou hranou grafu právě jednou. Problém obchodního cestujícího: Nejkratší Hamiltonovská kružnice úplného grafu. ZOE: Pro matici Amxn složenou z nul a jedniček najděte vektor xm nul a jedniček takový, že Ax=1, kde 1 je vektor m jedniček. SSUM: Zjistěte, zda existuje podmožina čísel a1,...,aN taková, že její součet je právě K. BATOH: Zloděj může odnést předměty o hmotnosti a1,...,aN. Má nosnost M. Kolik nejvíc kilogramů lupu může odnést? [Jako rozhodovací problém dostane na vstupu K a otázka je, zda může zloděj odnést alespoň K kilogramů lupu.] Řešené příklady: Dokažte následující převody: Nezávislá množina -> Vrcholové pokrytí, 3D párování -> ZOE, ZOE -> SSUM, SSUM -> Batoh, SSUM -> Celočíselné lineární programování. (E3,E3)-SAT má vždy řešení. Vyřešte vrcholové pokrytí v bipartitním grafu pomocí toků [vzpomeňte si na úlohy o policistech]. Najděte polynomiální algoritmus pro SSum a Batoh zadané v unární soustavě [pro zakódování čísla K je potřeba K bitů místo obvyklých log2 K].
20. prosinec 2007	Dnešní tabulka byla podobná té minulé: NP úplné P Hamiltonovská kružnice a cesta Eulerovský tah Problém obchodního cestujícího Minimální kostra Nejdelší cesta Nejkratší cesta Dokázali jsme NP-úplnost všech problémů v levém sloupci. Také jsme si popovídali o hledání Eulerovském tahu, souvislosti mezi nejkratšími sledy a nejkratšími cestami. Skončili jsme 2-aproximací vrcholového pokrytí a naťukli 3/2-aproximaci TSP s trojúhelníkovou nerovností. Hamiltonovsá cesta: pro daný graf a dva vrcholy s a t najděte cestu z s do t, která prochází všemi vrcholy. Nejdelší cesta: pro daný graf a dva vrcholy s a t najděte nejdelší cestu z s do t. Řešené příklady: Dokažte převodem z vrcholového pokrytí, že Hamiltonovská kružnice je NP-úplná. [těžší] Dokažte převodem ze ZOE, že Hamiltonovská kružnice je NP-úplná. [těžší] [další příklady už jsou lehké] Dokažte převodem Hamiltonovské kružnice na Hamiltonovskou cestu, že Hamiltonovská cesta je NP-úplná. Dokažte převodem Hamiltonovské cesty na nejdelší cestu, že nejdelší cesta je NP-úplná. Nalezněte eulerovský tah v grafu se sudými stupni všech vrcholů. [O(N+M), prohledávání do hloubky, do tahu přidávejte hranu až při zpětném průchodu touto hranou.] Vymyslete 2-aproximační algoritmus na vrcholové pokrytí. [Rozmyslete si vztah velikosti maximálního párování a vrcholového pokrytí a pak v lineárním čase hladově nalezněte maximální párování vzhledem k inkluzi a použijte ho místo globálně maximálního párování.] Vymyslete 3/2-aproximační algoritmus na TSP s trojúhelníkovou nerovností. [Použijte MST, u vrcholů MST lichého stupně najděte nejmenší perfektní párování, přidejte k MST. Pak najděte Eulerovský tah a vrcholy, které procházíte víckrát, přeskočte pomocí trojúhelníkové nerovnosti.]
3. leden 2008	Cvičení odpadlo
10. leden 2008	Zadefinovali jsme 2-SAT a HORN-SAT a ukázali, že jsou řešitelné v polynomiálním (dokonce lineárním) čase. Dále jsme si uvědomili, že složitost Eukleidova algoritmu je O(N2). Pomocí cykličnosti Zp* pro p prvočíslo jsme si uvědomili, jak je to s odmocninami v Zp* a pomocí nich a ČVOZ jsme nahlédli, proč funguje Rabin-Miller a že má pravděpodobnost chyby nejvýš 1/2 [dokázat se dá i 1/4, ale to je těžší]. Řešené příklady: Vyřešte 2-SAT (SAT, každá klauzule má nejvýš 2 literály) v lineárním čase. Vyřešte HORN-SAT (SAT, každá klauzule má 1 neznegovaný literál) v lineárním čase. Dokažte, že Eukleidův algoritmus jde naimplementovat v čase O(N2). Pokud víte, že pro p prvočíslo je Zp* cyklická, dokažte, že každá sudá mocnina generátoru má právě dvě odmocniny a všechny liché mocniny generátoru nemají žádnou odmocninu. Pomocí minulého příkladu víte, že 1 v Zp* pro p prvočíslo má právě dvě odmocniny (určitě to jsou 1 a -1). Dokažte pomocí ČVOZ, že pro n=a1a2...ak má 1 v Zn* právě 2k různých odmocnin. Pomocí dvou předchozích cvičení ukažte, že když Rabin-Miller prohlásí číslo za složené, má vždy pravdu. Zkuste nahlédnout, že v opačném případě je pravděpodobnost chyby nejvýš 1/2.

Zápočtové práce (25. 05. 2018)

Jméno	Specifikace	Zápočet

Pokud byste něco potřebovali, napište mi na fox {zavináč} ucw {tečka} cz.