Contrôler la consommation en ressources des programmes informatiques est d'importance capitale, non seulement pour des raisons de performance, mais aussi pour des questions de sécurité quand par exemple certains systèmes mobiles ou embarqués disposent de quantités limitées de ressources. Dans cette thèse, nous développons des critères statiques pour contrôler la consommation en ressources de programmes concurrents d'ordre supérieur. Nous prenons comme point de départ le cadre des Logiques Light qui a été étudié afin de contrôler la complexité de programmes fonctionnels d'ordre supérieur au moyen de la correspondance preuves-programmes. La contribution de cette thèse est d'étendre ce cadre aux programmes concurrents d'ordre supérieur. Plus généralement, cette thèse s'inscrit dans le domaine de la complexité implicite qui cherche à caractériser des classes de complexité par des principes logiques ou des restrictions de langage. Les critères que nous proposons sont purement syntaxiques et sont développés graduellement afin de contrôler le temps de calcul des programmes de plus en plus finement: dans un premier temps nous montrons comment garantir la terminaison des programmes (temps fini), puis nous montrons comment garantir la terminaison des programmes en temps élémentaire, et enfin nous montrons comment garantir la terminaison des programmes en temps polynomial. Nous introduisons également des systèmes de types tels que les programmes bien typés terminent en temps borné et retournent des valeurs. Enfin, nous montrons que ces systèmes de types capturent des programmes concurrents intéressants qui itèrent des fonctions produisant des effets de bord sur des structures de données inductives. Dans la dernière partie, nous étudions une méthode sémantique alternative afin de contrôler la consommation en ressources de programmes impératifs d'ordre supérieur. Cette méthode est basée sur la réalisabilité quantitative de Dal Lago et Hofmann et permet d'obtenir plusieurs bornes de complexité de manière uniforme. Cette dernière partie est un travail en collaboration avec Aloïs Brunel.

L'objectif de la thèse est de créer et développer de nouvelles méthodes de résolution efficaces des problèmes combinatoires en configuration des lignes de fabrication. Deux problèmes ont été particulièrement étudiés: le problème d'équilibrage et de choix d'équipement pour des lignes dédiées et le problème de minimisation des coûts de changements de séries pour des lignes multi-produits. Une solution du premier problème consiste en une affectation admissible des ressources à un nombre de stations à déterminer de sorte que le coût total soit minimal. Afin de résoudre ce problème, nous l'avons réduit au problème de partition d'ensemble et l'avons résolu par des heuristiques gloutonnes et une méthode exacte de génération de contraintes. Les expérimentations sur différentes instances ont montré que la nouvelle approche de résolution surclasse les approches antérieures de la littérature en termes de qualité de solution et de temps de calcul. Pour le second problème deux critères sont considérés lexicographiquement : la minimisation du nombre de stations et la minimisation du coût de changement de séries. Nous avons examiné successivement les cas d'exécution parallèle et séquentielle des opérations. Des solutions approchées ont été trouvées par des heuristiques gloutonnes. Ensuite, nous avons proposé deux modèles de programmation linéaire en nombres entiers (PLNE) afin de trouver le nombre de stations minimal et ensuite d'obtenir le coût de changement de séries minimal. Les résultats des expérimentations sur ces nouveaux problèmes se sont avérés prometteurs à la fois en termes de qualité de solution et de temps de calcul.

