Poslední úprava: 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í.
Poslední úprava: 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.
Výstupy studia předmětu -
Poslední úprava: 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
Poslední úprava: 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.
Literatura -
Poslední úprava: 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ů.
Poslední úprava: Cejnar Pavel RNDr. Mgr. Ph.D. (30.07.2013)
1. Graphs, their terminology and basic definitions, graph description and coding
2. Time and storage complexity of algorithms, NP-complete problems
3. Directed and undirected acyclic graphs, topological ordering and finding a circle in a graph
4. Depth-first and breadth-first search in graphs, mutual reachability of nodes and its analysis
5. Bipartite graphs, matching in bipartite graphs and output mapping of equation set
6. Strong components, k-edge-connected graphs and irreducible subsystems of equation set
7. Graph condensation, hierarchical structure of a directed graph, computation sequencing
8. Planar graphs, their embedding into a plane, application in design of printed circuits and chips
9. Finding shortest path in graphs
10. Pipeline networks, spanning tree, search for independent circuits, minimization of pipe networks
11. Flow networks, maximum flow and minimum cut, transportation reserves, Eulerian path
12. General matching problems, critical path method
13. Discrete optimization, local and systematic search - principles of methods, constraint programming, branch-and-bound method
14. Examples of application in engineering and technology
Studijní prerekvizity -
Poslední úprava: 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
Poslední úprava: 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)
Podmínky zakončení předmětu (Další požadavky na studenta) -
Poslední úprava: 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í.
Poslední úprava: 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.
Zátěž studenta
Činnost
Kredity
Hodiny
Účast na přednáškách
1
28
Příprava na přednášky, semináře, laboratoře, exkurzi nebo praxi