Dans cette thèse, nous étudions plusieurs modèles de routage efficaces en énergie. Pour chaque modèle, nous présentons une formulation en programmation linéaire mixte permettant de trouver une solution exacte. En outre, comme il s’agit de problèmes NP-Difficiles, nous proposons des heuristiques efficaces pour des réseaux de grande taille. Dans la première partie de cette thèse, nous étudions une solution de routage efficace en énergie dans laquelle nous ajoutons la possibilité d’éliminer des redondances dans les paquets transmis sur le réseau. Nous montrons premièrement que l’ajout de l’élimination des redondances permet d’améliorer l’efficacité énergétique des réseaux en éteignant plus de liens. Ensuite, nous étendons le modèle afin qu’il prenne en compte un certain niveau d’incertitudes dans le volume de trafic et le taux de redondances. La deuxième partie de cette thèse est consacrée aux problèmes qui se posent lors du déploiement de tels protocoles dans les réseaux. Plus particulièrement, nous proposons de minimiser les changements entre deux configurations réseaux consécutives lorsque plusieurs matrices de trafic sont considérées. Le routage des demandes étant alors assuré avec le protocole de routage OSPF (Open Shortest Path First). Ensuite, nous abordons le problème de la limitation du nombre de règles de routage dans les routeurs en utilisant une technologie de type SDN (Software Defined Networks). Enfin, nous présentons en annexe des travaux complémentaires réalisés au cours de cette thèse concernant le routage multicast et le contrôle de congestion TCP. / In this thesis, we study several models of energy-Aware routing. For each model, we present a linear programming formulation to find the exact solution. Moreover, since energy-Aware routing is NP-Hard problem, we also propose efficient heuristic algorithms for large scale networks. In the first part of this thesis, we deal with GreenRE - a new energy-Aware routing model with the support of redundancy elimination. We first present a deterministic model in which we show how to combine energy-Aware routing and redundancy elimination to improve energy efficiency for backbone networks. Then, we extend the model in order to take into account uncertainties in traffic volumes and redundancy rates. The second part of this thesis is devoted to the deployment issues of energy- aware routing in practice. In detail, to avoid service deterioration for end-Users, we limit changes of network configurations in multi-Period traffic matrices in Open Shortest Path First (OSPF) protocol. Next, we address the problem of limited rule space in OpenFlow switches when installing energy-Aware routing configurations. Finally, we present in the appendix other works developed during this thesis: multicast network protocol and TCP congestion control algorithm.

Le choléra est une diarrhée hydrique sévère volontiers épidémique causée par des Vibrio cholerae O1 toxinogènes. Ses déterminants environnementaux ont donné naissance à un paradigme influent sur les stratégies de lutte, qui sont se sont avérées peu efficientes en Afrique comme en Haïti. Elles pourraient être améliorées par une meilleure compréhension de la dynamique des épidémies. La synthèse bibliographique des influences de l'environnement sur les épidémies de choléra en Afrique y montre les limites du paradigme environnemental. L'étude multidisciplinaire des origines de l'épidémie de choléra en Guinée en 2012 suggère fortement qu'elle fut importée par voie humaine depuis la Sierra Leone voisine. Une description spatio-temporelle du choléra au Mozambique démontre l'hétérogénéité de sa transmission et amène à questionner le concept d'endémicité du choléra. Depuis son importation en Haïti en octobre 2010, l'épidémie de choléra présente également une répartition spatiale et temporelle très hétérogène. Son importante rétractation en saison sèche et son absence d'enracinement significatif dans l'environnement laissent espérer la possibilité d'une élimination rapide à condition d'apporter une réponse ciblée à tous les foyers épidémiques du pays. Une stratégie d'élimination basée sur nos recommandations y est actuellement menée par le Ministère de la Santé, l'UNICEF et leurs partenaires. Après des résultats spectaculaires en 2013 et au premier semestre 2014, la situation s'est à nouveau dégradée pendant la saison des pluies. Une élimination du choléra dans saison sèche à venir demeure cependant réaliste si nous parvenons à convaincre et remobiliser les acteurs de terrain. / Cholera is an epidemic acute watery diarrhea caused by toxigenic bacteria Vibrio cholerae O1. Its environment determinants have been at the source of a popular paradigm. Many recent control strategies have shown little efficiency in Africa or in Haiti, but they could be improved by a better comprehension of the epidemics dynamic. The bibliographic synthesis of environment influences on cholera in Africa highlights the limits of the environmental paradigm on this continent. A multidisciplinary study of the origin of cholera epidemic in Guinea in 2012 strongly suggests it was humanly imported from nearby Sierra Leone. A space-time description of cholera in Mozambique demonstrates heterogeneous transmission patterns and challenges the concept of cholera endemicity. Since its importation in Haiti in October 2010, cholera transmission also exhibits a marked spatio-temporal heterogeneity. Cholera important retraction during the dry season and its absence of significant establishment in the Haitian environment suggest it may be possible to rapidly eliminate cholera in the country, provided that every outbreak focus receives a targeted response. An elimination strategy based on our recommendations is currently implemented by Haitian Ministry of Health, UNICEF and their partners. After spectacular results in 2013 and during the first half of 2014, the situation has slowly deteriorated during the rainy season. However, cholera elimination during the coming dry season remains realistic provided that we succeed in persuading and remobilizing the partners present on the field.

