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

Cvičení se koná ve středu v 12:20 v S7.

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

Zápočet získáte za odevzdání dvou časově omezených úkolů a vypracování zápočtové práce. Ta by měla obsahovat popis některého zajímavého a netriviálního algoritmu, ať už z přednášky nebo odjinud. Takový text by měl obsahovat to, jak algoritmus funguje, proč funguje a jakou má časovou a paměťovou složitost. Co přesně musíte udělat:

V termínu odevzdat první a druhý domácí úkol. Úkoly budou oznámeny na cvičení a na webových stránkách alespon s měsíčním předstihem.
Domluvit se se mnou do konce semestru, tj. do 16. 1. 2011 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. Jedno téma je nanejvýš pro 3 lidi, aby se témata moc neopakovala.
Poslat mi zápočťák. Většinou po krátké iteraci dostanete zápočet, ale mohu požadovat i osobní předvedení.

Témata by se neměla moc opakovat, takže jedno téma povoluji nanejvýš třem lidem.

Seznam domácích úkolů

Domácí úkoly se odevzdávají v CodExu, ve skupině I-ADS2 (ZS, Streda). Do této skupiny vás mohu přiřadit jenom já, takže mi napiště email, až se zeregistrujete do CodExu. Úkoly řešte jednotlivě, takže neodevzdávejte cizí řešení, protože je budu ručně kontrolovat. Pokud na nějaké zkopírované narazím, nikomu z účastníků nedám zápočet.

První domácí úkol je úloha Debordelizace. Musíte ji odevzdat do 30. listopadu 23:59. Pro uznání úkolu musíte získat 100 ze 100 bodů (tj. na všech deset z deseti testovacích vstupů odpovíte správně). Pokud chcete svůj program testovat sami, zde si můžete stáhnout ukázková data. Tato data jsou přesně tak velká, jako ostrá testovací data, ale nejsou samozřejmě stejná. Časový limit v CodExu je 1s na každý vstup, paměťový je 64MB. Časový limit je 10-krát víc než nejlepší řešení v C++ a více než 2-krát více než nejlepší řešení v C#.
Druhý domácí úkol je úloha Taneční seance. Musíte ji odevzdat do 22. prosince 23:59. Pro uznání úkolu musíte získat 100 ze 100 bodů (tj. na všech deset z deseti testovacích vstupů odpovíte správně). Pokud chcete svůj program testovat sami, zde si můžete stáhnout ukázková data. Tato data jsou přesně tak velká, jako ostrá testovací data, ale nejsou samozřejmě stejná. Časové limity v CodExu jsou 1s 1s 1s 1s 2s 3s 4s 4s 5s 5s, paměťový limit je 64MB.

Načítání vstupu v C# v CodExu

Pro načítení vstupu v C#, který se skládá z mnoha čísel, je vhodné použít třídu Reader.cs. Tu najdete v CodExu v sekci 'Uvítací stránka'. V CodExu je váš program s touto třídou kompilován automaticky, stačí přidat

using
  CodEx

, doma ji musíte přikompilovávat ručně. Pomocí ní můžete načíst další číslo ze standardního vstupu jako Reader.Console().Int(). Kromě čísel jde načítat ještě Char, Double, Word a Line.

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

Obsah cvičení (12. 01. 2011)

Datum Obsah
29. září 2010 Cvičení odpadá.
6. října 2010 Organizační povídání, opakování
Řešené příklady:
Jak setřídit posloupnost N obecných prvků? [Ο(N²), Ο(N log N)]
Jak setřídit posloupnost čísel 1..H? [Ο(N+H)]
Jak setřídit posloupnost čísel 0..2³²-1 [3*O(N+2¹¹), Ο(2¹¹) paměti]
Jak setřídit posloupnost, kde je každý prvek nejvýš o K míst mimo od své výsledné pozice? [Ο(N log K) haldou či tříděním po blocích]

