No description available.

Les systèmes critiques comme les commandes de vol peuvent entraîner des désastres en cas de dysfonctionnement. D'où l'intérêt porté à la fois par le monde industriel et académique aux méthodes de preuve formelle capable d'apporter, plus ou moins automatiquement, une preuve mathématique de correction. Parmi elles, cette thèse s'intéresse particulièrement à l'interprétation abstraite, une méthode efficacepour générer automatiquement des preuves de propriétés numériques qui sont essentielles dans notre contexte.Il est bien connu des automaticiens que les contrôleurs linéaires sont stables si et seulement si ils admettent un invariant quadratique(un ellipsoïde, d'un point de vue géométrique). Ils les appellent fonction de Lyapunov quadratique et une première partie propose d'encalculer automatiquement pour des contrôleurs donnés comme paire de matrices. Ceci est réalisé en utilisant des outils de programmation semi-définie. Les aspects virgule flottante sont pris en compte, que ce soit dans les calculs effectués par le programme analysé ou dans les outils utilisés pour l'analyse. Toutefois, le véritable but est d'analyser des programmes implémentant des contrôleurs (et non des paires de matrices), incluant éventuellement des réinitialisation ou des saturations, donc non purement linéaires. L'itération sur les stratégies est une techniqued'analyse statique récemment développée et bien adaptée à nos besoins. Toutefois, elle ne se marrie pas facilement avec lestechniques classiques d'interprétation abstraite. La partie suivante propose une interface entre les deux mondes.Enfin, la dernière partie est un travail plus préliminaire sur l'usage de l'optimisation globale sur des polynômes basée sur les polynômes deBernstein pour calculer des invariants polynomiaux sur des programmes polynomiaux. / Critical Systems such as flight commands may have disastrous results in case of failure. Hence the interest of both the industrial and theacademic communities in formal methods able to more or less automatically deliver mathematical proof of correctness. Among them, this thesis will particularly focus on abstract interpretation, an efficient method to automatically generate proofs of numerical properties which are essential in our context.It is well known from control theorists that linear controllers are stable if and only if they admit a quadratic invariant (geometrically speaking, an ellipsoid). They call these invariants quadratic Lyapunov functions and a first part offers to automatically compute such invariants for controllers given as a pair of matrices. This is done using semi-definite programming optimization tools. It is worth noting that floating point aspects are taken care of, whether they affectcomputations performed by the analyzed program or by the tools used for the analysis.However, the actual goal is to analyze programs implementing controllers (and not pairs of matrices), potentially including resets or saturations, hence not purely linears. The policy iteration technique is a recently developed static analysis techniques well suited to that purpose. However, it does not marry very easily with the classic abstract interpretation paradigm. The next part tries to offer a nice interface between the two worlds.Finally, the last part is a more prospective work on the use of polynomial global optimization based on Bernstein polynomials to compute polynomial invariants on polynomials systems.

La géométrie algébrique réelle est dans sa définition la plus simple, l'étude des ensembles de solutions d'un système d'équations polynomiales à coefficients réelles. Dans cette vaste thématique, on se concentre sur les intersections de quadriques où déjà le cas de trois quadriques reste largement ouvert. Notre sujet peut être résumé comme l'étude topologique des variétés algébriques réelles et l'interaction entre leur topologie d'une part et leur déformations et dégénérations d'autre part, un problème issu du 16ième problème de Hilbert et enrichi par des développements récents. Au cours de cette thèse, nous allons nous focaliser sur les intersections maximales de quadriques réelles et en particulier démonter l'existence de telles intersections en utilisant des développements issus des recherches effectuées depuis la fin des années 80. Dans le cas d'intersections de trois quadriques, nous allons mettre en évidence le lien très étroits entre ces intersections d'une part et les courbes planes d'autre part, et démontrer que l'étude des M-courbes (une des problématiques du 16ième problème de Hilbert) peut se faire à travers l'étude des intersections maximales. Nous utiliserons ensuite les résultats sur les courbes planes nodales afin de déterminer dans certains cas les classes de déformations d'intersections de trois quadriques réelles. / Real algebraic geometry is in its simplest definition, the study of sets of solutions of a system of polynomial equations with real coefficients. In this theme, we focus on the intersections of quadrics where already the case of three quadrics remains wide open. Our subject can be summarized as the topological study of real algebraic varieties and interaction between their topology on the one hand and their deformations and degenerations on the other hand, a problem coming from the 16th Hilbert problem and enriched by recent developments. In this thesis, we will focus on maximum intersections of real quadrics and particularly prove the existence of such intersections using research developments made since the late 80. In the case of intersections of three quadrics, we will point the very close link between the intersections on the one hand and on the other plane curves, and show that the study of M-curves (one of the problems of the 16th Hilbert problem) may be done through the study of maximum intersections. Next, we will use the study on nodal plane curves to determine in some cases deformation classes of intersections of three real quadrics.

