Cvičení z Algoritmů a Datových Struktur II

… se v ZS 2011/2012 koná ve středu od 12:20 v S1.

Zápočet se uděluje za zápočtovou práci a vyřešení domácích úkolů za 100 bodů. Účast na cvičení je polehčující okolností. Dalších 100 bodů za úkoly může nahradit zápočtovou práci.

Informace o přednášce (syllabus, učební texty atd.) získáte na stránce prof. Kučery. Dalším zajímavým zdrojem je stránka mé loňské přednášky, kde jsou dostupná i skriptíčka pokrývající většinu látky.

Co jsme dělali

datum	téma
3. 10.	Jak rotovat řetězec. Nejčetnější slovo v textu (pomocí trie).
10. 10.	Variace na Knuthův-Morrisův-Prattův algoritmus: Kdy je jeden řetězec rotací druhého? Nejdelší slovo, které je současně prefixem i suffixem zadaného.
17. 10.	Variace à la Aho-Corasicková: nejdelší či nejkratší výskyt na každé pozici, proč jsou potřeba zkratkové hrany, počítání četností slov.
24. 10.	Toky v sítích: kdy je F-F algoritmus pomalý; toky s kapacitami ve vrcholech; co nejvíce hranově či vrcholově disjunktních cest mezi dvěma vrcholy; pokrývání šachovnice dominovými kostkami. Dinicův algoritmus. (cvičil Michal Vaner)
31. 10.	Toky v sítích: Celočíselné sítě a celočíselné toky. Chování algoritmů pro jednotkové kapacity. Ještě trocha párování. Do konce listopadu pošlete téma své zápočtové práce.
7. 11.	Goldbergův algoritmus a jeho implementace.
14. 11.	Diskrétní Fourierova transformace.
21. 11.	Hradlové sítě: zvěřinec booleovských funkcí; jak vypadají minimální generátory; proč si vystačíme s binární abecedou a 2-vstupovými hradly. Paralelní OR a sekvenční sčítačka.
28. 11.	Pokračování hradlových sítí: souvislosti mezi sítěmi, funkcemi a formulemi. Porovnávání binárních čísel.
5. 12.	Geometrické algoritmy: Robin Hood kontra billboardy. Trocha analytické geometrie: obsahy trojúhelníků a testy orientace pomocí determinantů. Obsah sjednocení obdélníků zametáním roviny. Obsah obecného mnohoúhelníku.
12. 12.	Pokračování geometrických algoritmů. Polomáčené mrakodrapy 1D i 2D. Průsečíky úseček.
19. 12.	Převody problémů: nezávislá množina, klika, vrcholové pokrytí, SAT, 3-SAT.
2. 1.	Převody problémů: 3,3-SAT, obvodový SAT, nezávislá množina na SAT.
9. 1.	Otázky a odpovědi. Pár poznámek o složitostních třídách a úplnosti.

Zápočtová práce

Zápočtová práce obnáší vyřešení nějaké algoritmické úlohy. Chci od vás popis algoritmu, rozbor správnosti a časové i paměťové složitosti, velice doporučuji napsat i program a nepoužívat v něm knihovní funkce, u kterých netušíte, jak jsou implementované. Dobrou inspirací k tomu, jak o algoritmech psát, může být třeba archiv KSP nebo MO-P.

Pokud vás žádné téma nenapadá, můžete využít služeb našeho nápadníku. Není sice tak sladký jako polibek informatické múzy, ale v nouzi také poslouží.

Přečtěte si úvodní text o tom, jak psát.

Domácí úkoly

Na cvičeních budu zadávat různě obtížné domácí úkoly, měli byste za ně získat celkem 100 bodů. Po dvou týdnech od zadání úkolu na cvičení povím nápovědu, od té doby můžete za úkol získat jen poloviční počet bodů.

