Intuitivement, une simulation graphique (monde virtuel, jeu,...) peut etre vue comme un espace borne dans lequel plusieurs entites, disposant chacune d'un comportement propre, evoluent en parallele. Il parait donc naturel d'utiliser des langages concurrents pour programmer ces comportements. Cependant, c'est rarement le cas pour des raisons de complexite de programmation et de deboguage, de non-determinisme et d'efficacite. Nous proposons d'utiliser l'Approche Reactive introduite par F. Boussinot qui permet de definir clairement les comportements d'entites graphiques. Nous avons enrichi les Icobjs qui est un modele d'objets reactifs graphiques. Il offre la possibilite a des non-specialistes de construire graphiquement des comportements complexes a partir de comportements simples et de constructeurs graphiques. Nous avons realise une implementation dont l'objet central est Icobj. Il definit une structure minimale dynamiquement extensible pour permettre une construction graphique generique. Un icobj particulier, le Workspace, execute et affiche les icobjs qu'il contient. Les comportements sont executes par un moteur reactif dedie aux Icobjs appele Reflex. Il reprend les principales primitives du formalisme Junior en modifiant la semantique de certaines instructions et en y ajoutant de nouvelles. Toutes les instructions sont formalisees par des regles de reecritures au format SOS. De plus, nous avons developpe un environnement qui permet d'interagir dynamiquement avec les simulations. Enfin, nous presentons quelques experimentations autour de l'utilisation des Icobjs dans le cadre de simulations distribuees, de simulations physiques ou de simulations multi-horloges.

Cette thèse présente une perspective relationnelle à plusieurs aspects de la programmation. L'algèbre relationnelle de Tarski est utilisée pour formuler, et parfois résoudre, des problèmes pertinents à la programmation tels que: la spécification de programmes, l'analyse fonctionnellle de programmes, la vérification de programmes, la conception de programmes et le traitement d'erreurs dans les programmes. La perspective que nous adoptons dans cette thèse est caractérisée par les prémisses suivantes: les programmes sont spécifiés à l'aide de relations; l'analyse fonctionnellle de programmes se fait par composition de fonctions; la conception de programmes se fait par décomposition de relations

Le couplage des approches orientées objets avec la méthode B est une piste pour l'amélioration de l'activité de spécification et de développement de logiciels. La méthode B fournit des notations et des outils supports puissants permettant de modéliser et de vérifier des modèles. Les approches objets fournissent des mécanismes intéressants pour la structuration et le développement de gros systèmes. L'apport de notre travail de thèse contribue aux activités de couplage entre ces deux formalismes en utilisant le prouveur de B pour valider et vérifier des spécifications UML.<br /><br />En étendant les schémas de dérivation d'UML vers B proposés dans des travaux précédents réalisés dans l'équipe de recherche Dédale, nous proposons une approche de dérivation en B de méta-modèles UML, de diagrammes statiques et de diagrammes dynamiques. L'objectif de cette proposition est de vérifier la sémantique et la cohérence entre différents diagrammes de spécifications UML.<br /><br />Notre thèse apporte aussi une contribution au développement de spécifications objets en utilisant la méthode B. La première proposition concerne la prise en compte de certains types d'associations entre classes lors de la dérivation en B. La deuxième proposition concerne la validation de spécifications orientées objets décrites à l'aide de diagrammes de séquence UML2.0.

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.

Pour satisfaire les exigences du marché, les outils de vérification formelle doivent permettre aux concepteurs de vérifier des descriptions complexes et de raisonner sur des domaines de valeurs grands ou infinis. Il est nécessaire de se concentrer sur la correction d'algorithmes et sur les propriétés mathématiques essentielles des blocks à concevoir. La plupart des outils de vérification formelle comme les "Model-checkers" sont restrictifs car ils ne peuvent travailler avec des niveaux plus haut que le "RTL", et ils sont également limités sur le nombre total d'états. Les démonstrateurs de théorèmes ne souffrent pas de ces restrictions, mais ne sont pas automatiques et requièrent des méthodes pour faciliter leur utilisation systématique. Cette thèse aborde la vérification formelle de descriptions VHDL au moyen du démonstrateur ACL2. Nous proposons un environnement combinant simulation symbolique et démonstrateur de théorèmes pour l'analyse formelle de descriptions de haut niveau d'abstraction. Plus précisément, notre approche consiste à développer des méthodes<br />- pour formaliser un sous-ensemble de VHDL,<br />- pour "diriger" le démonstrateur pour effectuer de la simulation symbolique<br />- pour utiliser ces résultats pour les preuves.<br />Un outil a été développé combinant des traducteurs (VHDL vers ACL2), des moteurs de simulation symbolique et de preuves, et une interface utilisateur. Les définitions et les théorèmes sont générés automatiquement. Un même modèle généré est ainsi utilisé pour toutes les tâches. Nous aspirons à fournir au concepteur une méthodologie pour insérer la vérification formelle le plus tôt possible dans le cycle de conception. Le démonstrateur est utilisé pour des manipulations symboliques et pour prouver qu'ils sont équivalents à une fonction spécifiée. Le résultat de cette thèse est de rendre la technique de démonstration de théorèmes acceptable dans une équipe de concepteur du point de vue de la facilité d'utilisation, et de diminuer le temps de vérification.

