prikaz prve stranice dokumenta Spektralni normalizirani rezovi u težinskim grafovima
  Preuzmi
PDF 1.1 MB
diplomski rad
Spektralni normalizirani rezovi u težinskim grafovima
Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2017. urn:nbn:hr:217:351592
Palajsa, Franjo
Sveučilište u Zagrebu
Prirodoslovno-matematički fakultet
Matematički odsjek

Institucijski repozitorij: Repozitorij Prirodoslovno-matematičkog fakulteta

Citirajte ovaj rad

Palajsa, F. (2017). Spektralni normalizirani rezovi u težinskim grafovima (Diplomski rad). Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet. Preuzeto s https://urn.nsk.hr/urn:nbn:hr:217:351592

Palajsa, Franjo. "Spektralni normalizirani rezovi u težinskim grafovima." Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2017. https://urn.nsk.hr/urn:nbn:hr:217:351592

Palajsa, Franjo. "Spektralni normalizirani rezovi u težinskim grafovima." Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2017. https://urn.nsk.hr/urn:nbn:hr:217:351592

Palajsa, F. (2017). 'Spektralni normalizirani rezovi u težinskim grafovima', Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, citirano: 23.11.2024., https://urn.nsk.hr/urn:nbn:hr:217:351592

Palajsa F. Spektralni normalizirani rezovi u težinskim grafovima [Diplomski rad]. Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet; 2017 [pristupljeno 23.11.2024.] Dostupno na: https://urn.nsk.hr/urn:nbn:hr:217:351592

F. Palajsa, "Spektralni normalizirani rezovi u težinskim grafovima", Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, Zagreb, 2017. Dostupno na: https://urn.nsk.hr/urn:nbn:hr:217:351592

Za citiranje koristite ovu mrežnu adresu: https://urn.nsk.hr/urn:nbn:hr:217:351592
Podaci o radu
NaslovSpektralni normalizirani rezovi u težinskim grafovima
AutorFranjo Palajsa
MentorZlatko Drmač (mentor)
Član povjerenstvaZlatko Drmač (predsjednik povjerenstva)
Član povjerenstvaLuka Grubišić (član povjerenstva)
Član povjerenstvaMiljenko Marušić (član povjerenstva)
Član povjerenstvaNela Bosner (č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 obrane2017-11-29, Hrvatska
Znanstveno / umjetničko
područje, polje i grana		PRIRODNE ZNANOSTI
Matematika
Sažetak
U ovom radu dajemo detaljan opis metode particioniranja težinskog grafa primjenom kriterija spektralnog normaliziranog reza. Argumentiramo odabir takvog kriterija u kontekstu zahtjeva na dobro particioniranje. U teorijskom razvoju metode uglavnom se pozivamo na elementarne pojmove i rezultate iz spektralne teorije matrica. Prvo problem particioniranja oblikujemo kao optimizacijski problem koji potom relaksiramo. Rješenja relaksiranog optimizacijskog problema dana su ortogonalnim transformacijama prvih nekoliko svojstvenih vektora simetrične matrice. U drugom koraku nastojimo pronaći rješenje originalnog diskretnog problema koje je najbliže dobivenom skupu kontinuiranih rješenja. To ostvarujemo iterativnim postupkom u kojem naizmjenično primjenjujemo dvije procedure: metodom potiskivanja ne-maksimuma pronalazimo diskretno rješenje najbliže kontinuiranom, dok se kontinuirano rješenje koje je dobra aproksimacija diskretnog može dobiti rješavanjem ortogonalnog Prokrustovog problema. Možemo garantirati da je tako dobiveno rješenje skoro globalno-optimalno. U zadnjem poglavlju dajemo implementaciju metode koju potom testiramo i evaluiramo.
Sažetak (engleski)
In this thesis we give a detailed description of a weighted graph partitioning method using the spectral normalized cut criterion. We argue the choice of such a criterion in the context of good partitioning requirements. In the theoretical development of the method we mainly rely on elementary definitions and results from spectral theory. First we redefine the partitioning problem as an optimization problem that we then relax. The solutions to the relaxed optimization problem are given by orthogonal transformations of the first few eigenvectors of a symmetric matrix. In the next step we try to find a solution to the original discrete problem that is closest to the obtained set of continuous optima. We can achieve this in an iterative fashion by alternately applying two procedures: using non-maximum suppression we find the discrete solution closest to a continuous one, while the continuous optimum that is a good approximation of a discrete one can be obtained by solving the orthogonal Procrustes problem. We can guarantee that the obtained solution is nearly global-optimal. In the last chapter we implement the method which we then test and evaluate.
Ključne riječi
Ključne riječi (engleski)
Jezikhrvatski
URN:NBNurn:nbn:hr:217:351592
Studijski programNaziv: 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 resursaTekst
Način izrade datotekeIzvorno digitalna
Prava pristupaOtvoreni pristup
Uvjeti korištenjaIkona licence Zaštićeno autorskim pravom.
Datum i vrijeme pohrane2018-06-29 10:37:30