Paralelni algoritmi za probleme toka u mreži : doktorska disertacija - Nogo, Goranka (Zagreb : G. Nogo, 1997)
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 osnovne teorije složenosti paralelnog računa, te se dokazuje tvrdnja 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 PV M. Izvještava se o korištenom hardveru, test podacima i rezultatima eksperimenata. U prilogu je dan izvorni tekst svih korištenih programa.
Summary: In this thesis three new parallel algorithms are developed: the first two for the network flow problem and the third for the minimum-cost circulationproblem. The correctness of the considered algorithms is proved and their complexity is analysed. Also, a detailed experimental evaluation of the algorithms is carried out. The thesis of four chapters and an appendix. Chapter 1 reviews the theory of parallel computing. Special emphasis is put on the results that are needed in the forthcoming complexity analysis. As a model of parallel computing, the so-called P-RAM is assumed. Chapter 2 deals with the maximum flow problem. A basic sequential algorithm is first described and then parallelised. Next, a modification of the basic sequential algorithm is considered and also parallelised.
Results regarding the correctness and complexity of the two parallel algoritms are stated and proved. Chapter 3 is devoted to the minimum-cost circulation problem. The chapter starts again with the description of a suitable sequential algorithm, concludes with parallelisation, and ends with results on correctness and complexity. Chapter 4 describes an experimental implementation of the three algorithms in the C language combined with the PV M package. The available hardware configuration is specific. Test data are described and the obtained experimental results are presented. The appendix consist the source code of all programs.
Doktor prirodnih znanosti - matematika
Datum obrane: 04.02.1998.
Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, Zagreb, 1997
Bibliografija: str. 89-92
Summary
Keywords: Paralelni algoritmi -- Disertacije