Browsing Doctoral Dissertations by Title

Stojadinović, Mirko (Beograd , 2016)[more][less]
Abstract: Many realworld problems can be modeled as constraint satisfaction problems (CSPs) and then solved by one of many available techniques for solving these problems. One of the techniques is reduction to SAT, i.e. Boolean Satisfiability Problem. Variables and constraints of CSP are translated (encoded) to SAT instance, that is then solved by stateoftheart SAT solvers and solution, if exists, is translated to the solution of the original CSP. The main aim of this thesis is to improve CSP solving techniques that are using reduction to SAT. Two new hybrid encodings of CSPs to SAT are presented and they combine good sides of the existing encodings. We give the proof of correctness of one encoding that did not exist in literature. We developed system meSAT that enables reduction of CSPs to SAT by using 4 basic and 2 hybrid encodings. The system also enables solving of CSPs by reduction to two problems related to SAT, SMT and PB. We developed a portfolio for automated selection of encoding/solver to be used on some new instance that needs to be solved. The developed portfolio is comparable with the stateoftheart portfolios. We developed a hybrid approach based on short solving timeouts with the aim of significantly reducing the preparation time of a portfolio. By using this approach, we got results comparable to the ones obtained by using preparation time of usual length. We made comparison between several machine learning techniques with the aim to find out which one is the best suited for the short training approach. The problem of assigning air traffic controllers to shifts is described and three models of this problem are presented. We used a large number of different solving methods and a diverse set of solvers for solving this problem. We developed optimization techniques that aim to find optimal solutions of the problem. A hybrid technique combining reduction to SAT and local search is shown to be the most efficient one. We also considered sudoku puzzles and the existing techniques of solving the puzzles of greater size than 9 9. Amongst the used techniques, the existing reduction to SAT is the most efficient in solving these puzzles. We improved the existing algorithm for generating large sudoku puzzles. It is shown that simple preprocessing rules additionally improve speed of generating large sudokus. URI: http://hdl.handle.net/123456789/4427 Files in this item: 1
MirkoStojadinovicTeza.pdf ( 2.030Mb ) 
Todorčević, Stevo (Belgrade)[more][less]
Abstract: The thesis consists of four chapters and one appendix. The relation between trees and ordering types, especially the relation between treesubtree and the typesubtype are considered in Chapter 1. By using Jensens’s principle, Aronszajn’s tree which does not contain any Aronszajn’s subtree and Cantor’s subtree are constructed. Moreover, it is shown that in the model ZFC+GCH each ω_2 Aronszajn’s tree contains Aronszajn’s and Cantor’s subtree. In the first part of Chapter 2 the problem of the existence of Boolean algebras which have nontrivial automorphisms and endomorptisms are studied. It is shown that for each cardinal k, k>ω, there are exactly 2^k types of isomorphic Boolean algebras without nontrivial automorphisms. In the second part of that chapter the problem of isomorphism and automorhism of ω_1trees is studied. It is shown that there are 2^ω1 types of isomorphic total rigid Aronszajn’s trees, so one Aronszajn’s tree does not have any nontrivial automorphism. Several problems of the partition relations of cardinal numbers are solved in Chapter 3. The appendix contains the proof of the property that in ZFC the σdense partial ordered set of power ω_1 does not exist. It is shown that in ZFC there is not any linearly ordered topological space with weight less or equal ω_1 which satisfies Kurepa’s generalization of the notion of separable topological space. It is also shown that if ¬ω Kurepa’s hypothesis + Martin’s axiom + ¬Continuum hypothesis is assumed, then each perfect normal non  Arhimedian space whose weight is ω1 is measurable. URI: http://hdl.handle.net/123456789/316 Files in this item: 1
phdStevoTodorcevic.pdf ( 18.19Mb ) 
Dragović, Vladimir (Beograd , 1992)[more][less]

