Ce travail montre que l'introduction de contraintes dans un modèle de connaissances à objets permet d'en accroître à la fois l'expressivité (les contraintes sont des énoncés déclaratifs de relations entre attributs) et les capacités d'inférence (la maintenance et la résolution des contraintes sont chargées de la cohérence et de la complétion des bases de connaissances). Les répercussions de la présence de contraintes au sein d'un tel système sont également étudiées. Les attributs contraints sont désignés à l'aide de la notion d'accès, qui étend la notion classique de chemin au traitement des attributs multivalués (dont la valeur est un ensemble ou une liste de valeurs). Les niveaux de représentation considérés (concept, classe, instance) définissent la portée d'une contrainte comme l'ensemble des objets sur lesquels elle doit être posée, et induisent alors entre eux un héritage de ce trait descriptif. De même, le maintien d'un certain degré de consistance locale sur les domaines des attributs exige une gestion interne de leurs types. Vis-a-vis des mécanismes d'inférence du modèle (instanciation, classification, procédures, etc.), un comportement adapté des contraintes est établi, qui ne remet pas en cause la sémantique de ces mécanismes. Ces principes d'intégration ont été validés dans le modèle de connaissances à objets Tropes. Nous avons réalisé un module de programmation par contraintes, appelé Micro, qui est semi-faiblement couplé à Tropes. Micro répond à de nombreuses exigences de la représentation de connaissances par objets, en gérant la maintenance et la résolution de Problèmes de Satisfaction de Contraintes (CSP) dynamiques, définis sur des variables numériques, booléennes, ou multivaluées, dont les domaines sont finis ou infinis. L'intégration qui a été réalisée autorise, en outre, l'utilisation de la puissance expressive et calculatoire des contraintes par le système de représentation de connaissances lui-même. Ainsi, la présence des contraintes permet d'étendre et de contrôler la sémantique de notions diverses et évoluées comme celles d'objet composite, de tâche, de relation, ou encore de filtre.

L'objectif de cette thèse est le développement d'algorithmes et de modèles permettant l'optimisation d'itinéraires dans les réseaux routiers. Dans un premier temps, ce travail de recherche étudie le problème de l'interception d'un mobile dans un graphe. Dans ce contexte, l'objectif est de calculer un itinéraire optimal permettant de rejoindre une cible mobile dont la trajectoire est connue. Cette problématique est traitée pour plusieurs situations (un poursuivant/un objectif et plusieurs poursuivants/plusieurs objectifs) et pour plusieurs types de graphes (graphes statiques et graphes FIFO). Pour chaque cas, un algorithme de résolution est proposé et l'optimalité du résultat qu'il retourne est démontrée. De plus, un ensemble de simulations est réalisé afin de vérifier l'efficacité des algorithmes en termes de temps de calcul. Dans un deuxième temps, une nouvelle classe de graphes dynamiques est définie : les graphes dynamiques avec intervalles. La particularité de ces graphes est que le poids de chaque arc dépende du temps et qu'il est représenté par un intervalle. Pour ce nouveau type de graphes, le problème du plus court chemin est étudié. Ce problème peut être vu soit en tant que problème d'optimisation monocritère soit en tant que problème d'optimisation multicritère. Pour chaque cas, le problème est formulé et des approches pour la résolution sont proposées.

Cette these traite d'un ensemble de problemes lies a l'acheminement des messages dans les machines paralleles a memoire distribuee. L'accent est mis sur des solutions extensibles qui necessitent un nombre de ressources independant de la taille de la machine. A travers l'exemple des machines Supernodes (dont les processeurs sont interconnectes par un reseau de Clos 3-etages) nous montrons que l'acheminement des messages par reconfiguration dynamique est difficilement envisageable dans des machines de grande taille. Nous nous interessons ensuite au routage des messages dans des reseaux a topologie quelconque, et proposons une nouvelle methode de generation de fonctions de routage sans interblocage. La nouvelle generation des machines paralleles integre de plus en plus de fonctions dans le materiel, notamment le routage des messages. Pour que cette integration soit la plus efficace possible, des methodes nouvelles de representation compacte de l'information de routage sont necessaires. Santoro et Khatib ont propose une methode, le routage par intervalles, bien adaptee aux reseaux generaux. La deuxieme partie de cette these s'inscrit dans la continuite de ce type de travail et propose de nouvelles methodes de generation de fonctions de routage par intervalles. Deux cas sont consideres : le tore, et les reseaux generaux. Nous insistons plus particulierement sur des solutions sans interblocage, caracteristique rarement prise en compte. De plus dans le cas du tore, les longueurs des chemins sont proches des optima. Enfin, nous proposons une extension de la notion de routage par intervalles, le schema d'etiquetage etendu (SEE), permet de representer un spectre plus large de fonctions de routage.

