Recherche de nouvelles méthodes de synthèse logique sur différentes cibles technologiques: PLA détaillé libre et PLD de type PAL. Une méthode originale de minimisation deux couches d'un ensemble de fonctions booléennes sur une cible de type PLA libre est étudiée. Une méthode de synthèse sur les réseaux programmables de type PAL, dont les dimensions et les structures sont figées, est aussi proposée

L'étude des moyens de déductions pour entreprendre une construction assistée de programmes mène à la définition d'un système de déduction automatique capable :<br />- de traiter l'égalité d'une façon générale ;<br />- d'entreprendre la preuve de formules qui ne sont pas des théorèmes, d'étudier les causes d'échec ;<br />- d'effectuer un tri pour retirer d'un large ensemble d'informations, celles utiles à la preuve.<br /><br />Ces caractères ont pu être pris en compte dans le cadre d'un système général, de genre "déduction matérielle".<br />Certaines classes d'expression reçoivent toutefois un traitement particulier. Ainsi une méthode de codage permet de déterminer, sans simplification ni mise en forme normale, l'équivalence d'expressions numériques.

Le processus de certification de logiciels est dans la plupart des<br /> cas une tâche laborieuse et coûteuse qui nécessite aussi bien des<br /> méthodes mathématiques, pour exprimer sans ambiguïté et de façon<br /> structurée le comportement attendu du logiciel, que des outils<br /> automatiques pour vérifier ses propriétés. Parmi les techniques de<br /> preuve, la récurrence est parfaitement adaptée pour raisonner sur<br /> des structures de données infinies, comme les entiers et les<br /> listes, ou des systèmes paramétrés.<br /> <br /> Cette thèse comprend deux parties, l'une théorique, l'autre<br /> applicative. La première partie est centrée autour d'un nouveau<br /> concept, l'\emph(ensemble couvrant contextuel) (ECC). Le principe<br /> de preuve par récurrence avec ECC est exprimé par un système<br /> d'inférence abstrait qui introduit des conditions suffisantes pour<br /> son application correcte. La conception modulaire de règles<br /> d'inférence concrètes est un avantage de cette approche. Comme<br /> étude de cas, nous spécifions le système d'inférence du<br /> démonstrateur SPIKE en tant qu'instance de ce système.<br /> <br /> Dans la deuxième partie, nous analysons tout d'abord le problème<br /> d'interactions de services téléphoniques. Nous proposons une<br /> méthodologie pour les détecter et les résoudre, reposant sur des<br /> techniques basées sur la réécriture conditionnelle et la<br /> récurrence. Dans une autre application, nous obtenons, à l'aide<br /> du démonstrateur PVS, la première preuve formelle de l'équivalence<br /> entre deux algorithmes de conformité du protocole ABR. Puis,<br /> nous utilisons SPIKE pour vérifier complètement automatiquement<br /> la majorité des 80 lemmes de cette preuve.

Nous étudions les logiques du temps arborescent en tant qu'outils de spécification et de preuve des programmes. Les différentes logiques modales et temporelles sont comparées par rapport aux deux critères suivantes: puissance d'expression et décidabilité. Cette étude porte essentiellement sur fa comparaison des logiques du temps arborescent et des logiques du temps linéaire. Ensuite, le problème de l'utilisation des logiques du temps arborescent en tant qu'outils de preuves des programmes est étudié. Nous proposons une logique pour la preuve constructive des propriétés des processus contrôlables de CCS. Cette logique est telle, que la relation de congruence induite est la congruence observationnelle de CCS

Nous étudions comment faciliter la réutilisation des <br />preuves formelles en théorie des types. Nous traitons cette question <br />lors de l'étude <br />de la correction du programme de calcul de la racine carrée de GMP. <br />A partir d'une description formelle, nous construisons <br />un programme impératif avec l'outil Correctness. Cette description <br />prend en compte tous les détails de l'implantation, y compris <br />l'arithmétique de pointeurs utilisée et la gestion de la mémoire. <br />Nous étudions aussi comment réutiliser des preuves formelles lorsque<br />l'on change la représentation concrète des données. <br />Nous proposons un outil qui permet d'abstraire <br />les propriétés calculatoires associées à un type inductif dans<br />les termes de preuve.<br />Nous proposons également des outils pour simuler ces propriétés<br />dans un type isomorphe. Nous pouvons ainsi passer, systématiquement,<br />d'une représentation des données à une autre dans un développement<br />formel.

