Počkejte prosím...
Data pro 2018/2019

Grafy v inženýrství

Kredity 3
Rozsah 2 / 1 / 0
Examinace KZ
Jazyk výuky čeština
Úroveň bakalářský předmět
Garant RNDr. Pavel Cejnar

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ů.

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.

VŠCHT Praha
Technická 5
166 28 Praha 6 – Dejvice
IČO: 60461373
DIČ: CZ60461373

Datová schránka: sp4j9ch

Copyright VŠCHT Praha 2014
Za informace odpovídá Oddělení komunikace, technický správce Výpočetní centrum
zobrazit plnou verzi