Detail předmětu

Algoritmy

FIT-IAL Ak. rok: 2027/2028 Zimní semestr

Přehled základních datových struktur a jejich použití. Časová složitost algoritmů – úvod. Specifikace abstraktní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ávací strom, vyvážený strom (AVL), stromy s více klíči ve vrcholech. 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 rekurzivní a nerekurzivní notaci, Merge-sort, Radix-sort. Rekurze a dynamické programování. Vyhledávání podřetězců v textu. Grafové algoritmy. Dokazování programů. 

5 kreditů, t.j. cca 125-150 hodin představuje studijní zátěž:

  • 39 hodin přednášek
  • 26 hodin 2 domácí úlohy
  • 35 hodin práce na projektu
  • 20 hodin průběžné studium
  • 30 hodin příprava na půlsemestrální a závěrečnou zkoušku

Jazyk výuky

čeština

Počet kreditů

5

Garant předmětu

Ing. Ivana Burgetová, Ph.D.

Zajišťuje ústav

Ústav informačních systémů

Vstupní znalosti

  • Znalost základů programování v procedurálně orientovaném programovacím jazyce.
  • Středoškolské znalosti z matematiky.

Způsob zakončení předmětu a pravidla hodnocení studentů

  • Půlsemestrální písemná zkouška – 20 bodů
  • Hodnocený projekt s obhajobou – 15 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 – 65 bodů; Pro získání bodů ze závěrečné písemné zkoušky je nutné zkoušku vypracovat tak, aby byla hodnocena nejméně 30 body. V opačném případě bude zkouška hodnocena 0 body.

 

 

Pokud v průběhu semestru student onemocní nebo se vyskytne jiná překážka ve studiu, je třeba tuto překážku řádně ohlásit a doložit. Pak k ní lze přihlédnout a přizpůsobit jí hodnocení:

  • Pokud se student nemohl zúčastnit půlsemestrální zkoušky, může svého přednášejícího požádat, aby body za půlsemestrální zkoušku byly odvozeny od bodového zisku u prvního termínu zkoušky, kterého se zúčastní. Podmínkou pro přistoupení k tomuto termínu zkoušky je zisk alespoň 6 bodů za projekt.
  • Pokud se student nemůže zúčastnit obhajoby projektu a ostatní členové týmu s tím vysloví souhlas, může získat za obhajobu stejný počet bodů jako na obhajobě přítomní členové týmu.

Učební cíle

Student porozumí základním principům složitosti algoritmů a bude je schopen využít při tvorbě programů. Student porozumí základním abstraktním datovým typům a strukturám, naučí se je implementovat a používat. Student se naučí  rekurzivní a nerekurzivní zápisy základních algoritmů a bude schopen je využívat při tvorbě programů. Student se naučí vytvářet a analyzovat algoritmy vyhledávání a řazení. Student porozumí základním algoritmům pro vyhledávání v textu a základním grafovým algoritmům. Student se seznámí s rekurzivním způsobem řešení problémů a se základy dynamického programování. Student porozumí principům metod dokazování správnosti programů a znalosti bude schopen používat při tvorbě 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.
  • Naučí se rekurzivní a nerekurzivní zápisy základních algoritmů.
  • Seznámí se s různými variantami vyhledávacích tabulek a porozumí jejich vlastnostem.
  • Naučí se vytvářet a analyzovat algoritmy vyhledávání a řazení.
  • Student se naučí 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.
  • Student porozumí významu metod dokazování správnosti programů a tvorby dokázaných programů.

Použití předmětu ve studijních plánech

Program B-MAI-P: Matematické inženýrství, bakalářský, volitelný

Typ (způsob) výuky

 

Přednáška

39 hod., nepovinná

Osnova


  1. Přehled datových struktur. Časová složitost algoritmů.

  2. Abstraktní datový typ a jeho specifikace. Specifikace, implementace a použití ADT seznam.

  3. Specifikace, implementace a použití ADT zásobník, fronta, vzhledávací tabulka. Vyčíslení výrazů s použitím zásobníku.

  4. Algoritmy nad binárním stromem.

  5. Vyhledávání, sekvenční, v poli, binární vyhledávání, binární vyhledávací stromy, AVL strom.

  6. Stromy s více klíči ve vrcholech. Vyhledávání v tabulkách s rozptýlenými položkami.

  7. Řazení, principy, bez přesunu položek, s vícenásobným klíčem.

  8. Známé metody řazení polí I

  9. Vyhledávání v textu.

  10. Rekurze a dynamické programování.

  11. Grafové algoritmy.

  12. Dokazování správnosti programů.

Projekt

13 hod., povinná

Osnova


  • Dvě domácí úlohy – implementace operací vybraných ADT.

  • Projekt s miniobhajobou skupiny studentů.

Individuální příprava na půlsemestrální zkoušku

13 hod., nepovinná

Osnova

Individuální příprava na závěrečnou zkoušku

26 hod., nepovinná

Osnova

Individuální příprava na vypracování projektu

26 hod., nepovinná

Osnova

Individuální příprava – vypracování zadaných úkolů

13 hod., nepovinná

Osnova