Aujourd'hui encore, certains systèmes embarqués n'intègrent pas leur propre unité flottante, pour des contraintes de surface, de coût et de consommation d'énergie. Cependant, ce type d'architecture est largement utilisé dans des domaines d'application extrêmement exigeants en calculs flottants (le multimédia, l'audio et la vidéo ou les télécommunications). Pour compenser le fait que l'arithmétique flottante ne soit pas implantée en matériel, elle doit être émulée efficacement à travers une implantation logicielle. Cette thèse traite de la conception et de l'implantation d'un support logiciel efficace pour l'arithmétique virgule flottante IEEE 754 aux processeurs entiers embarqués. Plus spécialement, elle propose de nouveaux algorithmes et outils pour la génération efficace de programmes à la fois rapides et certifiés, permettant notamment d'obtenir des codes C de très faibles latences pour l'évaluation polynomiale en arithmétique virgule fixe. Comparés aux implantations complètement écrites à la main, ces outils permettent de réduire de manière significative le temps de développement d'opérateurs flottants. La première partie de la thèse traite de la conception d'algorithmes optimisés pour certains opérateurs flottants en base 2, et donne des détails sur leur implantation logicielle pour le format virgule flottante binary32 et pour certains processeurs VLIW entiers embarqués comme ceux de la famille ST200 de STMicroelectronics. En particulier, nous proposons ici une approche uniforme pour l'implantation correctement arrondie des racines et de leur inverse, ainsi qu'une extension à la division. Notre approche, qui repose sur l'évaluation d'un seul polynôme bivarié, permet d'exprimer un plus haut degré de parallélisme d'instruction (ILP) que les méthodes précédentes, et s'avère particulièrement efficace en pratique. Ces travaux nous ont permis de fournir une version complètement remaniée de la bibliothèque FLIP, entraînant des gains significatifs par rapport à la version précédente. La deuxième partie de la thèse présente une méthodologie pour générer automatiquement et efficacement des codes C rapides et certifiés pour l'évaluation de polynômes bivariés en arithmétique virgule fixe. En particulier, elle consiste en un ensemble d'heuristiques pour calculer des schémas d'évaluation très parallèles et de faible latence, ainsi qu'un ensemble de techniques pour vérifier si ces schémas restent efficaces sur une architecture cible réelle et suffisamment précis pour garantir l'arrondi correct de l'implantation des opérateurs sous-jacente. Cette approche a été implantée dans l'environnement logiciel CGPE (Code Generation for Polynomial Evaluation). Nous avons ainsi utilisé notre outil pour générer et certifier rapidement des parties significatives des codes de la bibliothèque FLIP.

Ce sujet s'inscrit dans la continuité des travaux commencés au sein du L2ES dans le cadre du programme ECCE en partenariat avec CREEBEL qui assure le nancement. La plateforme ECCE est un véhicule hybride électrique série à 4 roues indépendantes d'une puissance nominale en propulsion de 120kW électrique. La source d'énergie principale est constituée de deux moteurs diesels entraînant deux alternateurs. L'énergie électrique produite alimente les 4 moteurs électriques de traction et le reste est stocké dans le pack des batteries. Cette thèse développe les stratégies de couplage énergétique entre ce pack des batteries et les supercondensateurs an d'assurer au véhicule une dynamique de fourniture et du stockage de l'énergie électrique. Une étude bibliographique a permis de passer en revue le bilan technologique et les applications potentielles des supercondensateurs, puis d'élaborer le modèle simplié des supercondensateurs qui traduit dèlement le comportement des cellules durant les phases de charge et de décharge. Diérentes topologies des convertisseurs DC/DC avec des stratégies originales de gestion d'énergie électrique embarquée sont traitées. Les topologies proposées sont basées sur les convertisseurs Buck-Boost et les convertisseurs DC/AC-AC/DC à étage intermédiaire haute fréquence. Pour une raison de coût, les maquettes expérimentales des topologies ont été réalisées à l'échelle réduite ( 1/10 ). Les résultats expérimentaux obtenus ont permis de comparer les performances des topologies pour deux types de commande. La stratégie de gestion d'énergie à base des correcteurs polynomiaux (RST) est comparée à celle utilisant des correcteurs PI classiques. Ces études comparatives ont permis de choisir la meilleure topologie destinée au couplage des supercondensateurs sur le bus continu du banc ECCE.

