SubjectsSubjects(version: 847)
Course, academic year 2018/2019
  
Algorithms and Graphs 1 - N500015
Title in English: Algoritmy a grafy 1
Guaranteed by: CTU in Prague, Faculty of Information Technology (500)
Actual: from 2016
Semester: winter
Points: winter s.:6
E-Credits: winter s.:6
Examination process: winter s.:
Hours per week, examination: winter s.:2/2 C+Ex [hours/week]
Capacity: unknown / unknown (unknown)
Min. number of students: unlimited
Language: Czech
Teaching methods: full-time
Level:  
For type:  
Guarantor: Tvrdík Pavel prof. Ing. CSc.
Annotation - Czech
Last update: 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.
Aim of the course -
Last update: Svozil Daniel doc. Mgr. Ph.D. (29.03.2016)

Students will be able to:

  • Understand a set of well-known standard algorithms
  • Recognize a proper algorithm variant for any specific usage
  • Use learn basic methods of algorithm analysis to be used as a main efficiency criterion
Literature -
Last update: Jirát Jiří Ing. Ph.D. (23.01.2017)

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

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

Syllabus - Czech
Last update: 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

Registration requirements -
Last update: Svozil Daniel doc. Mgr. Ph.D. (29.03.2016)

An ability to solve basic algorithmic problems actively, to express the algorithmic solution in a high-level programming language (Java, C++), and knowledge of basic notions from calculus and combinatorics is assumed.

Teaching methods
Activity Credits Hours
Úč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