FI:IB108 Návrh algoritmů II - Informace o předmětu
IB108 Návrh algoritmů II
Fakulta informatikyjaro 2006
- Rozsah
- 2/0. 2 kr. (plus ukončení). Ukončení: zk.
- Vyučující
- prof. RNDr. Ivana Černá, CSc. (přednášející)
Bc. Tomáš Richter (cvičící) - Garance
- prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování – Fakulta informatiky - Rozvrh
- Čt 12:00–13:50 D3
- Předpoklady
- ( I002 Návrh algoritmů I || IB002 Návrh algoritmů I )&&! I063 Návrh algoritmů II
- Omezení zápisu do předmětu
- Předmět je nabízen i studentům mimo mateřské obory.
- Mateřské obory/plány
- Aplikovaná informatika (program FI, B-AP)
- Informatika a druhý obor (program FI, B-BI)
- Informatika a druhý obor (program FI, B-FY)
- Informatika a druhý obor (program FI, B-GE)
- Informatika a druhý obor (program FI, B-GK)
- Informatika a druhý obor (program FI, B-CH)
- Informatika a druhý obor (program FI, B-IO)
- Informatika a druhý obor (program FI, B-MA)
- Informatika a druhý obor (program FI, B-SO)
- Informatika a druhý obor (program FI, B-TV)
- Informatika (program FI, B-IN)
- Cíle předmětu
- Kurz navazuje na úvodní kurz Návrh algoritmů I. Prezentuje algoritmické koncepty a konstrukty bez jejich přímé návaznosti na jakýkoliv programovací jazyk a bez požadavků na jejich praktickou programovou realizaci. Cílem je naučit studenta konstruovat a analyzovat algoritmy v kontextu pseudokódů, což umožní studentovi rozlišit mezi obecnými koncepty a specifikami konkrétních programovacích jazyků. Kurz uvádí pokročilé techniky analýzy algoritmů. Rozšiřuje seznam algoritmických strategií a charakterizuje typ problémů, pro které jsou jednotlivé strategie vhodné. Nové datové struktury jsou prezentovány spolu s příklady algoritmů, které je využívají, přičemž důraz je kladen na propojenost návrhu algoritmu a návrhu datové struktury.
- Osnova
- Techniky návrhu a analýzy algoritmů: dynamické programování, hladové strategie, backtracking, lokální vyhledávání. Amortizovaná analýza složitosti.
- Datové struktury: binomiální a Fibonacciho haldy, datové struktury pro reprezentaci disjunktních množin.
- Grafové algoritmy: kostry v grafech, problém nejkratších cest, toky v sítích, párování.
- Algoritmy pro práci s řetězci: přímý algoritmus, Rabin-Karpův algoritmus, užití konečných automatů.
- Algoritmy pro NP-těžké problémy: aproximativní algoritmy. Problém pokrytí množin a problém obchodního cestujícího.
- Náhodnostní algoritmy: náhodnostní třídění, problém maximální nezávislé množiny. Náhodnost v datových strukturách.
- Literatura
- Záložky
- https://is.muni.cz/ln/tag/FI:IB108!
- Metody hodnocení
- Informace na webové stránce předmětu http://www.fi.muni.cz/usr/cerna/NAII/ib108.html
- Informace učitele
- http://www.fi.muni.cz/usr/cerna/NAII/ib108.html
Informace na webové stránce předmětu http://www.fi.muni.cz/usr/cerna/NAII/ib108.html - Další komentáře
- Studijní materiály
Předmět je vyučován každoročně.
- Statistika zápisu (jaro 2006, nejnovější)
- Permalink: https://is.muni.cz/predmet/fi/jaro2006/IB108