Cette thèse s'inscrit dans le domaine de l'optimisation combinatoire. Elle utilise l'approche polyèdrale pour résoudre des problèmes combinatoires qui se posent dans le contexte des réseaux de télécommunications. Nous introduisons et étudions le problème de synthèse de réseaux à composantes connexes unicycliques. Après avoir rappelé que le problème est facile à résoudre en absence d'autres contraintes, nous étudions de nouvelles variantes en intégrant de nouvelles contraintes techniques. Nous commençons par une contrainte portant sur la taille des cycles. Nous souhaitons interdire tous les cycles contenant au plus $p$ sommets. Le problème est alors NP-Difficile. Des inégalités valides sont alors proposées pour ce problème. On montre sous des conditions bien précises que ces inégalités peuvent être des facettes. Plusieurs algorithmes polynomiaux ont été proposés pour la séparation des inégalités valides. Ces algorithme sont mis en oeuvre et des résultats numériques sont donnés. Nous nous focalisons par la suite sur un nouveau problème dit de Steiner consistant à partitionner un réseau en composantes unicycliques tout en imposant que certains sommets soient sur les cycles. On montre alors que ce problème est facile au sens de la complexité algorithmique en proposant un algorithme polynomial et une formulation étendue du problème. On présente également une description partielle de l'enveloppe convexe des vecteurs d'incidence de ces réseaux. La séparation des inégalités est également étudiée. Nous proposons notamment une généralisation de l'algorithme de Padberg-Rao pour séparer les inégalités Blossom. D'autres contraintes techniques sont prises en compte : contraintes de degrés, contrainte sur le nombre de composantes connexes, appartenance de certains sommets à une même composante connexe et enfin la séparation de certains sommets qui doivent être sur des composantes différentes. Enfin, nous faisons une étude spectrale de deux classes spécifiques de graphes unicycliques.

La sélection d'un modèle approprié est l'une des tâches essentielles de l'apprentissage statistique. En général, pour une tâche d'apprentissage donnée, on considère plusieurs classes de modèles ordonnées selon un certain ordre de " complexité". Dans ce cadre, le processus de sélection de modèle revient 'a trouver la " complexité " optimale, permettant d'estimer un modèle assurant une bonne généralisation. Ce problème de sélection de modèle se résume à l'estimation d'un ou plusieurs hyper-paramètres définissant la complexité du modèle, par opposition aux paramètres qui permettent de spécifier le modèle dans la classe de complexité choisie. L'approche habituelle pour déterminer ces hyper-paramètres consiste à utiliser une " grille ". On se donne un ensemble de valeurs possibles et on estime, pour chacune de ces valeurs, l'erreur de généralisation du meilleur modèle. On s'intéresse, dans cette thèse, à une approche alternative consistant à calculer l'ensemble des solutions possibles pour toutes les valeurs des hyper-paramètres. C'est ce qu'on appelle le chemin de régularisation. Il se trouve que pour les problèmes d'apprentissage qui nous intéressent, des programmes quadratiques paramétriques, on montre que le chemin de régularisation associé à certains hyper-paramètres est linéaire par morceaux et que son calcul a une complexité numérique de l'ordre d'un multiple entier de la complexité de calcul d'un modèle avec un seul jeu hyper-paramètres. La thèse est organisée en trois parties. La première donne le cadre général des problèmes d'apprentissage de type SVM (Séparateurs à Vaste Marge ou Support Vector Machines) ainsi que les outils théoriques et algorithmiques permettant d'appréhender ce problème. La deuxième partie traite du problème d'apprentissage supervisé pour la classification et l'ordonnancement dans le cadre des SVM. On montre que le chemin de régularisation de ces problèmes est linéaire par morceaux. Ce résultat nous permet de développer des algorithmes originaux de discrimination et d'ordonnancement. La troisième partie aborde successivement les problèmes d'apprentissage semi supervisé et non supervisé. Pour l'apprentissage semi supervisé, nous introduisons un critère de parcimonie et proposons l'algorithme de chemin de régularisation associé. En ce qui concerne l'apprentissage non supervisé nous utilisons une approche de type " réduction de dimension ". Contrairement aux méthodes à base de graphes de similarité qui utilisent un nombre fixe de voisins, nous introduisons une nouvelle méthode permettant un choix adaptatif et approprié du nombre de voisins.

