Přeskočit na hlavní obsah
Přeskočit hlavičku
Ukončeno v akademickém roce 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.

Osnova předmětu

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.

Povinná literatura

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

Doporučená literatura

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