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ů.

DatumKódBodůZadání
7. 10. sseq10Hledá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é.
rymy7Vymyslete 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.
rymy28Upravte řešení předchozí úlohy, aby vypisovalo lexikograficky nejmenší z nejlepších rýmů.
14. 10. peri10Zjistě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.)
aczk8Ukaž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.
acset10Př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. fib12/15Fibonacciho slova nad abecedou {a,b} jsou definována následovně: φ0 = a, φ1 = b, φn+2 = φnφn+1. Tedy například φ2 = ab, φ3 = bab, φ4 = 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 φ4 nad abecedou {d,c}.]
cens20Censor 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 anbn a zakázaných slovech an+1, b.
sifra15Substituč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. veze10/12Na š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.
pokr12Je 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á.)
bipm8/14Vzpomeň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. doly17Mějme T továren a D dolů. Vybudovat i-tý důl stojí di 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 tj, ale potřebujeme k tomu suroviny z nějaké množiny Sj. 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.)
ddfs10Naprogramujte Dinicův algoritmus pomocí prohledávání do hloubky (jak jsme ukazovali na cvičení).
18. 11. vyska20Bude 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.)
adder10Uvaž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. xor8Vymyslete, jak složit XOR ze čtyř hradel NAND.
div610Sestrojte booleovskou hradlovou síť logaritmické hloubky, která otestuje, zda dané binární číslo je dělitelné 6.
expf15Existují 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(nk) hradlech.
lfrm20Ukaž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. ins8Sestrojte 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ů.
psort10Mějme nějakou pevnou permutaci π na množině {1,…n}. Sestrojte logaritmicky hlubokou komparátorovou síť, která tuto permutaci setřídí.
zone10Dokažte, že pokud komparátorová síť setřídí každou posloupnost nul a jedniček, tak už setřídí cokoliv.
csort10Vý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. sym8Jak efektivně zjistit, jestli je zadaná množina bodů středově symetrická?
horiz10Jak v daném (ne nutně konvexním) mnohoúhelníku najít nejdelší vodorovnou úsečku?
rect15Navrhněte algoritmus, který spočítá obsah sjednocení dané množiny obdélníků v rovině (v osové poloze).
16. 12. fft17Jak vypadá DFT vektoru (4,-4,4,-4,4,-4,4,-4)? [Vyjde hezky.]
fft27Jak vypadá DFT vektoru (0,1,0,1,0,1,0,1)? [Vyjde hezky.]
fftq8Nechť n=4k, x∈Cn a y=DFT(x). Co říká yn/4 o vektoru x?
6. 1. skck10Spočítejte Fourierův obraz vektorů ck a sk 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.
ftrot10Jak se změní Fourierův obraz, když vektor zrotujeme (cyklicky posuneme) o k pozic?
dtmf20Zí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. code10Př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 log2 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 2log2 x + O(1) bitech. Vymyslete instantní kód, kterému stačí log2 x + o(log x) bitů.
tdp10Převeďte 3D-párování na SAT.
axb10/15Dokaž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.]
batoh10Dokaž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.

Stránku spravuje Martin Mareš