La génomique comparée est essentiellement une forme de fouille de données dans des grandes collections de relations n-aires. La croissance du nombre de génomes sequencés créé un stress sur la génomique comparée qui croit, au pire géométriquement, avec la croissance en données de séquence. Aujourd'hui même des laboratoires de taille modeste obtient, de façon routine, plusieurs génomes à la fois - et comme des grands consortia attend de pouvoir réaliser des analyses tout-contre-tout dans le cadre de ses stratégies multi-génomes. Afin d'adresser les besoins à tous niveaux il est nécessaire de repenser les cadres algorithmiques et les technologies de stockage de données utilisés pour la génomique comparée. Pour répondre à ces défis de mise à l'échelle, dans cette thèse nous développons des méthodes originales basées sur les technologies NoSQL et MapReduce. À partir d'une caractérisation des sorts de données utilisés en génomique comparée et d'une étude des utilisations typiques, nous définissons un formalisme pour le Big Data en génomique, l'implémentons dans la plateforme NoSQL Cassandra, et évaluons sa performance. Ensuite, à partir de deux analyses globales très différentes en génomique comparée, nous définissons deux stratégies pour adapter ces applications au paradigme MapReduce et dérivons de nouveaux algorithmes. Pour le premier, l'identification d'événements de fusion et de fission de gènes au sein d'une phylogénie, nous reformulons le problème sous forme d'un parcours en parallèle borné qui évite la latence d'algorithmes de graphe. Pour le second, le clustering consensus utilisé pour identifier des familles de protéines, nous définissons une procédure d'échantillonnage itérative qui converge rapidement vers le résultat global voulu. Pour chacun de ces deux algorithmes, nous l'implémentons dans la plateforme MapReduce Hadoop, et évaluons leurs performances. Cette performance est compétitive et passe à l'échelle beaucoup mieux que les algorithmes existants, mais exige un effort particulier (et futur) pour inventer les algorithmes spécifiques.

L'eau est à la fois ressource et source de danger dans nos sociétés. Elle est aussi l'un des principaux acteurs du climat. Que ce soit pour la gestion des ressources en eau, la prévention des extrêmes climatiques ou une meilleure compréhension du climat, une bonne connaissance du cycle hydrologique est clairement indispensable. Ce projet consiste en l'étude du bilan d'eau atmosphérique tel que simulé par le Modèle Régional Canadien du Climat (MRCC) piloté par le Modèle Climatique Canadien Global (MCCG3) au-dessus de l'Amérique du nord. Deux simulations de 30 ans sont considérées, représentant pour l'une le climat actuel, et pour l'autre un climat futur plus chaud, selon le scénario A2 du Rapport Spécial sur les Scénarios d'Emission. La climatologie actuelle du bilan d'eau atmosphérique de ces deux climats est étudiée par le calcul de statistiques saisonnières pour les saisons d'été et d'hiver. Les variables du bilan d'eau sont de plus décomposées en trois échelles spatiales: une très grande échelle résolue par le MCCG3 et imposée au MRCC par le pilotage, une grande échelle résolue à la fois par le MRCC et le MCCG3, et une petite échelle résolue uniquement par le MRCC. La divergence horizontale du flux d'humidité atmosphérique est également décomposée de façon alternative en 9 termes d'interaction impliquant une des trois échelles de vent et d'humidité. Cette décomposition d'échelle permet d'une part d'explorer la contribution des différentes échelles à la climatologie du bilan d'eau atmosphérique, et d'autre part d'évaluer la valeur ajoutée des fines échelles du MRCC en les comparant aux plus grandes échelles du modèle. Les résultats traduisent des climatologies distinctes du bilan d'eau atmosphérique pour la saison d'hiver, dominée par le passage des dépressions des moyennes latitudes, et la saison d'été, où davantage de convection se produit. La contribution des petites échelles à la moyenne saisonnière des variables du bilan d'eau apparaît très limitée. En revanche, elle s'avère être importante pour leur variabilité intrasaisonnière, suggérant une valeur ajoutée importante des petites échelles. La comparaison des deux simulations de climat révèle une intensification générale de la branche atmosphérique du cycle hydrologique dans le climat futur simulé par le MRCC, comparable en termes relatifs pour les champs de moyenne et de variabilité temporelle. Elle apparaît également plus forte en termes relatifs en hiver qu'en été. Les changements observés, ainsi que la contribution des différentes échelles à ces changements, présentent des patrons cohérents avec ceux des variables dans le climat présent et sont gradués en amplitude selon l'intensité des signaux du climat présent. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : MRCC, Décomposition d'échelle, Bilan d'eau atmosphérique, Changement climatique, Valeur ajoutée.

