ADS II (2017/2018)

Cvičení k přednášce Algoritmy a datové struktury II

Organizace

K získání zápočtu je nutno nasbírat 90 bodů.

Na každém cvičení bude zadáno několik úkolů a za správné vyřešení alespoň jednoho z nich je odměna 10 bodů (tj. za vyřešení více úkolů z jednoho cvičení je stále 10 bodů).

Aktivita na cvičení bude odměněna 5 body (tj. více aktivity na jednom cvičení je stále 5 bodů).

Body

Smazáno kvůli GDPR.

Úkoly

3.10. (do 17.10.) - opakování ADS I

Najděte funkce f a g takové, že neplatí ani f = O(g), ani g = O(f).
Barvení 5 barvami: Mějme rovinný graf, tedy takový, co se dá nakreslit do roviny bez křížení hran. Přiřaďte vrcholům čísla z množiny {1, ..., 5} tak, aby žádné dva vrcholy spojené hranou nedostaly stejné číslo. Zkuste v čase O(n^2)
Kritická hrana budiž taková, která leží na všech nejkratších cestách. Tedy ta, jejíž prodloužení by ovlivnilo vzdálenost. Navrhněte algoritmus, který najde všechny kritické hrany.

10.10. (do 24.10.)

Nalezněte lexikograficky minimální rotaci řetězce (v O(n))
Zjistěte, zda je zadané slovo periodické (v O(n))
Pestrý budeme říkat takovému řetězci, jehož všechny rotace jsou navzájem různé. Kolik existuje pestrých řetězců délky n (n je prvočíslo) nad abecedou P?

17.10. (do 31.10.)

Pro daný slovník chceme vytvořit datovou strukturu, která bude umět rychle odpovídat na dotazy "je ve slovníku rotace slova x?" pro zadané slovo x. Můžete předpokládat, že ve slovníku je m slov a každé má délku n. Doba stavění struktury není důležitá, ale použijte rozumné množství paměti (pamatování si všech možných rotací pro každé slovo není rozumné množství)
Upravte automat z algoritmu AC tak, aby byl efektivní i pro velké abecedy.
Definujeme Fibonacciho slovo takto: F(0) = a, F(1) = b, F(n+2) = F(n)F(n+1). Vymyslete algoritmus, který v řetězci nad abecedou {a,b} nalezne nejdelší Fibonacciho slovo v řetězci délky n.
Stejně jako v předchozím příkladě hledáme nejdelší Fibonacciho slovo, ale můžeme libovolně prohodit písmena a a b v definici F(0) a F(1).

24.10. (do 7.11.)

Nalezněte příklad sítě s reálnými kapacitami, na které se Ford Fulkersonův algoritmus nezastaví. (limita, ke které jde nalezený tok může být libovolná)
Máte zadaný orientovaný graf G a v něm dva vrcholy u a v. Jak nalézt všechny hranově disjunktní cesty? Jak všechny vrcholově disjunktní?

31.10. (do 14.11.)

Nalezněte síť, na které Dinicův algoritmus provede co největší počet kroků (blížící se k hornímu odhadu z hodiny - O(V^2 E))
Máte danou šachovnici s dírami. Jak na ni rozestavit co nejvíce věží aniž se budou navzájem ohrožovat? Věž nesmí stát na díře a věže se přes díry neohrožují.
Dopravní problém: Uvažujme továrny T_1, ..., T_p a obchody I_1, ..., O_q. Všichni vyrábějí a spotřebovávají stejný druh zboží. T_i vyrobí t_i zboží za den a O_i spotřebuje o_i za den. Navíc známe bipartitní graf, který udává která továrna může dodávat do kterého obchodu (a kolik). Jak zjisti zda se všechny požadavky obchodů dají splnit? Která továrna má dodávat kolik zboží do kterého obchodu?

7.11. (do 21.11.)

Máme děravou šachovnici NxN. Budeme na ní pokládat kostičky velikosti 1x2 (můžete je i otáčet), tak aby žádná neležela na díře. Zjistěte, kolik nejvíce kostiček lze na šachovnici umístit a zda můžu pokrýt každé neděravé políčko šachovnice.
Jak pro zadané k a graf G zjisti, zda je graf vrcholově k-souvislý? Algoritmus pro hledání toku můžete pustit méně než řádově n^2-krát, kde n je počet vrcholů G.
Jak pro zadané k a graf G zjisti, zda je graf hranově k-souvislý? Algoritmus pro hledání toku můžete pustit méně než řádově n^2-krát, kde n je počet vrcholů G.

