I4130 Návrh algoritmů

Přírodovědecká fakulta
jaro 2000
Rozsah
2/2/0. 5 kr. Ukončení: zk.
Vyučující
RNDr. Libor Škarvada (přednášející)
Garance
RNDr. Libor Škarvada
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: RNDr. Libor Škarvada
Omezení zápisu do předmětu
Předmět je určen pouze studentům mateřských oborů.
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. Nejktatší cesta, minimální kostra, barvení. Algoritmy dynamického programovýní.
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.