(UM)
-
Algoritmični pristopi k problemu maksimalnega prereza grafov : magistrsko deloSmogavec, KsenijaProblem 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.Vrsta gradiva - magistrsko delo ; neleposlovje za odrasleZaložništvo in izdelava - Maribor : [K. Smogavec], 2014Jezik - slovenskiCOBISS.SI-ID - 20542216
Avtor
Smogavec, Ksenija
Drugi avtorji
Bokal, Drago, 1978-
Teme
Univerzitetna in visokošolska dela |
teorija grafov |
maksimalni prerez grafa |
semidefinitno programiranje |
hevristika |
NP-polni problemi |
magistrska dela |
graph theory |
max cut |
semidefinite programming |
heuristics |
NP-complete problem |
master theses
Knjižnica | Signatura – lokacija, inventarna št. ... | Status izvoda | Rezervacija |
---|---|---|---|
Miklošičeva knjižnica - FPNM, Maribor | D MAG 51 SMOGAVEC K. Algoritmični IN: 920140031 |
prosto - za čitalnico | |
Univerzitetna knjižnica Maribor | Skladišče II 85885 | prosto - za čitalnico |
Vnos na polico
Trajna povezava
- URL:
Faktor vpliva
Dostop do baze podatkov JCR je dovoljen samo uporabnikom iz Slovenije. Vaš trenutni IP-naslov ni na seznamu dovoljenih za dostop, zato je potrebna avtentikacija z ustreznim računom AAI.
Leto | Faktor vpliva | Izdaja | Kategorija | Razvrstitev | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Baze podatkov, v katerih je revija indeksirana
Ime baze podatkov | Področje | Leto |
---|
Povezave do osebnih bibliografij avtorjev | Povezave do podatkov o raziskovalcih v sistemu SICRIS |
---|---|
Smogavec, Ksenija | |
Bokal, Drago, 1978- | 22402 |
Vir: Osebne bibliografije
in: SICRIS
Izberite prevzemno mesto:
Prevzem gradiva po pošti
Naslov za dostavo:
Med podatki člana manjka naslov.
Storitev za pridobivanje naslova trenutno ni dostopna, prosimo, poskusite še enkrat.
S klikom na gumb "V redu" boste potrdili zgoraj izbrano prevzemno mesto in dokončali postopek rezervacije.
S klikom na gumb "V redu" boste potrdili zgoraj izbrano prevzemno mesto in naslov za dostavo ter dokončali postopek rezervacije.
S klikom na gumb "V redu" boste potrdili zgoraj izbrani naslov za dostavo in dokončali postopek rezervacije.
Obvestilo
Trenutno je storitev za avtomatsko prijavo in rezervacijo nedostopna. Gradivo lahko rezervirate sami na portalu Biblos ali ponovno poskusite tukaj kasneje.
Izbira mesta prevzema
Gradivo iz matične enote je brezplačno. Če je gradivo na mesto prevzema dostavljeno iz drugih enot, lahko knjižnica to storitev zaračuna.
Mesto prevzema | Status gradiva | Rezervacija |
---|
Rezervacija v teku
Prosimo, počakajte trenutek.
Rezervacija je uspela.
Rezervacija ni uspela.
Rezervacija...
Članska izkaznica:
Mesto prevzema: