Předmět Teorie sítí (KMA / TSI)
Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu KMA / TSI - Teorie sítí, Fakulta aplikovaných věd, Západočeská univerzita v Plzni (ZČU).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
Obsah
- Základní pojmy z teorie grafů. Maticový popis grafu: matice sousednosti, incidenční matice grafu (uzlů, hran, kružnic, řezů), jejich algebraické vlastnosti, souvislost s Kirchhoffovými zákony.- Ohodnocené grafy. Základní úlohy na grafech, řešitelné v polynomiálním čase: minimální cesty a kostry, vzdálenost, souvislost, Eulerovské grafy, acyklické grafy, kritická cesta a metody CPM- Toky v sítích a transportní úlohy, Ford-Fulkersonova věta o maximálním toku. Toky v sítích s cenami a minimalizace celkové ceny. Příklady praktického použití, algoritmy řešení a jejich výpočetní složitost.- Základní pojmy z výpočetní složitosti - efektivní algoritmy, polynomialita, NP-úplnost.- Základní NP-úplné úlohy: hamiltonovské grafy a problém obchodního cestujícího, nezávislé množiny a pokrytí, klikovost, dominance, jádro, barevnost grafu.- Příklady praktických aplikací, přibližné algoritmy a heuristiky.
Získané způsobilosti
Student bude po absolvování předmětu:- rozumět základním pojmům z teorie grafů. - rozumět základním pojmům z výpočetní složitosti- mít přehled o základních NP-úplných úlohách- schopen řešit základní úlohy na grafech řešitelných v polynomiálním čase: minimální cesty a kostry, vzdálenost, souvislost, Eulerovské grafy, acyklické grafy, kritická cesta a metody CPM,transportní úlohy převodem na tok v sítích- ovládat základy teorie NP-úplnosti, - u konkrétních grafových a kombinatorických problémů umět ověřit jejich NP-úplnost, včetně konstrukce příslušných polynomiálních převodních algoritmů.- umět použít přibližné algoritmy a heuristiky pro řešení konkrétních kombinatorických problémů
Literatura
Gibbons, Alan. Algorithmic graph theory. Cambridge : Cambridge University Press, 1994. ISBN 0-521-28881-9.Vágó, I. Graph Theory - Application to the Calculation of Electrical Networks. Budapest, 1985. Andrásfai, B. Graph Theory - Flows, Matrices. Budapest, 1991. Kučera, Luděk. Kombinatorické algoritmy. 2. nezm. vyd. Praha : SNTL, 1989. Holenda, Jiří; Ryjáček, Zdeněk. Lineární algebra II : úvod do diskrétní matematiky. 1. vyd. Plzeň : ZČU, 1992. ISBN 80-7082-060-8.http://www.kma.zcu.cz
Požadavky
Zápočet: 1 test ke konci semestru alespoň 8 bodů z 15. Zkouška: písemná část - 3 příklady, ústní část - 2 otázky.
Garant
Doc. Ing. Roman Čada, Ph.D.
Vyučující
Doc. Ing. Roman Čada, Ph.D.Doc. Ing. Roman Čada, Ph.D.