Nous introduisons les notions de forêts préordonnées et préordonnées en tas, généralisant les constructions des forêts ordonnées et ordonnées en tas. On démontre que les algèbres des forêts préordonnées et préordonnées en tas sont des algèbres de Hopf pour le coproduit de coupes et on construit un morphisme d'algèbres de Hopf dans l'algèbre des mots tassés. Ensuite, nous définissons un autre coproduit sur les forêts préordonnées donné par la contraction d'arêtes et nous donnons une description combinatoire de morphismes définis sur des algèbres de Hopf de forêts et à valeurs dans les algèbres de Hopf de battages et de battages contractants. Par ailleurs, nous introduisons la notion d'algèbre bigreffe, généralisant les notions d'algèbres de greffes à gauche et à droite. Nous décrivons l'algèbre bigreffe libre engendrée par un générateur et nous munissons cette algèbre d'une structure d'algèbre de Hopf et d'un couplage. Nous étudions ensuite le dual de Koszul de l'operade bigreffe et nous donnons une description combinatoire de l'algèbre bigreffe dual engendrée par un générateur. A l'aide d'une méthode de réécriture, nous prouvons que l'opérade bigreffe est Koszul. Nous définissons la notion de bialgèbre bigreffe infinitésimale et nous prouvons un analogue des théorèmes de Poincaré-Birkhoff-Witt et de Cartier-Milnor-Moore pour les bialgèbres bigreffe infinitésimales connexes. Pour finir, à partir de deux opérateurs de greffes, nous construisons des algèbres de Hopf d'arbres enracinés et ordonnés $ mathbf{B}^{i} $, $ i in mathbb{N}^{ast} $, $ mathbf{B}^{infty} $ et $ mathbf{B} $ vérifiant les relations d'inclusions $ mathbf{B}^{1} subseteq hdots mathbf{B}^{i} subseteq mathbf{B}^{i+1} subseteq hdots subseteq mathbf{B}^{infty} subseteq mathbf{B} $. On munit $ mathbf{B} $ d'une structure de bialgèbre dupliciale dendriforme et on en déduit que $ mathbf{B} $ est colibre et auto-duale. Nous démontrons que $ mathbf{B} $ est engendrée comme algèbre bigreffe par un générateur. / We introduce the notions of preordered and heap-preordered forests, generalizing the construction of ordered and heap-ordered forests. We prove that the algebras of preordered and heap-preordered forests are Hopf for the cut coproduct, and we construct a Hopf morphism to the Hopf algebra of packed words. In addition, we define another coproduct on the preordered forests given by the contraction of edges, and we give a combinatorial description of morphims defined on Hopf algebras of forests with values in the Hopf algebras of shuffes or quasi-shuffles. Moreover, we introduce the notion of bigraft algebra, generalizing the notions of left and right graft algebras. We describe the free bigraft algebra generated by one generator and we endow this algebra with a Hopf algebra structure, and a pairing. Next, we study the Koszul dual of the bigraft operad and we give a combinatorial description of the free dual bigraft algebra generated by one generator. With the help of a rewriting method, we prove that the bigraft operad is Koszul. We define the notion of infinitesimal bigraft bialgebra and we prove an analogue of Poincaré-Birkhoff-Witt and Cartier-Milnor-Moore theorems for connected infinitesimal bigraft bialgebras. Finally, with two grafting operators, we construct Hopf algebras of rooted and ordered trees $ mathbf{B}^{i} $, $ i in mathbb{N}^{ast} $, $ mathbf{B}^{infty} $ and $ mathbf{B} $ satisfying the inclusion relations $ mathbf{B}^{1} subseteq hdots mathbf{B}^{i} subseteq mathbf{B}^{i+1} subseteq hdots subseteq mathbf{B}^{infty} subseteq mathbf{B} $. We endow $ mathbf{B} $ with a structure of duplicial dendriform bialgebra and we deduce that $ mathbf{B} $ is cofree and self-dual. We prove that $ mathbf{B} $ is generated as bigraft algebra by one generator.