Cette thèse traite de la theorie de la preuve pour les logiques a points fixes, telles que le μ-calcul, lalogique lineaire a points fixes, etc. ces logiques sont souvent munies de systèmes de preuves finitairesavec des règles d’induction à la Park. Il existe néanmoins d’autres sytèmes de preuves pour leslogiques à points fixes, qui reposent sur la notion de preuve infinitaire, mais qui sont beaucoupmoins developpés dans la litterature. L’objectif de cette thèse est de pallier à cette lacune dansl’état de l’art, en developpant la théorie de la preuve infnitaire pour les logiques a points fixes,avec deux domaines d’application en vue: les langages de programmation avec types de données(co)inductifs et la vérification des systèmes réactifs.Cette thèse contient trois partie. Dans la première, on rappelle les deux principales approchespour obtenir des systèmes de preuves pour les logiques à points fixes: les systèmes finitaires avecrègle explicite d’induction et les systèmes finitaires, puis on montre comment les deux approchesse relient. Dans la deuxième partie, on argumente que les preuves infinitaires ont effectivement unréel statut preuve-theorique, en montrant que la logique lineaire additive multiplicative avec pointsfixes admet les propriétés d’élimination des coupures et de focalisation. Dans la troisième partie,on utilise nos developpements sur les preuves infinitaires pour monter de manière constructive lacomplétude du μ-calcul lineaire relativement à l’axiomatisation de Kozen. / The subject of this thesis is the proof theory of logics with fixed points, such as the μ-calculus,linear-logic with fixed points, etc. These logics are usually equipped with finitary deductive systemsthat rely on Park’s rules for induction. other proof systems for these logics exist, which relyon infinitary proofs, but they are much less developped. This thesis contributes to reduce thisdeficiency by developing the infinitary proof-theory of logics with fixed points, with two domainsof application in mind: programming languages with (co)inductive data types and verification ofreactive systems.This thesis contains three parts. In the first part, we recall the two main approaches to theproof theory for logics with fixed points: the finitary and the infinitary one, then we show theirrelationships. In the second part, we argue that infinitary proofs have a true proof-theoreticalstatus by showing that the multiplicative additive linear-logic with fixed points admits focalizationand cut-elimination. In the third part, we apply our proof-theoretical investigations to obtain aconstructive proof of completeness for the linear-time μ-calculus w.r.t. Kozen’s axiomatization.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Il est important que les logiciels pilotant les systèmes critiques (avions, centrales nucléaires, etc.) fonctionnent correctement — alors que la plupart des systèmes informatisés de la vie courante (micro-ordinateur, distributeur de billets, téléphone portable) ont des dysfonctionnements visibles. Il ne s'agit pas là d'un simple problème d'ingéniérie : on sait depuis les travaux de Turing et de Cook que la preuve de propriétés de bon fonctionnement sur les programmes est un problème intrinsèquement difficile.<br /><br />Pour résoudre ce problème , il faut des méthodes à la fois efficaces (coûts en temps et en mémoire modérés), sûres (qui trouvent tous les problèmes possibles) et précises (qui fournissent peu d'avertissements pour des problèmes inexistants). La recherche de ce compromis nécessite des recherches faisant appel à des domaines aussi divers que la logique formelle, l'analyse numérique ou l'algorithmique « classique ».<br /><br />De 2002 à 2007 j'ai participé au développement de l'outil d'analyse statique Astrée. Ceci m'a suggéré quelques développements annexes, à la fois théoriques et pratiques (utilisation de techniques de preuve formelle, analyse de filtres numériques...). Plus récemment, je me suis intéressé à l'analyse modulaire de propriétés numériques et aux applications en analyse de programme de techniques de résolution sous contrainte (programmation semidéfinie, techniques SAT et SAT modulo théorie).

