Spelling suggestions: "subject:"ordered set"" "subject:"6rdered set""
11 |
A Study on Poset Probability / En studie om PomängdsprobabilitetJaldevik, Albin January 2022 (has links)
Let <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cmathbb%7BP%7D%20=%20(%5Cmathbb%7BP%7D,%20%5Cpreceq)" data-classname="equation_inline" data-title="" /> be a finite poset (partially ordered set) with cardinality <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?n" data-classname="equation_inline" data-title="" />. A linear extension of <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cmathbb%7BP%7D" data-classname="equation_inline" data-title="" /> is an order-preserving bijection <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Csigma" data-classname="equation_inline" data-title="" />: <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cmathbb%7BP%7D%20%5Crightarrow%20%5Bn%5D" data-classname="equation_inline" data-title="" />, that is, if <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?x%20%5Cpreceq%20y" data-classname="equation_inline" data-title="" /> in <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cmathbb%7BP%7D" data-classname="equation_inline" data-title="" /> then <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Csigma(x)%20%5Cle%20%5Csigma(y)" data-classname="equation_inline" data-title="" />. We define the poset probability <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?P(%5Calpha%20%5Cpreceq%20%5Cbeta)" data-classname="equation_inline" data-title="" /> as the proportion of linear extensions where <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Csigma(%5Calpha)%20%5Cle%20%5Csigma(%5Cbeta)" data-classname="equation_inline" data-title="" />. We are primarily interested in <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?P(%5Calpha%20%5Cpreceq%20%5Cbeta)" data-classname="equation_inline" data-title="" /> for incomparable elements <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Calpha%20%5Cparallel%20%5Cbeta" data-classname="equation" data-title="" />. The probability has significance in areas such as information theory. Let <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?e(%5Cmathbb%7BP%7D)" data-classname="equation_inline" data-title="" /> denote the total number of linear extensions of <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cmathbb%7BP%7D" data-classname="equation_inline" data-title="" />. We prove that the poset probability can be evaluated as <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?P(%5Calpha%20%5Cpreceq%20%5Cbeta)%20=%20%5Cfrac%7B%20%5Csum_%7BT%20%5Cin%20B(%5Calpha,%5Cbeta)%7D%20e(T)%20e(%5Cmathbb%7BP%7D%20%5Csetminus%20(T%20%5Ccup%20%5C%7B%5Calpha%5C%7D))%7D%7Be(%5Cmathbb%7BP%7D)%7D" data-classname="equation" data-title="" /> where <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?B(%5Calpha,%5Cbeta)" data-classname="equation_inline" data-title="" /> is the set of order ideals of <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cmathbb%7BP%7D" data-classname="equation_inline" data-title="" /> without <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Calpha" data-classname="equation" data-title="" /> or <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cbeta" data-classname="equation" data-title="" />, where we can add <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Calpha" data-classname="equation_inline" data-title="" /> to get a new order ideal of <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cmathbb%7BP%7D" data-classname="equation_inline" data-title="" />. The practicality of the preceding formula is explored and we show that <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?T%20%5Cin%20B(%5Calpha,%5Cbeta)%20%5CLeftrightarrow%20%5Cleft%5C%7B%20x%20%7C%20x%20%5Cprec%20%5Calpha%20%5Cright%5C%7D%20%5Csubseteq%20T%20%5Ctext%7B%20and%20%7D%20T%20%5Ctext%7B%20order%20ideal%20of%20%7D%0A%5Cleft%5C%7B%20x%20%7C%20%5Calpha%20%5Cnot%20%5Cpreceq%20x,%5C%20%5Cbeta%20%5Cnot%20%5Cpreceq%20x%7D" data-classname="equation" /> The formula is particularly useful for certain classes of posets such as partition posets which are examined in further detail. We apply the formula to prove that, for all partition posets of shape <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Bn,n%5D" data-classname="equation_inline" data-title="" />, the probability obeys <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?P((2,a)%20%5Cpreceq%20(1,a+1))%20=%20%5Cfrac%7B%20C_a%20C_%7Bn-a%7D%7D%20%7BC_n%7D" data-classname="equation" data-title="" /> where <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?C_n" data-classname="equation_inline" data-title="" /> is the nth Catalan number and <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?a%20%3C%20n" data-classname="equation_inline" data-title="" />. We also explore how Monte Carlo methods can be used to estimate <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?P(%5Calpha%20%5Cpreceq%20%5Cbeta)" data-classname="equation_inline" data-title="" />.
|
12 |
A global optimization method for mixed integer nonlinear nonconvex problems related to power systems analysis / Une méthode d'optimisation globale pour problèmes non linéaires et non convexes avec variables mixtes (entières et continues) issus de l'analyse des réseaux électriquesWanufelle, Emilie 06 December 2007 (has links)
Abstract: This work is concerned with the development and the implementation of a global optimization method for solving nonlinear nonconvex problems with continuous or mixed integer variables, related to power systems analysis. The proposed method relaxes the problem under study into a linear outer approximation problem by using the concept of special ordered sets. The obtained problem is then successively refined by a branch-and-bound strategy. In this way, the convergence to a global optimum is guaranteed, provided the discrete variables or those appearing nonlinearly in the original problem are bounded. Our method, conceived to solve a specific kind of problem, has been developed in a general framework in such a way that it can be easily extended to solve a large class of problems. We first derive the method theoretically and next present numerical results, fixing some choices inherent to the method to make it as optimal as possible.
/
Résumé: Ce travail a pour objet la conception et l'implémentation d'une méthode d'optimisation globale pour la résolution de problèmes non linéaires et non convexes, continus ou avec variables mixtes (entières et continues), issus de l'analyse des réseaux électriques. La méthode proposée relâche le problème traité en un problème d'approximation externe linéaire en se basant sur le concept d ensembles spécialement ordonnés. Le problème obtenu est alors successivement raffiné grâce à une stratégie de branch-and-bound. La convergence vers un optimum global est ainsi assurée, pour autant que les variables discrètes ou apparaissant non linéairement dans le problème de départ soient bornées. Notre méthode, mise au point pour résoudre un type de problème bien particulier, a été conçue dans un cadre général permettant une extension aisée à la résolution d'une grande variété de problèmes. Nous développons tout d'abord la méthode théoriquement et présentons ensuite des résultats numériques dont le but est de fixer certains choix inhérents à la méthode afin de la rendre la plus optimale possible.
|
13 |
Statická analýza možných hodnot proměnných v programech v C / Static Value Analysis over C ProgramsĎuričeková, Daniela January 2013 (has links)
Value-range analysis is a static analysis technique based on arguing about the values that a variable may take on a given program point. It can be used to prove absence of run-time errors such as out-of-bound array accesses. Since value-range analysis collects information on each program point, data-flow analysis can be used in association with it. The main goal of this work is designing and implementing such a value-range analysis tool. The work begins with an introduction into the topic, an explanation of data-flow and value-range analyses and a description of abstract interpretation, which provides the formal basis of the analyser. The core of this work is the design, implementation, testing and evaluation of the analyser. In the conclusion, our personal experience obtained in the area of the thesis is mentioned, along with a discussion of a possible future development of the designed tool.
|
Page generated in 0.0578 seconds