Předmět Algoritmy a datové struktury (KSA / ADSP)

Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu KSA / ADSP - Algoritmy a datové struktury, Fakulta strojní, Technická univerzita v Liberci (TUL).

Materiál	Typ	Datum	Počet stažení

Obsah

PŘEDNÁŠKY :1. Abstrakce a implementace datových typů. Algebraická specifikace abstraktního typu dat - syntaktická část (signatura), sémantická část (množina axiomů). Příklady. Datové struktury s charakterem posloupnosti prvků stejného typu.2. Zásobník (paměť LIFO). Charakteristické operace, signatura a axiomy. Zjednodušené vyjádření sémantiky operací. Implementace zásobníku pomocí pole a pomocí dynamických proměnných. Použití zásobníků.3. Rekurse. Rekursivní definice a procesy. Jednoduché příklady - faktoriál, binární vyhledávání. Mechanismy realizace rekurse v symbolických jazycích. Nepřímá (vzájemná) rekurse. Rekursivní definice algebraických výrazů4. Praktická použití rekurse. Hanojské věže. Algoritmy prohledávání s návratem - problém osmi dam. Konverse zápisu výrazů.5. Simulace rekursivních algoritmů - konverse rekursivního řešení na nerekursivní. Příklad simulace na funkci faktoriál.6. Fronta (paměť FIFO). Operace a implementace fronty v symbolickém jazyku. Příklady použití fronty.7. Seznam. Vnitřní ukazatel, sémantika operací se seznamem. Implementace seznamu v symbolickém jazyku. Obousměrné propojení, kruhové seznamy, obousměrně propojené kruhové seznamy.8. Stromy. Binární stromy - definice, uzel, list, úroveň uzlu, úplné binární stromy, striktně binární stromy. Rekursivní definice průchodů binárními stromy.9. Použití binárních stromů - representace výrazů (infixový, prefixový a postfixový zápis výrazů), rychlé třídění pomocí binárních stromů, Huffmanův algoritmus.10. Vícecestné stromy a jejich aplikace. Representace vícecestných stromů v symbolickém jazyku. Les a metody průchodu. Strategické hry jako aplikace.11. Grafy. Grafy jako množiny uzlů a hran. Orientované a neorientované grafy. Sítě (ohodnocené grafy). Primitivní operace s grafy. Cesty - cyklické a acyklické grafy. Representace grafů. Transitivní uzávěr (Warshallův algoritmus).12. Aplikace grafů. Tok sítí (maximální tok sítí). Aplikace na problémy plánování. Topologické třídění. Síť PERTH.13. Tabulky, zavedení a typické operace s tabulkami. Tabulky s přímým a sekvenčním výběrem. Uspořádané tabulky. Rozptýlené tabulky14. Třídění. Porovnání různých metod třídění. Třídění transpozicí, výběrem, vkládáním, sléváním. Principy vnějšího třídění.CVIČENÍ :1. Procvičování práce s dynamickými proměnnými - příklad reversace posloupnosti symbolů, lineární uspořádaný seznam.2. Vytvoření vlastní implementace zásobníku.3. Použití zásobníku pro konversi infixového zápisu výrazu na postfixový zápis.4. Dokončení řešení zadání z předchozího cvičení.5. Zápis rekursivních funkcí - Euklidův algoritmus pro určení největšího společného dělitele dvou celých kladných čísel, rekursivní funkce pro nalezení maximálního prvku pole.6. Aplikace algoritmu prohledávání s návratem - problém nalezení cesty bludištěm.7. Aplikace kruhového seznamu ("Josephus problem").8. Dokončení řešení zadání z předchozích cvičení.9. Konverse rekursivní rutiny pro Fibonacciho posloupnost na iterační metodu.10. Aplikace binárních stromů - použití binárního stromu pro třídění posloupnosti celých čísel. Konstrukce Huffmanova stromu.11. Určení cest v digrafu daném maticí přiléhavosti. Spojová reprezentace grafů.12. Aplikace grafů na problémy plánování. Topologické třídění.13. Implementace uspořádaných tabulek - uspořádané tabulky organizované jako pole, uspořádané tabulky organizované jako kruhový seznam.14. Dokončení řešení zadání z předchozího cvičení. Zápočet.

Získané způsobilosti

Studenti se orientují v datových typech na vyšší úrovni abstrakce, v jejich použití a implementaci v symbolických jazycích.

Literatura

VĚCHET, V. Algoritmy a datové struktury. Stromy & grafy. Liberec, TU, 1997. VĚCHET, V. Počítače a programování. Díl III. Výběrový kurz Turbo Pascalu. Liberec, VŠST, 1994. VĚCHET, V. Rekursivní algoritmy v Pascalu. Liberec, VŠST, 1992.

Požadavky

Podmínkou udělení zápočtu je splnění všech zadaných úloh na cvičení. Zkouška je písemná a ústní.

Garant

Ing. Jan Kolaja, Ph.D.

Vyučující

Ing. Jan Kolaja, Ph.D.Ing. Jan Kolaja, Ph.D.Ing. Michal Moučka, Ph.D.Ing. Lukáš Stanislavprof. Ing. Vladimír Věchet, CSc.