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
• Hillier, F. S., & Lieberman, G. J. (2021). Introduction to operations research (11th ed., str. XVII, 964). McGraw Hill. https://plus.cobiss.net/cobiss/adz/sl/bib/180409091
• Foulds. (1992). Graph Theory Applications. Springer New York. https://plus-legacy.cobiss.net/cobiss/adz/sl/bib/3400000000089328
• Žerovnik, J. (2005). Osnove teorije grafov in diskretne optimizacije (2. popravljena izd., str. 173). Fakulteta za strojništvo. https://plus.cobiss.net/cobiss/adz/sl/bib/54389249
• Aldous, J. M., & Wilson, R. J. (2006). Graphs and applications: an introductory approach (5th print. 2006, str. XI, 444). Springer. https://plus.cobiss.net/cobiss/adz/sl/bib/11038486
Pogoji za vključitev v delo oz. za opravljanje študijskih obveznosti
Jih ni.
Podrobnosti o izvedbi in ocenjevanju Ni opomb
