1,720,994 research outputs found
Android application for representation of FNM\u27s study programmes
Get PDFV diplomskem delu se bomo seznanili z izdelavo Android aplikacije za predstavitev študijskih programov FNM.
V prvem delu bomo predstavili operacijski sistem Android, si pogledali njegovo zgodovino, arhitekturo in napovedi uporabe za prihodnost. Sledi predstavitev jezika XML, saj naša aplikacije pridobiva podatke iz XML dokumentov, ki so shranjeni na spletnem strežniku. Pogledali si bomo tudi tehnologije in programska orodja, ki smo jih uporabili pri razvoju aplikacije. Sledi predstavitev načrta in implementacija aplikacije, kjer bomo predstavili nekaj najpomembnejših razredov in metod, ki smo jih uporabili. Celotna implementacija aplikacije je objavljena kot priloga na zgoščenki.In this graduation thesis we will present the development of our own Android application for representation of FNM\u27s study programmes.
In the first part we will introduce the Android operating system, its history, architecture and predictions of use in the future. In the next part we will introduce XML language, because our application is receiving data from XML documents, which are stored on a web server. All technologies and software tools that we used for developing the application will be presented. In the last part we will introduce a design plan for the application and its practical implementation, where we will present some of the most important classes and methods that are used. The implementation is fully published as an annex on the CD
Na razdaljah osnovane invariante in mere v grafih
Get PDFThis 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 be a connected graph, let be a vertex, and let be an edge. The distance between the vertex and the edge is given by . A vertex distinguishes two edges if . A set of vertices in a connected graph is an edge metric generator of if every two distinct edges of are distinguished by some vertex of . The smallest cardinality of an edge metric generator of is called the edge metric dimension and is denoted by . 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 distinguishes two elements of a graph if . A set of vertices in a connected graph is a mixed metric generator of if every two elements of , where , are distinguished by some vertex of . The smallest cardinality of a mixed metric generator of is called the mixed metric dimension and is denoted by . 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.V doktorski disertaciji se posvetimo nekaterim temam, ki so povezane z razdaljami v grafih. Osredotočimo se na tri glavne teme, in sicer na pred kratkim vpeljano Hausdorffovo razdaljo med grafi in na dve novi grafovski invarianti - povezavno metrično dimenzijo grafa in mešano metrično dimenzijo grafa. Vse tri obravnavane teme spadajo v metrično teorijo grafov, saj so tesno povezane s konceptom razdalje med dvema vozliščema grafa.
Hausdorffova razdalja med grafi je relativno nova mera podobnosti grafov. Določitev Hausdorffove razdalje med dvema grafoma temelji na posebnem skupnem podgrafu primerjanih grafov, ki ga določimo na podlagi strukturnih lastnosti zunaj samega skupnega podgrafa. V disertaciji obravnavamo Hausdorffovo razdaljo med nekaterimi družinami grafov, ki se pogosto pojavljajo v kemijski teoriji grafov. Poleg rezultatov za splošne grafe izračunamo formule za Hausdorffovo razdaljo med potmi in cikli. Do sedaj ni bil poznan noben učinkovit algoritem za reševanje problema določitve Hausdorffove razdalje med dvema drevesoma, v tej disertaciji pa predstavimo algoritem, ki reši omenjen problem v polinomskem času. Algoritem je rekurziven in uporablja strategijo reševanja problemov "deli in vladaj". Algoritem za reševanje enega od podproblemov uporablja tudi metodo, ki temelji na dobro poznanem algoritmu za iskanje največjega prirejanja v dvodelnem grafu.
Povezavna metrična dimenzija je grafovska invarianta, ki se nanaša na razlikovanje povezav grafa. Naj bo povezan graf, naj bo vozlišče grafa in naj bo povezava grafa. Razdalja med vozliščem in povezavo je določena z . Vozlišče razlikuje povezavi , če . Množica vozlišč v povezanem grafu je povezavni metrični generator za , če za vsaki dve različni povezavi grafa velja, da ju razlikuje neko vozlišče iz množice . Moči najmanjšega povezavnega metričnega generatorja grafa rečemo povezavna metrična dimenzija in jo označimo z .
Povezavna metrična dimenzija je nov koncept. V disertaciji proučujemo njene matematične lastnosti. Skozi predstavitev rezultatov o obstoju grafov z vnaprej določeno povezavno metrično dimenzijo in standardno metrično dimenzijo naredimo primerjavo med obema. Dokažemo, da je izračun povezavne metrične dimenzije povezanih grafov NP-težek problem in podamo nekaj rezultatov o približnih rešitvah. Poleg tega predstavimo še meje in natančne formule za povezavno metrično dimenzijo številnih družin grafov.
Mešana metrična dimenzija grafa je grafovska invarianta, ki je podobna povezavni metrični dimenziji. Nanaša se na razlikovanje elementov grafa (vozlišč in povezav). Vozlišče razlikuje dva elementa grafa , če . Množica vozlišč v povezanem grafu je mešani metrični generator za , če za vsaka dva elementa grafa , kjer , velja, da ju razlikuje neko vozlišče iz množice . Moči najmanjšega mešanega metričnega generatorja grafa rečemo mešana metrična dimenzija in jo označimo z . V disertaciji obravnavamo strukturo mešanih metričnih generatorjev in podamo karakterizacijo grafov, za katere je mešana metrična dimenzija enaka naravnim spodnjim in zgornjim mejam. Podamo tudi rezultate za mešano metrično dimenzijo nekaterih družin grafov in predstavimo zgornjo mejo glede na ožino grafa. Na koncu dokažemo, da je izračun mešane metrične dimenzije povezanih grafov v splošnem NP-težek problem
Construction and analysis of huge graphs from keywords
No full textV magistrskem delu se lotevamo problema konstrukcije grafa ključnih besed iz velikega korpusa besedil. V grafu ključne besede predstavljajo vozlišča, ki so povezana s temami. Dve ključni besedi sta v grafu povezani z neko temo, v kolikor sta v nekem besedilu medsebojno odvisni in to besedilo pripada izbrani temi.
V prvem delu so ob konstrukciji takšnega grafa predstavljene še metode za izluščitev ključnih besed in določitev tem besedila.
Predstavljeno znanje nato uporabimo na konkretnem primeru. Nad celotno angleško Wikipedijo skonstruiramo graf in ga tudi analiziramo. Predstavimo splošne lastnosti grafa in argumentiramo dobljene rezultate pri analizi grafa.
V zadnjem delu navedemo še nekaj primerov uporabe definirane strukture in predstavimo podatkovne baze, ki so za shranjevanje grafa primerne.
Končna ugotovitev kaže na to, da graf ključnih besed ni uporaben le za iskanje po besedilih, ampak tudi za vse sorodne probleme, kot so: klasifikacija novega besedila in predlaganje podobnih besedil.This master\u27s thesis deals with the problem of constructing a graph of keywords from a large text corpus. In graph, keywords represent vertices, while topics are being saved on edges. In a graph, two keywords are connected with a topic, if they are co-dependent in a text and if this text falls under this topic.
In the first part, methods of extracting keywords and determining the topic of a text are presented alongside the construction of such a graph.
The presented knowledge is then used on an actual case. A graph was constructed and analysed for the whole English Wikipedia. General characteristics of the graph are presented and the results of the graph analysis are explained. In the last part, some examples of the use of the defined structure are listed and databases suitable for the storage of the graph are presented.
The main finding suggests that a graph of keywords is useful not only during text search but also for all similar problems, such as: classification of new and suggestion of similar texts
Forecasting probability of default with neural networks
Get PDFUmetna 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.Artificial intelligence refers to the theory and development of computer systems that can perform tasks, which typically require human intelligence. Deep learning is a subset of machine learning where artificial neural networks, algorithms inspired by the human brain, learn from large amounts of data. Similarly to how people learn from experience, the deep learning algorithm would repeat the same task several times and each time adjust it slightly in order to improve the result. In this master’s thesis, we present neural networks, types of neural networks and their usage. We also thoroughly describe the use of neural networks for the purpose of forecasting the probability of default. A deep neural network algorithm is used on anonymized company data. The whole process includes data preparation and teaching the algorithm on the input data. The final analysis shows that neural networks are suitable for our problem, because the algorithm provides high accuracy
Nonograms
Get PDFNonogram 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.A nonogram is a puzzle, with which we can draw a picture, while solving it. The thesis provides algorithmic solutions to black-and-white nonograms. With these algorithms we can check the correctness of the nonogram\u27s solutions, and we can also use them as an aid for human solving.
First, an algorithm is presented that can solve only some nonograms, and later on this algorithm is improved so it finds all possible solutions. The question of how good the first algorithm is when increasing the dimensions of random nonograms is also answered. A quick way to paint the corners of some nonograms is also presented.
Lastly, the influence of some components on the time it takes to solve a nonogram puzzle is presented
Span of a graph
Get PDFV 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.In the thesis, we define the basics terminology of graph theory and spans of a graph and present theorems related to them. We connect spans of a graph with determining the maximum safety distance two players can keep at all times while traversing all vertices or all edges of a graph. We also introduce three movement rules, which players must consider while traversing a graph, and provide a relation between those rules and graph products.
In the thesis, we also characterize the graphs in which it is impossible to keep a positive safety distance between the two players at all times, according to the movement rule.
At the end, we introduce a polynomial time algorithm to compute the chosen span for a given graph
A comparison of approximate string matching algorithms
Get PDFV magistrskem delu predstavimo tri algoritme za reševanje problema 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.In this thesis, we present three approximate string matching algorithms for the differences problem, namely dynamic programming solution, including Ukkonen\u27s improvement of expected time complexity (Ukkonen\u27s cut-off method), Galil-Park algorithm and Tarhio-Ukkonen algorithm. We implement the algorithms in Python programming language and measure their execution times for various test cases, on texts both in English and Slovene. Finally, we present the test results and compare the algorithms based on them
Predicting GPS tracks with deep neural networks
Get PDFMetode 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.Machine learning methods are increasingly influencing all areas of the modern economic and research environment. Existing algorithms achieve top results in tasks such as image recognition, understanding text and speech, etc. Automated solutions to such tasks were until recently considered unavailable. In this master\u27s thesis, we review the most popular deep neural networks, underlying models and their learning tipes.
With the acquired knowledge and repeated testing in the second part, we develop a deep neural network model for predicting GPS tracks. Basic testing of the model takes place on our own synthetically generated dataset. The two most successful models are further taught using selected real data obtained from GoOpti d. o. o. and the final, best performing, model is taught with an expanded set of real data. The master\u27s thesis describes the choice and implementation of the model, the tipe of learning, the creation and retrieval of data sets, and the obtained results
Hardware and software implementation of a robot
Get PDFV sodobnem svetu nas obdaja vedno več tehnologije. V tem svetu je ena izmed najbolj uporabnih sposobnosti programiranje, saj si lahko na takšen način zelo olajšamo življenje. Zlahka ustvarimo nove stvari ali nadgradimo že obstoječe. V tej diplomski nalogi je opisano, kako si lahko vsak na zanimiv in cenovno dosegljiv način zgradi svojega robota in se ob tem nauči veliko o programiranju, ustvarjanju lastnih vezij in povezavi teh vezij med sabo. Ob obilni izbiri strežnikov, programskih jezikov in ostalih pripomočkov na spletu, je možno opaziti, da so le malokateri zadostno dokumentirani, kar zelo oteži gradnjo robota. V diplomski nalogi je opisan celoten potek izdelave in tudi rešitve problemov, ki so nastali pri izdelavi robota, s slikami elementov ter programskimi kodami, ki robota poganjajo.In the modern world, there is a lot of technology. In such a world programming is one of the more useful skills to know, since it can make our life much less complicated, and we can easily invent new things and upgrade the old ones. This Graduation Thesis describes how anyone can build their own robot, in an interesting and cost affordable way. While at it, one can also learn a lot about programming, creating his own electrical circuits, and about the way those circuits are connected. While there is a vast choice of program servers, program languages and other add-ins on the Internet, only a few of them are sufficiently documented, which makes robot building much more difficult. This thesis, therefore, describes the whole process of robot building, and the solutions of problems that emerged during it. That is accompanied by the photos of components and programming codes of the robot
Visualisation of backtracking
Get PDFCilj diplomskega dela je izdelava spletnega dokumenta, ki omogoča spremljanje delovanja sestopanja po korakih. V teoretičnem delu diplomske naloge najprej opišemo tehnologijo, ki je bila uporabljena za izdelavo spletnega dokumenta. Predstavimo tudi druga orodja, ki bi bila primerna za vizualizacijo. Prav tako opišemo uporabniški vmesnik na primeru reševanja sudokuja in iskanja izhoda iz labirinta. Reševanje sudokuja poteka rekurzivno, reševanje labirinta pa nerekurzivno. V zaključku povzamemo ugotovitve in morebitne nadaljnje izboljšave vizualizacije.The goal of this graduation thesis is to create a web document that provides a step by step demonstration of backtracking. The theoretical part of the graduation thesis begins with a description of the technology used to create the web document. Other tools that are suitable for visualization are also outlined. The user interface is described on the examples of solving a sudoku puzzle and finding a path through a maze. Sudoku solving is implemented recursively, while maze solving is done non-recursively. In conclusion we summarize our findings and list the possible future enhancements of the visualization
- …