14. října 2010 Řešené příklady:
Jak setřídit posloupnost, kde je každý prvek nejvýš o K míst mimo od své výsledné pozice a K neznáme? [Ο(N log K) umocňováním K]
Nejkratší cesta v neohodnoceném grafu [Ο(N+M)]
Nejkratší cesta v ohodnoceném grafu [Ο(N²), Ο(M log N), Ο(M + N log N)]
Nejkratší cesta v grafu ohodnoceným celými čísly 1..K [Ο(K(N+M)), Ο(NK+M)]
Nejkratší cesta v acyklickém grafu [Ο(N+M)].

20. října 2010 Řešené příklady:
Jak nalézt nejdelší opakující se podslovo ve slově délky N [Ο(N²) pomocí trie suffixů nebo posunu podslov, Ο(N) pomocí suffixových stromů, Ο(N log N) pomocí hashování a binárního hledání délky opakujícího se podslova]
Jaké hashování zvolit, když je výhodné umět rychle upravovat hash hodnotu pro přidání písmenka na konec slova nebo odebrání písmenka ze začátku.
V daném textu délky N vymažte všechny výskyty daného slova. Pozor na to, že smazáním jednoho výskytu mohou vzniknout výskyty jiné. [Ο(N)]

27. října 2010 Záskok odcvičil Martin Böhm, díky!
Řešené příklady:
Je dané slovo rovno nějaké své netriviální rotaci? [Ο(N)]
Dostanete seznam slov. Pro každé slovo z něj zjistěte, kolikrát se vyskytuje v daném textu. [Ο(délka seznamu slov + délka textu)]
Dostanete slova o celkové délce P písmen z abecedy velikosti A. Setřiďte tato slova, jak nejrychleji dokážete. [Ο(P + A)]

3. listopadu 2010 Řešené příklady:
Najděte cestu věží na šachovnici s vykouslými protilehlými rohy.
Najděte pokrytí šachovnice dominovými kostkami 2x1, přičemž některá políčka šachovnice mohou být vykousnutá. [Ο(N³)]
Ukažte složitost Dinice [Ο(N² M)]
Dokažte, že pro grafy s jednotkovými kapacitami trvá Dinic Ο(N M).
Dokažte, že pro grafy s jednotkovými kapacitami, které navíc splňují, že každý vrchol má vstupní nebo výstupní stupeň nejvýše jedna, trvá Dinic jenom Ο(√N M). [Ukažte, že po √N iteracích následuje už nanejvýš dalších √N iterací.]

10. listopadu 2010 Řešené příklady:
Na šachovnici o rozměrech NxN jsou některá políčka zakázaná. Rozmistěte na ni co nejvíc věží, aby se navzájem neohrožovaly. Pokud se věže vidí jenom skrz zakázané políčko, neohrožují se. [Ο(N³)]
Naimplementujte Goldbergův algoritmus, aby běžel v čase Ο(N²√M).
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ů.

17. listopadu 2010 Státní svátek
24. listopadu 2010 Řešené příklady:
Zopakujte si definici Fourierovy transformace, ukažte, že je lineární a má inverzi.
Dokažte, že výsledek Fourierovy transformace reálných čísel je antisymetrický, tj. že y_i = y_n-i.
Pomocí Fourierovy transformace navrhněte algoritmus rychlého násobení polynomů [Ο(N log N)].
Pomocí Fourierovy transofrmace navrhněte algoritmus pro spektrální analýzu zvuku, tj. rozklad daného vzorku na několik sinusovek, jejichž složením vzorek vznikl.

1. prosince 2010 Řešené příklady:
Převod automatu Aho-Corrasickové na konečný automat bez zpětné funkce.
Implementace rychlé fourierovy transformace nejprve rekurzivně, potom iterativně v jednom poli [Ο(N log N)]
Rekurzivní algoritmus násobení čísel a polynomů, který převede násobení dvou n-bitových čísel na tři násobení tří n/2-bitových čísel [Ο(N^{log₂ 3})]

8. prosince 2010 Komparátorové sítě
Řešené příklady:
Vytvořte sít, která hledá minimum daných prvků [Ο(log N) hladin].
Vytvořte sít, která zatřídí prvek do setříděné posloupnosti [Ο(log N) hladin].
Popište bitonické třídění.
Popište Batcherovo třídění.

