Les réseaux ad hoc sont un type particulier de réseaux sans fil privés de toute infrastructure fixe. Cette particularité rend le routage très problématique en cas de grande instabilité des éléments qui les composent (n\oe{}uds et liens). Le but de cette thèse est d'évaluer l'impact d'une stratégie non conventionnelle consistant à, d'une part, utiliser plusieurs routes en parallèle, d'autre part, introduire de la redondance entre les données réparties sur ces routes grâce à des méthodes de codage à description multiple. Ces méthodes permettent de transformer l'information à transmettre en un nombre défini d'éléments appelés descriptions, et tels que la perte d'un certain nombre d'entre eux n'empêche pas la reconstruction de l'information initiale. L'objectif d'une telle stratégie est de rendre chaque route moins critique, tout en veillant à modérer la redondance globale introduite. Dans ce contexte, un algorithme de sélection de routes est proposé, et différentes stratégies de répartition de descriptions sur ces routes sont étudiées. Afin d'évaluer cette approche, nous avons mis en œuvre de deux protocoles inspirés de mécanismes standards et incluant les idées précédemment mentionnées. Le premier, MPOLSR, est proactif. Dans ce cas, il suffit d'extraire un ensemble de routes intéressantes de l'information topologique rassemblée. Le second, TMR, est réactif. La récupération d'informations topologiques suffisament variées nécessite alors des mécanismes différents de ceux utilisés dans les protocoles réactifs standards. Des simulations sont réalisées à l'aide de NS2 pour comparer les performances de ces propositions.

Les architectures distribuées des systèmes embarqués sont souvent décrites sous la forme de composants concurrents communiquant entre eux. De tels systèmes sont à la fois orientés flot de données pour leur description, et dirigés par le temps pour leur exécution. Cette thèse s'inscrit dans cette problématique et se concentre sur le contrôle de la compatibilité temporelle d'un ensemble de données interdépendantes utilisées par les composants du système. L'architecture d'un système modélisé par composants forme un graphe où plusieurs chemins peuvent relier deux composants, avec des caractéristiques temporelles hétérogènes, ce qui induit des temps de parcours disparates. Il est alors important que ces flots d'information soient assemblés de façon cohérente sur le composant destinataire, c'est-à-dire de telle manière que le composant utilise en entrée des données dépendant (directement ou indirectement) du même pas d'exécution du composant à l'origine de ces flots multiples. Dans un premier temps, ce principe d'association cohérente de données est identifié et formalisé. Une méthodologie est proposée afin de détecter, dans un graphe de composants, les configurations pouvant poser des problèmes d'association de données Dans un deuxième temps, différentes approches sont détaillées afin de gérer l'association cohérente des données dans des systèmes périodiques sans supposer de propriétés strictes sur l'ordonnancement des composants. Dans les systèmes où les composants partagent la même période et où les communications intra-périodiques sont interdites, l'association des données est gérée par un mécanisme de files permettant de rééquilibrer les temps de parcours des données sur les différents chemins. Dans le cas où les composants sont de périodes diverses, un mécanisme d'estampillage des données est utilisé afin de mémoriser les dépendances entre données. Associé à l'utilisation de files, cet estampillage permet aux composants de sélectionner, à chacune de leurs phases d'activation, des ensembles de données cohérents choisis parmi les données à leur disposition. La notion d'association cohérente est ensuite relâchée, permettant une utilisation de données approximativement cohérentes. Des files filtrantes, n'enregistrant qu'une donnée sur un certain nombre de données reçues, permettent de réduire la taille des files nécessaires. Par ailleurs, du fait de la liberté du modèle d'exécution choisi, il existe des situations où il est impossible de garantir la vivacité de l'association cohérente des données. D'autre part, une architecture particulière peut générer des contraintes de cohérence conflictuelles et aboutir à une impossibilité de gestion de la cohérence. Pour terminer, les résultats de ces travaux sont appliqués sur le logiciel applicatif d'un satellite d'observation terrestre détectant des points chauds.

