Nous nous intéressons dans cette thèse à des problèmes d'optimisation liés au domaine des réseaux. Ces problèmes sont d'une part des problèmes d'optimisation ``classiques'' dans lesquels nous cherchons à pallier la NP-difficulté d'un problème en proposant des algorithmes approchés, le plus souvent avec garantie de performance. D'autre part, nous avons considéré des problèmes dans lesquels les utisateurs du réseau sont indépendants et individualistes. Chaque utilisateur souhaite alors optimiser sa propre fonction objectif, qui peut être très différente de la fonction objectif globale que, en tant que concepteurs d'un protocole, nous souhaitons optimiser. Nous nous plaçons alors dans le cadre de la théorie des jeux algorithmique et cherchons à optimiser cette fonction objectif globale en prenant en compte des contraintes supplémentaires dues au fait que les utilisateurs se comportent de façon individualiste. Les problémes que nous avons considérés sont des problémes d'ordonnancement et de routage.

Dans un graphe orienté contenant un nœud appelé racine, un sous ensemble de nœuds appelés terminaux et une pondération sur les arcs, le problème de l’arborescence de Steiner (DST) consiste en la recherche d’une arborescence de poids minimum contenant pour chaque terminal un chemin de la racine vers ce terminal. Ce problème est NP-Complet. Cette thèse se penche sur l’étude de l’approximabilité de ce problème. Sauf si P=NP, il n’existe pas pour ce problème d’approximation de rapport constant ou logarithmique en k, oú k est le nombre de terminaux. Le plus petit rapport d’approximation connu est O (k") où " est un réel strictement positif. Dans la première partie, nous donnons trois algorithmes d’approximation : un algorithme glouton efficace qui associe deux techniques d’approximations connues pour DST, un algorithme dans le cas des graphes structurés en paliers qui étudie l’approximabilité du problème quand les terminaux sont éloignés de la racine, et un algorithme exponentiel qui combine un algorithme d’approximation et un algorithme exact, dont le rapport d’approximation et la complexité temporelle sont paramétrés par le nombre de terminaux couverts par l’algorithme exact. Dans la seconde partie, nous étudions deux problèmes issus de DST auquel est ajoutée une contrainte sur les nœuds de branchement. Cette contrainte réduit le nombre de solutions réalisables et peut faciliter la recherche d’une solution optimale parmi ce sous-ensemble de solutions. En fonction de la contrainte, nous étudions la possibilité de la trouver en temps polynomial et quel est le rapport d’approximation entre cette solution et la solution du problème non contraint / The directed Steiner tree problem (DST) asks, considering a directed weighted graph, a node r called root and a set of nodes X called terminals, for a minimum cost directed tree rooted in r spanning X. DST is an NP-complete problem. We are interested in the search for polynomial approximations for DST. Unless P = NP, DST can not be approximated neither within a constant ratio nor a logarithmic ratio with respected to k, where k is the number of terminals. The smallest known approximation ratio is O(kԑ)$ where ԑ is a positive real.In the first part, we provide three new approximation algorithms : a practical greedy algorithm merging two of the main approximation techniques for DST, an algorithm for the case where the graph is layered and where the distance between the terminals and the root is high, and an exponential approximation algorithm combining an approximation algorithm and an exact algorithm, parameterized with the number of terminals the exact algorithm must cover.In the last part we study DST with two branching constraints. With this technique, we are able to reduce the number of feasible solutions, and possibly facilitate the search for an optimal solution of the constraint problem. We study how it is possible to build such a solution in polynomial time and if this solution is a good approximation of an optimal solution of the non-constraint problem

L'objectif de ce travail de thèse est le développement d'une approximation polynomiale axiale dans un solveur basé sur la Méthode des Caractéristiques. Le contexte, est celui de la solution stationnaire de l'équation de transport des neutrons pour des systèmes critiques, et l'implémentation pratique a été réalisée dans le solveur "Two/three Dimensional Transport" (TDT), faisant partie du projet APOLLO3®. Un solveur MOC pour des géométries en trois dimensions a été implémenté dans ce code pendant un projet de thèse antécédent, se basant sur une approximation constante par morceaux du flux et des sources des neutrons. Les développements présentés dans la suite représentent la continuation naturelle de ce travail. Les solveurs MOC en trois dimensions sont capables de produire des résultats précis pour des géométries complexes. Bien que précis, le coût computationnel associé à ce type de solveur est très important. Une représentation polynomiale en direction axiale du flux angulaire des neutrons a été utilisée pour réduire ce coût computationnel.Le travail réalisé pendant cette thèse peut être considéré comme divisé en trois parties: transport, accélération et autres. La première partie est constituée par l'implémentation de l'approximation polynomiale choisie dans les équations de transmission et de bilan typiques de la Méthode des Caractéristiques. Cette partie a aussi été caractérisée par le calcul d'une série de coefficients numériques qui se sont révélés nécessaires afin d'obtenir un algorithme stable. Pendant la deuxième partie, on a modifié et implémenté la solution des équations de la méthode d'accélération DPN. Cette méthode était déjà utilisée pour l'accélération et des itérations internes et externes dans TDT pour les solveurs deux et trois dimensionnels avec l'approximation des flux plat, quand ce travail a commencé. L'introduction d'une approximation polynomiale a demandé plusieurs développements numériques regardant la méthode d'accélération. Dans la dernière partie de ce travail on a recherché des solutions pour un mélange de différents problèmes liés aux premières deux parties. En premier lieux, on a eu à faire avec des instabilités numériques associées à une discrétisation spatiale ou angulaire pas suffisamment précise, soit pour la partie transport que pour la partie d'accélération. Ensuite, on a essayé d'utiliser différentes méthodes pour réduire l'empreinte mémoire des coefficients d'accélération. L'approche qu'on a finalement choisie se base sur une régression non-linéaire au sens des moindres carrés de la dépendance en fonction des sections efficaces typique de ces coefficients. L'approche standard consiste dans le stockage d'une série de coefficients pour chaque groupe d'énergie. La méthode de régression permet de remplacer cette information avec une série de coefficients calculés pendant la régression qui sont utilisés pour reconstruire les matrices d'accélération au cours des itérations. Cette procédure ajoute un certain coût computationnel à la méthode, mais nous pensons que la réduction de la mémoire rende ce surcoût acceptable.En conclusion, le travail réalisé a été concentré sur l'application d'une simple approximation polynomiale avec l'objectif de réduire le coût computationnel et l'empreinte mémoire associées à un solveur basée sur la Méthodes des Caractéristiques qui est utilisé pour calculer le flux neutroniques pour des géométries à trois dimensions extrudées. Même si cela ne constitue pas une amélioration radicale des performances, l'approximation d'ordre supérieur qu'on a introduit permet une réduction en termes de mémoire et de temps de calcul d'un facteur compris entre 2 et 5, selon le cas. Nous pensons que ces résultats constitueront une base fertile pour des futures améliorations. / The purpose of this PhD is the implementation of an axial polynomial approximation in a three-dimensional Method Of Characteristics (MOC) based solver. The context of the work is the solution of the steady state Neutron Transport Equation for critical systems, and the practical implementation has been realized in the Two/three Dimensional Transport (TDT) solver, as a part of the APOLLO3® project. A three-dimensional MOC solver for 3D extruded geometries has been implemented in this code during a previous PhD project, relying on a piecewise constant approximation for the neutrons fluxes and sources. The developments presented in the following represent the natural continuation of this work. Three-dimensional neutron transport MOC solvers are able to produce accurate results for complex geometries. However accurate, the computational cost associated to this kind of solvers is very important. An axial polynomial representation of the neutron angular fluxes has been used to lighten this computational burden.The work realized during this PhD can be considered divided in three major parts: transport, acceleration and others. The first part is constituted by the implementation of the chosen polynomial approximation in the transmission and balance equations typical of the Method Of Characteristics. This part was also characterized by the computation of a set of numerical coefficients which revealed to be necessary in order to obtain a stable algorithm. During the second part, we modified and implemented the solution of the equations of the DPN synthetic acceleration. This method was already used for the acceleration of both inners and outers iteration in TDT for the two and three dimensional solvers at the beginning of this work. The introduction of a polynomial approximation required several equations manipulations and associated numerical developments. In the last part of this work we have looked for the solutions of a mixture of different issues associated to the first two parts. Firstly, we had to deal with some numerical instabilities associated to a poor numerical spatial or angular discretization, both for the transport and for the acceleration methods. Secondly, we tried different methods to reduce the memory footprint of the acceleration coefficients. The approach that we have eventually chosen relies on a non-linear least square fitting of the cross sections dependence of such coefficients. The default approach consists in storing one set of coefficients per each energy group. The fit method allows replacing this information with a set of coefficients computed during the regression procedure that are used to re-construct the acceleration matrices on-the-fly. This procedure of course adds some computational cost to the method, but we believe that the reduction in terms of memory makes it worth it.In conclusion, the work realized has focused on applying a simple polynomial approximation in order to reduce the computational cost and memory footprint associated to a Method Of Characteristics solver used to compute the neutron fluxes in three dimensional extruded geometries. Even if this does not a constitute a radical improvement, the high order approximation that we have introduced allows a reduction in terms of memory and computational times of a factor between 2 and 5, depending on the case. We think that these results will constitute a fertile base for further improvements.

L'arithmétique des ordinateurs est une branche de l'informatique qui traite des systèmes de représentation des nombres, des algorithmes arithmétiques et de leurs implantations matérielles ou logicielles. Cette thèse porte sur l'étude et l'implantation matérielle d'opérateurs pour l'évaluation de fonctions pour des applications spécifiques en traitement du signal et des images et en cryptographie. La première partie présente des opérateurs d'évaluation de fonctions basés sur des approximations polynomiales qui demandent peu de matériel. La seconde partie étudie la génération automatique d'opérateurs à base d'additions et décalages (type SRT) pour l'évaluation de certaines fonctions algébriques. Enfin, la dernière partie présente une implantation efficace et compacte des fonctions de hachage cryptographique de la famille SHA-2. Les différents opérateurs proposés dans cette thèse ont tous été validés sur des circuits FPGA.

L'arithmétique des ordinateurs est une branche de l'informatique qui traite des systèmes de représentation des nombres, des algorithmes arithmétiques et de leurs implantations matérielles ou logicielles. Cette thèse porte sur l'étude et l'implantation matérielle d'opérateurs pour l'évaluation de fonctions en traitement du signal et des images. Sont présentés successivement un générateur d'opérateurs optimisés pour la division, des études portant sur un algorithme d'évaluation de fonctions au moyen d'approximations par fractions rationnelles, et des opérateurs d'évaluation de fonctions basés sur des approximations polynomiales qui demandent peu de matériel. Les différents opérateurs proposés dans cette thèse ont tous été validés sur des circuits FPGA.

Les systèmes informatiques permettent d'évaluer des fonctions numériques telles que f = exp, sin, arccos, etc. Cette thèse s'intéresse au processus d'implémentation de ces fonctions. Suivant la cible visée (logiciel ou matériel, faible ou grande précision), les problèmes qui se posent sont différents, mais l'objectif est toujours d'obtenir l'implémentation la plus efficace possible. Nous étudions d'abord, à travers un exemple, les problèmes qui se posent dans le cas où la précision est arbitraire. Lorsque, à l'inverse, la précision est connue d'avance, la fonction f est souvent remplacée par un polynôme d'approximation p. Un tel polynôme peut ensuite être évalué très efficacement en machine. En pratique, les coefficients de p doivent être représentables sur un nombre fini donné de bits. Nous proposons un ensemble d'algorithmes (certains sont heuristiques, d'autres rigoureux) pour trouver de très bons polynômes d'approximation répondant à cette contrainte. Ces résultats s'étendent au cas où la fonction d'approximation est une fraction rationnelle. Une fois p trouvé, il faut prouver que l'erreur |p-f| n'excède pas un certain seuil. La nature particulière de la fonction p-f (soustraction de deux fonctions très proches) rend cette propriété difficile à prouver rigoureusement. Nous proposons un algorithme capable de contourner cette difficulté. Tous ces algorithmes ont été intégrés au logiciel Sollya, développé pendant la thèse. À l'origine conçu pour faciliter l'implémentation de fonctions, ce logiciel s'adresse à présent à toute personne souhaitant faire des calculs numériques dans un cadre complètement fiable.

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.

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.

