Computer Science
Recent Submissions
-
Srdanović, Vladimir (University of Belgrade , 1987)[more][less]
Abstract: The dissertation relates to the elements of medical decision-making, modeled by a consultative expert system, characteristic to the domain of rheumatology and potentially other domains of medicine with a similar structure. URI: http://hdl.handle.net/123456789/5764 Files in this item: 1
Konsultativni ekspertni sistem.pdf ( 7.218Mb ) -
Mrkela, Lazar (Beograd , 2024)[more][less]
Abstract: This dissertation examines two discrete location problems and their bi- objective variants. The first problem under consideration is the maximal covering location problem with user preferences and budget constraints imposed on facility opening. This variant of the maximal covering problem has not been previously studied in the literature. Unlike the classical maximal covering problem, the variant proposed in this dissertation includes user preferences for locations, where users are assigned to the location with opened facility that they prefer the most. Additionally, different locations have different costs for establishing facilities, and the available budget for opening facilities is limited. This problem is solved using the Variable Neighborhood Search (VNS) method, and the results were compared with the ones obtained by an exact solver on modified instances from the literature. Furthermore, an existing variant of the maximal covering problem is also addressed, which imposes the limit on the number of opened facilities instead of limiting the budget for opening facilities. The second problem examined is the regenerator placement in optical networks. In optical networks, signal quality degrades with distance, necessitating the place- ment of costly devices to restore the signal. This dissertation studies an existing model where the set of possible regenerator locations and the set of user nodes are different, defining the problem as generalized. The generalized regenerator place- ment problem in optical networks is also solved using the Variable Neighborhood Search method, with results compared to the best available solutions from the lit- erature. Bi-objective variants of these problems are defined as well. For the maximal covering location problem, user preferences are included as weighted factors in the total covered demand, forming the first objective function. The second objective function represents the number of uncovered users and aims to ensure fairness in the model. In the regenerator placement problem for optical networks, it is assumed that, due to budget constraints, uninterrupted communication between all pairs of user nodes may not be feasible. Each pair is assigned a weight, and the sum of the weights of connected pairs constitutes the first objective function, while the second objective function represents the cost of placing regenerators. These bi-objective variants are solved using an adapted multi-objective version of the Variable Neigh- borhood Search method, and the results are compared with general evolutionary algorithms. URI: http://hdl.handle.net/123456789/5750 Files in this item: 1
lazar_mrkela_doktorska_disertacija.pdf ( 17.56Mb ) -
Protić, Danijela (Beograd , 2023)[more][less]
Abstract: Anomaly detection is the recognition of suspicious computer network behavior by comparing unknown network traffic to a statistical model of normal network behavior. Binary classifiers based on supervised machine learning are good candidates for normality detection. This thesis presents five standard binary classifiers: the k-nearest neighbors, weighted k-nearest neighbors, decision trees, support vector machines and feedforward neural network. The main problem with supervised learning is that it takes a lot of data to train high-precision classifiers. To reduce the training time with minimal degradation of the accuracy of the models, a two-phase pre-processing step is performed. In the first phase, numeric attributes are selected to reduce the dataset. The second phase is a novel normalization method based on hyperbolic the tangent function and the damping strategy of the Levenberg-Marquardt algorithm. The Kyoto 2006+ dataset, the only publicly available data set of real-world network traffic intended solely for anomaly detection research in computer networks, was used to demonstrate the positive impact of such pre-processing on classifier training time and accuracy. Of all the selected classifiers, the feedforward neural network has the highest processing speed, while the weighted k-nearest neighbor model proved to be the most accurate. The assumption is that when the classifiers work concurrently, they should detect either an anomaly or normal network traffic, which occasionally is not the case, resulting in different decision about the anomaly, i.e. a conflict arises. The conflicting decision detector performs a logical exclusive OR (XOR) operation on the outputs of the classifiers. If both classifiers simultaneously detected an anomaly or recognized traffic as normal, their decision was no conflict had occurred. Otherwise a conflict is detected. The number of conflicts detected provides an opportunity for additional detection of changes in computer network behavior. URI: http://hdl.handle.net/123456789/5599 Files in this item: 1
Danijela Protic - Doktorska Disertacija.pdf ( 3.143Mb ) -
Radosavljević, Jovan (Beograd , 2023)[more][less]
Abstract: Graph G = (V,E) is an ordered pair of set of nodes V and branches E. Order graph G is the number of nodes |V |, and its size is the number of branches |E|. Knots u, v ∈ V are adjacent if there is a branch uv ∈ E between them. Distance dist(u, v) nodes u and v G is the length of the shortest path from u to v. The diameter of the graph G is the largest distance dist(u, v) let two nodes in, v. They are discussed in the dissertation graphs of diameter 2. Intuitively, the notion that graphs are dia- meters 2 simple structures; however, they are known to be asymptotically close all graphs of diameter 2. That is why a narrower class is interesting — class D2C of critical graphs of diameter 2, i.e. graphs where the removal of any branches leads to an increase in diameter. In addition, a narrower class of pri- mitive D2C (PD2C) graphs, i.e. D2C graphs that do not have two nodes with the same set of neighbors. In the introductory chapter 2, the basic concepts, algorithms and dings used in the dissertation. They are presented in the following chapters original results regarding diameter graphs 2. Chapter 3 describes the procedure for obtaining a list of D2C graphs of order up to 13. With built-in parallelization, the creation of a list of D2C graphs of order up to 13 it lasted a month. This was a step forward, because previously there was a spi- around all graphs of diameter 2 lines up to 10. The obtained results were used for testing several known hypotheses about graphs of diameter 2. In chapter 4 it is shown that for every m ⩾ 3 a D2C graph containing cli- a ku of size m must have at least 2m nodes. At the same time, with accuracy up to isomorphism, there is exactly one graph of size 2m that contains a clique of characters m. Chapter 5 discusses PD2C graphs with the smallest number of branches. From list of all PD2C graphs of order n ⩽ 13 are selected PD2C graphs of size at most 2n − 4. Only three of the isolated graphs are of size 2n − 5, which is in accordance with the statement of the Erdes-Renji theorem about the lower bound for the size graphs of diameter 2 that do not contain a node adjacent to all other nodes (that limit is 2n − 5). PD2C graphs of size 2n − 4 rows up to 13 sorted are in three groups: • The first group belongs to the Z family, defined in the dissertation, which for each n ⩾ 6 contains exactly one PD2C graph of order n of size 2n − 4. • The second group consists of seven Hamiltonian PD2C graphs of order at most 9 of size 2n−4. In the dissertation it was proved that there is no such Hamil- tone graph of order greater than 11, i.e. that the seven graphs found are the only ones Hamiltonian PD2C graphs of size 2n − 4. • The third group consists of a unique graph that does not belong to any of the first two groups. Based on these results, the hypothesis was formulated that all PD2C graphs re- that n ⩾ 10 and sizes 2n − 4 belong to the family Z. Keywords: graphs, critical graphs of diameter 2, primitive graph- You Scientific field: Computing and informatics Narrower scientific field: Graph theory UDC number: 004.415.5(519.1 URI: http://hdl.handle.net/123456789/5594 Files in this item: 1
disertacijaJovanRadosavljevic.pdf ( 746.0Kb ) -
Carić, Marko (Beograd , 2023)[more][less]
Abstract: This dissertation discusses the problem of calculating the number of equivalent classes of a Boolean function. The difficulty of determining the number of equivalence classes increases sharply with the number of variables sn. The motivation for choosing this topic lies in the fact that concrete numbers have been known so far only for relatively small values of n, although the problem itself has long been theoretically solved. Let G be the permutation group of the set Bn={0,1}n. Effect of Gonscalar group, Bn→B1, that is, vector invertible Boolean functions, Bn→Bn. Two scalar Boolean functions f(k)ig(k), defined by Bn, are considered equivalent. ∈G forever ∈Bnf(k )=g(σ(k)) holds. Two vector invertible Boolean functions f(k) and g(k) are considered equivalent in relation to the group G, i.e. ))).The equivalence relation∼decomposes the sets of all Boolean functions into equivalence classes.The equivalence of Boolean functions confers significant applications in the logical synthesis of combinatorial circuits and cryptography, especially in connection with the design of S-boxes. Let Un(G) and Vn(G) denote the number of scalar equivalence classes, ie. vector invertible Boolean functions of n variables with respect to the group G. The numbers Un(G) and Vn(G) can be calculated relatively simply if the cycle index from the group G to the G group is known. Induced by the group Snpermutations of coordinate elements step = (k1,k2,...,kn)∈Bn, •group Gn, induced by permutations and additions of coordinates, •group GLnlinear invertible transformations of elements of vector space Bn, and •group AGLof invertible transformations of elements Bn. If the permutation σ∈Ghasikcycles of lengthk1, its cycle structure is(σ)=(i1,i2,...).The cyclic index of the groupGisgeneratrix ZG(f1,f2,...)=1 |G|σ∈Gk1 fik k structure cycles σene structures of cycles σfraconstructionsGsides ∗pressuresGpermutations of the red group are known, but the cycle indexes itself, i.e. numbers Un(G) and Vn(G), are practically calculated only for relatively small values, for example n10. The dissertation presents original results in the field of enumeration of equivalence classes of Boolean functions in relation to these four groups of soft transformations. A similar expression is derived for all four groups of soft transformations for the cycle index in the form of the sumover partition softhennumbern. Based on the precyclical index much more. An overview of known results for relatively small and new results in the thesis for larger ones are shown in the following table: Number\GSnGnGLnAGLn Un(G)11→3310→328→3110→31 Vn(G)6→307→276→266, participates in direct effect, by special effect 26 latingthenumberofequivalenceclassesthatdoesnotuseacycleindex is shown and described in the third paper from the introductory chapter. These second parts of the dissertation refer to monotone Boolean functions — scalar Boolean functions that satisfy the condition of monotonicity (from which follows f(k)f(i)). Letrn, i.e. monotoneBooleanfunctionsofnvariables. The difficulty of calculating the number rn increases rapidly with n, so that until recently the last term of the sequence to be calculated was r7. The procedure described in the dissertation is based on Frobenius' theorem, on the basis of which the number r8 was determined. The dissertation consists of the first introductory chapter and the following three chapters. In the second chapter, theoretical concepts related to the material from chapters 3 and 4 are introduced, and they relate to discrete mathematics, combinatorics and the index of the cycle considered by the soft cycle of the 3rd form for describing the 3rd cycle. indices for the four considered groups of permutations, as well as the numbers Un(G) and Vn(G) of the equivalent class of the Boolean function with respect to these groups. First, the common improvements for all four groups are discussed, and then the specific accelerations related to individual groups are published by group. ter. In Chapter 4, the problem of finding the number of equivalence classes of a monotone Boolean function is solved. First, a general expression for calculating a number is given based on the Frobenius theorem of the form of the sum (by the soft number partition of the number) of the number from the fixed part of the graph corresponding to the point corresponding to the point. In different partitions, different ways of calculating the number of non-fixed points for n8 are shown. The procedure based on which the number r8 was calculated, which also represents the original contribution of this dissertation, is shown in the first paper from the list from pp. 1 to 3. practically at the same time the obtained result described in the dissertation. URI: http://hdl.handle.net/123456789/5571 Files in this item: 1
MarkoCaricDisertacija.pdf ( 1.467Mb )