L'extraction de connaissances à partir de données incomplètes constitue un axe de recherche en plein essor. Dans cette thèse, nous y contribuons par la proposition d'une méthode de complétion des valeurs manquantes. Nous commençons par aborder cette problématique par la définition de modèles d'apparition des valeurs manquantes. Nous en proposons une nouvelle typologie en fonction des données connues et nous les caractérisons de façon non redondante grâce à la base d'implications propres. Un algorithme de calcul de cette base de règles, formalisé à partir de la théorie des hypergraphes, est également proposé dans cette thèse. Ensuite, nous exploitons les informations fournies lors de l'étape de caractérisation afin de proposer une méthode de complétion contextualisée, qui complète les valeurs manquantes selon le type aléatoire/non-aléatoire et selon le contexte. La complétion des valeurs manquantes non aléatoires est effectuée par des valeurs spéciales, renfermant intrinsèquement les origines des valeurs manquantes et déterminées grâce à des schémas de caractérisation. Finalement, nous nous intéressons aux techniques d'évaluation des méthodes de complétion et nous proposons une nouvelle technique fondée sur la stabilité d'un clustering entre les données de référence et les données complétées.

Les systèmes de workflows disposent de modules de gestion de provenance qui collectent les informations relatives aux exécutions (données consommées et produites) permettant d'assurer la reproductibilité d'une expérience. Pour plusieurs raisons, la complexité de la structure du workflow et de ses d'exécutions est en augmentation, rendant la réutilisation de workflows plus difficile. L'objectif global de cette thèse est d'améliorer la réutilisation des workflows en fournissant des stratégies pour réduire la complexité des structures de workflow tout en préservant la provenance. Deux stratégies sont introduites. Tout d'abord, nous introduisons SPFlow un algorithme de réécriture de workflow scientifique préservant la provenance et transformant tout graphe acyclique orienté (DAG) en une structure plus simple, série-parallèle (SP). Ces structures permettent la conception d'algorithmes polynomiaux pour effectuer des opérations complexes sur les workflows (par exemple, leur comparaison) alors que ces mêmes opérations sont associées à des problèmes NP-difficile pour des structures générales de DAG. Deuxièmement, nous proposons une technique capable de réduire la redondance présente dans les workflow en détectant et supprimant des motifs responsables de cette redondance, nommés "anti-patterns". Nous avons conçu l'algorithme DistillFlow capable de transformer un workflow en un workflow sémantiquement équivalent "distillé", possédant une structure plus concise et dans laquelle on retire autant que possible les anti-patterns. Nos solutions (SPFlow et DistillFlow) ont été testées systématiquement sur de grandes collections de workflows réels, en particulier avec le système Taverna. Nos outils sont disponibles à l'adresse: https://www.lri.fr/~chenj/.

Partant d'un projet de base géographique (SIG), cette recherche compose un hypertexte, soit un réseau de nœuds et de liens instaurant un mode d'organisation de l'information indépendant d'une structure préétablie (structure web). Un examen des représentations actuelles et passées de la notion d'activité humaine, une analyse des pratiques et des conceptions de l'activité scientifique, une approche des multiples dimensions de l'activité informatique, et une exploration des connaissances géographiques du temps présent, constituent les nœuds majeurs de cet hypertexte. Ainsi, à partir de l'explicitation de nos propres raisonnements, des raisonnements des géographes et des opérations de pensée des utilisateurs s'organise la mise ne mouvement d'une géomatique humaniste.

