PředmětyPředměty(verze: 948)
Předmět, akademický rok 2023/2024
  
Algoritmy a grafy 1 - N500015
Anglický název: Algorithms and Graphs 1
Zajišťuje: ČVUT v Praze, Fakulta informačních technologií (500)
Fakulta: Vysoká škola chemicko-technologická v Praze
Platnost: od 2021
Semestr: zimní
Body: zimní s.:6
E-Kredity: zimní s.:6
Způsob provedení zkoušky: zimní s.:
Rozsah, examinace: zimní s.:2/2, Z+Zk [HT]
Počet míst: neurčen / neurčen (neurčen)
Minimální obsazenost: neomezen
Jazyk výuky: čeština
Způsob výuky: prezenční
Způsob výuky: prezenční
Úroveň:  
Je zajišťováno předmětem: B500008
Pro druh:  
Garant: Tvrdík Pavel prof. Ing. CSc.
Je záměnnost pro: B500008
Termíny zkoušek   Rozvrh   
Anotace
Poslední úprava: Jirát Jiří Ing. Ph.D. (23.01.2017)
Předmět pokrývá to nejzákladnější z efektivních algoritmů, datových struktur a teorie grafů, které by měl znát každý informatik. Spolupracuje se souběžně vyučovaným předmětem BI-ZDM, ve kterém studenti získají znalosti a dovednosti nezbytné pro vyhodnocování operační a paměťové složitosti algoritmů a naučí se prakticky používat asymptotickou matematiku.
Výstupy studia předmětu -
Poslední úprava: Svozil Daniel prof. Mgr. Ph.D. (29.03.2016)

Studenti budou umět:

  • budou mít důkladný přehled efektivních algoritmů pro řešení standardních problémů.
  • pracovat s asymptotickou notací používanou při vyjadřování složitosti.
  • budou rozumět algoritmům pro řazení o složitosti O(n.log n), pro speciální řazení s lineární složitostí a pro řazení ve vnějších pamětech, algoritmům asociativního a adresního vyhledávání (vyhledávací stromy, rozptýlené tabulky, vícerozměrné vyhledávací stromy).
  • znát a používat pokročilé datové struktury.
  • ovládat metody používané pro analýzu paměťové a operační složitosti algoritmů.
Literatura -
Poslední úprava: Jirát Jiří Ing. Ph.D. (23.01.2017)

Z:Cormen, T. H., Leiserson, C. E., Rivest, R. L. Introduction to Algorithms. The MIT Press, 2001. ISBN 0262032937.

Z:Handbook of Graph Theory, 2nd Edition (Discrete Mathematics and Its Applications). Chapman and Hall/CRC, 2013. ISBN 978-1439880180.

Sylabus
Poslední úprava: Jirát Jiří Ing. Ph.D. (23.01.2017)

Osnovy přednášek:

1. Motivace a úvod do teorie grafů

2. Základní definice a pojmy teorie grafů I 3. Základní definice a pojmy teorie grafů II

4. Řadící algoritmy O(n^2). Binární haldy a HeapSort.

5. Nafukovací pole, amortizovaná složitost, binomiální haldy

6. Vyhledávací stromy a jejich vyvažování

7. Pravděpodobnostní algoritmy a jejich složitost. QuickSort.

8. Rekurzivní algoritmy a metoda Rozděl a panuj. Lineární řazení

9. Rozptylování (hešování) a vyhledávací tabulky

10. Dynamické programování

11. Minimální kostry grafu

12. Nejkratší cesty v grafech

13. Rezerva

Osnovy cvičení:

1. Motivace a úvod do teorie grafů

2. Základní definice a pojmy teorie grafů I 3. Základní definice a pojmy teorie grafů II

4. Řadící algoritmy O(n^2). Binární haldy a HeapSort.

5. Nafukovací pole, amortizovaná složitost, binomiální haldy

6. Vyhledávací stromy a jejich vyvažování

7. Pravděpodobnostní algoritmy a jejich složitost. QuickSort.

8. Rekurzivní algoritmy a metoda Rozděl a panuj. Lineární řazení

9. Rozptylování (hešování) a vyhledávací tabulky

10. Dynamické programování

11. Minimální kostry grafu

12. Nejkratší cesty v grafech

13. Rezerva

Studijní prerekvizity -
Poslední úprava: Svozil Daniel prof. Mgr. Ph.D. (29.03.2016)

Předpokládá se schopnost aktivního algoritmického řešení základních typů úloh, znalost nějakého vyššího programovacího jazyka (Java, C++) a znalost základních pojmů z matematické analýzy a kombinatoriky.

Zátěž studenta
Činnost Kredity Hodiny
Účast na přednáškách 1 28
Práce na individuálním projektu 1.5 42
Příprava na zkoušku a její absolvování 1.1 30
Účast na seminářích 1 28
5 / 6 128 / 168
 
VŠCHT Praha