Dans cette thèse, nous avons étudié les problèmes de décisions séquentielles, avec comme application la gestion de stocks d'énergie. Traditionnellement, ces problèmes sont résolus par programmation dynamique stochastique. Mais la grande dimension, et la non convexité du problème, amènent à faire des simplifications sur le modèle pour pouvoir faire fonctionner ces méthodes. Nous avons donc étudié une méthode alternative, qui ne requiert pas de simplifications du modèle: Monte Carlo Tree Search (MCTS). Nous avons commencé par étendre le MCTS classique (qui s'applique aux domaines finis et déterministes) aux domaines continus et stochastiques. Pour cela, nous avons utilisé la méthode de Double Progressive Widening (DPW), qui permet de gérer le ratio entre largeur et profondeur de l'arbre, à l'aide de deux méta paramètres. Nous avons aussi proposé une heuristique nommée Blind Value (BV) pour améliorer la recherche de nouvelles actions, en utilisant l'information donnée par les simulations passées. D'autre part, nous avons étendu l'heuristique RAVE aux domaines continus. Enfin, nous avons proposé deux nouvelles méthodes pour faire remonter l'information dans l'arbre, qui ont beaucoup amélioré la vitesse de convergence sur deux cas tests. Une part importante de notre travail a été de proposer une façon de mêler MCTS avec des heuristiques rapides pré-existantes. C'est une idée particulièrement intéressante dans le cas de la gestion d'énergie, car ces problèmes sont pour le moment résolus de manière approchée. Nous avons montré comment utiliser Direct Policy Search (DPS) pour rechercher une politique par défaut efficace, qui est ensuite utilisée à l'intérieur de MCTS. Les résultats expérimentaux sont très encourageants. Nous avons aussi appliqué MCTS à des processus markoviens partiellement observables (POMDP), avec comme exemple le jeu de démineur. Dans ce cas, les algorithmes actuels ne sont pas optimaux, et notre approche l'est, en transformant le POMDP en MDP, par un changement de vecteur d'état. Enfin, nous avons utilisé MCTS dans un cadre de méta-bandit, pour résoudre des problèmes d'investissement. Le choix d'investissement est fait par des algorithmes de bandits à bras multiples, tandis que l'évaluation de chaque bras est faite par MCTS. Une des conclusions importantes de ces travaux est que MCTS en continu a besoin de très peu d'hypothèses (uniquement un modèle génératif du problème), converge vers l'optimum, et peut facilement améliorer des méthodes suboptimales existantes.

