| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

Search the digital library catalog Help

Query: search in
search in
search in
search in
* old and bologna study programme

Options:
  Reset


1 - 10 / 198
First pagePrevious page12345678910Next pageLast page
1.
2.
3.
4.
5.
3-BARVANJE GRAFOV IN OPTIMIZACIJA Z ROJI DELCEV
Aleš Krauser, 2009, undergraduate thesis

Abstract: Optimizacija z roji delcev je relativno nova evolucijska tehnika, ki je bila prvotno razvita za reševanje zveznih problemov. Kasneje so se pojavile različne izvedbe za reševanje diskretnih problemov. Na začetku se seznanimo z osnovno in diskretno optimizacijo z roji delcev. Nato spoznamo parametre, ki nastopajo v optimizaciji z roji delcev. Opišemo problem 3-barvanja grafov, ki smo ga izbrali kot diskretni problem za izvajanje optimizacije z roji delcev. Temu sledi opis znanih tradicionalnih in evolucijskih algoritmov za reševanje problema 3-barvanja grafov. Nato predstavimo dva pristopa reševanja tega diskretnega problema z optimizacijo z roji delcev. Na koncu primerjamo rezultate, ki smo jih dobili z optimizacijo z roji delcev z rezultati, ki so dobljeni z hibridnim samo-prilagodljivim evolucijskim algoritmom.
Keywords: optimizacija z roji delcev, 3-barvanje grafov, hibridno samo-prilagodljivi evolucijski algoritem
Published: 02.10.2009; Views: 2245; Downloads: 133
.pdf Full text (1,37 MB)

6.
Prometno uravnoteženi usmerjevalni algoritmi za brezžična senzorska omrežja : doktorska disertacija
Karl Benkič, 2010, dissertation

Abstract: Brez i ne komunikacije, kot na primer GSM tehnologija, WiFi vstopne točke, digitalna televizija in drugo postajajo v naših ž ivljenjih vedno bolj prisotna. Cenovna dostopnost komponent in nagel industrijski razvoj je vzpodbudil uporabo brezžičnih komunikacij tudi v osebne namene (kot primer podajmo samo GSM telefon in BlueTooth slušalko). Ljudje smo vedno bolj vpeti v svet komunikacij pa se često tega niti ne zavedamo. Vedno manjše, cenejše in zmogljivejše komponente so pripomogle k uporabi brezžičnih komunikacij v prej nepredstavljivih aplikacijah. Eno izmed takšnih aplikacij predstavljajo tudi brezžična senzorska omrežja (BSO). Brezžična senzorska omrežja so omrežja, sestavljena iz majhnih, baterijsko napajanih, pametnih senzorjev sposobnih brezžične komunikacije. Njihova radijska vidljivost je ponavadi majhna, cena pa tako nizka, da senzorske enote po uporabi preprosto zavržemo. Namenjena so spremljanju različnih fenomenov (sezmiologija, spremljanje habitata, spremljanje požarov, vojaške aplikacije... ). Med intenzivnejše raziskave brežičnih senzorskih omrežij že od vsega začetka spadajo raziskave usmerjevalnih algoritmov. Standardni usmerjevalni algoritmi uporabljeni v standardih IEEE 802.11x zaradi posebnosti BSO niso uporabni ali pa je njihova uporaba v BSO nesmiselna (zaradi velike potrošnje procesorskih ali spominskih virov ter energije). Posledično so raziskave usmerjene v za brezžična senzorska omrežja posebej prilagojene protokole usmerjanja prometa. V tezi smo se omejili na raziskave prometno uravnote enih algoritmov, ki sporočila pošiljajo po najkrajši možni poti (minimalno število etap). Raziskovali smo usmerjanje v statičnih BSO, kjer senzorji s časom ne spreminjajo svoje lege ali pa jo spreminjajo v intenziteti, ki ni bistvena za delovanje algoritmov. Predlagan usmerjevalni protokol je sestavljen iz dveh algoritmov: BFS algoritma in optimalnega polprirejanja. Algoritem za izra un minimalnega števila potrebnih etap, da je sporočilo poslano od vozlišča do bazne postaje je v bistvu dodelan BFS algoritem. Z BFS algoritmom izračunamo nivo vsakega vozlišča (nivo predstavlja oddaljenost od bazne postaje v etapah) v omrežju. Vozlišča iz dveh sosednjih nivojev za potrebe algoritma iskanja optimalnega polprirejanja predstavimo kot virtualni dvodelni graf. Teh virtualnih grafov je za ena manj kot število nivojev vozlišč (n -1). Na vsak kem virtualnem dvodelnem grafu posebej izračunamo optimalno polprirejanje. Cilj optimalnega polprirejanja je uravnotežitev prometa med vozlišči. Skupen rezultat obeh algoritmov je topologija imenovana topologija prirejanja. Topologija prirejanja je v bistvu vpeto drevo, ki ga uporablja protokol usmerjanja. Kvaliteto uravnotežitve na vseh nivojih vpetega drevesa ocenimo po metriki faktorja uravnotežitve (Chebyshevo sumo). V delu predlagamo tudi nov, hitrejši algoritem za izračun optimalnega polprirejanja. Eksperimenti so pokazali, da je izvajanje algoritma vsaj 15 % hitrejše kot pri ostalih, do sedaj znanih algoritmih. Za testiranje in simuliranje usmerjevalnega protokola smo uporabili standardni MAC protokol (IEEE 802.15.4), temelje na CSMA-CA izmikanju kolizij, kateremu smo dodali e RTS/CTS kontrolne okvirje. Za potrditev teze smo uporabili simulacijsko okolje OPNET kjer smo razvili model prototipa brezžičnega senzorskega vozlišča SPaRCMosquito razvitega v laboratoriju. Rezultati simulacij so potrdili, da protokol zaradi svojega načina delovanja pripomore k manj i porabi energije celotnega senzorskega omre ja in kraj im latentnim časom sporočil poslanih od senzorskih vozlišč do bazne postaje. Predlagan usmerjevalni algoritem
Keywords: brezžična senzorska omrežja, protokoli usmerjanja, teorija grafov, uravnoteževanje obremenitev
Published: 12.10.2010; Views: 2386; Downloads: 208
.pdf Full text (8,60 MB)

