L'objectif de cette dissertation est de développer une approche originale de validation de circuits digitaux complexes décrits dans le langage VHDL. Nous proposons de générer automatiquement, à partir d'une description VHDL comportemental au niveau algorithmique, les vecteurs de test à appliquer sur une description de niveau RTL. Nous présentons d'abord la validation de descriptions VHDL au niveau algorithmique dans le contexte général du processus de conception de circuits complexes. Ce type de description étant similaire à un programme, nous explorons les techniques utilisées dans le domaine du test de logiciels, notamment celles basées sur un critère de couverture. Nous présentons le critère du test structuré, qui est fondé sur l'utilisation du graphe de flot de contrôle du programme sous test, et de la complexité cyclomatique de McCabe comme index du nombre de chemins à tester. Nous présentons également l'algorithme de Poole qui permet de générer cet ensemble de chemins. Cependant, le langage VHDL possède des caractéristiques que l'on ne retrouve pas dans les langages de programmation traditionnels (notion de temps, interconnexion de « process » s'exécutant en parallèle, mécanisme de « retard delta »). Nous proposons donc une modélisation adéquate sous forme de graphes, permettant d'appliquer les techniques précédentes à des descriptions VHDL restreintes à un sous-ensemble prenant en compte un style de description algorithmique : un graphe de flot de contrôle, un graphe de modélisation de « process », un graphe de dépendance. Nous exposons ensuite une méthodologie pour la génération de vecteurs de test à partir des chemins générés depuis ces graphes : application de l'algorithme de Poole sur la base de la complexité cyclomatique, analyse et modification éventuelle des chemins, génération et résolution des contraintes, extraction des vecteurs de test. L'approche est finalement illustrée par la réalisation du prototype logiciel GENESI qui nous a permis d'obtenir des résultats sur les « benchmarks ITC'99 ».

Cette thèse présente l'étude de l'implantation d'un système Prolog parallèle sur une architecture sans mémoire commune dans le cadre du projet PLoSys (Parallel Logic System). L'exécution exploite le parallélisme de manière implicite. Le système repose sur un modèle OU multiséquentiel. Le partage de l'état d'exécution est assuré par copie des données. Le langage Prolog supporté est complet, et intègre les effets de bord classiques du langage. La gestion parallèle fait l'objet d'une étude complète pour préserver la compatibilité avec l'exécution séquentielle du langage Prolog. En particulier, une méthode originale est présentée pour la gestion parallèle des effets de bord. Enfin, ce document présente la réalisation d'un prototype portable, ainsi que l'analyse des résultats obtenus

Ce travail a pour thème l'extraction de connaissances à partir de données provenant de plusieurs sources reflétant un même phénomène. L'objectif visé est l'amélioration de la qualité des systèmes de surveillance. Lorsque les données sont redondantes, l'utilisation de plusieurs sources permet de pallier aux problèmes de perte de signal et de bruit. Lorsque les données sont complémentaires, l'utilisation conjointe des différentes sources permet d'augmenter les performances en détection de ces systèmes. Nous appliquons nos travaux au domaine du diagnostic d'arythmies cardiaques. Nous utilisons une technique d'apprentissage artificiel relationnel (la programmation logique inductive) pour apprendre des règles discriminantes permettant de caractériser les arythmies à partir de plusieurs voies d'un électrocardiogramme et de mesures de pression artérielle. Pour exploiter la redondance des sources, nous apprenons dans un premier temps, des règles à partir des données des différentes sources prises séparément. Pour exploiter la complémentarité des sources, un apprentissage multisource naïf consisterait à apprendre globalement sur l'ensemble des données et avec un langage d'expression des concepts permettant de couvrir toute la richesse des données représentées. En alternative à un tel type d'apprentissage, nous proposons une méthode plus efficace qui s'appuie sur des apprentissages monosources, ie. effectués sur chacune des sources séparément, pour biaiser l'espace de recherche multisource. Le fait de s'appuyer sur les règles monosources permet de restreindre le langage des hypothèses ainsi que le nombre de relations possibles entre les objets représentés sur les différentes sources. Ce travail a été effectué dans le cadre du projet RNTS (Réseau National des Technologies et de la Santé) Cepica. Les résultats montrent que les règles apprises par apprentissage multisource sont au moins aussi bonnes que les règles monosources dans le cas où les données sont redondantes et meilleures dans les cas où les sources sont complémentaires. La technique d'apprentissage biaisé permet en outre d'apprendre des règles de manière beaucoup plus efficace que dans le cas naïf en bénéficiant d'un biais de langage généré automatiquement. Ces nouvelles règles sont incorporées au système Calicot pour la surveillance de patients souffrant de troubles du rythme cardiaque.<br />~

Le terme agent a été introduit pour masquer l'origine diverse des participants (produits logiciels ou humains) intervenant dans une interaction. Un agent est considéré comme une boîte noire capable de contrôler son comportement. Cette propriété, appelée autonomie, est en contradiction avec la possibilité de contrôler l'agent depuis l'extérieur. Dans cette thèse, nous proposons la norme sociale comme une solution de compromis à ce conflit. Une norme a le double rôle d'informer quel est le comportement désirable et d'influencer les agents pour qu'ils l'adoptent. Cette thèse comprend deux parties, la première introduit les concepts, la seconde propose les outils. La première partie est centrée autour du paradigme de la conception sociale des Systèmes Multi-Agents (SMA). Nous montrons comment les notions de dépendance sociale, d'organisation et de rôle permettent de mieux décrire l'interaction entre agents. La notion de norme est définie dans ses diférentes acceptions : domaine juridique, sécurité informatique, systèmes distribués, et SMA. Ensuite, nous présentons nos choix et nos solutions concernant l'interaction normative. Les structures architecturales qui en résultent sont appelées Système d'Agents Normatifs (SAN). Nous montrons quels en sont les acteurs majeurs et quels sont les outils pour les construire. La description des normes utilise les concepts d'action, de temps, d'obligation et d'agence. La deuxième partie montre comment ces concepts sont formalisés dans la littérature (p. ex. logique temporelle, déontique, de l'action) et présente leurs inconvénients majeurs. Ensuite, nous proposons un modèle temporel pour décrire l'interaction normative en expliquant les choix des éléments utilisés et nous montrons son applicabilité. Le modèle est utilisé pour produire les outils nécessaires à la construction des SAN : le monitoring des comportements des agents, la détection des violations, l'ordonnancement déontique, la communication normative.

De nombreuses applications du traitement automatique des langues (recherche d'information, traduction automatique, etc.) requièrent des ressources sémantiques spécifiques à leur tâche et à leur domaine. Pour répondre à ces besoins spécifiques, nous avons développé ASARES, un système d'acquisition d'informations sémantiques lexicales sur corpus. Celui-ci répond à un triple objectif : il permet de fournir des résultats de bonne qualité, ses résultats et le processus ayant conduit à leur extraction sont interprétables, et enfin, il est assez générique et automatique pour être aisément portable d'un corpus à un autre. Pour ce faire, ASARES s'appuie sur une technique d'apprentissage artificiel symbolique --- la programmation logique inductive --- qui lui permet d'inférer des patrons d'extraction morphosyntaxiques et sémantiques à partir d'exemples des éléments lexicaux sémantiques que l'on souhaite acquérir. Ces patrons sont ensuite utilisés pour extraire du corpus de nouveaux éléments. Nous montrons également qu'il est possible de combiner cette approche symbolique avec des techniques d'acquisition statistiques qui confèrent une plus grande automaticité à ASARES. Pour évaluer la validité de notre méthode, nous l'avons appliquée à l'extraction d'un type de relations sémantiques entre noms et verbes définies au sein du Lexique génératif appelées relations qualia. Cette tâche d'acquisition revêt deux intérêts principaux. D'une part, ces relations ne sont définies que de manière théorique ; l'interprétabilité linguistique des patrons inférés permet donc d'en préciser le fonctionnement et les réalisations en contexte. D'autre part, plusieurs auteurs ont noté l'intérêt de ce type de relations dans le domaine de la recherche d'information pour donner accès à des reformulations sémantiquement équivalentes d'une même idée. Grâce à une expérience d'extension de requêtes, nous vérifions expérimentalement cette affirmation : nous montrons que les résultats d'un système de recherche exploitant ces relations qualia, acquises par ASARES, sont améliorés de manière significative quoique localisée.

Durant cette thèse, nous avons travaillé sur l'adaptation des algorithmes d'inférence grammaticale pour la recherche des propriétés communes à un ensemble de protéines. L'inférence grammaticale positive cherche à générer, à partir d'un ensemble de mots appartenant à un langage cible particulier inconnu, une représentation grammaticale qui est "optimale" par rapport à ce langage, c'est-à-dire qui rassemble et organise les particularités des mots du langage. Nous avons utilisé le diagramme de Taylor, qui classe les acides aminés suivant leurs propriétés physico-chimiques, pour construire, sous forme de treillis, un ordre sur les groupes d'acides aminés. Nous avons aussi développé une méthode d'inférence (SDTM) qui calcule les meilleurs alignements locaux entre les paires de protéines suivant un score fondé à la fois sur cet ordre et sur les propriétés statistiques de l'ensemble de protéines donné. Le résultat est une machine séquentielle proche de celle de Mealy avec des sorties réduites à "accepte" et "rejette". L'algorithme commence par construire le plus grand automate reconnaissant exactement les mots du langage et le généralise par fusions successives des paires de transitions correspondant aux acides aminés appariés dans les alignements sélectionnés. Les expérimentations ont montré l'intérêt de cette combinaison de méthodes importées de la découverte de motifs et de l'inférence grammaticale.

Déterminer la structure 3D des protéines expérimentalement est une tâche très lourde et coûteuse, qui peut s'avérer parfois impossible à réaliser. L'arrivée massive de données provenant des programmes de séquençage à grande échelle impose de passer d'une approche biochimique à une approche bioinformatique, et nécessite en particulier de développer des méthodes de prédiction sur des séquences.<br />Cette thèse propose l'exploration de deux nouvelles pistes pour progresser dans la résolution de prédiction de ponts disulfures dans les protéines. Cette liaison covalente stabilise et contraint fortement la conformation spatiale de la protéine et la connaissance des positions où elle intervient peut réduire considérablement la complexité du problème de la prédiction de la structure 3D. Pour cela, nous utilisons dans un premier temps, l'inférence grammaticale et plus particulièrement les langages de contrôle introduit par Y. Takada, puis dans un deuxième temps, la programmation logique inductive.<br />Diverses expériences visent à confronter un cadre théorique d'apprentissage et des algorithmes généraux d'inférence grammaticale régulière à une application pratique de prédiction d'appariements spécifiques au sein d'une séquence protéique. D'autres expérimentations montrent que la programmation logique inductive donne de bons résultats sur la prédiction de l'état oxydé des cystéines en inférant des règles interprétables par les biologistes. Nous proposons un algorithme d'induction heuristique dont l'idée est d'effectuer plusieurs phases d'apprentissage en tenant compte des résultats obtenus aux phases précédentes permettant ainsi de diminuer considérablement la combinatoire dans les espaces d'hypothèses logiques en construisant des règles de plus en plus discriminantes.

Une demande croissante d'outils pour construire et décrypter des réseaux génétiques contrôlant des processus cellulaires est ressentie en biologie. Nous soutenons que l'utilisation de l'approche déclarative est pertinente et applicable pour répondre aux questions des biologistes sur ces réseaux, en général partiellement connus. L'idée principale est de modéliser des connaissances portant à la fois sur la structure et la dynamique d'un réseau par un ensemble de contraintes représentant l'ensemble des solutions, de vérifier sa cohérence, de réparer une incohérence éventuelle par un relâchement automatique, et d'inférer des propriétés sur la structure et la dynamique du réseau. Pour montrer la faisabilité de l'approche, nous formalisons les réseaux discrets de R. Thomas et les propriétés biologiques pertinentes, proposons un outil reposant sur la programmation logique par contraintes en coopération avec un solveur SAT, et la validons sur des applications biologiques significatives.

Ce travail de thèse, effectué dans la cadre du projet FUI Minalogic Bluesky, porte sur le test fonctionnel automatisé d'une classe particulière de contrôleurs logiques programmables (em4) produite par InnoVista Sensors. Ce sont des systèmes synchrones qui sont programmés au moyen d'un environnement de développement intégré (IDE). Les personnes qui utilisent et programment ces contrôleurs ne sont pas nécessairement des programmeurs experts. Le développement des applications logicielles doit être par conséquent simple et intuitif. Cela devrait également être le cas pour les tests. Même si les applications définies par ces utilisateurs ne sont pas nécessairement très critiques, il est important de les tester d'une manière adéquate et efficace. Un simulateur inclu dans l'IDE permet aux programmeurs de tester leurs programmes d'une façon qui reste à ce jour informelle et interactive en entrant manuellement des données de test. En se basant sur des recherches précédentes dans le domaine du test des programmes synchrones, nous proposons un nouveau langage de spécification de test, appelé SPTL (Synchronous Programs Testing Language) qui rend possible d'exprimer simplement des scénarios de test qui peuvent être exécutées à la volée pour générer automatiquement des séquences d'entrée de test. Il permet aussi de décrire l'environnement où évolue le système pour mettre des conditions sur les entrées afin d'arriver à des données de test réalistes et de limiter celles qui sont inutiles. SPTL facilite cette tâche de test en introduisant des notions comme les profils d'utilisation, les groupes et les catégories. Nous avons conçu et développé un prototype, nommé "Testium", qui traduit un programme SPTL en un ensemble de contraintes exploitées par un solveur Prolog qui choisit aléatoirement les entrées de test. La génération de données de test s'appuie ainsi sur des techniques de programmation logique par contraintes. Pour l'évaluer, nous avons expérimenté cette méthode sur des exemples d'applications EM4 typiques et réels. Bien que SPTL ait été évalué sur em4, son utilisation peut être envisagée pour la validation d'autres types de contrôleurs ou systèmes synchrones. / This thesis work done in the context of the FUI project Minalogic Bluesky, concerns the automated functional testing of a particular class of programmable logic controllers (em4) produced by InnoVista Sensors. These are synchronous systems that are programmed by means of an integrated development environment (IDE). People who use and program these controllers are not necessarily expert programmers. The development of software applications should be as result simple and intuitive. This should also be the case for testing. Although applications defined by these users need not be very critical, it is important to test them adequately and effectively. A simulator included in the IDE allows programmers to test their programs in a way that remains informal and interactive by manually entering test data.Based on previous research in the area of synchronous test programs, we propose a new test specification language, called SPTL (Synchronous Testing Programs Language) which makes possible to simply express test scenarios that can be executed on the fly to automatically generate test input sequences. It also allows describing the environment in which the system evolves to put conditions on inputs to arrive to realistic test data and limit unnecessary ones. SPTL facilitates this testing task by introducing concepts such as user profiles, groups and categories. We have designed and developed a prototype named "Testium", which translates a SPTL program to a set of constraints used by a Prolog solver that randomly selects the test inputs. So, generating test data is based on constraint logic programming techniques.To assess this, we experimented this method on realistic and typical examples of em4 applications. Although SPTL was evaluated on EM4, its use can be envisaged for the validation of other types of synchronous controllers or systems.

On étudie dans cette thèse une structure de semi-anneau dont le produit est basé sur la règle de résolution de la programmation logique. Cet objet mathématique a été initialement introduit dans le but de modéliser la procédure d'élimination des coupures de la logique linéaire, dans le cadre du programme de géométrie de l'interaction. Il fournit un cadre algébrique et abstrait, tout en étant présenté sous une forme syntaxique et concrète, dans lequel mener une étude théorique du calcul. On reviendra dans un premier temps sur l'interprétation interactive de la théorie de la démonstration dans ce semi-anneau, via l'axiomatisation catégorique de l'approche de la géométrie de l'interaction. Cette interprétation établit une traduction des programmes fonctionnels vers une forme très simple de programmes logiques. Dans un deuxième temps, on abordera des problématiques de théorie de la complexité: bien que le problème de la nilpotence dans le semi-anneau étudié soit indécidable en général, on fera apparaître des restrictions qui permettent de caractériser le calcul en espace logarithmique (déterministe et non-déterministe) et en temps polynomial (déterministe). / We study in this thesis a semiring structure with a product based on the resolution rule of logic programming. This mathematical object was introduced initially in the setting of the geometry of interaction program in order to model the cut-elimination procedure of linear logic. It provides us with an algebraic and abstract setting, while being presented in a syntactic and concrete way, in which a theoretical study of computation can be carried on. We will review first the interactive interpretation of proof theory within this semiring via the categorical axiomatization of the geometry of interaction approach. This interpretation establishes a way to translate functional programs into a very simple form of logic programs. Secondly, complexity theory problematics will be considered: while the nilpotency problem in the semiring we study is undecidable in general, it will appear that certain restrictions allow for characterizations of (deterministic and non-deterministic) logarithmic space and (deterministic) polynomial time computation.