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.

DatumKódBodůZadání
4. 10. wmin10Na 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).
lib10Byla 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. okraj9Chceme pro daný řetězec najít jeho nejdelší vlastní prefix, který je zároveň suffixem.
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}.]
18. 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.
opak10/20Pro 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. ram10Naprogramujte na RAMu bublinkové třídění a stanovte jeho složitost v nejhorším případě (včetně všech konstant).
imst10Vymyslete 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. 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á.)
dinic15Vymyslete síť, na níž Dinicův algoritmus poběží řádově n2m kroků.
15. 11. fft18Spočítejte Fourierův obraz vektoru (0,1,0,1,0,1,0,1).
fft28Spočítejte Fourierův obraz vektoru (1,i,-1,-i,1,i,-1,-i).
22. 11. vyska15Bude 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.)
next10Mě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. fftr10Dokažte, že ve Fourierově obrazu reálného vektoru jsou yk a yn-k navzájem komplexně sdružená.
ftrot10Jak se změní Fourierův obraz, když vektor zrotujeme (cyklicky posuneme) o k pozic?
6. 12. xor8Vymyslete, jak složit XOR ze čtyř hradel NAND.
gen10Dokažte, že žádná jiná booleovská funkce 2 proměnných než NAND a NOR negeneruje všechny ostatní.
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.
13. 12. div510Navrhněte hradlovou síť, která otestuje, jestli je zadané n-bitové číslo dělitelné pěti.
log210Navrhněte hradlovou síť, která pro dané n-bitové číslo spočítá jeho celočíselný dvojkový logaritmus (tedy index nejvyšší jedničky).
20. 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í.)
ploty10V 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. bit10Vymyslete 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í.
rez10Př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. lineq15Dokaž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?
e3e315Nechť 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í.
pcomp8Jak 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.

Výsledky

Pokud chcete být uvedeni pod přezdívkou, nebo dokonce vůbec, dejte mi vědět.

JménoPříkladyBodů
Kateřina Altmanováwmin(8) lib(7) okraj(9) fib(12) imst(10) veze(10) ram(10) fft1(8) fft2(8) xor(8) e3e3(15)105
Jan Babušíkwmin(10) lib(7) okraj(9) fib(12) imst(10) ram(0) veze(12) pokr(12) fft1(8) fft2(8) fftr(10) div5(10)108
Jiří Bernýwmin(10) lib(7) okraj(9) fib(12) opak(10) ram(10) veze(12) pokr(12) fft1(8) fft2(0) fftr(10)100
Lukáš Březinawmin(8) lib(7) okraj(9) fib(12) opak(10) ram(10) imst(10) veze(10) pokr(12) fft1(8) xor(8)104
Kateřina Břicháčkováwmin(8) lib(7) fib(8) okraj(9) opak(20) ram(10) veze(10) fft1(8) fft2(8) xor(8) pokr(12)108
Jan Čandaxor(8) vyska(15)23
Petra Doubravováwmin(10) lib(7) okraj(9) fib(12) ram(10) pokr(12) veze(10) fft1(8) fft2(8) fftr(10) csort(10)106
Peter Dräxlerwmin(8) okraj(9) fib(12) ram(10) imst(10) veze(12)61
Tomáš Gruntorádwmin(10) okraj(9) fib(12) veze(10) pokr(12) fft1(8) fft2(8) fftr(10)79
Ondřej Hrubýwmin(10) okraj(9) imst(10) ram(10) pokr(12) fft1(8) fft2(8) xor(8) gen(10) log2(10) veze(5)100
Jakub Kopálwmin(8) lib(7) okraj(9) dinic(15) pokr(12) veze(10) next(10) fib(6) xor(8) csort(10) log2(10)105
Tereza Kotěšovcováwmin(8) okraj(9) fib(12) opak(10) ram(10) pokr(12) imst(8) veze(10) fft1(8) fft2(8) fftr(10)105
Tomáš Kremelwmin(10) lib(10) okraj(9) opak(10) ram(10) imst(10) pokr(12) dinic(15) fft1(8) veze(12)106
Karolína Kuchyňoválib(7) wmin(8) okraj(9) fib(12) opak(10) ram(10) veze(10) pokr(12) fft1(8) fft2(8) fftr(10)104
Patrícia Lakatošoválib(7) wmin(8) okraj(9) fib(12) opak(10) ram(10) imst(10) veze(12) pokr(12) fft1(8) fft2(8)106
Kačka Mackováwmin(10) lib(7) okraj(9) fib(12) opak(20) cens(20) ram(10) imst(8) veze(12)108
Pavel Myšičkawmin(10) okraj(9) fib(12) ram(10) fft1(8) fft2(8) ftrot(10) fftr(10) gen(5) xor(8)90
Michal Nekvindawmin(8) lib(7) okraj(9) fib(12) opak(10) imst(10) ram(10) veze(12) pokr(12) fft1(8) fft2(8)106
Hana Pařízkoválib(10) wmin(10) okraj(9) fib(15) cens(20) opak(20) ram(10) imst(10) veze(12)116
Tomáš Pilařwmin(10) lib(7) okraj(9) fib(12) opak(10) ram(10) fft1(8) fft2(8) veze(12) fftr(10) vyska(5)101
Štěpán Procházkawmin(10) lib(10) okraj(9) opak(10) cens(20) ram(10) imst(10) fft1(8) fft2(8) ftrot(10)105
Samuel Slavkovskýwmin(8) lib(1) fib(12) okraj(9) opak(10) imst(10) dinic(0) fftr(10) fft1(0) fft2(4) log2(8) div5(1) xor(8) ploty(10)91
Vojtěch Tázlarwmin(10) lib(10) okraj(9) fib(15) cens(20) opak(20) ram(10) imst(10)104
Vikiwmin(10) lib(7) okraj(9) fib(15) cens(20) opak(15) ram(10) imst(10) pokr(12)108

Videozáznamy

Stránku spravuje Martin Mareš