Detail předmětu

Algoritmy

FEKT-BPC-ALGAk. rok: 2020/2021

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

češ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 BPC-AMT bakalářský 0 ročník, zimní semestr, volitelný

  • Program BPC-AUD bakalářský

    specializace AUDB-TECH , 0 ročník, zimní semestr, volitelný
    specializace AUDB-ZVUK , 0 ročník, zimní semestr, volitelný

  • Program BPC-EKT bakalářský 0 ročník, zimní semestr, volitelný
  • Program BPC-IBE bakalářský 0 ročník, zimní semestr, volitelný
  • Program BPC-MET bakalářský 0 ročník, zimní semestr, volitelný
  • Program BPC-SEE bakalářský 0 ročník, zimní semestr, volitelný
  • Program BPC-TLI bakalářský 0 ročník, zimní semestr, volitelný

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

Projekt

13 hod., nepovinná

Vyučující / Lektor

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

Osnova

Domácí úlohy dvojic studentů
Projekt s miniobhajobou čtveřice studentů.