Au cours de ce travail, une implantation de la méthode d'analyse de sensibilité d'ordre élevé a été réalisée au sein de la méthode des éléments finis (MEF). Tout d'abord nous avons posé ta base théorique des développements: la MEF classique et surtout la méthode de dérivées d'ordre élevé qui engendre les résultats sous la forme de développements de Taylor par rapport aux paramètres de conception. En s'appuyant sur la structure typique d'un code de calculs EF, nous avons développé ensuite les modules d'un calcul "paramétré": la paramétrisation géométrique, la dérivation du maillage et la résolution paramétrée. L'originalité de cette implantation consiste dans une nouvelle organisation des calculs de dérivées qui sont basés notamment sur les opérations symboliques. Pour valider des étapes de calculs, plusieurs exemples ont été présentés. Enfin, les applications possibles des résultats paramétrés sont évoquées, entre autres, une procédure pour définir le modèle analytique équivalent de dispositifs électromagnétiques a été proposée. Notons que plusieurs problèmes de réalisation informatique ont été mise en évidence et résolus, ce qui représente un gros investissement en programmation. Des nombreuses perspectives sont ouvertes par cette approche, le travail mériterait donc d'être poursuivi.

Ce travail de recherche est consacré à l'élaboration et le développement d'une nouvelle méthode d'estimation<br />et de reconstruction de signaux fortement non-stationnaires, modulés non-linéairement à la fois<br />en amplitude et en fréquence. L'estimation de tels signaux dans un contexte trés bruité est un problème<br />délicat et les méthodes existantes de la littérature présentent plusieurs inconvénients dans ce cas.<br />Nous avons montré comment une approche locale permet une meilleure adaptabilité du modèle à la<br />nature des variations locales des amplitudes et des fréquences instantanées. Les résultats de l'estimation<br />sont par conséquent améliorés. L'originalité de la méthode proposée tient à l'application de modèles paramétriques bien adaptés sur des segments temporels de courtes durées extraits du signal étudié. Nous<br />avons proposé une stratégie de segmentation puis une stratégie de fusion des segments estimés permettant<br />la reconstruction du signal dans la totalité de sa durée. L'approche proposée permet de s'affranchir d'un<br />modèle global du signal requérant un ordre d'approximation élevé.<br />La validation de l'efficacité de l'estimation a été effectuée au préalable sur un segment temporel court.<br />Le modèle considéré localement consiste en une approximation polynomiale de la fréquence et de l'amplitude<br />exprimée dans une base polynomiale discrète et orthonormale que nous avons calculée. Cette base<br />permet de réduire le couplage entre les paramètres du modèle. Nous proposons et comparons deux techniques<br />différentes pour estimer ces derniers. La première est fondée sur la maximisation de la fonction<br />de vraisemblance en utilisant la technique d'optimisation stochastique le recuit simulé. Tandis que la<br />deuxième se base sur une approche Bayésienne employant les méthodes MCMC simulées par l'algorithme<br />de Metroplois-Hastings.<br />Nous montrons, sur des simulations et également sur des signaux réels, que l'approche proposée fournit<br />de bons résultats d'estimation par comparaison à celles de la HAF.

Ces travaux portent sur l'étude de la complexité en requêtes de <br />problèmes symétriques, dans les cadres du calcul probabiliste classique <br />et du calcul quantique.<br /><br />Il est montré, dans le cas quantique, une application de la méthode de <br />bornes inférieures dite "polynomiale" au calcul de la complexité en <br />requêtes des problèmes de sous-groupes cachés abéliens, via la technique de "symétrisation".<br /><br />Dans le cas du calcul probabiliste, sous une hypothèse de "symétrie <br />transitive" des problèmes, il est donné une formule combinatoire <br />permettant de calculer la complexité en requêtes exacte du meilleur <br />algorithme non-adaptatif. De plus, il est mis en évidence que sous <br />certaines hypothèses de symétrie, ce meilleur algorithme non-adaptatif <br />est optimal même parmi les algorithmes probabilistes plus généraux, ce qui donne pour la classe de problèmes correspondante une expression exacte de la complexité en requêtes.