Cette thèse est dédiée au développement et à l'application de méthodes ensemblistes pour l'estimation d'état et de paramètres pour des systèmes non-linéaires. Deux types de modèles sont considérés : modèles donnés par des fonctions explicites à variables complexes et modèles décrits par des équations différentielles ordinaires (EDOs). L'identification de paramètres de modèles décrits par des fonctions explicites est réalisée à l'aide des techniques d'inversion ensembliste par analyse par intervalles. Par ailleurs, les modèles utilisés sont à variables complexes ; dans ce cas l'évaluation de la sortie se fait à l'aide d'intervalles complexes. Dans ce travail, nous avons développé une arithmétique des intervalles complexes basée sur la représentation polaire. La multiplication et la division sont des opérations exactes, mais la somme et la différence ne le sont pas. Pour réduire le pessimisme introduit par ces dernières opérations, nous avons développé des algorithmes assurant les propriétés de minimalité. Cette bibliothèque a été associée aux méthodes d'inversion ensembliste dans le cadre de l'estimation de paramètres de modèles diélectriques, d'une part, et pour l'identification de paramètres thermophysiques d'autre part. Dans la deuxième partie de cette thèse, des algorithmes d'estimation d'état pour des systèmes décrits par des équations différentielles sont présentés. Ils permettent de fournir, à chaque instant, un ensemble contenant d'une manière garantie, toutes les valeurs du vecteur d'état compatibles avec les mesures et avec les bornes d'erreurs. Ces estimateurs sont basés sur des méthodes d'intégration garantie d'EDOs et sur l'inversion ensembliste. Enfin, une technique d'estimation de paramètres de modèles décrits par des EDOs est proposée.

Cette thèse est consacrée à l'identification et à la commande de machines parallèles (robot H4 du LIRMM). Les robots parallèles possèdent une dynamique élevée ce qui impose de lois de commande capables de prendre en compte cette dynamique. Ces lois sont bassées sur le modèle dynamique du robot et les paramètres dynamiques doivent être estimés d'abord. Nous avons proposé deux approches pour identifier ces paramètres : une première approche par moindres carrés pondérés et une deuxième approche dans un contexte à erreur bornée qui fourni un ensemble solution garantie. Dans ce dernier cas deux méthodologies sont mises en œuvre : estimation ellipsoïdale et estimation par intervalles. Une analyse expérimentale comparative des trois méthodes pour l'estimation des 14 paramètres du robot est alors presentée. Les paramètres sont alors utilisés pour la synthèse d'une commande prédictive fonctionnelle référencée sur un modèle linéaire. Une méthodologie originale a été développée : d´abord l'identification du modèle dynamique et linéarisation du système, puis l'identification du modèle interne pour la commande prédictive et synthèse de cette commande avec pré-bouclage en vitesse afin de stabiliser le processus linéarisé. Cette commande est comparée à deux stratégies classiques utilisées en robotique : la commande PID et la commande dynamique. Les performances de ces commandes ont été testées lors de mouvements simples et complexes. La stratégie prédictive fournit de meilleures réponses en termes de dynamique, précision et robustesse.

La conception architecturale de systèmes mécaniques et énergétiques permet d'étudier la faisabilité de concepts préalablement choisis pendant la phase de recherche de concepts. Elle fait partie de la phase de conception préliminaire et son achèvement vise à définir l'architecture globale qui sera étudiée pendant la phase de conception détaillée d'un produit. Les principales caractéristiques d'un produit (dimensions, choix de composants, de formes, de topologies ou de matériaux) sont alors fondamentales à ce stade de la conception. La conception architecturale nécessite aussi la prise en compte des comportements physiques et des interactions du produit, de ses composants et des milieux extérieurs, de critères économiques, environnementaux, etc. suivant les exigences du cahier des charges fonctionnel. Le concepteur définit un modèle mathématique exprimant cette connaissance liée au produit. Ce modèle peut être traité à l'aide d'un solveur de Problèmes de Satisfaction de Contraintes numériques (CSP). Ce type de solveur traite de manière générique des problèmes formulés à l'aide de contraintes, de variables et de domaines. Nous proposons de nouveaux algorithmes et de nouvelles heuristiques qui prennent en compte des besoins spécifiques au concepteur en conception préliminaire, comme : la classification des variables, les précisions relatives aux valeurs de certaines variables, les contraintes par morceaux. Les études de faisabilité de plusieurs systèmes mécaniques et énergétiques ont été réalisées avec succès. Les nouveaux algorithmes ont permis de diminuer significativement les temps de calculs, mais ils ont aussi permis d'améliorer la qualité des solutions calculées au regard des besoins du concepteur.

Ce mémoire a pour vocation de prouver aux membres du jury ma capacité à diriger des recherches. Il est organisé de la manière suivante : La première partie regroupe mon curriculum vitae, et une liste de publications. Le chapitre 2 est une présentation générale d'une partie des travaux que j'ai initié au cours de la dernière décennie. Dans un souci de cohérence d'ensemble je n'ai présenté que les travaux relatifs à la commande de systèmes (max,+) linéaires. Ils constituent le dénominateur commun aux trois thèses que j'ai encadrées. Ce chapitre inclut quelques nouveautés à l'attention du lecteur averti, notamment la synthèse d'un observateur d'état est introduite pour la première fois ici. Il se termine sur la présentation de quelques perspectives de recherche. La troisième partie regroupe quelques publications qui permettront au lecteur de retrouver les preuves des résultats énoncés dans le second chapitre.

