Given a square with integer side length n, we ask for the number of different ways to divide it into sub-squares, considering only the list of parts. We enumerate all possible lists and check whether a placement with those squares is possible. In order to do this, we propose a new algorithm for creating perfect square packings.

For a graph G, the minimum dominating set problem is to find a minimum size set S of vertices of G such that every vertex is either in S or adjacent to a vertex in the set. The decision version of this problem, which asks whether G has a dominating set of a particular size k, is known to be NP-complete, and no polynomial time algorithm to solve the problem is currently known to exist. The queen domination problem is to find the minimum number of queens which, collectively, can attack every square on an n by n chess board. The related border queen problem is to find such a collection of queens with the added restriction that all queens lie on the outer border of the board. This thesis studies practical exponential time algorithms for solving domination problems, and presents an experimental comparison of several different algorithms, with the goal of producing a broadly effective general domination solver for use by future researchers. The developed algorithms are then used to solve several open problems, including cases of the queen domination problem and the border queen problem. In addition, new theoretical upper bounds are presented for the border queen problem for some families of queen graphs. / Graduate

Given a square with integer side length n, we ask for the number of different ways to divide it into sub-squares, considering only the list of parts. We enumerate all possible lists and check whether a placement with those squares is possible. In order to do this, we propose a new algorithm for creating perfect square packings.

No description available.

No description available.

Le but de cette thèse est de modéliser la propagation d’un contaminant au sein d’un réseau d’eau potable muni de capteurs temps réel. Elle comporte les trois axes de développement suivant: la résolution des équations de transport, celle du problème d’identification des sources de contamination et le placement des capteurs.Le transport d’un produit chimique est modélisé dans un réseau d’eau potable par l’équation de transport réaction 1-D avec l’hypothèse de mélange parfait aux noeuds. Il est proposé d’améliorer sa prédiction par l’ajout d’un modèle de mélange imparfait aux jonctions double T et d’un modèle de dispersion prenant en compte un profil de vitesse 3-D et la diffusion radiale. Le premier modèle est créé à l’aide d’un plan d’expériences avec triangulation de Delaunay, de simulations CFD, et de la méthode d’interpolation krigeage. Le second utilise les équations adjointes du problème de transport avec l’ajout de particules évoluant à l’aide d’une marche aléatoire, cette dernière modélisant la diffusion radiale dans la surface droite du tuyau.Le problème d’identification des sources consiste, à l’aide de réponses positives ou négatives à la contamination des noeuds capteurs, à trouver l’origine, le temps d’injection et la durée de la contamination. La résolution de ce problème inverse est faite par la résolution des équations de transport adjointes par formulation backtracking. La méthode donne la liste des sources potentielles ainsi que le classement de celles-ci selon leur probabilité d’être la vraie source de contamination. Elle s’exprime en fonction de combien, en pourcentage, cette source potentielle peut expliquer les réponses positives aux capteurs.Le placement des capteurs est optimisé pour l’identification des sources. L’objectif est la maximisation du potentiel de détection de la véritable source de contamination. Deux résolutions sont testées. La première utilise un algorithme glouton combiné à une méthode de Monte Carlo.La seconde utilise une méthode de recherche locale sur graphe.Finalement les méthodes sont appliquées à un cas test réel avec dans l’ordre : le placement des capteurs, l’identification de la source de contamination et l’estimation de sa propagation. / The aim of this thesis is to model the propagation of a contaminant inside a water distribution network equipped with real time sensors. There are three research directions: the solving of the transport equations, the source identification and the sensor placement. Classical model for transport of a chemical product in a water distribution network isusing 1D-advection-reaction equations with the hypothesis of perfect mixing at junctions. It isproposed to improve the predictions by adding a model of imperfect mixing at double T-junctions and by considering dispersion effect in pipes which takes into account a 3-D velocity profile. The first enhancement is created with the help of a design of experiment based on the Delaunay triangulation, CFD simulations and the interpolation method Kriging. The second one uses the adjoint formulation of the transport equations applied with an algorithm of particle backtracking and a random walk, which models the radial diffusion in the cross-section of a pipe.The source identification problem consists in finding the contamination origin, itsinjection time and its duration from positive and negative responses given by the sensors. The solution to this inverse problem is computed by solving the adjoint transport equations with a backtracking formulation. The method gives a list of potential sources and the ranking of thosemore likely to be the real sources of contamination. It is function of how much, in percentage, they can explain the positive responses of the sensors.The sensor placement is chosen in order to maximize the ranking of the real source of contamination among the potential sources. Two solutions are proposed. The first one uses agreedy algorithm combined with a Monte Carlo method. The second one uses a local search method on graphs. Finally the methods are applied to a real test case in the following order: the sensor placement, the source identification and the estimation of the contamination propagation.

