http://hdl.handle.net/123456789/4 http://hdl.handle.net/123456789/5792 PREBROJAVANJE KLASA EKVIVALENCIJE BULOVIH FUNKCIJA Carić, Marko 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. http://hdl.handle.net/123456789/5791 METAHEURISTIČKE METODE VIŠEKRITERIJUMSKE OPTIMIZACIJE I PRIMENE NA DISKRETNE LOKACIJSKE PROBLEME Mrkela, Lazar 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. http://hdl.handle.net/123456789/5790 PROMENA V I R MAGNITUDA IZABRANIH KVAZARA I POVEZIVANJE SISTEMA GAIA SA SISTEMOM ICRF Jovanović, Miljana 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. http://hdl.handle.net/123456789/5789 KOHOMOLOŠKA ALGEBRA GRASMANOVIH MNOGOSTRUKOSTI ORIJENTISANIH TRODIMENZIONALNIH RAVNI U EUKLIDSKOM PROSTORU Jovanović, Milica 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.