prikaz prve stranice dokumenta Algoritmi za problem maksimalnog reza
No public access
undergraduate thesis
Algoritmi za problem maksimalnog reza
Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing, 2023. urn:nbn:hr:168:058478
Perak, Jana
University of Zagreb
Faculty of Electrical Engineering and Computing

Institutional repository: FER Repository

Cite this document

Perak, J. (2023). Algoritmi za problem maksimalnog reza (Undergraduate thesis). Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing. Retrieved from https://urn.nsk.hr/urn:nbn:hr:168:058478

Perak, Jana. "Algoritmi za problem maksimalnog reza." Undergraduate thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, 2023. https://urn.nsk.hr/urn:nbn:hr:168:058478

Perak, Jana. "Algoritmi za problem maksimalnog reza." Undergraduate thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, 2023. https://urn.nsk.hr/urn:nbn:hr:168:058478

Perak, J. (2023). 'Algoritmi za problem maksimalnog reza', Undergraduate thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, accessed 28 June 2024, https://urn.nsk.hr/urn:nbn:hr:168:058478

Perak J. Algoritmi za problem maksimalnog reza [Undergraduate thesis]. Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing; 2023 [cited 2024 June 28] Available at: https://urn.nsk.hr/urn:nbn:hr:168:058478

J. Perak, "Algoritmi za problem maksimalnog reza", Undergraduate thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, Zagreb, 2023. Available at: https://urn.nsk.hr/urn:nbn:hr:168:058478

Metadata
TitleAlgoritmi za problem maksimalnog reza
Title (english)Algorithms for maximum cut problem
AuthorJana Perak
MentorLana Horvat Dmitrović (mentor)
Committee memberLana Horvat Dmitrović (predsjednik povjerenstva)
Committee memberAna Žgaljić Keko (član povjerenstva)
Committee memberMate Puljiz (član povjerenstva)
GranterUniversity of Zagreb
Faculty of Electrical Engineering and Computing
Zagreb
Defense date and country2023-07-06, Croatia
Scientific / art field,
discipline and subdiscipline		TECHNICAL SCIENCES
Computing
Abstract
U ovom završnom radu proučili smo problem maksimalnog reza. Uveli smo osnovne pojmove o grafu te smo vidjeli da je problem maksimalnog reza NP težak problem. Naveli smo algoritam iscrpne pretrage koji daje točnu vrijednost reza ali za mali broj vrhova te smo naveli i neke algoritme koji ne daju točnu vrijednost reza ali ju dobro aproksimiraju. Najprije je opisan slučajni algoritam, zatim algoritam lokalne pretrage i na kraju Goemans- Williamsonov algoritam, najbolji algoritam za rješavanje problema maksimalnog reza. Na kraju je prikazana implementacija algoritama iscrpne pretrage i Goemans-Williamsonovog algoritma, te je dana usporedba rješenje, uz vizualizaciju rješenja.
Abstract (english)
In this paper we studied the maximum cut problem. We introduced the basic notions of graphs and saw that the maximum cut problem is an NP-hard problem. We listed a greedy search algorithm that gives the exact value of the cut, but only for a small number of the vertices, and we also listed some algorithms that do not give the exact value of the cut, but approximate them well. First, the randomized algorithm is described, then the local search algorithm, and finally the Goemans-Williamson algorithm, the best algorithm for solving the maximum cut problem. At the end, the implementation of the greedy algorithm and the Goemans-Williamson algorithm is presented, and a comparison of the solutions is given, along with a visualization of the solutions.
Keywords
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:168:058478
Study programmeTitle: Computing
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 conditionsClosed access
Terms of useLicence In copyright icon
Public note
Created on2023-07-13 10:27:25