Detail předmětu

Algoritmy (v angličtině)

IALe Ak. rok 2020/2021 zimní semestr 5 kreditů

Aktuální akademický rok

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

Honzík Jan M., prof. Ing., CSc. (UIFS)

Jazyk výuky

anglicky

Zakončení

zápočet+zkouška (písemná)

Rozsah

  • 39 hod. přednášky
  • 13 hod. projekty

Bodové hodnocení

  • 51 bodů závěrečná zkouška (písemná část)
  • 14 bodů půlsemestrální test (písemná část)
  • 35 bodů projekty

Zajišťuje ústav

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

Přednášející

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

Cvičící

Burgetová Ivana, Ing., Ph.D. (UIFS)
Křena Bohuslav, Ing., Ph.D. (UITS)
Masařík Karel, Ing., Ph.D. (CSC)

Získané dovednosti, znalosti a kompetence z 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

Cíle předmětu

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

Doporučené prerekvizity

Požadované prerekvizitní znalosti a dovednosti

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

Literatura studijní

  • 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

Osnova přednášek

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

Osnova ostatní - projekty, práce

  • Dvě domácí úlohy

Průběžná kontrola studia

  • 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í.

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

Nahoru