Datum	Kód	Bodů	Zadání
3. 10.	rot	10	Na cvičení jsme vymysleli algoritmus na rotování řetězce, který každý znak přesune jen jednou (rovnou na cílovou pozici). Dokažte, že tento algoritmus funguje.
	rymy	7	Vymyslete algoritmus, který načte slovník a pak umí pro zadaná slova nacházet nejlepší rýmy – tím se myslí slovo ve slovníku, které má se zadaným slovem má co nejdelší společný suffix (a je od něj různé). Pokud je nejlepších rýmů více, vypište libovolný z nich. Časová složitost odpovědi na dotaz by neměla záviset na velikosti slovníku.
	rymy2	8	Upravte řešení předchozí úlohy, aby vypisovalo lexikograficky nejmenší z nejlepších rýmů.
10. 10.	peri	20	Zjistěte, zda je zadaný řetězec periodický, tj. zda ho lze zapsat jako několikanásobné opakování nějakého kratšího řetězce. (Např. `abcabc` je periodický, `abcabca` nikoliv.)
17. 10.	cens	20	Censor dostane slovník zakázaných slov a text ke kontrole. V textu vždy nalezne nejlevější výskyt zakázaného slova (přesněji s nejlevějším možným koncem a pokud je takových více, tak nejdelší), ten vystříhne a proceduru opakuje, dokud jsou v textu nějaká zakázaná slova. Nalezněte algoritmus, který téhož výsledku dosáhne v lineárním čase. Než své řešení odevzdáte, vyzkoušejte ho na textu aⁿbⁿ a zakázaných slovech aⁿ⁺¹, b.
17. 10.	arot	10	Nechť n je prvočíslo. Kolik existuje slov délky n nad abecedou {0,1}, která nejsou rovna žádné své netriviální rotaci? (Za řešení, které funguje pro libovolné n, nadělím dalších 10 bodů.)
24. 10.	coko	10	Model trhu s čokoládou. Uvažujme graf železniční sítě. Hrany jsou tratě, každá má svou přepravní kapacitu. Ve vrcholu muže být továrna (vyrábí až daný počet vagonů čokolády denně) nebo Matfyz (spotřebuje až daný počet vagonů čokolády denně). Navrhněte, kolik kde vyrábět, spotřebovat a přepravovat, aby se celkově prodalo co nejvíce čokolády.
31. 10.	veze	15	Na šachovnici R×S, které některá políčka chybí, chceme rozestavět co nejvíce šachových věží tak, aby se navzájem neohrožovaly. V lehčí verzi se ohrožují i přes chybějící políčka, v těžší verzi (+5 bodů) nikoliv.
31. 10.	pokr	15	Je dán bipartitní graf. Chcete najít jeho nejmenší vrcholové pokrytí, tj. nejmenší množinu vrcholů takovou, aby každá hrana obsahovala alespoň jeden z vybraných vrcholů. (Chceme rozestavět co nejméně strážníků na křižovatky, aby každá ulice byla hlídaná.)
7. 11.	vyska	20	Bude Goldbergův algoritmus stále fungovat, pokud zdroji nastavíme výšku n-1, n-2, popřípadě n-3? Přijímám i částečná řešení za část bodů. (Úlohu jsem upravil a zvýšil počet bodů.)
	gint	8	Jakou časovou složitost bude mít Goldbergův algoritmus na sítích s jednotkovými kapacitami?
	adder	8	Dokažte, že následující algoritmus na sčítání dvojkových čísel má lineární časovou složitost: Nejprve čísla sečteme po číslicích, tím vzniknou číslice 0, 1, 2. Poté číslo procházíme zleva. Narazíme-li na číslici 0 nebo 1, posuneme se o cifru doprava. Pokud narazíme na větší číslici, odečteme od ní 2, posuneme se o cifru doleva a tam přičteme jedničku. Opustíme-li číslo levým okrajem, přimyslíme si tam 0. Opustíme-li pravým, zastavíme se.
	gmax	10	Popište implementaci Goldbergova algoritmu s výběrem nejvyššího vrcholu s přebytkem tak, aby doběhla v čase O(n³). Můžete používat věty dokázané ve studijním textu.
