Dans le domaine du Travail Coopératif Assisté par Ordinateur (TCAO) la recherche sinterroge toujours sur les fondements à adopter lors du développement dapplications collaboratives, aussi dites collecticiels, capables de supporter et de répondre au mieux aux besoins des utilisateurs. Outre la multidisciplinarité associée à ce domaine, le fait que les activités collaboratives impliquent plusieurs personnes exprimant des besoins différents et souvent imprévisibles de travail en groupe imposent des fortes exigences en terme dévolutivité et flexibilité pour les applications collaboratives. Manque dun environnement collaboratif intégré assez ouvert, extensible et reconfigurable pour répondre à ces exigences, différentes applications collaboratives doivent être parallèlement employées pour réaliser de manière effective un travail en groupe. Bien quelles soient utilisées pour accomplir une tâche collaborative commune, ces applications sont exécutées de manière indépendante, sans profiter réellement les unes des autres. Lintégration de telles applications permettrait de les faire interagir de manière dynamique tout en combinant de manière contrôlée leurs fonctionnalités. Cette thèse a donc pour objectif de concevoir un nouvel environnement pour rendre possible lintégration de collecticiels existants tout en évitant de considérer des détails internes à ces systèmes. Cet environnement, que nous avons appelé LEICA (Loosely-coupled Environment for Integrating Collaborative Applications) définit une approche générale dintégration faiblement couplée qui sappuie sur la technologie des services Web, sur un système de notification dévénements, et sur des politiques de collaboration pour contrôler les interactions entre applications intégrées. Nous réalisons tout dabord une description informelle de lapproche générale dintégration, où les applications intégrées sont initialement contactées à travers leurs interfaces de services Web et interagissent par la suite en échan geant des notifications dévénements. Leurs interactions sont contrôlées par la politique de collaboration spécifiée pour une session de travail définissant comment lactivité collaborative supportée par une application est affectée par linformation reçue dune ou plusieurs autres applications. Nous spécifions de façon détaillée larchitecture de LEICA permettant de mettre en Suvre une telle approche dintégration. Nous proposons ensuite une méthode pour formaliser et valider cette architecture au moyen du profil UML/SDL et du module de simulation supportés par loutil TAU G2 de Telelogic. Un premier prototype de LEICA a été également implémenté et deux applications collaboratives se trouvent actuellement intégrée à lenvironnement. null null