14.11. (do 28.11.)

Máte k dispozici komparátor (hradlo, které pro 2 vstupní čísla vydá jejich minimum vlevo a jejich maximum vpravo). Navrhněte komparátorovou síť, která na vstupu dostane n čísel a vydá jejich permutaci, v níž je poslední hodnota největší. Kolik jste použili hradel? Kolik má síť hladin? Dokažte, že to nejde udělat v méně hladinách.
Definujeme "výhybku" - ternární booleovské hradlo se vstupy x_0, x_1, p, jehož výstupem je x_p. Ukažte, že libovolná booleovská funkce se dá poskládat z výhybek. Jak naopak poskládat výhybku z binárních hradel?
Navrhněte komparátorovou síť pro Insert Sort. Jak se bude lišit od sítě pro Bubble Sort? Síť pro Bubble Sort jsme si předvedli na cvičeních, případně můžete použít skripta Martina Mareše - strana 361.

21.11. (do 5.12.)

Cvičení odpadá

28.11. (do 12.12.)

Modifikujte sčítací síť, aby odčítala.
Navrhněte síť, která bude násobit. Můžete použít sčítačku logaritmické hloubky z hodiny. Snažte se alespoň o čas O(log^2(n)). Lze udělat i v čase O(log n)
Sestrojte hradlovou síť, která dostane matici sousednosti neorientovaného grafu a rozhodne, zda je graf souvislý.

5.12. (do 19.12.)

Z následujících vektorů si vyberte libovolné dva a spočítejte jejich DFT. Správné řešení příkladu z hodiny naleznete zde. Můžete předpokládat, že délka vektoru je sudá. "w" značí primitivní n-tou odmocninu z jedné.
- (1,-1,1,-1,1,...)
- (1,0,1,0,1,0,...)
- (x,x,x,x,...)
- (w^0,w^1,w^2,w^3,...)
- (w^0,w^2,w^4,w^6,...)
O jakých vlastnostech vektoru vypovídá 0-tý a (n/2)-tý prvek jeho Fourierova obrazu?
Nalezněte pro každé j vektor, jehož obraz má na j-tém místě 1 a všude jinde 0.

12.12. (do 2.1.)

Navrhněte algoritmus pro výpočet obsahu nekonvexního mnohoúhelníku. Lze udělat v O(n), ale stačí mi i O(n^2).
Vymyslete datovou strukturu, která bude udržovat konvexní obal množiny bodů a bude ho umět rychle přepočítat po přidání nového bodu do množiny. Nezapomeňte uvést časovou a prostorovou složitost.
Je dána množina obdélníků, jejichž hrany jsou rovnoběžné s osami souřadnic. Spočítejte obsah jejich sjednocení.

19.12. (do 9.1.)

Následující problémy jsou NP-úplné. Vyberte si nějakou dvojici a převeďte jeden na druhý. Neberu převody, které jsme si ukazovali na hodině (barvení <-> klika, SAT -> klika, nezávislá množina <-> klika) nebo jsou triviální (3-SAT -> SAT): SAT, 3-SAT, 3,3-SAT, Nezávislá množina, Klika, Barvení grafu, Hamiltonovská cesta/kružnice, Batoh, Batoh s cenami, Dva loupežníci.
Pomocí SAT nalezněte nejdelší cestu v grafu, pokud víte, že má délku K.

9.1. (do 23.1.)

Problém E3,E3-SAT je dalším zesílením 3,3-SATu. Chceme zjistit splnitelnost formule v CNF, jejíž každá klauzule obsahuje právě tři různé proměnné a každá proměnná se nachází v právě třech klauzulích. Ukažte, že tento problém lze řešit efektivně z toho prostého důvodu, že každá taková formule je splnitelná.
Hledejme vrcholové pokrytí následujícím hladovým algoritmem. V každém kroku vybereme vrchol nejvyššího stupně, přidáme ho do pokrytí a odstraníme ho z grafu i se všemi již pokrytými hranami. Je nalezené pokrytí nejmenší? Nebo alespoň O(1)-aproximace nejmenšího?