prikaz prve stranice dokumenta Algoritmi za problem maksimalnog reza
Rad nije dostupan
završni rad
Algoritmi za problem maksimalnog reza
Zagreb: Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, 2023. urn:nbn:hr:168:058478
Perak, Jana
Sveučilište u Zagrebu
Fakultet elektrotehnike i računarstva

Institucijski repozitorij: Repozitorij FER-a

Citirajte ovaj rad

Perak, J. (2023). Algoritmi za problem maksimalnog reza (Završni rad). Zagreb: Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva. Preuzeto s https://urn.nsk.hr/urn:nbn:hr:168:058478

Perak, Jana. "Algoritmi za problem maksimalnog reza." Završni rad, Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, 2023. https://urn.nsk.hr/urn:nbn:hr:168:058478

Perak, Jana. "Algoritmi za problem maksimalnog reza." Završni rad, Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, 2023. https://urn.nsk.hr/urn:nbn:hr:168:058478

Perak, J. (2023). 'Algoritmi za problem maksimalnog reza', Završni rad, Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, citirano: 30.11.2024., https://urn.nsk.hr/urn:nbn:hr:168:058478

Perak J. Algoritmi za problem maksimalnog reza [Završni rad]. Zagreb: Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva; 2023 [pristupljeno 30.11.2024.] Dostupno na: https://urn.nsk.hr/urn:nbn:hr:168:058478

J. Perak, "Algoritmi za problem maksimalnog reza", Završni rad, Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, Zagreb, 2023. Dostupno na: https://urn.nsk.hr/urn:nbn:hr:168:058478

Za citiranje koristite ovu mrežnu adresu: https://urn.nsk.hr/urn:nbn:hr:168:058478
Podaci o radu
NaslovAlgoritmi za problem maksimalnog reza
Naslov (engleski)Algorithms for maximum cut problem
AutorJana Perak
MentorLana Horvat Dmitrović (mentor)
Član povjerenstvaLana Horvat Dmitrović (predsjednik povjerenstva)
Član povjerenstvaAna Žgaljić Keko (član povjerenstva)
Član povjerenstvaMate Puljiz (član povjerenstva)
Ustanova koja je dodijelila
akademski / stručni stupanj		Sveučilište u Zagrebu
Fakultet elektrotehnike i računarstva
Zagreb
Datum i država obrane2023-07-06, Hrvatska
Znanstveno / umjetničko
područje, polje i grana		TEHNIČKE ZNANOSTI
Računarstvo
Sažetak
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.
Sažetak (engleski)
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.
Ključne riječi
Ključne riječi (engleski)
Jezikhrvatski
URN:NBNurn:nbn:hr:168:058478
Studijski programNaziv: Računarstvo
Vrsta studija: sveučilišni
Stupanj studija: preddiplomski
Akademski / stručni naziv: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (univ.bacc.ing.comp.)
Vrsta resursaTekst
Način izrade datotekeIzvorno digitalna
Prava pristupaZatvoreni pristup
Uvjeti korištenjaIkona licence Zaštićeno autorskim pravom.
Javna napomena
Datum i vrijeme pohrane2023-07-13 10:27:25