Cvičení z algoritmů a datových struktur, TIN061

Cvičení se koná v pátek v 9:00 na Malé Straně v S6.

Podmínky k získání zápočtu

Zápočet získáte za vypracování zápočtové práce. Ta by měla obsahovat implementaci některého zajímavého a netriviálního algoritmu, ať už z přednášky nebo odjinud, a dokumentaci. Dokumentace je popis toho, jak algoritmus nebo implementace funguje, proč funguje a jakou má časovou a paměťovou složitost. Co přesně musíte udělat:

Poslat do Vánoc mail, že budete chtít zápočet. (Objevíte se v seznamu.)
Domluvit se se mnou do konce semestru, tj. do 18. 1. 2009 mailem na tématu zápočtové práce. Inspirace například v seznamu Martina Mareše. Pokud jsme nějaké téma dopodrobna rozebrali na cvičení, tak se mi nejspíš nebude líbit.
Vytvořit zápočtové práce včetně dokumentace.
Poslat mi hotový zápočťák a domluvit se na termínu osobního předvedení.

Kromě předchozího seznamu je velmi vhodná aktivní účast na cvičení (když si vás budu pamatovat, tak nejspíš nemusíte dělat neudělatenou práci a tak :–).

Seznam přidělených zápočtových prací.

Obsah cvičení (03. 11. 2010)

