Cvičení z Algoritmů a Datových Struktur II

... se v ZS 2010/2011 koná v pondělí od 16:30 v T8. Oficiálně se jedná o cvičení k přednášce prof. Kučery, můžete chodit, i pokud jste v druhé paralelce, vzhledem k mnoha chybějícím a nahrazovaným přednáškám bude letos návaznost na přednášku spíše volná.

Zápočet se uděluje za zápočtovou práci a vyřešení dvou domácích úkolů v CodExu (viz níže). Účast na cvičení je polehčující okolností (kdo bude na cvičení aktivní, může řešit jednodušší úlohu, případně mu ji mohu odpustit).

Informace o přednášce (syllabus, učební texty atd.) získáte na stránce přednášejícího.

Některé další učební texty najdete u mé loňské přednášky.

Co jsme dělali

datum téma
4. 10. Vyhledávání v textu: opakování algoritmů Knuth-Morris-Pratt a Aho-Corasicková. Jak vypadají okrajové případy (superlineární počet výskytů, superlineární velikosti množin apod.)?
11. 10. Třídění řetězců.
18. 10.

Úlohy o řetězcích:

  • počítání výskytů řetězců
  • (*) dolní odhad složitosti Rabinova-Karpova algoritmu, když nic nenajde
  • censorův problém
  • jak poznat, že jeden řetězec je rotací jiného?
  • (*) rozdělit množinu řetězců na třídy rotační ekvivalence
  • nejčastější podřetězec zadané délky
  • nejdelší společný podřetězec dvou řetězců
  • nejdelší opakující se podřetězec

Založte si do příštího cvičení účet v CodExu.

25. 10. Toky v sítích: Fordův-Fulkersonův algoritmus a jeho vlastnosti. Celočíselné toky a jejich použití na párování v bipartitních grafech.
1. 11. Toky v sítích: Hledání disjunktních cest. Hrátky s děravou šachovnicí – pokrývání dominovými kostkami a rozestavění neohrožujících se věží.
8. 11. Toky v sítích: Vrcholová pokrytí a nezávislé množiny v bipartitních grafech. Továrny a doly.
15. 11. Fourierova transformace: komplexní mocniny a odmocniny, DFT a její inverze.
22. 11. Fourierova transformace: násobení polynomů a spektrální rozklad signálů (na sin a cos).
29. 11. Hradlové sítě: hrajeme si s booleovskými obvody.
6. 12. Hradlové sítě: paralelní sčítání a variace na něj. Komparátorové sítě.
13. 12. Geometrické algoritmy: konvexní obal (a jak testovat orientaci úhlu), obsah (ne)konvexního mnohoúhelníku. Zametání roviny a jeho použití na průsečíky úseček.
20. 12. Opět zametání roviny: obvod/obsah sjednocení obdélníků. Lokalizace bodu. Datová struktura pro obdélníkové dotazy (2D intervalový strom).
3. 1. Převody problémů a NP-úplnost.
10. 1. Převody problémů a NP-úplnost. Povídání o složitostních třídách a způsobech, jak se dá jejich struktura zkoumat.

Zápočtová práce

Zápočtová práce obnáší vyřešení nějaké algoritmické úlohy. Chci od vás popis algoritmu, rozbor správnosti a časové i paměťové složitosti, velice doporučuji napsat i program a nepoužívat v něm knihovní funkce, u kterých netušíte, jak jsou implementované. Dobrou inspirací k tomu, jak o algoritmech psát, může být třeba archiv KSP nebo MO-P.

Pokud vás žádné téma nenapadá, můžete využít služeb našeho nápadníku. Není sice tak sladký jako polibek informatické múzy, ale v nouzi také poslouží.

Domácí úkoly

Během semestru byste měli naprogramovat dvě úlohy (jednoduché variace na látku z přednášky, které aspoň stručně probereme na cvičení) a odevzdat je v CodExu pro Programování 1/2. Z každé musíte mít plný počet bodů.

Okurence

Poslední bulánčí válka

Záchranný úkol: Théseus a Minotauros

Pokud se vám v prvních dvou úkolech nedaří získat plný počet bodů, případně jste prošvihli termín, můžete si ještě zápočet vysloužit vyřešením záchranného úkolu. Deadline: 30. 6.

Podmínky: Získat z každého úkolu alespoň 70 bodů (počítají se i body získané po termínu) a tento úkol vyřešit za plný počet bodů.

Stránku spravuje Martin Mareš