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

V ZS 2015/2016 vedu jedno cvičení ke své přednášce z ADS2. Koná se každou středu od 15:40 v S1 (přestěhováno z S7).

Co jsme dělali

datum	téma
7. 10.	Pomalé hledání podřetězců je opravdu pomalé. Jak se změní vyhledávací úloha, pokud nehledáme souvislý podřetězec, ale vybranou podposloupnost? Rotování řetězce na místě.
14. 10.	Opakování algoritmů KMP a AC. 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ů.
21. 10.	Řetězce: Nejkratší a nejdelší jehla končící na dané pozici. Histogram výskytů v lineárním čase. Nejdelší společný podřetězec.
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: chování pro jednotkové kapacity, maximální možný počet fází. Výroba a pojídání čokolády.
18. 11.	Goldbergův algoritmus a jeho podivuhodné vlastnosti. Implementace téhož. Odbočka od věží k permanentům matic a algebraickým rozšířením těles.
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.	Hradlové sítě podruhé: paralelní porovnávačka, odčítačka a nasobička. Dolní odhady pomocí dosažitelnosti.
9. 12.	Geometrické algoritmy. Trocha analytické geometrie: obsahy trojúhelníků a testy orientace úhlu pomocí determinantů. Jak se zbavit předpokladů o obecné poloze.
16. 12.	Fourierova transformace na vlastní kůži. Jak se transformují jednoduché vektory. Odvozujeme inverzní transformaci.
6. 1.	Fourierova transformace podruhé: antisymetrie, vzorkování reálných funkcí.
13. 1.	Převody problémů a NP-úplnost. Kódování vstupů a bezprefixové kódy. Algebraická odbočka o testování prvočíselnosti.

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.	sseq	10	Hledáme v seně jehlu coby vybranou podposloupnost. Navrhněte algoritmus, který vypíše všechny výskyty. Plný počet bodů za řešení se složitostí O(S+JV), kde S je délka sena, J délka jehly a V počet výskytů; menší počet bodů za méně efektivní, ale stále polynomiální řešení. Můžete předpokládat, že všechny znaky jehly jsou navzájem různé.
	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ů.
14. 10.	peri	10	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.)
	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.)
21. 10.	fib	12/15	Fibonacciho slova nad abecedou {a,b} jsou definována následovně: φ₀ = a, φ₁ = b, φ_n+2 = φ_nφ_n+1. Tedy například φ₂ = ab, φ₃ = bab, φ₄ = abbab, … Najděte v daném seně nad abecedou {a,b} nejdelší podřetězec, který je Fibonacciho slovem. [Obecnější verze za 15 bodů: je dáno seno nad obecnou abecedou, hledáme nejdelší podřetězec, který je Fibonacciho slovem nad nějakou abecedou. Tedy například v seně `adccdca` je to `dccdc`, což je φ₄ nad abecedou {d,c}.]
	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.
	sifra	15	Substituční šifra funguje tak, že zpermutujeme znaky abecedy: například permutací abecedy `ABCDEO` na `DACEBO` zašifrujeme slovo `ABADCODE` na `DADECOEB`. Zašifrovaný text je méně srozumitelný, ale například vyzradí, kde v originálu byly stejné znaky a kde různé. Úloha: Je dáno seno zašifrované substituční šifrou a nezašifrovaná jehla. Najděte všechny možné výskyty jehly v originálním seně (tedy takové pozice v seně, pro něž existuje permutace abecedy, která přeloží jehlu na příslušný kousek sena).
