Univerza na Primorskem
Fakulteta za matematiko, naravoslovje in informacijske tehnologije
V ponedeljek, 25. avgusta 2014, bo ob 16.00 uri v prostorih Fakultete za matematiko, naravoslovje in informacijske tehnologije Univerze na Primorskem, Glagoljaška 8, Koper predavanje v okviru skupnega SEMINARJA ZA MATEMATIČNE IN RAČUNALNIŠKE ZNANOSTI Oddelka za matematiko in Oddelka za Informacijske znanosti in tehnologije UP FAMNIT, Oddelka za matematiko in Oddelka za Informacijske znanosti in tehnologije UP IAM, Oddelka za matematiko in računalništvo UP PEF ter Oddelkov za matematiko in teoretično računalništvo IMFM.
RAČUNALNIŠKI SEMINAR
Prostor: FAMNIT-1-RU1 ob 16:00
Predavatelj: Marko Grgurovič
Naslov: Tranzitivna ovojnica, dinamični algoritmi in najkrajše poti
Povzetek:
Na seminarju si bomo ogledali kako lahko učinkovito izračunamo tranzitivno ovojnico grafa. Pri tem bomo uporabili nekaj trikov iz “word RAM” modela, ter pokazali, kako lahko tovrstne prijeme prevedemo na bolj splošne modele računanja. Ogledali si bomo tudi nekaj sodobnih dinamičnih algoritmov za hrambo tranzitivne ovojnice grafa. Vse skupaj bomo povezali s t.i. problemom “bottleneck shortest path” in pokazali, da ga je moč reducirati na problem dinamične hrambe tranzitivne ovojnice.
Vabljeni!
