Algoritmy a datové struktury

1. Úvod: Cíl předmětu, formy výuky, účast na výuce, pravidla hodnocení, přednáška, domácí cvičení a zadání, půlsemestrální a závěrečná zkouška, prémiové úkoly. Algoritmy a datové struktury. Složitost algoritmu a datové struktury. Typy řídicích struktur algoritmu a jejich užití. Typy datových struktur a jejich užití. Vlastnosti a klasifikace algoritmů a datových struktur. Zdroj: soubory na www stránkách.
2. Dynamické přidělování paměti (DPP) - bez regenerace , s regenerací s využitím zřetězeného zásobníku , princip "garbage collectoru". Jiné metody. Uživatelská implementace DPP (UDPP) - bez regenerace (v poli s operacemi init, new, neúčinné dispose, mark a release s regenerací (zřetězený zásobník). Implementace dynamických struktur v nepascalovském prostředí s využitím uživatelského DPP.
3. Datové struktury, statické, dynamické, homogenní, heterogenní; konstruktor, selektor. Dynamické struktury Pascalu, seznamy (jednosměrný, dvojsměrný, kruhový hlavička seznamu). ATD - syntaktická a sémantická specifikace, diagramy signatury. ATD seznam - jednosměrný, dvousměrný, kruhový, dvojsměrný seznam v poli s jedním ukazatelem, seznamy s hlavičkou, bez hlavičky, operace, principy implementace. Základní operace, některé další operace (ekvivalence, relace uspořádání, počet prvků, uchování a obnova aktivity, kopie, destrukce, inserce podseznamu, rušení podseznamu, konkatenace, dekatenace aj.). Zdroj: Přednáška, skripta VKPT kap.5.
4. Seznamy - práce s ukazateli. ATD seznam - jednosměrný, dvousměrný, kruhový, seznamy s hlavičkou, bez hlavičky, operace, principy implementace. Seznam a rekurze.
5. ATD zásobník. Užití zásobníku: algoritmy s návratem, rekurze, bloková struktura a dynamické přidělování paměti, převod z infixové do postfixové notace se zásobníkem, vyčislování aritmetických výrazů v postfixové notaci se zásobníkem. ATD fronta a její užití. Implementace zásobníku a fronty. ATD pole, jedno a vícedimenzionální, statické a dynamické, přístupové metody k prvku pole (mapovací funkce, informační vektor/záznam). Prostorově úsporné metody implementace některých polí - trojúhelníková matice, pole s nestejně dlouhými řádky, řídké pole. ATD množina. Zdroj: Přednáška, skripta PT kap. 5.
6. Průchody binárním stromem. Rekurzivní a nerurzivní zápis průchodových algoritmů. Stromové etudy - implementace některých operací nad BS (ekvivalence struktu dvou BS, ekvivalence dvou BS, kopie BS, destrukce BS, počet listů BS, výška BS, nalezení nejdelší cesty od kořene k listu, váhová/výšková vyváženost stromu). Zdroj: Přednáška, skripta PT kap. 5.
7. Vyhledávání I. Klasifikace metod. Sekvenční vyhledávání v souboru, poli, seznamu. Použití zarážky. Využití seřazení podle pravděpodobnosti vyhledávání, Adaptivní řazení podle pravděpodobnosti četnosti vyhledávání v poli seřazeném podle klíče. Binární vyhledávání, Dijkstrova metoda, uniformní binární vyhledávání, Sharova metoda, Fibonacciho vyhledávání. Zdroj: přednáška, skripta VKPT kap. 6
8. Vyhledávání II. Binární vyhledávací stromy (BVS). Rekurzivní i nerekurzívní verze operací nad BVS. BVS se zpětnými ukazateli. AVL stromy. Zdroj: přednáška, skripta VKPT kap 6.
9. Vyhledávání III. Tabulky s přímým přístupem, princip indexsekvenčního vyhledávání. Tabulky s rozptýlenými položkami (TRP). Vlastnosti a konstrukce rozptylovací (hashovací) funkce. TRP s explicitním a implicitním zřetězením synonym. Metoda dvojí rozptylové funkce. Hodnocení metod vyhledávání. Řazení I. Základní pojmy: stabilita, přirozenost, časová a prostorová složitost algoritmu řazení. Řazení podle více klíčů, řazení bez přesunu položek. MacLarenova metoda. Zdroj: přednáška, skripta VKPT kap 6.,7.
10. Řazení II. Klasifikace principů řazení. Řazení na principu výběru - Bubble-sort a jeho varianty, Heap sort. Řazení II. Řazení polí na principu vkládání, "Bubble-Insert sort", "Binary-insert sort". "Quick sort"; "Shell sort"; "Merge sort"; "List merge sort", "Radix sort". Zdroj: přednáška, skripta VKPT kap 7.
11. Řazení III. Hodnocení metod řazení polí. Princip řazení sekvenčních souborů. 3 a 4 pásková metoda řazení sekvenčních souborů - přímá a přirozená. Mnohacestné vyvážené setřiďování, polyfázové setřidování. Hodnocení metod řazení sekvenčních souborů. Vyhledávání v řetězcích. Knuth-Morris-Prattův algoritmus, Boyer-Mooreův algoritmus.

    Zdroj: přednáška, skripta VKPT kap 7. Zdroj: přednáška; soubor na síti.

12. Rekurse, principy typických rekurzivních algoritmů;převod mezi rekursívním a nerekursívním zápisem algoritmu; Hanoiské věže, 8 dam, cesta koně, rekurse v grafice (Hilbertovy křivky). Zdroj: přednáška; soubor na síti.
13. Dokazování správnosti programu. Tvorba dokázaných programů I (Dijkstra). Zdroj: Přednáška, Skripta Vybrané kapitoly z programovacích technik (VKPT) kap.15., soubor na síti.

1. 4 domácí úlohy
2. 1 projekt s prezentací a obhajobou

1. Honzík,J. a kolektiv: Programovací techniky. Skriptum VUT v Brně
2. Honzík,J.,Hruška,T.,Máčel,M.: Vybrané kapitoly z rogamovacích technik

1. Úplný soubor studijních podkladů na internetové adrese dostupné studentům zapsaným do kurzu.