La fonctionnalisation de liaisons C-H réputées peu réactives ouvre de nouvelles perspectives en synthèse organique. Une stratégie efficace consiste en l'utilisation d'un métal de transition. Les travaux de thèse présentés dans ce mémoire s'inscrivent dans ce contexte. Dans un premier temps, la réaction étudiée, catalysée par le palladium, vise à étendre une méthodologie mise au point au laboratoire, permettant la synthèse de benzocyclobutènes par activation intramoléculaire de liaisons C(sp3)-H de groupements méthyles benzyliques, à des composés non aromatiques. Plusieurs substrats ont été synthétisés pour être ensuite placés dans les conditions de la réaction d'activation C(sp3)-H, dans le but d'induire la formation du cyclobutène ou du cyclobutane désiré. Le processus n'est pas sélectif et de nombreux produits secondaires sont obtenus par des réactions péricyliques ou par des réarrangements suite à l'ouverture du palladacycle intermédiaire. Dans un deuxième temps, nos travaux ont permis de mettre à jour une nouvelle réaction de fonctionnalisation C(sp3)-H, catalysée par le palladium permettant l'arylation d'esters en position β par un mécanisme original. Les investigations portent sur l'optimisation complète de cette réaction, la compréhension du mécanisme et le développement d'une version énantiosélective prometteuse. Le mécanisme de cette réaction, confirmé par des calculs DFT réalisés en collaboration avec C. Kefalidis et E. Clot, se rapproche formellement de celui observé en α-arylation, puisqu'il repose sur la formation d'un énolate de palladium. La stratégie mise au point permet le couplage, dans des conditions douces, d'esters simples et commerciaux avec des halogénures d'aryles contenant un groupement électronégatif en position ortho, donnant ainsi accès à des intermédiaires de synthèse intéressants tels qu'un analogue de la phénylalanine ou des composés fluorés.

L'objectif principal de cette thèse est le pré-traitement des signaux d'électroencéphalographie (EEG). En particulier, elle vise à développer une méthodologie pour obtenir un EEG dit "propre" à travers l'identification et l'élimination des artéfacts extra-cérébraux (mouvements oculaires, clignements, activité cardiaque et musculaire) et du bruit. Après identification, les artéfacts et le bruit doivent être éliminés avec une perte minimale d'information, car dans le cas d'EEG, il est de grande importance de ne pas perdre d'information potentiellement utile à l'analyse (visuelle ou automatique) et donc au diagnostic médical. Plusieurs étapes sont nécessaires pour atteindre cet objectif : séparation et identification des sources d'artéfacts, élimination du bruit de mesure et reconstruction de l'EEG "propre". A travers une approche de type séparation aveugle de sources (SAS), la première partie vise donc à séparer les signaux EEG dans des sources informatives cérébrales et des sources d'artéfacts extra-cérébraux à éliminer. Une deuxième partie vise à classifier et éliminer les sources d'artéfacts et elle consiste en une étape de classification supervisée. Le bruit de mesure, quant à lui, il est éliminé par une approche de type débruitage par ondelettes. La mise en place d'une méthodologie intégrant d'une manière optimale ces trois techniques (séparation de sources, classification supervisée et débruitage par ondelettes) constitue l'apport principal de cette thèse. La méthodologie développée, ainsi que les résultats obtenus sur une base de signaux d'EEG réels (critiques et inter-critiques) importante, sont soumis à une expertise médicale approfondie, qui valide l'approche proposée.

