Dans le cadre de la télécommunication, les entreprises développent des protocoles gérant le transfert de données entre machines. Ces protocoles fonctionnent sur le principe d'envoi de messages entre deux parties par l'intermédiaire de canaux non fiables. Pour s'assurer que tous les messages ont bien été reçus, les techniques employées consistent à réémettre les messages perdus et/ou à attendre un laps de temps déterminé avant de conclure à l'échec de la transmission. De plus, les systèmes sont souvent modélisés en fonction de paramètres. Nous avons travaillé sur un modèle mathématique permettant la vérification de spécifications (comportements attendus des systèmes) pour des protocoles manipulant à la fois des compteurs, des files d'attente ou des horloges, ainsi que des paramètres. Le but de l'analyse est de calculer l'ensemble des comportements possibles du système puis de vérifier qu'aucun d'eux ne viole une spécification attendue. Le problème ici est que cet ensemble est infini. En effet, un comportement est fonction des valeurs prises par les variables du système au cours de l'exécution et certaines sont définies sur un domaine infini. Il faut alors pouvoir représenter ces comportements de façon finie et aussi trouver des méthodes pour calculer en un temps fini un ensemble infini. Plus formellement, nous nous sommes placés dans le cadre de l'analyse automatique des systèmes (model-checking). La représentation choisie pour les modèles à compteurs et horloges paramétrés est une extension des matrices de bornes pour laquelle nous avons une méthode exacte d'accélération (calcul en un temps fini d'ensembles de comportements infinis). Du côté pratique, nous avons implanté ces méthodes dans un outil TReX qui est, à notre connaissance, le seul pouvant manipuler de manière exacte des compteurs, des horloges et des files d'attente. Nous avons pu vérifier des exemples conséquents tels que le protocole de retransmission bornée.

L'importance des systèmes temps-réels embarqués dans les sociétés industrialisées modernes en font un terrain d'application privilégié pour les méthodes formelles. La prépondérance des contraintes temporelles dans les spécifications de ces systèmes motive la mise au point de solutions spécifiques. Cette thèse s'intéresse à une classe de systèmes temps-réels incluant ceux développés avec la chaîne d'outils OASIS, développée au CEA LIST. Nos travaux portent sur la notion de délai de bout-en-bout, que nous proposons de modéliser comme une contrainte temporelle concernant l'influence du flot d'informations des entrées sur celui des sorties. Afin de répondre à la complexité croissante des systèmes temps-réels, nous étudions l'applicabilité de cette notion nouvelle au développement incrémental par raffinement et par composition. Le raffinement est abordé sous l'angle de la conservation de propriétés garantes de la correction du système au cours du processus de développement. Nous délimitons les conditions nécessaires et suffisantes à la conservation du délai de bout-en-bout lors d'un tel processus. De même, nous donnons des conditions suffisantes pour permettre le calcul du délai de bout-en-bout de manière compositionnelle. Combinés, ces résultats permettent d'établir un formalisme permettant la preuve du délai de bout-en-bout lors d'une démarche de développement incrémentale.

Nous proposons une méthodologie de conception pour les systèmes de commande tolérants aux fautes en partant d'un modèle de base exhaustif pour le système complexe à superviser. En pratique, la modélisation exhaustive est réalisée grâce à un automate hybride enrichi par des paramètres quantifiant les défaillances possibles. Ceci permet de modéliser les défaillances partielles. Dans la phase hors ligne, ce système complexe est transformé en un système discret abstrait et exploitable selon des techniques dédiées. Un superviseur est alors construit selon les objectifs de fonctionnement.Lors du fonctionnement du système, l'occurrence d'une défaillance se traduit par l'invalidation de plusieurs comportements dans le modèle abstrait et l'introduction d'incertitudes. Par la suite, les modules de diagnostic et d'identification (qui ne rentrent pas dans l'objet de notre thèse) réduisent de façon progressive le modèle hybride au cours du temps. Afin de pouvoir mettre à jour le modèle discret abstrait, on a développé des algorithmes de calcul d'atteignabilité, de vérification et de génération de régions stabilisées.Pour pouvoir superviser un tel système, l'utilisation de méthodologies d'abstraction est nécessaire afin de transformer le modèle bas niveau exhaustif en un modèle discret approprié. Nous réalisons cette abstraction en proposant des algorithmes qui tiennent compte du contexte d'utilisation (objectifs, contraintes...). Lorsqu'une défaillance est détectée, la reconfiguration est déclenchée en essayant, au fur et à mesure de l'enrichissement du modèle abstrait, de réduire le fonctionnement du système défaillant dans un des schémas prédéfinis

