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

Cvičení se koná v úterý 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 15. 1. 2012 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 dva studenty, 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í.

Seznam domácích úkolů

Domácí úkoly se odevzdávají v CodExu, ve skupině ADS2-Straka Do této skupiny vás mohu přiřadit jenom já, takže až budete mít v CodExu účet, napište mi mail, přiřadím vás do ní. Ú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 5. 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ý 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 9. ledna 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 možné 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í (13. 12. 2011)

Datum Obsah
4. října 2011 Řešené příklady:
Na středu kruhového rybníku plave kačenka a na břehu jí mlsně pozoruje kočka. Ta se pohybuje čtyřikrát rychleji než kačenka. Najděte strategii, která kačence vždy umožní dostate se na břeh rybníčku, aby se tam nepotkala s kočkou.
Funkce f(x, y) je pro x≥0, y≥0 kladná a ostře rostoucí v každé souřadnici. Dostanete hodnotu z a vaším úkolem je co nejrychleji najít všechny nezáporné dvojice x, y, že f(x, y) = z. [Ο(n log (m/n) + m log (n/m)) pro n, m minimální takové, že f(n, 0)≥z a f(0, m)≥z, a dokázali jsme, že je to i spodní odhad].
Navrhněte datovou strukturu, která podporuje operace vlož, odeber a medián. [všechny operace Ο(log N)]
Navrhněte datovou strukturu umožňující vyhledávání stránek obsahující daná klíčková slova – Google hadr :–)

11. října 2011 Cvičení odcvičil Tomáš Gavenčiak, díky!
18. října 2011 Cvičení odcvičil Tomáš Gavenčiak, díky!
25. října 2011 Cvičení odcvičil Tomáš Gavenčiak, díky!
1. listopadu 2011 Řešené příklady:
Pro dvě slova A a B najděte nejdelší souvislé společné podslovo. [pro N=součet délek A a B umíme Ο(N²) pro vyzkoušení všech posunů, Ο(N log N) pomocí hešování a Ο(N) pomocí suffixových stromů]
Dostanete text ohromné délky, smíte si ho předzpracovat. Poté chcete odpovídat na otázky obsahuje text slovo α, nejlépe v čase úměrném délce α. [vyřešili jsme pomocí suffixových stromů a suffixových polí]
Předvedli jsme si algoritmus Boyer-Moore.
V N továrnách se vyrábí jeden typ výrobku, v továrně i ho denně vyrobí t_i. M obchodů chce výrobek prodávat, obchod i ho denně potřebuje o_i. Mezi některými továrnami a obchody je možné převážet libovolné množství výrobků. Navrhněte, jak dopravovat výrobky mezi továrnami a obchody, aby se denně prodalo maximum výrobků.
Máte N projektů, za vyřešení každého dostanete sumu p_i. Dále máte M zdrojů, každý vás stojí z_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ů. [minimální řez]

8. listopadu 2011 Řešené příklady:
Máme rozehranou hokejovou ligu. Zajímá nás, jestli existuje dohrání, že zvolený tým skončí na prvním místě.
Předpokládejme, že graf křižovatek a silnic ve městě je bipartitní. Umístěte co nejméně policistů na křižovatky, aby každá ulice na alespoň jednom kraji měla policistu, který ji hlídá.
Navrhněte algoritmus, který dokáže řešit toky v síti nejen s maximálními, ale i minimálními kapacitami.

15. listopadu 2011 Řešené příklady:
Dokončení algoritmu, který řeší toky s maximálními i minimálními kapacitami.
Vyřešte problém naokrouhlování matice – dostali jsme matici s reálnými prvky. Nahraďte každý prvek jeho spodní či horní celou částí tak, aby součty řádek a sloupců byly po zaokrouhlení stejné jako v původní matici.
Vyřešte problém letecké společnosti – máte seznam L letů, které máte obsloužit. Zjistěte, kolik nejméně posádek potřebujete. Jedna posádka může obsloužit libovolně mnoho letů, jenom každý další musí začínat tam, kde končil předchozí. Těžší varianta smí v jednom letadle převážet až 3 posádky najednou.
Ukažte složitost Dinice [Ο(N² M)]
Dokažte, že pro grafy s jednotkovými kapacitami trvá Dinic Ο(N M), Ο(√M * M) a také Ο(N^2/3 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í.]
Naimplementujte Goldbergův algoritmus, aby běžel v čase Ο(N²√M).

22. listopadu 2011 Řešené příklady:
Ukažte, že v hradlové síti s hradly OR je pro spočítání OR N vstupních bitů potřeba alespoň log₂ N vrstev.
Ukažte, že libovolnou binární funkci N proměnných lze spočítat hradlovou sítí s jediným typem hradel (např. NAND či NOR) s hloubkou N. Ukažte, že hloubka N je u některých opravdu potřeba.
Navrhněte sčítačku dvou N-bitových čísel jako hradlovou síť s Ο(log N) vrstvami.
Navrhněte násobičku dvou N-bitových čísel jako hradlouvou síť s Ο(log N) vrstvami.
Vytvořte hradlovou síť, která počítá zbytek po dělení daného N-bitového čísla pěti.

