|
Lecturer(s)
|
-
Hofman Martin, RNDr. Mgr. Ph.D.
-
Marek Josef, doc. Ing. Ph.D.
|
|
Course content
|
Basic problems solvable in polynomial time: minimum path, minimum spanning tree, distance, connectivity, Eulerian graphs, acyclic graphs, critical path and CPM. Network flows and transportational problems, Ford-Fulkerson theorem on maximum flow. Graphs and matrices: irreducibility, weak irreducibility, generic rank and their determination using transformation to graph-theoretical problems. Basic NP-complete problems: hamiltonian graphs and the Travelling Salesman Problem, independent sets, coverings, cliques, domination, kernel, graph coloring. Elements of theory of NP-completeness: deterministic and nondeterministic algorithms, classes of languages P and NP, NP-completeness of the satisfiability problem, polynomial transformations of NP-complete problems, NP-completenss of the independence, clique and 3-colorability problems.
|
|
Learning activities and teaching methods
|
Collaborative instruction, Lecture
- Contact hours
- 52 hours per semester
- Preparation for comprehensive test (10-40)
- 25 hours per semester
- Preparation for an examination (30-60)
- 60 hours per semester
|
| prerequisite |
|---|
| Knowledge |
|---|
| explain basic concepts of relation structures as binary relations, equivalence (with applications to congruence mod 2), orderings and partial orderings, Boolean algebras, Boolean polynomials and functions |
| formulate basic concepts of graph theory (within the scope of KMA/DMA) a and explain their basic properties and relationships |
| define matrices related to a graph and explain relationships between graph properties and algebraic properties of corresponding matrix |
| Skills |
|---|
| invent and formulate algorithms for solving basic graph problems (within the range of KMA/DMA) |
| master concepts of equivalence and partition of a set |
| actively use basics of Boolean algebra theory, including conjunctive and disjunctive normal form |
| Competences |
|---|
| N/A |
| learning outcomes |
|---|
| Knowledge |
|---|
| explain concepts and problems of graph theory and their basic properties including context understanding |
| analyze particular algorithms from computational complexity view |
| clarify basic problems of graph theory and discrete mathematics from computational complexity view |
| explain basics of computational complexity and basic principles of NP-completness |
| Skills |
|---|
| be able to verify NP-completness of particular graph and combinatorial problems including their polynomial reductions |
| be able to classify algorithms according their computational complexity and estimate complexity of particular algorithms |
| invent, formulate and practically use algorithms for solving basic graph theory problems |
| actively master discussed concepts and problems of graph theory |
| invent heuristics for getting approximations and particular solutions of selected hard problems |
| Competences |
|---|
| N/A |
| aktivně využívá získané znalosti a dovednosti při řešení praktických problémů |
| teaching methods |
|---|
| Knowledge |
|---|
| Practicum |
| Lecture |
| Skills |
|---|
| Practicum |
| Competences |
|---|
| Lecture |
| assessment methods |
|---|
| Knowledge |
|---|
| Combined exam |
| Test |
| Skills demonstration during practicum |
| Skills |
|---|
| Skills demonstration during practicum |
| Test |
| Competences |
|---|
| Combined exam |
|
Recommended literature
|
-
Bondy, Adrian; Murty, U. S. R. Graph theory. 2008. ISBN 978-1-84996-690-0.
-
Bovet, Daniel Pierre; Crescenzi, Pierluigi. Introduction to the theory of complexity. 1994. ISBN 0-13-915380-2.
-
Čada, Roman; Kaiser, Tomáš; Ryjáček, Zdeněk. Diskrétní matematika. Plzeň : Západočeská univerzita, 2004. ISBN 80-7082-939-7.
-
Gross, Jonathan L.; Yellen, Jay; Anderson, Mark. Graph theory and its applications. Third edition. 2019. ISBN 978-1-4822-4948-4.
-
Sanjoy Dasgupta; Papadimitriou, Christos; Vazirani, Umesh. Algorithms. New York : McGraw-Hill, 2008. ISBN 978-0-07-352340-8.
|