| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Iskanje po katalogu digitalne knjižnice Pomoč

Iskalni niz: išči po
išči po
išči po
išči po
* po starem in bolonjskem študiju

Opcije:
  Ponastavi


1 - 10 / 29
Na začetekNa prejšnjo stran123Na naslednjo stranNa konec
1.
Span of a graph : keeping the safety distance
Iztok Banič, Andrej Taranenko, 2023, izvirni znanstveni članek

Opis: Inspired by Lelek's idea from [Disjoint mappings and the span of spaces, Fund. Math. 55 (1964), 199 -- 214], we introduce the novel notion of the span of graphs. Using this, we solve the problem of determining the \emph{maximal safety distance} two players can keep at all times while traversing a graph. Moreover, their moves must be made with respect to certain move rules. For this purpose, we introduce different variants of a span of a given connected graph. All the variants model the maximum safety distance kept by two players in a graph traversal, where the players may only move with accordance to a specific set of rules, and their goal: visit either all vertices, or all edges. For each variant, we show that the solution can be obtained by considering only connected subgraphs of a graph product and the projections to the factors. We characterise graphs in which it is impossible to keep a positive safety distance at all moments in time. Finally, we present a polynomial time algorithm that determines the chosen span variant of a given graph.
Ključne besede: strong span of a graph, direct span of a graph, Cartesian span of a graph, safety distance
Objavljeno v DKUM: 07.06.2024; Ogledov: 38; Prenosov: 5
.pdf Celotno besedilo (213,47 KB)
Gradivo ima več datotek! Več...

2.
Lomljena drevesa : magistrsko delo
Nina 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: 697; Prenosov: 44
.pdf Celotno besedilo (2,11 MB)
Gradivo ima več datotek! Več...

3.
Nonogrami : magistrsko delo
Aljaž Ferk, 2022, magistrsko delo

Opis: Nonogram je uganka, s katero lahko ob njenem reševanju narišemo sliko. Naloga je namenjena algoritmičnemu reševanju črno-belih nonogramov. S temi algoritmi lahko preverjamo pravilnost rešitve nonograma, lahko jih pa tudi uporabljamo kot pomoč pri človeškem reševanju. Najprej je predstavljen algoritem, ki lahko reši le nekatere nonograme, kasneje pa je ta algoritem nadgrajen tako, da najde vse možne rešitve. Odgovori se tudi vprašanje, kako dober je prvoten algoritem ob večanju dimenzij naključnih nonogramov. Predstavi se tudi hiter način barvanja kotov nekaterih nonogramov. Na koncu je predstavljen še vpliv nekaterih komponent na čas reševanja nonograma.
Ključne besede: nonogram, Chernoffova meja
Objavljeno v DKUM: 28.10.2022; Ogledov: 1489; Prenosov: 37
.pdf Celotno besedilo (1,30 MB)

4.
Primerjava algoritmov nenatančnega iskanja vzorcev v nizih : magistrsko delo
Karmen Potočan, 2022, magistrsko delo

Opis: V magistrskem delu predstavimo tri algoritme za reševanje problema $k$ razlik, in sicer rešitev z dinamičnim programiranjem, vključno z Ukkonenovo izboljšavo pričakovane časovne zahtevnosti, algoritem Galila in Parkova ter algoritem Tarhia in Ukkonena. Predstavljene algoritme implementiramo v programskem jeziku Python in izvedemo meritve časov izvajanja pri različnih testnih primerih, tako na angleškem kot slovenskem besedilu. Na koncu predstavimo rezultate meritev in na podlagi le-teh primerjamo algoritme.
Ključne besede: nizi, urejevalna razdalja, nenatančno iskanje vzorcev v nizih, problem $k$ razlik, algoritmi, analiza algoritmov
Objavljeno v DKUM: 28.10.2022; Ogledov: 579; Prenosov: 45
.pdf Celotno besedilo (723,33 KB)

5.
Razpon grafa : magistrsko delo
Lara Drožđek, 2022, magistrsko delo

Opis: V magistrskem delu predstavimo osnove teorije grafov, razpone grafa, z njimi povezane pojme in rezultate. Pojem razpona grafa povežemo z določanjem največje varnostne razdalje, ki jo lahko v grafu ohranjata dva igralca, ki želita obiskati vsa vozlišča (ali vse povezave) grafa. Predstavimo tudi tri pravila premikanja, ki jih morata igralca med premikanjem po grafu upoštevati, in jih povežemo s produkti grafov. V delu je podana tudi karakterizacija grafov, v katerih ni mogoče ohranjati pozitivne varnostne razdalje med igralcema, glede na podano pravilo premikanja po grafu. Na koncu predstavimo polinomski algoritem za določanje razpona grafa. Katero različico razpona grafa nam algoritem izračuna, je odvisno od podanega pravila premikanja po grafu.
Ključne besede: krepki razpon grafa, direktni razpon grafa, kartezični razpon grafa, produkti grafov, karakterizacija, algoritem, varnostna razdalja
Objavljeno v DKUM: 28.10.2022; Ogledov: 663; Prenosov: 59
.pdf Celotno besedilo (1,55 MB)

