Název:

Algoritmy a datové struktury

Zkratka:ADS
Ak.rok:ukončen 2004/2005 (není otevřen)
Semestr:letní
Vyučovací jazyk:čeština
Informace veřejné:http://www.fit.vutbr.cz/study/courses/ADS/public/
Informace pro zapsané:http://www.fit.vutbr.cz/study/courses/ADS/private/
Kredity:7 kreditů
Ukončení:zkouška (písemná)
Výuka:
hod./sempřednáškasem./cvič.lab. cvič.poč. cvič.jiná
Rozsah:3900039
 zkouškatestycvičenílaboratořeostatní
Body:00000
Garant:Honzík Jan M., prof. Ing., CSc. (UIFS)
Přednášející:Honzík Jan M., prof. Ing., CSc. (UIFS)
Cvičící:Křena Bohuslav, Ing., Ph.D. (UITS)
Fakulta:Fakulta informačních technologií VUT v Brně
Pracoviště:Ústav informačních systémů FIT VUT v Brně
 
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ů.
Anotace:
  Ú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ů.
Osnova přednášek:
 
  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.
Osnova laboratorních cvičení:
 
  1. 4 domácí úlohy
  2. 1 projekt s prezentací a obhajobou
Literatura referenční:
 
  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
Literatura studijní:
 
  1. Úplný soubor studijních podkladů na internetové adrese dostupné studentům zapsaným do kurzu.
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
 

Vaše IPv4 adresa: 52.200.130.163
Přepnout na https