Předmět Algoritmy a datové struktury II (IV003)
Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu IV003 - Algoritmy a datové struktury II, Fakulta informatiky, Masarykova univerzita (MU).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
Cíl
Kurz navazuje na úvodní kurz Algoritmy a datové struktury I. Prezentuje algoritmické koncepty a konstrukty bezjejich přímé návaznosti na jakýkoliv programovací jazyk a bez požadavkůna jejich praktickou programovou realizaci. Cílem je naučit studentakonstruovat a analyzovat algoritmy v kontextu pseudokódů, což umožnístudentovi rozlišit mezi obecnýmikoncepty a specifikami konkrétních programovacích jazyků.Kurz uvádí pokročilé techniky analýzy algoritmů. Rozšiřuje seznamalgoritmických strategií a charakterizuje typ problémů, pro které jsoujednotlivé strategie vhodné. Nové datové struktury jsou prezentoványspolu s příklady algoritmů, které je využívají, přičemž důraz je kladenna propojenost návrhu algoritmu a návrhu datové struktury.
Osnova
Techniky analýzy algoritmů: složitost algoritmů, amortizovanáanalýza složitosti.Techniky návrhu algoritmů: rozděl a panuj, dynamické programování,hladové strategie, backtracking, lokální vyhledávání.Datové struktury: binomiální a Fibonacciho haldy, datové strukturypro reprezentaci disjunktních množin.Grafové algoritmy: problém nejkratších cest z jednoho zdroje (Bellmanův-Fordův algoritmus), obecný problém nejkraších cest (Flydův-Warhallův algoritmus, násobení matic, Johnsonův algoritmus pro řídké grafy). Toky v sítích (Fordova-Fulkersonova metoda, metoda push-relabel), párování.Algoritmy pro práci s řetězci: přímý algoritmus, užití konečných automatů, Rabin-Karpůvalgoritmus, algoritmus KMP.
Literatura
Algorithms. Edited by Sanjoy Dasgupta - Christos H. Papadimitriou - Umesh Virkumar Vazirani. 1st ed. Boston: McGraw-Hill Companies, 2008. x, 320 s. ISBN 978-0-07-352340-8. infoKLEINBERG, Jon a Éva TARDOS. Algorithm design. Boston: Pearson/Addison-Wesley, 2006. xxiii, 838. ISBN 0-321-37291-3. infoCORMEN, Thomas H., Charles E. LEISERSON a Ronald L. RIVEST. Introduction to algorithms. Cambridge: MIT Press, 1990. xi, 1028 s. ISBN 0-262-03141-8. info
Požadavky
( IB002 Algoritmy a datové struktury || PROGRAM ( 1431:N - MA )) && ! IB108 Algoritmy a dat. struktury II
Garant
prof. RNDr. Mojmír Křetínský, CSc.
Vyučující
prof. RNDr. Ivana Černá, CSc.RNDr. Nikola Beneš, Ph.D.RNDr. Mária SvoreňováMgr. Filip ŠtefaňákMgr. Petr BauchRNDr. Peter BezděkRNDr. Petra Budíková, Ph.D.Bc. Jan FikejsMgr. Bc. Tomáš JaníkBc. David KlaškaMgr. Jan Obdržálek, PhD.Bc. Vladimír Štill