Mathematical Sciences
Sub-communities within this community
Collections in this community
Recent Submissions
-
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 ) -
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/5791 Files in this item: 1
Disertacija_17133.pdf ( 17.47Mb ) -
Jovanović, Miljana (Beograd , 2024)[more][less]
Abstract: One of the main objectives of the Gaia mission of the European Space Agency is to construct a celestial reference frame at the wavelengths of the optical domain, Gaia CRF. This frame needs a link to the International Celestial Reference Frame – ICRF which is fixed with respect to distant objects (quasars). The objects serving for the purpose of linking are required to be visible in both domains (optical and radio). A set of 47 such objects has been proposed and included which in the radio domain have no detected extended emission. The mentioned objects are active galactic nuclei (AGN) the brightness of which varies over the whole electromagnetic spectrum. The brightness change may be due to activity in different AGN regions, but also to external factors. Such variations can lead to changes in the photocentre position and, consequently, to changes of the object coordinates. In order to establish which objects are suitable for linking these two frames we have examined the brightness variation in the optical domain. The objects have been observed from 2013 in the V and R bands. We have analysed the brightness, colour (V − R) and optical spectral index (α). It has been established that for the majority of objects the brightness is variable, or possibly variable. Almost 15% of all objects have significant changes in their brightness (more than 1 mag), only ∼10% are stable with minor brightness changes of ∼0.3 mag. The results concerning the change analysis of the colour and α are also presented. Based on these results 17 objects are chosen as suitable for linking ICRF to Gaia CRF. The results of the analysis, as well as the observed values, are essential for the examination of these objects because of their importance in astrometry, also in astrophysics. These data are relevant to a better understanding of formation and evolution of galaxies. URI: http://hdl.handle.net/123456789/5790 Files in this item: 1
Disertacija_17135.pdf ( 39.58Mb ) -
Jovanović, Milica (Beograd , 2024)[more][less]
Abstract: The analysis of Grassmann manifolds, which were first introduced in the 19th century, is one of the classical problems in the algebraic topology. When analyzing topological spaces, it is always useful to determine their cohomology algebra. The cohomology of Grassmann manifolds is already well known, but their covering spaces, so called oriented Grassmann manifolds, are far less examined. The oriented Grassmann manifold ˜Gn,k is defined to be the space of oriented k-dimensional subspaces of Rn. In this dissertation we analyze the cohomology algebra of oriented Grassmann manifolds ˜Gn,k with integer and modulo 2 coe!cients, predominantly the case k = 3. The dissertation comprises three chapters. The first chapter is an introduction where an overview of known results and necessary tools is given. In the second chapter we study the cohomology with the modulo 2 coe!cients. First of all, the known results in the case k = 2 are presented. Next, we move onto the case k = 3 where the partial description of the cohomology algebra is given. This section is based on papers published in the last several years. We give an overview of these results in the thesis, and we also present original results for n close to a power of two. In the last part of this chapter, we investigate the cohomology algebra of the manifold ˜G2t,4, and that is as far as we have come with the examination of modulo 2 cohomology. The third chapter is dedicated to the integral cohomology. This chapter, like the previous one, also splits in several sections, depending on the value of k. When k = 2, the integral cohomology is completely determined, and we present the proof for n odd. When k = 3, only the integral cohomology of ˜Gn,3, n → {6, 8, 10}, has been determined so far, while for k ↭ 4 only some partial results are known. In this segment we also analyze the connection between the integer and the modulo 2 cohomology algebra of these Grassmannians by analyzing the morphism between them induced by the modulo 2 reduction. URI: http://hdl.handle.net/123456789/5789 Files in this item: 1
Disertacija_17158.pdf ( 1.723Mb ) -
Babić, Marijana (Beograd , 2026)[more][less]
Abstract: The only non-compact four-dimensional rank-one symmetric spaces are the complex hyperbolic plane CH2 and the four-dimensional real hyperbolic space RH4. As connected homogeneous manifolds of negative sectional curvature, these spaces admit the structure of a four-dimensional real solvable Lie group equipped with a left-invariant metric. This Lie group appears naturally in the Poincar´e half-space model of real hyperbolic space and in the Siegel paraboloid model of the complex hyperbolic plane. The boundary of the paraboloid model carries the structure of the Heisenberg group. Hermitian structures consist of a left-invariant Riemannian metric together with a compatible complex structure. In this thesis, all such structures are classified and their geometric properties are studied. It is shown that every Riemannian metric on real hyperbolic space admits a two-dimensional sphere of Hermitian complex structures. In the case of the complex hyperbolic plane, some metrics admit exactly four distinct Hermitian complex structures, while others admit a two-dimensional sphere of such structures. Their curvature properties, holonomy groups, and self-duality are investigated. It is shown that the standard metric on the complex hyperbolic plane is the unique K¨ahler metric within the obtained classification, whereas all Riemannian metrics on real hyperbolic space are Einstein. Geodesics on the solvable Lie groups of the spaces CH2 and RH4, with respect to all possible left-invariant Riemannian metrics, are studied in this thesis using the Euler–Arnold equations. These equations effectively reduce a system of secondorder differential equations on a Lie group to a system of first-order equations on the corresponding Lie algebra. Numerical solutions of these equations enable the visualization of geodesics and geodesic spheres. URI: http://hdl.handle.net/123456789/5787 Files in this item: 1
Marijana_Babic_doktorska_disertacija.pdf ( 1.761Mb )