La découverte de motifs fréquents est un des problèmes en fouille de données. Afin de mieux comprendre l'influence des données sur les algorithmes, nous présentons une étude expérimentale des jeux de données communément utilisés par la communauté. Cette étude permet d'aboutir à une nouvelle classification des données en fonction des bordures : stable et en accord avec les performances des algorithmes. Malgré le grand nombre de travaux et un cadre théorique des problèmes d'extraction de motifs intéressants, l'utilisation de ces algorithmes pour résoudre des problèmes "équivalents" est peu répandue et reste délicate. Face à ces limites, nous proposons un algorithme générique de découverte des bordures des motifs intéressants, appelé ABS (Adaptive borders Search), adaptant dynamiquement sa stratégie en fonction des données. De plus, une librairie générique de composants C++ a été proposée pour faciliter le développement de solutions logicielles pour cette famille de problèmes.

Cette thèse a pour objectif de faciliter le déploiement d'applications distribuées sur des grilles de calcul à grande échelle, en utilisant une infrastructure pair-à-pair (P2P) pour les grilles. De plus, cette thèse propose aussi une bibliothèque basée sur la technique << Elagage et Branchement >> (de l'anglais, Branch-and-Bound -- B&B) pour résoudre les problèmes d'optimisation combinatoire.<br /><br />Les modèles et infrastructures pour le P2P existant sont plutôt décevants : seulement des tâches indépendantes généralement sans communication entre les tâches, et des API de bas niveau. Cette thèse propose une infrastructure P2P qui partage des noeuds de calcul, afin de fournir des grilles à grande échelle. L'infrastructure est un réseau P2P non-structuré, auto-organisé, configurable et qui permet le déploiement d'applications communicantes.<br /><br />Les environnements P2P semblent être bien adaptés aux applications avec un faible ratio communication/computation, comme les algorithmes de recherche parallèle et plus particulièrement les algorithmes de B&B. En plus d'une infrastructure P2P, cette thèse propose une bibliothèque de B&B parallèle pour la grille. Cette bibliothèque aide les utilisateurs, en masquant toutes les difficultés liées à la distribution, à paralléliser leurs problèmes sur des grilles. La bibliothèque repose sur un modèle maître-travailleur hiérarchique et offre un système transparent de communication afin d'améliorer la vitesse de résolution.<br /><br />Nous avons tout d'abord implémenté notre infrastructure P2P au-dessus de l'intergicielle Java pour la grille, ProActive. Cette infrastructure P2P a été déployée comme grille de bureau de manière permanente, avec laquelle nous avons pu réaliser un record mondial de calcul en résolvant le problème des n-reines avec 25 reines. Ensuite, nous avons aussi implémenté avec ProActive notre bibliothèque pour le B&B. Nous montrons le passage à l'échelle et l'efficacité de la bibliothèque en déployant sur une grille de taille nationale (Grid'5000) une application qui résout le problème du << flow-shop >>. Pour finir, nous avons mixé Grid'5000 et notre grille de bureau pour expérimenter le déploiement à grande échelle des n-reines et du flow-shop.

Le monde physique dans lequel nous vivons est essentiellement géométrique. Le calcul géométrique est une brique centrale de nombreux domaines, comme la conception assistée par ordinateur, le graphisme, la robotique, la vision artificielle et bien d'autres. Depuis plus de trois décennies, la géométrie algorithmique est la discipline dédiée à l'établissement de bases solides pour l'étude des algorithmes géométriques qui relèvent de ces applications. Elle s'est historiquement et traditionnellement concentrée sur le traitement d'objets linéaires. Pour de nombreuses applications, il est nécessaire de manipuler des objets généraux comme des courbes et des surfaces complexes. L'extension du répertoire de la géométrie algorithmique aux objets courbes pose de nombreuses difficultés: refonte des structures de données et algorithmes fondamentaux; irruption massive de questions algébriques; explosion du nombre de cas dégénérés...<br /><br />Cette thèse d'habilitation contribue à l'établissement d'un calcul géométrique effectif pour les objets courbes de faible degré. Elle reprend mes principales contributions sur le sujet ces dernières années. Mentionnons notamment: un algorithme exact, optimal et efficace pour le calcul du paramétrage de l'intersection de deux quadriques à coefficients entiers; la caractérisation des positions relatives de deux coniques projectives à l'aide de prédicats géométriques de faible degré, mis au jour grâce à la théorie des invariants algébriques; la caractérisation des dégénérescences du problème de tangentes réelles communes à quatre sphères; la convexité du cône des directions de droites perçant trois boules disjointes, et les conséquences importantes de ce résultat en théorie de transversales géométriques. Le manuscrit se conclue par un panel de directions de recherche poursuivant et étendant les résultats obtenus à ce jour.

