PředmětyPředměty(verze: 838)
Předmět, akademický rok 2018/2019
  

Z důvodů aktualizace databázového systému bud o víkendu 15.12. - 16.12.  nedostupný studijní informační systém.

E-learning ( https://e-learning.vscht.cz ) bude fungovat, v případě výpadku pište na cis-support@vscht.cz

Děkujeme za pochopení,

Výpočetní centrum VŠCHT Praha

Algoritmy a grafy 1 - N500015
Anglický název: Algorithms and Graphs 1
Zajišťuje: ČVUT v Praze, Fakulta informačních technologií (500)
Platnost: od 2016
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 [hodiny/týden]
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í
Úroveň:  
Pro druh:  
Garant: Tvrdík Pavel prof. Ing. CSc.
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 doc. 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 doc. 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