1. Razširjanje in ojačano pronicanje v produktih grafovJaka Hedžet, 2025, doktorska disertacija Opis: V doktorski disertaciji obravnavamo spreminjanje stanja vozlišč grafa po pravilu procesa, imenovanega $r$-ojačano pronicanje. Bolj podrobno se lotimo preučevanja tega procesa na standardnih grafovskih produktih in vpeljemo nov pojem, imenovan razširjanje, ki sestoji iz kombinacije pravil ojačanega pronicanja ter ničelne prisile oziroma $k$-prisile. Po uvodnih poglavjih je disertacija razdeljena na pet delov, znotraj katerih predstavimo rezultate na omenjeno temo.
V prvem delu obravnavamo proces pronicanja na kartezičnih mrežah, ki so kartezični produkti poti. Natančneje, določimo $3$-ojačitveno število pronicanja za kartezične mreže velikosti $3 \times n$ in $5 \times n$, kjer je $n$ poljubno naravno število. Dodatno omejimo vrednost $3$-ojačitvenega števila za kartezično mrežo velikosti $4\times n$ na dve možni vrednosti.
V drugem delu disertacije se usmerimo v preučevanje pronicanja na krepkih produktih grafov, in sicer za poljubno število faktorjev. Določimo vrednosti za prag $r$, pri katerih $r$-ojačitveno število produkta $k$ grafov zasede svojo trivialno spodnjo mejo, ki je enaka $r$. Nadalje postavimo dodatne pogoje za faktorje krepkega produkta, pri katerih ohranimo enako lastnost $r$-ojačitvenega števila za višji prag $r$. Posebej se lotimo tudi najmanjšega primera, ki ni zajet v teh rezultatih, to je produkt dveh faktorjev in prag $r=3$, kjer karakteriziramo tiste krepke produkte, katerih $3$-ojačitveno število je enako $3$. Raziskavo razširimo na neskončne grafe, kjer opazujemo obnašanje $r$-ojačitvenega števila na krepkih produktih dvosmernih neskončnih poti.
V tretjem delu se lotimo še zadnjega izmed treh standardnih komutativnih grafovskih produktov, to je direktnega produkta grafov. Določimo nekaj zgornjih mej za $r$-ojačitveno število direktnega produkta dveh grafov in karakteriziramo grafe, ki dosežejo dve zgornji meji v primeru praga $r=2$. Določimo tudi natančne vrednosti za $r$-ojačitveno število produkta dveh poti poljubnih dolžin in med drugim okarakteriziramo tiste direktne produkte grafov, katerih $2$-ojačitveno število je enako redu enega izmed faktorjev.
Četrti in zadnji del doktorske disertacije posvetimo vpeljavi in preučevanju pojma razširjanje. Posplošimo do sedaj znane rezultate iz procesov pronicanja in $k$-prisile ter zapolnimo nekatere vrzeli pri rezultatih o kartezičnih mrežah in dokažemo, da je problem razširjanja NP-težek. Z vidika razširjanja dodatno preučujemo kubične grafe brez krempljev, kjer določimo bodisi natančne vrednosti, bodisi meje za vse variante razširjevalnega števila, in drevesa, kjer predstavimo algoritem za iskanje najmanjše širitvene množice poljubnega drevesa.
Ključne besede: ojačano pronicanje, ojačitveno število pronicanja, razširjanje, kartezični produkt, direktni produkt, krepki produkt, mreža, kubični graf, drevo.
Objavljeno v DKUM: 06.10.2025; Ogledov: 0; Prenosov: 13
 Celotno besedilo (581,56 KB) |
