Detail předmětu

Algoritmy (v angličtině)

IALe Ak. rok 2023/2024 letní 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, 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.

Garant předmětu

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

Přednášející

Cvičící

Cíle předmětu

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

Doporučené prerekvizity

Požadované prerekvizitní znalosti a dovednosti

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

Literatura studijní

  • 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

Osnova přednášek

  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.

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

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