Ce travail de thèse porte sur l'élaboration de modèles de haut-niveau de systèmes pluridisciplinaires à base d'électronique. L'objectif est de réaliser des prototypes virtuels de ces systèmes et de vérifier formellement leur comportement dès les premières étapes du cycle de conception. Grâce à une approche descendante et au formalisme HiLeS, nous réalisons des représentations hiérarchiques qui associent des réseaux de Petri à un ensemble de blocs et de canaux interagissant mutuellement. Nous avons développé l'outil HiLeS Designer pour rendre utilisable le formalisme avec plusieurs améliorations opérationnelles telles que le couplage avec un outil d'analyse de réseaux de Petri (TINA) et la compatibilité avec VHDL-AMS. Nous proposons donc, une plate-forme de conception amont autour de l'outil HiLeS Designer avec des passerelles vers TINA et VHDL-AMS. L'utilisation de cette plate-forme nous a permis d'identifier plusieurs perspectives de développement, notamment vers la conduite de projet.

Les systèmes hybrides sont des systèmes qui combinent des dynamiques discrètes et continues. Cette thèse propose des techniques algorithmiques de vérification et de synthèse pour ces systèmes Le manque de méthodes pour calculer les ensembles atteignables des dynamiques continues est l'obstacle principal vers une méthodologie algorithmique de vérification. Nous développons deux techniques d'atteignabilité approximatives pour les systèmes continus basées sur une méthode efficace pour représenter des ensembles et une combinaison des techniques de la simulation, de la géométrie algorithmique, de l'optimisation, et de la commande optimale. La première technique d'atteignabilité est spécialisée pour les systèmes linéaires et étendue aux systèmes avec entrée incertaine, et la seconde peut être appliquée aux systèmes non-linéaires. En appliquant ces techniques nous développons un algorithme de vérification des propriétés de sûreté pour une large classe des systèmes hybrides avec des dynamiques continues arbitraires et des dynamiques discrètes assez générales. Nous étudions ensuite le problème de la synthèse de contrôleurs de sûreté pour les systèmes hybrides. Nous présentons un algorithme de synthèse des contrôleurs par commutation basé sur le calcul de l'ensemble d'invariance maximal et les techniques d'analyse d'atteignabilité. Nous avons implanté les algorithmes développés dans un outil appelé "d/dt", qui permet la vérification et la synthèse automatique pour les systèmes hybrides avec des inclusions différentielles linéaires. En dehors de nombreux exemples académiques, nous avons appliqué avec succès l'outil pour analyser quelques systèmes pratiques.

Ce travail porte sur la verification formelle de programmes paralleles. Parmi les methodes habituellement utilisees, nous nous interessons aux methodes basees sur la construction d'un modele du programme a verifier; la verification proprement dite s'effectue sur ce modele. Cette approche est limitee par l'explosion de la taille du modele, des que le programme traite est de complexite realiste. Notre but est l'etude et la mise en oeuvre de techniques permettant d'effectuer la verification malgre cette explosion. Les techniques que nous presentons sont liees par une caracteristique commune : l'utilisation de methodes symboliques de representation du modele. Nous etudions en premier lieu des techniques de reduction de modeles. Ces reductions s'operent par rapport a des relations d'equivalence basees sur la notion de bisimulation. Nous etudions en particulier un algorithme de minimisation de modele (\em pendant ) sa generation(Generation de Modele Minimal). Dans une seconde partie, nous nous interessons a deux techniques symboliques de representation de modeles. Il s'agit d'une part de Graphes de Decision Binaires, qui permettent la manipulation efficace de formules booleennes, et d'autre part de systemes d'inequations lineaires, connus sous le nom de polyedres convexes, pour la manipulation de variables entieres. L'utilisation de ces techniques permet de representer et manipuler des modeles de taille souvent prohibitive pour des methodes enumeratives classiques. Nous presentons la mise en oeuvre de methodes de comparaison et reduction de modeles aves les Graphes de Decision Binaires, avec en particulier l'algorithme de Generation de Modele Minimal. L'application de l'outil correspondant a plusieurs exemples de programmes lotos a permis de montrer l'interet, mais aussi les limites de l'utilisation de cette representation symbolique. Enfin, nous presentons une methode d'analyse statique de protocoles, basee sur l'utilisation des polyedres convexes. Cette analyse permet le calcul d'approximations superieures d'invariants du programme et de verifier la veracite de proprietes definies en termes de variables du programme.

