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

... se v LS 2011/2012 koná v pondělky od 12:20 v T11.

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
20. 2. Krátké zamyšlení nad tím, co je to algoritmus a jak se dají algoritmy mezi sebou porovnávat. Rekurzivní hádanky a složitost aritmetických operací.
27. 2. Ještě trocha aritmetiky: největší společný dělitel Euklidovým algoritmem i půlením. Jakou složitost má Eratosthenovo síto? Odhad součtu harmonické řady a řady převrácených hodnot prvočísel.
Na rozmyšlenou: Jak síto upravit, aby počítalo, kolik má které číslo dělitelů? Kolik iterací může nejvýše provést Euklidův algoritmus?
5. 3. Vyhledávací stromy a operace s nimi.
Na rozmyšlenou: Jak pro daný prvek zjistit, kolikátý nejmenší je? Jak vytvořit dokonale vyvážený strom z prvků, které nejsou v poli, ale v seznamu?
12. 3. Pokračování procházky binárním lesem. Intervalové stromy (operace "nastav hodnotu i-tého prvku" a "spočti minimum z i-tého až j-tého prvku").
Na rozmyšlenou: Hledání cesty s daným součtem ve stromu s ohodnocenými hranami. Vyvažování stromů pomocí rekonstrukcí.
19. 3. Trochu obecněji o vyvažování stromů. (a,b) stromy a jejich souvislosti s červeno-černými stromy. Potenciálové důkazy: přičítání jedničky, vyvažování rekonstrukcí stromu.
Na rozmyšlenou: Delete v (a,b) stromu.
26. 3. Úloha o cestách ve stromech a její různé varianty.
2. 4. Přehled třídicích algoritmů. Kolik porovnání je potřeba na nalezení minima a maxima z n prvků? Jak přerovnat kuličky tří barev?
Do konce dubna si vyberte téma zápočtové práce.
16. 4. Prohledávání grafů do hloubky, šířky či jinak. Reprezentace grafů a proč na ní záleží. Komponenty souvislosti a test bipartitnosti. Kulhavý kůň, kulhavé autíčko a Théseus s Minotaurem.
23. 4. DFS stromy a druhy jejich hran. Topologické uspořádání grafu. Hledání mostů.
30. 4. V jakém pořadí odtrhávat vrcholy, aby graf zůstal stále souvislý? Hasiči a továrny na třaskaviny. Wanted: šéf agentů. Asfaltování městečka. Vyvážená a skoro vyvážená orientace grafu.
7. 5. Kreslení grafu jedním tahem. Nejkratší cesty v ohodnocených grafech: obecný relaxační algoritmus.
14. 5. Relaxační algoritmus ze všech stran. Fronta versus zásobník versus Dijkstrovo pravidlo.
21. 5. Metoda Rozděl a panuj: násobení čísel a řešení rekurencí.

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

Počet inverzí

Vrabci na střeše

Stránku spravuje Martin Mareš