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:
  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 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.
  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 (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.

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)

DatumObsah
29. září 2010Cvičení odpadá.
6. října 2010Organizační povídání, opakování
Řešené příklady:
  • Jak setřídit posloupnost N obecných prvků? [Ο(N2), Ο(N log N)]
  • Jak setřídit posloupnost čísel 1..H? [Ο(N+H)]
  • Jak setřídit posloupnost čísel 0..232-1 [3*O(N+211), Ο(211) 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 [Ο(N2), Ο(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 [Ο(N2) 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 2010Zá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á. [Ο(N3)]
  • Ukažte složitost Dinice [Ο(N2 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. [Ο(N3)]
  • Naimplementujte Goldbergův algoritmus, aby běžel v čase Ο(N2M).
  • 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ů.
17. listopadu 2010Stá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 yi = yn-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 [Ο(Nlog2 3)]
8. prosince 2010Kompará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 2010Hradlové 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 2010NP ú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 2010Asymetrické š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 (28. 09. 2011)

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

JménoÚkol 1Úkol 2SpecifikaceZápočťákZápočet
Martin Baláž100100Wildcardy a`la ESETOKOK
Tibor Baláž
Marek Beliš100100Třídění řetězcůOKOK
Michal Brabec100100AVL stromyOKOK
Leonid Buneev100100FFTOKOK
Přemysl Čech100100RSAOKOK
Jan Čurda100
Tuan Do Manh100100Algoritmus tří Indů
Richard Dobřichovský20
Jan Dufek100100Test prvočíselnostiOKOK
Martin Dvořáček0
Juraj Figura1001003D konvexní obalOKOK
Marek Fišer100100Fraktální komprese obrázkůOKOK
Jan Forst100100
Robert Guth100100Průsečíky přímekOKOK
Juraj Hámorník100100RSAOKOK
Radim Horák1001003D konvexní obalOKOK
Miroslav Chomut100100N-rozměrné integrályOKOK
Jakub Jenis100100AVL merge-OKOK
Milan Ježek100100Nejdelší palindromOKOK
Tomáš Kafka100
Vojtěch Kaluža100100Algoritmus tří IndůOKOK
Ondřej Klejch100100Nejdelší palindromOKOK
Jan Kolárik100100Třídění řetězcůOKOK
Jaroslav Kovář
Ivan Krasičenko100100Sjednocení a obvod obdélníkůOKOK
Jaroslav Kubát100100TriangulaceOKOK
Jakub Kúdela100100Nejdelší palindromOKOK
Šimon Kvasnička
Lukáš Lánský100100Algoritmus tří IndůOKOK
Ondřej Linhart100100Třídění řetězců
Erik Lux1001003D konvexní obalOKOK
Martin Pilný100100FF a Edmondsonův algoritmusOKOK
Jan Smrčina30
Kristýna Stodolová1001002-SATOKOK
Veronika Steffanová100100Inkrementální konstrukce Voroneho diagramuOKOK
Peter Šimora100100Nejčastější podřetězecOKOK
Petr Škoda100100Sjednocení a obvod obdélníkůOKOK
Jan Šrogl1000
Miroslav Vodolán100100Dekompozice do BCNFOKOK
Jiří Vytasil100100Ultimátní konvexní obalOKOK
Tomáš Witzany100100Konstrukce Voroneho diagramuOKOK
Lijun Wu100100AVL mergeOKOK
Pavel Zbytovský100100Open Street Map
Hujer100100Otázka života, vesmíru a vůbecOKOK

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


Zpět