Seminar za teorijsko računarstvo

lokacija: 
PMF Matematički odsjek
vrijeme: 
18.11.2019 - 15:00 - 17:00

U okviru Seminara za teorijsko računarstvo, u ponedjeljak 18. studenog 2019. u 15 sati, predavaonica 104 PMF-MO,

Robert Manger s Matematičkog odsjeka PMF Sveučilišta u Zagrebu održat će predavanje pod naslovom:

"Konstruiranje algebri putova metodom redukcije".

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" (idempotentnim polu-prstenom), dakle vlastitim primjerkom iste apstraktne algebarske strukture. Da bismo neki novi tip problema uključili u spomenuti zajednički algebarski okvir, ključni korak je konstrukcija odgovarajuće nove algebre putova. U tom ključnom koraku može nam pomoći metoda redukcije: njome se postojeća algebra pretvara u novu algebru s donekle izmijenjenim svojstvima. U ovom predavanju definiramo metodu redukcije i dokazujemo njezinu korektnost. Zatim ilustriramo korisnost metode kroz nekoliko primjera koji su vezani uz problem ispisa elementarnih putova te uz višekriterijsku odnosno robusnu optimizaciju.

Pozivaju se svi članovi seminara kao i ostali zainteresirani da prisustvuju ovom predavanju. 

Robert Manger.

Share this