Tsirvoulis, Georgios (Beograd , 2019)[more][less]
Abstract: Asteroid families are populations of asteroids in the Main Belt that share a common origin, that is they are the fragments of energetic collisions between two asteroids. Their study over the years has produced a number of important results concerning the collisional and dynamical evolution of the Main Belt, the physical properties of the primordial bodies of the Solar System and the physics of energetic collisions, to name a few. The contribution of the present thesis can be summarized into two main topics: The first is the discovery of a new mechanism that leads to significant perturbations on the orbits of asteroids, and consequently on the evolution of asteroid families affected by it, and the second is the discovery of a couple of new families, each with its own peculiarities. The first part of this thesis was initially motivated by the irregular shape of the (1726) Hoffmeister asteroid family. In an effort to explain this peculiarity we carried out a thorough dynamical analysis of its past evolution and found out that none of the mechanisms known to affect the orbits of asteroids could explain it. Investigating further we discovered that the linear nodal secular resonance with the most massive asteroid (1) Ceres, is the mechanism responsible for the anisotropic inclination distribution of Hoffmeister family members. Having established the importance of the nodal secular resonance with Ceres, we sought to expand on the subject with the study of all linear secular resonances, nodal and periapsidal, involving not only (1) Ceres, but (4) Vesta, the second most massive asteroid, as well. To do so we utilized numerical integrations of test particles across the whole Main Belt, and evaluated the impact of these resonances on their orbits. Furthermore we identified all asteroid families crossed by one or more of these resonances. Two of these cases, the families of (1251) Seinajoki and (1128) Astrid were then studied in more detail, confirming the importance of the previously ignored secular resonances with massive asteroids. The second part details the discovery of two new asteroid families. The first one, that of (326) Tamara family, was motivated by the unexpectedly high number of dark asteroids in the Phocaea region, a part of the inner Main Belt which is expected to consist mostly of bright ones. Using all available physical data we were able to show that most of the dark asteroids therein belong to a single dynamical family, which we then further analyzed finding that it is 264 ± 43 Myrs old and that it could have a significant contribution to the influx of small dark asteroids toward the Near Earth region. The second discovered family, that of (633) Zelima, is a small cluster, subfamily of the large (221) Eos family. After identifying its members, we derived the age of the Zelima family, which turned out to be only about 3.66 Myrs. URI: http://hdl.handle.net/123456789/4752 Files in this item: 1
Tsirvoulis_Georgios.pdf ( 76.51Mb ) 
Borisavljević, Mirjana (Beograd , 1997)[more][less]

Bakić, Radoš (Belgrade)[more][less]

Mijajlović, Ivana (London)[more][less]

Pavlović, Aleksandar (Novi Sad)[more][less]
URI: http://hdl.handle.net/123456789/295 Files in this item: 1
PhdAleksandarPavlovic.pdf ( 7.226Mb ) 
Urošević, Dejan (Belgrade)[more][less]

Ćatović, Zlatko (Belgrade)[more][less]

Pogany, Tibor (Belgrade)[more][less]

Todorović, Petar (Belgrade , 1961)[more][less]

Ikodinović, Nebojša (Kragujevac)[more][less]
Abstract: The thesis is devoted to logics which are applicable in different areas of mathematics (such as topology and probability) and computer sciences (reasoning with uncertainty). Namely, some extensions of the classical logic, which are either modeltheoretical or nonclassical, are studied. The thesis consists of three chapters: an introductory chapter and two main parts (Chapter 2 and Chapter 3). In the introductory chapter of the thesis the wellknown notions and properties from extensions of the first order logic and nonclassical logics are presented. Chapter 2 of the thesis is related to logics for topological structures, particularly, topological class spaces (topologies on proper classes). One infinite logic with new quantifiers added is considered as the corresponding logic. Methods of constructing models, which can be useful for many others similar logics, are used to prove the completeness theorem. A number of probabilistic logic suitable for reasoning with uncertainty are investigated in Chapter 3. Especially, some ways of incorporation into the realm of logic conditional probability understood in different ways (in the sense of Kolmogorov or De Finnety) are given. For all these logics the corresponding axiomatizations are given and the completeness for each of them is proved. The decidability for all these logics is discussed too. URI: http://hdl.handle.net/123456789/194 Files in this item: 1
phdNebojsaIkodinovic.pdf ( 3.008Mb ) 
Ognjanović, Zoran (Kragujevac)[more][less]
Abstract: The thesis consists of seven chapters and two appendixes. The Chapter 1 and the appendixes contain known notions and properties from probability logics. In Chapter 2 some propositional probability logics are introduced and their languages, models, satisfiability relations, and (in)finitary axiomatic systems are given. Object languages are countable, formulas are finite, while only proofs are allowed to be infinite. The considered languages are obtained by adding unary probabilistic operators of the form P≥s. Decidability of the logics is proved. In Chapter 3 some first order probability logics are considered while in Chapter 4 new types of probability operators are introduced. The new operators are suitable for describing events in discrete sample spaces. It is shown that they are not definable in languages of probability logics that have been used so far. A propositional and a firstorder logic for reasoning about discrete linear time and finitely additive probability are given in Chapter 5. Sound and complete infinitary axiomatizations for the logics are provided as well. In Chapter 6 a probabilistic extension of modal logic is studied and it is shown that those logics are closely related, but that modal necessity is a stronger notion than probability necessity. In Chapter 7 decidability of these logics is shown by reducing the corresponding satisfiability problem to the linear programming problem. Finally, two automated theorems provers based on that idea are described. URI: http://hdl.handle.net/123456789/197 Files in this item: 1
phdZoranOgnjanovic.pdf ( 1.259Mb ) 
Knežević, Zoran (Belgrade)[more][less]

