Grafy v inženýrství
Přednáška
Cvičení/laboratoř
2020,
letní semestr
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Po
Út
St
Čt
Pá
| Kredity | 3 |
| Rozsah | 2 / 1 / 0 |
| Examinace | KZ |
| Jazyk výuky | čeština |
| Úroveň | bakalářský předmět |
| Garant |
RNDr. Mgr. Pavel Cejnar, Ph.D. |
Anotace
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í.
Sylabus
1. Grafy, terminologie a základní definice, popis a kódování grafů.
2. Výpočetní a paměťová složitost algoritmů, NP-úplné problémy.
3. Acyklické očíslování, topologické uspořádání grafu, test acykličnosti grafu.
4. Prohledávání grafů a šířky a hloubky, vzájemná dosažitelnost uzlů a její analýza.
5. Výstupní zobrazení soustavy rovnic, párování v bipartitních grafech - přiřazovací problémy, souvislost s výstupním zobrazením soustavy rovnic.
6. Silné komponenty souvislosti, komponenty 2-souvislosti - ireducibilní subsystémy soustavy rovnic, záložní provoz a analýza kritických prvků sítě.
7. Kondenzace a hierarchická struktura grafu, splňování preferencí - optimální posloupnost výpočtů.
8. Nakreslení grafu do roviny - aplikace při návrhu tištěných spojů a integrovaných obvodů.
9. Hledání nejkratší cesty v grafu.
10. Kostra grafu - nalezení nezávislých obvodů, minimalizace potrubní sítě.
11. Toky v sítích, eulerovský tah.
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ů.
2. Výpočetní a paměťová složitost algoritmů, NP-úplné problémy.
3. Acyklické očíslování, topologické uspořádání grafu, test acykličnosti grafu.
4. Prohledávání grafů a šířky a hloubky, vzájemná dosažitelnost uzlů a její analýza.
5. Výstupní zobrazení soustavy rovnic, párování v bipartitních grafech - přiřazovací problémy, souvislost s výstupním zobrazením soustavy rovnic.
6. Silné komponenty souvislosti, komponenty 2-souvislosti - ireducibilní subsystémy soustavy rovnic, záložní provoz a analýza kritických prvků sítě.
7. Kondenzace a hierarchická struktura grafu, splňování preferencí - optimální posloupnost výpočtů.
8. Nakreslení grafu do roviny - aplikace při návrhu tištěných spojů a integrovaných obvodů.
9. Hledání nejkratší cesty v grafu.
10. Kostra grafu - nalezení nezávislých obvodů, minimalizace potrubní sítě.
11. Toky v sítích, eulerovský tah.
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ů.
Literatura
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.
D: Kučera L.: Kombinatorické algoritmy. SNTL, Praha, 1983.
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.
D: Kučera L.: Kombinatorické algoritmy. SNTL, Praha, 1983.