Nous proposons une méthode pour aider les administrateurs des applications XML dans la tâche de faire évoluer des schémas en préservant la cohérence de la base de données sans la modifier.<br />L'utilisateur donne au système ce qu'il souhaite comme nouveau document devant être accepté par le schéma.<br />À partir de ce document, le système construit des schémas candidats, qui d'une part préservent la validité de la base de documents et, d'autre part augmentent la classe de documents acceptée par le schéma.<br />L'approche est implantée par un algorithme appelé GREC. <br />Cet algorithme utilise l'automate d'arbre A qui accepte le langage défini par le schéma pour trouver les informations nécessaires à la modification. <br />Plus précisément, il utilise les expressions régulières des règles de transitions de A pour proposer les candidats.<br />Ainsi, les modifications sont faites sur les graphes qui représentent les automates d'états finis construits à partir des expressions régulières concernées.<br />Les expressions régulières engendrées par GREC représentent des schémas présentés à l'utilisateur afin qu'il choisisse le plus adapté à la sémantique de son application.

Les systèmes sensorimoteurs autonomes, placés dans des environnements dynamiques, doivent répondre continuellement à la question ultime: comment contrôler les commandes motrices à partir des entrées sensorielles? Répondre à cette question est un problème très complexe, principalement à cause de l'énorme quantité d'informations qui doit être traitée, tout en respectant plusieurs restrictions: contraintes de temps réel, espace mémoire restreint, et capacité de traitement des données limitée. Un autre défi majeur consiste à traiter l'information incomplète et imprécise, habituellement présente dans des environnements dynamiques. Cette thèse s'intéresse au problème posé par la commande des systèmes sensorimoteurs autonomes et propose un enchaînement d'hypothèses et de simplifications. Ces hypothèses et simplifications sont définies dans un cadre mathématique précis et strict appelé programmation bayésienne, une extension des réseaux bayésiens. L'enchaînement se présente en cinq paliers: utilisation d'états internes; les hypothèses de Markov de premier ordre, de stationnarité et les filtres bayésiens; exploitation de l'indépendance partielle entre les variables d'état; addition d'un mécanisme de choix de comportement;la focalisation de l'attention guidée par l'intention de comportement. La description de chaque étape est suivie de son analyse selon les exigences de mémoire, de complexité de calcul, et de difficulté de modélisation. Nous présentons également des discussions approfondies concernant d'une part la programmation des robots et d'autre part les systèmes cognitifs. Enfin, nous décrivons l'application de ce cadre de programmation à un robot mobile.

Les travaux présentés dans cette thèse ont pour thème la transformation des documents structurés. Un document structuré est une collection d'éléments typés organisée par un ensemble de relations logiques définissant une structure hiérarchique. Ces relations sont définies par des grammaires hors-contexte qui décrivent des classes de documents. L'utilisation des documents structurés permet d'automatiser une partie des traitements effectués sur les documents et contribue également à améliorer leur portabilité en proposant une syntaxe commune définie par des normes (SGML, XML). Les applications utilisant cette représentation souffrent néanmoins de limites liées aux contraintes impliquées par la structuration des documents. L'objectif de ce travail est de répondre à ces limites par des techniques de transformation. Ces techniques ont pour but de modifier la structure d'un ensemble d'éléments typés pour le conformer à d'autres types ou à une nouvelle classe de documents. Cette thèse est articulée en trois parties : 1. Une étude des applications de traitement de documents identifiant les besoins de transformation, plus particulièrement dans le domaine de l'édition interactive. 2. Une évaluation des techniques et outils existant conduisant à une classific- ation des approches (filtres, transformation explicite ou automatique). Chaque classe fait l'objet d'une étude théorique, d'une étude des systèmes disponibles et d'une expérimentation. 3. Une proposition de méthode de transformation combinant les différentes techniques pour tirer parti de leurs points forts et répondre aux limitations de chacune. Cette méthode est fondée sur un algorithme de transformation automatique paramétré à l'aide de pré-couples explicites. Ce travail a conduit au développement des systèmes de transformation aujourd'h- ui intégrés dans des logiciels du projet Opéra (Thot, Byzance) et du consortiu- m W3C (Amaya).

