Les méthodes d'apprentissage statistiques exploitent des exemples, pour enseigner un comportement à un modèle prédictif. La classification supervisée requiert des exemples étiquetés. En pratique, l'étiquetage des exemples peut se révélé coûteux. Dans certain cas, l'étiquetage implique un expert humain, un instrument de mesure, un temps de calcul élevé...etc. Les méthodes d'apprentissage actif réduisent le coût de préparation des données d'apprentissage. Ces méthodes cherchent à étiqueter uniquement les exemples les plus utiles à l'apprentissage d'un modèle. Les travaux présentés dans ce manuscrit sont réalisés dans le cadre de l'échantillonnage sélectif, qui n'autorise pas les stratégies actives à générer de nouveaux exemples d'apprentissage. Les stratégies actives de la littérature utilisent généralement des modèles globaux à l'espace des variables d'entrées. Nous proposons dans ce manuscrit une stratégie originale qui effectue un partitionnement dichotomique récursif de l'espace d'entrée. Cette stratégie met en compétition les modèles locaux à chacune des zones, pour choisir les exemples à étiqueter. Notre stratégie décide “quand” couper une zone et “où” la couper. Une amélioration possible consiste `a exploiter une méthode de discrétisation pour prendre ces deux décisions. L'extension de l'approche de discrétisation MODL au cas de l'apprentissage semi-supervisé constitue un des apports majeurs de cette thèse. Nous proposons une deuxième amélioration qui consiste à sélectionner, localement à la meilleure zone, l'exemple le plus utile à l'apprentissage du modèle local. Nous proposons une stratégie active originale, qui maximise la probabilité des modèles de discrétisation connaissant les données et l'exemple candidat à l'étiquetage.

In this document, I explore the problem of scheduling pipelined applications onto large-scale distributed platforms, in order to optimize several criteria. A particular attention is given to throughput maximization (i.e., the number of data sets that can be processed every time unit), latency minimization (i.e., the time required to process one data set entirely), and failure probability minimization. First, I accurately define the models and the scheduling problems, and exhibit surprising results, such as the difficulty to compute the optimal throughput and/or latency that can be obtained given a mapping. In particular, I detail the importance of the communication models, which induce quite different levels of difficulty. Second, I give an overview of complexity results for various cases, both for mono-criterion and for bi-criteria optimization problems. I illustrate the impact of the models on the problem complexity. Finally, I show some extensions of this work to different applicative contexts and to dynamic platforms.

Ces dernières années ont vu apparaître de nombreuses applications traitant des données générées en continu et à de grandes vitesses. Ces données sont désormais connues sous le nom de flux de données. Leurs quantités de données potentiellement infinies ainsi que les contraintes qui en dérivent posent de nombreux problèmes de traitement. Parmi ces contraintes, citons par exemple l'impossibilité de bloquer un flux de données, ou encore le besoin de produire des résultats en temps réel. Néanmoins, les multiples domaines d'application de ces traitements (comme les transactions bancaires, l'usage du Web, la surveillance des réseaux, etc) ont suscité beaucoup d'intérêt tant dans les milieux industriels qu'académiques. Ces quantités potentiellement infinies de données interdisent tout espoir de stockage complet ; toutefois, on a besoin de pouvoir interroger l'historique des flux. Cela a conduit au compromis des « résumés » des flux de données et des résultats « approximatifs ». Aujourd'hui, un grand nombre de méthodes propose différents types de résumés des flux de données. Mais le développement incessant de la technologie et des applications afférentes demande un développement au moins équivalent des méthodes d'analyse et de résumé. De plus, l'extraction de motifs séquentiels y est encore peu étudiée: au commencement de cette thèse, il n'existait aucune méthode d'extraction de motifs séquentiels dans les flux de données. Motivés par ce contexte, nous nous sommes intéressés à une méthode qui résume les flux de données d'une manière efficace et fiable et qui permet principalement d'en extraire des motifs séquentiels. Dans cette thèse, nous proposons l'approche CLARA (CLAssification, Résumés et Anomalies). CLARA permet d'obtenir des clusters à partir d'un flux de séquences d'itemsets, de calculer et gérer des résumés de ces clusters et d'y détecter des anomalies. Les différentes contributions détaillées dans ce mémoire concernent: - La classification non supervisée de séquences d'itemsets sous forme de flux. A notre connaissance, cette technique est la première à permettre une telle classification. - Les résumés de flux de données à l'aide de l'extraction de motifs. Les résumés de CLARA sont composés de motifs séquentiels alignés représentant les clusters associés à leur historique dans le flux. L'ensemble de ces motifs permet de résumer le flux de manière fiable à un instant t. La gestion de l'historique de ces motifs est un point essentiel dans l'analyse des flux. CLARA introduit une nouvelle gestion de la granularité temporelle afin d'optimiser cet historique. - La détection d'anomalies. Cette détection, quand elle concerne les flux, doit être rapide et fiable. En particulier, les contraintes liées aux flux interdisent de consulter l'utilisateur final pour ajuster des paramètres (une anomalie détectée trop tard peut avoir de graves conséquences). Avec CLARA, cette détection est automatique et auto-adaptative. Nous proposerons également un cas d'étude sur des données réelles, réalisé en collaboration avec Orange Labs.

L'objectif de cette étude est de proposer une approche générale d'évaluation de la validité d'une Modélisation et Simulation (M&S) utilisée dans le cadre du développement des systèmes embarqués. Cette approche s'inscrit dans une démarche visant à améliorer la confiance en l'utilisation d'une simulation dont les résultats sont souvent remis en cause sans justification cohérente. Le cadre d'application de l'étude est l'ensemble des produits de simulation d'Airbus. Au regard d'un objectif de validation d'un système, une simulation doit être la plus proche possible du système qu'elle représente. Dans le cycle de développement d'un avion, les simulations doivent être disponibles avant les systèmes eux-mêmes. Si le niveau de validité est trop faible les résultats nécessaires à l'expérience ne peuvent être atteints. Si le niveau de validité est trop élevé, du temps de travail de modélisation et de calcul est inutilement dépensé. Nous avons assimilé le problème de niveau de validité à une hiérarchie d'abstraction de modèles. Nous proposons un modèle de description des propriétés d'abstractions qui permet de parler strictement des mêmes choses lorsque le terme de "validité" est évoqué et d'évaluer la compatibilité entre un niveau de validité attendu par l'expérience et un niveau de validité fourni par le produit de simulation. Puis, nous avons établi des règles formelles de mise en correspondance d'un objectif d'utilisation et du domaine d'usage d'un modèle. Le problème de la mise en correspondance est fondé sur le principe qu'un objectif d'utilisation et un domaine d'usage d'une simulation sont deux composants, au sens formel du terme. Nous avons adapté les techniques de l'ingénierie basée composants, pour enrichir, par des techniques itératives, nos deux composants. Enfin nous avons proposé une méthodologie permettant d'intégrer nos concepts formels au processus d'Ingénierie Systèmes. Nous illustrons cette démarche sur un système de communication avionique.

Dans des réseaux opportunistes --- dont la topologie est dynamique --- de dispositifs intelligents, nous traitons le problème de la recherche et de la composition dynamique de fonctionnalités à l'aide d'une description logique des dispositifs. Nous définissons un langage logique du premier ordre dans lequel les dispositifs, leurs fonctionnalités et leur propriétés sont exprimés, en utilisant une taxonomie de classes pour contraindre le type des ressources. Nous définissons conjointement un langage de requêtes basé sur celui de la description nous permettant d'utiliser des raisonneurs du type Prolog pour répondre aux requêtes. Ces réponses sont des instanciations des variables d'intérêt présentes dans la requête et représentent des constructions de fonctionnalités composées. Dans un second temps, pour faire face aux spécificités d'un réseau dynamique, nous utilisons la plateforme SomeWhere --- qui permet de faire du raisonnement en logique propositionnel lorsque la base de connaissances est totalement distribuée --- comme un service de lookup récupérant un sous-ensembles des ressources dont les descriptions sont nécessaires à l'obtention de toutes les réponses à la requête donnée via le raisonneur. Dans cette optique, nous utilisons un encodage des descriptions et de la requête écrites en logique du premier ordre vers la logique propositionnelle qui conserve les bonnes propriétés de la description.

La gestion performante de la mobilité et l'amélioration des performances des couches basses sont deux enjeux fondamentaux dans le contexte des réseaux sans fil. Cette thèse apporte des solutions originales et innovantes qui visent à répondre à ces deux problématiques empêchant à ce jour d'offrir des possibilités de communication performantes et sans couture aux usagers mobiles accédant à l'Internet via des réseaux d'accès locaux sans fil (WLAN). Ces solutions se distinguent en particulier par l'impact minimum qu'elles ont sur les protocoles standards de l'Internet (niveaux transport et réseau) ou de l'IEEE (niveaux physique et liaison de données). S'inscrivant dans les paradigmes de "bout en bout" et "cross-layer", notre architecture permet d'offrir des solutions efficaces pour la gestion de la mobilité : gestion de la localisation et des handover en particulier. En outre, nous montrons que notre approche permet également d'améliorer l'efficacité des transmissions ainsi que de résoudre efficacement plusieurs syndromes identifiés au sein de 802.11 tels que les anomalies de performance, l'iniquité entre les flux et l'absence de contrôle de débit entre la couche MAC et les couches supérieures. Cette thèse résout ces problèmes en combinant des modèles analytiques, des simulations et de réelles expérimentations. Ces mécanismes adaptatifs ont été développés et intégrés dans une architecture de communication qui fournit des services de communication à haute performance pour réseaux sans fils tels que WIFI et WIMAX.

Ces travaux de thèse se sont déroulés dans le cadre du projet Gothic, qui avait pour objectif de concevoir et réaliser un système distribué intégré tolérant aux fautes pour un réseau local de machines multiprocesseurs dotées de Mémoires Stables Rapides (MSR). Le langage de programmation du système Gothic, appelé Polygoth, introduit le concept de multiprocédure pour la construction d'applications distribuées. La multiprocédure est une généralisation de la procédure permettant l'exécution en parallèle de plusieurs calculs. Ces travaux de thèse ont porté sur la conception de protocoles de communication fiable pour la mise en oeuvre d'un protocole d'appel de multiprocédure à distance (RMPC). Nous avons défini un système de communication fiable dont les composants essentiels sont un protocole de communication fiable par messages et un protocole de diffusion fiable ordonnée. L'originalité de ces protocoles repose sur l'utilisation de la MSR associée à chaque processeur pour y ranger les informations cruciales du système de communication et des points de reprise des processus communicants. Le système de communication fiable de Gothic dépasse le cadre du protocole RMPC. Nous avons en particulier défini un protocole de rendez-vous atomique mis en oeuvre dans le système Gothic au-dessus du protocole de communication fiable par messages.

Dans le cadre de la manipulation et de la description du contenu des documents, mes travaux de thèse consistent à étudier la modélisation générique de documents multimédia par des métadonnées. Nous proposons une approche qui consiste à l'homogénéisation des structures de représentation de tels documents facilitant leur traitement final sans avoir recours aux contenus multimédia eux-mêmes. Nous avons proposé la structuration de ces métadonnées dans des documents XML appelés « méta-documents ». Ces méta-documents représentent une structure supplémentaire par rapport à d'éventuelles structures logiques ou physiques rédigées par les auteurs des documents. Nous avons étendu les méta-documents en intégrant des descripteurs sémantiques définis selon le besoin de l'utilisateur et des relations spatiales et temporelles. Au niveau de l'interrogation des documents multimédia, nous avons proposé un outil d'aide à la formulation graphique de requêtes XQuery en utilisant les métadonnées et en intégrant les relations spatio-temporelles entre ces métadonnées.

L'intégration des données biologiques est un des principaux défis de la bioinformatique aujourd'hui. La mise à disposition de quantités importantes de données concernant tous les niveaux d'organisation de la cellule, nécessite la mise en place de stratégies d'intégration pour rassembler toutes ces données, et ainsi mieux comprendre le fonctionnement de la cellule. Nous nous sommes intéressés à l'exploitation du concept de voisinage pour représenter et intégrer des données biologiques. Dans un premier temps, notre travail met l'accent sur l'importance du choix de la représentation pour mener une intégration efficace. Notre étude sur la représentation du métabolisme a montré que les modes élémentaires sont une alternative pertinente à la représentation classique sous forme de voies métaboliques. De plus, les modes élémentaires nous ont permis de trouver des routes métaboliques utilisées par la cellule en réponse à divers stress. Nous avons également exploité le voisinage dans une perspective de génomique comparative. Nous avons cherché à déterminer si le voisinage d'expression peut être une signature pour les gènes, et s'il peut être utilisé pour caractériser des gènes en établissant des équivalences entre des génomes (orthologues ou gènes fonctionnellement similaires). Les résultats présentés confirment l'intérêt de l'exploration du voisinage, des gènes et de leur produit, pour intégrer des données hétérogènes. L'efficacité de cette exploration est fortement liée au choix de la représentation des connaissances.

Le problème de l'exploration de graphes trouve ses motivations en informatique fondamentale, notamment en logique et en théorie de la complexité. Il possède également de nombreuses applications en robotique. Quel que soit le cadre, la quantité de mémoire utilisée par l'entité mobile (robot, automate fini, etc.) effectuant l'exploration est un des paramètres importants à considérer. Dans cette thèse, nous étudions en détail la complexité en espace de l'exploration de graphes, à travers différents modèles. Nous distinguons principalement deux cadres d'études.<br /><br />Dans la première partie de la thèse, nous nous attachons à l'étude de l'exploration ``sans assistance'', c'est-à-dire lorsque l'entité mobile ne possède aucune information sur le graphe à explorer. Dans ce contexte, nous prouvons plusieurs bornes inférieures et supérieures sur la quantité de mémoire nécessaire et suffisante à l'entité pour explorer tous les graphes. En particulier, nous montrons que l'algorithme très simple de parcours en profondeur d'abord est optimal en mémoire lorsque la complexité est exprimée en fonction du degré et du diamètre.<br /><br />Dans la seconde partie de la thèse, nous nous attachons à l'étude de l'exploration ``avec assistance''. Nous considérons un modèle supposant l'existence d'un oracle ayant une connaissance exhaustive du graphe exploré, et capable d'aider l'entité mobile en lui fournissant de l'information. Nous nous intéressons ainsi à la quantité minimale d'information (mesurée en nombre de bits) que l'oracle doit fournir à l'entité pour permettre l'exploration. Cette information peut être soit donnée directement à l'entité, soit codée sur les sommets du graphes.