Název:	Programovací techniky
Zkratka:	PT
Typ:	povinně volitelný
Rozsah:	14 týdnů, týdně 2 hodiny přednášek + 2 hodiny seminárních cvičení
Způsob ukončení:	zkouška
Katedra:	katedra softwarového inženýrství FM TUL
Přednášející:	Ing. Jan Cvejn, Ph.D.

 
Stručná anotace předmětu:

Předmět se zaměřuje na implementaci a využití nejčastěji se vyskytujících datových struktur a souvisejících algoritmů.

 
Témata přednášek:

Základní (statické) datové struktury a elementární datové typy.
Jednorozměrná a vícerozměrná pole. Uložení v paměti. Mapovací funkce. Efektivita přístupu.
Speciální implementace pole. Položky proměnné délky. Přístupový vektor. Iliffovy vektory. Řídká pole.
Sekvenční a binární vyhledávání. Algoritmy řazení polí. Přirozenost a stabilita řazení. Efektivita algoritmů třídění.
Přehled nejpoužívanějších metod řazení polí.
Sekvenční soubory. Základní operace. Algoritmy řazení souborů. Jednocesté a vícecesté setřiďování. Polyfázové třídění. Využití hromady pro řazení souborů.
Tabulky a vyhledávání. Transformační funkce. Tabulky s rozptýlenými položkami. Asociativní pole.
Dynamické datové struktury. Jednosměrné a vícesměrné seznamy. Implementace a využití seznamů.
Zásobník a fronta. Využití zásobníku v rekurzivních algoritmech. Implementace zásobníku a fronty.
Stromové struktury. Binární vyhledávací stromy. Algoritmy prohledávání stromů.
Vyvážené a výškově vyvážené vyhledávací stromy. Optimální vyhledávací stromy.
Kořenový strom. Způsoby implementace. B-stromy.
Prohledávání stavového prostoru. Prohledávání do hloubky a do šířky. Dynamické programování.

 
Náplň cvičení:

Cvičení jsou zaměřena na praktickou realizaci vybraných datových struktur a algoritmů a jejich funkční využití v aplikacích.

 
Literatura:

N. Wirth - Algoritmy a štruktúry údajov , Alfa, 1987

J. Rychlík - Programovací techniky, Kopp, 1993

 
Prerekvizity: -

Navazující:    -

 
Datum poslední změny: 19.12.2001