Paralelni algoritmi za probleme toka u mreži (CROSBI ID 329572)
Ocjenski rad | doktorska disertacija
Podaci o odgovornosti
Nogo, Goranka
Manger, Robert
hrvatski
Paralelni algoritmi za probleme toka u mreži
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.
tok u mreži; paralelni algoritmi
nije evidentirano
engleski
Parallel algorithms for network flow problems
nije evidentirano
network flow; parallel algorithms
nije evidentirano
Podaci o izdanju
97
04.02.1998.
obranjeno
Podaci o ustanovi koja je dodijelila akademski stupanj
Prirodoslovno-matematički fakultet, Zagreb
Zagreb