Ce travail propose une approche originale pour l'ordonnancement de tâches sous contraintes de temps et de ressources. Les méthodes et techniques développées s'inscrivent dans la problématique de l'"Analyse Sous Contraintes" (A.S.C.) des problèmes d'ordonnancement. Cette A.S.C. vise à caractériser les ordonnancements admissibles de manière à proposer au décideur un choix d'actions cohérentes vis-à-vis des contraintes, tout en lui offrant une certaine flexibilité face à des aléas éventuels. L'A.S.C. est décrite comme un processus d'inférence mettant en interaction une base de règles et une base de faits temporels et séquentiels représentant les caractéristiques des ordonnancements admissibles. Un logiciel (MASCOT) écrit en Prolog-II a été réalisé selon ce principe. Une nouvelle approche pour l'A.S.C. et plus particulièrement pour le raisonnement temporel sous contraintes de ressources a été développée. L'originalité de cette approche réside essentiellement dans la prise en compte du couplage temps/ressource à l'aide du concept d'intervalle temps-ressource qui conduit à utiliser un raisonnement énergétique. L'intervalle temps-ressource permet de représenter à la fois les tâches ou intervalles consommateurs et les intervalles de temps alloués sur lesquels des ressources sont disponibles, appelés intervalles fournisseurs. Le problème de l'ordonnancement de tâches amène à étudier l'interaction entre intervalles consommateurs et fournisseurs sur la base de considérations énergétiques. Le logiciel MASCOT met en jeu un processus de déduction symbolique. Ce type de déduction a été amélioré par la prise en compte de l'énergie obligatoirement consommée ou consommation obligatoire d'intervalles consommateurs sur un intervalle fournisseur. De nouvelles règles de déduction ont été écrites et intégrées dans MASCOT. D'autre part, un processus de déduction basé sur un raisonnement purement énergétique a été élaboré et implémenté (logiciel REPORT) en Prolog-II. Il utilise un autre type de déduction, la déduction numérique, qui permet d'affiner les bornes temporelles d'un intervalle fournisseur en considérant la consommation obligatoire des autres intervalles consommateurs. En d'autres termes, ces résultats consistent à actualiser des dates limites et correspondent à des conditions nécessaires d'admissibilité ; ils permettent ainsi de détecter des infaisabilités éventuelles. L'outil de modélisation utilisé est le graphe potentiels-bornes qui permet de représenter des contraintes numériques (sur la durée des tâches par exemple) et des contraintes symboliques entre intervalles. Il sert de support à un processus d'inférence par propagation numérique des contraintes.

Cette thèse présente une approche pour la construction d'évaluateurs de requêtes adaptés aux besoins des applications et/ou à l'environnement d'exécution. L'approche proposée distingue trois types d'adaptation : statique (à la construction de l'évaluateur), personnalisée (avant l'exécution de requête ayant des contraintes spécifiques) et dynamique (pendant l'exécution de la requête). Nous avons présenté une analyse systématique des différentes dimensions d'un évaluateur. La principale contribution de cette thèse est un canevas d'évaluation de requêtes nommé QBF (Query Broker Framework). QBF présente les fonctionnalités d'un évaluateur de requêtes de manière abstraite et séparée dans le but de favoriser leur réutilisation et leur adaptation. En s'appuyant sur QBF, nous avons proposé les mécanismes pour assurer les trois types d'adaptation, à savoir l'instanciation de QBF, l'évaluation personnalisée et l'évaluation interactive de requêtes. Une implémentation de QBF ainsi que de quelques instances (i.e. évaluateurs) ont été réalisées. Elles nous ont permis de montrer la faisabilité de notre approche et le bénéfice de la séparation et de l'abstraction des fonctionnalités proposées dans QBF. Nous avons également mené une évaluation expérimentale des mécanismes implémentés (i.e. opérateurs, surveillances) afin de mesurer le surcoût de l'adaptation dans QBF et d'aider les programmeurs à choisir des éléments (ou composants) appropriés pour construire leurs évaluateurs.