Shkheam, Abejela (, 2013)[more][less]
Abstract: This thesis has been written under the supervision of my mentor, Prof. dr. Milo s Arsenovi c at the University of Belgrade academic, and my comentor dr. Vladimir Bo zin in year 2013. The thesis consists of three chapters. In the rst chapter we start from de nition of harmonic functions (by mean value property) and give some of their properties. This leads to a brief discussion of homogeneous harmonic polynomials, and we also introduce subharmonic functions and subharmonic behaviour, which we need later. In the second chapter we present a simple derivation of the explicit formula for the harmonic Bergman reproducing kernel on the ball in euclidean space and give a proof that the harmonic Bergman projection is Lp bounded, for 1 < p < 1, we furthermore discuss duality results. We then extend some of our previous discussion to the weighted Bergman spaces. In the last chapter, we investigate the Bergman space for harmonic functions bp, 0 < p < 1 on RnnZn. In the planar case we prove that bp 6= f0g for all 0 < p < 1. Finally we prove the main result of this thesis bq bp for n=(k + 1) q < p < n=k, (k = 1; 2; :::). This chapter is based mainly on the published paper [44]. M. Arsenovi c, D. Ke cki c,[5] gave analogous results for analytic functions in the planar case. In the plane the logarithmic function log jxj, plays a central role because it makes a di erence between analytic and harmonic case, but in the space the function jxj2n; n > 2 hints at the contrast between harmonic function in the plane and in higher dimensions. URI: http://hdl.handle.net/123456789/3053 Files in this item: 1
phd_Shkheam_Abejela.pdf ( 650.6Kb ) 
Tepavčević, Andreja (Novi Sad)[more][less]

Bulatović, Jelena (Belgrade)[more][less]

Borovićanin, Bojana (Kragujevac, Serbia , 2008)[more][less]
Abstract: Different spectral characterizations of certain classes of graphs are considered in this dissertation. The large number of papers concerning this topic, indicates that problems of this kind are very interesting in spectral graph theory. This dissertation, beside Preface and References with 46 items, consists of two chapters: 1. Harmonic graphs, 2. Graphs with maximal index. Harmonic graphs are introduced and studied in details in Chapter 1. This chapter consists of four sections. In section 1.1 the definition of harmonic graphs, as well as their basic properties, are given. Harmonic trees are discussed in section 1.2. In section 1.3 we characterize harmonic graphs with small number of cycles; in particular, all unicyclic, bicyclic, tricyclic and tetracyclic graphs are determined. Finally, in section 1.4, we determine all connected 3harmonic graphs with integral spectrum. The solution of maximal index problem in certain classes of graphs is given in Chapter 2. This chapter consists of four sections. In sections 2.1 and 2.2 we review some results related to the index of a graph. The emphasis is on graphs with given number of both vertices and edges; in particular we discuss graphs having the fixed number of pendant edges, too. In section 2.3 we give the solution of maximal index problem in the class of connected tricyclic graphs with n vertices and k pendant edges. Finally, in section 2.4, we determine graphs with maximal index among all connected cactuses with n vertices. URI: http://hdl.handle.net/123456789/1834 Files in this item: 1
disertacija_Bojana Borovicanin.pdf ( 1.939Mb ) 
Jovanović, Irena (Beograd , 2014)[more][less]
Abstract: Spectral graph theory is a mathematical theory where graphs are considered by means of the eigenvalues and the corresponding eigenvectors of the matrices that are assigned to them. The spectral recognition problems are of particular interest. Between them we can distinguish: characterizations of graphs with a given spectrum, exact or approximate constructions of graphs with a given spectrum, similarity of graphs and perturbations of graphs. In this dissertation we are primarily interested for the similarity of graphs, where graphs with the same number of vertices and graphs of different orders are considered. Similarity of graphs of equal orders can be established by computation of the spectral distances between them, while for graphs with different number of vertices the measures of similarity are introduced. In that case, graphs under study are usually very large and they are denoted as networks, while the measures of similarity can be spectraly based. Some mathematical results on the Manhattan spectral distance of graphs based on the adjacency matrix, Laplacian and signless Laplacian matrix are given in this dissertation. A new measure of similarity for the vertices of the networks under study is proposed. It is based on the difference of the generating functions for the numbers of closed walks in the vertices of networks. These closed walks are calculated according to the new spectral formula which enumerates the numbers of spanning closed walks in the graphlets of the corresponding graphs. The problem of the characterization of a digraph with respect to the spectrum of AAT , apropos ATA, where A is the adjacency matrix of a digraph, is introduced. The notion of cospectrality is generalized, and so the cospectrality between some particular digraphs with respect to the matrix AAT and multigraphs with respect to the signless Laplacian matrix is considered. URI: http://hdl.handle.net/123456789/4233 Files in this item: 1
Jovanović_Irena.pdf ( 1.138Mb )