4. 11.	veze	10/12	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 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/14	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. [14 bodů: uměli byste totéž s úlohou o kostkách na šachovnici?]
11. 11.	doly	17	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_j, ale potřebujeme k tomu suroviny z nějaké množiny S_j. 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.)
11. 11.	ddfs	10	Naprogramujte Dinicův algoritmus pomocí prohledávání do hloubky (jak jsme ukazovali na cvičení).
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.)
18. 11.	adder	10	Uvažujme následující algoritmus na sčítání n-ciferných dvojkových čísel: Čísla sečteme cifru po cifře. Tím vzniknou cifry 0, 1 a 2. Dvojek se zbavíme takto: vždy si vybereme libovolnou 2, přepíšeme ji na 0 a cifru vlevo od ní zvýšíme o 1. Kdyby někde vznikla 3, přepíšeme ji na 1 a cifru vlevo od ní opět zvýšíme o 1. Dokažte, že tento algoritmus doběhne v čase O(n). Nápověda: Definujte vhodný potenciál.
25. 11.	xor	8	Vymyslete, jak složit XOR ze čtyř hradel NAND.
	div6	10	Sestrojte booleovskou hradlovou síť logaritmické hloubky, která otestuje, zda dané binární číslo je dělitelné 6.
	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.
	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.)
3. 12.	ins	8	Sestrojte komparátorovou síť pro zatřídění prvku do setříděné posloupnosti Na vstupu tedy dostane n-prvkovou setříděnou posloupnost a jeden další prvek a na výstupu bude mít n+1 setříděných prvků.
	psort	10	Mějme nějakou pevnou permutaci π na množině {1,…n}. Sestrojte logaritmicky hlubokou komparátorovou síť, která tuto permutaci setřídí.
	zone	10	Dokažte, že pokud komparátorová síť setřídí každou posloupnost nul a jedniček, tak už setřídí cokoliv.
	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í.)
9. 12.	sym	8	Jak efektivně zjistit, jestli je zadaná množina bodů středově symetrická?
	horiz	10	Jak v daném (ne nutně konvexním) mnohoúhelníku najít nejdelší vodorovnou úsečku?
	rect	15	Navrhněte algoritmus, který spočítá obsah sjednocení dané množiny obdélníků v rovině (v osové poloze).
16. 12.	fft1	7	Jak vypadá DFT vektoru (4,-4,4,-4,4,-4,4,-4)? [Vyjde hezky.]
	fft2	7	Jak vypadá DFT vektoru (0,1,0,1,0,1,0,1)? [Vyjde hezky.]
	fftq	8	Nechť n=4k, x∈Cⁿ a y=DFT(x). Co říká y_n/4 o vektoru x?
6. 1.	skck	10	Spočítejte Fourierův obraz vektorů c^k a s^k vzorkovaných cosinů a sinů (definici najdete ve skriptech). Dokažte pomocí toho, že každý reálný vektor lze zapsat jako lineární kombinaci těchto sinových a cosinových vektorů pro k=0,…n/2.
	ftrot	10	Jak se změní Fourierův obraz, když vektor zrotujeme (cyklicky posuneme) o k pozic?
	dtmf	20	Získejte heslo z této nahrávky. Prozradíme, že se jedná o frekvenční telefonní volbu (DTMF), ale dekodér si napište sami. Prozradíme, že se na to hodí FFT :)
13. 1.	code	10	Při kódování vstupu řetězcem bitů se často hodí umět zapsat číslo předem neznámé velikosti instantním kódem, tj. takovým, při jehož čtení poznáme, kdy skončil. Dvojkový zápis čísla x zabere log₂ x + O(1) bitů, ale není instantní. Pokud za každý bit dvojkového zápisu připíšeme informaci o tom, zda kód pokračuje, získáme instantní kód o 2log₂ x + O(1) bitech. Vymyslete instantní kód, kterému stačí log₂ x + o(log x) bitů.
	tdp	10	Převeďte 3D-párování na SAT.
	axb	10/15	Dokažte NP-úplnost následujicího problému: je dána celočíselná matice A a celočíselný vektor b, existuje vektor x tvořený nulami a jedničkami, pro který Ax=b? [15 bodů: A, b jsou také tvořeny nulami a jedničkami.]
	batoh	10	Dokažte NP-úplnost rozhodovací verze problému batohu z přednášky.

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.