Vaš brskalnik ne omogoča JavaScript!
JavaScript je nujen za pravilno delovanje teh spletnih strani. Omogočite JavaScript ali uporabite sodobnejši brskalnik.
|
|
SLO
|
ENG
|
Piškotki in zasebnost
DKUM
EPF - Ekonomsko-poslovna fakulteta
FE - Fakulteta za energetiko
FERI - Fakulteta za elektrotehniko, računalništvo in informatiko
FF - Filozofska fakulteta
FGPA - Fakulteta za gradbeništvo, prometno inženirstvo in arhitekturo
FKBV - Fakulteta za kmetijstvo in biosistemske vede
FKKT - Fakulteta za kemijo in kemijsko tehnologijo
FL - Fakulteta za logistiko
FNM - Fakulteta za naravoslovje in matematiko
FOV - Fakulteta za organizacijske vede
FS - Fakulteta za strojništvo
FT - Fakulteta za turizem
FVV - Fakulteta za varnostne vede
FZV - Fakulteta za zdravstvene vede
MF - Medicinska fakulteta
PEF - Pedagoška fakulteta
PF - Pravna fakulteta
UKM - Univerzitetna knjižnica Maribor
UM - Univerza v Mariboru
UZUM - Univerzitetna založba Univerze v Mariboru
COBISS
Ekonomsko poslovna fakulteta
Fakulteta za kmetijstvo in biosistemske vede
Fakulteta za logistiko
Fakulteta za organizacijske vede
Fakulteta za varnostne vede
Fakulteta za zdravstvene vede
Knjižnica tehniških fakultet
Medicinska fakulteta
Miklošičeva knjižnica - FPNM
Pravna fakulteta
Univerzitetna knjižnica Maribor
Večja pisava
|
Manjša pisava
Uvodnik
Iskanje
Brskanje
Oddaja dela
Za študente
Za zaposlene
Statistika
Prijava
Prva stran
>
Izpis gradiva
Izpis gradiva
Naslov:
Algoritmični pristopi k problemu maksimalnega prereza grafov
Avtorji:
ID
Smogavec, Ksenija
(Avtor)
ID
Bokal, Drago
(Mentor)
Več o mentorju...
Datoteke:
MAG_Smogavec_Ksenija_2014.pdf
(2,88 MB)
MD5: 33B635AD38E31C8C1CF92F1A8EF34BA7
Jezik:
Slovenski jezik
Vrsta gradiva:
Magistrsko delo
Tipologija:
2.09 - Magistrsko delo
Organizacija:
FNM - Fakulteta za naravoslovje in matematiko
Opis:
Problem maksimalnega prereza grafa je najti takšno razbitje množice vozlišč grafa, da bo vsota uteži na povezavah, ki povezujejo ta dva kosa razbitja, največja. Problem maksimalnega prereza je NP-poln in je eden izmed osnovnih 21-ih Karpovih problemov. Zaradi njegove teoretične in praktične pomembnosti, aplikacije ima v statistični fiziki in vezjih, je bilo zapisanih že kar nekaj različnih aproksimacijskih algoritmov, hevristik ali kombinacij optimizacijskih metod in hevristik, ki rešujejo problem maksimalnega prereza. V magistrskem delu predstavimo problem maksimalnega prereza na posebnih razredih grafov, na katerih lahko najdemo rešitev problema v polinomskem času. Tretje poglavje je namenjeno Goemans Williamsonovemu aproksimacijskemu algoritmu, ki s pomočjo semidefinitnega programa najde rešitev, katere garantirana vrednost je vsaj 87 % optimalne rešitve in predstavlja prelom na področju aproksimacijskih algoritmiov. Poleg njunega algoritma predstavimo še Biq Mac algoritem, ki doseže skoraj optimalne rešitve za grafe z n ≤ 100, in dualno skaliran algoritem, ki je primeren tudi za velike redke grafe. Temu sledi predstavitev posplošitve Goemans Williamsonovega algoritma za maksimalen k-prerez. Nazadnje predstavimo še nekaj hevristik, ki so učinkovite pri iskanju maksimalnega prereza.
Ključne besede:
maksimalen prerez grafa
,
semidefinitno programiranje
,
hevristika
,
NP-poln problem
Kraj izida:
Maribor
Založnik:
[K. Smogavec]
Leto izida:
2014
PID:
20.500.12556/DKUM-44031
UDK:
519.17(043.2)
COBISS.SI-ID:
20542216
NUK URN:
URN:SI:UM:DK:VUWAJUW2
Datum objave v DKUM:
21.05.2014
Število ogledov:
2079
Število prenosov:
157
Metapodatki:
Področja:
FNM
Citiraj gradivo
Navadno besedilo
BibTeX
EndNote XML
EndNote/Refer
RIS
ABNT
ACM Ref
AMA
APA
Chicago 17th Author-Date
Harvard
IEEE
ISO 690
MLA
Vancouver
:
SMOGAVEC, Ksenija, 2014,
Algoritmični pristopi k problemu maksimalnega prereza grafov
[na spletu]. Magistrsko delo. Maribor : K. Smogavec. [Dostopano 13 april 2025]. Pridobljeno s: https://dk.um.si/IzpisGradiva.php?lang=slv&id=44031
Kopiraj citat
Skupna ocena:
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
(0 glasov)
Vaša ocena:
Ocenjevanje je dovoljeno samo
prijavljenim
uporabnikom.
Objavi na:
Podobna dela iz repozitorija:
Primerjalna analiza spletnih bank v Sloveniji
Elektronsko bančništvo
Analiza programskih orodij za testiranje dizajna mobilnih aplikacij
Spletno bančništvo za podjetnike na primeru UniCredit Bank
Oblikovanje mobilne aplikacije za upravljanje in plačevanje parkirnine
Podobna dela iz ostalih repozitorijev:
Statistična analiza zadovoljstva komitentov z internetnim bančništvom v Sloveniji
Vpliv digitalizacije na uporabnike bančnih storitev v Sloveniji
Vpliv digitalizacije na uporabniško izkušnjo hotelskih gostov
Načrtovanje in izdelava spletnega mesta ter analiza uporabniške izkušnje
Načrtovanje uporabniške izkušnje za mobilno aplikacijo Herq.me
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše podrobnosti ali sproži prenos.
Sekundarni jezik
Jezik:
Angleški jezik
Naslov:
Algorithmic approach to max cut problem
Opis:
Max cut problem consists of partitioning the vertices of undirected weighted graph into two subsets, such that the sum of the weights of the edges that connect vertices in different partitions is maximized. Max cut problem is NP-complete and is one of Karp's 21 problems. Because of its theoretical and practical importance, applications in statistical physics and circuit layout design, various approximation algorithms, heuristics or combinations of optimization and heuristics methods have been developed to solve max cut problem. In this master thesis we describe max cut problem on classes of graphs for which max cut is solvable in polynomial time. Third chapter presents Goemans Williamson approximation algorithm that uses semidefinite programming and provides result of which expected value is at least 87 % times of optimal solution and presents break-through in field of approximation algorithms. We also present Biq Mac algorithm, which can obtain nearly optimal solutions for graphs with n ≤ 100, and dual scaling algorithm, which has been used to solve large scale semidefinite programs. Additionally a generalised Goemans Williamson algorithm for max k-cut is given. The final chapter presents some heuristics that are efficient in solving max cut problem.
Ključne besede:
max cut
,
semidefinite programming
,
heuristics
,
NP-complete problem
Komentarji
Dodaj komentar
Za komentiranje se morate
prijaviti
.
Komentarji (0)
0 - 0 / 0
Ni komentarjev!
Nazaj
