Paralelne heuristike za problem max-cut

diplomski rad

• Autor: Saša Buzov
• Mentor: Goranka Nogo (mentor)
• Član povjerenstva: Goranka Nogo (predsjednik povjerenstva)
• Član povjerenstva: Nela Bosner (član povjerenstva)
• Član povjerenstva: Vjeran Hari (član povjerenstva)
• Član povjerenstva: Marko Vrdoljak (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2014-09-24, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

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.

Sažetak (engleski)

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.

• Ključne riječi: maksimalni rez; sekvencijalna implementacija; paralelna implementacija
• Ključne riječi (engleski): maximum cut; sequential algorithm; parallel algorithm
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:852402
• Studijski program: Naziv: Računarstvo i matematika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra računarstva i matematike (mag. inf. et math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2019-01-07 09:38:39