La conception des systèmes multimédia embarqués présente de nombreux défis comme la croissante complexité du logiciel et du matériel sous-jacent, ou les pressions liées aux délais de mise en marche. L'optimisation du processus de débogage et validation du logiciel peut aider à réduire sensiblement le temps de développement. Parmi les outils de débogage de systèmes embarqués, un puissant outil largement utilisé est l'analyse de traces d'exécution. Cependant, l'évolution des techniques de tra¸cage dans les systèmes embarqués se traduit par des traces d'exécution avec une grande quantité d'information, à tel point que leur analyse manuelle devient ingérable. Dans ce cas, les techniques de recherche de motifs peuvent aider en trouvant des motifs intéressants dans de grandes quantités d'information. Concrètement, dans cette thèse, nous nous intéressons à la découverte de comportements périodiques sur des applications multimédia. Donc, les contributions de cette thèse concernent l'analyse des traces d'exécution d'applications multimédia en utilisant des techniques de recherche de motifs périodiques fréquents. Concernant la recherche de motifs périodiques, nous proposons une définition de motif périodique adaptée aux caractéristiques de la programmation paralléle. Nous proposons ensuite une représentation condensée de l'ensemble de motifs périodiques fréquents, appelée Core Periodic Concepts (CPC), en adoptant une approche basée sur les relations triadiques. De plus, nous définissons quelques propriétés de connexion entre ces motifs, ce qui nous permet de mettre en oeuvre un algorithme efficace de recherche de CPC, appelé PerMiner. Pour montrer l'efficacité et le passage à l'échelle de PerMiner, nous réalisons une analyse rigoureuse qui montre que PerMiner est au moins deux ordres de grandeur plus rapide que l'état de l'art. En plus, nous réalisons un analyse de l'efficacité de PerMiner sur une trace d'exécution d'une application multimédia réelle en présentant l'accélération accompli par la version parallèle de l'algorithme. Concernant les systèmes embarqués, nous proposons un premier pas vers une méthodologie qui explique comment utiliser notre approche dans l'analyse de traces d'exécution d'applications multimédia. Avant d'appliquer la recherche de motifs fréquents, les traces d'exécution doivent ˆetre traitées, et pour cela nous proposons plusieurs techniques de pré-traitement des traces. En plus, pour le post-traitement des motifs périodiques, nous proposons deux outils : un outil qui trouve des pairs de motifs en compétition ; et un outil de visualisation de CPC, appelé CPCViewer. Finalement, nous montrons que notre approche peut aider dans le débogage des applications multimédia à travers deux études de cas sur des traces d'exécution d'applications multimédia réelles.

