prikaz prve stranice dokumenta Paralelni algoritam za Josipov problem u programskom jeziku C++
  Download
PDF 611.52 KB
undergraduate thesis
Paralelni algoritam za Josipov problem u programskom jeziku C++
Osijek: Josip Juraj Strossmayer University of Osijek, Faculty of Electrical Engineering, Computer Science and Information Technology Osijek, 2021. urn:nbn:hr:200:110928
Kodžoman, Leon
Josip Juraj Strossmayer University of Osijek
Faculty of Electrical Engineering, Computer Science and Information Technology Osijek
Department of Core Courses
Chair of Mathematics, Physics and Mechanical Engineering

Institutional repository: Faculty of Electrical Engineering, Computer Science and Information Technology Osijek

Cite this document

Kodžoman, L. (2021). Paralelni algoritam za Josipov problem u programskom jeziku C++ (Undergraduate thesis). Osijek: Josip Juraj Strossmayer University of Osijek, Faculty of Electrical Engineering, Computer Science and Information Technology Osijek. Retrieved from https://urn.nsk.hr/urn:nbn:hr:200:110928

Kodžoman, Leon. "Paralelni algoritam za Josipov problem u programskom jeziku C++." Undergraduate thesis, Josip Juraj Strossmayer University of Osijek, Faculty of Electrical Engineering, Computer Science and Information Technology Osijek, 2021. https://urn.nsk.hr/urn:nbn:hr:200:110928

Kodžoman, Leon. "Paralelni algoritam za Josipov problem u programskom jeziku C++." Undergraduate thesis, Josip Juraj Strossmayer University of Osijek, Faculty of Electrical Engineering, Computer Science and Information Technology Osijek, 2021. https://urn.nsk.hr/urn:nbn:hr:200:110928

Kodžoman, L. (2021). 'Paralelni algoritam za Josipov problem u programskom jeziku C++', Undergraduate thesis, Josip Juraj Strossmayer University of Osijek, Faculty of Electrical Engineering, Computer Science and Information Technology Osijek, accessed 27 November 2024, https://urn.nsk.hr/urn:nbn:hr:200:110928

Kodžoman L. Paralelni algoritam za Josipov problem u programskom jeziku C++ [Undergraduate thesis]. Osijek: Josip Juraj Strossmayer University of Osijek, Faculty of Electrical Engineering, Computer Science and Information Technology Osijek; 2021 [cited 2024 November 27] Available at: https://urn.nsk.hr/urn:nbn:hr:200:110928

L. Kodžoman, "Paralelni algoritam za Josipov problem u programskom jeziku C++", Undergraduate thesis, Josip Juraj Strossmayer University of Osijek, Faculty of Electrical Engineering, Computer Science and Information Technology Osijek, Osijek, 2021. Available at: https://urn.nsk.hr/urn:nbn:hr:200:110928

Metadata
TitleParalelni algoritam za Josipov problem u programskom jeziku C++
Title (english)C++ parallel algorithm for Josephus problem
AuthorLeon Kodžoman
MentorTomislav Rudec (mentor)
MentorAlfonzo Baumgartner (sumentor)
Committee memberIrena Galić (predsjednik povjerenstva)
GranterJosip Juraj Strossmayer University of Osijek
Faculty of Electrical Engineering, Computer Science and Information Technology Osijek
(Department of Core Courses)
(Chair of Mathematics, Physics and Mechanical Engineering)
Osijek
Defense date and country2021-09-22, Croatia
Scientific / art field,
discipline and subdiscipline		TECHNICAL SCIENCES
Computing
Program Engineering
Abstract
Josipov problem je problem u kojem n osoba stoji u krugu. Cilj je prolaziti kroz krug i uklanjati svaku drugu osobu sve dok ne preostane samo jedna. Moguće je izvesti formulu pomoću koje se može iz broja n odrediti koja osoba treba preživjeti. Poopćavanjem problema se dobije nova inačica problema takva da se traže q-ovi, a ne preživjele osobe. Traženjem rješenja poopćenog problema se dođe do spoznaje da određeni slučaji nisu mogući. Traženje tih nemogućih slučajeva je cilj implementiranog programa. Analiza algoritma koji traži nemoguće slučaje je bitna jer implementacija algoritma ovisi o njoj. Zbog velike kompleksnosti određena žrtvovanja su potrebna po pitanju vremena izvođenja i zauzete memorije. Implementacija je napravljena u programskom jeziku C++ zbog performansi i lakoće korištenja više niti. Radi ubrzavanja programa, implementiraju se dvije optimizacije, jedna vezana za kopiranje memorije, a druga vezana za modulo operaciju. Obje optimizacije zajedno ubrzavaju program za 60%.
Abstract (english)
The Josephus problem is a problem in which n people are standing in a circle. The goal is to go through the circle and eliminate every second person until only one remains. It is possible to produce a formula that is capable of calculating the position of the survivor from the number of people. By generalizing the problem a new form of it is created such that the solutions are q-s and not the surviving people. Searching for solutions of the generalized problem reveals the fact that some combinations are impossible. The searching of those combinations is the goal of the implemented program. Analysis of the algorithm which searches for the impossible cases is important because the implementation depends on it. Due to its high complexity, some sacrifices are necessary with respect to memory and execution time. The implementation is made in C++ because of performance and the ease of use of threads. To speed up the program, 2 optimizations are made, one to speed up memory transfers and the other to optimize the modulo operation. Together the optimizations speed up the program by 60%.
Keywords
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:200:110928
Study programmeTitle: Undergraduate University Study Programme in Computer Engineering
Study programme type: university
Study level: undergraduate
Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
Type of resourceText
File originBorn digital
Access conditionsOpen access
Terms of useLicence In copyright icon
Created on2021-11-22 14:29:14