I502 Návrh algoritmů I

Fakulta informatiky
jaro 2000
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
Předpoklady
! U212 Návrh algoritmů pro VT IV
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
Osnova
  • Programovací paradigmata, výrazy, příkazy, stav programu.
  • Korektnost algoritmu, vstupní a výstupní podmínky, parciální korektnost, konvergence. Verifikační metody.
  • Růst funkcí. Rekursivní rovnice. Sčítání.
  • Délka výpočtu, složitost algoritmu, složitost problému.
  • Datové struktury (seznamy, stromy, grafy, pole).
  • Vyhledávání. Vyhledávací stromy, B-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, barvení.
  • Algoritmy dynamického programování.
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.
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 jaro 2001, jaro 2002.