FI:I002 Návrh algoritmů I - Informace o předmětu

I002 Návrh algoritmů I

Fakulta informatiky
jaro 2002

Rozsah

2/0. 2 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: k, z.

Vyučující

Garance

Rozvrh

Út 18:00–19:50 D1, Čt 9:00–10:50 D1

Předpoklady

! U212 Návrh algoritmů pro VT IV && (! I502 Návrh algoritmů I )&&(!NOW( I502 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.

Navazující předměty

Informace učitele

http://www.fi.muni.cz/usr/skarvada/vyuka/I002/

Další komentáře

Předmět je vyučován každoročně.