6.
Napovedovanje verjetnosti neplačila z nevronskimi mrežami
Urban Rajter, 2021, magistrsko delo

Opis: Umetna inteligenca se nanaša na teorijo in razvoj računalniških sistemov, ki lahko opravljajo naloge, ki običajno zahtevajo človeško inteligenco. Podskupina strojnega učenja je globoko učenje, kjer se umetne nevronske mreže, algoritmi, ki jih navdihujejo človeški možgani, učijo iz velikih količin podatkov. Podobno, kot se ljudje učimo iz izkušenj, bi algoritem globokega učenja večkrat ponovil isto nalogo in jo vsakič nekoliko prilagodil, da bi izboljšal rezultat. V tej magistrski nalogi so predstavljene nevronske mreže, tipi nevronskih mrež in njihova uporaba. Podrobneje je opisana uporaba nevronskih mrež za namene napovedovanja verjetnosti neplačila. Uporabljen je model globoke nevronske mreže na anonimiziranih podatkih podjetja. Opisan je postopek priprave podatkov in postopek učenja modela na vhodnih podatkih. Analiza končnega rezultata pove, da je uporaba nevronskih mrež smiselna, saj algoritem nudi visoko natančnost.
Ključne besede: strojno učenje, nevronske mreže, globoko učenje, globoke nevronske mreže, kreditno tveganje
Objavljeno v DKUM: 02.08.2021; Ogledov: 1518; Prenosov: 174
.pdf Celotno besedilo (1,95 MB)

7.
Distance-based Invariants and Measures in Graphs
Aleksander Kelenc, 2019, doktorska disertacija

Opis: This doctoral dissertation is concerned with aspects on distance related topics in graphs. We study three main topics, namely a recently introduced measure called the Hausdorff distance of graphs and two new graph invariants - the edge metric dimension and the mixed metric dimension of graphs. All three topics are part of the metric graph theory since they are tightly connected with the basic concept of distance between two vertices of a graph. The Hausdorff distance is a relatively new measure of the similarity of graphs. The notion of the Hausdorff distance considers a special kind of common subgraph of the compared graphs and depends on the structural properties outside of the common subgraph. We study the Hausdorff distance between certain families of graphs that often appear in chemical graph theory. Next to a few results for general graphs, we determine formulae for the distance between paths and cycles. Previously, there was no known efficient algorithm for the problem of determining the Hausdorff distance between two trees, and in this dissertation we present a polynomial-time algorithm for it. The algorithm is recursive and it utilizes the divide and conquer technique. As a subtask it also uses a procedure that is based on the well-known graph algorithm for finding a maximum bipartite matching. The edge metric dimension is a graph invariant that deals with distinguishing the edges of a graph. Let $G=(V(G),E(G))$ be a connected graph, let $w \in V(G)$ be a vertex, and let $e=uv \in E(G)$ be an edge. The distance between the vertex $w$ and the edge $e$ is given by $d_G(e,w)=\min\{d_G(u,w),d_G(v,w)\}$. A vertex $w \in V(G)$ distinguishes two edges $e_1,e_2 \in E(G)$ if $d_G(w,e_1) \ne d_G(w,e_2)$. A set $S$ of vertices in a connected graph $G$ is an edge metric generator of $G$ if every two distinct edges of $G$ are distinguished by some vertex of $S$. The smallest cardinality of an edge metric generator of $G$ is called the edge metric dimension and is denoted by $dim_e(G)$. The concept of the edge metric dimension is new. We study its mathematical properties. We make a comparison between the edge metric dimension and the standard metric dimension of graphs while presenting some realization results concerning the two. We prove that computing the edge metric dimension of connected graphs is NP-hard and give some approximation results. Moreover, we present bounds and closed formulae for the edge metric dimension of several classes of graphs. The mixed metric dimension is a graph invariant similar to the edge metric dimension that deals with distinguishing the elements (vertices and edges) of a graph. A vertex $w \in V(G)$ distinguishes two elements of a graph $x,y \in E(G)\cup V(G)$ if $d_G(w,x) \ne d_G(w,y)$. A set $S$ of vertices in a connected graph $G$ is a mixed metric generator of $G$ if every two elements $x,y \in E(G) \cup V(G)$ of $G$, where $x \neq y$, are distinguished by some vertex of $S$. The smallest cardinality of a mixed metric generator of $G$ is called the mixed metric dimension and is denoted by $dim_m(G)$. In this dissertation, we consider the structure of mixed metric generators and characterize graphs for which the mixed metric dimension equals the trivial lower and upper bounds. We also give results on the mixed metric dimension of certain families of graphs and present an upper bound with respect to the girth of a graph. Finally, we prove that the problem of determining the mixed metric dimension of a graph is NP-hard in the general case.
Ključne besede: Hausdorff distance, distance between graphs, graph algorithms, trees, graph similarity, edge metric dimension, edge metric generator, mixed metric dimension, metric dimension
Objavljeno v DKUM: 03.08.2020; Ogledov: 1489; Prenosov: 115
.pdf Celotno besedilo (800,48 KB)