15. prosince 2010 Hradlové sítě
Řešené příklady:
Zkonstruujte XOR pomocí čtyř NANDů.
Popište carry-lookahead sčítačku.
Popište násobičku s Ο(log N) vrstvami.
Vytvořte síť počítající zbytek daného čísla po dělení 7.

22. prosince 2010 Řešené příklady:
Výpočet konvexního obalu v čase Ο(N log N) a Ο(N K), kde K je velikost výsledného obalu.
Ukažte, že nalézt konvexní obal nelze rychleji než setřídit souřadnice daných bodů.
Popište Fortunův algoritmus na nalezení Voroneho diagramu.

5. ledna 2010 NP úplnost a převody
Řešené příklady:
Definice jazyka, TS, P, NTS, NP, NP-těžký problém, NP-úplný problém.
Ekvivalence certifikátové definice NP a definice pomocí NTS.
Definice třídy coNP, problém TAUT.
Definice tříd RP, coRP, ZPP, BPP, PP.

12. ledna 2010 Asymetrické šifrování, RSA a testy prvočíselnosti
Řešené příklady:
Popište veřejný a soukromý klíč RSA a dokažte, že RSA funguje.
Ukažte, že pokud pošlete stejnou zprávu e příjemcům s veřejnými klíči s exponentem e, je jednoduché dešifrovat poslanou zprávu.
Popište Fermatův test prvočíselnosti.
Popište Rabin-Millerův test prvočíselnosti.