2. Odprto pakiranje povezav grafa : na študijskem programu 2. stopnje Izobraževalna matematikaAleksandra Keše, 2025, magistrsko delo Opis: V magistrskem delu preučujemo lastnosti odprtega pakiranja povezav grafa. Za lažje razumevanje obravnavanega pojma najprej predstavimo osnovne pojme in rezultate iz teorije grafov ter opišemo osnovne družine grafov. V drugem delu magistrske naloge opišemo pojma odprto pakiranje povezav in povezavno odprto pakirno število ter ju predstavimo na osnovnih družinah grafov. Tretji del magistrske naloge je namenjen preučevanju mej za povezavno odprto pakirno število poljubnega grafa in identificiranju družin grafov, ki te meje dosežejo. V zadnjem delu magistrske naloge obravnavamo problem odprtega pakiranja povezav grafa kot NP-poln problem za grafe z univerzalnim vozliščem, Eulerjeve dvodelne grafe in ravninske grafe z maksimalno stopnjo največ 4. Opišemo postopek za izračun povezavnega odprtega pakirnega števila dreves in zapišemo, da obstaja algoritem, ki to število poišče v linearnem času.
Ključne besede: odprto pakiranje povezav, povezavno odprto pakirno število, drevo, časovna zahtevnost algoritma, NP-poln problem
Objavljeno v DKUM: 07.07.2025; Ogledov: 0; Prenosov: 45
Celotno besedilo (1,62 MB) |
3. Interaktivno upodabljanje digitalnega modela reliefa s štiriškim drevesom : diplomsko deloAnej Krajnc, 2025, diplomsko delo Opis: Diplomsko delo opisuje implementacijo upodabljanja digitalnega modela reliefa s štiriškim drevesom, trikotniško mrežo, z Blinn-Phongovo osvetlitvijo in sivinsko barvo. Cilj je pohitriti prikaz digitalnega modela reliefa s štiriškim drevesom. Ugotovili smo, da je prikaz s štiriškim drevesom hitrejši od prikaza celotnega modela reliefa, vendar ima večjo pomnilniško zahtevnost. Hitrost izrisa je odvisna tudi od števila oglišč, kar smo ugotovili z uporabo treh digitalnih modelov reliefa z različnim številom oglišč.
Ključne besede: štiriško drevo, digitalni model reliefa, trikotniška mreža, Blinn-Phongov osvetlitveni model, OpenGL
Objavljeno v DKUM: 08.05.2025; Ogledov: 0; Prenosov: 20
Celotno besedilo (1,61 MB) |
4. Super dominantno število grafaTajda Remic, 2024, magistrsko delo Opis: Množica $D$ vozlišč grafa $G$ je super dominantna množica, če za vsako vozlišče $v \in V(G)-D$ obstaja vozlišče $u \in D$, ki je sosednje z $v$ in velja, da je $v$ edini sosed od $u$ v $V(G)-D$. Velikost najmanjše super dominantne množice grafa $G$ je super dominantno število grafa $G$, ki ga označujemo z $\gamma_{sp}(G)$.
V magistrskem delu raziskujemo lastnosti super dominantnega števila. V ta namen najprej predstavimo osnovne pojme na grafih, predstavimo nekaj pomembnih družin grafov in veliko različnih grafovskih invariant, ki so povezane s super dominantnim številom.
V drugem delu pričnemo z raziskovanjem super dominantnih množic. Najprej izračunamo super dominantno število za nekaj pomembnih družin grafov in dokažemo, da za vsak povezan graf na vsaj dveh vozliščih velja: $\frac{n}{2} \leq \gamma_{sp}(G)\leq |V(G)|-1$. Nato super dominantno število raziskujemo na drevesih. Dokažemo boljšo zgornjo mejo super dominantnega števila dreves in se ukvarjamo z grafi, ki to mejo dosežejo. Na koncu super dominantno število dreves navzgor omejimo še z $2$-dominantnim številom grafa. V zadnjem delu magistrske naloge predstavimo zvezo super dominantnega števila z mnogimi grafovskimi invariantami, kot so velikost največjega prirejanja, neodvisnostno število in mnoge druge.
Ključne besede: super dominantno število, super dominantna množica, drevo, neodvisnostno število, dominantno število, prirejanje
Objavljeno v DKUM: 11.06.2024; Ogledov: 153; Prenosov: 57
Celotno besedilo (6,92 MB) |
5. Analiza in primerjava podatkovnih struktur različnih platform verig blokov : diplomsko deloJan Bajec, 2022, diplomsko delo Opis: Veriga blokov je decentralizirana podatkovna struktura s katero hranimo podatke, ki jih je praktično nemogoče manipulirati. Obstaja več različnih platform, ki so na svoj način implementirale svojo verigo blokov. V zaključnem delu bomo analizirali šest različnih platform verig blokov in jih med seboj tudi primerjali. Izbrali smo si tri platforme javnih omrežij: Bitcoin, Ethereum, Polkadot in tri platforme konzorcijskih omrežij: Hyperledger Fabric, Hyperledger Besu in Corda.
Ključne besede: veriga blokov, podatkovna struktura, javno omrežje, konzorcijsko omrežje, Merklovo drevo
Objavljeno v DKUM: 07.11.2022; Ogledov: 762; Prenosov: 90
Celotno besedilo (1,85 MB) |
6. Lomljena drevesa : magistrsko deloNina Turnšek, 2022, magistrsko delo Opis: V magistrskem delu je predstavljena podatkovna struktura imenovana lomljeno drevo. Gre za dvojiško iskalno drevo, kjer se oblika drevesa spremeni po vsakem posegu (operaciji) v drevo. Vozlišče, nad katerim izvajamo poljubno operacijo, je na koncu operacije vedno v korenu drevesa. Postopku, ki vozlišče premakne v koren drevesa, pravimo \emph{lomljenje}. Namen lomljenih dreves je, da so podatki, ki jih pogosto uporabljamo, hitro dostopni. Tako podatki, ki jih večkrat uporabljamo, ostanejo bližje vrha drevesa in jih ob naslednji uporabi hitreje najdemo. Podatki, ki so redko v uporabi, se nahajajo nižje v drevesu.
Na podlagi amortizirane časovne zahtevnosti je analizirana hitrost delovanja osnovnih operacij lomljenih dreves. Amortizirana časovna zahtevnost je povprečen čas posamezne operacije v najslabšem zaporedju operacij. V magistrskem delu je predstavljen tudi implementiran program za lomljena drevesa, v katerem so definirane osnovne operacije na lomljenih drevesih. Nazadnje je narejena še analiza hitrosti delovanja operacij implementiranega programa za lomljena drevesa in primerjava lomljenih dreves z drugimi uravnoteženimi drevesi.
Ključne besede: lomljeno drevo, lomljenje, amortizirana časovna zahtevnost, uravnotežena drevesa
Objavljeno v DKUM: 28.10.2022; Ogledov: 763; Prenosov: 63
Celotno besedilo (2,11 MB)
Gradivo ima več datotek! Več... |
7. Uporaba pregledne plošče Dash za analizo filmov v Pythonu : diplomsko deloKristian Grgić, 2022, diplomsko delo Opis: V diplomskem delu je obravnavano področje strojnega učenja. Predstavljena je pregledna plošča Dash, ki jo uporabimo za prikaz rezultatov in algoritmi, ki jih uporabimo v okviru diplomske naloge za ustvaritev modela znanja in ekstrakcijo ključnih besed iz opisa pripadajočega filma. Po predstavitvi je opisan proces ustvaritve podatkovne zbirke filmov in zasnove produkta. Rezultat diplomskega dela je spletna aplikacija, ki uporabniku omogoča dinamično in interaktivno spreminjanje oz. prilagajanje vhodnih parametrov in izbiro algoritma za ustvaritev modela znanja na podlagi katerega napovedujemo zaslužek posameznega filma, skupne rezultate oz. napovedi pa prikažemo na pregledni plošči. Uporabniku prav tako omogočimo izbiro filma, kjer na podlagi njegovega opisa prikažemo vse ključne besede.
Ključne besede: Pregledna plošča Dash, Analiza filmov, Strojno učenje, Ekstrakcija ključnih besed, Regresijsko drevo, Naivni Bayes, RAKE algoritem
Objavljeno v DKUM: 26.10.2022; Ogledov: 609; Prenosov: 50
Celotno besedilo (1,34 MB) |
8. Sodobne igre barvanj in sorodne igre na grafihDaša Štesl, 2022, doktorska disertacija Opis: V doktorski disertaciji obravnavamo v zadnjih letih vpeljane variacije klasične igre barvanja in njim sorodne igre na grafih. Doktorsko delo sestoji iz štirih delov, znotraj katerih predstavimo nova spoznanja na omenjeno temo.
V prvem delu disertacije obravnavamo indicirano igro barvanja kartezičnih produktov grafov. Natančneje, določimo indicirano igralno kromatično število kartezičnih produktov grafov, katerih indicirano kromatično število znaša 3, s polnim dvodelnim grafom. Dodatno obravnavamo indicirano kromatično število kartezičnih produktov bločnih grafov in dreves ter indicirano kromatično število kartezičnega produkta dveh ciklov.
V drugem delu disertacije se posvetimo študiji štirih variacij neodvisnostne igre barvanja, ki so posebna oblika klasične igre barvanja, pri kateri igralca ne preideta na višjo raven, dokler ne izčrpata vseh možnosti za uporabo dane barve. Dobljene igralne invariante primerjamo med seboj in s klasičnim igralnim kromatičnim številom. Poleg tega ugotovimo, da neodvisnostno igralno kromatično število v razredu dreves ni omejeno.
V tretjem delu preučujemo vozliščno kritične grafe glede na klasično igralno kromatično število, glede na indicirano kromatično število in glede na A-neodvisnostno ter AB-neodvisnostno igralno kromatično število. Med drugim obravnavamo vprašanje povezanosti grafov, ki so kritični glede na omenjene igralne grafovske invariante, obnašanje dane igralne invariante ob odstranitvi poljubnega vozlišča iz igralno vozliščno kritičnega grafa ter karakteriziramo igralno vozliščno kritične grafe, ki imajo majhno vrednost pripadajoče invariante.
Zadnji del doktorske disertacije posvetimo neodvisni dominacijski igri s preprečevanjem. Določimo neodvisni dominantni števili s preprečevanjem za poti in cikle. Poleg tega postavimo meje za obe variaciji omenjene igre ter karakteriziramo (povezane) grafe, ki dosežejo dobljeni meji. Dodatno opozorimo na tesno povezavo med neodvisno dominacijsko igro s preprečevanjem in pakirno igro barvanja v grafih z diametrom 2.
Ključne besede: igra barvanja, indicirana igra barvanja, neodvisnostna igra barvanja, neodvisna dominacijska igra, pakirna igra barvanja, kartezični produkt, drevo, vozliščno kritičen graf
Objavljeno v DKUM: 25.10.2022; Ogledov: 703; Prenosov: 80
Celotno besedilo (614,26 KB) |
9. Implementacija odločitvenih dreves v programskem jeziku Python : diplomsko deloGregor Gorjanc, 2020, diplomsko delo Opis: V diplomskem delu je predstavljeno področje strojnega učenja, del katerega so odločitvena drevesa. Čeprav je odločitveno drevo v osnovi pripomoček za vizualizacijo, nas v sklopu strojnega učenja zanima proces gradnje. Obstaja več algoritmov, ki s pomočjo podatkovnih množic generirajo odločitvena drevesa. V delu je podrobno predstavljeno delovanje algoritma C4.5, čigar implementacija predstavlja jedro naloge. Algoritem je bil implementiran s pomočjo programskega jezika Python. Po osnovni implementacijo je bil izveden proces optimizacije, kjer so preizkušene različne strukture programskega jezika Python. Po optimizaciji je bila izvedena primerjalna analiza delovanja. Izvedena je bila tudi primerjava delovanja implementiranega algoritma z obstoječo implementacijo J48.
Ključne besede: strojno učenje, odločitveno drevo, Python, C4.5
Objavljeno v DKUM: 03.07.2020; Ogledov: 1801; Prenosov: 287
Celotno besedilo (2,12 MB) |
10. Uporaba strojnega učenja za napovedovanje škodnih dogodkovVito Čoh, 2020, magistrsko delo Opis: V magistrskem delu je predstavljena uporaba posplošenega linearnega modela in različnih metod strojnega učenja v zavarovalništvu. Delo je razdeljeno na teoretični in praktični del.
Na začetku teoretičnega dela so opisani osnovni pojmi iz verjetnosti in zavarovalništva. Predstavljeno je tudi, kako zavarovalnice določijo višino premije. Nato sta predstavljena teoretično ozadje posplošenega linearnega modela in uporaba tega modela za napovedovanje višine škode. Na koncu teoretičnega dela pa je opisano strojno učenje in bolj podrobno so predstavljena odločitvena drevesa, naključni gozdovi ter nevronske mreže.
V praktičnem delu magistrskega dela pa so posplošeni linearni model, naključni gozd in nevronska mreža uporabljeni za napovedovanje višine škode pri avtomobilskem zavarovanju. Najprej so podatki predstavljeni ter ustrezno obdelani. Nato so določeni parametri posameznih modelov. Na koncu pa so modeli med seboj primerjani in izbran je najboljši model.
Ključne besede: zavarovalništvo, posplošeni linearni model, strojno učenje, odločitveno drevo, naključni gozd, nevronska mreža
Objavljeno v DKUM: 09.06.2020; Ogledov: 1857; Prenosov: 211
Celotno besedilo (1,53 MB) |