Solar parks are increasingly getting a larger market share of PV installations over the world, and have for the last couple of years managed to establish itself in the Swedish market. The market has for a long time been known for its decline in module prices, which has allowed an emergence of more efficient PV-techniques such as one-axis trackers and bifacial modules. Bifacial modules use the backside of modules for improved utiliziation of incoming light, while one-axis trackers have the ability to track the sun in order to maximise light absorption. These innovations have now caught the interest of companies willing to invest in large-scale PV-farms, where efficient land use is highly regarded. The aim of this thesis was to examine how bifacial modules and one-axis trackers perform in terms of system performance and profitabilty if implemented in 'Solpark Fyrislund', a solar park owned by Vasakronan AB. This was done by modelling and simulating cases in which said techniques were incorporated. The data was later used to estimate profitabilty of each investigated case. Results showed that the highest system performance and profitability was achieved by installing bifacial modules on the site. One-axis trackers are currently too expensive, require higher maintenance and has a higher demand for land, resulting in its profitability not being justified. It was also found that the current configuration could be optimized further for higher profit, by slightly reducing the pitch as well as increasing the tilt of the existing modules. The study should be followed up by further investigating the use of backtracking for one-axis trackers. Said innovations should also be more established in the Swedish market so that CAPEX- and OPEX prices become more accessible.

An interesting problem in proof theory is to find representations of proof that do not distinguish between proofs that are ‘morally’ the same. For many logics, the presentation of proofs in a traditional formalism, such as Gentzen’s sequent calculus, introduces artificial syntactic structure called ‘bureaucracy’; e.g., an arbitrary ordering of freely permutable inferences. A proof system that is free of bureaucracy is called canonical for a logic. In this dissertation two canonical proof systems are presented, for two logics: a notion of proof nets for additive linear logic with units, and ‘classical proof forests’, a graphical formalism for first-order classical logic. Additive linear logic (or sum–product logic) is the fragment of linear logic consisting of linear implication between formulae constructed only from atomic formulae and the additive connectives and units. Up to an equational theory over proofs, the logic describes categories in which finite products and coproducts occur freely. A notion of proof nets for additive linear logic is presented, providing canonical graphical representations of the categorical morphisms and constituting a tractable decision procedure for this equational theory. From existing proof nets for additive linear logic without units by Hughes and Van Glabbeek (modified to include the units naively), canonical proof nets are obtained by a simple graph rewriting algorithm called saturation. Main technical contributions are the substantial correctness proof of the saturation algorithm, and a correctness criterion for saturated nets. Classical proof forests are a canonical, graphical proof formalism for first-order classical logic. Related to Herbrand’s Theorem and backtracking games in the style of Coquand, the forests assign witnessing information to quantifiers in a structurally minimal way, reducing a first-order sentence to a decidable propositional one. A similar formalism ‘expansion tree proofs’ was presented by Miller, but not given a method of composition. The present treatment adds a notion of cut, and investigates the possibility of composing forests via cut-elimination. Cut-reduction steps take the form of a rewrite relation that arises from the structure of the forests in a natural way. Yet reductions are intricate, and initially not well-behaved: from perfectly ordinary cuts, reduction may reach unnaturally configured cuts that may not be reduced. Cutelimination is shown using a modified version of the rewrite relation, inspired by the game-theoretic interpretation of the forests, for which weak normalisation is shown, and strong normalisation is conjectured. In addition, by a more intricate argument, weak normalisation is also shown for the original reduction relation.

Dans cette thèse, nous nous intéressons à la résolution exacte de programmes linéaires en variables binaires. L'ensemble de nos travaux s'articule autour de l'étude de Resolution search (Chvátal (1997)) pour la résolution du problème du sac à dos multidimensionnel en 0-1. Dans un premier temps, nous proposons un algorithme d'énumération implicite centré sur une analyse des coûts réduits à l'optimum de la relaxation continue ainsi que sur une décomposition de l'espace de recherche en hyperplans. Nous proposons une stratégie de branchement originale visant à élaguer au plus tôt l'arbre de recherche. Cette stratégie est efficace pour résoudre des instances jugées difficiles mais rend l'algorithme dépendant de la connaissance d'une bonne solution de départ. Dans un deuxième temps, nous proposons une méthode de résolution plus autonome combinant Resolution search avec une énumération implicite inspirée du premier algorithme. Cette coopération permet d'obtenir rapidement de bonnes solutions et prouve les optimums d'instances de plus grande taille. Finalement, nous présentons une application de Resolution Search à la résolution d'un problème de planification dans le domaine des télécommunications.

No description available.