Detail předmětu

Algorithms

FEKT-CALGAk. rok: 2011/2012

Přehled základních datových struktur a jejich použití.
Principy dynamického přidělování paměti.
Specifikace abtraktních datových typů (ADT).
Specifikace a implementace ADT: seznamy, zásobník, fronta, množina, pole, vyhledávací tabulka, graf, binární strom. Algoritmy nad binárním stromem.
Vyhledávání: sekvenční, v neseřazeném a seřazeném poli, vyhledávání se zarážkou, binární vyhledávání, binární vyhledávácí strom, vyvážený strom (AVL). Vyhledávání v tabulkách s rozptýlenými položkami.
Řazení, principy, řazení bez přesunu položek, řazení podle více klíčů. Nejznámější metody řazení: Select-sort, Bubble-sort, Heap-sort, Insert-sort a jeho varianty, Shell-sort, Quick sort v rekurzívní a nerekurzívní notaci, Merge-sort, List-merge-sort, Radix-sort. Sekvenční metody řazení. Rekurze a algoritmy s návratem. Vyhledávání podřetězců v textu. Dokazování programů, tvorba dokázaných programů.

Jazyk výuky

angličtina

Počet kreditů

5

Garant předmětu

prof. Ing. Jan M. Honzík, CSc.

Zajišťuje ústav

Fakulta informačních technologií (FIT)

Výsledky učení předmětu

Student se naučí analyzovat a navrhovat jednoduché algoritmy pro počítače. Seznámí se se základní koncepcí programovacích jazyků. Naučí se vytvářet programy ve vyšších programovacích jazycích. Porozumí EBNF pro popis syntaxe programovacího jazyka. Osvojí si odborné pojmy z oblasti programování, syntax a sémantiku programovacího jazyka.

Prerekvizity

Jsou požadovány znalosti na úrovni středoškolského studia.

Plánované vzdělávací činnosti a výukové metody

Metody vyučování závisejí na způsobu výuky a jsou popsány článkem 7 Studijního a zkušebního řádu VUT.

Způsob a kritéria hodnocení

Podmínky pro úspěšné ukončení předmětu stanoví každoročně aktualizovaná vyhláška garanta předmětu.

Osnovy výuky

1. Základy algoritmického jazyka. Přehled datových struktur. Abstraktní datový typ a jeho specifikace.
2. Specifikace, implementace a použití ADT seznam.
3. Specifikace, implementace a použití ADT zásobník, fronta. Vyčíslení výrazů s použitím zásobníku.
4. ADT pole, množina, graf, binární strom.
5. Algoritmy nad binárním stromem.
6. Vyhledávání, sekvenční, v poli, binární vyhledávání.
7. Binární vyhledávácí stromy, AVL strom.
8. Vyhledávání v tabulkách s rozptýlenými položkami.
9. Řazení, principy, bez přesunu, s vícenásobným klíčem.
10. Známé metody řazení polí I
11. Známé metody řazení polí II, řazení souborů.
12. Rekurze, algoritmy s návratem.
Dokazování správnosti programů, tvorba dokázaných programů.

Učební cíle

Seznámit se s metodami dokazování správnosti programů a s tvorbou dokázaných programů.
Seznámit se základními principy složitosti algoritmů.
Seznámit se základními abstraktními datovýni typy a strukturami, naučit se je implementovat a používat. Seznámit se s principy dynamického přidělování paměti. Naučit se rekurzívní a nerekurzívní zápisy základních algoritmů. Naučit se vytvářet a analyzovat algoritmy vyhledávání a řazení.

Vymezení kontrolované výuky a způsob jejího provádění a formy nahrazování zameškané výuky

Vymezení kontrolované výuky a způsob jejího provádění stanoví každoročně aktualizovaná vyhláška garanta předmětu.

Základní literatura

Aho A.V., Hoppcroft J.E., Ullman J.D.: Data Structures and Algorithms.
Amsbury, W: Data Structures: From Arrays to Priority Queues.
Baase, S.: Computer Algorithms - Introduction to Design and Analysis. Addison Wesley, 1998
Cormen, T.H. ,Leiserson, Ch.E., Rivest, R.L.: Introduction to Algorithms.
Honzík, J.,Hruška, T.,Máčel, M.: Vybrané kapitoly z programovacích technik, Ed.stř.VUT Brno,1991.
Horovitz, Sahni: Fundamentals of Data Structures.
Knuth, D.: The Art of Computer programming, Vol.1,2,3. Addison Wesley, 1968
Kruse, R.L.>Data Structures and Program Design. Prentice- Hall,Inc. 1984
Wirth, N.: Alorithms+Data Structures=Programs, Prentice Hall, 1976

Zařazení předmětu ve studijních plánech

  • Program EEKR-BC bakalářský

    obor BC-AMT , 3 ročník, zimní semestr, volitelný mimooborový

Typ (způsob) výuky

 

Přednáška

39 hod., nepovinná

Vyučující / Lektor

prof. Ing. Jan M. Honzík, CSc.

Osnova

Přehled datových struktur. Abstraktní datový typ a jeho specifikace.
Specifikace, implementace a použití ADT seznam.
Specifikace, implementace a použití ADT zásobník, fronta. Vyčíslení výrazů s použitím zásobníku.
ADT pole, množina, graf, binární strom.
Algoritmy nad binárním stromem.
Vyhledávání, sekvenční, v poli, binární vyhledávání.
Binární vyhledávácí stromy, AVL strom.
Vyhledávání v tabulkách s rozptýlenými položkami.
Řazení, principy, bez přesunu, s vícenásobnám klíčem.
Známé metody řazení polí
Známé motody řazení polí, řazení souborů.
Rekurze, algoritmy s návratem.
Dokazování správnosti programů, tvorba dokázaných programů.