Detail předmětu

Algoritmy (v angličtině)

FIT-IALeAk. rok: 2023/2024

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, vyhledávací tabulka. 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.

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

Vstupní znalosti

  • Znalost základů programování v procedurálně orientovaném programovacím jazyce (pro řešení domácích úloh je nezbytná znalost programovacího jazyka C). 
  • Středoškolské znalosti z matematiky.

Pravidla hodnocení a ukončení předmětu

  • 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 - 10 bodů
  • Zápočet - podmínkou pro udělení zápočtu je získání minimálně 15 bodů za semestr.
  • Závěrečná písemná zkouška - 51 bodů

Učební cíle

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

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

Prerekvizity a korekvizity

Doporučená literatura

Cormen, T.H., Leiserson, Ch.E., Rivest, R.L.: Introduction to Algorithms, Cambridge: MIT Press, 2009
Knuth, D.: The Art of Computer programming, Vol.1,2,3. Addison Wesley, 1968
Wirth, N.: Alorithms+Data Structures=Programs, Prentice Hall, 1976
Horowitz, Sahni: Fundamentals of Data Structures in C, University Press, 2010
Aho A.V., Hoppcroft J.E., Ullman J.D.: Data Structures and Algorithms, Addison Wesley, 1983.
Kruse, R.L.: Data Structures and Program Design. Prentice- Hall,Inc. 1984
Baase, S.: Computer Algorithms - Introduction to Design and Analysis. Addison Wesley, 1998

eLearning

eLearning: aktuální otevřený kurz

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

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

    specializace BCH , libovolný ročník, letní 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. Radek Hranický, Ph.D.

Osnova

  1. Přehled datových struktur, úvod do způsobů hodnocení časové složitosti algoritmů.
  2. Abstraktní datový typ a jeho specifikace.
  3. Specifikace, implementace a použití ADT seznam.
  4. Specifikace, implementace a použití ADT zásobník, fronta. Vyčíslení výrazů s použitím zásobníku.
  5. ADT vyhledávací tabulka.
  6. Binární strom, algoritmy nad binárním stromem.
  7. Vyhledávání, sekvenční, v poli, binární vyhledávání.
  8. Binární vyhledávácí stromy, AVL strom.
  9. Vyhledávání v tabulkách s rozptýlenými položkami.
  10. Řazení, principy, bez přesunu, s vícenásobným klíčem.
  11. Známé metody řazení polí I
  12. Známé metody řazení polí II.

Projekt

13 hod., povinná

Vyučující / Lektor

Ing. Daniel Dolejška
Ing. Jan Zavřel

Osnova

  • Dvě domácí úlohy

eLearning

eLearning: aktuální otevřený kurz