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

DatumKódBodůZadání
3. 10. rot10Na 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.
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ů.
10. 10. peri20Zjistě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. 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.
arot10Nechť 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. coko10Model 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. veze15Na š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.
pokr15Je 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. 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ů. (Úlohu jsem upravil a zvýšil počet bodů.)
gint8Jakou časovou složitost bude mít Goldbergův algoritmus na sítích s jednotkovými kapacitami?
adder8Dokaž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.
gmax10Popište implementaci Goldbergova algoritmu s výběrem nejvyššího vrcholu s přebytkem tak, aby doběhla v čase O(n3). Můžete používat věty dokázané ve studijním textu.
14. 11. four17Spočtěte Fourierův obraz vektoru (1,-1,1,-1,1,-1,1,-1).
four27Spočtěte Fourierův obraz vektoru (0,1,0,1,0,1,0,1).
fbase10Najděte vektory x0, … xn-1 takové, že Fourierův obraz vektoru xi má jedničku na i-té pozici a všude jinde nuly.
finv8Pomocí výsledku předchozího cvičení zkonstruujte invezní Fourierovu transformaci.
21. 11. equiv7Dokažte, že ekvivalence není generátor všech booleovských funkcí 2 proměnných.
xor10Vymyslete, jak složit XOR ze čtyř hradel NAND.
expf20Existují 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.
28. 11. cmp15Navrhněte hradlovou síť logaritmické hloubky, která rozhodne, zda je jedno n-bitové číslo menší než druhé.
form10Ukažte, že ke každé hradlové síti s jedním výstupem existuje booleovská formule, která počítá totéž.
5. 12. 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í.)
obsah15Sestrojte algoritmus, který vypočítá obsah zadaného (ne nutně konvexního) mnohoúhelníku.
sym10Jak efektivně zjistit, jestli je zadaná množina bodů středově symetrická?
12. 12. rect15Navrhněte algoritmus, který spočítá obsah sjednocení dané množiny obdélníků v rovině (v osové poloze).
horiz10Jak v daném (ne nutně konvexním) mnohoúhelníku najít nejdelší vodorovnou úsečku?
ins8Domyslete detaily algoritmu na průsečíky úseček z cvičení, aby fungoval i pro jinou než obecnou polohu úseček.
conv8Vymyslete 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. 2sat15Ukaž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.
e3e315Nechť 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í.
3sat9Na 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. lineq15Uvaž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?
ssum10Př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?"
nzm410Změ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.

Stránku spravuje Martin Mareš