Přeskočit na hlavní obsah
Přeskočit hlavičku
Terminated in academic year 2002/2003

Základy algoritmizace (T)

Typ studia magisterské
Jazyk výuky čeština
Kód 456-0114/02
Zkratka ZALT
Název předmětu česky Základy algoritmizace (T)
Název předmětu anglicky Introduction to algorithms (T)
Kreditů 4
Garantující katedra Katedra informatiky
Garant předmětu RNDr. Daniela Szturcová, Ph.D.

Subject syllabus

Přednášky:
Pojem algoritmu. Konstanty, proměnné, výrazy, přiřazení. Návrh algoritmu. Řídicí struktury. Krokovací tabulka.
Princip číslicového počítače. Reprezentace čísel v číslicovém počítači. Číselné soustavy.
Základní datové typy. Vlastnosti datových typů. Jednoduché datové typy (boolean, číselné typy, znak) a operace nad nimi. Ukazatel.
Strukturované datové typy a operace nad nimi. Pole, struktura.
Abstraktní datové typy. Zásobník, fronta, graf (strom), stream, tabulka, seznam.
Implementace. Procedury a funkce.

Rekurze. Rekurzivní a nerekurzivní definice a algoritmus. Rekurzivní funkce.
Složitost. Dominantní operace, O(f) notace.
Třídění. Třídění přímým vkládáním, přímým výběrem. Bubble sort, Quick sort, Heap sort, Radix sort.
Vnější třídění. Princip slévání, Merge sort.
Hashing. Hashovací funkce, řešení kolizí. Separate chaining, Linear probing.
Vyhledávání. Sekvenční, binární vyhledávání. Vyhledávání k-tého prvku.
Vyhledávání podřetězce (Pattern Matching). Jednotlivé algoritmy.
Operace se stromy (vkládání, vyhledávíní, rušení uzlů). Průchody stromem. Operace vyvažování. Vybrané typy stromů (Red-Black stromy, B-stromy řádu n).
Zpracování aritmetických výrazů, prefix, infix a postfix.




Cvičení:
Cvičení navazuje na přednášky praktickými příklady.

Literature

Sylaby přednášek
Wirth, N.: Algoritmy a struktůry údajov, Alfa, Bratislava 1989
Topfer, P.: Algoritmy a programovací techniky, Prometheus, Praha 1995
Harel, D.: Algorithmics, The Spirits of Computing, Addison-Wesley Publishing Company, 1993
Virius, M.: Základy algoritmizace, ČVUT Praha, 1997, skripta
Sedgewick, R.: Algorithms in C++, Addison-Wesley Publishing Company, 1992

Advised literature

Sylaby přednášek v elektronické podobě.
Manuály programovacích jazyků.