29. listopadu 2011 Řešené příklady:
Dostanete N čísel a₁, ..., a_N. Vaším cílem je provést předzpracování a poté co nejrychleji odpovídat na dotazy "jaké je maximum čísel a_i až a_j?" [Postupně jsme navrhli řešení, přičemž uvádíme čas na předzpracování + čas na dotaz: Ο(N)+Ο(log N), Ο(N log N) +Ο(1), Ο(N)+Ο(log log N), Ο(N)+Ο(log log log N), Ο(N)+Ο(log^* N).]
Vytvořte síť, která hledá minimum daných prvků [Ο(log N) hladin].
Vytvořte síť, která zatřídí prvek do setříděné posloupnosti [Ο(log N) hladin].
Napište program, který pro danou permutaci sestrojí komparátorovou síť s Ο(log N) vrstvami, která tuto permutaci setřídí.
Dokažte, že pokud máme monotónní funkci (x≤y ⇒ f(x)≤y), můžeme ji se stejným výsledkem aplikovat jak před, tak po provedení libovolné komparátorové sítě.
Dokažte, že pokud komparátorová síť korektně setřídí všechny posloupnosti nul a jedniček, tak už korektně setřídí libovolný vstup.
Dokažte, že Batcherovo třídění funguje.

6. prosince 2011 Řešené příklady:
Ukažte, že nalézt konvexní obal nelze rychleji než setřídit souřadnice daných bodů.
Nalezněte konvexní obal v čase Ο(N log N).
Nalezněte konvexní obal v čase Ο(N H), kde H je velikost výsledného obalu.
Nalezněte konvexní obal v čase Ο(N log H), kde H je velikost výsledného obalu.
Spočtěte obsah sjednocení osově souběžných obdélníků v čase O(N log N).

13. prosince 2011 Ř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í předchozího faktu zkonstruujte DCT, diskrétní kosinusovou transformaci – dostanete N reálných čísel, okopírováním prostředních N-2 prvků vytvořte antisymetrický vektor, spusťte FFT, a zahoďte posledních N-2 prvků (které jsou stejně symetrické).
Pomocí Fourierovy transformace navrhněte algoritmus pro spektrální analýzu zvuku, tj. rozklad daného vzorku na několik sinusovek, jejichž složením vzorek vznikl.

