I002 Návrh algoritmů I

Fakulta informatiky
léto 1997
Rozsah
2/2. 4 kr. Doporučované ukončení: zk. Jiná možná ukončení: k, z.
Vyučující
doc. RNDr. Renata Ochranová, CSc. (přednášející)
Garance
Kontaktní osoba: doc. RNDr. Renata Ochranová, CSc.
Předpoklady
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. 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í.
Předmět je zařazen také v obdobích zima 1995, léto 1996, zima 1996, zima 1997, léto 1998, jaro 1999, jaro 2000, jaro 2001, jaro 2002, jaro 2003.