Le développement d'applications avec une architecture Pair-à-Pair (P2P) est devenu de plus en plus important en ingénierie du logiciel. Aujourd'hui, un grand nombre d'organisations de tailles et secteurs différents compte d'une manière croissante sur la collaboration entre multiples acteurs (individus, groupes, communautés, etc.) pour accomplir des tâches essentielles. Ces applications P2P ont généralement un comportement récursif que plusieurs approches de modélisation ne peuvent pas décrire et analyser (ex. les approches basées sur les automates à états finis). Un autre challenge qui concerne le développement d'applications P2P est le couplage fort entre la spécification d'une part, et les technologies et protocoles sous-jacents d'autre part. Cela force les développeurs à faire des efforts considérables pour trouver puis comprendre des informations sur les détails de ces couches basses du P2P. De plus, ce couplage fort oblige les applications à s'exécuter dans des environnements figés. Par conséquent, choisir par exemple un autre protocole pour répondre à un nouveau besoin à l'exécution devient une tache très difficile. Outre ces points, les applications P2P sont souvent spécifiées avec une faible capacité à déléguer des traitements entre les pairs, et se focalisent surtout sur le partage et le stockage de données. Ainsi, elles ne profitent pas pleinement de la puissance de calcul et de traitement offerte par le réseau P2P sous-jacent. Dans cette thèse, nous présentons une approche qui combine les principes du développement orienté composants et services avec des techniques issues des Grammaires Attribuées et d'analyses de flot de données (techniques utilisées surtout dans la construction de compilateurs) afin de faciliter la spécification, l'analyse et le déploiement d'applications dans des architectures P2P. Cette approche incorpore: i) Un langage formel nommé DDF (de l'anglais Data-Dependency Formalism) pour spécifier les applications et construire leurs graphes de dépendances de données. Un graphe de dépendances de données est nommé DDG (de l'anglais Data-Dependency Graph) et est défini pour être une représentation abstraite de l'application spécifiée. ii) Une méthode d'analyse qui utilise le graphe de dépendances de données pour inférer et calculer diverses propriétés, y compris certaines propriétés que les model-checkers ne peuvent pas calculer si le système présente un comportement récursif. iii) Un intergiciel nommé SON (de l'anglais Shared data Overlay Network) afin de développer et d'exécuter des applications dans une architecture P2P sans faire face à la complexité des couches sous-jacentes. Cela grâce essentiellement au couplage faible (par une approche orientée services) et à la fonctionnalité de génération de code automatique.

Ce document présente l'étude de plusieurs modèles de machines à états finis qui étendent tous le même formalisme: les automates d'arbres classiques, et leur application dans différentes tâches telles que l'analyse statique de programmes ou de systèmes, la typage, la vérification de la cohérence de spécifications, le model checking... Les arbres sont une structure naturelle de données, très répandue en informatique, par exemple pour la représentation des structures de données hiérarchiques ou imbriquées, pour des algorithmes spécifiques (arbres binaires de recherche, algorithmes distribués), comme modèle abstrait pour des données semi-structurées utilisées pour l'échange d'information dans le Web, pour une présentation algébrique de processus récursifs, comme les termes en logique... Lorsqu'il s'agit de raisonner sur des systèmes manipulant des arbres, ou modelisés par des arbres, il est crucial d'avoir une représentation finie d'ensembles infinis d'arbres. Les automates d'arbres sont des machines à états finis permettant une telle représentation. Ils ont fait la preuve de leur adéquation à des tâches de raisonnement: ils ont un modèle théorique bien établi, en étroite relation avec la logique, ils bénéficient de bonnes propriétés de composition et d'algorithmes de décision efficaces. En particulier, les automates d'arbres sont utilisées au coeur de systèmes de vérification formelle d'outils de déduction automatique. Toutefois, les automates d'arbres ont des limitations sévères en expressivité. Par exemple, ils sont incapables de faire du filtrage non-linéaire ou d'exprimer des contraintes d'intégrité tels que les clés dans les bases de données. Certaines extensions ont été proposées afin d'améliorer le modèle en essayant de conserver de bonnes propriétés. Nous présentons dans ce document de plusieurs de telles extensions, leurs propriétés et leur utilisation en vérification symbolique de systèmes et de programmes.

Les systèmes d'information mobiles et ambiants liés à la localisation et à la navigation évoluent progressivement vers des environnements à petite échelle. La nouvelle frontière scientifique et technologique concernent les applications qui assistent les utilisateurs dans leurs déplacements et activités au sein d'espaces bâtis dits "indoor" (e.g., aéroports, musées, bâtiments). La recherche présentée par cette thèse développe une représentation de données spatiales d'un environnement "indoor" qui tient compte des dimensions contextuelles centrées sur l'utilisateur et aborde les enjeux de gestion de données mobiles. Un modèle de données "indoor" hiérarchique et sensible au contexte est proposé. Ce modèle intègre différentes dimensions du contexte en plus de la localisation des entités concernées, telles que le temps et les profils des utilisateurs. Ce modèle est basé sur une structure arborescente dans laquelle l'information spatiale est représentée à différents niveaux d'abstraction. Cette conception hiérarchique favorise un traitement adaptatif et efficace des Requêtes Dépendantes de la Localisation (RDL) qui sont considérées comme des éléments clés pour le développement des différentes catégories de services de géolocalisation sensibles au contexte. Un langage de requêtes continues est développé et illustré par des exemples de requêtes RDL. Ce langage exploite le concept des granules spatiaux, et permet de représenter les requêtes continues et dépendantes de la localisation en prenant compte des préférences de l'utilisateur au moment de l'exécution. Cette approche de modélisation est complétée par le développement d'une architecture générique pour le traitement continu des requêtes RDL et par la conception et la mise en œuvre de plusieurs algorithmes qui permettent un traitement efficace des requêtes dépendantes de la localisation sur des objets mobiles en "indoor". Plusieurs algorithmes de traitement continu des requêtes de recherche de chemin hiérarchique et des requêtes de zone appliquées à des objets statiques et/ou en mouvement sont présentés. Ces algorithmes utilisent une approche hiérarchique et incrémentale afin d'exécuter efficacement les requêtes RDL continues. Un prototype encapsulant le modèle de données hiérarchique, les opérateurs et les contraintes introduits dans le langage de requête ainsi que les différents algorithmes et méthodes pour la manipulation de requêtes RDL a été développé comme une extension du SGBD Open Source PostgreSQL. Une étude expérimentale des solutions développées a été menée pour étudier la performance et le passage à l'échelle à l'égard des propriétés intrinsèques des solutions proposées.

Le stockage et la gestion de données sont des questions centrales en infor- matique. La structuration sous forme d'arbres est devenue la norme (XML, JSON). Pour en assurer la pérennité et l'échange efficace des données, il est nécessaire d'identifier de nouveaux mécanismes de transformations automati- sables. Nous nous concentrons sur l'étude de transformations d'arbres en mots représentées par des machines à états finies. Nous définissons les transducteurs séquentiels d'arbres en mots ne pouvant utiliser qu'une et unique fois chaque nœud de l'arbre d'entrée pour décider de la production. En réduisant le problème d'équivalence des transducteurs séquentiels à celui des morphismes appliqués à des grammaires algébriques (Plandowski, 95), nous prouvons qu'il est décidable en temps polynomial. Cette thèse introduit la notion de transducteur travailleur, forme norma- lisée de transducteurs séquentiels, cherchant à produire la sortie le "plus tôt possible" dans la transduction. A l'aide d'un algorithme de normalisation et de minimisation, nous prouvons qu'il existe un représentant canonique, unique transducteur travailleur minimal, pour chaque transduction de notre classe. La décision de l'existence d'un transducteur séquentiel représentant un échantillon, i.e. paires d'entrées et sorties d'une transformation, est prouvée NP-difficile. Nous proposons un algorithme d'apprentissage produisant à par- tir d'un échantillon le transducteur canonique le représentant, ou échouant, le tout en restant polynomial. Cet algorithme se base sur des techniques d'infé- rence grammaticales et sur l'adaptation du théorème de Myhill-Nerode.