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

V ZS 2016/2017 vedu jedno cvičení z ADS 2. Koná se každé úterý od 17:20 v S7.

Co jsme dělali

datum	téma
4. 10.	Opakování ADS1: Souvislé mazání grafu. Odbočka: Asymptotická notace pro funkce více proměnných. Hledání nuly v monotónní matici. Rotování řetězce na místě.
11. 10.	Vyhledávání v textu: Knuth-Morris-Pratt. Jak rozeznat zrotovaný řetězec.
18. 10.	Vyhledávání v textu: Aho-Corasicková. Různé varianty algoritmu lišící se složitostí. Nejdelší/nejkratší jehla pro každé místo v seně. Počítání výskytů.
25. 10.	Odbočka k definici algoritmu a výpočetnímu modelu RAM. Vzpomínka na profesora Machovce. O tocích a Fordově-Fulkersonově algoritmu.
1. 11.	Rozcvička: nejmenší chybějící číslo. Dinicův algoritmus a hledání těžkých sítí. Jak se chová pro jednotkové kapacity?
8. 11.	Děkanský sportovní den. Necvičíme, protože cvičíme.
15. 11.	Diskrétní Fourierova transformace.
22. 11.	Krátce o Goldbergově algoritmu na maximální tok. DFT: jak najít inverzní transformaci.
29. 11.	Aplikace Fourierovy transformace: násobení polynomů, diagonalizace tenzoru konvoluce, spektrální rozklad navzorkovaného signálu.
6. 12.	Ještě o amortizaci. Hradlové sítě: motivace, skládání všech funkcí k proměnných z 2vstupových hradel.
13. 12.	Hradlové sítě: paralelní OR a dolní odhad hloubky, porovnávání čísel, sčítání čísel. Redukce abecedy na binární.
20. 12.	Geometrické algoritmy: testování orientace, obecná poloha, střed symetrie, přímka s nejvíce body, dva ploty.
3. 1.	Převody mezi rozhodovacími problémy.
10. 1.	Další převody. NP-úplnost. Povídání o složitostních třídách a otevřených problémech.

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ů. Nad úkoly můžete rozmýšlet se svými kolegy, ale řešení musí každý sepsat sám.

Datum	Kód	Bodů	Zadání
4. 10.	wmin	10	Na počátku dostaneme číslo K. Pak nám postupně na vstupu chodí celá čísla a pokaždé máme vypsat, jaké je minimum z posledních K čísel (pokud tedy už přišlo alespoň K čísel).
4. 10.	lib	10	Byla jednou jedna knihovna, ale představte si to, chodili do ní čtenáři. Cháska nezbedná – ledva vyndají knížku z pečlivě uspořádaného regálu, po chvíli listování ji založí zpět na náhodné místo. Chudák knihovník, jak tohle má napravit? Formálněji: Mějme posloupnost N celých čísel, která vznikla ze setříděné posloupnosti přemístěním K prvků (K předem neznáme). Jak ji co nejrychleji dotřídit?
11. 10.	okraj	9	Chceme pro daný řetězec najít jeho nejdelší vlastní prefix, který je zároveň suffixem.
11. 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}.]
18. 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.
18. 10.	opak	10/20	Pro zadaný řetězec hledáme jeho nejdelší opakovaný podřetězec (tj. takový, jenž se vyskytuje na alespoň dvou různých pozicích). 10 bodů za řešení v kvadratickém čase, více za efektivnější.
25. 10.	ram	10	Naprogramujte na RAMu bublinkové třídění a stanovte jeho složitost v nejhorším případě (včetně všech konstant).
25. 10.	imst	10	Vymyslete co nejrychlejší algoritmus pro hledání minimální kostry grafu, jehož hrany jsou ohodnoceny čísly z množiny {1,2,3,4,5}.
1. 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á.)
	dinic	15	Vymyslete síť, na níž Dinicův algoritmus poběží řádově n²m kroků.
15. 11.	fft1	8	Spočítejte Fourierův obraz vektoru (0,1,0,1,0,1,0,1).
15. 11.	fft2	8	Spočítejte Fourierův obraz vektoru (1,i,-1,-i,1,i,-1,-i).
22. 11.	vyska	15	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.)
22. 11.	next	10	Mějme vyvážený binární vyhledávací strom s operacemi Find (nalezení prvku s danou hodnotou) a Next (nalezení následníka prvku vráceného předchozí operací Find nebo Next). Ukažte (třeba pomocí vhodného potenciálu), že amortizovaná složitost operace Find je O(log n) a operace Next O(1).
29. 11.	fftr	10	Dokažte, že ve Fourierově obrazu reálného vektoru jsou y_k a y_n-k navzájem komplexně sdružená.
29. 11.	ftrot	10	Jak se změní Fourierův obraz, když vektor zrotujeme (cyklicky posuneme) o k pozic?
6. 12.	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.
13. 12.	div5	10	Navrhněte hradlovou síť, která otestuje, jestli je zadané n-bitové číslo dělitelné pěti.
13. 12.	log2	10	Navrhněte hradlovou síť, která pro dané n-bitové číslo spočítá jeho celočíselný dvojkový logaritmus (tedy index nejvyšší jedničky).
20. 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í.)
20. 12.	ploty	10	V rovině je N bodů, chceme najít dva mnohoúhelníky s co nejmenším součtem obvodů, které budou obsahovat všechny zadané body.
3. 1.	bit	10	Vymyslete kódování vstupů pro rozhodovací problém k-obarvitelnosti grafu pomocí řetězců bitů. Tato a následující úlohy se počítají za plný počet bodů do konce zkouškového období.
3. 1.	rez	10	Převeďte následující problém na SAT: Je dán neorientovaný graf a číslo K. Existuje rozklad množiny vrcholů na dvě podmnožiny takové, že mezi nimi vede alespoň K hran?
10. 1.	lineq	15	Dokažte, že následující problém je NP-úplný: Je dána soustava lineárních rovnic s celočíselnými koeficienty. Existuje řešení této soustavy, v němž jsou hodnoty všech proměnných nuly a jedničky?
	e3e3	15	Nechť 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í.
	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.

Videozáznamy

Algoritmy a datové struktury I 2015 (přístupné pouze studentům a zaměstnancům MFF UK)
Algoritmy a datové struktury II 2012 (nekompletní; přístupné pouze studentům a zaměstnancům MFF UK)