La vérification formelle de systèmes concurrents temps réels se heurte au problème de l'explosion du nombre d'états à explorer. Ce problème connu sous le nom ``d'explosion combinatoire'' à plusieurs causes. Cette thèse s'intéresse à deux d'entre-elles. · Pour lutter contre l'explosion due à la représentation du parallélisme par l'entrelacement d'actions, cette thèse propose des techniques basées sur l'approche des ordres-partiels pour construire un graphe réduit. Pour exploiter les ordres-partiels, les techniques proposées utilisent la construction de « pas de transitions » afin de limiter le nombre d'états explorés. Différentes constructions des « pas de transitions » sont proposées en fonction de la classe de propriétés que l'on souhaite préserver (Blocages, Équivalence de traces, LTL). · Pour lutter contre l'explosion due aux contraintes temporelles, cette thèse propose une approche par sur-approximation du comportement. L'objectif est d'avoir un graphe abstrait du comportement de la sur-approximation plus petit que celui du système. Comme classiquement, les techniques d'abstractions permettent d'obtenir une procédure de décision semi-effective. Lorsque l'analyse de la sur-approximation ne permet pas de conclure, la thèse propose une méthode effective permettant de conclure pour les formules de LTL: le système est analysé, guidé par les résultats obtenus sur la sur-approximation. Cette thèse présente les algorithmes de ces différentes techniques de réduction et l'outil tina (http://www.laas.fr/tina) dans lequel ils ont été implémentés.

Ce travail aborde le problème de la validation de spécifications de services téléphoniques et notamment la recherche d'interactions entre services. Une interaction correspond à la modification du comportement d'un ou plusieurs services, du fait de la coexistence des services. L'interaction est un obstacle majeur au développement de l'offre de services de télécommunications. La validation de spécifications requiert une modélisation des services et du réseau sous-jacent. Nous proposons une méthode de spécification formelle et de validation de services. Celle-ci est basée sur l'utilisation d'un formalisme synchrone pour la modélisation et la spécification, et sur la mise en oeuvre de méthodes de test pour la validation. Nous avons à cette fin proposé une méthode de test adaptée au problème. Cette méthode a été intégrée à Lutess, un environnement de test fonctionnel de systèmes réactifs synchrones, reposant sur un principe de génération de données dynamique et aléatoire. Elle est basée sur la notion de "guidage par schémas". Un schéma représente une classe de comportements de l'environnement du système sous test, comportements que l'on souhaite tester principalement, soit parce qu'ils sont réalistes, soit parce qu'ils conduisent à une situation estimée critique. Cette méthode a été formalisée, puis validée expérimentalement dans plusieurs études de cas conséquentes, en particulier lors du premier concours de détection d'interaction proposé en marge de la conférence "Feature Interaction Workshop", qui a consacré Lutess "Meilleur outil pour la détection d'interactions".

Nous considérons une sous classe d'automates temporisés probabilistes où les contraintes temporelles au niveau des gardes et des invariants sont exprimées par des paramètres. Cette sous classe est appelée la classe des automates Temporisés Probabilistes Paramétrés Semi Déterminés (ATPP Semi Déterminés). Cette classe d'automates se définit en particulier par l'attribution d'une unique distribution à chaque état et par des gardes de la forme x<=a où a est un paramètre ou un entier naturel. Nous imposons de plus deux propriétés sur ces automates qui sont celles de non blocage et fortement non zenon. Notre travail vise à calculer le temps moyen maximal de convergence vers un état dit absorbant q_end dans ce type d'automates. L'unique méthode traitant déjà ce type de problème fait appel à la discrétisation du temps et à l'application de techniques de programmation linéaire. Elle est cependant exponentielle car elle dépend du nombre d'horloges et de la plus grande constante à laquelle sont comparées les horloges, lors de la discrétisation. Le graphe résultant peut être de taille exponentielle. Pour tout ATPP Semi Déterminé, on définit un automate totalement déterministe, appelé ATPP Déterminé, en remplaçant toute garde de la forme x<=a par une garde de la forme x=a. Le temps d'attente en chaque état est ainsi fixé par la valuation de l'état initial qui remet toutes les horloges à zéro. Nous démontrons que le temps moyen de convergence vers q_end dans l'ATPP Déterminé est égal au temps moyen maximal de convergence dans l'ATPP Semi Déterminé dont il découle. Pour calculer le temps moyen de convergence vers q_end nous construisons à partir de l'ATPP Déterminé un graphe appelé "graphe des macro-steps" qui contient de façon concise l'information nécessaire au calcul du coût moyen de convergence vers q_end. Ce graphe est de taille polynomiale et se construit en temps polynomial. Le calcul du temps moyen de convergence dans le graphe des macro-steps est solution d'un système linéaire, comme dans le cas des chaînes de Markov avec coûts. On résout ce système linéaire en temps polynomial, ce qui permet d'obtenir finalement le temps moyen maximal de convergence vers q_end dans l'ATPP Semi Déterminé. Nous appliquons enfin cette méthode à certains protocoles de communication, notamment BRP (Bounded Retransmission Protocol) et CSMA/CD (Carrier Sense Multiple Access with Collision Detection).

Le sujet principal de cette thèse porte sur la fouille de données numériques et plus particulièrement de données d'expression de gènes. Ces données caractérisent le comportement de gènes dans diverses situations biologiques (temps, cellule, etc.). Un problème important consiste à établir des groupes de gènes partageant un même comportement biologique. Cela permet d'identifier les gènes actifs lors d'un processus biologique, comme par exemple les gènes actifs lors de la défense d'un organisme face à une attaque. Le cadre de la thèse s'inscrit donc dans celui de l'extraction de connaissances à partir de données biologiques. Nous nous proposons d'étudier comment la méthode de classification conceptuelle qu'est l'analyse formelle de concepts (AFC) peut répondre au problème d'extraction de familles de gènes. Pour cela, nous avons développé et expérimenté diverses méthodes originales en nous appuyant sur une extension peu explorée de l'AFC : les structures de patrons. Plus précisément, nous montrons comment construire un treillis de concepts synthétisant des familles de gènes à comportement similaire. L'originalité de ce travail est (i) de construire un treillis de concepts sans discrétisation préalable des données de manière efficace, (ii) d'introduire une relation de similarité entres les gènes et (iii) de proposer des ensembles minimaux de conditions nécessaires et suffisantes expliquant les regroupements formés. Les résultats de ces travaux nous amènent également à montrer comment les structures de patrons peuvent améliorer la prise de d écision quant à la dangerosité de pratiques agricoles dans le vaste domaine de la fusion d'information.

La fusion d'informations consiste à résumer plusieurs informations provenant des différentes sources en une information exploitable et utile pour l'utilisateur. Le problème de la fusion est délicat surtout quand les informations délivrées sont incohérentes et hétérogènes. Les résultats de la fusion ne sont pas souvent exploitable et utilisables pour prendre une décision, quand ils sont imprécis. C'est généralement due au fait que les informations sont incohérentes. Plusieurs méthodes de fusion sont proposées pour combiner les informations imparfaites et elles appliquent l'opérateur de fusion sur l'ensemble de toutes les sources et considèrent le résultat tel qu'il est. Dans ce travail, nous proposons une méthode de fusion fondée sur l'Analyse Formelle de Concepts, en particulier son extension pour les données numériques : les structures de patrons. Cette méthode permet d'associer chaque sous-ensemble de sources avec son résultat de fusion. Toutefois l'opérateur de fusion est choisi, alors un treillis de concept est construit. Ce treillis fournit une classification intéressante des sources et leurs résultats de fusion. De plus, le treillis garde l'origine de l'information. Quand le résultat global de la fusion est imprécis, la méthode permet à l'utilisateur d'identifier les sous-ensemble maximaux de sources qui supportent une bonne décision. La méthode fournit une vue structurée de la fusion globale appliquée à l'ensemble de toutes les sources et des résultats partiels de la fusion marqués d'un sous-ensemble de sources. Dans ce travail, nous avons considéré les informations numériques représentées dans le cadre de la théorie des possibilités et nous avons utilisé trois sortes d'opérateurs pour construire le treillis de concepts. Une application dans le monde agricole, où la question de l'expert est d'estimer des valeurs des caractéristiques de pesticide provenant de plusieurs sources, pour calculer des indices environnementaux est détaillée pour évaluer la méthode de fusion proposée.