I502 Návrh algoritmů I

Fakulta informatiky
jaro 2001
Rozsah
2/0. 2 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í), prof. RNDr. Tomáš Pitner, Ph.D. (zástupce)
Garance
prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: RNDr. Libor Škarvada
Rozvrh
Út 10:00–11:50 D1, St 18:00–19:50 D1
Předpoklady
! U212 Návrh algoritmů pro VT IV && (! I002 Návrh algoritmů I )
Doporučuje se zapsat společně s I065 Seminář z návrhu algoritmů I. Předpokládá se, že posluchači jsou schopni psát elementární programy v nějakém funkcionálním a nějakém imperativní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á některé důležité datové struktury a algoritmy.
Osnova
  • Programovací paradigmata, výrazy, příkazy, stav programu.
  • Korektnost algoritmu, vstupní a výstupní podmínky, parciální korektnost, konvergence. Verifikace.
  • Růst funkcí. Rekursivní rovnice.
  • Délka výpočtu, složitost algoritmu, složitost problému.
  • Datové struktury (seznamy, stromy, grafy, pole).
  • Vyhledávání. Vyhledávací stromy.
  • Třídění, dolní odhad složitosti. Třídění rozdělováním, slučováním, haldou.
  • Kombinatorické a grafové algoritmy. Nejkratší cesta, minimální kostra.
Literatura
  • PARSONS, Thomas W. Introduction to algorithms in Pascal. New York: John Wiley & Sons, 1995, xiv, 447. ISBN 0471305944. 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.
Informace učitele
http://www.fi.muni.cz/usr/skarvada/vyuka/I502/
Další komentáře
Předmět je vyučován každoročně.
Předmět je zařazen také v obdobích jaro 2000, jaro 2002.