Un très grand nombre de problèmes combinatoires appartient à la famille des problèmes de satisfaction de contraintes (Constraint Satisfaction Problem ou CSP) : configuration, ordonnancement, affectation de ressources... Ces problèmes partagent une description commune qui autorise en général une modélisation claire et intuitive. Dans cette thèse, nous avons proposé et étudié une nouvelle méthode de résolution hybride pour les CSPs. Nous avons nommé cette méthode Tabu-NG pour Tabu Search based on NoGood. Le nom est un peu réducteur car il s'agit d'une hybridation d'algorithme de filtrage, de propagation de contraintes, de Recherche Tabou et de gestion de nogoods. La méthode a été appliquée sur deux types de problèmes. Le premier est l'affectation des fréquences (FAP) dans les réseaux de radiocommunications militaires, en particulier les problèmes proposés de 1993 (instances du projet européen CALMA) jusqu'à 2010 (instances d'un projet DGA). Le deuxième est le problème académique de k-coloration de graphes sur les instances DIMACS. La méthode a amélioré quelques meilleurs scores connus actuellement. Dans les deux problèmes nous avons traité des contraintes unaires et binaires, ainsi que des contraintes n-aires et de l'optimisation de fonction sous contraintes pour le FAP. Les principes de Tabu-NG sont généraux et elle peut s'appliquer sur d'autres CSP. Elle peut par ailleurs accueillir des heuristiques spécifiques aux problèmes, nous l'avons pratiqué sur les problèmes cités, et en ce sens nous pensons pouvoir qualifier la méthode de métaheuristique sans abuser de cette définition.

Les travaux présentés dans cette thèse visent à proposer des méthodes de calcul d'itinéraires adaptés aux cyclistes à l'échelle d'une agglomération. Plusieurs critères sont considérés, comme la distance, la sécurité et l'effort. La difficulté est de calculer des chemins de compromis sous une contrainte de temps de quelques secondes pour pouvoir intégrer ce calculateur à un site web. Deux approches ont été abordées pour résoudre ce problème. L'approche a posteriori dans laquelle l'ensemble des solutions de compromis est calculé et l'approche a priori dans laquelle les préférences de l'utilisateur sont prises en compte et permettent d'orienter la recherche pour privilégier les chemins les plus prometteurs. Enfin, nous proposons de modéliser le réseau routier sous la forme d'un graphe adjoint pour pouvoir prendre en compte de nouveaux critères nécessitant, par exemple, des coûts sur les enchaînements d'arcs. L'ensemble de ce travail a permis de développer le service Géovélo qui est un calculateur d'itinéraires multiobjectif adaptés au vélo. Le service est disponible sous la forme d'un site web et d'applications mobiles.