Les espaces d'ordres abstraits sont introduits par M. Marshall dans les années 70, dans la perspective d'offrir un cadre abstrait à l'étude des formes quadratiques. Vers le début des années 90, les travaux de M. Dickmann, L. de Lima et de F. Miraglia, ont donné naissance à la version duale des groupes spéciaux. Le premier thème que nous traiterons est la caractérisation des points d'un espace d'ordres du corps de fonctions d'une variété réelle, nous reprendrons un résultat de Brumfiel affirmant l'existence d'une correspondance entre ces ordres et des ultrafiltres de semi-algébriques. Nous appliquerons ceci au corps R(x,y). Suivra la caractérisation des ordres de ce corps à travers la notion de demi-branche de Bézout. Le second thème traite des principes locaux-globaux généralisés (ou Conjecture pp). Le premier résultat de la thèse porte sur la séparation des constructibles et sur la principalité des basiques. Nous montrerons que le langage des groupes spéciaux nous offre une vision claire du fait que ces principes découlent trivialement du principe de l'isotropie étendu. Le second résultat traite des contre-exemples à la conjecture dans le cas de la conique rationnelle donnée par l'équation x2+y2=3. Le dernier résultat (le plus important), aborde la conjecture pp dans le cadre du corps R(x,y). Nous nous intéresserons à des familles de polynômes vérifiant certaines conditions géométriques et montrerons que toute formule pp, ayant ses paramètres dans cette famille, vérifie un principe local-global. Nous les baptiserons formules V-universelles. Nous clorons le dernier chapitre par deux méthodes de construction. / Spaces of orderings were introduced in the last of 70s by M. Marshall, in order to provide an abstract framework to the study of a generalized theory of quadratic forms. In the 90s, the work of M. Dickmann , joined by his student L. Lima and his collaborator F. Miraglia , gave rise to the dual version of this theory, the special groups. First, we focus on the characterization of points of a space of orderings in special the case of function fields of real varieties, we review a Brumfiel?s result proving the existence of a one-to-one correspondence between points of such a space and some family of ultrafilters of semi-algebraic sets of the variety. We apply this to the case where the field is R(x,y). Another characterization uses the concept of Bezout?s half-branch. The second topic deals with a generalized local-global principle, known as the pp-conjecture. The first new result of this thesis focuses on the separation of constructibles and the principality of basics. We show that the first order language traduces well these properties and offers a clear vision that they derive trivially from extended isotropy theorem. The second result presents a generalized counter-example to the pp-conjecture in the case of the rational conic defined by the equation x2 + y2 = 3. The last result (most important), addresses the pp-conjecture in the context of the space of orderings of the field R(x,y). We will focus on families of polynomials satisfying certain geometric conditions and show that any pp-formula, with its parameters in this family, verifies a local-global principle. We baptize them V-universal formulas. We close the last chapter by two construction methods.

