Detail předmětu

Algoritmy (v angličtině)

FIT-IALeAk. rok: 2019/2020

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

Ústav informačních systémů (UIFS)

Nabízen zahradničním studentům

Všech fakult

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

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

  • Student se nučí odborné terminologii v českém i anglickém jazyce
  • Student se naučí vytvářet malé projekty v malém týmu
  • Student se naučí prezentaci a obhajobě výsledků v malém projektu

Prerekvizity

  • Znalost základů programování v procedurálně orientovaném programovacím jazyce. ZNALOSTI A KOMPETENCE V ZÁKLADECH PROGRAMOVÁNÍ (C, Pascal aj.) BUDOU NA ZAČÁTKU VÝUKY PŘEZKOUŠENY. NEDOSTATEČNÉ ZNALOSTI POVEDOU KE ZRUŠENÍ PŘÉDMĚTU !!!
  • Středoškolské znalosti z matematiky.

Způsob a kritéria hodnocení

  • Dvě opravované domácí úlohy - 25 bodů
  • Půlsemestrální písemná zkouška - 14 bodů
  • Vypracování krátkých příkladů během přednášek - max 10 bodů
  • Závěrečná písemná zkouška - 51 bodů

Podmínky zápočtu:
  • získání minimálně 15 bodů za semestr

  • Pokud bude odhaleno plagiátorství nebo nedovolená spolupráce na projektech či domácích úlohách, zápočet nebude udělen a dále bude zváženo zahájení disciplinárního řízení.

Učební cíle

Seznámit se s principy metod dokazování správnosti programů a s tvorby dokázaných programů. Seznámit se základními principy složitosti algoritmů. Seznámit se s principy dynamického přidělování paměti. Seznámit se základními abstraktními datovými typy a strukturami, naučit se je implementovat a používat.  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í.

Prerekvizity a korekvizity

Doporučená literatura

Amsbury, W: Data Structures: From Arrays to Priority Queues.
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.
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 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

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

  • Program IT-BC-1H bakalářský

    obor BCH , libovolný ročník, zimní semestr, doporučený

Typ (způsob) výuky

 

Přednáška

39 hod., nepovinná

Vyučující / Lektor

Ing. Ivana Burgetová, Ph.D.
prof. Ing. Jan M. Honzík, CSc.
Ing. Karel Masařík, Ph.D.

Osnova

  • Základy algoritmického jazyka. 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í I
  • Známé metody řazení polí II, řazení souborů.
  • Rekurze, algoritmy s návratem.
  • Dokazování správnosti programů, tvorba dokázaných programů.

Projekt

13 hod., povinná

Vyučující / Lektor

Ing. Ivana Burgetová, Ph.D.
Ing. Bohuslav Křena, Ph.D.
Ing. Karel Masařík, Ph.D.

Osnova

  • Dvě domácí úlohy