IB002 Návrh algoritmů I

Fakulta informatiky
jaro 2008
Rozsah
2/1. 3 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: k, z.
Vyučující
RNDr. Libor Škarvada (přednášející)
RNDr. Filip Andres (cvičící)
RNDr. Lukáš Boháč (cvičící)
Mgr. et Mgr. Martin Derka, M.Sc. (cvičící)
RNDr. Štěpán Kozák (cvičící)
doc. RNDr. Barbora Kozlíková, Ph.D. (cvičící)
RNDr. Václav Lorenc (cvičící)
Mgr. Matúš Madzin (cvičící)
prof. RNDr. Jan Strejček, Ph.D. (cvičící)
doc. RNDr. David Svoboda, Ph.D. (cvičící)
RNDr. Josef Šprojcar, Ph.D. (cvičící)
Mgr. Filip Štefaňák (cvičící)
Mgr. Marek Trtík, Ph.D. (cvičící)
RNDr. Aleš Zlámal (cvičící)
Mgr. Radek Holčák (pomocník)
Garance
prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: RNDr. Libor Škarvada
Rozvrh
Po 16:00–17:50 D2, Po 16:00–17:50 D3, Po 16:00–17:50 D1
  • Rozvrh seminárních/paralelních skupin:
IB002/01: každou sudou středu 14:00–15:50 A107, J. Strejček
IB002/02: každou lichou středu 14:00–15:50 A107, J. Strejček
IB002/03: každé sudé úterý 12:00–13:50 B011, V. Lorenc
IB002/04: každé liché úterý 12:00–13:50 B011, V. Lorenc
IB002/05: každé sudé úterý 10:00–11:50 B011, B. Kozlíková
IB002/06: každé liché úterý 10:00–11:50 B011, B. Kozlíková
IB002/07: každý sudý pátek 10:00–11:50 B011, D. Svoboda
IB002/08: každý lichý pátek 10:00–11:50 B011, D. Svoboda
IB002/09: každé sudé úterý 8:00–9:50 B410, F. Andres
IB002/10: každé liché úterý 8:00–9:50 B410, F. Andres
IB002/11: každý sudý pátek 8:00–9:50 A107, J. Šprojcar
IB002/12: každý lichý pátek 8:00–9:50 A107, J. Šprojcar
IB002/13: každý sudý čtvrtek 18:00–19:50 B410, L. Boháč
IB002/14: každý lichý čtvrtek 18:00–19:50 B410, L. Boháč
IB002/15: každé sudé úterý 16:00–17:50 B204, L. Škarvada
IB002/16: každé liché úterý 16:00–17:50 B204, L. Boháč
Předpoklady
Předpokládá se, že posluchači jsou schopni číst a psát elementární programy v nějakém funkcionálním a nějakém imperativním programovacím jazyce.
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
předmět má 23 mateřských oborů, zobrazit
Cíle předmětu
Kurs probírá základní techniky analýzy algoritmů, datové struktury a operace nad nimi. Zaměřuje se na dokazování korektnosti algoritmů a na jejich efektivnost. Základní algoritmické pojmy a konstrukce jsou uváděny bez přímé návaznosti na konkrétní programovací jazyk a bez požadavků na jejich praktickou programovou realizaci. Cílem je naučit studenta pracovat s vlastními algoritmy oproštěnými od implementačních detailů. To dovoluje presentovat poměrně široký záběr technik, používaných ve funkcionálním, imperativním i v objektově orientovaném programování.
Osnova
  • Základy analýzy algoritmů: Korektnost algoritmu, vstupní a výstupní podmínky, parciální korektnost, konvergence, verifikace. Délka výpočtu, složitost algoritmu, složitost problému. Asymptotická analýza časové a prostorové složitosti, růst funkcí, využití rekurentních relací při analýze algoritmů.
  • Fundamentální datové struktury: Seznamy, zásobníky a fronty. Binární vyhledávací stromy, vyvážené stromy, representace množin.
  • Řadicí algoritmy: Řazení rozdělováním, slučováním, haldou, dolní odhad složitosti.
  • Základní grafové algoritmy: Representace grafů. Procházení grafu do hloubky a do šířky.
Literatura
  • SKIENA, Steven S. The algorithm design manual. New York: Springer, 1998, xvi, 486. ISBN 0387948600. info
  • CORMEN, Thomas H., Charles Eric LEISERSON a Ronald L. RIVEST. Introduction to algorithms. Cambridge: MIT Press, 1989, xvii, 1028. ISBN 0070131430. info
Metody hodnocení
Zkoušky jsou písemné. Dvě zkoušky budou průběžné (polosemestrální) a jedna závěrečná za celý semestr.
Účast na cvičeních je povinná, neučast je možná pouze ze závažných důvodů. Student může maximálně ve dvou případech navštívit jinou skupinu cvičení, než do které je zapsán. V tomto případě je ale povinen tuto skutečnost nahlásit cvičícímu své seminární skupiny e-mailem a zapsat se na prezenční listinu seminární skupiny, na kterou se dostaví.
Navazující předměty
Informace učitele
http://www.fi.muni.cz/~libor/vyuka/IB002/
Další komentáře
Studijní materiály
Předmět je vyučován každoročně.
Nachází se v prerekvizitách jiných předmětů
Předmět je zařazen také v obdobích jaro 2003, jaro 2004, jaro 2005, jaro 2006, jaro 2007, jaro 2009, jaro 2010, jaro 2011, jaro 2012, jaro 2013, jaro 2014, jaro 2015, jaro 2016, jaro 2017, jaro 2018, jaro 2019, jaro 2020, jaro 2021, jaro 2022, jaro 2023, jaro 2024, jaro 2025.