Dans cette thèse, nous proposons une méthode rigoureuse, formellement fondée pour traiter de l'interopérabilité d'une famille de langages dédiés (DSL) issus d'un même domaine métier. A partir de la sémantique de chacun des DSL, notre démarche construit, par un calcul de co-limite sur des spécifications algébriques, un langage qui unifie les concepts de la famille. L'approche se caractérise notamment par la capacité à traduire automatiquement le code d'un DSL vers le langage unificateur. Un autre bénéfice réside dans la preuve qu'une propriété sur un langage de la famille se décline, par construction, vers l'environnement unifié. La mise en œuvre de la démarche a été outillée ; elle s'appuie principalement sur le logiciel Specware de Kestrel et l'assistant de preuve Isabelle.

Pour modéliser le fonctionnement d'un système, décrire une situation ou représenter des idées, on se met intuitivement à dessiner des bulles et les lier par des flèches sous forme de graphes étiquetés. Les logiques modales constituent un cadre formel expressif et extensible qui permet de définir ces graphes sous forme de « modèles », et d'exprimer certaines propriétés de ces graphes sous forme de « formules » afin de pouvoir raisonner là-dessus: model checking, test de satisfiabilité ou de validité, etc. Pour des formules et modèles de tailles importantes, ces tâches deviennent compliquées. De ce fait, un outil permettant de les réaliser automatiquement s'avère nécessaire. LoTREC en est un exemple. Il permet à son utilisateur de créer sa propre méthode de preuve, grâce à un langage simple et de haut niveau, sans avoir besoin d'aucune expertise spécifique en programmation. Durant ma thèse, j'ai revu le travail qui était déjà accompli dans LoTREC et j'ai apporté de nouvelles extensions qui s'avéraient nécessaires pour pouvoir traiter de nouvelles logiques (K.alt1, universal modality, Hybrid Logic HL(@),Intuitionistic logic, Public Announcement Logic, ...) et offrir à l'utilisateur certaines nouvelles techniques. D'autre part, j'ai examiné les origines de LoTREC dans le monde de réécriture de graphes et j'ai spécifié la sémantique de son moteur de réécriture. Cela a permis d'éclaircir comment l'on peut hériter dans nos méthodes de preuve des résultats et des propriétés théoriques déjà bien établies dans le domaine de la réécriture de graphes.

L'étude des polynômes réels en plusieurs variables est un problème classique en géométrie algébrique réelle et en calcul formel. Plusieurs questions sont naturelles : positivité éventuelle, calcul du minimum...<br /><br />Nous nous proposons, dans cette thèse, d'étudier ces questions dans le cas particulier où l'étude est menée sur un simplexe de $\R^k$.<br /><br />L'outil essentiel dans notre travail est la base de Bernstein, plus adaptée à la situation que la traditionnelle base des monômes. Elle jouit notamment de propriétés de positivité et d'encadrement essentielles à notre étude.<br /><br />Elle permet tout d'abord d'obtenir un algorithme décidant si un polynôme $f$ est positif sur un simplexe $V$, et le cas échéant, fournissant une écriture de $f$ rendant triviale cette positivité : on parle de certificat de positivité.<br /><br />En outre, elle est à l'origine d'un algorithme de minimisation polynomiale sur un simplexe. Ces deux algorithmes sont certifiés, et l'étude de leur complexité est menée dans cette thèse. Ils ont également fait l'objet d'implémentation sur ordinateur.

Cette thèse, fruit d'une collaboration LORIA / INRA, porte sur l'étude du raisonnement à partir de cas pour aider à l'interprétation d'organisations spatiales agricoles. Les agronomes effectuent des enquêtes auprès d'exploitants agricoles, afin d'appréhender les relations entre structure spatiale et fonctionnement des exploitations. Des modèles graphiques, appelés chorèmes d'exploitations, permettent de synthétiser ces données d'enquêtes. Sur la base de ces chorèmes, nous avons modélisé l'organisation spatiale des exploitations par des graphes bipartites aux sommets et aux arc étiquetés par des concepts. A certains sous-graphes, décrivant des structures spatiales intéressantes, sont adjoints des explications, décrivant l'organisation fonctionnelle, pour constituer des cas. La modélisation conjointe a abouti à la reconception des chorèmes et à la constitution d'une base de cas et de hiérarchies de concepts du domaine. Le système de RàPC ROSA permet de proposer des explications de fonctionnement à un graphe d'organisation spatiale en utilisant les cas enregistrés. La comparaison des graphes s'appuie sur le mécanisme des logiques de description : étant donné un graphe d'exploitation cible, on lui associe des graphes sources de la base de cas au moyen d'opérations de généralisation et de spécialisation.

