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.
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.