Cilji in kompetence
Cilji predmeta so, da študenti razumejo problematiko kombinatorike in učinkovitost algoritmov, osvojijo spretnosti modeliranja problemov s pomočjo teorije grafov, poznajo korake za iskanje optimalnih rešitev, znajo izvesti algoritme po korakih in uporabljati programska orodja.
Vsebina
Pregled pojmov iz teorije grafov
grafi, digrafi, omrežja, vpeta drevesa, izomorfizem, preštevanje grafov, ravninskost, potovalnost, Eulerjev obhod, Hamiltonov cikel, barvanje grafov, grafovske invariante, prirejanja, povezanost po vozliščih, povezanost po povezavah, premer grafa, okvarni premeri, klasični problemi v teoriji grafov.
Kombinatorična optimizacija
kompleksnost algoritmov, problemi reševanja v kombinatorični optimizaciji, odločitveni in optimizacijski problemi, razredi problemov v teoriji grafov, optimizacija projekta, otpimizacija omrežij, najkrajše in najdaljše poti, Bellmanov algoritem, maksimalni pretoki, minimalni stroški, Ford-Fulkersonov algoritem, uporaba računalniških programov.
Del snovi bo prilagojen interesom študentom in sproti se porajajočim trendom v teoriji grafov.
Metode poučevanja in učenja
Predavanja, diskusija, delo s programskimi orodji.
Predvideni študijski rezultati - znanje in razumevanje
Znanje in razumevanje:
Po zaključku tega predmeta bo študent sposoben:
- razumeti problematiko kombinatorike in razložiti učinkovitost algoritmov,
- posplošiti klasične optimizacijske probleme,
- modelirati in reševati praktične probleme z uporabo kombinatoričnih orodij,
- izvesti obravnavane algoritme po korakih in uporabljati programska orodja,
- načrtovati transportna in prometna omrežja,
- načrtovati in sestaviti osnovne algoritme na omrežjih in analizirati njihovo časovno zahtevnost.
Temeljni literatura in viri
J. Žerovnik, Osnove teorije grafov in diskretne optimzacije, 2. popravljena izdaja, FS UM, Maribor, 2005.
L. R. Foulds, Graph Theory Applications, Springer, New York, 1992.
J. A. Bondy, U. S. R. Murty, Graph Theory, Springer, London, 2008.
F. S. Hillier, G. J. Lieberman, Introduction to Operation Research, Ninth Edition, McGraw-Hill, New York, 2009.
Pogoji za vključitev v delo oz. za opravljanje študijskih obveznosti
Ni pogojev za vključitev v delo.
Pogoji za opravljanje študijskih obveznosti:
pogoj za pristop k ustnemu izpitu je opravljena projektna naloga z rezultatom vsaj 70%.
Podrobnosti o izvedbi in ocenjevanju Opomba: pogoj za pristop k ustnemu izpitu je opravljena projektna naloga z rezultatom vsaj 70%.