Valiant définit des analogues algébriques des classes P et NP. Nous caractérisons les classes VP et VQP, d'où une preuve simplifiée de VNP = VNPe et de la VQP-complétude du déterminant, et la preuve d'une conjecture de Bürgisser. Les classes VPo et VNPo, définies sans constantes arbitraires, donnent facilement un lien entre la complexité d'un polynôme et celle de sa fonction coefficient: VNPo est stable par passage à la fonction coefficient et réciproquement; supposer ce résultat pour VPo est équivalent à VPo = VNPo. Pour traiter le cas du degré non borné, il faut un calcul rapide des coefficients binomiaux, faisable en caractéristique positive et peu probable en caractéristique 0. Nous étudions enfin un problème lié: l'effet de la dérivation sur la complexité. Nous retrouvons le résultat de Kaltofen (le nombre de variables fait exploser la taille plus que l'ordre de dérivation) et donnons un calcul simultané des dérivées partielles.

L'évolution constante des processeurs vers des architectures proposant des capacités superscalaires, de parallélisme au niveau des instructions, de prédiction, de spéculation et la multiplication des niveaux de hiérarchie mémoire donnent de plus en plus d'importance au travail du compilateur.<br />Dans cette thèse, nous nous intéressons aux transformations du programme source destinées à l'optimisation dans la chaîne de compilation, et plus particulièrement à une transformation appelée décalage d'instructions.<br />Cette transformation sert de base au pipeline logiciel, elle a une influence sur le parallélisme au niveau des instructions et l'utilisation des registres.<br />Elle intervient également comme composante des techniques de parallélisation de boucles par ordonnancement affine.<br />Nous avons voulu mieux comprendre les perspectives offertes par le décalage d'instructions, savoir quels objectifs il permettait d'atteindre mais aussi savoir quels problèmes de décalage restaient difficiles.<br />Pour cela nous avons étudié le décalage d'instructions dans plusieurs contextes plus ou moins proches, et apporté des contributions à chacun d'entre eux.<br /><br />Dans le cadre du pipeline logiciel, nous proposons un algorithme polynomial pour déterminer le décalage le plus à même de produire un maximum de parallélisme au niveau des instructions, et une étude expérimentale de l'efficacité absolue de la technique à l'aide de l'outil logiciel que nous avons réalisé dans ce but : PASTAGA (pour Plate-forme d'Analyse Statistique et de Tests d'Algorithmes sur Graphes Aléatoires).<br />Dans le cadre de l'utilisation des registres (stage scheduling), de la parallélisation de boucle et de la localité, nous apportons des réponses aux problèmes de décalage d'instructions associés~: complexité, solutions exactes, approximations.

L'étude de programmes probabilistes intéresse plusieurs domaines de l'informatique : les réseaux, l'embarqué, ou encore la compilation optimisée. C'est tâche malaisée, en raison de l'indécidabilité des propriétés sur les programmes déterministes à états infinis, en plus des difficultés provenant des aspects probabilistes.<br /><br />Dans cette thèse, nous proposons un langage de formules permettant de spécifier des propriétés de traces de systèmes de transition probabilistes et non-déterministes, englobant celles spécifiables par des automates de Büchi déterministes. Ces propriétés sont en général indécidables sur des processus infinis.<br /><br />Ce langage a à la fois une sémantique concrète en termes d'ensembles de traces et une sémantique abstraite en termes de fonctions mesurables. Nous appliquons ensuite des techniques d'interprétation abstraite pour calculer un majorant de la probabilité dans le pire cas de la propriété étudiée et donnons une amélioration de cette technique lorsque l'espace d'états est partitionné, par exemple selon les points de programme. Nous proposons deux domaines abstraits convenant pour cette analyse, l'un paramétré par un domaine abstrait non probabiliste, l'autre modélisant les gaussiennes étendues.<br /><br />Il est également possible d'obtenir de tels majorants par des calculs propageant les mesures de probabilité en avant. Nous donnons une méthode d'interprétation abstraite pour analyser une classe de formules de cette façon et proposons deux domaines abstraits adaptés à ce type d'analyse, l'un paramétré par un domaine abstrait non probabiliste, l'autre modélisant les queues sous-exponentielles. Ce dernier permet de prouver la terminaison probabiliste de programmes.<br /><br />Les méthodes décrites ci-dessus sont symboliques et ne tirent pas parti des propriétés statistiques des probabilités. Nous proposons d'autre part une méthode de Monte-Carlo abstrait, utilisant des interpréteurs abstraits randomisés.

Après un état de l'art sur l'ordonnancement en général et l'ordonnancement temps réel en particulier permetttant de préciser les notions utilisées par la suite et après avoir motivé l'intérêt d'une nouvelle contrainte temps réel de latence, nous proposons un modèle qui formalise les systèmes temps réel avec contraintes de précédences, de périodicités et de latences. Dans ce modèle, les précédences sont définies par un graphe orienté acyclique infiniment répété. Pour le cas monoprocesseur, on étudie trois problèmes d'ordonnancement : celui des systèmes avec contraintes de précédences et de périodicités, celui des systèmes avec contraintes de précédences et de latences et enfin celui des systèmes avec contraintes de précédences, de périodicités et de latences. Pour chaque problème on étudie la cohérence entre les différentes contraintes, on donne des conditions d'ordonnançabilité et on propose un algorithme prouvé optimal dans le sens où s'il y a un ordonnancement, l'algorithme le trouvera. On passe ensuite au cas multiprocesseur où l'architecture est définie par un graphe non-orienté. On étudie trois problèmes d'implantation (distribution et ordonnancement) dans les mêmes cas qu'en monoprocesseur en tenant compte des temps de communications. On prouve que ces trois problèmes sont NP-difficiles et on propose, donc, des heuristiques. Les performances de chaque heuristique sont comparées à celles d'algorithme exacte de type "branch and bound", en utilisant des simulations numériques.

Le domaine de la simulation interactive ou computational steering a pour but d'améliorer le processus de simulation numérique (modélisation, calcul, analyse) en le rendant plus interactif. Dans cette approche, le scientifique n'attend plus passivement les résultats de la simulation ; il peut visualiser en ligne l'évolution des données calculées et peut interagir à tout moment en modifiant certains paramètres à la volée ou plus généralement en pilotant le déroulement des calculs. Un tel outil peut s'avérer très utile pour la compréhension des phénomènes physiques modélisés et la détection d'erreurs dans le cas de simulations longues.<br /><br />L'objectif de cette thèse est de concevoir et de développer une plate-forme logicielle, appelée EPSN (Environnement pour le Pilotage des Simulations Numériques), permettant de piloter une application numérique parallèle en s'appuyant sur des outils de visualisation eux-mêmes parallèles. En d'autres termes, il s'agit de mettre au service des scientifiques les capacités de la visualisation parallèle et plus largement de la réalité virtuelle (environnement immersif, murs d'images), une étape aujourd'hui cruciale pour la conception et l'exploitation de simulations numériques complexes en vraie grandeur. La mise en oeuvre d'un couplage efficace entre simulation et visualisation soulève deux problèmes majeurs, que nous étudions<br />dans cette thèse et pour lesquels nous souhaitons apporter une contribution : le problème de la coordination efficace des opérations de pilotages en parallèle et le problème de la redistribution pour des données complexes (grilles structurées, ensembles de particules, maillages non structurés).