Cette thèse traite du problème de la redistribution dynamique parallèle efficace de la charge pour les problèmes numériques de très grande taille. Nous présentons tout d'abord un état de l'art des algorithmes permettant de résoudre les problèmes du partitionnement, du repartitionnement, du placement statique et du re-placement. Notre première contribution vise à étudier, dans un cadre séquentiel, les caractéristiques algorithmiques souhaitables pour les méthodes parallèles de repartitionnement. Nous y présentons notre contribution à la conception d'un schéma multi-niveaux k-aire pour le calcul sequentiel de repartitionnements. La partie la plus exigeante de cette adaptation concerne la phase d'expansion. L'une de nos contributions majeures a été de nous inspirer des méthodes d'influence afin d'adapter un algorithme de raffinement par diffusion au problème du repartitionnement.Notre deuxième contribution porte sur la mise en oeuvre de ces méthodes sur machines parallèles. L'adaptation du schéma multi-niveaux parallèle a nécessité une évolution des algorithmes et des structures de données mises en oeuvre pour le partitionnement. Ce travail est accompagné d'une analyse expérimentale, qui est rendue possible grâce à la mise en oeuvre des algorithmes considérés au sein de la bibliothèque Scotch.

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

La technique de changement d'échelles a été largement développée dans la littérature pour décrire le comportement global des milieux granulaires en prenant en compte leurs propriétés locales. Cette technique considère classiquement deux échelles : l'échelle macroscopique du volume élémentaire représentatif et l'échelle microscopique du contact entre particules. Le défi majeur de ce changement d'échelles "micro-macro" réside dans la définition de la déformation macroscopique : en effet, si la contrainte macroscopique peut être clairement définie à partir des forces de contact, il a été montré qu'il n'était pas approprié de déduire la déformation macroscopique à partir de la cinématique aux contacts. Dans ce cadre, ce travail propose d'introduire une troisième échelle dite mésoscopique. Cette échelle, à laquelle peuvent être définies à la fois contrainte et déformation, est intermédiaire entre les échelles microscopique et macroscopique et permet de palier au défi majeur mentionné ci-dessus. Elle est définie au niveau d'arrangements locaux de particules, appelés sous-domaines, et sa pertinence est étudiée sur la base d'échantillons numériques composés de particules circulaires puis sphériques, simulés par la méthode des éléments discrets. Les milieux bidimensionnels sont géométriquement représentés par un graphe de particules composé de sous-domaines fermés, encore appelés cellules de vide, dont la frontière est constituée de branches connectant les centres de particules en contact : l'échelle mésoscopique est donc définie au niveau de ces cellules de vide fermées. A cette échelle locale, on décrit tout d'abord la structure du milieu en termes de densité et de texture puis l'on définit les variables statique et cinématique locales du milieu en termes de contrainte et déformation. De fortes hétérogénéités des milieux granulaires en termes de structure, déformation et contrainte sont mises en évidence à l'échelle mésoscopique, avec de plus une structuration des hétérogénéités de contraintes et de déformations et une forte corrélation entre ces deux quantités. Concernant les milieux tridimensionnels, une partition en cellules de vide fermées est impossible du fait de la complexité de la structure 3D de ces milieux. On propose donc une méthode de partition du milieu basée sur la distribution des vides en son sein. La méthode consiste en premier lieu en une subdivision du milieu en tétraèdres, par une partition de Delaunay, puis en une association de tétraèdres voisins selon un critère prédéfini en vue de la création de sous-domaines, non fermés, mais au rôle analogue aux sous-domaines fermés de l'étude 2D. Le critère d'association proposé est basé sur le rapport entre la taille des constrictions (vide sur chaque face des tétraèdres) et la taille des pores au voisinage de chaque constriction. Cette méthode d'association constitue donc l'étape préliminaire à l'extension au cas tridimensionnel des résultats obtenus dans le cas bidimensionnel.

Les séquences répétées en tandem sont constituées de motifs adjacents. Elles constituent une classe de séquences génétiques dont font partie microsatellites et minisatellites. Dans cette thèse, nous traitons le problème de la comparaison de séquences répétées en tandem sous un modèle évolutif particulier. Plus précisément, nous nous intéressons au problème de leur alignement dans lequel, en plus des trois opérations classiques, mutation, insertion et délétion, nous considérons l'amplification en tandem et la contraction en tandem. L'amplification copie un facteur de la séquence, c'est-à-dire un ou plusieurs caractère(s), et met le ou les exemplaire(s) du facteur copié à côté du facteur original, la contraction est l'événement inverse. L'amplification (resp. la contraction) est dite « n-aire d'ordre m », si elle copie (resp. retire) m motif(s) n fois. Nous proposons une méthode donnant un score d'alignement, qui est une métrique, entre deux séquences répétées en tandem, sous un modèle comprenant les cinq opérations précédemment citées où l'amplification et la contraction sont unaires d'ordre 1. Le problème est difficile car les opérations ne sont pas commutatives. Notre solution fait appel à de l'algorithmique de graphe. Nous avons réalisé un programme nommé MS_Align qui implémente cette méthode. Il s'agit du premier programme capable d'aligner des cartes de minisatellites. À l'aide de ce programme, nous avons étudié des données biologiques provenant du minisatellite humain MSY1. Comme nous le montrons, notre modèle évolutif s'applique bien à ce type de séquences d'ADN. Nous avons construit à partir de nos résultats des arbres phylogénétiques semblables à ceux obtenus grâce à d'autres marqueurs du chromosome Y indépendants de MSY1, nos arbres offrent une meilleure résolution. Une partie de cette thèse est consacrée au problème général où nous relaxons les contraintes sur les amplifications et contractions.