L'ensemble des travaux présentés relève de l'Apprentissage Artificiel, et aborde l'apprentissage supervisé, ainsi que l'aide à la découverte par la fouille de données. On se place ici dans le cas où un problème d'apprentissage passe par l'exploration d'un "Espace de Recherche", constitué de représentations formées dans un certain langage d'énoncés. La structure cachée liant "énoncés" et sous-ensembles d'"objets", représentable dans un treillis intension/extension, permet en particulier de réduire l'espace de recherche dans les problèmes d'apprentissage supervisé. Je présente ensuite une forme d'"abstraction" ordonnée faisant varier le niveau de granularité des énoncés, ou des objets considérés, et garantissant que le treillis intension/extension est ainsi lui-même réduit. Certains travaux concernant la recherche de motifs séquentiels réquents, sont également interprétés du point de vue de cette relation intension/extension. Enfin, deux "paradigmes" nouveaux en apprentissage supervisé sont présentés, l'un traitant de la notion d'ambiguïté des exemples, l'autre étendant l'apprentissage supervisé cohérent dans un cadre collectif.

<p>Quite often modelers with constraint programming (CP) use the same modelling patterns for different problems, possibly from different domains. This results in recurring idioms in constraint programs. Our approach can be seen as a three-step approach. First, we identify some of these recurring patterns in constraint programs. Second, we propose a general way of describing these patterns by introducing proper constructs that would cover a wide range of applications. Third, we propose automating the process of reproducing these idioms from these higher-level descriptions. The whole process can be seen as a way of encapsulating some of the expertise and knowledge often used by CP modelers and making it available in much simpler forms. Doing so, we are able to extend current CP languages with high-level abstractions that open doors for automation of some of the modelling processes.</p><p>In particular, we introduce function variables and allow the statement of constraints on these variables using function operations. A <i>function variable</i> is a decision variable that can take a value from a set of functions as opposed to an <i>integer variable</i> that ranges over integers, or a <i>set variable</i> that ranges over a set of sets. We show that a function variable can be mapped into different representations in terms of integer and set variables, and illustrate how to map constraints stated on a function variable into constraints on integer and set variables. As a result, a function model expressed using function variables opens doors to the automatic generation of alternate CP models. These alternate models either use a different variable representation, or have extra implied constraints, or employ different constraint formulation, or combine different models that are linked using channelling constraints. A number of heuristics are also developed that allow the comparison of different constraint formulations. Furthermore, we present an extensive theoretical comparison of models of injection problems supported by asymptotic and empirical studies. Finally, a practical modelling tool that is built based on a high-level language that allows function variables is presented and evaluated. The tool helps users explore different alternate CP models starting from a function model that is easier to develop, understand, and maintain.</p>

<p>De nos jours, il est peu de processus ou de tâches qui ne requièrent pas l'optimisation d'une quantité : diminuer le temps de livraison, diminuer l'espace utilisé, réduire les efforts de développement, ... C'est donc sans surprise que la recherche en optimisation soit l'un des domaines les plus actifs des sciences des technologies de l'information. En optimisation combinatoire, les métaheuristiques sont à compter parmi le fleuron des techniques algorithmiques. Mais ce succès est encore au prix d'une quantité significative de temps de conception et développement. Ne serait-il pas possible d'aller encore plus loin ? D'automatiser la préparation des métaheuristiques ? En particulier dans des conditions telles le manque de temps, l'ignorance de techniques spécialisées ou encore la mauvaise compréhension du problème traité ? C'est ce à quoi nous répondons dans la présente thèse au moyen d'une approche de méta-modélisation de la recherche : l'heuristique de la Gestalt.</p> <p>Considérant la représentation du problème comme un levier que l'on peut activer sous le processus de recherche mené par une métaheuristique, la thèse suggère la construction d'une abstraction de cette représentation capable d'assister la métaheuristique à trouver de bonnes solutions en contraignant sa recherche. Cette approche, inspirée de la psychologie de la Gestalt, nous l'appelons l'heuristique de la Gestalt. Son fonctionnement repose principalement sur l'agrégation des variables de la représentation. Cette agrégation donne lieu à une abstraction structurelle, mais également fonctionnelle en ce sens que les opérateurs de la métaheuristique doivent désormais respecter l'intégrité des agrégats définis.</p> <p>Après avoir établi le contexte de la dissertation, nous discutons de la transposition de la psychologie de la Gestalt dans le cadre de l'optimisation combinatoire et des métaheuristiques. S'ensuit la formalisation de l'heuristique de la Gestalt et la description de sa réalisation. Finalement, une série d'études expérimentales sont menées pour éprouver le concept avancé et valider l'implémentation basée sur les algorithmes évolutionnistes que nous proposons. En conclusion, nous affirmons que l'implémentation de l'heuristique de la Gestalt basée, entre autres, sur un algorithme génétique de groupement est capable d'assister positivement des algorithmes génétiques lorsque les instances de problèmes traitées possèdent une structure riche et complexe, que leur taille est importante, que l'on est tôt dans le processus d'optimisation et que l'algorithme génétique n'est pas paramétré spécifiquement.</p>