Datum	Obsah
29. září 2010	Cvičení odpadá.
6. října 2010	Organizační povídání, opakování Řešené příklady: Jak setřídit posloupnost N obecných prvků? [Ο(N²), Ο(N log N)] Jak setřídit posloupnost čísel 1..H? [Ο(N+H)] Jak setřídit posloupnost čísel 0..2³²-1 [3O(N+2¹¹), Ο(2¹¹)* paměti] Jak setřídit posloupnost, kde je každý prvek nejvýš o K míst mimo od své výsledné pozice? [Ο(N log K) haldou či tříděním po blocích]
14. října 2010	Řešené příklady: Jak setřídit posloupnost, kde je každý prvek nejvýš o K míst mimo od své výsledné pozice a K neznáme? [Ο(N log K) umocňováním K] Nejkratší cesta v neohodnoceném grafu [Ο(N+M)] Nejkratší cesta v ohodnoceném grafu [Ο(N²), Ο(M log N), Ο(M + N log N)] Nejkratší cesta v grafu ohodnoceným celými čísly 1..K [Ο(K(N+M)), Ο(NK+M)] Nejkratší cesta v acyklickém grafu [Ο(N+M)].
20. října 2010	Řešené příklady: Jak nalézt nejdelší opakující se podslovo ve slově délky N [Ο(N²) pomocí trie suffixů nebo posunu podslov, Ο(N) pomocí suffixových stromů, Ο(N log N) pomocí hashování a binárního hledání délky opakujícího se podslova] Jaké hashování zvolit, když je výhodné umět rychle upravovat hash hodnotu pro přidání písmenka na konec slova nebo odebrání písmenka ze začátku. V daném textu délky N vymažte všechny výskyty daného slova. Pozor na to, že smazáním jednoho výskytu mohou vzniknout výskyty jiné. [Ο(N)]
27. října 2010	Záskok odcvičil Martin Böhm, díky! Řešené příklady: Je dané slovo rovno nějaké své netriviální rotaci? [Ο(N)] Dostanete seznam slov. Pro každé slovo z něj zjistěte, kolikrát se vyskytuje v daném textu. [Ο(délka seznamu slov + délka textu)] Dostanete slova o celkové délce P písmen z abecedy velikosti A. Setřiďte tato slova, jak nejrychleji dokážete. [Ο(P + A)]
3. listopadu 2010	Řešené příklady: Najděte cestu věží na šachovnici s vykouslými protilehlými rohy. Najděte pokrytí šachovnice dominovými kostkami 2x1, přičemž některá políčka šachovnice mohou být vykousnutá. [Ο(N³)] Ukažte složitost Dinice [Ο(N² M)] Dokažte, že pro grafy s jednotkovými kapacitami trvá Dinic Ο(N M). Dokažte, že pro grafy s jednotkovými kapacitami, které navíc splňují, že každý vrchol má vstupní nebo výstupní stupeň nejvýše jedna, trvá Dinic jenom Ο(√N M). [Ukažte, že po √N iteracích následuje už nanejvýš dalších √N iterací.]
10. listopadu 2010	Řešené příklady: Na šachovnici o rozměrech NxN jsou některá políčka zakázaná. Rozmistěte na ni co nejvíc věží, aby se navzájem neohrožovaly. Pokud se věže vidí jenom skrz zakázané políčko, neohrožují se. [Ο(N³)] Naimplementujte Goldbergův algoritmus, aby běžel v čase Ο(N²√M). 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ů.
17. listopadu 2010	Státní svátek
24. listopadu 2010	Řešené příklady: Zopakujte si definici Fourierovy transformace, ukažte, že je lineární a má inverzi. Dokažte, že výsledek Fourierovy transformace reálných čísel je antisymetrický, tj. že y_i = y_n-i. Pomocí Fourierovy transformace navrhněte algoritmus rychlého násobení polynomů [Ο(N log N)]. Pomocí Fourierovy transofrmace navrhněte algoritmus pro spektrální analýzu zvuku, tj. rozklad daného vzorku na několik sinusovek, jejichž složením vzorek vznikl.
1. prosince 2010	Řešené příklady: Převod automatu Aho-Corrasickové na konečný automat bez zpětné funkce. Implementace rychlé fourierovy transformace nejprve rekurzivně, potom iterativně v jednom poli [Ο(N log N)] Rekurzivní algoritmus násobení čísel a polynomů, který převede násobení dvou n-bitových čísel na tři násobení tří n/2-bitových čísel [Ο(N^{log₂ 3})]
8. prosince 2010	Komparátorové sítě Řešené příklady: Vytvořte sít, která hledá minimum daných prvků [Ο(log N) hladin]. Vytvořte sít, která zatřídí prvek do setříděné posloupnosti [Ο(log N) hladin]. Popište bitonické třídění. Popište Batcherovo třídění.
15. prosince 2010	Hradlové sítě Řešené příklady: Zkonstruujte XOR pomocí čtyř NANDů. Popište carry-lookahead sčítačku. Popište násobičku s Ο(log N) vrstvami. Vytvořte síť počítající zbytek daného čísla po dělení 7.
22. prosince 2010	Řešené příklady: Výpočet konvexního obalu v čase Ο(N log N) a Ο(N K), kde K je velikost výsledného obalu. Ukažte, že nalézt konvexní obal nelze rychleji než setřídit souřadnice daných bodů. Popište Fortunův algoritmus na nalezení Voroneho diagramu.
5. ledna 2010	NP úplnost a převody Řešené příklady: Definice jazyka, TS, P, NTS, NP, NP-těžký problém, NP-úplný problém. Ekvivalence certifikátové definice NP a definice pomocí NTS. Definice třídy coNP, problém TAUT. Definice tříd RP, coRP, ZPP, BPP, PP.
12. ledna 2010	Asymetrické šifrování, RSA a testy prvočíselnosti Řešené příklady: Popište veřejný a soukromý klíč RSA a dokažte, že RSA funguje. Ukažte, že pokud pošlete stejnou zprávu e příjemcům s veřejnými klíči s exponentem e, je jednoduché dešifrovat poslanou zprávu. Popište Fermatův test prvočíselnosti. Popište Rabin-Millerův test prvočíselnosti.

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

Výsledky úkolů se aktualizují z CodExu jednou nočně.

Jméno Úkol 1 Úkol 2 Specifikace Zápočťák Zápočet

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

Zpět