L'objet de cette thèse est l'étude d'une représentation structurée pour les sons polyphoniques. Dans un premier temps, certains pics (maxima locaux du spectre de puissance) sont sélectionnés dans une succession de spectres à court terme. Un algorithme dit de "suivi de partiels" relie ensuite de trame en trame certains de ces pics pour former des partiels : oscillateurs quasi-sinusoïdaux dont les paramètres de fréquence et d'amplitude évoluent lentement et de façon continue au cours du temps. Les contraintes liées à l'analyse de signaux polyphoniques amènent des artefacts dans la représentation spectrale, des pics sont manquants ou corrompus. Ces dégradations rendent le plus souvent inopérantes les techniques de suivi de partiel basées sur des heuristiques simples. L'utilisation des contraintes relatives au modèle sinusoïdal, comme le caractère prédictible des évolutions des paramètres des partiels de même que l'absence théorique de hautes fréquences dans ces évolutions permettent de proposer de nouveaux algorithmes de suivi adaptés au problème posé. Cette plus grande fidélité se fait au détriment du coût de calcul, coût qui reste toutefois raisonnable pour la plupart des méthodes proposées dans ce document. L'ensemble des partiels extraits se doit d'avoir de bonnes propriétés pour permettre ensuite une agrégation sans ambiguïté. Une première série de tests évalue un algorithme pour ses propriétés intrinsèques, tandis que la seconde série évalue les propriétés de cet algorithme lorsqu'il est inclus dans un module complet d'analyse / synthèse. A la suite d'un défaut de transmission ou d'une insuffisance de l'analyse, certains partiels peuvent être incomplets ou dégradés. Ces partiels sont alors reconstruits selon un algorithme original d'interpolation basée sur la prédiction linéaire des paramètres de fréquences et d'amplitude évitant les discontinuités de phase aux bornes de la zone interpolée. Enfin, les partiels présentant certaines corrélations sont ensuite agrégés pour former des entités sonores, chaque entité étant perçue par le système auditif humain non plus comme plusieurs sons simples mais comme un unique son complexe. On utilise pour cela plusieurs indices issus d'études psychoacoustiques tels que l'apparition simultanée de partiels, leur relation d'harmonicité et les évolutions corrélées de leurs paramètres.

Les travaux développés dans ce mémoire se situent à l'intersection des domaines du Génie Logiciel et de l'Intelligence Artificielle Distribuée : l'objectif est de spécifier un système d‘aide à la gestion d'information au sein d'une organisation de type administrative complexe sous la forme d'un système multi-agent. Le modèle holonique a été choisi, suite à une étude générale sur les organisations humaines et sur les organisations multi-agent, afin de structurer un système d'aide distribué en adéquation avec notre problématique, à savoir l'apport d'une aide au niveau de chaque acteur de l'organisation et la gestion de la cohérence de son fonctionnement global. Le choix d'une méthode d'analyse et de modélisation de système administratif complexe a nécessité la confrontation, à l'aide d'un benchmark, d'un ensemble de méthodes issues du Génie Logiciel et couramment utilisées. Aucune des méthodes comparées ne répondant totalement aux critères établis, la méthode MAMOSACO, conçue par adaptation et intégration des éléments les plus pertinents des méthodes comparées, est proposée. Cette méthode permet de spécifier un Système Orienté Holon pour l'aide au Travail COopératif (SOHTCO) d'un ensemble des acteurs impliqués dans une procédure donnée. La méthode MAMOSACO a été appliquée, au travers de son atelier de modélisation, sur un ensemble de cas réels de procédures administratives complexes. Et, finalement, sur base du cas d'application développé, un ensemble de perspectives de recherches, tant en ce qui concerne la modélisation qu'en ce qui concerne le système multi-agent holonique, est proposé.