Un principal résultat de la thèse est une preuve conceptionnelle du fait que le nombre pondéré de courbes tropicales de degré et genre donnés qui passent par le bon nombre de points en position générale dans $\RR^2$ (resp., qui passent par le bon nombre de points en position générale dans $ \RR^r $ et représentent un point fixé dans l'espace de modules de courbes tropicales abstraites de genre g ) ne dépend pas du choix de points. Un autre principal résultat est un nouveau théorème de correspondance entre les cycles tropicaux plans et les courbes algébriques elliptiques planes.

The so-called Web 2.0 revolution has fundamentally changed the way people interact with the Internet. The Web has turned from a read-only infrastructure to a collaborative platform. By expressing their preferences and sharing private information, the users benefit from a personalized Web experience. Yet, these systems raise several problems in terms of \emph{privacy} and \emph{scalability}. The social platforms use the user information for commercial needs and expose the privacy and preferences of the users. Furthermore, centralized personalized systems require costly data-centers. As a consequence, existing centralized social platforms do not exploit the full extent of the personalization possibilities. In this thesis, we consider the design of social networks and social information services in the context of \emph{peer-to-peer} (P2P) networks. P2P networks are decentralized architecture, thus the users participates to the service and control their own data. This greatly improves the privacy of the users and the scalability of the system. Nevertheless, building social systems in a distributed context also comes with many challenges. The information is distributed among the users and the system has be able to efficiently locate relevant data. The contributions of this thesis are as follow. We define the \emph{cold start link prediction} problem, which consists in predicting the edges of a social network solely from the social information of the users. We propose a method based on a \emph{probabilistic graph} to solve this problem. We evaluate it on a dataset from Flickr, using the group membership as social information. Our results show that the social information indeed enables a prediction of the social network. Thus, the centralization of the information threatens the privacy of the users, hence the need for decentralized systems. We propose \textsc{SoCS}, a \emph{decentralized} algorithm for \emph{link prediction}. Recommending neighbors is a central functionality in social networks, and it is therefore crucial to propose a decentralized approach as a first step towards P2P social networks. \textsc{SoCS} relies on gossip protocols to perform a force-based embedding of the social networks. The social coordinates are then used to predict links among vertices. We show that \textsc{SoCS} is adapted to decentralized systems at it is churn resilient and has a low bandwidth consumption. We propose \textsc{GMIN}, a \emph{decentralized} platform for \emph{personalized services} based on social information. \textsc{GMIN} provides each user with neighbors that share her interests. The clustering algorithm we propose takes care to encompass all the different interests of the user, and not only the main ones. We then propose a personalized \emph{query expansion} algorithm (\textsc{GQE}) that leverages the \textsc{GMIN} neighbors. For each query, the system computes a tag centrality based on the relations between tags as seen by the user and her neighbors.

Le partitionnement de graphes est une technique employée dans de nombreux domaines scientifiques. Il est utilisé pour résoudre des problèmes d'optimisation, modélisés sous la forme de graphes valués ou non, et pour lesquels la recherche de bonnes solutions équivaut au calcul, éventuellement récursivement, de coupes sommet ou arête les plus petites possible et qui équilibrent les tailles des sous-parties séparées. La plupart des méthodes actuelles de partitionnement de graphes mettent en oeuvre un schéma multi-niveaux, dans lequel le graphe à partitionner est successivement contracté pour former une famille de graphes de plus en plus petits, mais de structure topologique similaire, de sorte qu'une partition initiale calculée sur le plus petit graphe puisse être propagée de proche en proche, par prolongations et raffinements successifs, jusqu'à obtenir un partitionnement du graphe initial. Du fait de l'augmentation croissante de la taille des problèmes à résoudre, ceux-ci ne peuvent plus être traités de façon séquentielle sur un unique ordinateur. Il est donc nécessaire de concevoir des algorithmes parallèles de partitionnement de graphes, aptes à traiter des graphes à plusieurs milliards de sommets distribués sur plusieurs milliers de processeurs. Plusieurs auteurs s'étaient déjà attelés à cette tâche, mais la performance des algorithmes proposés, ou la qualité des solutions produites, se dégradent lorsque le nombre de processeurs augmente. Ce mémoire présente les travaux réalisées au sein du projet PT-Scotch sur la conception d'algorithmes efficaces et robustes pour la parallélisation du schéma multi-niveaux. Il se concentre en particulier sur les phases de contraction et de raffinement, qui sont les plus critiques en termes de performance et de qualité des solutions produites. Il propose un algorithme parallèle probabiliste d'appariement, ainsi qu'un ensemble de méthodes permettant de réduire l'espace des solutions au cours la phase de raffinement et facilitant l'usage de méthodes globales, qui passent mieux à l'échelle mais sont en général bien plus coûteuses que les algorithmes d'optimisation locale habituellement mis en oeuvre dans le cas séquentiel.

Cette thèse concerne l'étude des graphes quantiques, c'est à dire, des systèmes quantiques dans lesquels une particule non relativiste est confinée sur un graphe. Nous proposons une nouvelle voie pour représenter des conditions aux limites, et à l'aide de ce résultat nous résolvons le problème, resté longtemps ouvert, d'approximation par des graphes réguliers de tous les couplages singuliers aux sommets dans un graphe quantique. Nous présentons une construction dans laquelle les arêtes sont disjointes et les paires d'extrémités ainsi obtenues sont raccordés par des arêtes additionnelles de longueur 2d. Chacune de ces arêtes porte un potentiel delta et un potentiel vectoriel . Nous montrons que lorsque d tend vers zéro et les potentiels dépendent convenablement de d, la limite peut produire tout couplage singulier de sommets requis. Ce type de conditions aux limites est utilisé pour examiner les propriétés de diffusion par des sommets singuliers de degré 3. Nous montrons que les couplages entre chaque paire de lignes issues du sommet sont réglables individuellement ce qui pourrait permettre la conception de filtre quantique de type "aiguillage spectral". Nous étudions aussi les opérateurs de Schrödinger sur un graphe infini en forme de chaîne composée de cercles identiques couplés aux points de contact par les interactions. delta Si le graphe est périodique, l'hamiltonien a un spectre de bande. Nous considérons une déformation "courbée" de la chaîne qui consiste en un changement de la position du point de contact entre deux cercles. On montre que cette déformation a pour conséquence la naissance de valeurs propres et analyse leur dépendance par rapport à l"angle de courbature".

Ce travail se place dans le cadre du calcul haute performance sur des plateformes d'exécution de grande taille telles que les grilles de calcul. Les grilles de calcul sont notamment caractérisées par (1) des changements fréquents des conditions d'exécution et, en particulier, par (2) une probabilité importante de défaillance due au grand nombre de composants. Pour exécuter une application efficacement dans un tel environnement, il est nécessaire de prendre en compte ces paramètres. Nos travaux de recherche reposent sur la représentation abstraite de l'application sous forme d'un graphe de flot de données de l'environnement de programmation parallèle et distribuée Athapascan/Kaapi. Nous utilisons cette représentation abstraite pour apporter des solutions aux problèmes (1) de reconfiguration dynamique et (2) de tolérance aux fautes. - Tout d'abord, nous proposons un mécanisme de reconfiguration dynamique qui gère, de manière transparente pour le programmeur de la reconfiguration, les problèmes d'accès concurrents sur l'état de l'application et la cohérence mutuelle des états en cas de reconfiguration distribuée. - Ensuite, nous présentons un protocole de tolérance aux fautes original qui permet d'effectuer une reprise partielle de l'application en cas de panne. Pour cela, il détermine l'ensemble des tâches de calcul strictement nécessaires à la reprise de l'application. Ces contributions sont évaluées en utilisant les logiciels Kaapi et X-Kaapi sur la plateforme de calcul Grid'5000.

Les systèmes d'information (S.I.) d'entreprise se construisent à partir de progiciels configurés, intégrés et déployés dans des organisations en mouvement, à l'exemple des ERP ( Enterprise Resource Planning). Les enjeux d'efficacité des projets, d'efficience des usages, de performances opérationnelles, d'alignement aux stratégies d'entreprise sont connus. Ils fondent la problématique de l'intégration organisationnelle et informationnelle, avec la généricité nécessaire à la diffusion des bonnes pratiques et normes, dans une démarche continue mêlant analyse de l'existant, conception et mise en oeuvre par l'organisation. Un cadre d'ingénierie dirigée par les modèles se diffuse progressivement à partir des travaux en modélisation d'entreprise et en système d'information. Ce mémoire propose une approche centrée sur l'intégration organisationnelle et informationnelle afin d'enrichir ce cadre dans les phases de conception, d'intégration et d'usage pour prendre en compte les interdépendances entre les éléments d'un système et entre les points de vue différents sur ce système. Ce cadre étendu repose sur un méta-modèle de l'intégration et une démarche d'alignement entre les points de vue. Il s'appuie sur la théorie des graphes pour définir une « distance » et un « voisinage » permettant de représenter les différentes formes d'intégration qui conditionnent, permettent ou limitent les résultats des projets. L'analyse de différents cas issus de référentiels métiers permet de valider la pertinence du cadre proposé pour enrichir les représentations de ces modèles.

Cette thèse, fruit d'une collaboration LORIA / INRA, porte sur l'étude du raisonnement à partir de cas pour aider à l'interprétation d'organisations spatiales agricoles. Les agronomes effectuent des enquêtes auprès d'exploitants agricoles, afin d'appréhender les relations entre structure spatiale et fonctionnement des exploitations. Des modèles graphiques, appelés chorèmes d'exploitations, permettent de synthétiser ces données d'enquêtes. Sur la base de ces chorèmes, nous avons modélisé l'organisation spatiale des exploitations par des graphes bipartites aux sommets et aux arc étiquetés par des concepts. A certains sous-graphes, décrivant des structures spatiales intéressantes, sont adjoints des explications, décrivant l'organisation fonctionnelle, pour constituer des cas. La modélisation conjointe a abouti à la reconception des chorèmes et à la constitution d'une base de cas et de hiérarchies de concepts du domaine. Le système de RàPC ROSA permet de proposer des explications de fonctionnement à un graphe d'organisation spatiale en utilisant les cas enregistrés. La comparaison des graphes s'appuie sur le mécanisme des logiques de description : étant donné un graphe d'exploitation cible, on lui associe des graphes sources de la base de cas au moyen d'opérations de généralisation et de spécialisation.

L'��tude des marches al ��atoires fait appara��tre des connexions entre leurs propri��t��s alg ebriques, g ��om ��triques ou encore combinatoires et leurs propri��t��s stochastiques. Le premier exemple de telles connexions est donn �� par le th ��or��me de P olya concernant les marches al��atoires aux plus proches voisins sur le groupe Z^N. Si les marches al��atoires sur les groupes - ou sur des espaces homog��nes - fournissent beaucoup d'exemples, il serait appr��ciable d'obtenir de tels r��sultats de rigidit �� sur des structures alg��briques plus faibles telles celles de semi-groupo��de ou de groupo��de. Dans cette th��se il est consid��r�� un exemple de semi-groupo��de et un exemple de groupo��de, tous les deux sont d��fi nis �� partir de sous-graphes contraints du graphe de Cayley d'un groupe - le premier graphe est dirig�� alors que le second ne l'est pas. Pour ce premier exemple, on pr��cise un r��sultat de Campanino et Petritis - ils ont montr�� que la marche al��atoire simple etait transiente pour cet exemple de graphe dirig�� - en d ��terminant la fronti��re de Martin associ ��e �� cette marche et ��tablissant sa trivialit��. Dans le second exemple apparaissant dans ce manuscrit, on consid��re des pavages quasi-p��riodiques de l'espace euclidien obtenus �� l'aide de la m��thode de coupe et projection. Nous consid��rons la marche al��atoire simple le long des ar��tes des polytopes constituant le pavage, et nous r epondons a la question du type de celle-ci, c'est-��-dire nous d��terminons si elle est r��currente ou transiente. Nous montrons ce r esultat en etablissant des in egalit es isop erim etriques. Cette strat egie permet d'obtenir des estim��es de la vitesse de d ecroissance du noyau de la chaleur, ce que n'aurait pas permis l'utilisation d'un crit��re de type Nash-Williams.