Seminar za teorijsko računarstvo

lokacija: 
PMF Matematički odsjek (virtualno)
vrijeme: 
19.07.2021 - 15:00 - 17:00

 

U okviru Seminara za teorijsko računarstvo, u ponedjeljak 19. srpnja 2021. u 15:00 sati

Krunoslav Puljić, Ekonomski fakultet Zagreb, održat će predavanje pod naslovom:

"Evaluacija softverskog paketa za rješavanje problema putova u grafu".

Sažetak:  Problemi putova svode se na generiranje i usporedbu putova u usmjerenom grafu. Najpoznatiji primjeri su: provjera postojanja puta, traženje najkraćih ili najpouzdanijih putova, traženje putova s najvećim kapacitetom, ispis svih putova, itd. Algebarski pristup problemima putova omogućuje rješavanje svih takvih tipova problema pomoću istih apstraktnih algoritama. Pritom je svaki tip opisan svojom vlastitom "algebrom putova", dakle vlastitim primjerkom iste apstraktne algebarske strukture. U ovom predavanju prikazat ćemo najnoviju verziju našeg softverskog paketa kojim se realizira opisani algebarski pristup. Naš paket implementira razne algebre putova: najprije jednostavne (skalarne algebre), zatim one složenije koje su građene na temelju jednostavnih (npr. vektorske, matrične, skupovne ili vektorsko-skupovne algebre). Paket također implementira nekoliko apstraktnih algoritama za rješavanje problema putova. Svi dijelovi softvera oblikovani su na fleksibilan način, tako da se mogu kombinirati. S takvim kombinacijama moguće je rješavati razne probleme putova, uključujući i njihove višekriterijske ili robusne varijante. U predavanju ćemo također izložiti rezultate eksperimentalne evaluacije performansi našeg softvera na robusnim primjercima problema najkraćeg puta. Svrha eksperimenata bila je utvrditi vremenske i prostorne zahtjeve našeg postupka rješavanja problema najkraćeg puta, ovisno o veličini i gustoći grafa te broju scenarija za duljine lukova.

Predavanje će se održati u obliku telekonferencije (on-line) na platformi Zoom. Podaci za spajanje:

Join Zoom Meeting
https://zoom.us/j/98307532449?pwd=Z1l2TXpkOWg4T1IwUitBck5ZMy9vdz09

Meeting ID: 983 0753 2449

Pozivaju se svi članovi seminara, studenti diplomskih studija, kao i ostali zainteresirani da se pridruže.

Robert Manger.

Share this