I002 Návrh algoritmů I

Fakulta informatiky
jaro 1999
Rozsah
2/0. 2 kr. Doporučované ukončení: zk. Jiná možná ukončení: k, z.
Vyučující
RNDr. Libor Škarvada (přednášející)
Garance
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 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
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. Třídy P, NP.
  • 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
  • CORMEN, Thomas H., Charles Eric LEISERSON a Ronald L. RIVEST. Introduction to algorithms. Cambridge: MIT Press, 1989, xvii, 1028. ISBN 0070131430. info
Informace učitele

Letos (1999 léto) je vždy ve středu od 18 hodin v posluchárnách D1 a D2.
K disposici budou stručná shrnutí přednášek (ps, pdf, dvi, 2.ps, 4.ps) v průběhu semestru postupně doplňovaná.
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 2000, jaro 2001, jaro 2002, jaro 2003.