Paralelne heuristike za problem max-cut

U ovom radu smo prezentirali jedan mogući pristup rješavanju problema maksimalnog reza. Uveli smo osnovne definicije i pojmove iz teorije grafova i složenosti algoritama, kako bi se razumio problem, i kojoj klasi pripada. Pokazali smo primjer sekvencijalne implementacije genetskog algoritma. Opisali smo arhitekturu CUDA, te našu implementaciju genetskog algorimna u CUDA okruženju. Opisali smo naš skup testnih primjera, metodologiju i okruženje testiranja, te rezultate i analizu istih. Pokazali smo da je paralelni pristup brži nakon što se prođe određena granica veličine problema, koja naravno ovisi o sustavu na kojem se testira.In this thesis, we presented one possible solution to problem of finding maximum cut in graph. We started with describing the problem with basic definitions from graph theory and computational complexity. Later we provided both sequential and parallel algorithms for solving before mentioned problem. In last few chapter we described testing environment, test data set, and our test results. Obtained results show that parallel approach has better performance for large scale problems. After analysis, we came to conclusion that parallel is the way to go, if and only if you have large scale problem