Last update: Cejnar Pavel RNDr. Mgr. Ph.D. (30.07.2013)
The course concentrates on important problems from graph theory with emphasis on engineering applications. It deals with basic terms of graph theory, properties of various types of graphs and methods their numerical coding with aims on computational complexity of algorithms. It systematically goes over real-life graphs problems (large-scale sets of equations, numerical applications, engineering problems, tasks of operational research/analysis and decision-making problems) and presents effective algorithms of their solution.
Last update: Cejnar Pavel RNDr. Mgr. Ph.D. (12.11.2012)
Předmět je zaměřen na důležité problémy z teorie grafů s důrazem na inženýrské aplikace. Zabývá se základními pojmy teorie grafů, vlastnostmi různých typů grafů a metodami jejich číselného kódování se zaměřením na výpočetní složitost algoritmů. Systematicky probírá praktické grafové problémy (rozsáhlé soustavy rovnic, numerické aplikace, inženýrské problémy, úkoly operačního výzkumu/operační analýzy a rozhodovací problémy) a uvádí efektivní algoritmy jejich řešení.
Aim of the course -
Last update: Cejnar Pavel RNDr. Mgr. Ph.D. (30.07.2013)
Students will be able to:
Extract the graph theory problems in industrial tasks.
Analyze the graph theory problems and solve them using efficient known graph algorithms.
Have an overview of many problems solvable by various graph algorithms.
Distinguish computationally intensive tasks among various graph theory problems.
Last update: Cejnar Pavel RNDr. Mgr. Ph.D. (13.11.2012)
Studenti budou umět:
Analyzovat průmyslovou úlohu pohledem teorie grafů a abstrahovat řešený problém
Řešit danou úlohu pomocí známých efektivních grafových algoritmů a dále budou mít přehled o mnoha problémech řešitelných pomocí různých grafových algoritmů
Rozlišovat výpočetně náročně řešitelné úlohy
Literature -
Last update: Cejnar Pavel RNDr. Mgr. Ph.D. (25.04.2018)
A: Thulasiraman K., Swamy M. N. S.: Graphs: Theory and Algorithms. Wiley-Interscience, 1992. ISBN 978-0471513568.
A: West D. B.: Introduction to Graph Theory. Pearson, 2001. ISBN 978-0130144003.
A: Diestel R.: Graph Theory (Graduate Texts in Mathematics). Springer, 2010. ISBN 978-3642142789.
A: Christofides N.: Graph Theory. An Algoritmic Approach. Academic Press Inc, 1975. ISBN 978-0121743505.
Last update: Cejnar Pavel RNDr. Mgr. Ph.D. (16.11.2012)
Z: Demel J.: Grafy a jejich aplikace. Academia, Praha, 2002. ISBN 80-200-0990-6.
Z: Matoušek J., Nešetřil J.: Kapitoly z Diskrétní matematiky. Matfyzpress, Praha, 1996. ISBN 80-85863-17-0.
D: Töpfer P.: Algoritmy a programovací techniky. Prometheus, Praha, 1995. ISBN 80-85849-83-6.
12. Síťové grafy, maximální párování v obecném grafu - metoda kritické cesty.
13. Lokální a systematické prohledávání, programování s omezujícími podmínkami - hledání optimálních cest, diskrétní optimalizace, principy řešení, metoda větví a mezí.
14. Příklady technických a inženýrských aplikací teorie grafů.
Registration requirements -
Last update: Cejnar Pavel RNDr. Mgr. Ph.D. (30.07.2013)
Mathematics I or any equivalent subject
one subject in the topic of computer programming (in any computer language)
Last update: Cejnar Pavel RNDr. Mgr. Ph.D. (13.11.2012)
Matematika I
alespoň jeden předmět o programování v libovolném programovacím jazyku
Course completion requirements -
Last update: Cejnar Pavel RNDr. Mgr. Ph.D. (26.04.2018)
To complete the course, student must successfully elaborate 5 individual tasks. The assignment of all the tasks is announced during the semester and all the tasks must be successfully finished by the specified date in the exam period.
Last update: Cejnar Pavel RNDr. Mgr. Ph.D. (26.04.2018)
Pro udělení klasifikovaného zápočtu je třeba úspěšně vyřešit 5 zadaných úloh. Zadání jednotlivých úloh je postupně zveřejňováno v průběhu semestru a všechny úlohy je třeba úspěšně vyřešit nejpozději k určenému datu ve zkouškovém období.
Teaching methods
Activity
Credits
Hours
Účast na přednáškách
1
28
Příprava na přednášky, semináře, laboratoře, exkurzi nebo praxi