Algoritmy a datové struktury 1
Přednáška z Algoritmů a datových struktur 1 [NTIN060] se koná v LS 2021/2021 ve čtvrtky od 10:40 (v N1, dá-li PES, jinak online).
Na přednášky používáme Zoom, odkaz jste dostali mailem. Pokud vám chybí, napište mi prosím. Videozáznamy přednášek se budou objevovat zde.
Kdybyste čemukoliv nerozuměli, rád si s vámi domluvím konzultaci. Ozvěte se mi prosím na adresu mares+ads@kam.mff.cuni.cz.
Co se přednášelo
datum | téma | video |
---|---|---|
4. 3. | Úvodní příklad s nejdelší rostoucí podposloupností a přehlídka způsobů, jak ho vyřešit. Pokus o definici algoritmu. Výpočetní model RAM: paměť, aritmetické instrukce. | video board |
11. 3. | Plán: Výpočetní model RAM. Čas a prostor konkrétního výpočtu (různé varianty: jednotková cena, logaritmická cena, omezený rozsah čísel), časová a paměťová složitost algoritmu. Programování na RAMu a počítání složitosti: příklad s tříděním výběrem. Připomenutí asymptotické notace (O, Ω, Θ). |
Cvičení
Cvičení k této paralelce vedou:
- Jiří Beneš
- Jan Hric
- Marika Ivanová
- Václav Končický
- Martin Koutecký
- Petr Kučera
- Vladan Majerech
- Michal Opler
- Kristýna Pantůčková
Studentům kombinovaného studia doporučuji vybrat si libovolného cvičícího a domluvit se s ním na získání zápočtu za domácí úkoly. Účast na cvičení není nutná, ale hodí se alespoň občas se tam stavit, abyste měli přehled, co se dělá. Za mnou samozřejmě můžete přijít na konsultaci, domluvte se e-mailem.
Literatura
- Martin Mareš, Tomáš Valla: Průvodce labyrintem algoritmů
- Videozáznamy z roku 2015 (přístupné pouze studentům a zaměstnancům MFF UK)
- Mé minulé přednášky z let 2018, 2017, 2015, 2013, 2011, 2009, 2007 a zápisy z nich.
- Dasgupta, Papadimitriou, Vazirani: Algorithms (velice pěkná knížka pokrývající většinu přednášky, navíc dostupná online)
- Programátorská kuchařka KSP (nepříliš formální textíky o různých algoritmech)
- Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms (2nd Edition), Mc Graw Hill 2001 (vpravdě monumentální dílo)
Ostatní zajímavé knihy:
- Jiří Demel: Grafy a jejich aplikace (grafové algoritmy)
- Martin Mareš: Krajinou grafových algoritmů (lahůdky pro pokročilé a zvídavé)
- Matoušek, Nešetřil: Kapitoly z diskrétní matematiky (kombinatorické pozadí, také úvod do pravděpodobnosti)
- Pavel Töpfer: Algoritmy a programovací techniky (pěkná úvodní knížka)
Sbírky příkladů:
- Martin Mareš, Pavel Töpfer: Korespondeční seminář z programování 1987-1998
- Archiv KSP a MO-P na webu
- Ivan Libicher, Pavel Töpfer: Od problému k algoritmu a programu
Různé:
- Animovaný výklad algoritmů v Algovision kolegy Kučery.
- Applet demonstrující vyhledávací stromy
- Robert Sedgewick: Left-Leaning Red-Black Trees (varianta červeno-černých stromů zmíněná na přednášce)