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:
  1. Poslat do Vánoc mail, že budete chtít zápočet. (Objevíte se v seznamu.)
  2. 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.
  3. Vytvořit zápočtové práce včetně dokumentace.
  4. 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)

DatumObsah
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=Θ(N2) [Ο(M)], M=Θ(N1+ε) [Ο(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 a1aN a musíte umět odpovídat na dotazy "pro dané i a j najděte mezi čísly aiaj nejmenší". Zmínili jsme triviální řešení s Ο(1) předzpracováním + Ο(N) na dotaz a další triviální řešení s Ο(N2) 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 2008Kvů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 [Ο(log2 N) vrstev].
  • Zkuste vymyslet (normální, ne pro hradlovou síť) algoritmus pro násobení dvou N-bitových čísel v čase lepším než Ο(N2).
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 x1, ..., xn. Vaším úkolem je spočítat hodnoty zi = x1 x2 ... xi-1 xi+1 ... xn v pořadí z1, z2, ..., zn. 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 Ο(log2 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ě [Ο(N2M)].
  • 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 2009Zabý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 01,...,ωn-1).
Řešené příklady:
  • Máte N projektů, za vyřešení každého dostanete sumu ci. Dále máte M zdrojů, každý vás stojí rj. Na každý projekt i potřebujete nějakou podmnožinu zdrojů si1,...,sik. 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 2009Bavili 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 log2 N), v čase Ο(N log N (loglog N)2), v čase Ο(N log N loglog N (logloglog N)2), 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 [(j,k/2-iδj,n-k/2)j=0..n-1].
  • DFT obraz reálného vektoru je antisymetrický (yk = konjugace yn-k).
  • DFT obraz antisymetrického vektoru je reálný.
  • "Upravte" DFT pomocí dvou předchozích případů, aby fungovala z Rn do Rn.
9. ledna 2009Promysleli 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 (08. 09. 2009)

JménoSpecifikaceZápočet
Karel BílekSchönhage-StrassenAno
Jan BímDinicAno
Jan ČernýPalindromNe
Jakub Čapek3D obalNe
Michal DanilákPodřetězceAno
Jana DivišováRabin-MillerAno
Petr KadlečekGoldbergAno
Martin KahounHuffmanAno
Stanislav KocandaParalelní K-MeansNe
Jan KohoutPočítání výskytůAno
Jaromír NechanickýLZWAno
Ondřej OdcházelDynamický HuffmanAno
Helena PouchováCenzorAno
Šimon SotákPrůsečíkyAno
Antonin SteinhauserRSAAno
Ivan ŠtubňaNásobení dlouhých číselAno

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


Zpět