La syncope, dont l'origine peut ne pas être clairement définie, est considérée comme une pathologie fréquente. Dans ce cas et lorsque les épisodes sont répétés, le patient peut être amené à réaliser le test de la table d'inclinaison. Cet examen appelé tilt-test, est une méthode reconnue pour recréer les conditions dans lesquelles le patient ressent les symptômes de la syncope. Cependant, le principal problème de ce test est sa durée, qui peut atteindre une heure. Dès lors, pour des raisons de coût et de bien-être des patients, il paraît important de pouvoir réduire sa durée. C'est dans cet objectif que s'inscrivent les travaux réalisés dans le cadre de cette thèse, qui tentent de prédire l'apparition des symptômes liés à la syncope, et ce, le plus tôt possible. Durant nos recherches, deux axes sont ressortis naturellement : la fouille de données et le dé- veloppement de modèles capables de prédire le résultat du tilt-test. Ces deux axes partagent des méthodes issues de l'apprentissage articiel, qui permettent d'acquérir et d'extraire des connaissances à partir d'un ensemble d'observations signicatif. La littérature propose tout un ensemble de méthodes, qui nous ont permis de mettre en évidence certaines caractéristiques pertinentes, de manière à construire des modèles parcimonieux et robustes. Ces derniers ont permis d'obtenir des résultats intéressants pour la prédiction du résultat du tilt-test au terme notamment, des dix premières minutes de l'examen. Ces performances ont pu être considérablement améliorées par le développement de nouvelles techniques de fouille de données, permettant d'extraire très e- cacement de la connaissance. Les méthodes mises en place s'articulent autour de la sélection de variables et de l'interprétation de projections non linéaires. Ces méthodes, bien que développées autour de notre thématique, se sont montrées reproductibles lors de tests sur d'autres ensembles de données.

Le domaine de la simulation numérique évolue vers des simulations de phénomènes physiques toujours plus complexes. Cela se traduit typiquement par le couplage de plusieurs codes de simulation, où chaque code va gérer une physique (simulations multi-physiques) ou une échelle particulière (simulations multi-échelles). Dans ce cadre, l'analyse des résultats des simulations est un point clé, que ce soit en phase de développement pour valider les codes ou détecter des erreurs, ou en phase de production pour confronter les résultats à la réalité expérimentale. Dans tous les cas, le pilotage de simulations peut aider durant ce processus d'analyse des résultats. L'objectif de cette thèse est de concevoir et de réaliser une plate-forme logicielle permettant de piloter de telles simulations. Plus précisément, il s'agit à partir d'un client de pilotage distant d'accéder ou de modifier les données de la simulation de manière cohérente, afin par exemple de visualiser "en-ligne" les résultats intermédiaires. Pour ce faire, nous avons proposé un modèle de pilotage permettant de représenter des simulations couplées et d'interagir avec elles efficacement et de manière cohérente. Ces travaux ont été validés sur une simulation multi-échelles en physique des matériaux.

