Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2018/2019

Algorithms and Graphs 2

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah Jazyk výuky
BIE-AG2 Z,ZK 5 2P+2C
Předmět nesmí být zapsán současně s:
Graph Algorithms and Complexity Theory (BIE-GRA)
Přednášející:
Jiřina Scholtzová (gar.)
Cvičící:
Jiřina Scholtzová (gar.)
Předmět zajišťuje:
katedra teoretické informatiky
Anotace:
Požadavky:
Osnova přednášek:

1. Euler graphs, dominating and independent sets, colorability, distance.

2. All-pairs shortest-path algorithms.

3. Advanced network flow algorithms (inluding circulation).

4. Matching problem, Hall's matching theorem.

5. State space search, heuristics.

6. Hamilton circuit problem and the TSP problem (approximation algorithms).

7. Randomized algorithms.

8. Advanced balanced search trees - RB trees.

9. Advanced heaps (nbinomial, Fibonnaci), amortized complexity analysis.

10. B-trees.

11. Computational geometry algorithms.

12. Graphs drawing algorithms.

13. String matching agorithms.

Osnova cvičení:
Cíle studia:

The course is a continuation of the BIE-AG1 compulsory course. It covers advanced topics from the graph theory, algorithms, and data structures. It includes randomized and approximation algorithms and amortized complexity analysis.

Studijní materiály:

[1] Cormen, T. H. - Leiserson, C. E. - Rivest, R. L. - Stein, C.: Introduction to Algorithms, 3rd Edition, MIT Press, 2009, 978-026203384,

[2] Joyner, D. - et al.: Algorithmic Graph Theory and Sage (Version 0.8-r1991), http://code.google.com/p/graphbook/, 2014,

[3] Gross, J. L. - Yellen, J.: Graph Theory and Its Applications, 2nd Edition, Chapman and Hall, 2005, 158488505X,

Poznámka:

2++2

Rozvrh na zimní semestr 2018/2019:
Rozvrh není připraven
Rozvrh na letní semestr 2018/2019:
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po
Út
St
místnost T9:347
Scholtzová J.
11:00–12:30
(přednášková par. 1)
Dejvice
NBFIT učebna
místnost T9:347
Scholtzová J.
12:45–14:15
(přednášková par. 1
paralelka 101)

Dejvice
NBFIT učebna
Čt

Předmět je součástí následujících studijních plánů:
Platnost dat k 23. 7. 2019
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet3464406.html