Les systèmes multi-agents (SMA) peuvent être utilisé pour modéliser les phénomènes qui peuvent être décomposés en plusieurs agents qui interagissent et qui existent au sein d'un environnement. En particulier, ils peuvent être utilisés pour modéliser les sociétés humaines et animales, aux fins de l'analyse de leurs propriétés par des moyens de calcul. Cette thèse est consacrée à l'analyse automatisée d'un type particulier de ces modèles sociaux, à savoir, celles qui sont fondées sur les principes comportementalistes, qui contrastent avec les approches cognitives plus dominante dans la littérature des SMAs. La caractéristique des théories comportementalistes est l'accent mis sur la définition des comportements basée sur l'interaction entre les agents et leur environnement. De cette manière, non seulement des actions réflexives, mais aussi d'apprentissage, les motivations, et les émotions peuvent être définies. Plus précisément, dans cette thèse, nous introduisons une architecture formelle d'agent (spécifiée avec la Notation Z) basée sur la théorie d'analyse comportementale de B. F. Skinner, ainsi que une notion appropriée et formelle de l'environnement (basée sur l'algèbre de processus pi-calculus) pour mettre ces agents ensemble dans un SMA. La simulation est souvent utilisée pour analyser les SMAs. Les techniques consistent généralement à simuler le SMA plusieurs fois, soit pour recueillir des statistiques, soit pour voir ce qui se passe à travers l'animation. Toutefois, les simulations peuvent être utilisés d'une manière plus orientée vers la vérification si on considère qu'elles sont en réalité des explorations de grandes espaces d'états. Dans cette thèse nous proposons une technique de vérification nouvelle basé sur cette idée, qui consiste à simuler un SMA de manière guidée, afin de vérifier si quelques hypothèses sur lui sont confirmées ou non. À cette fin, nous tirons profit de la position privilégiée que les environnements sont dans les SMAs de cette thèse: la spécification formelle de l'environnement d'un SMA sert à calculer les évolutions possibles du SMA comme un système de transition, établissant ainsi l'espace d'états à vérifier. Dans ce calcul, les agents sont pris en compte en les simulant afin de déterminer, à chaque état de l'environnement, quelles sont leurs actions. Chaque exécution de la simulation est une séquence d'états dans cet espace d'états, qui est calculée à la volée, au fur et à mesure que la simulation progresse. L'hypothèse à étudier, à son tour, est donnée comme un autre système de transition, appelé objectif de simulation, qui définit les simulations désirables et indésirables (e.g., "chaque fois que l'agent fait X, il fera Y plus tard"). Il est alors possible de vérifier si le SMA est conforme à l'objectif de simulation selon un certain nombre de notions de satisfiabilité très précises. Algorithmiquement, cela correspond à la construction d'un produit synchrone de ces deux systèmes de transitions (i.e., celui du SMA et l'objectif de simulation) à la volée et à l'utiliser pour faire fonctionner un simulateur. C'est-à-dire, l'objectif de simulation est utilisé pour guider le simulateur, de sorte que seuls les états concernés sont en réalité simulés. À la fin d'un tel algorithme, il délivre un verdict concluant ou non concluant. Si c'est concluant, il est connu que le SMA est conforme à l'objectif de simulation par rapport aux observations qui ont été faites lors des simulations. Si c'est non-concluant, il est possible d'effectuer quelques ajustements et essayer à nouveau. En résumé, donc, dans cette thèse nous fournissons quatre nouveaux éléments: (i) une architecture d'agent; (ii) une spécification formelle de l'environnement de ces agents, afin qu'ils puissent être composés comme un SMA; (iii) une structure pour décrire les propriétés d'intérêt, que nous avons nommée objectif de simulation, et (iv) une technique pour l'analyse formelle du SMA résultant par rapport à un objectif de simulation. Ces éléments sont mis en œuvre dans un outil, appelé Simulateur Formellement Guidé (FGS, de l'anglais Formally Guided Simulator). Des études de cas exécutables dans FGS sont fournies pour illustrer l'approche.

Depuis l'A380 et avec l'introduction du standard ARINC 661, les systèmes d'affichage et de contrôle des cockpits sont passés d'un rôle de simple afficheur, à celui d'un système interactif permettant à l'équipage d'interagir sur les écrans grâce à l'utilisation d'un ensemble clavier/dispositif de pointage appelé KCCU. L'utilisation de cette nouvelle capacité d'interaction est à ce jour limitée à des interactions avec des systèmes avions non critiques. Pour envisager son extension à des systèmes critiques il faut se poser la question du respect d'exigences de sureté de fonctionnement imposées à de tels systèmes sans pour autant diminuer son niveau d'utilisabilité. Dans cette optique, nous proposons dans le cadre de nos travaux de recherche, différentes approches pour contribuer au développement d'un tel système interactif critique. La première approche est de tendre vers une conception zéro défaut, en réalisant une description précise et non ambigüe des composants logiciels du système interactif en utilisant une technique de description formelle. La seconde approche est l'utilisation de techniques de tolérance aux fautes car il existe toujours des fautes résiduelles de conception, des fautes matérielles ou venant de l'environnement. Dans ce cas, l'utilisation de technique de tolérance aux fautes permet au système de continuer à remplir ses fonctions en dépit de l'occurrence de fautes. La troisième approche est l'explicitation de l'impact des différentes approches de tolérance aux fautes sur l'utilisabilité du système interactif. Cette explicitation est faite au travers de la réalisation et de l'analyse des modèles de tâche, décrivant l'activité de l'utilisateur du système.

Dans les années 90, la commission européenne a sollicité la mise au point d'un système de contrôle commande et de signalisation ferroviaire commun à tous les réseaux des états membres : le système ERTMS " European Railway Traffic Management System ". Il s'agit d'un système réparti complexe dont le déploiement complet est long et coûteux. L'objectif global consiste à diminuer les coûts de validation et de certification liés à la mise en œuvre de ce nouveau système en Europe. La problématique scientifique réside dans la modélisation formelle de la spécification afin de permettre la génération automatique des scénarios de test. Les verrous scientifiques, traités dans cette thèse, sont liés d'une part à la transformation de modèle semi-formel en modèle formel en préservant les propriétés structurelles et fonctionnelles des constituants réactifs du système réparti, et d'autre part à la couverture des tests générés automatiquement. Les constituants sont sous la forme de boîte noire. L'objectif consiste à tester ces derniers à travers la spécification ERTMS. Nous avons développé une approche de modélisation basée sur le couplage de modèles semi-formels (UML) et de modèles formels (Réseaux de Petri). Ce couplage se fait à travers une technique de transformation de modèles. Nous avons développé ensuite une méthode de génération automatique de scénarios de test de conformité à partir des modèles en réseaux de Petri. Les scénarios de test ont été considérés comme une séquence de franchissement filtrée puis réduite du réseau de Petri interprété représentant la spécification. Ces scénarios ont été exécutés sur notre plateforme de simulation ERTMS

La validation des systèmes critiques réalistes nécessite d'être capable de modéliser et de vérifier formellement des données complexes, du parallélisme asynchrone, et du temps-réel simultanément. Des langages de haut-niveau, comme ceux qui héritent des fondations théoriques des algèbres de processus, ont une syntaxe concise et une grande expressivité pour représenter ces aspects. Cependant, ils disposent de peu d'outils logiciels permettant d'appliquer des algorithmes efficaces du model-checking. Néanmoins, de tels outils existent pour des modèles graphiques, de niveau plus bas, tels que les automates temporisés (par exemple Uppaal) et les réseaux de Petri temporisés (par exemple Tina). Les modèles intermédiaires sont un moyen pour combler le fossé qui sépare les langages des modèles graphiques. Par exemple, NTIF (New Technology Intermediate Format) a été proposé pour représenter des processus séquentiels non-temporisés qui manipulent des données complexes. Dans cette thèse, nous proposons un nouveau modèle nommé ATLANTIF, qui enrichit NTIF de constructions temps-réel et de compositions parallèles de processus séquentiels. Leur synchronisation est exprimée d'une manière simple et intuitive par la nouvelle notion de synchroniseur. Nous montrons qu'ATLANTIF est capable d'exprimer les constructions principales des langages de haut niveau. Nous présentons aussi des traducteurs d'ATLANTIF vers des automates temporisés (pour la vérification avec Uppaal) et vers des réseaux de Petri temporisés (pour la vérification avec Tina). Ainsi, ATLANTIF étend la classe des systèmes qui peuvent en pratique être vérifiés formellement, ce que nous illustrons par un exemple.

Cette thèse est consacrée à l'étude de l'existence d'applications holomorphes entre des sous-variétés réelles dans des espaces complexes. On s'intéresse plus particulièrement à la convergence et à l'approximation à la Artin d'applications formelles entre sous-variétés réelles. Tout d'abord, on montre la convergence des applications formelles de jacobien non identiquement nul entre une sous-variété générique analytique réelle minimale et une sous-variété générique analytique réelle holomorphiquement non dégénérée. Grâce à ce résultat, on obtient la convergence de toutes les applications formelles entre une hypersurface analytique réelle minimale holomorphiquement non dégénérée et une hypersurface qui ne contient pas de courbe holomorphe. D'autre part, on établit la convergence de l'application de réflexion associée à une application formelle de jacobien non identiquement nul entre hypersurfaces lorsque l'hypersurface source est minimale. Cela nous permet ensuite de montrer un résultat d'approximation à la Artin dans ce même cas. Pour finir, on prouve un théorème artinien pour des applications CR lisses entre deux sous-variétés dans des espaces complexes de dimensions différentes.

Cette thèse en informatique se place dans le cadre de l'Analyse de Concepts Formels (ACF) ou les treillis de Galois. Ce sont des outils basés sur des opérateurs mathématiques appelés fermetures de Galois permettant de calculer des concepts. Un concept est formé d'un ensemble d'objets partageant tous un ensemble d'attributs communs. Ces concepts sont extraits à partir d'un contexte qui est une table de relation binaire entre ces objets et ces attributs. Nous nous intéressons à des contextes complexes dont la complexité repose sur deux axes. D'une part, les contextes multi-valués dont les attributs se divisent en plusieurs modalités. D'autre part, les contextes flous dont la relation entre objets et attributs n'est pas binaire. Nous définissons les contextes multi-valués flous qui héritent de ces deux complexités et présentons deux conversions des données multi-valuées floues. La première conversion est une binarisation par une disjonction totale des attributs permettant d'une part l'exploitation d'outils comme des implications et d'autre part de comparer et combiner les treillis avec des méthodes statistiques telles que l'analyse factorielle. La seconde conversion est issue de l'échelonnage histogramme que nous définissons et qui permet de convertir les attributs en histogrammes. Afin de générer les concepts à partir des histogrammes, nous proposons une nouvelle fermeture de Galois basée sur une mesure de similarité entre ces histogrammes. Cette fermeture permet d'obtenir des concepts pour lesquels les objets possèdent des attributs non plus égaux mais similaires compris entre un minimum et un maximum communs. Nous proposons également des mesures de seuillage pour limiter le nombre de concepts générés et diminuer les temps de calculs. Enfin, deux algorithmes ont été testés pour implémenter cette fermeture : MinMaxNC et MinMaxC, dont nous comparons les performances. Cette thèse trouve son application notamment dans le domaine hydrobiologique dont une problématique est la sélection de traits écologiques de taxons permettant de caractériser l'état écologique des cours d'eau par le comportement des espèces au sein de leur environnement. La sélection de ces traits s'appuie sur la recherche de groupes de taxons possédant des caractéristiques morphologiques et physiologiques (appelés traits biologiques) communes. Ces groupes correspondent à des concepts au sens de l'ACF et les données biologiques se présentent sous la forme d'un contexte multi-valué flou pour lequel nous montrons l'efficacité de notre approche.

Cette thèse est consacrée aux algorithmes de morphologie mathématique qui peuvent considérer les pixels d'une image comme un flux de données. Nous allons démontrer qu'un grand nombre d'algorithmes de morphologie mathématique peuvent être décrits comme un flux de données traversant des unités d'exécution. Nous verrons que cette approche peut aussi fonctionner sur des processeurs génériques possédant un jeu d'instructions multimédia ou sur des cartes graphiques. Pour décrire les algorithmes en flux de données, nous proposons d'utiliser le langage fonctionnel Haskell, ce qui nous permettra de décrire les briques de base de la construction des algorithmes de morphologie mathématique. On applique ces briques dans la description des algorithmes les plus couramment utilisés (dilatation/érosion, opérations géodésiques, fonction distance et nivellements) ce qui facilitera le portage de ces algorithmes sur plusieurs plate-formes. Nous proposons pour la construction des algorithmes morphologiques un mode d'exécution original par macro blocs et nous étudions en profondeur la transposition de cette idée aux architectures SIMD. Nous montrons que l'utilisation des macro blocs est intéressante pour les architectures multimédia et nous montrons également que les algorithmes morphologiques proposés dans cette thèse atteignent de meilleures performances que les implémentations standard. Un nouveau champ s'ouvre ainsi aux algorithmes développés dans les applications de traitement d'images en temps réel. Cette thèse explore également les processeurs graphiques et démontre sur des résultats expérimentaux qu'ils sont, dès à présent, assez performants pour concurrencer les processeurs généraux.