La complexité algorithmique est l'étude des ressources nécessaires -- le temps, la mémoire, ... -- pour résoudre un problème de manière algorithmique. Dans ce cadre, la théorie de la complexité algébrique est l'étude de la complexité algorithmique de problèmes de nature algébrique, concernant des polynômes.Dans cette thèse, nous étudions différents aspects de la complexité algébrique. D'une part, nous nous intéressons à l'expressivité des déterminants de matrices comme représentations des polynômes dans le modèle de complexité de Valiant. Nous montrons que les matrices symétriques ont la même expressivité que les matrices quelconques dès que la caractéristique du corps est différente de deux, mais que ce n'est plus le cas en caractéristique deux. Nous construisons également la représentation la plus compacte connue du permanent par un déterminant. D'autre part, nous étudions la complexité algorithmique de problèmes algébriques. Nous montrons que la détection de racines dans un système de n polynômes homogènes à n variables est NP-difficile. En lien avec la question " VP = VNP ? ", version algébrique de " P = NP ? ", nous obtenons une borne inférieure pour le calcul du permanent d'une matrice par un circuit arithmétique, et nous exhibons des liens unissant ce problème et celui du test d'identité polynomiale. Enfin nous fournissons des algorithmes efficaces pour la factorisation des polynômes lacunaires à deux variables.

Cette thèse présente une étude des systèmes dynamiques polynomiaux motivée à la fois par le grand spectre d'applications de cette classe (modèles de réactions chimiques, modèles de circuits électriques ainsi que les modèles biologiques) et par la difficulté (voire incapacité) de la résolution théorique de tels systèmes. Dans une première partie préliminaire, nous présentons les polynômes multivariés et nous introduisons les notions de forme polaire d'un polynôme (floraison) et de polynômes de Bernstein qui seront d'un grand intérêt par la suite. Dans une deuxième partie, nous considérons le problème d'optimisation polynomial dit POP. Nous décrivons dans un premier temps les principales méthodes existantes permettant de résoudre ou d'approcher la solution d'un tel problème. Puis, nous présentons deux relaxations linéaires se basant respectivement sur le principe de floraison ainsi que les polynômes de Bernstein permettant d'approcher la valeur optimale du POP. La dernière partie de la thèse sera consacrée aux applications de nos deux méthodes de relaxation dans le cadre des systèmes dynamiques polynomiaux. Une première application s'inscrit dans le cadre de l'analyse d'atteignabilité : en effet, on utilisera notre relaxation de Bernstein pour pouvoir construire un algorithme permettant d'approximer les ensembles atteignables d'un système dynamique polynomial discrétisé. Une deuxième application sera la vérification et le calcul d'invariants pour un système dynamique polynomial. Une troisième application consiste à calculer un contrôleur et un invariant pour un système dynamique polynomial soumis à des perturbations. Dans le contexte de l'invariance, on utilisera la relaxation se basant sur le principe de floraison. Enfin, une dernière application sera d'exploiter les principales propriétés de la forme polaire pour pouvoir étudier des systèmes dynamiques polynomiaux dans des rectangles.