Pour modéliser au mieux les phénomènes linguistiques dans les systèmes de traitement automatique des langues (traduction, analyse, etc.), il faut disposer de ressources de qualité. Or, les ressources existantes sont souvent incomplètes et ne permettent pas de traiter correctement les données. Cette thèse s'intéresse à l'acquisition de connaissances linguistiques, plus précisément à leur extraction à partir de corpus. Nous étudions en particulier le problème des collocations, ces couples de termes dont l'un est choisi en fonction de l'autre pour exprimer un sens particulier (comme " pluie battante " où " pluie " exprime l'intensification). Pour permettre l'acquisition de données à grande échelle, il faut la rendre facile à réaliser de manière automatique, et simple à paramétrer par des linguistes aux connaissances limitées en programmation ; cela nécessite une modélisation adaptée et précise des données et des processus. Nous avons réalisé et décrivons MuLLinG, modèle de graphes linguistiques multiniveau, où chaque niveau représente l'information d'une manière différente,et les opérations de manipulation de ces graphes. Ce modèle permet de représenter et traiter divers types de ressources. En effet, les opérations associées ont été écrites pour être les plus génériques possibles : elles sont indépendantes de ce que peuvent représenter les nœuds et les arcs du graphe, et de la tâche à réaliser. Cela permet à notre modèle, mis en œuvre et utilisé pour plusieurs expérimentations (entre autres l'extraction de collocations), de voir un processus parfois complexe d'extraction de connaissances linguistiques comme une succession d'opérations simples de manipulation de graphes.

Le but de cette thèse est d'exploiter efficacement le parallélisme présent dans les applications informatiques séquentielles afin de bénéficier des performances fournies par les multiprocesseurs, en utilisant une nouvelle méthodologie pour la parallélisation automatique des tâches au sein des compilateurs. Les caractéristiques clés de notre approche sont la prise en compte des contraintes de ressources et le caractère statique de l'ordonnancement des tâches. Notre méthodologie contient les techniques nécessaires pour la décomposition des applications en tâches et la génération de code parallèle équivalent, en utilisant une approche générique qui vise différents langages et architectures parallèles. Nous implémentons cette méthodologie dans le compilateur source-à-source PIPS. Cette thèse répond principalement à trois questions. Primo, comme l'extraction du parallélisme de tâches des codes séquentiels est un problème d'ordonnancement, nous concevons et implémentons un algorithme d'ordonnancement efficace, que nous nommons BDSC, pour la détection du parallélisme ; le résultat est un SDG ordonnancé, qui est une nouvelle structure de données de graphe de tâches. Secondo, nous proposons une nouvelle extension générique des représentations intermédiaires séquentielles en des représentations intermédiaires parallèles que nous nommons SPIRE, pour la représentation des codes parallèles. Enfin, nous développons, en utilisant BDSC et SPIRE, un générateur de code que nous intégrons dans PIPS. Ce générateur de code cible les systèmes à mémoire partagée et à mémoire distribuée via des codes OpenMP et MPI générés automatiquement.

Les sciences qui traitent de la réalité, qu'elles soient naturelles, de la société ou de la vie, fonctionnent avec des modèles. Une partie de ces modèles décrivent les relations entre certaines grandeurs mesurables de la réalité, sans aller jusqu'au détail des interactions entre les éléments qui la composent. D'autres modèles décrivent ces interactions en prenant le point de vue des individus qui constituent le système, le comportement global n'est alors plus décrit à priori, mais observé à posteriori. Nous faisons le constat que dans les deux cas le scientifique a peu de liberté pour décrire les structures, en particulier spatiales, susceptibles de porter ces interactions. Nous proposons une approche de modélisation que l'on peut situer à mi-chemin entre les deux, et qui incite à étudier un système à travers la nature de ses interactions et des structures de graphes qui peuvent les porter. En plaçant au même niveau les relations spatiales, fonctionnelles, sociales ou hiérarchiques, nous tentons aussi de nous affranchir des contraintes induites par le choix effectué souvent à priori d'une forme de représentation de l'espace. Nous avons formalisé les concepts de base de cette approche, et ceux-ci ont constitué les éléments d'un langage métier, nommé Ocelet, que nous avons défini. Les outils permettant la mise en œuvre de ce langage ont été développés et intégrés sous la forme d'un environnement de modélisation et de simulation. Enfin nous avons pu expérimenter notre nouvelle approche de modélisation et le langage Ocelet à travers la réalisation de plusieurs modèles présentant des situations variées de dynamiques paysagères