Un robot manipulateur parallèle est composé de deux solides, une plate-forme et une base, reliés par des chaînes cinématiques articulées et motorisées permettant leur mouvement relatif. Le problème du modèle géométrique direct des robots parallèles est essentiel. Il consiste a déterminer la position et l'orientation de la plate-forme par rapport a un repère de base lorsque les variables articulaires sont fixées. Ce problème revient a considérer le placement d'un solide quelconque sur six sphères de rayons et de centres fixés. Il présente deux facettes, une géométrique et l'autre algébrique, menant a diverses méthodes à mettre en oeuvre. Le modèle géométrique direct est connu pour admettre au plus quarante solutions complexes. Nous présentons une approche consistant a utiliser des capteurs additionnels pour simplifier et résoudre ce problème. Nous utilisons ou développons toute une gamme de méthodes symboliques et parfois numériques permettant la résolution dans ce contexte précis. Les résultats obtenus permettent de définir des architectures de robot ayant un nombre minimum de solutions pour la résolution du modèle géométrique direct, Voire même des solutions explicites ou uniques.

Dans cette thèse, nous définissons algébriquement le résultant déterminantiel d'un morphisme f de modules libres de type dont la matrice a en entrée des polynômes homogènes f_i,j. A l'aide des complexes d'Eagon-Northcott et de Buchsbaum-Rim associés au morphisme P nous proposons des méthodes effectives pour calculer ce résultant déterminantiel ainsi que son degré. Dans le cas où les polynômes f_i,j sont à deux variables, nous montrons que ce résultant déterminantiel est donné par le déterminant d'une matrice en les coefficients des f_i,j , qui est une généralisation de la matrice de Sylvester de deux polynômes. Dans la deuxième partie de la thèse, nous étudions des problèmes d'intersection de courbes et surfaces de Bézier en évitant la fameuse conversion instable entre la base de Bernstein et la base monomiale. Ces problèmes jouissent d'une structure particulière qui est dégénérée pour le résultant de Macaulay. Nous prouvons l'existence d'un résultant anisotrope adapté à ces systèmes dégénérés et proposons un algorithme pour le calculer.

L'auteur n'a pas fourni de résumé en français / The end of chip frequency scaling capacity, due heat dissipation limitations, made manufacturers search for an alternative to sustain the processing capacity growth. The chosen solution was to increase the hardware parallelism, by packing multiple independent processors in a single chip, in a Multiple-Instruction Multiple-Data (MIMD) fashion, each with special instructions to operate over a vector of data, in a Single-Instruction Multiple-Data (SIMD) manner. Such paradigm change, brought to software developer the convoluted task of producing efficient and scalable applications. Programming languages and associated tools evolved to aid such task for new developed applications. But automated optimizations capable of coping with such a new complex hardware, from legacy, single threaded applications, is still lacking.To apply code transformations, either developers or compilers, require to assert that, by doing so, they are not changing the expected comportment of the application producing unexpected results. But syntactically poor codes, such as use of pointer parameters with multiple possible indirections, complex loop structures, or incomplete codes, make very hard to extract application behavior solely from the source code in what is called a static analyses. To cope with the lack of information extracted from the source code, many tools and research has been done in, how to use dynamic analyses, that does application profiling based on run-time information, to fill the missing information. The combination of static and dynamic information to characterize an application are called hybrid analyses. This works advocates for the use of hybrid analyses to be able to optimizations on loops, regions where most of computations are done. It proposes a framework capable of statically applying some complex loop transformations, that previously would be considered unsafe, by assuring their safe use during run-time with a lightweight test.The proposed framework uses application execution profiling to help the static loop optimizer to: 1) identify and classify program hot-spots, so as to focus only on regions vital for the execution time; 2) guide the optimizer in understanding the overall loop behavior, so as to reduce the valid loop transformations search space; 3) using instruction's memory access functions, it statically builds a lightweight run-time test that determine, based on the program parameters values, if a given optimization is safe to be used or not. It's applicability is shown by performing complex loop transformations into a variety of loops, obtained from applications of different fields, and demonstrating that the run-time overhead is insignificant compared to the loop execution time or gained performance, in the vast majority of cases.