|
|
Main menu for Browse IS/STAG
Course info
KMA / TGD2
:
Course description
Department/Unit / Abbreviation
|
KMA
/
TGD2
|
Academic Year
|
2023/2024
|
Academic Year
|
2023/2024
|
Title
|
Graph Theory, Optimization, Complexity 2
|
Form of course completion
|
Exam
|
Form of course completion
|
Exam
|
Long Title
|
Graph Theory, Discrete Optimization and Computational Complexity 2
|
Accredited / Credits
|
Yes,
5
Cred.
|
Type of completion
|
Combined
|
Type of completion
|
Combined
|
Time requirements
|
Lecture
3
[Hours/Week]
Seminar
1
[Hours/Week]
|
Course credit prior to examination
|
Yes
|
Course credit prior to examination
|
Yes
|
Automatic acceptance of credit before examination
|
No
|
Included in study average
|
YES
|
Language of instruction
|
Czech
|
Occ/max
|
|
|
|
Automatic acceptance of credit before examination
|
No
|
Summer semester
|
4 / -
|
0 / -
|
1 / -
|
Included in study average
|
YES
|
Winter semester
|
0 / -
|
0 / -
|
0 / -
|
Repeated registration
|
NO
|
Repeated registration
|
NO
|
Timetable
|
Yes
|
Semester taught
|
Summer semester
|
Semester taught
|
Summer semester
|
Minimum (B + C) students
|
1
|
Optional course |
Yes
|
Optional course
|
Yes
|
Language of instruction
|
Czech
|
Internship duration
|
0
|
No. of hours of on-premise lessons |
|
Evaluation scale |
1|2|3|4 |
Periodicity |
každý rok
|
Evaluation scale for credit before examination |
S|N |
Periodicita upřesnění |
|
Fundamental theoretical course |
No
|
Fundamental course |
No
|
Fundamental theoretical course |
No
|
Evaluation scale |
1|2|3|4 |
Evaluation scale for credit before examination |
S|N |
Substituted course
|
None
|
Preclusive courses
|
N/A
|
Prerequisite courses
|
N/A
|
Informally recommended courses
|
KMA/TGD1
|
Courses depending on this Course
|
KMA/DIM, KMA/DM, KMA/DMI, KMA/SZMZ
|
Histogram of students' grades over the years:
Graphic PNG
,
XLS
|
Course objectives:
|
The course gives basic knowledge in Discrete Optimization. The student will have an overview
of basic optimization problems on graphs and networks, and will be able to design algorithms for basic optimization problems, including their computational complexity. The student will understand the theoretical background of individual methods and their mutual trasformability, including undestanding the role of good characterizations.
|
Requirements on student
|
Students are supposed to have knowledge in Algoritgmic Graph Theory and Computational Complexity corresponding to the contents of the course KMA/TGD1.
Examination: written part - 3 problems, 90 minutes, oral part - 2 questions.
With all questions, main emphasis is given on algorithmic aspects of the problem under consideration (i.e. algorithms and their complexity).
|
Content
|
Optimization problems on graphs and networks: flows with costs and minimum cost flows, potentials. Maximum matching and optimum matching in a (weighted) bipartite graph. Maximum matching in a nonbipartite graph (Tuttes Theorem and Edmonds algorithm).
Real linear programming: simplex algorithm, duality, computational complexity.
Integer linear programming: NP-completeness, totally unimodular matrices, branch-and-bound methods and Gomory algorithms. Formulation of various optimization problems on graphs and networks as linear programming problems.
|
Activities
|
|
Fields of study
|
Studentům jsou k dispozici kompletní studijní materiály na webové stránce předmětu
https://home.zcu.cz/~ryjacek/TGD2.php
|
Guarantors and lecturers
|
|
Literature
|
-
Basic:
Pracovní texty přednášek
-
Recommended:
Hromkovič, Juraj. Algorithmics for hard problems : introduction to combinatorial optimization, randomization, approximation, and heuristics. 2nd ed. Berlin : Springer, 2003. ISBN 3-540-44134-4.
-
Recommended:
Cook, W.J.; Cunningham, W.H.; Pulleyblank, W.R.; Schrijve, A. Combinatorial Optimization. New York: Wiley, 1998.
-
Recommended:
Papadimitriou, Christos H.; Steiglitz, Kenneth. Combinatorial optimization : algorithms and complexity. 1st pub. Mineola : Dover Publications, 1998. ISBN 0-486-40258-4.
-
Recommended:
Korte, Bernhard; Vygen, Jens. Combinatorial optimization : theory and algorithms. 2nd ed. Berlin : Springer, 2002. ISBN 3-540-43154-3.
-
Recommended:
Kučera, Luděk. Kombinatorické algoritmy. 2. nezm. vyd. Praha : SNTL, 1989.
-
Recommended:
Plesník, Ján; Dupačová, Jitka; Vlach, Milan. Lineárne programovanie. 1. vyd. Bratislava : Alfa, 1990. ISBN 80-05-00679-9.
-
Recommended:
Lovász, L.; Plummer, M. Matching Theory. Budapest: Akadémiai Kiadó, 1986.
-
On-line library catalogues
|
Time requirements
|
All forms of study
|
Activities
|
Time requirements for activity [h]
|
Contact hours
|
52
|
Preparation for an examination (30-60)
|
60
|
Preparation for comprehensive test (10-40)
|
25
|
Total
|
137
|
|
Prerequisites
|
Knowledge - students are expected to possess the following knowledge before the course commences to finish it successfully: |
analyzovat konkrétní algoritmy z hlediska jejich výpočetní složitosti |
klasifikovat základní problémy teorie grafů a diskrétní matematiky z hlediska výpočetní složitosti |
vysvětlit pojmy a úlohy teorie grafů (v rozsahu předmětu KMA/TGD1) a jejich základní vlastnosti, včetně porozumění souvislostem |
vysvětlit základy teorie výpočetní složitosti a základní principy teorie NP-úplnosti |
Skills - students are expected to possess the following skills before the course commences to finish it successfully: |
aktivně ovládat pojmy a úlohy teorie grafů v rozsahu předmětu KMA/TGD1 |
navrhnout, formulovat a prakticky použít algoritmy řešení základních grafových úloh |
ovládat klasifikaci algoritmů z hlediska jejich výpočetní složitosti a posoudit výpočetní složitost konkrétních algoritmů |
pro vybrané algoritmicky obtížné úlohy navrhnout heuristické algoritmy umožňující jejich přibližné nebo částečné řešení |
u vybraných konkrétních grafových a kombinatorických problémů ověřit jejich NP-úplnost, včetně konstrukce příslušných polynomiálních převodních algoritmů |
Competences - students are expected to possess the following competences before the course commences to finish it successfully: |
N/A |
|
Learning outcomes
|
Knowledge - knowledge resulting from the course: |
formulovat základní optimalizační úlohy na grafech a sítích, vysvětlit jejich vlastnosti a základní metody |
popsat algoritmy řešení základních optimalizačních úloh a posoudit jejich výpočetní složitost |
vysvětlit teoretické pozadí jednotlivých metod a jejich vzájemné převoditelnosti, včetně role charakterizačních vět a dobrých charakteristik při konstrukci efektivních algoritmů |
Skills - skills resulting from the course: |
aktivně používat metody a algoritmy řešení jednotlivých úloh |
klasifikovat jednotlivé problémy z hlediska výpočetní složitosti a u NP-těžkých problémů ovládat základní heuristické a aproximační algoritmy |
ovládat základní optimalizační úlohy na grafech a sítích |
používat vzájemné převody úloh, včetně převodů grafových a síťových optimalizačních úloh na úlohy lineárního programování |
Competences - competences resulting from the course: |
N/A |
N/A |
aktivně využívá získané znalosti a dovednosti při řešení praktických problémů |
|
Assessment methods
|
Knowledge - knowledge achieved by taking this course are verified by the following means: |
Combined exam |
Test |
Skills demonstration during practicum |
Skills - skills achieved by taking this course are verified by the following means: |
Skills demonstration during practicum |
Competences - competence achieved by taking this course are verified by the following means: |
Combined exam |
|
Teaching methods
|
Knowledge - the following training methods are used to achieve the required knowledge: |
Lecture |
Collaborative instruction |
Skills - the following training methods are used to achieve the required skills: |
Collaborative instruction |
Competences - the following training methods are used to achieve the required competences: |
Lecture |
|
|
|
|