De nombreuses méthodes de traitement du signal reposent sur des résultats puissants d'approximation numérique. Un exemple significatif en est l'utilisation de l'approximation de type Chebyshev pour l'élaboration de filtres numériques.En pratique, le caractère fini des formats numériques utilisés en machine entraîne des difficultés supplémentaires pour la conception de filtres numériques (le traitement audio et le traitement d'images sont deux domaines qui utilisent beaucoup le filtrage). La majorité des outils actuels de conception de filtres ne sont pas optimisés et ne certifient pas non plus la correction de leurs résultats. Notre travail se veut un premier pas vers un changement de cette situation.La première partie de la thèse traite de l'étude et du développement de méthodes relevant de la famille Remez/Parks-McClellan pour la résolution de problèmes d'approximation polynomiale de type Chebyshev, en utilisant l'arithmétique virgule-flottante.Ces approches sont très robustes, tant du point de vue du passage à l'échelle que de la qualité numérique, pour l'élaboration de filtres à réponse impulsionnelle finie (RIF).Cela dit, dans le cas des systèmes embarqués par exemple, le format des coefficients du filtre qu'on utilise en pratique est beaucoup plus petit que les formats virgule flottante standard et d'autres approches deviennent nécessaires.Nous proposons une méthode (quasi-)optimale pour traîter ce cas. Elle s'appuie sur l'algorithme LLL et permet de traiter des problèmes de taille bien supérieure à ceux que peuvent traiter les approches exactes. Le résultat est ensuite utilisé dans une couche logicielle qui permet la synthèse de filtres RIF pour des circuits de type FPGA.Les résultats que nous obtenons en sortie sont efficaces en termes de consommation d'énergie et précis. Nous terminons en présentant une étude en cours sur les algorithmes de type Remez pour l'approximation rationnelle. Ce type d'approches peut être utilisé pour construire des filtres à réponse impulsionnelle infinie (RII) par exemple. Nous examinons les difficultés qui limitent leur utilisation en pratique. / The field of signal processing methods and applications frequentlyrelies on powerful results from numerical approximation. One suchexample, at the core of this thesis, is the use of Chebyshev approximationmethods for designing digital filters.In practice, the finite nature of numerical representations adds an extralayer of difficulty to the design problems we wish to address using digitalfilters (audio and image processing being two domains which rely heavilyon filtering operations). Most of the current mainstream tools for thisjob are neither optimized, nor do they provide certificates of correctness.We wish to change this, with some of the groundwork being laid by thepresent work.The first part of the thesis deals with the study and development ofRemez/Parks-McClellan-type methods for solving weighted polynomialapproximation problems in floating-point arithmetic. They are veryscalable and numerically accurate in addressing finite impulse response(FIR) design problems. However, in embedded and power hungry settings,the format of the filter coefficients uses a small number of bits andother methods are needed. We propose a (quasi-)optimal approach basedon the LLL algorithm which is more tractable than exact approaches.We then proceed to integrate these aforementioned tools in a softwarestack for FIR filter synthesis on FPGA targets. The results obtainedare both resource consumption efficient and possess guaranteed accuracyproperties. In the end, we present an ongoing study on Remez-type algorithmsfor rational approximation problems (which can be used for infinite impulseresponse (IIR) filter design) and the difficulties hindering their robustness.

L'implantation en Virgule Flottante (VF) d'une fonction à valeurs réelles est réalisée avec arrondi correct si le résultat calculé est toujours égal à l'arrondi de la valeur exacte, ce qui présente de nombreux avantages. Mais pour implanter une fonction avec arrondi correct de manière fiable et efficace, il faut résoudre le "dilemme du fabricant de tables" (TMD en anglais). Deux algorithmes sophistiqués (L et SLZ) ont été conçus pour résoudre ce problème, via des calculs longs et complexes effectués par des implantations largement optimisées. D'où la motivation d'apporter des garanties fortes sur le résultat de ces pré-calculs coûteux. Dans ce but, nous utilisons l'assistant de preuves Coq. Tout d'abord nous développons une bibliothèque d'"approximation polynomiale rigoureuse", permettant de calculer un polynôme d'approximation et un intervalle bornant l'erreur d'approximation à l'intérieur de Coq. Cette formalisation est un élément clé pour valider la première étape de SLZ, ainsi que l'implantation d'une fonction mathématique en général (avec ou sans arrondi correct). Puis nous avons implanté en Coq, formellement prouvé et rendu effectif 3 vérifieurs de certificats, dont la preuve de correction dérive du lemme de Hensel que nous avons formalisé dans les cas univarié et bivarié. En particulier, notre "vérifieur ISValP" est un composant clé pour la certification formelle des résultats générés par SLZ. Ensuite, nous nous sommes intéressés à la preuve mathématique d'algorithmes VF en "précision augmentée" pour la racine carré et la norme euclidienne en 2D. Nous donnons des bornes inférieures fines sur la plus petite distance non nulle entre sqrt(x²+y²) et un midpoint, permettant de résoudre le TMD pour cette fonction bivariée. Enfin, lorsque différentes précisions VF sont disponibles, peut survenir le phénomène de "double-arrondi", qui peut changer le comportement de petits algorithmes usuels en arithmétique. Nous avons prouvé en Coq un ensemble de théorèmes décrivant le comportement de Fast2Sum avec double-arrondis.