I002 Návrh algoritmů I

Fakulta informatiky
jaro 2003
Rozsah
2/0. 2 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: k, z.
Vyučující
prof. RNDr. Tomáš Pitner, Ph.D. (přednášející)
RNDr. Libor Škarvada (přednášející)
Garance
prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: RNDr. Libor Škarvada
Předpoklady
! IB002 Návrh algoritmů I &&! I502 Návrh algoritmů I
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 jazyku.
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
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. Hašovací tabulky. Binární vyhledávací stromy, vyvážené stromy, representace množin.
  • Třídicí algoritmy: Třídění 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í
Kurs veden formou přednášek a je ukončen závěrečnou písemnou zkouškou.
Navazující předměty
Informace učitele
http://www.fi.muni.cz/usr/skarvada/vyuka/IB002/
Další komentáře
Předmět je vyučován každoročně.
Výuka probíhá každý týden.
Předmět je zařazen také v obdobích zima 1995, léto 1996, zima 1996, léto 1997, zima 1997, léto 1998, jaro 1999, jaro 2000, jaro 2001, jaro 2002.
  • Statistika zápisu (nejnovější)
  • Permalink: https://is.muni.cz/predmet/fi/jaro2003/I002