Datum Obsah
3. říjen 2008
Řešené příklady:
Různé varianty hledání nejkratší cesty v ohodnocených grafech s nezápornými hranami pro M=Θ(N²) [Ο(M)], M=Θ(N^1+ε) [Ο(M)], M=Θ(N) [Ο(N log N)], pro acyklický graf [Ο(M+N)] a pro ohodnocení hran malými celými čísly 1..k [Ο(M+KN), Ο(log K * (M + N)].
Třídění skoro setříděné posloupnosti. Nejprve je každý prvek nejvýš o k pozic mimo svojí pozici v setříděné posloupnosti a k známe [Ο(N log k)], poté k neznáme [Ο(N log k)] a nakonec hledáme algoritmus se složitostí Ο(N log (počet inverzí / N)).
Na rozmyšlenou bylo najít co nejlepší řešení následujícího problému: Dostanete N čísel a₁ až a_N a musíte umět odpovídat na dotazy "pro dané i a j najděte mezi čísly a_i až a_j nejmenší". Zmínili jsme triviální řešení s Ο(1) předzpracováním + Ο(N) na dotaz a další triviální řešení s Ο(N²) předzpracováním + Ο(1) na dotaz.
10. říjen 2008
Řešené příklady:
Minule zadaný příklad jsme vyřešili s Ο(N log N) předzpracováním a Ο(1) na dotaz, a také s Ο(N) předzpracováním a Ο(log N) dotazem.
Máte dvě setříděná pole délek N≥M. Vaším cílem je najít medián posloupnosti, která vznikne sjednocením prvků těchto polí [Ο(log N)].
Pro slovo délky N najděte jeho nejdelší podslovo (souvislá podposloupnost), které je palindromické [Ο(N)].
Pro řetězec délky N najděte co nejdelší opakující se podslovo (tato podslova se mohou překrývat) [Ο(N log N) v průměru].
Na rozmyšlenou: pro slovo délky N najít jeho lexikograficky minimální rotaci.
17. říjen 2008 Kvůli neúčasti cvičícího bude cvičení spojené s cvičením, které vede Honza Hubička. Toto cvičení se koná ve stejný čas v S9.
24. října 2008
Řešené příklady:
Pro dané slovo zjistěte, zda je rovno nějaké svojí netriviální rotaci [Ο(N)].
Pro slovo délky N najděte jeho minimální lexikografickou rotaci [Ο(N)].
Dostanete zakázané slovo délky P, dále text délky N a vaším úkolem je z tohoto textu smazat všechny výskyty zakázaného slova [Ο(N)].
Stejně jako v poslední úloze, ale zakázaných slov máte několik, přičemž P je součet jejich délek. Pozor, tato úloha není jen triviální rozšíření předchozí! [Ο(AN) kde A je počet písmen abecedy]
Dostanete N slov o celkovém počtu P písmen. Vaším úkolem je tato slova setřídit v čase Ο(P+A), kde A je počet písmen abecedy.
31. října 2008
Řešené příklady:
Hradlové sítě s NANDy umí vytvořit všechny boolovské funkce.
Vytvořte XOR na co nejméně NANDů [jdou 4].
Spočtěte OR pro N vstupů [log N vrstev] a dokažte, že to rychleji nejde.
Zopakujte si sčítačku na 2log N vrstev z přednášky.
Vymyslete násobičku [Ο(log² N) vrstev].
Zkuste vymyslet (normální, ne pro hradlovou síť) algoritmus pro násobení dvou N-bitových čísel v čase lepším než Ο(N²).
7. listopadu 2008
Řešené příklady:
Máte následující protokol: A dostane náhodně obarvenou "šachovnici". Musí změnit barvu právě jednoho políčka a poslat šachovnici B, se kterým může mít předem domluvený protokol. Vaším cílem je tímto způsobem přenést co nejvíc bitů informace od A k B [jde víc než 2].
Máte čísla x₁, ..., x_n. Vaším úkolem je spočítat hodnoty z_i = x₁ x₂ ... x_i-1 x_i+1 ... x_n v pořadí z₁, z₂, ..., z_n. Buď šetřte čas i paměť [Ο(N) čas, Ο(√N) paměť] nebo hlavně paměť [Ο(N log N) čas, Ο(log N) paměť].
Vymyslete hradlovou síť, která bude počítat zbytek binárně zadaného čísla po dělení 3 (a rozmyslete, co se změní pro zbytek po dělení 5).
14. listopadu 2008
Řešené příklady:
Vymyslete komparátorovou síť pro nalezení minimálního prvku.
Sestrojte komparátorovou síť, která do setříděné posloupnosti zatřídí daný prvek.
Pro danou permutaci sestrojte komparátorovou síť, která ji setřídí. Použijte Ο(log N) vrstev a Ο(N) komarátorů.
Dokažte, že pokud hradlová síť setřídí správně všechny posloupnosti nul a jedniček, tak setřídí správně každý vstup.
21. listopadu 2008
Řešené příklady:
Pro nějaké korektní rozmístění disků na Hanojských věžích rozhodněte, v kolika nejméně krocích je dokážete přemístit na libovolný kolík.
Vymyslete nějaký druh merge v komparátorové síti, nejlépe s Ο(log N) vrstvami. Pomocí něj navrhněte třídění v Ο(log² N) vrstvách.
Určete složitost FF na grafu s jednotkovými kapacitami.
Vyřešte problém maximálního párování v bipartitním grafu pomocí toků v síti.
Dostanete šachovnici se zakázanými políčky. Vaším úkolem je umístit na ni co nejvíc dominových kostek (2x1), aby se nepřekrývaly.
Dostanete opět šachovnici se zakázanými políčky. Vaším úkolem je umístit na ni co nejvíce věží, aby se neohrožovaly.
5. prosince 2009
Řešené příklady:
Určete složitost Dinicova algoritmu v obecném případě [Ο(N²M)].
Určete složitost Dinicova algoritmu pro grafy s jednotkovými kapacitami [Ο(NM)].
Určete složitost Dinicova algoritmu pro grafy s jednotkovými kapacitami, které mají vstupní nebo výstupní stupeň každého vrcholu roven jedné [Ο(√NM)].
Vyřešte problém vrcholového pokrytí v biparnitním grafu [jeho velikost je přesně rovna velikosti maximálního párování, ukažte navíc, jak lze z maximálního párování získat vrcholové pokrytí, a ukažte, že jeho doplňek je nezávislá množina].
12. prosince 2009 Zabývali jsme se příkladem na minimální řez. Poté jsme zadefinovali transformace DFT a IDFT a ukázali její význam jako počítání hodnot daného polynomu v bodech (ω⁰,ω¹,...,ω^n-1).
Řešené příklady:
Máte N projektů, za vyřešení každého dostanete sumu c_i. Dále máte M zdrojů, každý vás stojí r_j. Na každý projekt i potřebujete nějakou podmnožinu zdrojů s_i₁,...,s_{i_k}. Pokud zakoupíte nějaký zdroj, tak ho můžete použít ve všech projektech. Rozhodněte, jaké projekty vybrat a jaké zdroje zakoupit, abyste pro vybrané projekty měli všechny zdroje a abyste maximalizovali zist, tj. sumu zisků vybraných projektů - sumu cen vybraných zdrojů.
Spočítejte DFT obraz vektorů (ω^jk)_j=0..n-1 pro libovolné k [(δ_j,n-k)_j=0..n-1].
Násobení polynomů a čísel pomocí DFT, zatím bez určení časové složitosti.
19. prosince 2009 Bavili jsme se o algoritmu FFT a IFFT a ukazovali rekurzivní implementaci a implementaci bez rekurze s obracením bitů.
Řešené příklady:
Vynásobte dva polynomy stupně N v čase Ο(N log N).
Vynásobte dvě čísla o N bitech v čase Ο(N log² N), v čase Ο(N log N (loglog N)²), v čase Ο(N log N loglog N (logloglog N)²), a na RAMu v čase Ο(N log N).
Spočtěte DFT obraz vektorů (cos(2πjk/n))_j=0..n-1 pro k < n/2 [(δ_j,k/2+δ_j,n-k/2)_j=0..n-1].
Spočtěte DFT obraz vektorů (sin(2πjk/n))_j=0..n-1 pro k < n/2 [(iδ_j,k/2-iδ_j,n-k/2)_j=0..n-1].
DFT obraz reálného vektoru je antisymetrický (y_k = konjugace y_n-k).
DFT obraz antisymetrického vektoru je reálný.
"Upravte" DFT pomocí dvou předchozích případů, aby fungovala z Rⁿ do Rⁿ.
9. ledna 2009 Promysleli jsme si definici P a NP přes Turingovy stroje, dále ekvivalentní definici NP přes certifikáty, zadefinovali jsme redukování a NP-těžké a NP-úplné problémy.
Řešené příklady:
Kachlíčkování je NP-úplný problém.
Převeďte kachlíčkování na SAT.
Převeďte SAT na 3-SAT a 3,3-SAT.
Ukažte, že E3,E3-SAT má vždy řešení.
Převeďte nezávislou množinu na kliku a na vrcholové pokrytí.
Rozmyslete si, že dvojbarevnost, 2-SAT, Horn-SAT, a (nezávislá množina, klika, vrchlové pokrytí) v bipartitním grafu jdou řešit v P.

Datum	Obsah
3. říjen 2008	Řešené příklady: Různé varianty hledání nejkratší cesty v ohodnocených grafech s nezápornými hranami pro M=Θ(N²) [Ο(M)], M=Θ(N^1+ε) [Ο(M)], M=Θ(N) [Ο(N log N)], pro acyklický graf [Ο(M+N)] a pro ohodnocení hran malými celými čísly 1..k [Ο(M+KN), Ο(log K (M + N)]. Třídění skoro setříděné* posloupnosti. Nejprve je každý prvek nejvýš o k pozic mimo svojí pozici v setříděné posloupnosti a k známe [Ο(N log k)], poté k neznáme [Ο(N log k)] a nakonec hledáme algoritmus se složitostí Ο(N log (počet inverzí / N)). Na rozmyšlenou bylo najít co nejlepší řešení následujícího problému: Dostanete N čísel a₁ až a_N a musíte umět odpovídat na dotazy "pro dané i a j najděte mezi čísly a_i až a_j nejmenší". Zmínili jsme triviální řešení s Ο(1) předzpracováním + Ο(N) na dotaz a další triviální řešení s Ο(N²) předzpracováním + Ο(1) na dotaz.
10. říjen 2008	Řešené příklady: Minule zadaný příklad jsme vyřešili s Ο(N log N) předzpracováním a Ο(1) na dotaz, a také s Ο(N) předzpracováním a Ο(log N) dotazem. Máte dvě setříděná pole délek N≥M. Vaším cílem je najít medián posloupnosti, která vznikne sjednocením prvků těchto polí [Ο(log N)]. Pro slovo délky N najděte jeho nejdelší podslovo (souvislá podposloupnost), které je palindromické [Ο(N)]. Pro řetězec délky N najděte co nejdelší opakující se podslovo (tato podslova se mohou překrývat) [Ο(N log N) v průměru]. Na rozmyšlenou: pro slovo délky N najít jeho lexikograficky minimální rotaci.
17. říjen 2008	Kvůli neúčasti cvičícího bude cvičení spojené s cvičením, které vede Honza Hubička. Toto cvičení se koná ve stejný čas v S9.
24. října 2008	Řešené příklady: Pro dané slovo zjistěte, zda je rovno nějaké svojí netriviální rotaci [Ο(N)]. Pro slovo délky N najděte jeho minimální lexikografickou rotaci [Ο(N)]. Dostanete zakázané slovo délky P, dále text délky N a vaším úkolem je z tohoto textu smazat všechny výskyty zakázaného slova [Ο(N)]. Stejně jako v poslední úloze, ale zakázaných slov máte několik, přičemž P je součet jejich délek. Pozor, tato úloha není jen triviální rozšíření předchozí! [Ο(AN) kde A je počet písmen abecedy] Dostanete N slov o celkovém počtu P písmen. Vaším úkolem je tato slova setřídit v čase Ο(P+A), kde A je počet písmen abecedy.
31. října 2008	Řešené příklady: Hradlové sítě s NANDy umí vytvořit všechny boolovské funkce. Vytvořte XOR na co nejméně NANDů [jdou 4]. Spočtěte OR pro N vstupů [log N vrstev] a dokažte, že to rychleji nejde. Zopakujte si sčítačku na 2log N vrstev z přednášky. Vymyslete násobičku [Ο(log² N) vrstev]. Zkuste vymyslet (normální, ne pro hradlovou síť) algoritmus pro násobení dvou N-bitových čísel v čase lepším než Ο(N²).
7. listopadu 2008	Řešené příklady: Máte následující protokol: A dostane náhodně obarvenou "šachovnici". Musí změnit barvu právě jednoho políčka a poslat šachovnici B, se kterým může mít předem domluvený protokol. Vaším cílem je tímto způsobem přenést co nejvíc bitů informace od A k B [jde víc než 2]. Máte čísla x₁, ..., x_n. Vaším úkolem je spočítat hodnoty z_i = x₁ x₂ ... x_i-1 x_i+1 ... x_n v pořadí z₁, z₂, ..., z_n. Buď šetřte čas i paměť [Ο(N) čas, Ο(√N) paměť] nebo hlavně paměť [Ο(N log N) čas, Ο(log N) paměť]. Vymyslete hradlovou síť, která bude počítat zbytek binárně zadaného čísla po dělení 3 (a rozmyslete, co se změní pro zbytek po dělení 5).
14. listopadu 2008	Řešené příklady: Vymyslete komparátorovou síť pro nalezení minimálního prvku. Sestrojte komparátorovou síť, která do setříděné posloupnosti zatřídí daný prvek. Pro danou permutaci sestrojte komparátorovou síť, která ji setřídí. Použijte Ο(log N) vrstev a Ο(N) komarátorů. Dokažte, že pokud hradlová síť setřídí správně všechny posloupnosti nul a jedniček, tak setřídí správně každý vstup.
21. listopadu 2008	Řešené příklady: Pro nějaké korektní rozmístění disků na Hanojských věžích rozhodněte, v kolika nejméně krocích je dokážete přemístit na libovolný kolík. Vymyslete nějaký druh merge v komparátorové síti, nejlépe s Ο(log N) vrstvami. Pomocí něj navrhněte třídění v Ο(log² N) vrstvách. Určete složitost FF na grafu s jednotkovými kapacitami. Vyřešte problém maximálního párování v bipartitním grafu pomocí toků v síti. Dostanete šachovnici se zakázanými políčky. Vaším úkolem je umístit na ni co nejvíc dominových kostek (2x1), aby se nepřekrývaly. Dostanete opět šachovnici se zakázanými políčky. Vaším úkolem je umístit na ni co nejvíce věží, aby se neohrožovaly.
5. prosince 2009	Řešené příklady: Určete složitost Dinicova algoritmu v obecném případě [Ο(N²M)]. Určete složitost Dinicova algoritmu pro grafy s jednotkovými kapacitami [Ο(NM)]. Určete složitost Dinicova algoritmu pro grafy s jednotkovými kapacitami, které mají vstupní nebo výstupní stupeň každého vrcholu roven jedné [Ο(√NM)]. Vyřešte problém vrcholového pokrytí v biparnitním grafu [jeho velikost je přesně rovna velikosti maximálního párování, ukažte navíc, jak lze z maximálního párování získat vrcholové pokrytí, a ukažte, že jeho doplňek je nezávislá množina].
12. prosince 2009	Zabývali jsme se příkladem na minimální řez. Poté jsme zadefinovali transformace DFT a IDFT a ukázali její význam jako počítání hodnot daného polynomu v bodech (ω⁰,ω¹,...,ω^n-1). Řešené příklady: Máte N projektů, za vyřešení každého dostanete sumu c_i. Dále máte M zdrojů, každý vás stojí r_j. Na každý projekt i potřebujete nějakou podmnožinu zdrojů s_i₁,...,s_{i_k}. Pokud zakoupíte nějaký zdroj, tak ho můžete použít ve všech projektech. Rozhodněte, jaké projekty vybrat a jaké zdroje zakoupit, abyste pro vybrané projekty měli všechny zdroje a abyste maximalizovali zist, tj. sumu zisků vybraných projektů - sumu cen vybraných zdrojů. Spočítejte DFT obraz vektorů (ω^jk)_j=0..n-1 pro libovolné k [(δ_j,n-k)_j=0..n-1]. Násobení polynomů a čísel pomocí DFT, zatím bez určení časové složitosti.
19. prosince 2009	Bavili jsme se o algoritmu FFT a IFFT a ukazovali rekurzivní implementaci a implementaci bez rekurze s obracením bitů. Řešené příklady: Vynásobte dva polynomy stupně N v čase Ο(N log N). Vynásobte dvě čísla o N bitech v čase Ο(N log² N), v čase Ο(N log N (loglog N)²), v čase Ο(N log N loglog N (logloglog N)²), a na RAMu v čase Ο(N log N). Spočtěte DFT obraz vektorů (cos(2πjk/n))_j=0..n-1 pro k < n/2 [(δ_j,k/2+δ_j,n-k/2)_j=0..n-1]. Spočtěte DFT obraz vektorů (sin(2πjk/n))_j=0..n-1 pro k < n/2 [(iδ_j,k/2-iδ_j,n-k/2)_j=0..n-1]. DFT obraz reálného vektoru je antisymetrický (y_k = konjugace y_n-k). DFT obraz antisymetrického vektoru je reálný. "Upravte" DFT pomocí dvou předchozích případů, aby fungovala z Rⁿ do Rⁿ.
9. ledna 2009	Promysleli jsme si definici P a NP přes Turingovy stroje, dále ekvivalentní definici NP přes certifikáty, zadefinovali jsme redukování a NP-těžké a NP-úplné problémy. Řešené příklady: Kachlíčkování je NP-úplný problém. Převeďte kachlíčkování na SAT. Převeďte SAT na 3-SAT a 3,3-SAT. Ukažte, že E3,E3-SAT má vždy řešení. Převeďte nezávislou množinu na kliku a na vrcholové pokrytí. Rozmyslete si, že dvojbarevnost, 2-SAT, Horn-SAT, a (nezávislá množina, klika, vrchlové pokrytí) v bipartitním grafu jdou řešit v P.

Zápočtové práce (25. 05. 2018)

Jméno Specifikace Zápočet

Pokud byste něco potřebovali, napište mi na fox {zavináč} ucw {tečka} cz.

Zpět