Le calcul de réécriture est un lambda-calcul avec filtrage. Cette thèse est consacrée à l'étude de systèmes de types pour ce calcul et à son utilisation dans le domaine de la déduction.<br /><br />Nous étudions deux paradigmes de typage. Le premier est inspiré du lambda-calcul simplement typé, mais un terme peut y être typé sans être terminant. Nous l'utilisons donc pour représenter des programmes et des systèmes de réécriture. La seconde famille de systèmes de types que nous étudions est adaptée des Pure Type Systems. Nous en démontrons la normalisation forte grâce à une traduction vers le lambda-calcul typé.<br /><br />Enfin nous proposons deux approches pour l'utilisation du calcul de réécriture en logique. La première consiste à définir des termes de preuve pour la déduction modulo à l'aide des systèmes fortement normalisants. Dans la seconde, nous définissons une généralisation de la déduction naturelle et nous montrons que le filtrage est utile pour représenter les règles de ce système de déduction.

Cette thèse traite de la conception de système multi-agents. Elle se focalise sur des approches formelles et s'est donné pour objectif à long terme de construire de manière automatique et décentralisée les comportements d'agents coopératifs devant résoudre collectivement un problème. Ce travail a cherché à proposer des méthodes pour construire les comportements d'agents sociaux, capables de prendre en compte à l'exécution la présence d'autres agents dans le système.<br /><br />Les formalismes existants comme les DEC-POMDPs parviennent à représenter des problèmes multi-agents mais ne représentent pas au niveau individuel la notion d'interaction fondamentale dans les systèmes collectifs. Ceci induit une complexité algorithmique importante dans les algorithmes de résolution. Afin de donner aux agents la possibilité d'appréhender la présence d'autres agents et de structurer de manière implicite les systèmes multi-agents, cette thèse propose un formalisme original, l'interac-DEC-POMDP inspiré des DEC-POMDPs et d'Hamelin, une simulation développée au cours de cette thèse et issue d'expériences conduites en éthologie. La spécificité de ce formalisme réside dans la capacité offerte aux agents d'interagir directement et localement entre eux. Cette possibilité permet des prises de décision à un niveau intermédiaire entre des décisions globales impliquant l'ensemble des agents et des décisions purement individuelles.<br /><br />Nous avons proposé en outre un algorithme décentralisé basé sur des techniques d'apprentissage par renforcement et une répartition heuristique des gains des agents au cours des interactions. Une démarche expérimentale nous a permis de valider sa capacité à produire pour des restriction du formalisme des comportements collectifs pertinents adaptatifs sans qu'aucun agent ne dispose d'une vue globale du système.

