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

Mé cvičení se v ZS 2011/2012 koná ve středu od 9:00 v S10.

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ášky.

Co jsme dělali

datum téma
5. 10. Opakování ADS1: Jak mazat vrcholy v grafu, aby byl stále souvislý. Minimální kostra pro grafy ohodnocené čísly z 1, 2, 3. Jak vyvést dvojici robotů z bludiště. Hledáme v poli úsek dané délky, aby měl největší medián (nebo největší minimum). Totéž pro matici a její podmatice dané velikosti.
12. 10. Jak zjistit, že jeden řetězec je rotací druhého. Rotování "na místě" a prohazování podřetězců. Slovníkové datové struktury: obyčejné, modulo rotace, modulo přesmyčky. Rýmový slovník: rým s nejdelším suffixem, nejdelší takové slovo, lexikograficky nejmenší takový. Podstromy a osekané stromy pomocí kódování závorkami.
19. 10. Variace à la Aho-Corasicková: nejdelší či nejkratší výskyt na každé pozici, proč jsou potřeba zkratkové hrany, počítání četností slov.
26. 10. Ještě jednou řetězce: nejdelší slovo, které je současně prefixem i suffixem zadaného; těžký život censora (CodEx); nejdelší Fibonacciho podslovo.
Do konce listopadu pošlete téma své zápočtové práce.
2. 11. Toky v sítích: kdy je F-F algoritmus pomalý; největší párování v bipartitních grafech a obecněji největší podgrafy s omezenými stupni; rozmisťování věží na šachovnici a souvislost s permanentem matice.
9. 11. Toky v sítích: Dinicův algoritmus pro jednotkové kapacity; co nejvíce vrcholově a hranově disjunktních cest mezi danými vrcholy; pokrývání šachovnice dominovými kostkami; továrny a obchody; doly a továrny; jak najít dvě disjunktní párování.
16. 11. Ještě jednou disjunktní cesty. Goldbergův algoritmus a jeho chování pro jednotkové kapacity. Jak implementovat zvedání nejvyššího vrcholu?
23. 11. Hradlové sítě: zvěřinec booleovských funkcí; jak vypadají minimální generátory; proč si vystačíme s binární abecedou a 2-vstupovými hradly. Složitost obvodu versus složitost formule. XOR ze čtyř NANDů.
30. 11. Hradlové sítě: sčítání, odčítání a násobení binárních čísel, testování dělitelnosti třemi. Zatřiďování pomocí komparátorů.
7. 12. Geometrické algoritmy: Jak se orientovat v úhlech (determinanty a vektorové součiny), obsah sjednocení obdélníků (mnohoúhelníků?) pomocí zametání roviny.
14. 12. Fourierova transformace a spektrální rozklad signálů (na sin a cos).
21. 12. Převody problémů: 3D-párování na SAT. Na rozmyšlenou převody pro: vrcholové pokrytí, nezávislá množina s nízkými stupni, lineární rovnice a nerovnice.
4. 1. Rozcvička: Kombinační čísla a fraktály. Převody problémů: Lineární a kvadratické rovnice a nerovnice; problém batohu (a jeho varianta se součtem podmnožiny) a dva loupežníci.
11. 1. Otázky a odpovědi. Pár poznámek o složitostních třídách a úplnosti. Co je P-úplný problém? Proč nefunguje hladový algoritmus na batoh či na nezávislou množinu. Nezávislé množiny ve stromech a v bipartitních grafech.

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.

Debordelizace

Taneční seance

Stránku spravuje Martin Mareš