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

V ZS 2013/2014 vedu jedno cvičení ke své přednášce z ADS2. Koná se každé pondělí od 10:40 v S10.

Co jsme dělali

datum	téma
7. 10.	Opakování z minulého semestru: k-tá permutace v lexikografickém pořadí Dotřídění posloupnosti, která vznikla ze setříděné přesunutím nejvýše k prvků Jak z libovolného vyhledávacího stromu udělat AVL-strom Datové struktura pro dynamický výpočet mediánu Konstrukce nejdelšího slovního žebříku
14. 10.	Pomalé hledání podřetězců je opravdu pomalé. Rotování řetězce na místě. Opakování KMP.
21. 10.	Kdy je jeden řetězec rotací druhého? Jak najít nejdelší podslovo, které je současně prefixem i suffixem daného slova? Superlineární počet výskytů. Histogram výskytů v lineárním čase.
28. 10.	Cvičení se nekoná, slavíme státní narozeniny.
4. 11.	Toky v sítích: efektivita F-F algoritmu (pro celočíselné a pro jednotkové kapacity), párování a disjunktní cesty. Dominové kostky na okousané šachovnici.
11. 11.	Dinicův algoritmus a jeho chování pro jednotkové kapacity.
18. 11.	Goldbergův algoritmus a jeho podivuhodné vlastnosti. Implementace téhož.
25. 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.
2. 12.	Geometrické algoritmy. Trocha analytické geometrie: obsahy trojúhelníků a testy orientace úhlu pomocí determinantů. Obsahy konvexních i nekonvexních mnohoúhelníků.
9. 12.	Fourierova transformace na vlastní kůži. Jak se transformují jednoduché vektory.
16. 12.	Fourierova transformace podruhé. Odvozujeme inverzní transformaci. Pohled očima algebraikovýma. Kroucení hřebenu. Vzorkování funkcí.
6. 1.	Převody problémů a NP-úplnost. Kódování vstupů.

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í
7. 10.	prank	10	Na cvičení jsme ukázali, jak v lexikografickém uspořádání všech permutací na množině {1,…n} najít k-tou permutaci v čase O(n log n). Podobně by šlo řešit i inverzní problém: dostanu permutaci a mám zjistit, kolikátá v pořadí je. Zvolte jiné vhodné uspořádání a ukažte, že v něm lze obě úlohy zvládnout v čase O(n).
7. 10.	lavl	10	Už víme, jak z libovolného binárního vyhledávacího stromu vyrobit AVL-strom v čase O(n). Dokažte, že to lépe nejde.
14. 10.	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.
14. 10.	rymy2	8	Upravte řešení předchozí úlohy, aby vypisovalo lexikograficky nejmenší z nejlepších rýmů.
21. 10.	peri	15	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.)
	rper	8	Ukažte, že je-li řetězec roven nějaké své netriviální rotaci, pak je periodický.
	lmr	20	Navrhněte algoritmus, který pro zadané slovo nalezne lexikograficky nejmenší z jeho rotací.
	aczk	8	Ukažte, že u algoritmu Aho-Corasicková jsou zkratky potřeba: Předpokládejme, že bychom u každého stavu zkoumali, do jakých všech stavů se lze dostat po zpětných hranách, a sbírali ty koncové. Sestrojte vstup, pro který tím strávíme víc než lineární čas, ačkoliv nenajdeme vůbec žádný výskyt.
	acset	10	Předpokládejme, že kdybychom u algoritmu Aho-Corasicková pro každý stav sestrojili množinu slov, jejichž výskyt máme hlásit. Sestrojte slovník, u nějž bude celková velikost těchto množin (součet počtů prvků) větší než lineární s velikosti slovníku. (Z toho plyne, že při přímočaré reprezentaci množin nelze doufat v to, že půjdou sestrojit v lineárním čase.)
	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.
4. 11.	veze	10	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.
	pokr	12	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á.)
	bipm	8	Vzpomeňte si, jak jsme na cvičení převedli největší párování v bipartitním grafu na maximální tok v jisté síti. Nahlédněte, jak chod F-F algoritmu přeložit do řeči párování v původním grafu a získat tak algoritmus na největší párování, který vůbec nepoužívá toky. [+6 bodů: uměli byste totéž s úlohou o kostkách na šachovnici?]
11. 11.	coko	7	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 a přepravovat, aby byly požadavky všech Matfyzů uspokojeny.
11. 11.	doly	17	Model surovin. Mějme T továren a D dolů. Vybudovat i-tý důl stojí d_i peněz a od té doby důl produkuje neomezené množství i-té suroviny. Vybudujeme-li j-tou továrnu, přinese nám to (jednorázový) zisk t_i, ale potřebujeme k tomu suroviny z nějaké množiny S_i. Navrhněte, které doly a továrny postavit, aby každá postavená továrna dostala potřebné suroviny a čistý zisk byl největší možný. (Tím myslíme rozdíl zisku z továren a nákladů na doly.)
18. 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ů. (Úloha se počítá za plný počet bodů až do konce zkouškového.)
	gint	8	Jakou časovou složitost bude mít Goldbergův algoritmus na sítích s jednotkovými kapacitami?
	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.
	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.
25. 11.	xor	8	Vymyslete, jak složit XOR ze čtyř hradel NAND.
	gen	10	Dokažte, že žádná jiná booleovská funkce 2 proměnných než NAND a NOR negeneruje všechny ostatní.
	expf	15	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.
	form	10	Ukažte, že ke každé hradlové síti s jedním výstupem existuje booleovská formule, která počítá totéž.
	lfrm	20	Ukažte, že ke každé formuli existuje hradlová síť, která počítá totéž a má menší než lineární hloubku v délce formule. (Počet bodů závisí na tom, jak mělkou síť dokážete najít.)
2. 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í.)
	sym	10	Jak efektivně zjistit, jestli je zadaná množina bodů středově symetrická?
	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?
9. 12.	fft1	7	Jak vypadá DFT vektoru (4,-4,4,-4,4,-4,4,-4)? [Vyjde hezky.]
9. 12.	fft2	7	Jak vypadá DFT vektoru (0,1,0,1,0,1,0,1)? [Vyjde hezky.]
16. 12.	sinc	15	Uvažujme funkce sin(ax) a cos(ax) pro a ∈ {0,…n-1}, navzorkované v n bodech intervalu [0,2π). Spočítejte Fourierovu transformaci jejich vektorů vzorků. (Nápověda: sin x = (e^ix - e^-ix)/2i, cos x = (e^ix + e^-ix)/2.) Na tuto a následující úlohy se nevydává nápověda. Jsou stále za plný počet bodů.
	rft	10	Dokažte, že DFT reálného vektoru je "antisymetrická", přesněji, že y_j a y_n-j jsou komplexně sdružená čísla.
	rsin	10	Pomocí předchozích dvou cvičení dokažte, že každý reálný vektor lze zapsat jako lineární kombinaci navzorkovaných sinů a cosinů. To ukazuje, jak DFT použít ke spektrálnímu rozkladu navzorkovaného signálu.
6. 1.	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.
	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í.
	ssum	10	Dokažte NP-úplnost problému "Je dána množina přirozených čísel a číslo K. Existuje podmnožina, jejíž součet by byl roven K?" Můžete na něj zkusit převést soustavu celočíselných rovnic z cvičení.
	pcomp	8	Jak vypadají P-úplné problémy? Tedy takové, které leží v P a cokoliv z P se na ně dá převést.

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.