Les systèmes d'édition collaborative permettent à plusieurs utilisateurs d'éditer simultanément un document. Aujourd'hui, l'édition collaborative massive est une réalité. Il ne s'agit plus d'éditer à quelques utilisateurs mais à des milliers d'utilisateurs répartis dans le monde. Les éditeurs collaboratifs actuels n'ont pas été conçus pour supporter un nombre si important d'utilisateurs. Les problèmes soulevés ne sont pas d'ordre technologique, ils remettent en cause les fondements algorithmiques des éditeurs. L'objectif de cette thèse est de proposer des algorithmes adaptés à l'édition collaborative massive. Nous montrons qu'un tel algorithme doit assurer trois critères : convergence des données, préservation des intentions et passage à l'échelle. Au regard de l'état de l'art, seul le modèle des transformées opérationnelles (OT) peut concilier ces trois critères.<br />La première contribution de cette thèse montre que l'approche OT conçue pour des éditeurs temps réel peut être utilisée pour réaliser des outils asynchrones. Nous avons réalisé un gestionnaire de configurations dénommé SO6. La seconde contribution est une approche formelle à la conception et à la vérification de fonctions de transformation pour le modèle OT. Cette approche repose sur un démonstrateur automatique de théorème. Avec cette approche, nous montrons que toutes les fonctions de transformation proposées jusqu'ici sont fausses. La troisième et dernière contribution de ce travail est un nouvel algorithme de réplication optimiste (WOOT) adapté à l'édition collaborative massive de structures linéaires. Ce modèle repose sur le calcul monotone d'une extension linéaire des ordres partiels formés par les relations entre les différents éléments de la structure.

Nous proposons un cadre conceptuel pour l'ingénierie des systèmes d'information (SIs) par composants. Ce cadre est basé sur les concepts d'hyperclasse et de composant de SI.<br />Le concept d'hyperclasse est une généralisation du concept de classe. Construite à partir d'un ensemble de classes connexe et complet, une hyperclasse permet d'exprimer des concepts que le niveau de classe n'aurait permis d'exprimer, et se comporte comme une classe : elle dispose d'hyperobjets, d'hyperattributs et d'hyperméthodes, équivalents des concepts d'objet, d'attribut et de méthode pour une classe. Un hyperobjet de l'hyperclasse est formé à partir des objets des classes de l'hyperclasse, atteints par navigation, à partir d'une classe particulière de l'hyperclasse qui est sa classe racine, et en suivant un graphe de navigation. Un hyperattribut de l'hyperclasse est un attribut de l'une de ses classes. Une hyperméthode est une méthode associée à l'hyperclasse qui peut avoir comme opérandes des hyperattributs, des hyperobjets, d'autres hyperméthodes de l'hyperclasse, les classes de l'hyperclasse, leurs objets et leurs méthodes de classes. Le concept d'hyperclasse offre une forme d'indépendance entre la structure du SI et ses traitements.<br />Un composant de SI est une entité autonome et cohérente, dans un modèle de SI, qui regroupe les représentations des espaces informationnel et opérationnel associés à une zone de responsabilité. Il est défini à partir d'une hyperclasse, d'un ensemble de transactions et d'un ensemble de règles d'intégrité du SI. La notion de transaction est associée à une activité productrice ou consommatrice d'informations dans un processus de prise de décision. Les règles d'intégrité sont définies sur un SI pour garantir sa cohérence durant son exploitation.<br />Les concepts d'hyperclasse et de composant de SI sont munis d'ensembles complets d'opération d'évolution. Ils sont définis indépendamment des méthodes, des langages et des technologies dans lesquelles le SI est implanté.<br />Le cadre conceptuel que nous proposons permet notamment de prendre en charge les situations de recouvrement de composants de SI, leur évolution, l'évolution du SI et ses répercussions sur ses composants.