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