8.
Napovedovanje GPS sledi z globokimi nevronskimi mrežami
Jernej Borlinić, 2018, magistrsko delo

Opis: Metode strojnega učenja vse bolj prodirajo v vsa področja modernega gospodarskega in raziskovalnega okolja. Obstoječi algoritmi dosegajo vrhunske rezultate pri nalogah kot so prepoznavanje slik, razumevanje besedil in govora ipd. Avtomatizirane rešitve takšnih nalog so še nedavno veljale za nedosegljive. V tej magistrski nalogi pregledamo najpopularnejše globoke nevronske mreže, iz njih sestavljene modele in njihove načine učenja. S pridobljenim znanjem in večkratnim testiranjem v drugem delu, razvijemo model globoke nevronske mreže za napovedovanje GPS sledi. Osnovno testiranje modela poteka na lastnem naboru sintetično ustvarjenih podatkov. Dva najuspešnejša modela v nadaljevanju učimo s pomočjo izbranih realnih podatkov pridobljenih od podjetja GoOpti d. o. o. Končni izpopolnjen model pa učimo z razširjenim naborom realnih podatkov. V magistrski nalogi so opisani izbira in implementacija modela, način učenja, ustvarjanje in pridobivanje naborov podatkov in pridobljeni rezultati.
Ključne besede: Strojno učenje, globoko učenje, globoke nevronske mreže, povratne nevronske mreže.
Objavljeno v DKUM: 13.12.2018; Ogledov: 2529; Prenosov: 148
.pdf Celotno besedilo (9,58 MB)

9.
A new characterization and a recognition algorithm of Lucas cubes
Andrej Taranenko, 2013, izvirni znanstveni članek

Opis: Fibonacci and Lucas cubes are induced subgraphs of hypercubes obtained by excluding certain binary strings from the vertex set. They appear as models for interconnection networks, as well as in chemistry. We derive a characterization of Lucas cubes that is based on a peripheral expansion of a unique convex subgraph of an appropriate Fibonacci cube.This serves as the foundation for a recognition algorithm of Lucas cubes that runs in linear time.
Ključne besede: graph theory, Lucas cubes, characterization, recognition algorithm
Objavljeno v DKUM: 10.07.2017; Ogledov: 1294; Prenosov: 140
.pdf Celotno besedilo (563,10 KB)
Gradivo ima več datotek! Več...

10.
1-factors and characterization of reducible faces of plane elementary bipartite graphs
Andrej Taranenko, Aleksander Vesel, 2012, izvirni znanstveni članek

Opis: As a general case of molecular graphs of benzenoid hydrocarbons, we study plane bipartite graphs with Kekulé structures (1-factors). A bipartite graph ▫$G$▫ is called elementary if ▫$G$▫ is connected and every edge belongs to a 1-factor of ▫$G$▫. Some properties of the minimal and the maximal 1-factor of a plane elementary graph are given. A peripheral face ▫$f$▫ of a plane elementary graph is reducible, if the removal of the internal vertices and edges of the path that is the intersection of ▫$f$▫ and the outer cycle of ▫$G$▫ results in an elementary graph. We characterize the reducible faces of a plane elementary bipartite graph. This result generalizes the characterization of reducible faces of an elementary benzenoid graph.
Ključne besede: mathematics, graph theory, plane elementary bipartite graph, reducible face, benzenoid graph
Objavljeno v DKUM: 31.03.2017; Ogledov: 1067; Prenosov: 389
.pdf Celotno besedilo (139,73 KB)
Gradivo ima več datotek! Več...

Iskanje izvedeno v 1.85 sek.
Na vrh
Logotipi partnerjev Univerza v Mariboru Univerza v Ljubljani Univerza na Primorskem Univerza v Novi Gorici