Internet ainsi que tous les moyens numériques modernes disponibles pour communiquer, s'informer ou se divertir génèrent des données en quantités de plus en plus importantes. Dans des domaines aussi variés que la recherche d'information, la bio-informatique, la linguistique computationnelle ou la sécurité numérique, des méthodes automatiques capables d'organiser, classifier, ou transformer des téraoctets de données apportent une aide précieuse. L'apprentissage artificiel traite de la conception d'algorithmes qui permettent d'entraîner de tels outils à l'aide d'exemples d'apprentissage. Utiliser certaines de ces méthodes pour automatiser le traitement de problèmes complexes, en particulier quand les quantités de données en jeu sont insurmontables pour des opérateurs humains, paraît inévitable. Malheureusement, la plupart des algorithmes d'apprentissage actuels, bien qu'efficaces sur de petites bases de données, présentent une complexité importante qui les rend inutilisables sur de trop grandes masses de données. Ainsi, il existe un besoin certain dans la communauté de l'apprentissage artificiel pour des méthodes capables d'être entraînées sur des ensembles d'apprentissage de grande échelle, et pouvant ainsi gérer les quantités colossales d'informations générées quotidiennement. Nous développons ces enjeux et défis dans le Chapitre 1. Dans ce manuscrit, nous proposons des solutions pour réduire le temps d'entraînement et les besoins en mémoire d'algorithmes d'apprentissage sans pour autant dégrader leur précision. Nous nous intéressons en particulier aux Machines à Vecteurs Supports (SVMs), des méthodes populaires utilisées en général pour des tâches de classification automatique mais qui peuvent être adaptées à d'autres applications. Nous décrivons les SVMs en détail dans le Chapitre 2. Ensuite, dans le Chapitre 3, nous étudions le processus d'apprentissage par descente de gradient stochastique pour les SVMs linéaires. Cela nous amène à définir et étudier le nouvel algorithme, SGD-QN. Après cela, nous introduisons une nouvelle procédure d'apprentissage : le principe du “Process/Reprocess”. Nous déclinons alors trois algorithmes qui l'utilisent. Le Huller et LaSVM sont présentés dans le Chapitre 4. Ils servent à apprendre des SVMs destinés à traiter des problèmes de classification binaire (décision entre deux classes). Pour la tˆache plus complexe de prédiction de sorties structurées, nous modifions par la suite en profondeur l'algorithme LaSVM, ce qui conduit à l'algorithme LaRank présenté dans le Chapitre 5. Notre dernière contribution concerne le problème récent de l'apprentissage avec une supervision ambigüe pour lequel nous proposons un nouveau cadre théorique (et un algorithme associé) dans le Chapitre 6. Nous l'appliquons alors au problème de l'étiquetage sémantique du langage naturel. Tous les algorithmes introduits dans cette thèse atteignent les performances de l'état-de-l'art, en particulier en ce qui concerne les vitesses d'entraînement. La plupart d'entre eux ont été publiés dans des journaux ou actes de conférences internationaux. Des implantations efficaces de chaque méthode ont également été rendues disponibles. Dans la mesure du possible, nous décrivons nos nouveaux algorithmes de la manière la plus générale possible afin de faciliter leur application à des tâches nouvelles. Nous esquissons certaines d'entre elles dans le Chapitre 7.

De nombreux problèmes d'optimisation issus du monde réel, notamment dans le domaine de la logistique, doivent faire face à beaucoup de difficultés. En effet, ils sont souvent caractérisés par des espaces de recherche vastes et complexes, de multiples fonctions objectif contradictoires, et une foule d'incertitudes qui doivent être prises en compte. Les métaheuristiques sont des candidates naturelles pour résoudre ces problèmes, ce qui les rend préférables aux méthodes d'optimisation classiques. Toutefois, le développement de métaheuristiques efficaces découle d'un processus de recherche complexe. Le cœur de ce travail réside en la conception, l'implémentation et l'analyse expérimentale de métaheuristiques pour l'optimisation multiobjectif, ainsi que leurs applications à des problèmes logistiques de tournées et d'ordonnancement. Tout d'abord, une vue unifiée de ces approches est présentée, puis intégrée dans une plateforme logicielle dédiée à leur implémentation, ParadisEO-MOEO. Ensuite, plusieurs approches de coopération, combinant des métaheuristiques pour l'optimisation multiobjectif, sont proposées. Enfin, la question de la prise en compte l'incertitude est abordée dans le contexte de l'optimisation multiobjectif.