7.
GEODETSKO IN OVOJNIŠKO ŠTEVILO PRODUKTOV GRAFOV
Jasna Mrkonjić, 2010, undergraduate thesis

Abstract: Diplomsko delo obravnava geodetsko in ovojniško število standardnih produktov grafov s poudarkom na kartezičnem in krepkem produktu. V prvem delu so zapisane osnovne definicije s področja teorije grafov, ki se uporabljajo v nadaljevanju. V naslednjem poglavju si pogledamo grafe, za katere je geodetsko število enako ali za ena manjše od števila vozlišč ter enako za ovojniško število. Sledi poglavje v katerem se osredotočimo na geodetsko in ovojniško število v kartezičnem produktu grafov in si pogledamo robne množice. Zadnji del diplomske naloge je namenjen geodetskemu in ovojniškemu številu v krepkem produktu grafov, kjer so podane meje za obe števili in natančne vrednosti za določene tipe grafov.
Keywords: konveksnost, ovojnica, geodetska množica grafa, geodetsko število, ovojniško število, poln graf, cikel, produkt grafov, kartezični produkt grafov, krepki produkt grafov, robne množice
Published: 15.12.2010; Views: 1974; Downloads: 100
.pdf Full text (754,64 KB)

8.
KRONECKERJEVI GRAFI
Vesna Balan, 2010, undergraduate thesis