Nous nous intéressons dans cette thèse à la problématique de la décision collective. L’objectif est de déterminer une solution de compromis pour des problèmes soumis à de multiples points de vue. Les problèmes considérés sont de nature combinatoire. Plus précisément, il s’agit de la classe des systèmes d’ensembles qui ont une structure de matroïde. La théorie des matroïdes est centrale en optimisation combinatoire, elle a permis d’unifier des structures apparemment séparées comme les arbres et les couplages dans les graphes et elle a engendré des algorithmes efficaces pour résoudre des problèmes d’optimisation non triviaux en temps polynomial. Nous nous intéressons à fournir des algorithmes d’approximation polynomiaux centralisés et décentralisés avec garantie de performance pour déterminer une solution de compromis qui est une base du matroïde. La solution de compromis doit également être équitable pour tous les membres de la collectivité. Nous portons un intérêt particulier au problème de partage équitable de biens indivisibles qui est une thématique importante en choix social computationnel et dont le problème se modélise par les matroïdes. / In this thesis, we are interested in collective decision-making. The objective is to find a tradeoff solution for problems that are evaluated by multiple points of view. We consider problems having a matroid structure. Matroid theory is significant in combinatorial optimization, it helped to unify apparently separated structures like forests and matchings in graphs and it includes efficient algorithms for solving non-trivial optimization problems in polynomial time. We are interested to provide polynomial time centralized and decentralized approximation algorithms for finding a tradeoff solution which is a base of the matroid. The tradeoff solution must also be fair for all the members of the community. We are particularly interested in the issue of the fair division of indivisible goods which is central in computational social choice and that can be modeled by matroids.

Les gestionnaires des réseaux de transport d'électricité doivent adapter leurs outils d'aide à la décision aux avancées technologiques du XXIième siècle. Une opération sous-jacente à beaucoup d'outils est de calculer les flux en actif/réactif qui minimisent les pertes ou les coûts de production. Mathématiquement, il s'agit d'un problème d'optimisation qui peut être décrit en utilisant seulement l'addition et la multiplication de nombres complexes. L'objectif de cette thèse est de trouver des solutions globales. Un des aboutissements de ce projet doctoral hautement collaboratif est d'utiliser des résultats récents en géométrie algébrique pour calculer des flux optimaux dans le réseau Européen à haute tension. / Transmission system operators need to adapt their decision-making tools to the technological evolutions of the twenty first century. A computation inherent to most tools seeks to find alternating-current power flows that minimize power loss or generation cost. Mathematically, it consists in an optimization problem that can be described using only addition and multiplication of complex numbers. The objective of this thesis is to find global solutions, in other words the best solutions to the problem. One of the outcomes of this highly collaborative doctoral project is to use recent results from algebraic geometry to compute globally optimal power flows in the European high-voltage transmission network.

La thèse est portée essentiellement sur la stabilisation indirecte d’un système de deux équations des ondes couplées et sur la stabilisation frontière de poutre de Rayleigh.Dans le cas de la stabilisation d’un système d’équations d’onde couplées, le contrôle est introduit dans le système directement sur le bord du domaine d’une seule équation dans le cas d’un domaine borne ou à l’intérieur d’une seule équation mais dans le cas d’un domaine non borné. La nature du système ainsi couplé dépend du couplage des équations et de la nature arithmétique des vitesses de propagations, et ceci donne divers résultats pour la stabilisation polynomiale ainsi la non stabilité.Dans le cas de la stabilisation de poutre de Rayleigh, l’équation est considérée avec un seul contrôle force agissant sur bord du domaine. D’abord, moyennant le développement asymptotique des valeurs propres et des vecteurs propres du système non contrôlé, un résultat d’observabilité ainsi qu’un résultat de bornétude de la fonction de transfert correspondant sont obtenus. Alors, un taux de décroissance polynomial de l’énergie du système est établi. Ensuite, moyennant une étude spectrale combinée avec une méthode fréquentielle, l’optimalité du taux obtenu est assurée. / The thesis is driven mainly on indirect stabilization system of two coupled wave equations and the boundary stabilization of Rayleigh beam equation. In the case of stabilization of a coupled wave equations, the Control is introduced into the system directly on the edge of the field of a single equation in the case of a bounded domain or inside a single equation but in the case of an unbounded domain. The nature of thus coupled system depends on the coupling equations and arithmetic Nature of speeds of propagation, and this gives different results for the polynomial stability and the instability. In the case of stabilization of Rayleigh beam equation, we consider an equation with one control force acting on the edge of the area. First, using the asymptotic expansion of the eigenvalues and vectors of the uncontrolled system an observability result and a result of boundedness of the transfer function are obtained. Then a polynomial decay rate of the energy of the system is established. Then through a spectral study combined with a frequency method, optimality of the rate obtained is assured.