prikaz prve stranice dokumenta Paralelni algoritmi na grafovima
  Download
PDF 497.91 KB
master's thesis
Paralelni algoritmi na grafovima
Zagreb: University of Zagreb, Faculty of Science, 2023. urn:nbn:hr:217:915961
Horvat, Jurica
University of Zagreb
Faculty of Science
Department of Mathematics

Institutional repository: Repository of the Faculty of Science

Cite this document

Horvat, J. (2023). Paralelni algoritmi na grafovima (Master's thesis). Zagreb: University of Zagreb, Faculty of Science. Retrieved from https://urn.nsk.hr/urn:nbn:hr:217:915961

Horvat, Jurica. "Paralelni algoritmi na grafovima." Master's thesis, University of Zagreb, Faculty of Science, 2023. https://urn.nsk.hr/urn:nbn:hr:217:915961

Horvat, Jurica. "Paralelni algoritmi na grafovima." Master's thesis, University of Zagreb, Faculty of Science, 2023. https://urn.nsk.hr/urn:nbn:hr:217:915961

Horvat, J. (2023). 'Paralelni algoritmi na grafovima', Master's thesis, University of Zagreb, Faculty of Science, accessed 29 December 2024, https://urn.nsk.hr/urn:nbn:hr:217:915961

Horvat J. Paralelni algoritmi na grafovima [Master's thesis]. Zagreb: University of Zagreb, Faculty of Science; 2023 [cited 2024 December 29] Available at: https://urn.nsk.hr/urn:nbn:hr:217:915961

J. Horvat, "Paralelni algoritmi na grafovima", Master's thesis, University of Zagreb, Faculty of Science, Zagreb, 2023. Available at: https://urn.nsk.hr/urn:nbn:hr:217:915961

Metadata
TitleParalelni algoritmi na grafovima
Title (english)Parallel algorithms on graphs
AuthorJurica Horvat
MentorMladen Jurak (mentor)
Committee memberMladen Jurak (predsjednik povjerenstva)
Committee memberZvonimir Bujanović (član povjerenstva)
Committee memberMiljenko Marušić (član povjerenstva)
Committee memberNikola Sandrić (član povjerenstva)
GranterUniversity of Zagreb
Faculty of Science
(Department of Mathematics)
Zagreb
Defense date and country2023-07-18, Croatia
Scientific / art field,
discipline and subdiscipline		NATURAL SCIENCES
Mathematics
Abstract
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.
Abstract (english)
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.
Keywords
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:217:915961
Study programmeTitle: Computer Science and Mathematics
Study programme type: university
Study level: graduate
Academic / professional title: sveučilišni magistar računarstva i matematike (sveučilišni magistar računarstva i matematike)
Type of resourceText
File originBorn digital
Access conditionsOpen access
Terms of useLicence In copyright icon
Created on2024-02-08 16:03:36