L'objet de cette thèse est d'étudier les capacités du système Coq à mélanger démonstrations et programmes en pratique en essayant d'y implémenter une part du programme Kenzo, un outil de calcul formel en algèbre homologique. À cet effet, nous travaillons sous trois contrainte: nous voulons essayer de lire le programme comme une démonstration avec un contenu calculatoire, ces démonstrations doivent calculer efficacement et nous cherchons à éviter de dupliquer des morceaux de démonstration. Nous montrons dans un premier temps comment le soucis d'efficacité conduit à reconsidérer certains aspects des mathématiques traditionnelle. Nous proposons une abstraction catégorielle adaptée, qui répond à la fois à un soucis de clareté et au besoin de partager les démonstration quand c'est possible. Cette abstraction, bien que différente des propositions traditionnelles, permet de formuler les notions d'algèbre homologique dans un style proche de celui de Kenzo. Nous proposons par ailleurs des modifications au programme de Coq pour rendre les démonstrations plus confortables, et pour permettre d'écrire des programmes plus efficaces. La première modification permet d'utiliser des tactiques plus fines, souvent nécessaire quand l'utilisation des types dépendents se fait commune. La seconde permet d'utiliser les capacité du processeur pour faire des calculs plus efficaces sur des entiers. Pour finir nous proposons quelques pistes pour améliorer le partage et la clareté du code. Malheureusement, nous nous heurtons aux limites du système. Nous montrons ainsi que Coq ne tiens pas forcément ses promesses et qu'il y aura besoin de travaux théoriques pour comprendre comment lever ces limites.

En informatique, les logiques formelles ont une place centrale dans la représentation et le traitement des connaissances. Elles sont utilisées pour la modélisation et la vérification de systèmes informatiques et de leurs propriétés ainsi que pour la formalisation de différents types de raisonnement. Dans ce contexte il existe un large spectre de logiques non-classiques parmi lesquelles les logiques modales jouent un rôle important. Alors que les logiques modales classiques ont été largement étudiées, nous nous focalisons dans cette thèse sur les logiques modales intuitionnistes et aussi hybrides floues en abordant un certain nombre de questions principalement du point de vue de la théorie de la démonstration. Nous proposons pour ces logiques de nouveaux systèmes de preuve, notamment suivant les formalismes de déduction naturelle et de calcul des séquents, qui sont fondés sur de nouvelles structures multi-contextuelles généralisant la structure standard de séquent. Ainsi dans le cadre des logiques modales intuitionnistes formées à partir des combinaisons des axiomes T, B, 4 et 5, nous définissons des systèmes de preuve sans labels ayant de bonnes propriétés comme par exemple celle de la sous-formule. En outre, nous proposons des procédures de décision simples à partir de nos nouveaux calculs des séquents. Nous étudions également la première version intuitionniste de la logique hybride IHL et nous proposons son premier calcul des séquents à partir duquel nous donnons la première démonstration de sa décidabilité. Enfin, nous introduisons une nouvelle famille de logiques hybrides floues fondées sur les logiques modales de Gödel. Nous proposons pour ces logiques des procédures de décision avec génération de contre-modèles en utilisant un ensemble de règles de preuve fondées sur une structure multi-contextuelle adaptée.