Datum	Obsah
4. října 2011	Řešené příklady: Na středu kruhového rybníku plave kačenka a na břehu jí mlsně pozoruje kočka. Ta se pohybuje čtyřikrát rychleji než kačenka. Najděte strategii, která kačence vždy umožní dostate se na břeh rybníčku, aby se tam nepotkala s kočkou. Funkce f(x, y) je pro x≥0, y≥0 kladná a ostře rostoucí v každé souřadnici. Dostanete hodnotu z a vaším úkolem je co nejrychleji najít všechny nezáporné dvojice x, y, že f(x, y) = z. [Ο(n log (m/n) + m log (n/m)) pro n, m minimální takové, že f(n, 0)≥z a f(0, m)≥z, a dokázali jsme, že je to i spodní odhad]. Navrhněte datovou strukturu, která podporuje operace vlož, odeber a medián. [všechny operace Ο(log N)] Navrhněte datovou strukturu umožňující vyhledávání stránek obsahující daná klíčková slova – Google hadr :–)
11. října 2011	Cvičení odcvičil Tomáš Gavenčiak, díky!
18. října 2011	Cvičení odcvičil Tomáš Gavenčiak, díky!
25. října 2011	Cvičení odcvičil Tomáš Gavenčiak, díky!
1. listopadu 2011	Řešené příklady: Pro dvě slova A a B najděte nejdelší souvislé společné podslovo. [pro N=součet délek A a B umíme Ο(N²) pro vyzkoušení všech posunů, Ο(N log N) pomocí hešování a Ο(N) pomocí suffixových stromů] Dostanete text ohromné délky, smíte si ho předzpracovat. Poté chcete odpovídat na otázky obsahuje text slovo α, nejlépe v čase úměrném délce α. [vyřešili jsme pomocí suffixových stromů a suffixových polí] Předvedli jsme si algoritmus Boyer-Moore. V N továrnách se vyrábí jeden typ výrobku, v továrně i ho denně vyrobí t_i. M obchodů chce výrobek prodávat, obchod i ho denně potřebuje o_i. Mezi některými továrnami a obchody je možné převážet libovolné množství výrobků. Navrhněte, jak dopravovat výrobky mezi továrnami a obchody, aby se denně prodalo maximum výrobků. Máte N projektů, za vyřešení každého dostanete sumu p_i. Dále máte M zdrojů, každý vás stojí z_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ů. [minimální řez]
8. listopadu 2011	Řešené příklady: Máme rozehranou hokejovou ligu. Zajímá nás, jestli existuje dohrání, že zvolený tým skončí na prvním místě. Předpokládejme, že graf křižovatek a silnic ve městě je bipartitní. Umístěte co nejméně policistů na křižovatky, aby každá ulice na alespoň jednom kraji měla policistu, který ji hlídá. Navrhněte algoritmus, který dokáže řešit toky v síti nejen s maximálními, ale i minimálními kapacitami.
15. listopadu 2011	Řešené příklady: Dokončení algoritmu, který řeší toky s maximálními i minimálními kapacitami. Vyřešte problém naokrouhlování matice – dostali jsme matici s reálnými prvky. Nahraďte každý prvek jeho spodní či horní celou částí tak, aby součty řádek a sloupců byly po zaokrouhlení stejné jako v původní matici. Vyřešte problém letecké společnosti – máte seznam L letů, které máte obsloužit. Zjistěte, kolik nejméně posádek potřebujete. Jedna posádka může obsloužit libovolně mnoho letů, jenom každý další musí začínat tam, kde končil předchozí. Těžší varianta smí v jednom letadle převážet až 3 posádky najednou. Ukažte složitost Dinice [Ο(N² M)] Dokažte, že pro grafy s jednotkovými kapacitami trvá Dinic Ο(N M), Ο(√M M)* a také Ο(N^2/3 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í.] Naimplementujte Goldbergův algoritmus, aby běžel v čase Ο(N²√M).
22. listopadu 2011	Řešené příklady: Ukažte, že v hradlové síti s hradly OR je pro spočítání OR N vstupních bitů potřeba alespoň log₂ N vrstev. Ukažte, že libovolnou binární funkci N proměnných lze spočítat hradlovou sítí s jediným typem hradel (např. NAND či NOR) s hloubkou N. Ukažte, že hloubka N je u některých opravdu potřeba. Navrhněte sčítačku dvou N-bitových čísel jako hradlovou síť s Ο(log N) vrstvami. Navrhněte násobičku dvou N-bitových čísel jako hradlouvou síť s Ο(log N) vrstvami. Vytvořte hradlovou síť, která počítá zbytek po dělení daného N-bitového čísla pěti.
29. listopadu 2011	Řešené příklady: Dostanete N čísel a₁, ..., a_N. Vaším cílem je provést předzpracování a poté co nejrychleji odpovídat na dotazy "jaké je maximum čísel a_i až a_j?" [Postupně jsme navrhli řešení, přičemž uvádíme čas na předzpracování + čas na dotaz: Ο(N)+Ο(log N), Ο(N log N) +Ο(1), Ο(N)+Ο(log log N), Ο(N)+Ο(log log log N), Ο(N)+Ο(log^ N).] Vytvořte síť, která hledá minimum daných prvků [Ο(log N)* hladin]. Vytvořte síť, která zatřídí prvek do setříděné posloupnosti [Ο(log N) hladin]. Napište program, který pro danou permutaci sestrojí komparátorovou síť s Ο(log N) vrstvami, která tuto permutaci setřídí. Dokažte, že pokud máme monotónní funkci (x≤y ⇒ f(x)≤y), můžeme ji se stejným výsledkem aplikovat jak před, tak po provedení libovolné komparátorové sítě. Dokažte, že pokud komparátorová síť korektně setřídí všechny posloupnosti nul a jedniček, tak už korektně setřídí libovolný vstup. Dokažte, že Batcherovo třídění funguje.
6. prosince 2011	Řešené příklady: Ukažte, že nalézt konvexní obal nelze rychleji než setřídit souřadnice daných bodů. Nalezněte konvexní obal v čase Ο(N log N). Nalezněte konvexní obal v čase Ο(N H), kde H je velikost výsledného obalu. Nalezněte konvexní obal v čase Ο(N log H), kde H je velikost výsledného obalu. Spočtěte obsah sjednocení osově souběžných obdélníků v čase O(N log N).
13. prosince 2011	Ř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í předchozího faktu zkonstruujte DCT, diskrétní kosinusovou transformaci – dostanete N reálných čísel, okopírováním prostředních N-2 prvků vytvořte antisymetrický vektor, spusťte FFT, a zahoďte posledních N-2 prvků (které jsou stejně symetrické). Pomocí Fourierovy transformace navrhněte algoritmus pro spektrální analýzu zvuku, tj. rozklad daného vzorku na několik sinusovek, jejichž složením vzorek vznikl.

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