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:
  1. 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.
  2. 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.
  3. 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.

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)

DatumObsah
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 2011Cvičení odcvičil Tomáš Gavenčiak, díky!
18. října 2011Cvičení odcvičil Tomáš Gavenčiak, díky!
25. října 2011Cvič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 Ο(N2) 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í ti. M obchodů chce výrobek prodávat, obchod i ho denně potřebuje oi. 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 pi. Dále máte M zdrojů, každý vás stojí zj. 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ů. [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 [Ο(N2 M)]
  • Dokažte, že pro grafy s jednotkovými kapacitami trvá Dinic Ο(N M), Ο(√M * M) a také Ο(N2/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 Ο(N2M).
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ň log2 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 a1, ..., aN. Vaším cílem je provést předzpracování a poté co nejrychleji odpovídat na dotazy "jaké je maximum čísel aiaj?" [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 yi = yn-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 (04. 09. 2012)

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

JménoÚkol 1Úkol 2SpecifikaceZápočťákZápočet
Michal Bilanský100100Rychlé násobení číselOKOK
Tuan Do Manh100100Algoritmus tří IndůOKOK
Adam Dominec100100Voroneho diagram v metrice L∞
Vlastimil Dort100100Voroneho diagramOKOK
Tomáš Faltín100100Rychlé násobení číselOKOK
Peter Gerek100100Nejdelší palindromOKOK
Duc Trung Ha100100Sleator-Tarjanovy stromyOKOK
Jakub Hajič100100Rabin-Millerův test prvočíselnostiOKOK
Štěpán Havránek100100Detekce kolizíOKOK
Miloš Chromý100100Regulární výrazyOKOK
Ondřej Jarolímek
Ondřej Moravčík0
Roman Palkoci100100Nejdelší palindromOKOK
David Pěgřímek100100Boyer-MooreOKOK
Vítězslav Plachý
Jan Schwarz100100Rabin-Millerův test prvočíselnostiOKOK
Pavel Taufer100100Edmondsův algoritmus
Jan Tomášek100100
Dušan Variš100100Hranová souvislost grafuOKOK
Viktorie Vášová100100Voroneho diagramOKOK
Vojtěch Vondra100100Lokalizace bodu
Petr Vyhlas100100Suffixové stromy
Martin Wenisch1000
Hujer100100Otázka života, vesmíru a vůbec

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


Zpět