Prosím čekejte...
Nepřihlášený uživatel
logo VŠCHT
iduzel: 30011
idvazba: 38199
šablona: api_html
čas: 2.12.2022 21:50:39
verze: 5243
uzivatel:
remoteAPIs: https://cis-web-test.vscht.cz/studijni-system/
branch: trunk
Server: 147.33.89.150
Obnovit | RAW
iduzel: 30011
idvazba: 38199
---Nová url--- (newurl_...)
domena: 'www.vscht.cz'
jazyk: 'cs'
url: '/studijni-system/predmety/U/predmet/N445044/rok/2018'
iduzel: 30011
path: 1/4111/959/8547/4161/1398/8548/4168/4169/8547/4156/1394/8548/39341/39376/8548/48364/48365/8548/43892/43893/8548/39341/39375/8548/38914/38915/8548/29628/29629/8548/43413/8548/28158/28159/8548/24136/24137/8548/28861/28894/8548/25669/25670/8548/20508/20509/8548/22498/22499/8548/4162/1338/8548/15102/15103/8548/10022/10023/8548/4163/1558/8548/4164/945/8548/4165/1404/8548/4168/1410/8548/5338/5339/8548/6214/6522/8548/6996/6998/8548/7925/7928/8548/7925/7928/7937/8548/7924/7930/8548/7924/7930/7941/8548/7922/7926/8548/4167/1406/8548/11349/11351/1/12984/12985/8548/42398/42399/8547/11265/11271/8547/4154/1408/8547/4160/1399/8547/4156/1393/1/4111/942/8547/4161/1397/8547/4159/1395/1/1401/13358/519/30011
CMS: Odkaz na newurlCMS
branch: trunk
Obnovit | RAW
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. 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ů.

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Č: 60461373
DIČ: CZ60461373

Datová schránka: sp4j9ch

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

VŠCHT Praha
na sociálních sítích
zobrazit plnou verzi