Naslov
Paralelni algoritmi za probleme toka u mreži
(Parallel algorithms for network flow problems)

Autori
Nogo, Goranka

Vrsta, podvrsta i kategorija rada
Ocjenski radovi, doktorska disertacija

Fakultet
Prirodoslovno-matematički fakultet - Matematički odjel

Mjesto
Zagreb

Datum
04.02

Godina
1998

Stranica
97

Mentor
Manger, Robert

Ključne riječi
tok u mreži; paralelni algoritmi
(network flow; parallel algorithms)

Sažetak
U radu se razvijaju tri nova paralelna algoritma, od kojih prva dva rješavaju problem maksimalnog toka u mreži, a treći problem optoka s minimalnim troškom, Dokazuje se korektnost algoritama i procjenjuje njihova vremenska složenost. Također se provodi detaljna eksperimentalna evaluacija algoritama. Rad se sastoji od četiri poglavlja i dodatka. U prvom poglavlju izlažu se osnove teorije složenosti paralelnog računa, te se dokazuju tvrdnje koje će se koristiti u dokazima složenosti za konkretne algoritme. Kao model paralelnog računanja pretpostavlja se P-RAM. U drugom poglavlju razmatra se problem maksimalnog toka. Obrađuje se osnovni sekvencijalni algoritam koji se zatim paralelizira. Zatim se promatra modifikacija osnovnog algoritma, te pripadna paralelna verzija. Formuliraju se i dokazuju rezultati vezani uz korektnost i vremensku složenost paralelnih algoritama. Treće poglavlje posvećeno je problemu iznalaženja optoka s minimalnim troškom. Kao i u prethodnom poglavlju, prvo je dan opis pogodnog sekvencijalnog algoritma, a zatim se prešlo na paralelizaciju i izvod rezultata o korektnosti i složenosti. U četvrtom poglavlju detaljno je opisana implementacija triju algoritama u jeziku C uz pomoć paketa PVM. Izvještava se o korištenom hardveru, test podacima i rezultatima eksperimenata. U prilogu je dan izvorni tekst svih korištenih programa.

Izvorni jezik
Hrvatski

Znanstvena područja
Matematika

POVEZANOST RADA