PRATIQUE DES LANGAGES FONCTIONNELS TYPES Dans l'approche conception on s'intéresse à l'évolution de la compilation de ML en l'illustrant par la description de deux compilateurs : CeML un compilateur de ML vers C et OCamil un compilateur d'O'CAML vers .net. On montre ensuite les capacités d'extensions (parallèle et objet) au niveau des constructions du langage ML. Cela autorise de le choisir comme langage cible de compilation pour d'autres langages. Les capacités d'interopérer entre ML d'autres langages sont alors explorées pour plusieurs plates-formes d'exécution en conservant la sûreté du typage statique. Dans l'approche développement d'applications on s'intéresse aux outils de développement de l'édition structurée à la mise au point et à l'intégration de ces outils dans une même interface. On discute ensuite sur la formation du programmeur en montrant le cadre confortable du typage statique et l'intérêt de comprendre le modèle fonctionnel avant d'aborder le modèle objet. Le déploiement d'application est illustré par plusieurs applications embarquant un compilateur ML en tant que composant de l'application.

Ce travail a pour motivation une meilleure compréhension des graphes parfaits. La preuve en 2002 de la conjecture des graphes parfaits de Claude Berge par Chudnovsky, Robertson, Seymour et Thomas a jeté une lumière nouvelle sur ce domaine de la combinatoire, mais a laissé plusieurs questions en suspens, notamment l'existence d'un algorithme combinatoire de coloration des graphes parfaits. Une paire d'amis d'un graphe est une paire de sommets telle que tous les chemins les reliant sont de longueur paire. Comme l'ont montré Fonlupt et Urhy, la contraction d'une paire amis préserve le nombre chromatique du graphe, et appliquée récursivement, permet dans certains cas de colorier optimalement le graphe. Nous prouvons une conjecture de Everett et Reed affirmant que cette approche fonctionne pour une classe de graphes parfaits: les graphes d'Artémis. Nous en déduisons un algorithme de coloration des graphes Artémis de complexité O(mn^2). Nous donnons un algorithme de complexité O(n^9) pour la reconnaissance des graphes d'Artémis. D'autres algorithmes de reconnaissance sont donnés, tous fondés sur des routines de détection de sous-graphes dans des graphes de Berge. Nous montrons que ces problèmes de détection sont NP-complets si on cherche à les étendre aux graphes quelconques.

Notre étude porte sur les transporteurs ABC dans les génomes bactériens complets. L'analyse bioinformatique du répertoire de ces systèmes comprend l'identification des partenaires, l'assemblage, la reconstruction des systèmes incomplets, la classification en sous-familles, et l'identification du substrat transporté. Cette thèse propose des outils permettant l'étude de ces problèmes par l'utilisation de méthodes informatiques. Les hypothèses biologiques employées sont que : (i) des gènes voisins sur le chromosome peuvent être impliqués dans un même processus métabolique s'ils ont été conservés au cours de l'évolution, et (ii) des gènes présentant des similarités de séquence peuvent permettre la synthèse de protéines de même fonction. Trois études ont été menées sur le répertoire des transporteurs ABC : * L'exploration du voisinage chromosomique. D'après l'hypothèse selon laquelle plus les gènes conservés dans le voisinage d'un transporteur sont proches, plus leur lien fonctionnel avec le transporteur est fort, on essaye d'identifier le substrat transporté ou des associations de gènes. Ce problème est traité par une méthode de résolution issue des problèmes de satisfaction de contraintes. * La classification. Les transporteurs ABC sont classés par grandes catégories en fonction des molécules qu'ils transportent (sucres, ...). Pour chaque domaine, en représentant les relations d'homologie par un graphe, la recherche des zones de forte densité permet de déterminer des sous-classes de substrat. * La reconstitution des systèmes incomplets. Les transporteurs ABC sont assemblés en utilisant la proximité chromosomique des gènes codant pour les domaines et la compatibilité des sous-familles de domaines. Lorsque la proximité n'est pas respectée, on utilise une stratégie développée à partir d'une méthode d'analyse de graphes pour assembler les domaines et prédire des systèmes actifs. Ces méthodes, en complément de l'identification des partenaires et de l'assemblage, permettent une étude fonctionnelle des transporteurs ABC. Elles pourraient être appliquées à d'autres systèmes biologiques.