La première partie de cette thèse est consacrée à l'élaboration théorique de<br />processus adiabatiques permettant l'implémentation de portes logiques<br />quantiques, les constituants élémentaires des ordinateurs quantiques, par<br />l'interaction de champs laser impulsionnels avec des atomes. L'utilisation de<br />techniques adiabatiques permet des implémentations robustes, i.e. insensibles<br />aux fluctuations des paramètres expérimentaux. Les processus décrits dans cette<br />thèse ne nécessitent que le contrôle précis des polarisations et des phases<br />relatives des champs lasers. Ces processus permettent l'implémentation d'un<br />ensemble universel de portes quantiques, autorisant l'implémentation de toute<br />autre porte quantique par combinaisons.<br />La seconde partie de cette thèse concerne les effets de la décohérence par<br />déphasage sur le passage adiabatique. La formule de probabilité de transition<br />d'un système à deux niveaux tenant compte de ces effets décohérents est établie.<br />Cette formule est valable dans les différents régimes, diabatique et<br />adiabatique, et permet d'établir les paramètres de trajectoires elliptiques<br />optimisant le transfert de population.

Cette thèse donne deux applications du calcul de Malliavin pour les processus de sauts.<br />Dans la première partie, nous traitons la minoration de la densité des diffusions à sauts dont la partie continue est dirigée par un mouvement Brownien. Pour cela, nous utilisons une formule d'intégration par parties conditionnelle basée sur le mouvement Brownien uniquement.<br />Nous traitons ensuite le calcul d'options financières dont le prix du sous-jacent est un processus à sauts pur.<br />Dans la deuxième partie, nous développons un calcul abstrait du type Malliavin basé sur des variables aléatoires non indépendantes, de densité conditionnelle discontinue. Nous établissons une formule d'intégration par parties que nous appliquons aux amplitudes et temps de sauts des processus à sauts considérés. Dans la troisième partie, nous utilisons cette intégration par parties pour calculer le Delta d'options européennes et asiatiques, et pour calculer le prix et le Delta d'options américaines via des formules de représentation pour les espérances conditionnelles et leur gradient.

La production industrielle d'aluminium met en jeu plusieurs aspects physiques, à la fois chimiques, thermiques et magnétohydrodynamiques (MHD). L'une de ses particularités est la coexistence dans une cuve de deux fluides non miscibles, ce qui conduit à la présence d'une interface libre. Ce procédé consomme près de 2% de l'électricité mondiale, la moitié étant perdue par effet Joule. L'enjeu est de réduire ce coût sans déstabiliser le procédé: il s'agit typiquement d'un problème de contrôle optimal, que nous traitons en considérant une modélisation MHD de la cuve. Deux approches sont utilisées pour effectuer cette optimisation, à savoir considérer une contrainte d'état non linéaire basée sur un couplage entre les équations de Maxwell et de Navier-Stokes multifluides, et une contrainte d'état linéaire résultant d'une approximation shallow water de la précédente. Après une courte introduction à la modélisation du procédé et aux concepts du contrôle optimal basé sur le principe de Pontryagin, nous décrivons dans un premier temps le contrôle de l'évolution de l'interface modélisée par l'approximation shallow water. S'ensuivent un travail de parallèlisation du logiciel de simulation du procédé dans le cadre non linéaire et la recherche numérique d'actionneurs acceptables pour son contrôle. Enfin, un algorithme d'optimisation de la forme de l'interface est proposé sous une contrainte d'état non linéaire simplifié, à savoir les équations de Navier-Stokes bifluides en dimension deux.