Cette thèse décrit une nouvelle approche pour la méta-programmation sûre. Un méta-programme est un programme qui manipule des programmes ou assimilés. Les compilateurs et systèmes de preuves sont de bons exemples de méta-programmes qui bénéficieraient de cette approche. Dans ce but, ce travail se concentre sur la représentation des noms et des lieurs dans les structures de données. Les erreurs de programmation étant courantes avec les techniques usuelles, nous proposons une interface abstraite pour les noms et les lieurs qui élimine ces erreurs. Cette interface est implémentée sous forme d'une bibliothèque en Agda. Elle permet de définir et manipuler des représentations de termes dans le style nominal. Grâce à l'abstraction, d'autres styles sont aussi disponibles : le style de De Bruijn, les combinaisons de ces styles, et d'autres encore. Nous indiçons les noms et les termes par des mondes. Les mondes sont en même temps précis et abstraits. Via les relations logiques et la paramétricité, nous pouvons démontrer dans quel sens notre bibliothèque est sûre, et obtenir des "théorèmes gratuits" à propos des fonctions monde-polymorphiques. Ainsi une fonction monde-polymorphique de transformation de termes doit commuter avec n'importe quel renommage des variables libres. La preuve est entièrement conduite en Agda. Notre technique se montre utile sur plusieurs exemples, dont la normalisation par évaluation qui est connue pour être un défi. Nous montrons que notre approche indicée par des mondes permet d'exprimer un large panel de type de données grâce a des langages de définition embarqués.

Quite often modelers with constraint programming (CP) use the same modelling patterns for different problems, possibly from different domains. This results in recurring idioms in constraint programs. Our approach can be seen as a three-step approach. First, we identify some of these recurring patterns in constraint programs. Second, we propose a general way of describing these patterns by introducing proper constructs that would cover a wide range of applications. Third, we propose automating the process of reproducing these idioms from these higher-level descriptions. The whole process can be seen as a way of encapsulating some of the expertise and knowledge often used by CP modelers and making it available in much simpler forms. Doing so, we are able to extend current CP languages with high-level abstractions that open doors for automation of some of the modelling processes. In particular, we introduce function variables and allow the statement of constraints on these variables using function operations. A function variable is a decision variable that can take a value from a set of functions as opposed to an integer variable that ranges over integers, or a set variable that ranges over a set of sets. We show that a function variable can be mapped into different representations in terms of integer and set variables, and illustrate how to map constraints stated on a function variable into constraints on integer and set variables. As a result, a function model expressed using function variables opens doors to the automatic generation of alternate CP models. These alternate models either use a different variable representation, or have extra implied constraints, or employ different constraint formulation, or combine different models that are linked using channelling constraints. A number of heuristics are also developed that allow the comparison of different constraint formulations. Furthermore, we present an extensive theoretical comparison of models of injection problems supported by asymptotic and empirical studies. Finally, a practical modelling tool that is built based on a high-level language that allows function variables is presented and evaluated. The tool helps users explore different alternate CP models starting from a function model that is easier to develop, understand, and maintain.

Fault isolation is the process of reasoning required to find the cause of a system failure. In a model-based approach, the available information is a model of the system and some observations. Using knowledge of how the system generally behaves, as given in the system model, together with partial observations of the events of the current situation the task is to deduce the failure causing event(s). In our setting, the observable events manifest themselves in a message log. We study post mortem fault isolation for moderately concurrent discrete event systems where the temporal order of logged messages contains little information. To carry out fault isolation one has to study the correlation between observed events and fault events of the system. In general, such study calls for exploration of the state space of the system, which is exponential in the number of system components. Since we are studying a restricted class of all possible systems we may apply aggressive specialized abstraction policies in order to allow fault isolation without ever considering the often intractably large state space of the system. In this thesis we describe a mathematical framework as well as a prototype implementation and an experimental evaluation of such abstraction techniques. The method is efficient enough to allow for not only post mortem fault isolation but also design time diagnosability analysis of the system, which can be seen as a non-trivial way of analyzing all possible observations of the system versus the corresponding fault isolation outcome. This work has been supported by VINNOVA’s Competence Center ISIS.

Judgments that demand consideration of pieces of information in the environment occur repeatedly throughout our lives. One professional example is that of a physician that considers multiple symptoms to make a judgment about a patient’s disease. The scientific study of such, so called, multiple-cue judgments that involve multiple pieces of information (cues: e.g., symptoms) and continuous criterion (e.g., blood pressure) has been concerned with the statistical modelling of judgment data (see Brehmer, 1994; Cooksey, 1996; Hammond &amp; Stewart, 2001). In this thesis behavioural experiments, cognitive modelling and brain imaging is used to investigate an adaptive division of labor between multiple memory representations in multiple-cue judgment. It is hypothesized that the additive, independent linear effect of each cue can be explicitly abstracted and integrated by a serial, additive judgment process (Einhorn, Kleinmuntz, &amp; Kleinmuntz, 1979). It is further hypothesized that a variety of sophisticated task properties, like non-additive cue combination, nonlinear relations, and inter-cue correlation, are carried implicitly by exemplar-memory (Medin &amp; Schaffer, 1978; Nosofsky, 1984; Nosofsky &amp; Johansen, 2000). Study I and II investigates the effect of additive versus non-additive cue-combination and verify the predicted shift in cognitive representations as a function of the underlying cue-combination rule. The third study is a review that discusses the nature of these representational shifts; are they contingent upon early perceived learning performance instead of automatic and error-driven? Study IV verifies that this shift is evident also in the neural activity associated with making judgments in additive and non-additive tasks.