Algorithms and Graphs 2

Vztahy:

Předmět BIE-AG2 nesmí být zapsán, je-li v témže semestru zapsán anebo již dříve absolvován předmět BIE-GRA (vztah je symetrický)

Předmět BIE-AG2 nesmí být zapsán, je-li v témže semestru zapsán anebo již dříve absolvován předmět BIE-AX2 (vztah je symetrický)

Garant předmětu:

Přednášející:

Cvičící:

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/

Pro tento předmět se rozvrh nepřipravuje

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

• Bachelor branch Security and Information Technology, in English, 2015-2020 (volitelný předmět)
• Bachelor branch Web and Software Engineering, spec. Software Engineering, in English, 2015-2020 (volitelný předmět)
• Bachelor branch Computer Science, in English, 2015-2020 (povinný předmět oboru)
• Bachelor specialization, Computer Engineering, 2021 (volitelný předmět)
• Bachelor specialization, Information Security, 2021 (volitelný předmět)
• Bachelor specialization, Software Engineering, 2021 (volitelný předmět)
• Bachelor specialization Computer Systems and Virtualization, 2021 (volitelný předmět)
• Bachelor branch Computer Science, in English, 2015-2020 original version (povinný předmět oboru)