Ce travail de thèse porte sur le passage, dans l'enseignement secondaire, d'une géométrie du concret à une géométrie portant sur des objets idéaux. Nous montrons que des environnements de géométrie dynamique tridimensionnelle offrent des conditions favorables à ce passage, que nous détaillons. La réflexion théorique s'appuie sur la Théorie des situations didactiques (Brousseau, 1998) pour proposer des hypothèses quant aux conditions et mécanismes d'apprentissage. En outre, notre questionnement initial est interprété à l'aide de deux cadres principaux. Le point de vue épistémologique des paradigmes géométriques (Houdement et Kuzniak, 2006) permet d'identifier la référence à GII comme un objectif fondamental. L'approche cognitive de Duval (2005, 1994) montre qu'à cette fin, l'élève doit abandonner la visualisation iconique et s'appuyer sur déconstruction dimensionnelle pour l'interprétation et la résolution des problèmes de géométrie. La géométrie dynamique dans l'espace est envisagée comme moteur de cette double perspective, et la déconstruction instrumentale y joue un rôle clef. Ce rôle, ainsi que des hypothèses d'émergences de la déconstruction dimensionnelle, sont précisés par un important travail théorique s'appuyant sur le modèle cKc (Balacheff, 1995; Balacheff et Margolinas, 2005), ainsi que la mise en œuvre d'une ingénierie didactique. Celle-ci apporte une validation expérimentale de plusieurs plusieurs résultats, au nombre desquels : - la pertinence d'analyser l'activité géométrique simultanément en termes de visualisations, déconstructions, et paradigmes géométriques ; - l'intérêt de la géométrie dynamique dans l'espace pour déstabiliser la visualisation iconique ; - l'existence de deux déconstructions instrumentales, et leur rôle fondamental pour l'émergence de la déconstruction dimensionnelle ; - les interactions entre les différentes déconstructions, qui n'étaient pas établies dans les travaux antérieurs ; - la possibilité de produire des situations s'appuyant sur la géométrie dynamique dans l'espace favorisant l'émergence de la déconstruction dimensionnelle ; - l'intérêt du modèle cKc pour la modélisation et l'analyse des phénomènes observés.

Les technologies actuelles permettent l'intégration sur une même puce de systèmes complexes (SoCs) qui sont composés de blocs préconçus (IPs) pouvant être interconnectés grâce à un réseau sur la puce (NoCs). De manière générale, les IPs sont validés par diverses techniques (simulation, test, vérification formelle) et le problème majeur reste la validation des infrastructures des communications. Cette thèse se concentre sur la vérification formelle des réseaux sur puce à l'aide d'un outil de preuve automatique, le démonstrateur de théorèmes ACL2. Un méta-modèle pour les réseaux sur puce a été développé et implémenté dans ACL2. Il satisfait des propriétés de correction générique, conséquences logiques d'un ensemble d'obligations de preuve sur les constituants principaux du réseau (topologie, routage, technique de commutation,...). La preuve de correction pour une instance spécifique de réseau sur puce est alors réduite à la vérification de ces obligations de preuve. Cette thèse poursuit les travaux entrepris dans ce domaine en étendant ce méta-modèle dans plusieurs directions : prise en compte plus fine de la modélisation temporelle, du contrôle de flux, des mécanismes de priorités,... Les résultats sont démontrés sur plusieurs réseaux actuels : Hermes (Université fédérale du Rio Grande do Sul, Brésil et LIRMM) et Nostrum (Royal Institute Of Technology, Suéde).

Cette thèse présente une formalisation des nombres algébriques et de leur théorie. Elle apporte deux nouvelles contributions importantes à la formalisation de résultats mathématiques dans des assistants à la preuve, ici Coq : la construction intuitionniste des nombres algébriques réels et la preuve qu'ils constituent un corps réel clos, ainsi que la programmation et la certification de procédures d'élimination des quantificateurs pour les théories des corps algébriquement clos et des corps réels clos. Pour atteindre ces résultats, nous avons apporté des contributions aux outils et aux méthodologies de preuves et de formalisation des mathématiques en Coq. En particulier, nous fournissons pour Coq/SSReflect un cadre pour travailler avec des types quotients. Nous fournissons une bibliothèque complète sur les structures algébriques de nombres ordonnés et normés. Nous avons réalisé une courte implémentation des réels de Cauchy accompagnée de tactiques pour effectuer facilement des raisonnements comportant des affirmations de la forme "soit n un entier suffisamment grand", couramment utilisés dans les preuves mathématiques sur papier. Nous avons également développé une petite bibliothèque d'analyse de base sur les polynômes à coefficients dans un corps réel clos. Une grande partie de nos résultats s'intègrent dans la formalisation de la preuve du théorème de Feit-Thompson et ont aussi pour objectif d'aider à certifier des procédures plus efficace d'élimination des quantificateurs sur les réels.