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


Cvičení se koná v úterý v 14:00 v S11. První cvičení se koná až druhý týden školy, tedy v úterý 6. října.

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. 2010 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. 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. 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.

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. 2010)

DatumObsah
29. září 2009Cviko odpadá.
6. října 2009
Řešené příklady:
  • Dlaždičkování šachovnice s dírami dominovými kostkami 2x1.
  • Hledání maximálního párování pomocí toků v síti, jeho složitost.
  • Síť, na které FF nikdy neskončí (a dokonce konverguje k špatnému výsledku).
13. října 2009
Řešené příklady:
  • Nalezněte co nejvíce vrcholově a hranově disjunktních cest mezi dvěma danými vrcholy.
  • Umístěte na šachovnici, která má na některých políčkách zeď, co nejvíce navzájem se neohrožujících věží. Pokud je mezi dvěma věžemi zeď, tyto věže se neohrožují.
  • Ukažte, že následující hladový algoritmus neřeší předchozí úlohu. Pro každé políčko si spočítám následující hodnotu: pokud bych na toto políčko položil věž, na kolik jiných políček už nebudu kvůli tomu moct položit věž. (Jinak řečeno, pro každé políčko si spočítám, kolik dosud neohrozených políček ohrozím, když na toto políčko položím věž.) Poté vyberu libovolné políčko s nejnižší hodnotou a tam věž položím. Algoritmus se opakuje, dokud zbývají neohrožená políčka. První tři lidé, kteří mi pošlou mailem protipříklad, tím splní první úkol.
  • Ukažte, že složitost nalezení maximálního párování pomocí Dinicova algoritmu je Ο(N1/2M).
20. října 2009Cvičení suploval Martin Mareš, díky :–)
27. října 2009Cvičení suploval Tomáš Gavenčiak, děkuji :–)
3. listopadu 2009
Řešené příklady:
  • Každý booleovská funkce jde vyjádřit hradlovou sítí ...
  • ... i když ta musí být někdy exponenciálně veliká.
  • Binární přičítačka jedničky nemůže být rychlejší než logaritmická v nejhorším případě.
  • Opakování sčítačky s logaritmickou hloubkou.
  • Binární odčítačka s logaritmickou hloubkou.
  • Hradlová síť pro spočítání zbytku po dělení 3.
  • Komparátorová síť pro nalezení maxima.
  • Komparátorová síť, která zatřiďuje hodnotu do seřazené posloupnosti.
10. listopadu 2009
Řešené příklady:
  • 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.
  • Dostanete vstup a zakázané slovo. V lineárním čase vyškrtejte z tohoto vstupu všechna zakázaná slova. Pozor na to, že vyškrtnutím jednoho zakázaného slova může další vzniknout, jako například při odstraňování bug ze slova bubugga.
17. listopadu 2009Cvičení odpadá
24. listopadu 2009
Řešené příklady:
  • V textu délky N najděte nejčastější podslovo dané délky K.
  • V textu délky N najděte nejdelší opakující se podslovo.
  • Co nejjednodušeji zjistěte, jestli dva vektory svírají úhel méně nebo více než 180 stupňů.
  • Vymyslete způsob, jak počítat konvexní obal inkrementálně. Tedy když máte spočítaný konvexní obal N bodů a dostanete další, dokážete obal upravit, aby bral v úvahu i přidaný bod.
  • Spočtěte obsah daného konvexního mnohoúhelníku.
  • Spočtěte obsah daného nekonvexního mnohoúhelníku.
1. prosince
Řešené příklady:
  • Spočtěte obsah sjednocení osově souběžných obdélníků v čase O(N log N).
  • Procvičte si FFT: kolik je DFT(0, 0, ..., 0)
  • Procvičte si FFT: kolik je DFT(ω0, ω1, ..., ωn-1)
  • Procvičte si FFT: kolik je DFT(ω0*j, ω1*j, ..., ω(n-1)*j)
  • Procvičte si FFT: kolik je DFT(cos(0*2π/n), cos(1*2π/n), ..., cos((n-1)*2π/n))
  • Procvičte si FFT: kolik je DFT(sin(0*2π/n), sin(1*2π/n), ..., sin((n-1)*2π/n))