Le principal but de notre recherche a été de caractériser les individus connectés dans un réseau social en analysant la structure locale du réseau. Pour cela, nous avons proposé une méthode qui décrit la façon dont un noeud (correspondant à un individu) est intégré dans le réseau. Notre méthode est liée à l'analyse de réseaux égocentrés en sociologie et à l'approche locale dans l'étude des grands graphes de terrain. Elle peut être appliquée à des petits réseaux, à des fractions de réseaux et aussi à des grands réseaux, grâce à sa petite complexité. Nous avons appliqué la méthode proposée à deux grands réseaux sociaux, un modélisant des activités enligne sur MySpace, l'autre modélisant des communications par téléphone mobile. Dans le premier cas nous nous sommes intéressés à l'analyse de la popularité enligne des artistes sur MySpace. Dans le deuxième cas, nous avons proposé et avons utilisé une méthode pour regrouper les noeuds qui sont connectés au réseau de façon similaire. Nous avons constaté que la distribution des utilisateurs de téléphone mobile dans des groupes était corrélée à d'autres caractéristiques des individus (intensité de communication et 'âge). Bien que dans cette thèse nous ayons appliqué les deux méthodes seulement aux réseaux sociaux, elles peuvent être appliquées de la même manière à tout autre graphe, peu importe son origine.

Nous proposons une nouvelle structure de données distribuée et scalable appelée LH*RSP2P conçue pour les environnements pair à pair(P2P).Les données de l'application forment un fichier d’enregistrements identifiés par les clés primaires. Les enregistrements sont dans des cases mémoires sur des pairs, adressées par le hachage distribué (LH*). Des éclatements créent dynamiquement de nouvelles cases pour accommoder les insertions. L'accès par clé à un enregistrement comporte un seul renvoi au maximum. Le scan du fichier s’effectue au maximum en deux rounds. Ces résultats sont parmi les meilleurs à l'heure actuelle. Tout fichier LH*RSP2P est également protégé contre le Churn. Le calcul de parité protège toute indisponibilité jusqu’à k cases, où k ≥ 1 est un paramètre scalable. Un nouveau type de requêtes, qualifiées de sûres, protège également contre l’accès à toute case périmée. Nous prouvons les propriétés de notre SDDS formellement par une implémentation prototype et des expérimentations. LH*RSP2P apparaît utile aux applications Big Data, sur des RamClouds tout particulièrement / We propose a new scalable and distributed data structure termed LH*RSP2P designed for Peer-to-Peer environment (P2P). Application data forms a file of records identified by primary keys. Records are in buckets on peers, addressed by distributed linear hashing (LH*). Splits create new buckets dynamically, to accommodate inserts. Key access to a record uses at most one hop. Scan of the file proceeds in two rounds at most. These results are among best at present. An LH*RSP2P file is also protected against Churn. Parity calculation recovers from every unavailability of up to k≥1, k is a scalable parameter. A new type of queries, qualified as sure, protects also against access to any out-of-date bucket. We prove the properties of our SDDS formally, by a prototype implementation and experiments. LH*RSP2P appears useful for Big Data manipulations, over RamClouds especially.

Cette thèse vise à développer des stratégies permettant d'augmenter la puissance du calcul séquentiel et des systèmes distribués, elle traite en particulier, la décomposition séquentielle des opérations ainsi que des systèmes d'édition collaboratifs décentralisés. La croissance rapide de l'utilisation des nouvelles technologies informatiques résulte de la nécessité d'avoir des performances élevées, dans tout domaine lié au calcul informatique. Une telle quête de performances a abouti à une plus grande complexité dans les architectures informatiques, conduisant à un stress non négligeable dans la technologie des compilateurs. De puissants microprocesseurs se trouvent au cœur de toute machine informatique, allant des serveurs et ordinateurs personnels, aux ordinateurs portables, jusqu'aux téléphones cellulaires " iPhone ". En effet, l'augmentation incessante des performances constitue un défi permanent dans les sciences informatiques. Par ailleurs, le développement rapide des réseaux informatiques a conduit à un progrès vers une édition collaborative en temps réel (RCE). Cette dernière permet à des groupes d'utilisateurs l'édition simultanée de documents partagés résidant dans des sites physiques dispersés, mais interconnectés par un réseau informatique. Dans de tels systèmes distribués, les conflits liés aux communications sont un défi à relever. De ce fait, la communication indexée devient une nécessité absolue. Nous introduisons, une méthode d'indexage avec précision contrôlée. Celle-ci permet la génération d'identifiants uniques utilisés dans l'indexage des communications dans les systèmes distribués, plus particulièrement dans les systèmes d'édition collaboratifs décentralisés. Ces identifiants sont des nombres réels avec un motif de précision contrôlé. Un ensemble fini d'identifiants est conservé pour permettre le calcul de cardinalités locales et globales. Cette propriété joue un rôle prépondérant dans la gestion des communications indexées. De plus, d'autres propriétés incluant la préservation de l'ordre sont observées. La méthode d'indexage a été testée et vérifiée avec succès. Ceci a permis la conception d'un système d'édition collaboratif décentralisé. Aussi, nous explorons les stratégies existantes, relatives a la décomposition séquentielle d'opérations, que nous étendons à de nouvelles stratégies. Ces stratégies mènent à une optimisation (processeur, compilateur, mémoire, code). Ces styles de décomposition portent un intérêt majeur à la communauté scientifique. Des recherches et des implémentations de plus en plus rapides résultent de la conception d'unité arithmétique.

Medical images have been used to depict the anatomy or function. Their high-dimensionality and their non-linearity nature makes their analysis a challenging problem. In this thesis, we address the medical image analysis from the viewpoint of statistical learning theory. First, we examine regularization methods for analyzing MRI data. In this direction, we introduce a novel regularization method, the k-support regularized Support Vector Machine. This algorithm extends the 1 regularized SVM to a mixed norm of both '1 and '2 norms. We evaluate our algorithm in a neuromuscular disease classification task. Second, we approach the problem of graph representation and comparison for analyzing medical images. Graphs are a technique to represent data with inherited structure. Despite the significant progress in graph kernels, existing graph kernels focus on either unlabeled or discretely labeled graphs, while efficient and expressive representation and comparison of graphs with continuous high-dimensional vector labels, remains an open research problem. We introduce a novel method, the pyramid quantized Weisfeiler-Lehman graph representation to tackle the graph comparison problem for continuous vector labeled graphs. Our algorithm considers statistics of subtree patterns based on the Weisfeiler-Lehman algorithm and uses a pyramid quantization strategy to determine a logarithmic number of discrete labelings. We evaluate our algorithm on two different tasks with real datasets. Overall, as graphs are fundamental mathematical objects and regularization methods are used to control ill-pose problems, both proposed algorithms are potentially applicable to a wide range of domains.

Dans cette thèse, nous explorons la complexité algorithmique de plusieurs problèmes issus de la génomique comparative, et nous apportons des solutions à certains de ces problèmes sous la forme d'algorithmes d'approximation ou paramétrés. Le dénominateur commun aux problèmes soulevés est la mise en commun d'informations génomiques provenant de plusieurs espèces dans le but de tirer des conclusions pertinentes pour l'étude de ces espèces. Les problèmes de tri par transpositions et de tri par inversions pré xes permettent de retrouver l'histoire évolutive des deux espèces. Les problèmes de distance exemplaire et de plus petite partition commune ont pour but de comparer deux génomes dans les cas algorithmiquement di ciles où chaque gène apparait avec plusieurs copies indistinguables dans le génome. En n, les problèmes d'extraction de bandes et de linéarisation visent à préciser ou corriger l'information génomique a n qu'elle soit plus pertinente pour des traitements ultérieurs. Les résultats principaux que nous présentons sont la NP-di culté des problèmes de tri (par transpositions et par inversions pré xes) dont la complexité est restée longtemps une question ouverte; une étude complète de la complexité du calcul des distances exemplaires; un algorithme paramétré pour le calcul de plus petite partition commune (avec un unique paramètre étant la taille de la partition); une étude à la fois large et approfondie des problèmes d'extraction de bandes et en n une nouvelle structure de données permettant de résoudre plus e cacement le problème de linéarisation.

Ces dernières années, les ontologies ont suscité de nombreux travaux dans le domaine du web sémantique. Elles sont utilisées pour fournir le vocabulaire sémantique permettant de rendre la connaissance du domaine disponible pour l'échange et l'interprétation au travers des systèmes d'information. Toutefois, en raison de la nature décentralisée du web sémantique, les ontologies sont très hétérogènes. Cette hétérogénéité provoque le problème de la variation de sens ou ambiguïté dans l'interprétation des entités et, par conséquent, elle empêche le partage des connaissances du domaine. L'alignement d'ontologies, qui a pour but la découverte des correspondances sémantiques entre des ontologies, devient une tâche cruciale pour résoudre ce problème d'hétérogénéité dans les applications du web sémantique. Les principaux défis dans le domaine de l'alignement d'ontologies ont été décrits dans des études récentes. Parmi eux, la sélection de mesures de similarité appropriées ainsi que le réglage de la configuration de leur combinaison sont connus pour être des problèmes fondamentaux que la communauté doit traiter. En outre, la vérification de la cohérence sémantique des correspondances est connue pour être une tâche importante. Par ailleurs, la difficulté du problème augmente avec la taille des ontologies. Pour faire face à ces défis, nous proposons dans cette thèse une nouvelle approche, qui combine différentes techniques issues des domaines de l'apprentissage automatique, d'appariement de graphes et de recherche d'information en vue d'améliorer la qualité de l'alignement d'ontologies. En effet, nous utilisons des techniques de recherche d'information pour concevoir de nouvelles mesures de similarité efficaces afin de comparer les étiquettes et les profils d'entités de contexte au niveau des entités. Nous appliquons également une méthode d'appariement de graphes appelée propagation de similarité au niveau de la structure qui découvre effectivement des correspondances en exploitant des informations structurelles des entités. Pour combiner les mesures de similarité au niveau des entités, nous transformons la tâche de l'alignement d'ontologie en une tâche de classification de l'apprentissage automatique. Par ailleurs, nous proposons une méthode dynamique de la somme pondérée pour combiner automatiquement les correspondances obtenues au niveau des entités et celles obtenues au niveau de la structure. Afin d'écarter les correspondances incohérentes, nous avons conçu une nouvelle méthode de filtrage sémantique. Enfin, pour traiter le problème de l'alignement d'ontologies à large échelle, nous proposons deux méthodes de sélection des candidats pour réduire l'espace de calcul. Toutes ces contributions ont été mises en œuvre dans un prototype nommé YAM++. Pour évaluer notre approche, nous avons utilisé des données du banc d'essai de la compétition OAEI : Benchmark, Conference, Multifarm, Anatomy, Library and Large Biomedical Ontologies. Les résultats expérimentaux montrent que les méthodes proposées sont très efficaces. De plus, en comparaison avec les autres participants à la compétition OAEI, YAM++ a montré sa compétitivité et a acquis une position de haut rang.

Actuellement, la résolution de problèmes d'optimisation sous contraintes tire rarement parti de la structure du problème trait. Or, il existe de nombreux problèmes réels fortement structurés dont la décomposition arborescente pourrait s'avérer très profitable. Les travaux menés jusqu'à présent exploitent les décompositions arborescentes uniquement dans le cadre des méthodes de recherche complète. Dans cette thèse, nous étudions l'apport des décompositions arborescentes pour les méthodes de recherche locale de type VNS (Variable Neighborhood Search), dont l'objectif est de trouver une solution de très bonne qualité en un temps limité. Cette thèse apporte trois contributions. La première est un schéma générique (DGVNS), exploitant la décomposition arborescente pour guider efficacement l'exploration de l'espace de recherche. Trois différentes stratégies visant à équilibrer l'intensification et la diversification de DGVNS sont étudiées et comparées. La seconde contribution propose deux raffinements de la décomposition arborescente. Le premier exploite la dureté des fonctions de coût pour identifier les parties du graphe de contraintes les plus difficiles à satisfaire. Le second raffinement cherche à augmenter la proportion de variables propres dans les clusters. La troisième contribution consiste en deux extensions de DGVNS qui exploitent à la fois le graphe de clusters et les séparateurs. Chaque contribution proposée est évaluée et comparée au travers d'expérimentations menées sur de multiples instances de quatre problèmes réels.

Les décompositions de graphes, lorsqu'elles sont de petite largeur, sont souvent utilisées pour résoudre plus efficacement des problèmes étant difficiles dans le cas de graphes quelconques. Dans ce travail de thèse, nous nous intéressons aux limites liées à ces décompositions, et à la construction d'obstructions certifiant leur grande largeur. Dans une première partie, nous donnons un algorithme généralisant et unifiant la construction d'obstructions pour différentes largeurs de graphes, en temps XP lorsque paramétré par la largeur considérée. Nous obtenons en particulier le premier algorithme permettant de construire efficacement une obstruction à la largeur arborescente en temps O^{tw+4}. La seconde partie de notre travail porte sur l'étude du problème Ensemble [Sigma,Rho]-Dominant, une généralisation des problèmes de domination sur les graphes et caractérisée par deux ensembles d'entiers Sigma et Rho. Les diverses études de ce problème apparaissant dans la littérature concernent uniquement les cas où le problème est FPT, lorsque paramétré par la largeur arborescente. Nous montrons que ce problème ne l'est pas toujours, et que pour certains cas d'ensembles Sigma et Rho, il devient W[1]-difficile lorsque paramétré par la largeur arborescente. Dans la dernière partie, nous étudions la complexité d'un nouveau problème de coloration appelé k-Coloration Additive, combinant théorie des graphes et théorie des nombres. Nous montrons que ce nouveau problème est NP-complet pour tout k >= 4 fixé, tandis qu'il peut être résolu en temps polynomial sur les arbres pour k quelconque et non fixé.

La pratique quotidienne d'une activité génère un ensemble de connaissances qui se traduisent par un savoir-faire, une maîtrise, une compétence qu'une personne acquiert au cours du temps. Pour les préserver, la capitalisation des connaissances est devenue une activité essentielle dans les entreprises. Nos travaux de recherche ont pour objectif de modéliser et mettre en œuvre un système afin d'extraire et de formaliser les connaissances issues des anomalies qui surviennent dans un contexte de production industrielle et de les intégrer dans un framework facilitant la maintenance corrective et préventive. Ce framework structure la connaissance sous la forme de groupes d'anomalies. Ces groupes peuvent être rapprochés des patterns : ils représentent un problème auquel une ou plusieurs solutions sont associées. Ils ne sont pas définis a priori, c'est l'analyse des anomalies passées qui génère des groupes pertinents, qui peuvent évoluer avec l'ajout de nouvelles anomalies. Pour identifier ces patterns, supports de la connaissance, un processus complet d'extraction et de formalisation de la connaissance est suivi, Knowledge Discovery in Databases. Ce processus a été appliqué dans des domaines très variés. Nous lui donnons ici une nouvelle dimension, le traitement d'anomalies et plus particulièrement celles qui surviennent au cours de processus de production industrielle. Les étapes génériques qui le composent, depuis la simple sélection des données jusqu'à l'interprétation des patterns qui supportent les connaissances, sont considérées pour affecter à chacune un traitement spécifique pertinent par rapport à notre contexte applicatif.