Algoritmi za problem maksimalnog reza

završni rad

• Naslov (engleski): Algorithms for maximum cut problem
• Autor: Jana Perak
• Mentor: Lana Horvat Dmitrović (mentor)
• Član povjerenstva: Lana Horvat Dmitrović (predsjednik povjerenstva)
• Član povjerenstva: Ana Žgaljić Keko (član povjerenstva)
• Član povjerenstva: Mate 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 obrane: 2023-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: maksimalni rez
• Ključne riječi (engleski): maximum cut
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:058478
• Studijski program: Naziv: 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 resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2023-07-13 10:27:25