Algorithms and Graphs 2

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á, Maria Saumell Mendiola

Cvičící:

Jiřina Scholtzová, Maria Saumell Mendiola

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:

Information about the course and courseware are available at https://courses.fit.cvut.cz/BIE-AG2/

Další informace:

https://courses.fit.cvut.cz/BIE-AG2/

Rozvrh na zimní semestr 2020/2021:

Rozvrh není připraven

Rozvrh na letní semestr 2020/2021:

	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	místnost TH:A-1242 Scholtzová J. Saumell Mendiola M. 09:15–10:45 (přednášková par. 1) Thákurova 7 (FSv-budova A)místnost TH:A-1242 Scholtzová J. Saumell Mendiola M. 11:00–12:30 (přednášková par. 1 paralelka 101) Thákurova 7 (FSv-budova A)
St
Čt
Pá

Předmět je součástí následujících studijních plánů:

• Bc. Branch Security and Information Technology, Presented in English, Version 2015 to 2020 (volitelný předmět)
• Bc. Branch WSI, Specialization Software Engineering, Presented in English, Version 2015-2020 (volitelný předmět)
• Bc. Branch Computer Science, Presented in English, Version 2015 to 2020 (povinný předmět oboru)