Nous proposons de modéliser les données issues des technologies de séquençage du transcriptome (RNA-Seq) à l'aide de la loi binomiale négative, et nous construisons des modèles de segmentation adaptés à leur étude à différentes échelles biologiques, dans le contexte où ces technologies sont devenues un outil précieux pour l'annotation de génome, l'analyse de l'expression des gènes, et la détection de nouveaux transcrits. Nous développons un algorithme de segmentation rapide pour analyser des séries à l'échelle du chromosome, et nous proposons deux méthodes pour l'estimation du nombre de segments, directement lié au nombre de gènes exprimés dans la cellule, qu'ils soient précédemment annotés ou détectés à cette même occasion. L'objectif d'annotation précise des gènes, et plus particulièrement de comparaison des sites de début et fin de transcription entre individus, nous amène naturellement à nous intéresser à la comparaison des localisations de ruptures dans des séries indépendantes. Nous construisons ainsi dans un cadre de segmentation bayésienne des outils de réponse à nos questions pour lesquels nous sommes capable de fournir des mesures d'incertitude. Nous illustrons nos modèles, tous implémentés dans des packages R, sur des données RNA-Seq provenant d'expériences sur la levure, et montrons par exemple que les frontières des introns sont conservées entre conditions tandis que les débuts et fin de transcriptions sont soumis à l'épissage différentiel.

Nous présentons un ensemble de résultats concernant deux types de problèmes biologiques: (1) la comparaison de structures de molécules d'ARN et (2) le calcul de distances intergénomiques en présence de gènes dupliqués. Dans ce manuscrit, nous déterminons la complexité algorithmique de certains problèmes liés soit à la comparaison de structures de molécules d'ARN (distance d'édition, problème APS, recherche de motifs de 2-intervalles, design d'ARN), soit aux réarrangements génomiques (distances de breakpoints et d'intervalles conservés). \\ L'approche adoptée pour l'ensemble de ces problèmes a été de déterminer, si possible, des algorithmes exacts et rapides répondants aux problèmes posés. Pour tout problème pour lequel cela ne semblait pas possible, nous avons essayé de prouver qu'il ne peut être résolu de fa\ccon rapide. Pour ce faire, nous démontrons que le problème en question est algorithmiquement difficile. Enfin, le cas échéant, nous poursuivons l'étude de ce problème en proposant, essentiellement, trois types de résultats: (1) Approximation, (2) Complexité paramétrée, (3) Heuristique. Nous utilisons, dans ce manuscrit, des notions d'optimisation combinatoire, de mathématique, de théorie des graphes et d'algorithmique.

Dans cette thèse nous proposons une nouvelle formulation de la procédure de détection et d'isolation de défauts provenant des actionneurs pour les systèmes dynamiques. Habituellement, un système de commande se compose de trois parties : les capteurs, le procédé et les actionneurs. L'actionneur est un dispositif interne avec sa propre structure et ses caractéristiques dynamiques. Dans la majorité des études, il est considéré tout simplement et d'une manière approximative comme des coefficients constants, mais ce type de formulation d'actionneur n'est pas efficace pour l'identification exacte des défauts issus des organes de commande pour les systèmes réels. Dans le but de s'approcher de la réalité et aussi pour améliorer l'efficacité du diagnostic, nous allons considérer l'actionneur comme un sous-système connecté en cascade avec le procédé. En utilisant cette nouvelle formulation, les défauts actionneurs peuvent être modélisés en les considérant comme étant un changement au niveau des paramètres internes de ce sous-système actionneur. Nous supposons que la sortie de l'actionneur qui représente aussi l'entrée du système dynamique est non mesurable, donc nous allons obtenir l'information sur les défauts actionneurs seulement à partir de la variable de sortie du procédé. Une question intéressante peut se poser lors de l'implantation de la procédure de diagnostic des défauts actionneurs: est ce que l'information sur les défauts actionneurs peut être complètement vue à la sortie du système dynamique ? Cet apport informationnel constitue le problème primordial pour concevoir la procédure de diagnostic désirée. Pour décrire cette nouvelle reformulation, nous avons introduit quelques notions sur les systèmes inverses et nous avons donné également une condition de rang pour l'inversibilté à gauche des systèmes linéaires. Le but de l'étude de ces notions est de trouver les conditions satisfaisantes qui vont permettre la détection de défauts provenant de l'actionneur. Pour l'isolation des défauts, nous avons utilisé une approche basée sur les observateurs par intervalles. En effet, cette méthode nous a permis d'isoler les défauts d'une manière très rapide. L'ensemble des résultats présentés ont été illustrés par un exemple de simulation sur un réacteur nucléaire montrant l'efficacité de la méthode pour l'isolation de défaut.