Studenti budou umět:

budou mít základní přehled o používání grafových modelů v informatice, se zaměřením především na algoritmické otázky a řešení grafových problémů.

budou se orientovat i v dalších tématech, která tento přehled doplňují o specifické aplikace nebo postupy (toky v sítích, heuristické hledání, aproximační algoritmy) nebo se týkají obecnější problematiky algoritmické řešitelnosti a složitosti úloh (Turingovy stroje, NP úplné problémy).

Students will be able to:

Recognize which graph model is appropriate and which algorithm should be used when solving a specific problem.

Find or estimate bounds of algorithmic complexity or limits of practical solvability of some types of problems.

Z:Kolář, J. Teoretická informatika. Praha: Česká informatická společnost, 2000. ISBN 80-900853-8-5.

Z:Demel, J. Grafy a jejich aplikace. Praha: Academia, 2002. ISBN 80-200-0990-6.

R:Kolář, J. Theoretical Computer Science. Praha: ČVUT, 1998. ISBN 80-01-01788-5.

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

https://edux.fit.cvut.cz/courses/BI-GRA/

(nutné přihlášení)

https://edux.fit.cvut.cz/courses/BI-GRA/

(login necessary)

1. Grafové modely, neorientované grafy, izomorfismus.

2. Sousednost, souvislost, orientované grafy.

3. Silná souvislost, acyklické grafy, reprezentace grafů, procházení do šířky.

4. Procházení do hloubky, topologické uspořádání, silně souvislé komponenty.

5. Eulerovy grafy, dominující a nezávislé podmnožiny, barevnost, vzdálenost.

6. Stromy, kostry, kružnice, minimální kostry.

7. Nejkratší cesty, algoritmy hledání nejkratších cest 1 -> n.

8. Algoritmy hledání nejkratších cest n -> n, planarita.

9. Toky v sítích, určení maximálního toku v síti.

10. Nejlevnější cirkulace, párování, řešení přiřazovací úlohy.

11. Stavový prostor úloh, prohledávání, heuristické hledání.

12. Turingovy stroje.

13. Třídy složitosti, NP-úplné problémy. Aproximační algoritmy.

1. Graph models, graphs, isomorphism.

2. Degree, connectedness, components, digraphs.

3. Strong connectedness, acyclic graphs, graph representation and traversal.

4. Depth-first traversal, topologic sort, strong components.

5. Euler graphs, dominating and independent sets, graph coloring, distance.

6. Trees, spanning trees, circuits, minimal spanning trees.

7. Shortest paths, algorithms for 1 ? n shortest paths.

8. Algorithms for 1 ? n shortest paths, planarity.

9. Flows in networks, maximum flow algorithm.

10. Cheapest circulation, matchings, assignment problem.

11. Problem state space, heuristic search.

12. Turing machines.

13. Complexity classes, NP-complete problems. Approximation algorithms.

Předpokládá se znalost základních abstraktních datových typů, jejich efektivní implementace a použitelnost při řešení grafových problémů na úrovni předmětu BI-EFA. Studenti by měli pasivně zvládat základní důkazové postupy známé z povinných matematických předmětů (důkaz úplnou indukcí, důkaz sporem, konstruktivní důkaz) a vedle návrhu nového či modifikace známého algoritmu by měli být schopni provést jeho analýzu složitosti.

We assume a working knowledge of basic abstract data types, its efficient implementation and application to solve graph problems. Students are assumed to have a passive knowledge of basic proof techniques used in mathematics (proof by induction, by contradiction, constructive) and apart from being able to design a new or modify an existing algorithm, they should be able to analyse its complexity.