Abstract: Diplomsko delo se osredotoča na preučevanje Kroneckerjevih grafov. Najprej je predstavljena motivacija za vpeljavo in študij Kroneckerjevih grafov. V nadaljevanju je definiran Kroneckerjev ali tenzorski produkt matrik ter Kroneckerjev produkt grafov in njune osnovne lastnosti. V naslednjih poglavjih se pozornost nameni lastnostim Kroneckerjevih in stohastičnih Kroneckerjevih grafov. Predstavljen je porazdelitveni zakon stopnje posameznih vozlišč teh grafov. Dokazana sta zgostitveni potenčni zakon med številom vozlišč in številom povezav ter ohranjanje efektivnega premera glede na začetni graf. Pri stohastičnih Kroneckerjevih grafih so podani potrebni in zadostni pogoji za povezanost ter obstoj velike povezane komponente tega grafa. Dokazano je tudi, če je graf povezan, je premer v tem grafu konstanten. Na koncu so prikazani primeri praktične uporabe teorije, predstavljene skozi vso diplomsko nalogo.
Keywords: Kroneckerjevi grafi, stohastični Kroneckerjevi grafi, grafi omrežij, direktni produkt grafov, Kroneckerjev produkt matrik
Published: 06.09.2011; Views: 1295; Downloads: 71
.pdf Full text (1,27 MB)

9.
PARTICIJSKA DIMENZIJA GRAFOV
Adrijana Tivadar, 2011, undergraduate thesis

Abstract: Diplomsko delo obravnava particijsko dimenzijo grafov in je sestavljeno iz treh poglavij. V prvem poglavju bomo predstavili osnovne pojme iz teorije grafov in spoznali bomo štiri najbolj poznane produkte grafov, s poudarkom na kartezičnem produktu. Drugo poglavje bomo namenili predstavitvi dveh, za nas najbolj pomembnih dimenzij grafov. To sta metrična in particijska dimenzija grafov. Najprej bomo definirali metrično dimenzijo grafov in spoznali njene lastnosti. Nato se bomo posvetili particijski dimenziji grafov in njenim lastnostim. Pri obeh dimenzijah bomo za boljšo predstavitev podali tudi nekaj primerov. Na koncu tega poglavja pa si bomo še pogledali povezanost omenjenih dveh dimenzij. V zadnjem poglavju bomo definirali particijsko dimenzijo kartezičnega produkta grafov. Pogledali si bomo zgornjo mejo te dimenzije, nato bomo spoznali njeno povezavo z metrično dimenzijo in na koncu navedli še dva aktualna odprta problema.
Keywords: rešljiva particija, particijska dimenzija grafov, rešljiva množica, metrična dimenzija grafov, kartezični produkt grafov.
Published: 28.06.2011; Views: 1936; Downloads: 131
.pdf Full text (4,31 MB)

10.
RAVNINSKOST GRAFOV
Kristjan Fotivec, 2011, undergraduate thesis

Abstract: V diplomskem delu predstavimo merjenja ravninskosti grafov. Graf G je ravninski, če ga lahko narišemo v ravnini tako, da noben par povezav nima skupnega vozlišča, razen v vozlišču, ki je njuno skupno krajišče. Obravnavamo načine za določanje ravninskosti s pomočjo metode iskanja podgrafa, ki je subdivizija od K5 ali K3,3, določanja prekrižnega števila, debeline grafov in delitvenega števila pri določenih grafov. Grafa K5 in K3,3 nista ravninska grafa, torej če G vsebuje podgraf, ki je subdivizija od K5 ali K3,3, potem G ni ravninski. Debelina grafa G, t(G), je minimalno število ravninskih grafov iz katerih lahko sestavimo graf G. Torej t(G)=k pomeni, da je enak G=H1UH2U,...,Hk, kjer je Hi ravninski za vsaki i in graf G ne moremo razstaviti v k-1 ravninskih grafov. Na koncu diplomske naloge še predstavimo Heawood-ov problem dežel. Heawood je dokazal, da je vsak zemljevid 2-dežel lahko pobarvan z 12 barvami in obstaja zemljevid 2-dežel, ki potrebuje 12 barv.
Keywords: ravninskost grafov, subdivizija grafa, prekrižno število, debelina grafa, delitveno število, Heawood-ov problem dežel
Published: 10.10.2011; Views: 1443; Downloads: 160
.pdf Full text (1,55 MB)

Search done in 0.17 sec.
Back to top
Logos of partners University of Maribor University of Ljubljana University of Primorska University of Nova Gorica