14. 11.	four1	7	Spočtěte Fourierův obraz vektoru (1,-1,1,-1,1,-1,1,-1).
	four2	7	Spočtěte Fourierův obraz vektoru (0,1,0,1,0,1,0,1).
	fbase	10	Najděte vektory x₀, … x_n-1 takové, že Fourierův obraz vektoru x_i má jedničku na i-té pozici a všude jinde nuly.
	finv	8	Pomocí výsledku předchozího cvičení zkonstruujte invezní Fourierovu transformaci.
21. 11.	equiv	7	Dokažte, že ekvivalence není generátor všech booleovských funkcí 2 proměnných.
	xor	10	Vymyslete, jak složit XOR ze čtyř hradel NAND.
	expf	20	Existují těžké funkce: Dokažte, že pro každé k a dost velké n ("dost velké" může záviset na k) existuje booleovská funkce n proměnných, která se nedá spočítat hradlovou sítí o O(n^k) hradlech.
28. 11.	cmp	15	Navrhněte hradlovou síť logaritmické hloubky, která rozhodne, zda je jedno n-bitové číslo menší než druhé.
28. 11.	form	10	Ukažte, že ke každé hradlové síti s jedním výstupem existuje booleovská formule, která počítá totéž.
5. 12.	csort	10	Výpočet konvexního obalu je alespoň tak těžký jako třídění reálných čísel: ukažte, že umíte-li vypočítat konvexní obal množiny n bodů v čase T(n), lze třídit n reálných čísel v čase O(T(n)). (Vypočtením konvexního obalu přitom myslíme nejen stanovení, které body na obalu leží, ale i v jakém pořadí.)
	obsah	15	Sestrojte algoritmus, který vypočítá obsah zadaného (ne nutně konvexního) mnohoúhelníku.
	sym	10	Jak efektivně zjistit, jestli je zadaná množina bodů středově symetrická?
12. 12.	rect	15	Navrhněte algoritmus, který spočítá obsah sjednocení dané množiny obdélníků v rovině (v osové poloze).
	horiz	10	Jak v daném (ne nutně konvexním) mnohoúhelníku najít nejdelší vodorovnou úsečku?
	ins	8	Domyslete detaily algoritmu na průsečíky úseček z cvičení, aby fungoval i pro jinou než obecnou polohu úseček.
	conv	8	Vymyslete algoritmus, který najde konvexní obal množiny n bodů v rovině v čase O(nh), kde h je počet vrcholů nalezeného konvexního obalu.
19. 12.	2sat	15	Ukažte, jak 2-SAT (splnitelnost logických formulí v CNF, jejichž každá klauzule obsahuje nejvýše 2 literály) vyřešit v polynomiálním čase. Na tuto a následující úlohy se nevydává nápověda.
	e3e3	15	Nechť 3-SAT omezíme tak, aby každá klauzule obsahovala právě 3 různé proměnné a každá proměnná se vyskytovala v právě 3 klauzulích. Ukažte, že takový problém je triviální.
	3sat	9	Na cvičení jsme ukazovali, jak převést SAT na 3-SAT. Dodělejte detaily, aby převod proběhl v lineárním čase.
2. 1.	lineq	15	Uvažujme následující problém: "Je dána celočíselná matice A a vektor b. Existuje vektor x složený jen z 0 a 1 takový, že Ax=b?" Převeďte na tento problém SAT (nebo některý z dalších ekvivalentních problémů). O 5 bodů více: co když matice A i vektor b jsou také tvořeny jen 0 a 1?
	ssum	10	Převeďte problém z předchozího cvičení na "Je dána množina přirozených čísel a číslo K. Existuje podmnožina, jejíž součet by byl roven K?"
	nzm4	10	Změní se obtížnost problému nezávislé množiny, pokud se omezíme na grafy s maximálním stupněm 4?

Pokud je úkolem sestrojit algoritmus, nezapomeňte stanovit jeho časovou a paměťovou složitost.

Úkoly prosím posílejte na mj+ads@ucw.cz.