PředmětyPředměty(verze: 878)
Předmět, akademický rok 2020/2021
  
Algoritmy a grafy 1 - B500008
Anglický název: Algorithms and Graphs 1
Zajišťuje: ČVUT v Praze, Fakulta informačních technologií (500)
Platnost: od 2020
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: neomezen / neomezen (neurčen)
Minimální obsazenost: neomezen
Jazyk výuky: čeština
Způsob výuky: prezenční
Úroveň:  
Pro druh: bakalářské
Garant: Tvrdík Pavel prof. Ing. CSc.
Valla Tomáš RNDr. Ph.D.
Záměnnost : N500015
Anotace -
Poslední úprava: Svozil Daniel doc. Mgr. Ph.D. (04.01.2019)
Předmět pokrývá základní principy tvorby efektivních algoritmů, datových struktur a teorie grafů, které by měl znát každý informatik.
Výstupy studia předmětu -
Poslední úprava: Kubová Petra Ing. (02.01.2018)

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: Kubová Petra Ing. (02.01.2018)

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: Svozil Daniel doc. Mgr. Ph.D. (04.01.2019)

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: Kubová Petra Ing. (02.01.2018)

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.

Podmínky zakončení předmětu
Poslední úprava: Svozil Daniel doc. Mgr. Ph.D. (07.02.2018)

Pro zı́skánı́ zápočtu je potřeba dostatek bodů ze semestrálního testu a z programovacích úloh. Zkouška se skládá z povinné pı́semné části a z volitelné ústnı́ části.

Zátěž studenta
Činnost Kredity Hodiny
Konzultace s vyučujícími 1 28
Účast na přednáškách 1 28
Práce na individuálním projektu 2 56
Příprava na zkoušku a její absolvování 1 28
Účast na seminářích 1 28
6 / 6 168 / 168
 
VŠCHT Praha