Detail předmětu

Algoritmy (v angličtině)

FIT-IALeAk. rok: 2024/2025

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ů

Garant předmětu

Ing. Ivana Burgetová, Ph.D.

Zajišťuje ústav

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

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

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

Doporučená literatura

Aho A.V., Hoppcroft J.E., Ullman J.D.: Data Structures and Algorithms, Addison Wesley, 1983.
Baase, S.: Computer Algorithms - Introduction to Design and Analysis. Addison Wesley, 1998
Cormen, T.H., Leiserson, Ch.E., Rivest, R.L.: Introduction to Algorithms, Cambridge: MIT Press, 2009
Horowitz, Sahni: Fundamentals of Data Structures in C, University Press, 2010
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

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 , 0 ročník, letní semestr, doporučený kurs

Typ (způsob) výuky

 

Přednáška

39 hod., nepovinná

Vyučující / Lektor

RNDr. Libor Škarvada
Ing. Radek Hranický, Ph.D.
prof. Ing. Jan M. Honzík, CSc.
Ing. Ivana Burgetová, 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
Ing. Ivana Burgetová, Ph.D.

Osnova

  • Dvě domácí úlohy

Elearning

eLearning: aktuální otevřený kurz