Ce mémoire s'emploie à étudier les corps quadratiques réels ainsi qu'un élément particulier de tels corps quadratiques réels : l'unité fondamentale. Pour ce faire, le mémoire commence par présenter le plus clairement possible les connaissances sur différents sujets qui sont essentiels à la compréhension des calculs et des résultats de ma recherche. On introduit d'abord les corps quadratiques ainsi que l'anneau de ses entiers algébriques et on décrit ses unités. On parle ensuite des fractions continues puisqu'elles se retrouvent dans un algorithme de calcul de l'unité fondamentale. On traite ensuite des formes binaires quadratiques et de la formule du nombre de classes de Dirichlet, laquelle fait intervenir l'unité fondamentale en fonction d'autres variables. Une fois cette tâche accomplie, on présente nos calculs et nos résultats. Notre recherche concerne la répartition des unités fondamentales des corps quadratiques réels, la répartition des unités des corps quadratiques réels et les moments du logarithme de l'unité fondamentale. (Le logarithme de l'unité fondamentale est appelé le régulateur.) / This memoir aims to study real quadratic fields and a particular element of such real quadratic fields : the fundamental unit. To achieve this, the memoir begins by presenting as clearly as possible the state of knowledge on different subjects that are essential to understand the computations and results of my research. We first introduce quadratic fields and their rings of algebraic integers, and we describe their units. We then talk about continued fractions because they are present in an algorithm to compute the fundamental unit. Afterwards, we proceed with binary quadratic forms and Dirichlet's class number formula, which involves the fundamental unit as a function of other variables. Once the above tasks are done, we present our calculations and results. Our research concerns the distribution of fundamental units in real quadratic fields, the disbribution of units in real quadratic fields and the moments of the logarithm of the fundamental unit. (The logarithm of the fundamental unit is called the regulator.)

Ce mémoire s'emploie à étudier les corps quadratiques réels ainsi qu'un élément particulier de tels corps quadratiques réels : l'unité fondamentale. Pour ce faire, le mémoire commence par présenter le plus clairement possible les connaissances sur différents sujets qui sont essentiels à la compréhension des calculs et des résultats de ma recherche. On introduit d'abord les corps quadratiques ainsi que l'anneau de ses entiers algébriques et on décrit ses unités. On parle ensuite des fractions continues puisqu'elles se retrouvent dans un algorithme de calcul de l'unité fondamentale. On traite ensuite des formes binaires quadratiques et de la formule du nombre de classes de Dirichlet, laquelle fait intervenir l'unité fondamentale en fonction d'autres variables. Une fois cette tâche accomplie, on présente nos calculs et nos résultats. Notre recherche concerne la répartition des unités fondamentales des corps quadratiques réels, la répartition des unités des corps quadratiques réels et les moments du logarithme de l'unité fondamentale. (Le logarithme de l'unité fondamentale est appelé le régulateur.) / This memoir aims to study real quadratic fields and a particular element of such real quadratic fields : the fundamental unit. To achieve this, the memoir begins by presenting as clearly as possible the state of knowledge on different subjects that are essential to understand the computations and results of my research. We first introduce quadratic fields and their rings of algebraic integers, and we describe their units. We then talk about continued fractions because they are present in an algorithm to compute the fundamental unit. Afterwards, we proceed with binary quadratic forms and Dirichlet's class number formula, which involves the fundamental unit as a function of other variables. Once the above tasks are done, we present our calculations and results. Our research concerns the distribution of fundamental units in real quadratic fields, the disbribution of units in real quadratic fields and the moments of the logarithm of the fundamental unit. (The logarithm of the fundamental unit is called the regulator.)

Lorsqu’on fait face à des systèmes non linéaires, les notions classiques de stabilité ne suffisent pas à garantir un comportement approprié vis-à-vis de problématiques telles que le suivi de trajectoires, la synchronisation et la conception d’observateurs. La stabilité incrémentale a été proposée en tant qu’outil permettant de traiter de tels problèmes et de garantir que le système présente des comportements qualitatifs pertinents. Cependant, comme c’est souvent le cas avec les systèmes non linéaires, la complexité de l’analyse conduit les ingénieurs à rechercher des relaxations, ce qui introduit du conservatisme. Dans cette thèse, nous nous intéressons à la stabilité incrémentale d’une classe spécifique de systèmes, à savoir les systèmes affines par morceaux, qui pourraient fournir un outil avantageux pour aborder la stabilité incrémentale de systèmes dynamiques plus génériques.Les systèmes affines par morceaux ont un espace d’états partitionné, et sa dynamique dans chaque région est régie par une équation différentielle affine. Ils peuvent représenter des systèmes contenant des non linéarités affines par morceaux, ainsi que servir comme des approximations de systèmes non linéaires plus génériques. Ce qui est plus important, leur description est relativement proche de celle des systèmes linéaires, ce qui permet d’obtenir des conditions d’analyse exprimées comme des inégalités matricielles linéaires qui peuvent être traités numériquement de façon efficace par des solveurs existants.Dans la première partie de ce document de thèse, nous passons en revue la littérature sur l’analyse des systèmes affines par morceaux en utilisant des techniques de Lyapunov et la dissipativité. Nous proposons ensuite de nouvelles conditions pour l’analyse du gain L2 incrémental et la stabilité asymptotique incrémentale des systèmes affines par morceaux exprimés en tant qu’inégalités matricielles linéaires. Ces conditions sont montrées être moins conservatives que les résultats précédents et sont illustrées par des exemples numériques.Dans la deuxième partie, nous considérons le cas des systèmes affines par morceaux incertains représentés comme l’interconnexion entre un système nominal et un bloc d’incertitude structuré. En utilisant la théorie de la séparation des graphes, nous proposons des conditions qui étendent le cadre des contraintes quadratiques intégrales afin de considérer le cas où le système nominal est affine par morceaux, à la fois dans les cas non incrémental et incrémental. Via la théorie de la dissipativité, ces conditions sont ensuite exprimées en tant qu’inégalités matricielles linéaires.Finalement, la troisième partie de ce document de thèse est consacrée à l’analyse de systèmes non linéaires de Lur’e incertains. Nous développons une nouvelle technique d’approximation permettant de réécrire ces systèmes de façon équivalente comme des systèmes affines par morceaux incertains connectés avec l’erreur d’approximation. L’approche proposée garantit que l’erreur d’approximation est Lipschitz continue avec la garantie d’une borne supérieure prédéterminée sur la constante de Lipschitz. Cela nous permet d’utiliser les techniques susmentionnées pour analyser des classes plus génériques de systèmes non linéaires. / When dealing with nonlinear systems, regular notions of stability are not enough to ensure an appropriate behavior when dealing with problems such as tracking, synchronization and observer design. Incremental stability has been proposed as a tool to deal with such problems and ensure that the system presents relevant qualitative behavior. However, as it is often the case with nonlinear systems, the complexity of the analysis leads engineers to search for relaxations, which introduce conservatism. In this thesis, we focus on the incremental stability of a specific class of systems, namely piecewise-affine systems, which could provide a valuable tool for approaching the incremental stability of more general dynamical systems.Piecewise-affine systems have a partitioned state space, in each region of which the dynamics are governed by an affine differential equation. They can represent systems containing piecewise-affine nonlinearities, as well as serve as approximations of more general nonlinear systems. More importantly, their description is relatively close to that of linear systems, allowing us to obtain analysis conditions expressed as linear matrix inequalities that can be efficiently handled numerically by existing solvers.In the first part of this memoir, we review the literature on the analysis of piecewise-affine systems using Lyapunov and dissipativity techniques. We then propose new conditions for the analysis of incremental L2-gain and incremental asymptotic stability of piecewise-affine systems expressed as linear matrix inequalities. These conditions are shown to be less conservative than previous results and illustrated through numerical examples.In the second part, we consider the case of uncertain piecewise-affine systems represented as the interconnection between a nominal system and a structured uncertainty block. Using graph separation theory, we propose conditions that extend the framework of integral quadratic constraints to consider the case when the nominal system is piecewise affine, both in the non-incremental and incremental cases. Through dissipativity theory, these conditions are then expressed as linear matrix inequalities.Finally, the third part of this memoir is devoted to the analysis of uncertain Lur’e-type nonlinear systems. We develop a new approximation technique allowing to equivalently rewrite such systems as uncertain piecewise-affine systems connected with the approximation error. The proposed approach ensures that the approximation error is Lipschitz continuous with a guaranteed pre-specified upper bound on the Lipschitz constant. This enables us to use the aforementioned techniques to analyze more general classes of nonlinear systems.

Le projet HODISS dans le cadre duquel s'effectue nos travaux adresse la problématique de la synchronisation globale des systèmes complexes sur puce (System-on-Chip ou SOCs, par exemple un multiprocesseur monolithique). Les approches classiques de distribution d'horloges étant devenues de plus en plus obsolètes à cause de l'augmentation de la fréquence d'horloge, l'accroissement des temps de propagation, l'accroissement de la complexité des circuits et les incertitudes de fabrication, les concepteurs s’intéressent (pour contourner ces difficultés) à d'autres techniques basées entre autres sur les oscillateurs distribués. La difficulté majeure de cette dernière approche réside dans la capacité d’assurer le synchronisme global du système. Nous proposons un système d'horlogerie distribuée basé sur un réseau d’oscillateurs couplés en phase. Pour synchroniser ces oscillateurs, chacun d'eux est en fait une boucle à verrouillage de phase qui permet ainsi d'assurer un couplage en phase avec les oscillateurs des zones voisines. Nous analysons la stabilité de l'état synchrone dans des réseaux cartésiens identiques de boucles à verrouillage de phase entièrement numériques (ADPLLs). Sous certaines conditions, on montre que l'ensemble du réseau peut synchroniser à la fois en phase et en fréquence. Un aspect majeur de cette étude réside dans le fait que, en l'absence d'une horloge de référence absolue, le filtre de boucle dans chaque ADPLL est piloté par les fronts montants irréguliers de l'oscillateur local et, par conséquent, n'est pas régi par les mêmes équations d'état selon que l'horloge locale est avancée ou retardée par rapport au signal considéré comme référence. Sous des hypothèses simples, ces réseaux d'ADPLLs dits "auto-échantillonnés" peuvent être décrits comme des systèmes linéaires par morceaux dont la stabilité est notoirement difficile à établir. L'une des principales contributions que nous présentons est la définition de règles de conception simples qui doivent être satisfaites sur les coefficients de chaque filtre de boucle afin d'obtenir une synchronisation dans un réseau cartésien de taille quelconque. Les simulations transitoires indiquent que cette condition nécessaire de synchronisation peut également être suffisante pour une classe particulière d'ADPLLs "auto-échantillonnés". / The HODISS project, context in which this work is achieved, addresses the problem of global synchronization of complex systems-on-chip (SOCs, such as a monolithic multiprocessor). Since the traditional approaches of clock distribution are less used due to the increase of the clock frequency, increased delay, increased circuit complexity and uncertainties of manufacture, designers are interested (to circumvent these difficulties) to other techniques based among others on distributed synchronous clocks. The main difficulty of this latter approach is the ability to ensure the overall system synchronization. We propose a clock distribution system based on a network of phase-coupled oscillators. To synchronize these oscillators, each is in fact a phase-locked loop which allows to ensure a phase coupling with the nearest neighboring oscillators. We analyze the stability of the synchronized state in Cartesian networks of identical all-digital phase-locked loops (ADPLLs). Under certain conditions, we show that the entire network may synchronize both in phase and frequency. A key aspect of this study lies in the fact that, in the absence of an absolute reference clock, the loop-filter in each ADPLL is operated on the irregular rising edges of the local oscillator and consequently, does not use the same operands depending on whether the local clock is leading or lagging with respect to the signal considered as reference. Under simple assumptions, these networks of so-called “self-sampled” all-digital phase-locked-loops (SS-ADPLLs) can be described as piecewise-linear systems, the stability of which is notoriously difficult to establish. One of the main contributions presented here is the definition of simple design rules that must be satisfied by the coefficients of each loop-filter in order to achieve synchronization in a Cartesian network of arbitrary size. Transient simulations indicate that this necessary synchronization condition may also be sufficient for a specific class of SS-ADPLLs.

L'UWB (Ultra Wide Band) consiste à transmettre des signaux entre 3.1 et 10.6 GHz avec une puissance limitée à -41.3 dBm/MHz. Pour les communications hauts débits (100 à 500 Mbit/s) et courtes portées (1 à 10 m), les solutions de l'état de l'art reposent sur des traitements numériques complexes. Mitsubishi ITE propose une solution alternative multi-bandes (MB) impulsionnelle basée sur un récepteur non-cohérent. La démodulation OOK est effectuée par une détection d'énergie originale avec un seuillage adapté dynamiquement suivant les conditions de propagation. La parallélisation complète de ce système MB-OOK permet à la fois d'éviter les interférences inter-symboles et de récupérer la quasi totalité de l'énergie disponible. En outre, l'approche impulsionnelle limite les évanouissements du signal sur canal multi-trajets. La comparaison des systèmes MB-OOK et MB-OFDM démontre la pertinence de la solution proposée pour des applications très hauts débits, courte portée et faible consommation.