Detail předmětu

Algoritmy

IAL Ak. rok 2024/2025 zimní semestr 5 kreditů

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

Garant předmětu

Koordinátor předmětu

Jazyk výuky

česky, 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

Přednášející

Cvičící

Cíle předmětu

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

Doporučené prerekvizity

Požadované prerekvizitní znalosti a dovednosti

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

Literatura studijní

  • Mareš, M., Valla, T.: Průvodce labyrintem algoritmů, CZ.NIC, 2017, ISBN 978-80-88168-19-5, http://pruvodce.ucw.cz/
  • Honzík, J., Hruška, T., Máčel, M.: Vybrané kapitoly z programovacích technik, Ed. stř. VUT Brno, 1991
  • 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
  • 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
  • Sedgewick,R.:Algoritmy v C, Addison Wesley 1998, Softpress 2003

Osnova přednášek

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

Osnova ostatní - projekty, práce

  • Dvě domácí úlohy - implementace operací vybraných ADT.
  • Projekt s miniobhajobou skupiny studentů.

Průběžná kontrola studia

  • Domácí úlohy - 20 bodů
  • Půlsemestrální písemná zkouška - 14 bodů
  • Hodnocený projekt s obhajobou - 15 bodů
  • Zápočet - podmínkou pro udělení zápočtu je získání minimálně 20 bodů za semestr
  • Závěrečná písemná zkouška - 51 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ě 24 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í:

  • U domácí úlohy může student požádat příslušného učitele o přiměřené prodloužení termínu pro odevzdání domácí úlohy.
  • 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ň 14 bodů za domácí úlohy a 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.

Rozvrh

DenTypTýdnyMístn.OdDoKapacitaPSKSkupInfo
Út zkouška 2024-10-15 E104 E105 E112 12:0013:00 Půlsemestrální zkouška - úterý 12:15
Út přednáška 1., 2., 4., 5., 6., 7., 8., 9., 10., 11., 12. výuky E104 E105 E112 12:0014:50320 2BIB 3BIT 20 - 29 xx Burgetová
Út přednáška 2024-10-01 E104 E105 E112 12:0014:50320 2BIB 3BIT 20 - 29 xx Hranický
Út přednáška 2024-12-10 E104 E105 E112 12:0014:50320 2BIB 3BIT 20 - 29 xx Křena
St přednáška 1., 2., 3., 4., 5., 6., 8., 9., 10., 11., 12. výuky D105 18:0020:50316 2BIA 3BIT 10 - 19 xx Hranický
St přednáška 2024-10-30 D105 18:0020:50316 2BIA 3BIT 10 - 19 xx Burgetová
St přednáška 2024-12-11 D105 18:0020:50316 2BIA 3BIT 10 - 19 xx Křena
St zkouška 2024-10-16 D105 18:1519:15 Půlsemestrální zkouška - středa 18:15
St zkouška 2024-10-16 D105 19:2020:20 Půlsemestrální zkouška - středa 19:20
Čt ostatní 2024-10-31 C236 12:0023:59 Zápočet
ostatní 2024-11-01 C236 00:0013:00 Zápočet

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

Nahoru