Fakulta informačních technologií VUT v Brně

Detail předmětu

Algoritmy a datové struktury

ADS Ak. rok 2004/2005 letní semestr 7 kreditů

Předmět není v tomto roce otevřen
Zavřít
Úvod do algoritmizace. Základy složitosti algoritmu. Abstraktní datové struktury. Princip dynamického přidělování paměti. Abstraktní datové typy, jejich specifikace a implementace. Algoritmy vyhledávání. Algoritmy vnitřního a vnějšího řazení. Algoritmy pro zpracování textu. Rekurzívní a nerekurzívní zápis algoritmů. Dokazování programu a tvorba dokázaných programů.

Garant předmětu

Jazyk výuky

česky

Zakončení

zkouška (písemná)

Rozsah

39 hod. přednášky, 39 hod. projekty

Bodové hodnocení

Zajišťuje ústav

Přednášející

Cvičící

Cíle předmětu

Ovládnout návrh, specifikaci a implementaci abstraktních datových typů. Seznámit se a ovládnout nejvýznamnější algoritmy pro vyhledávání s náhodnám přístupem a se sekvenčním přístupem. Seznámit se a ovládnout nejvýznamnější algoritmy řazení polí a sekvenčních struktur. Seznámit se se základy dokazování správnosti algoritmů.

Literatura studijní

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

Literatura referenční

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

Osnova přednášek

  • Ú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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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
  • 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.
  • 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.
  • Ř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.
  • Ř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.

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

Průběžná kontrola studia

  • Půlsemestrální zkouška
  • 4 individuální domácí úlohy (projekty v Pascalu) na počítači zasílané elektronicky
Nahoru