8. prosince
Řešené příklady:
  • Máte dané body v rovině a číslo K. Vaším úkolem je najít kruh o poloměru K takový, že obsahuje co nejvíce ze zadaných bodů.
  • Procvičte si FFT: kolik je DFT(1,0,1,0,1,0,1,0)?
  • Procvičte si FFT: kolik je DFT(1,1,0,0,1,1,0,0)?
  • Procvičte si FFT: kolik je DFT(cos(0*2jπ/n+φ), cos(1*2jπ/n+φ), ..., cos((n-1)*2jπ/n+φ))
  • Jak co nejrychleji obrátit bity v uint32_t?
  • Implementujte FFT iterativně.
15. prosince
Řešené příklady:
  • Ukažte, že (E3,E3)-SAT (SAT, každá klauzule má přesně tři literály a každá proměnná se vyskytuje v přesně třech literálech) má vždy řešení.
  • Vyřešte 2-SAT v polynomiálním čase.
  • Ukažte, že nalezené minimální vrcholové pokrytí je NP-úplné.
  • Ukažte, že ZOE je NP-úplné.
5. prosince
Řešené příklady:
  • Dokažte, že v bipartitním grafu je velikost minimálního vrcholového pokrytí rovna velikosti maximálního párování.
  • Ukažte, že problém součtu podmnožiny (dostanete N čísel a1, ..., aN, dále číslo K a máte říct, zda existuje podmnožina čísel ai se součtem K) je ekvivalentní s problémem loupežníků (dostanete N čísel a1, ..., aN a máte říct, jestli jdou rozdělit na dvě skupiny o stejném součtu).
  • Vyřešte problém součtu podmnožiny pomocí problému batohu.
  • Ukažte, že problém součtu podmnožiny je NP-úplný.
12. prosince
Řešené příklady:
  • Pomocí minimální kostry a nejmenšího váženého párování (jeho cílem je v úplném ohodnoceném grafu se sudým počtem vrcholů najít perfektní párování s nejmenším součtem ohodnocení hran) vytvořte 1.5-aproximaci problému obchodního cestujícího.
  • Navrhněte 2-aproximaci minimálního vrcholového pokrytí [stačí hladový algoritmus + fakt, že minimální vrcholové pokrytí je alespoň tak velké jako maximální párování].
  • Navrhněte 2-aproximaci maximálního řezu. Dostanete graf a vaším cílem je rozdělit vrcholy do dvou skupin tak, aby mezi nimi vedlo co nejvíc hran.
  • Dostanete E3-SAT formuli, čili každá její klauzule obsahuje právě tři literály. Najděte ohodnocení, se kterým bude splněno co nejvíc klauzulí [jde splnit 7/8 klauzulí].

Zápočtové práce (14. 09. 2010)

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

JménoÚkol 1Úkol 2SpecifikaceZápočťákZápočet
Martin Antl0Lineární třídění řetězců
Adam Černý0RSA
Patrik Černý100100Počítání výskytů slovOKOK
Martin Dzurenko100100Triangulace mnohoúhelníkaOKOK
Ondřej Fialka100100Lineární třídění řetězcůOKOK
František Haas100100Goldbergův algoritmusOKOK
Ondřej Hamák50
Jakub Horák0
Tomáš Hubálek
Tomáš Hvorkový90100Počítání výskytů slov
Marika Ivanová0Počítání výskytů slov
Zbyněk Jiráček100100Rabin-MillerOKOK
Tomáš Kadlec90100Nejčastější podslovo délky KOKOK
Maroš Kasinec100100R-strom
Andrej Kouřil100100Suffixové stromy
Michal Kozák
Markéta Kráčalíková
Michal KrausUznáno100Goldbergův algoritmusOKOK
Filip Krijt100100RSAOKOK
Markéta Kůdelová20
Ladislav Láska100100Rychlé násobení číselOKOK
Marek Linka90100Lineární třídění řetězcůOKOK
Petr Mácha100
Jan MatějekUznáno100Hledání ve Voroneho diagramechOKOK
Vladimír Matěna100100Disjkunktní cestyOKOK
Jan Musílek
Olga PaščenkoPočítání výskytů slov
Martin Pelikán100100Suffixové stromy a pole
Libor Peltan1001003D konvexní obal
Jakub Samek
Jakub Skalický90100Goldbergův algoritmusOKOK
Jan Skalický100100Algoritmus tří IndůOKOK
Jiří Smolík100100Průsečíky úsečekOKOK
Petr Sokola0
Martin Stránský100100Algoritmus tří IndůOKOK
Miroslav Šiagi
Štěpán Šindelář100100Lineární třídění řetězcůOKOK
Jakub Šulek
Jan Tuček100100Průsečíky úsečekOKOK
Matěj Zábský100100Voroného diagramOKOK

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


Zpět