prikaz prve stranice dokumenta Paralelni algoritmi na grafovima
  Preuzmi
PDF 497.91 KB
diplomski rad
Paralelni algoritmi na grafovima
Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2023. urn:nbn:hr:217:915961
Horvat, Jurica
Sveučilište u Zagrebu
Prirodoslovno-matematički fakultet
Matematički odsjek

Institucijski repozitorij: Repozitorij Prirodoslovno-matematičkog fakulteta

Citirajte ovaj rad

Horvat, J. (2023). Paralelni algoritmi na grafovima (Diplomski rad). Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet. Preuzeto s https://urn.nsk.hr/urn:nbn:hr:217:915961

Horvat, Jurica. "Paralelni algoritmi na grafovima." Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2023. https://urn.nsk.hr/urn:nbn:hr:217:915961

Horvat, Jurica. "Paralelni algoritmi na grafovima." Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2023. https://urn.nsk.hr/urn:nbn:hr:217:915961

Horvat, J. (2023). 'Paralelni algoritmi na grafovima', Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, citirano: 15.05.2024., https://urn.nsk.hr/urn:nbn:hr:217:915961

Horvat J. Paralelni algoritmi na grafovima [Diplomski rad]. Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet; 2023 [pristupljeno 15.05.2024.] Dostupno na: https://urn.nsk.hr/urn:nbn:hr:217:915961

J. Horvat, "Paralelni algoritmi na grafovima", Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, Zagreb, 2023. Dostupno na: https://urn.nsk.hr/urn:nbn:hr:217:915961

Za citiranje koristite ovu mrežnu adresu: https://urn.nsk.hr/urn:nbn:hr:217:915961
Podaci o radu
NaslovParalelni algoritmi na grafovima
Naslov (engleski)Parallel algorithms on graphs
AutorJurica Horvat
MentorMladen Jurak (mentor)
Član povjerenstvaMladen Jurak (predsjednik povjerenstva)
Član povjerenstvaZvonimir Bujanović (član povjerenstva)
Član povjerenstvaMiljenko Marušić (član povjerenstva)
Član povjerenstvaNikola Sandrić (član povjerenstva)
Ustanova koja je dodijelila
akademski / stručni stupanj		Sveučilište u Zagrebu
Prirodoslovno-matematički fakultet
(Matematički odsjek)
Zagreb
Datum i država obrane2023-07-18, Hrvatska
Znanstveno / umjetničko
područje, polje i grana		PRIRODNE ZNANOSTI
Matematika
Sažetak
U ovom diplomskom radu analiziramo poznate algoritme na grafovima i implementiramo ih u jeziku C++, koristeći paralelizaciju kao sredstvo za optimizaciju. U uvodnom poglavlju smo se bavili izazovima koji se općenito javljaju kod programiranja višedretvenih aplikacija s dijeljenom memorijom. U drugom poglavlju smo stvorili bazu za konkurentno programiranje u modernom jeziku C++20, gdje smo istaknuli nekoliko korisnih i često korištenih sinkronizacijskih mehanizama te naveli korisne primjere. U glavnom dijelu rada smo se bavili s tri algoritma: pretraživanje u širinu (BFS), topološko sortiranje usmjerenih grafova bez ciklusa te Boruvkin algoritam za traženje minimalnog razapinjućeg stabla grafa. Za svaki od tih algoritama smo najprije opisali sekvencijalnu verziju, a onda ju paralelizirali i pritom detaljno analizirali mjesta izložena stanjima natjecanja. Na kraju smo sva tri algoritma implementirali u jeziku C++ i testirali njihova izvodenja sa različitim brojem korištenih dretvi, na odabranim testnim primjerima. Na samom kraju rada je iznesen motivacijski primjer, kojim se ističe korisnost algoritama na grafovima (konkretno, algoritama za traženje minimalnog razapinjućeg stabla) u stvarnom svijetu.
Sažetak (engleski)
In this thesis, we analyze well-known algorithms on graphs and implement them in the language C++, using parallelization as a tool for optimization. In the introductory chapter, we dealt with the challenges that generally arise when programming multithreaded applications with shared memory. In the second chapter, we created a base for concurrent programming in the modern C++20 language, where we highlighted several useful and frequently used synchronization mechanisms and provided useful examples. In the main part of the thesis, we covered three famous algorithms: breadth-first search (BFS), topological sorting of directed acyclic graphs, and Boruvka’s algorithm for finding the minimum spanning tree of a graph. For each of these algorithms, we first described sequential version, then parallelized it step by step and thoroughly analyzed the places exposed to data races. In the end, we implemented all three algorithms in the C++ and tested their performances with a variable number of running threads. At the very end of the thesis, a motivational example is presented, which highlights the usefulness of algorithms on graphs (specifically, algorithms for finding minimum spanning tree) in the real world.
Ključne riječi
Ključne riječi (engleski)
Jezikhrvatski
URN:NBNurn:nbn:hr:217:915961
Studijski programNaziv: Računarstvo i matematika
Vrsta studija: sveučilišni
Stupanj studija: diplomski
Akademski / stručni naziv: sveučilišni magistar računarstva i matematike (univ. mag. inf. et math.)
Vrsta resursaTekst
Način izrade datotekeIzvorno digitalna
Prava pristupaOtvoreni pristup
Uvjeti korištenjaIkona licence Zaštićeno autorskim pravom.
Datum i vrijeme pohrane2024-02-08 16:03:36