Detail předmětu

Algoritmy

FEKT-BPC-ALGAk. rok: 2018/2019

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

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.

Literatura

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

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.

Jazyk výuky

čeština

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

Cíl

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.

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

  • Program BPC-AUD bakalářský

    specializace AUDB-TECH , libovolný ročník, zimní semestr, 5 kreditů, volitelný

  • Program BPC-AMT bakalářský, libovolný ročník, zimní semestr, 5 kreditů, volitelný
  • Program BPC-EKT bakalářský, libovolný ročník, zimní semestr, 5 kreditů, volitelný
  • Program BPC-IBE bakalářský, libovolný ročník, zimní semestr, 5 kreditů, volitelný
  • Program BPC-MET bakalářský, libovolný ročník, zimní semestr, 5 kreditů, volitelný
  • Program BPC-SEE bakalářský, libovolný ročník, zimní semestr, 5 kreditů, volitelný
  • Program BPC-TLI bakalářský, libovolný ročník, zimní semestr, 5 kreditů, volitelný

Typ (způsob) výuky

 

Přednáška

39 hod., nepovinná

Vyučující / Lektor

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

Ostatní aktivity

13 hod., nepovinná

Vyučující / Lektor

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