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


Cvičení se koná ve čtvrtek v 9:00 na Malé Straně v S1. Pozor na to, že jsem si v třetím týdnu semestru prohodil cvičení s Martinem Marešem.

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

Zápočet získáte za vypracování zápočtové práce. Ta by měla obsahovat implementaci některého zajímavého a netriviálního algoritmu, ať už z přednášky nebo odjinud, a dokumentaci. Dokumentace je popis toho, jak algoritmus nebo implementace funguje, proč funguje a jakou má časovou a paměťovou složitost. Co přesně musíte udělat:
  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í.
Kromě předchozího seznamu je velmi vhodná aktivní účast na cvičení (když si vás budu pamatovat, tak nejspíš nemusíte dělat neudělatenou práci a tak :–).

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

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

DatumObsah
< 18. říjen 2007Tato cvičení jsem necvičil já.
18. říjen 2007Diniců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 2007Zamotá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 2007Rozmotá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 2007Vyř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 2007Prohrabali 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 2007Dodě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 2007Pořá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 2007Nejdří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 2007Dneš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 2007Dneš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 2008Cvičení odpadlo
10. leden 2008Zadefinovali 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 (15. 09. 2008)

JménoSpecifikaceZápočet
Peter BašistaNásobení dlouhých číselAno
Martin BrejchaŘešítko osmisměrekAno
Martin DouchaSimulátor hradlových sítíAno
Vladimír FiklíkDinicův algoritmusAno
Martin GalajdaDisjunktní cestyAno
Jan Havlíček3D konvexní obalNe
Tomáš HejlDělení dlouhých číselAno
Michal KmetMaximální párování v bipartitním grafuNe
Kamil KosVoroneho diagramyAno
Michal KrausGoldbergův algoritmusNe
Tomáš KrautMaximální párování v obecném grafuAno
Martin KupecNejdelší společné podslovoAno
Ondřej MoravčíkNejdelší palindromické podslovoNe
Zdeněk PátekHledání extrémů funkcíAno
Oto PetříkUltimátní konvexní obalAno
Peter SzépeRabin MillerAno
Radomir TarabicString-o-sortAno
Jan ZálohaŽádnáNe
Bohumír ZámečníkFFT a spektrální analýzaAno

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


Zpět