Computer Science
Recent Submissions
-
Šandrih, Branislava (Beograd , 2020)[more][less]
Abstract: The main goal of this dissertation is to put different text classification tasks in the same frame, by mapping the input data into the common vector space of linguistic attributes. Subsequently, several classification problems of great importance for natural language processing are solved by applying the appropriate classification algorithms. The dissertation deals with the problem of validation of bilingual translation pairs, so that the final goal is to construct a classifier which provides a substitute for human evalu- ation and which decides whether the pair is a proper translation between the appropriate languages by means of applying a variety of linguistic information and methods. In dictionaries it is useful to have a sentence that demonstrates use for a particular dictio- nary entry. This task is called the classification of good dictionary examples. In this thesis, a method is developed which automatically estimates whether an example is good or bad for a specific dictionary entry. Two cases of short message classification are also discussed in this dissertation. In the first case, classes are the authors of the messages, and the task is to assign each message to its author from that fixed set. This task is called authorship identification. The other observed classification of short messages is called opinion mining, or sentiment analysis. Starting from the assumption that a short message carries a positive or negative attitude about a thing, or is purely informative, classes can be: positive, negative and neutral. These tasks are of great importance in the field of natural language processing and the proposed solutions are language-independent, based on machine learning methods: sup- port vector machines, decision trees and gradient boosting. For all of these tasks, a demonstration of the effectiveness of the proposed methods is shown on for the Serbian language. URI: http://hdl.handle.net/123456789/5801 Files in this item: 1
Disertacija.pdf ( 9.053Mb ) -
Veljković, Aleksandar (Beograd , 2023)[more][less]
Abstract: Bioinformatics as a science of the future faces the problems of processing a large amount of data that is increasing every day. In addition to the problem of data storage, the challenge is also data analysis and the understanding of hidden relations between biological entities that are observed only after unifying data from different data sources. This thesis proposes a novel data model for the unification of heterogeneous data from multiple bioinformatics databases and a system architecture design for implementing software systems based on the proposed data model. Additionally, the thesis defines an automated pipeline for discovering new semantic similarity relations based on data mining methods using the data found in the proposed data model. The data model, software architecture, and automatic pipeline are evaluated using data from five real-world bioinformatics databases. The results demonstrate a high flexibility of the data model and the high efficiency of the software system implemented following the proposed architecture design. URI: http://hdl.handle.net/123456789/5794 Files in this item: 1
Disertacija_15649.pdf ( 2.864Mb ) -
Carić, Marko (Beograd , 2023)[more][less]
Abstract: In this dissertation, the problem of calculating the number of equiva- lence classes of Boolean functions is discussed. The difficulty of determining the number of equivalence classes increases sharply with the number of variables n. 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 was theoretically solved a long time ago. Let G be the group of permutations of the set Bn = {0, 1}n. The effect of the group G on scalar, Bn 7 → B1, that is, vectorial invertible Boolean functions, Bn 7 → Bn. Two scalar Boolean functions f (x) and g(x), defined on Bn, are considered equivalent with respect to the group G, i.e. f ∼ g, if for some σ ∈ G for every x ∈ Bn f (x) = g(σ(x)) holds. Two vector invertible Boolean functions f (x) and g(x), are considered equivalent with respect to the group G, i.e. f ∼ g, if for some pair (σ, ρ) ∈ G × G for each x ∈ Bn holds g(x) = ρ(f (σ(x))). The equivalence relation ∼ decomposes the set of all Boolean functions into equivalence classes. Equivalence of Boolean functions has significant applications in the logical synthesis of combinatorial circuits and in cryptography, especially in connection with the design of S-boxes. Let Un(G) and Vn(G) denote number of equivalence classes of scalar, i.e. vector invertible Boolean functions of n variables in relation to the group G. The numbers Un(G) and Vn(G) can be calculated relatively simply if the cycle index of the group G is known. The dissertation considers four groups G of permutations of the set Bn: • group S′ n induced by group Sn permutations of coordinates elements x = (x1, x2, . . . , xn) ∈ Bn, • group Gn, induced by permutations and complementations of coordinates, • group of GLn linear invertible transformations elements of the vector space Bn, i • group of AGLn affine invertible transformations elements Bn. If the permutation σ ∈ G has ik cycles of length k ⩾ 1, its cycle structure is i(σ) = (i1, i2, . . .). The cyclic index of the group G is the generatrix ZG(f1, f2, . . .) = 1 |G| X σ∈G Y k⩾1 f ik k of cycle structures of all permutations σ ∈ G. General expressions for cycle indices the four considered groups are known, but the cycle indices themselves, i.e. the numbers Un(G) and Vn(G), are practically calculated only for relatively small values, for e.g. n ⩽ 10. The dissertation presents original results in the field of enumeration of equiv- alence classes of Boolean functions in relation to these four groups of transfor- mations. A similar expression was derived for all four groups of transformations for the cycle index in the form of sum over partitions of the number n. Based on that expression and previously calculated tables, the cycle index is calculated much more efficiently. An overview of known results for relatively small n and new results in the thesis for larger n is shown in the following table: Number\ G S′ n Gn GLn AGLn Un(G) 11 → 33 10 → 32 8 → 31 10 → 31 Vn(G) 6 → 30 7 → 27 6 → 26 6 → 26 Specially, in the case of the permutation group S′ n, an effective direct procedure for calculating the number of equivalence classes that does not use a cycle index is shown, and is described in the third paper from the introductory chapter. The second part of the dissertation concerns monotone Boolean functions — scalar Boolean functions which satisfy the monotonicity condition (from x ⩽ y follows f (x) ⩽ f (y)). Let rn, i.e. dn (the n-th Dedekind number), denote the number of equivalence classes of monotone Boolean functions in relation to the group S′ n, that is, the total number of monotone Boolean functions of n variables. The difficulty of calculating the number rn increases rapidly with n, so that until recently the last calculated member of the sequence was r7. The procedure described in the dissertation is based on the Frobenius theorem, by which it was determined number r8. In doing so, the known value of the number d8 is used. The dissertation consists of the first - introductory chapter and the following three chapters. In the second chapter, theoretical terms related to the material from chapters 3 and 4 are introduced, and they refer to discrete mathematics, combinatorics and cycle indices of the considered four groups of transformations. Chapter 3 describes the procedure for calculating the cycle indices for the four considered groups of permutations, as well as numbers Un(G) and Vn(G) equivalence classes of Boolean functions in relation to these groups. First, common improvements for all four groups are considered, and then specific accelerations related to individual groups. These results are published in the second paper listed in the introductory chapter. In chapter 4, the problem of finding the number of equivalence classes of monotone Boolean functions is solved. First, a general expression for calculating the number rn is given based on the Frobenius theorem in the form of the sum (by partitions of the number n) of the number of fixed points of the permutation corresponding to the partition. After that, depending on the graphs corresponding to different partitions, different ways of calculating the number of fixed points for n ⩽ 8 are shown. The procedure based on which the number r8 was calculated, which also represents the original contribution of this dissertation is presented - see the first paper from the list from the introductory chapter. Applying a similar procedure, Pawelski [31] calculated r8 practically at the same time as the obtained result described in the dissertation. URI: http://hdl.handle.net/123456789/5792 Files in this item: 1
Disertacija_15671.pdf ( 2.414Mb ) -
Ristović, Ivan (Beograd , 2026)[more][less]
Abstract: Cloud-computing platforms provide services to consumers through multiple serviceoffering models. Recent advances in these models have led to the emergence of serverless computing, or simply serverless, where infrastructure is managed by the service provider. Serverless is usually coupled with function-based programming model in which software systems are composed of reusable, lightweight units of code executed within isolated sandboxed environments. Major cloud-computing platforms, including Amazon Web Services (AWS), Microsoft Azure, and Google Cloud, report that a substantial proportion of their customers employ serverless solutions. Most cloud-computing providers employ a pay-as-you-go billing model. Inefficient utilization of computing resources, particularly CPU time and working memory, which constitute the most costly resources, leads to increased overall operational costs. Moreover, the requirement for resource isolation adversely affects initialization latency and results in additional CPU and working-memory overhead. Serverless sandboxes are typically deployed on top of heavyweight virtualization stacks that includeJava, JavaScript, or Python runtime environments with accompanying frameworks, further increasing working-memory consumption. Modern cloud-computing architectures use Checkpoint/Restore (abbr. c/r) techniques to freeze initialized sandboxes into a continuable form. Such techniques, in combination with cloud-native deployments, allow the virtualized environment to optimize resource consumption and share code and pre-initialized data across multiple sandboxes. However, such solutions either operate at application-build time to support data pre-initialization or sharing, or operate at execution time with limited sharing potential for data available during application execution. Such data is processed multiple times and duplicated in each sandbox. This dissertation presents Doss, a direct object snapshotting and sharing system that performs data c/r during application execution. Doss persists data directly, without transformations, into reusable and shareable snapshots. Direct snapshotting allows Doss to achieve near-constant data deserialization time, greatly improving initialization times and reducing CPU usage. Doss architecture enables snapshot sharing across application instances, eliminating the excess memory footprint associated with data re-processing and duplication. GraalDoss, a Doss implementation for Java, is integrated into the GraalVM ecosystem. GraalDoss is evaluated using 106 correctness and robustness tests and a novel set of cloudnative micro and macro benchmarks that exercise real-world scenarios. A comprehensive evaluation of GraalDoss shows a consistent near-constant data-deserialization overhead with serialization times comparable to state-of-the-art Java JSON and binary serialization libraries. GraalDoss reduces the memory footprint of web API microservice caches by sharing populated cache snapshots across microservice instances, improving the overall density by 41% for 8 microservice instances and improving first-response times by 34%. In NLP applications, GraalDoss improves the pipeline execution times by six orders of magnitude by snapshotting pipeline results and subsequently loading the snapshots. URI: http://hdl.handle.net/123456789/5786 Files in this item: 1
IvanRistovic_PhD_Dissertation.pdf ( 4.683Mb ) -
Kapunac, Stefan (Beograd , 2026)[more][less]
Abstract: This dissertation addresses methods for efficiently solving several important variants of domination problems on graphs, with a particular focus on large-scale instances that frequ- ently appear in real-world systems. Domination problems have numerous applications in the analysis and management of complex networks, including social, telecommunication, transport, and biological networks. The study covers four problems: minimum weight total domination, minimum weight independent domination, k-strong Roman domination, and the canonical mi- nimum domination problem on large graphs. For the minimum weight total domination problem, a variable neighborhood search approach is proposed, with carefully designed mechanisms for shaking, local search, and fitness function evaluation. The results show that the proposed algorithm achieves optimal solutions on small and medium instances and outperforms competing approaches on large graphs. Additionally, an application of this problem for accelerating information spreading in social networks is proposed. For the minimum weight independent domination problem, two new integer linear pro- gramming models are developed. Solving these models finds optimal solutions for all smaller instances while demonstrating superior performance compared to competing exact approaches on larger graphs. In addition, a greedy heuristic is proposed that outperforms competing greedy methods on most instances. In the case of k-strong Roman domination, a greedy heuristic based on node coverage information is developed, along with a metaheuristic approach based on variable neighborhood search that uses the greedy algorithm for initialization. This problem is particularly challenging due to the exponential complexity of solution feasibility verification, leading to the introduction of the concept of quasi-feasibility that enables efficient feasibility assessment during the search. Experimental results show that the proposed algorithm consistently outperforms the greedy approach and existing competing methods, especially on larger graphs. The practical value of the algorithm is illustrated through a case study involving the optimal positioning of fire stations and vehicles in urban municipalities to ensure the entire city is safe in the event of k simultaneous fires. For the minimum domination problem, a new hybrid approach called IRIS is proposed. IRIS is designed as a general-purpose framework that bridges the gap between exact integer linear programming solvers and heuristic search by iteratively fixing selected variables to reduce the search space. Тhe novelty lies in its flexible subproblem construction mechanism, which can be tailored using various selection strategies. In this study, we implement and evaluate a specific configuration of IRIS that utilizes historical statistical data and a node-coverage-based heuristic to intelligently identify variables for fixing. This targeted approach allows the ILP solver to find high-quality solutions for large-scale instances that are computationally prohibitive for exact methods. Experimental results demonstrate that IRIS achieves competitive performance com- pared to the best existing methods, establishing it as a valid alternative for solving domination and potentially other NP-hard problems. URI: http://hdl.handle.net/123456789/5782 Files in this item: 1
phdStefanKapunac.pdf ( 3.299Mb )