Doctoral Dissertations
Recent Submissions

Lalović, Ana (Beograd , 2016)[more][less]
Abstract: The goal of this thesis is to reduce multidimensional space of galactic properties to the smallest number of dimensions su cient to describe them. For this purpose, the statistical analysis is applied over the parameters that describe fundamental galactic properties on the morphologically representative sample of 2180 galaxies. The sample of galaxies used in this thesis is based on the Arecibo Legacy Fast ALFA (Alfalfa) blind HI survey. The importance of an HI blind survey lies in the fact that galaxies are chosen on the basis of their gas content (HI) solely, thus free of optical selection e ects. From the initial sample counting 10000 galaxies, 2180 of them were chosen, since for this subsample the optical spectroscopy from the Sloan Digital Sky Survey (SDSS) was available and moreover the photometry in the UV (Galaxy Evolution Explorer, GALEX), and optical (SDSS) to the nearinfrared (Two Micron All Sky Survey, 2MASS). Parameters are selected according to the previously established correlations between fundamental galactic properties, relying on the previous work. They are extensively tested and confronted between each other to be chosen from the larger parametric space. To select parameters, we rst measured stellar kinematics using publicly available code (pPXF), and tested both empirical and synthetic stellar libraries. In particular, we have measured the velocity dispersion and the higher moments of the lineofsight velocity distribution function. This is the largest galaxy sample created so far with detailed stellar kinematics measured including higher moments of the lineofsight velocity distribution function. The sample size allows statistical tests to be applied to the higher moment of the velocity distribution function (h4), with respect to the di erent groups of morphological galaxy types. Various tests agree with the previous indication that elliptical and lenticular galaxies have the same origin. Further, we have measured the line strength indices for several absorption lines (Lick indices), since some of them are good proxies to galaxy ages and metallicity, also the fundamental galactic properties. In the nal statistical analysis, metallicity proves to be of no importance, but the inclusion of galaxy ages in the analysis, the results change signi cantly. The last step in the parameter selection is the modelling of the galaxies' surface brightness pro les with the Sersic pro le, that is performed in this thesis with the Gal t code. The velocity dispersion measured, along with the Sersic index and effective radius of the Sersic pro le takes the role in the dynamical mass calculation, being the fundamental galactic property and hence used in the nal statistical analysis. Finally, we have taken the mass of the gas component and maximal rotational velocity from the radiospectroscopy and Kron magnitudes (i.e. colours) from the ultraviolet/ optical/nearinfrared photometry (GALEX/SDSS/2MASS databases). After extensive testing, we have chosen the colour calculated from ultraviolet and optical magnitudes (NUV r colour), for the nal statistical analysis. It is worth noting that previous analysis of the galactic properties lack velocity dispersion, as well as the colour with the ultraviolet component, although it is a direct proxy to the speci c star formation rate in the galaxy. This particular colour makes correlations among analysed parameters stronger and proves to be more important than optical colours. Finally, when the proper parametric space of galactic properties is formed (velocity dispersion, colour, luminosity, Petrosian radii R50 and R90, dynamical, HI and stellar masses, maximal rotational velocity and the galaxy ages), the correlation analysis is performed to inspect correlations between parameters. This analysis con rms relations that are already known to hold. Then the principal component analysis is done with the purpose of nding and identifying the smallest number of galactic properties responsible for the nal products of galaxy evolution, as we see today, in the local Universe. The results of the corresponding analysis are the following: there are at least three statistically important, independent components. The rst and the most important component cannot be identi ed with either galactic property, but presents the mixture of several properties: dynamical mass, mass of the stellar and gas component, luminosity and Petrosian radii R50 and R90. Relaying on the previous work, this component may be identi ed with the "size" of the galaxies. The second component, mostly in uenced by the galactic colour, may be identi ed with the "aspect" of the galaxies. The colour was not found to be important in previous work. The galaxy ages can be identi ed with the third principal component. There is a hint on the fourth component, dominated by the maximal rotational velocity that can be identi ed with the speci c angular momentum of galaxies. Although not proven to be statistically important, it may become so in the larger sample of galaxies which will provide the information of the true peak of the galaxies' rotational curves, since the singlebeam HI spectra may show the single maximum and this may not be the true maximum. Also, the rotational velocity includes the inclination correction, another questionable parameter in the analysis. To conclude: there are at least three, and possibly four dimensions of the multidimensional galactic space, as we see today. URI: http://hdl.handle.net/123456789/4446 Files in this item: 1
Lalovic_Ana3.pdf ( 11.44Mb ) 
Mihajlović, Bojana (Beograd , 2016)[more][less]
Abstract: The subject of this dissertation belongs to scientific field of spectral graph theory, a young branch of mathematical combinatorics, i.e. graph theory, which finds important applications in many areas, such as chemistry, physics, computer science, telecommunications, sociology, etc., and various fields of mathematics. Spectral graph theory connects basic properties and the structure of a graph with characteristics of the spectra of its matrices (adjacency matrix, Laplacian matrix, etc.). In this dissertation we only work with the adjacency matrix. The second largest eigenvalue of the adjacency matrix of a graph (or, simply, second largest eigenvalue of a graph), as well as its distance from the largest eigenvalue, are very important especially in applications of spectral graph theory in computer science. The property of a graph that one of its eigenvalues does not exceed some given value is a hereditary one; therefore, many of the investigations of this kind have been directed at finding the maximal allowed graphs, or minimal forbidden graphs for that property. In this dissertation we determine some classes of graphs whose second largest eigenvalue does not exceed some given value, and, for that purpose, we develop some very useful tools. In methodological sense, investigations in this dissertation represent a combined approach consisting of application of the algebraic apparatus and methods of spectral graph theory and combinatorial reasoning, whilst at some stages the expert system newGRAPH has been used. The dissertation consists of eight chapters, each of which is divided into subchapters. In the beginning, some important previous work is shown, and afterwards we present some original elements of the algebraic and combinatorial apparatus that speed up and simplify the further work. We define some mappings between certain families of graphs, some of which preserve the sign of the expression 2 2 , and, using them, we describe and systematize some (already known) results in a new way. Further on we completely determine all maximal reflexive tricyclic cacti which are not RSdecidable and whose cycles do not form a bundle, from the classes 1 R and 3 R , and we give some partial results about the class 2 R , using previously induced mappings (until now only the graphs from the remaining class 4 R have been completely determined [40], [46]). Next, we completely describe all minimal forbidden graphs in the class of bicyclic graphs with a bridge, and all minimal forbidden graphs in the class 3 R  the approach that so far has never been used with reflexive graphs. Then we determine the maximal number of the cycles for RSundecidable reflexive cacti whose cycles do form a bundle, and, therefore, generally for RSundecidable reflexive cacti and we describe three classes of maximal reflexive RSundecidable reflexive cacti that contain a bundle. Further on, some of the previous results are generalized: the generalized RStheorem is stated and proved (socalled GRStheorem) for any r , r 0 ; previously induced mappings are generalized, their properties are proved and various examples of classes of graphs with the property 2 r (for r 0 ) are given. Based on this, we describe all GRSundecidable maximal graphs for the property 2 2 in the class of unicyclic and multicyclic graphs, and also all RSundecidable maximal θgraphs for this property as well as all GRSundecidable maximal trees with the property 2 5 1 2 . Furthermore, we investigate the limit 3 (as in [28]) and we describe all trees with the diameter 3 and the diameter larger than 8, with the property 2 3 , as well as all GRSundecidable multicyclic cacti with the same property. Finally, we introduce and apply socalled σmodifications of Smith trees. We describe seven σmodifications and corresponding extensions, and we notice the appearance in (already known) results in the class of multicyclic reflexive cacti with 4 cycles. Applying some extensions to certain families of tricyclic cacti, we obtained the results in the class of multicyclic reflexive cacti with 4 cycles, using a different approach [48]. Finally, in the conclusion, we suggest some possible directions of further investigations. URI: http://hdl.handle.net/123456789/4445 Files in this item: 1
Mihailovic_Bojana.pdf ( 6.960Mb ) 
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 ) 
Mišković, Stefan (Beograd , 2016)[more][less]
Abstract: In this dissertation, three NPhard minmax discrete optimization problems are considered. The rst considered problem is multiperiod emergency service location problem, the second one is dynamic maximal covering location problem with multiple covering radii, and the third one is uncapacitated multiple allocation phub center problem. In many practical situations, input parameters (such as user demands, transportation time or cost) often vary with unknown distributions. Therefore, it is necessary to involve these uncertainties in the deterministic variants of the problems by applying robust optimization approach. Mathematical models for the deterministic and nondeterministic variants of all three problems are developed, except for the deterministic uncapacitated multiple allocation phub center problem, which has already been addressed in the literature. In addition, for the rst time in the literature, it was proven that the emergency service location problem is NPhard. The considered problems and their robust variants have numerous applications, due to the fact that in reallife situations input parameters are often subject to uncertainty. Multiperiod emergency service location problem may be used when determining optimal locations for police stations, re brigades, ambulances, and other emergency units in the given region. The dynamic maximal covering location problem with multiple covering radii is useful when choosing the optimal strategy for establishing resources (service centers, suppliers, facilities, etc.) with maximal satisfaction of customer demands in a certain region, by assuming that the service e ciency directly depends on the distance between customer and service center (i.e., the selected coverage radius). The uncapacitated multiple allocation phub center problem has signi cant applications in designing telecommunication and transportation networks, postal delivery systems, emergency systems, supply networks, etc. Since exact methods provide optimal solutions only for problem instances of small dimensions, hybrid metaheuristic algorithms are developed to solve both deterministic and robust variants of the considered problems. The proposed hybrid algorithms are obtained by combining particle swarm optimization, with local search heuristic { classical local search or variable neighborhood search method. For dynamic maximal covering location problem with multiple covering radii, a hybridization of metaheuristic algorithm with exact method based on linear programming is developed. All elements of the proposed algorithms are adopted to the problems under consideration. Di erent strategies are implemented for improving the e ciency of proposed algorithms, especially for the calculation of the objective function value and the local search part. The in uence of di erent parameters of hybrid algorithms on the solution quality is analyzed in detail. All parameters are adjusted by using analysis of variance. For all considered problems (both deterministic and robust variant), the performance of the proposed hybrid algorithms is evaluated on adequate test data sets. The proposed algorithms are compared with existing heuristic from the literature and exact methods incorporated in commercial CPLEX solver. The obtained experimental results indicate the e ciency of proposed algorithms in obtaining high quality solutions for all considered test instances. The presented comparative analysis indicates the advantages of the proposed hybrid algorithms over existing methods in the sense of solution quality and/or required computational time, especially in the case of large problem dimensions. The results presented in this paper represent a contribution to the eld of discrete optimization, robust optimization and metaheuristic methods. URI: http://hdl.handle.net/123456789/4423 Files in this item: 1
Miskovic_Stefan_teza.pdf ( 1.773Mb ) 
Mladenović, Miljana (Beograd , 2016)[more][less]
Abstract: The beginning of the new millennium was marked by huge development of social networks, internet technologies in the cloud and applications of artificial intelligence tools on the web. Extremely rapid growth in the number of articles on the Internet (blogs, ecommerce websites, forums, discussion groups, and systems for transmission of short messages, social networks and portals for publishing news) has increased the need for developing methods of rapid, comprehensive and accurate analysis of the text. Therefore, remarkable development of language technologies has enabled their applying in processes of document classification, document clustering, information retrieval, word sense disambiguation, text extraction, machine translation, computer speech recognition, natural language generation, sentiment analysis, etc. In computational linguistics, several different names for the area concerning processing of emotions in text are in use: sentiment classification, opinion mining, sentiment analysis, sentiment extraction. According to the nature and the methods used, sentiment analysis in text belongs to the field of computational linguistics that deals with the classification of text. In the process of analysing of emotions we generally speak of three kinds of text classification: • identification of subjectivity (opinion classification or subjectivity identification) used to divide texts into those that carry emotional content and those that only have factual content • sentiment classification (polarity identification) of texts that carry emotional content into those with positive and those with negative emotional content • determining the strength or intensity of emotional polarity (strength of orientation). In terms of the level at which the analysis of feelings is carried out, there are three methodologies: an analysis at the document level, at the sentence level and at the level of attributes. Standardized methods of text classification usually use machine learning methods or rulebased techniques. Sentiment analysis, as a specific type of classification of documents, also uses these methods. This doctoral thesis, whose main task is the analysis of emotions in text, presents research related to the sentiment classification of texts in Serbian language, using a probabilistic method of machine learning of multinomial logistic regression i.e. maximum entropy method. The aim of this research is to create the first comprehensive, flexible, modular system for sentiment analysis of Serbian language texts, with the help of digital resources such as: semantic networks, specialized lexicons and domain ontologies. This research is divided into two phases. The first phase is related to the development of methods and tools for detecting sentiment polarity of literal meaning of the text. In this part of the work, a new method of reducing the feature vector space for sentiment classification is proposed, implemented and evaluated. The proposed method for reduction is applied in the classification model of maximum entropy, and relies on the use of lexicalsemantic network WordNet and a specialized sentiment lexicon. The proposed method consists of two successive processes. The first process is related to the expansion of feature vector space by the inflectional forms of features. The study has shown that usage of stemming in sentiment analysis as a standard method of reducing feature vector space in text classification, can lead to incomplete or incorrect sentimentpolarity feature labelling, and with the introduction of inflectional feature forms, this problem can be avoided. The paper shows that a feature vector space, increased due to the introduction of inflectional forms, can be successfully reduced using the other proposed procedure – semantic mapping of all predictors with the same sentimentpolarity into a small number of semantic classes. In this way, the feature vector space is reduced compared to the initial one, and it also retains the semantic precision. The second phase of the dissertation describes the design and implementation of formal ontologies of Serbian language rhetorical figures – the domain ontology and the task ontology. Usage of the task ontology in generating features representing figurative speech is presented. The research aim of the second phase is to recognize figurative speech to be used in improving of the existing set of predictors generated in the first phase of the research. The research results in this phase show that some classes of figures of speech can be recognized automatically. In the course of working on this dissertation, a software tool SAFOS (Sentiment Analysis Framework for Serbian), as an integrated system for sentiment classification of text in Serbian language, has been developed, implemented and statistically evaluated. Results of the research within the scope of this thesis are shown in papers (Mladenović & Mitrović, 2013; Mladenović & Mitrović, 2014; Mladenović, Mitrović & Krstev, 2014; Mladenović, Mitrović, Krstev & Vitas, 2015; Mladenović, Mitrović & Krstev, 2016). The dissertation consists of seven chapters with the following structure. Chapter 1 introduces and defines methods, resources and concepts used in the first phase of research: text classification, sentiment classification, machine learning, supervised machine learning, probabilistic supervised machine learning, and language models. At the end of the introductory section, the tasks and objectives of the research have been defined. Chapter 2 presents a mathematical model of text classification methods and classification of sentiment methods. A mathematical model of a probabilistic classification and an application of the probabilistic classification in regression models are presented. At the end of the chapter it is shown that the method using the mathematical model of maximum entropy, as one of the regression models, has been successfully applied to natural language processing tasks. Chapter 3 presents the lexical resources of the Serbian language and the methods and tools of their processing. Chapter 4 deals with the comprehensive research on the currently available types and methods of sentiment classification. It shows the current work and research in sentiment classification of texts. It also presents a comparative overview of research in sentiment classification of texts using the method of maximum entropy. Chapter 5 discusses the contribution of this thesis to methods of feature space reduction for maximum entropy classification. First, a feature space reduction method is analysed. A new feature space reduction method which improves sentiment classification is proposed. А mathematical model containing proposed method is defined. Learning and testing sets and lexicalsemantic resources that are used in the proposed method are introduced. Chapter 5 also describes building and evaluation of a system for sentiment classification – SAFOS, which applies and evaluates the proposed method of a feature vector space reduction. The parameters and the functions of SAFOS are defined. Also, measures for evaluation of the system were discussed – precision, recall, F1measure and accuracy. A description of the method for assessing the statistical significance of a system is given. Also, implementation of the statistical test in the system SAFOS is discussed. The chapter provides an overview of the presented experiments, results and evaluation of the system. Chapter 6 deals with methods of recognizing figurative speech which can improve sentiment classification. The notion of domain ontology is introduced, the role of rhetorical figures and domain ontology of rhetorical figures. The importance of figurative speech in the sentiment classification has been explored. The description of the construction and structure of the first domain ontology of rhetorical figures in Serbian language, RetFig.owl, is given. Also, the description of the construction and structure of the corresponding task ontology that contains rules for identification of some classes of rhetorical figures is given. At the end of this chapter, an overview of the performed experiments, results and evaluation of the SAFOS system plugin that improved the recognition of figurative speech is given. The final chapter of this study deals with the achievemnts, problems and disadvantages of the SAFOS system. The conclusion of this thesis points to the great technological, social, educational and scientific importance of the sentiment analysis and recognition of the figurative speech and gives some routes in further development of the SAFOS system. URI: http://hdl.handle.net/123456789/4422 Files in this item: 1
Mladenovic_Miljana.pdf ( 13.60Mb )