Témata ke zkoušce
Základní abstraktní datové typy a jejich implementace v Javě (zásobník, fronta, obousměrná fronta, vektor, seznam)
Tabulky s rozptýlenými položkami - vytvoření tabulky, vyhledávání, hash funkce
Stromové struktury (BVS, AVL, B-strom) – vytvoření, algoritmy vložení a rušení prvků
Red-Black stromy- znát vlastnosti, umět vkládat prvky
Vyhledávání řetězců v textu (algoritmus BF, KMP, Boayer-Moore, Rabin-Karp), umět vytvořit funci last (u BM algoritmu), a fail (u KMP)
Datová struktura trie (umět vytvořit trie, suffix trie a compressed trie), znát princip LCS a SCS umět najít LCS a SCS u dvou zadaných řetězců,
Algoritmus výpočtu vzdáleností mezi řetězci - znát princip a umět určit vzdálenost mezi dvěma řetězci
Algoritmy komprese textů (RLE, LZW, Huffman, Aritmetické kódování) – znát princip a umět zakódovat zadaný textový řetězec
Algoritmy ztrátové komprese obrazů ( JPEG, waveletová, fraktálová, komprese) znát princip
Grafy - reprezentace grafu, grafové algoritmy ( Dijkstra, Floyd-Warshal, minimální kostra grafu (Prim-Jarnik))
Šifrování – znát princip symetrického a asymetrického šifrování a elektronického podpisu, umět používat jednoduché substituční šifrování
Bucket sort, radix sort, mediány statistiky n-tého řádu – znát princip metod, umět používat metody
Kombinatorické algoritmy – znát princip algoritmů generování n-tic, permutací, kombinací, Grayův kód
Příklad zkouškové písemky z minulých let. Př.1 a Př. 2 již nejsou aktuální a budou nahrazeny jiným tématem (grafové algoritmy a algoritmy zpracování textů).
Poslední změna:
22.09.2016