Cette thèse traite du problème du calcul des implications, c'est-à-dire des régularités de la forme "quand il y a A, il y a B", dans des ensembles de données composés d'objets décrits par des attributs. Calculer toutes les implications peut être vu comme l'énumération d'ensembles d'attributs appelés pseudo-intensions. Nous savons que ces pseudo-intensions ne peuvent pas être énumérées avec un délai polynomial dans l'ordre lectique mais aucun résultat n'existe, à l'heure actuelle, pour d'autres ordres. Bien que certains algorithmes existants n'énumèrent pas forcément dans l'ordre lectique, aucun n'a un délai polynomial. Cette absence de connaissances sur les autres ordres autorise toujours l'existence d'un algorithme avec délai polynomial et le trouver serait une avancée utile et significative. Malheureusement, les algorithmes actuels ne nous autorisent pas à choisir l'ordre d'énumération, ce qui complique considérablement et inutilement l'étude de l'influence de l'ordre dans la complexité. C'est donc pour aller vers une meilleure compréhension du rôle de l'ordre dans l'énumération des pseudo-intensions que nous proposons un algorithme qui peut réaliser cette énumération dans n'importe quel ordre qui respecte la relation d'inclusion. Dans la première partie, nous expliquons et étudions les propriétés de notre algorithme. Comme pour tout algorithme d'énumération, le principal problème est de construire tous les ensembles une seule fois. Nous proposons pour cela d'utiliser un arbre couvrant, lui-même basé sur l'ordre lectique, afin d'éviter de multiples constructions d'un même ensemble. L'utilisation de cet arbre couvrant au lieu de l'ordre lectique classique augmente la complexité spatiale mais offre plus de flexibilité dans l'ordre d'énumération. Nous montrons que, comparé à l'algorithme Next Closure bien connu, le nôtre effectue moins de fermetures logiques sur des contextes peu denses et plus de fermetures quand le nombre moyen d'attributs par objet dépasse 30% du total. La complexité spatiale de l'algorithme est aussi étudiée de façon empirique et il est montré que des ordres différents se comportent différemment, l'ordre lectique étant le plus efficace. Nous postulons que l'efficacité d'un ordre est fonction de sa distance à l'ordre utilisé dans le test de canonicité. Dans la seconde partie, nous nous intéressons au calcul des implications dans un cadre plus complexe : les données relationnelles. Dans ces contextes, les objets sont représentés à la fois par des attributs et par des relations avec d'autres objets. Le besoin de représenter les informations sur les relations produit une augmente exponentielle du nombre d'attributs, ce qui rend les algorithmes classiques rapidement inutilisables. Nous proposons une modification de notre algorithme qui énumère les pseudo-intensions de contextes dans lesquels l'information relationnelle est représentée par des attributs. Nous fournissons une étude rapide du type d'information relationnelle qui peut être prise en compte. Nous utilisons l'exemple des logiques de description comme cadre pour l'expression des données relationnelles. Dans la troisième partie, nous étendons notre travail au domaine plus général des règles d'association. Les règles d'association sont des régularités de la forme ``quand il y a A, il y a B avec une certitude de x%''. Ainsi, les implications sont des règles d'association certaines. Notre algorithme calcule déjà une base pour les implications et nous proposons une très simple modification et montrons qu'elle lui permet de calculer la base de Luxenburger en plus de la base de Duquenne-Guigues. Cela permet à notre algorithme de calculer une base de cardinalité minimale pour les règles d'association. / This thesis deals with the problem of the computation of implications, which are regularities of the form "when there is A there is B", in datasets composed of objects described by attributes. Computing all the implications can be viewed as the enumeration of sets of attributes called pseudo-intents. It is known that pseudointents cannot be enumerated with a polynomial delay in the lectic order but no such result exists for other orders. While some current algorithms do not enumerate in the lectic order, none of them have a polynomial delay. The lack of knowledge on other orders leaves the possibility for a polynomial-delay algorithm to exist and inding it would be an important and useful step. Unfortunately, current algorithms do not allow us to choose the order so studying its inuence on the complexity of the enumeration is harder than necessary. We thus take a first step towards a better understanding of the role of the order in the enumeration of pseudo-intents by providing an algorithm that can enumerate pseudo-intents in any order that respects the inclusion relation.In the first part, we explain and study the properties of our algorithm. As with all enumeration algorithms, the first problem is to construct all the sets only once.We propose to use a spanning tree, itself based on the lectic order, to avoid multiple constructions of a same set. The use of this spanning tree instead of the classic lectic order increases the space complexity but others much more exibility in the enumeration order. We show that, compared to the well-known Next Closure algorithm, ours performs less logical closures on sparse contexts and more once the average number of attributes per object exceeds 30%. The space complexity of the algorithm is also empirically studied and we show that different orders behave differently with the lectic order being the most efficient. We postulate that the efficiency of an order is function of its distance to the order used in the canonicity test. In the second part, we take an interest in the computation of implications in a more complex setting : relational data. In these contexts, objects are represented by both attributes and binary relations with other objects. The need to represent relation information causes an exponential increase in the number of attributes so naive algorithms become unusable extremely fast. We propose a modification of our algorithm that enumerates the pseudo-intents of contexts in which relational information is represented by attributes. A quick study of the type of relational information that can be considered is provided. We use the example of description logics as a framework for expressing relational data. In the third part, we extend our work to the more general domain of association rules. Association rules are regularities of the form \when there is A there is B with x% certainty" so implications are association rules with 100% certainty. Our algorithm already computes a basis for implications so we propose a very simple modification and demonstrate that it can compute the Luxenburger basis of a context along with the Duquenne-Guigues basis. This effectively allows our algorithm to compute a basis for association rules that is of minimal cardinality.

Cette thèse s'inscrit dans la continuation du travail de Younes Achkire, consacré au contrôle actif des ponts haubanés. Elle traite de l'implémentation d'un système de contrôle actif sur des maquettes de structures câblées. Deux types de structures sont étudiés expérimentalement: les ponts haubanés et les treillis spatiaux. Après une brève introduction sur l'usage du contrôle actif dans ces domaines, le chapitre 2 traite numériquement des mécanismes d'interaction entre le câble et la structure. Au chapitre 3, nous présentons la stratégie de contrôle que nous utilisons pour stabiliser une structure câblée: il s'agit d'un contrôle décentralisé, basé sur des paires capteur/actionneur colocalisées, placées au niveau des ancrages des câbles, chacune équipée d'un contrôleur Intégral Force Feedback. Nous présentons une théorie linéaire simplifiée permettant de dimensionner le système et de prévoir son efficacité. Elle est illustrée sur un exemple, et nous discutons de la validité de certaines hypothèses simplificatrices. Le chapitre 4 est consacré au contrôle actif des ponts haubanés. Nous y présentons 2 maquettes. La première, de petite taille (3m) représente un pylône de pont haubané en construction. Elle est équipée d'actionneurs piézoélectriques. La seconde, installée au Centre Commun de Recherche d'Ispra (Italie), mesure 30m de long, et est équipée d'actionneurs hydrauliques. Les expériences réalisées sur ces maquettes ont démontré l'efficacité du contrôle et la fiabilité de la théorie prédictive. Le contrôle du flottement des ponts est traité sur un exemple numérique. Le chapitre 5 relate nos expériences d'amortissement actif des treillis spatiaux. Deux structures ont été étudiées: une colonne en treillis équipée de 3 câbles actifs, et une structure triédrique suspendue à des cordons élastiques pour simuler l'absence de gravité, également munie de câbles actifs. Deux concepts d'actionneur piézoélectrique ont été testés. Nous avons ensuite examiné le problème de la saturation des actionneurs, et celui du contrôle actif des microvibrations (~10nm) d'une structure câblée. Le chapitre 6 conclut ce travail, en souligne les aspects originaux et donne quelques perspectives de développement.

.

Les systèmes informatiques jouent un rôle essentiel dans la vie actuelle, et leurs erreurs peuvent avoir des conséquences dramatiques. Il existe des méthodes formelles permettant d'assurer qu'un système informatique est fiable. La méthode formelle utilisée dans cette thèse est appelée complétion d'automates d'arbres et permet d'analyser les systèmes à nombre d'états infini. Dans cette représentation, les états du système sont représentés par des termes et les ensembles d'états par des automates d'arbres. L'ensemble des comportements possibles d'un système est calculé grâce à l'application successive d'un système de réécriture modélisant le comportement du système vérifié. On garantit la fiabilité d'un système en vérifiant qu'un comportement interdit n'est pas présent dans l'ensemble des états accessibles. Mais cet ensemble n'est pas toujours calculable, et nous devons alors calculer une sur-approximation calculable de cet ensemble. Mais cette approximation peut s'avérer trop grossière et reconnaître de faux contre-exemples. La première contribution de cette thèse consiste alors à caractériser, par des formules logiques et de manière automatique, ce qu'est une "bonne" sur-approximation : une approximation représentant un sur-ensemble des configurations accessibles, et qui soit suffisamment précise pour ne pas reconnaître de faux contre-exemples. Résoudre ces formules conduit alors automatiquement à une sur-approximation concluante si elle existe, sans avoir recours à aucun paramétrage manuel. Le second problème de la complétion d'automates d'arbres est le passage à l'échelle, autrement dit le temps de calcul parfois élevé du calcul de complétion quand on s'attaque à des problèmes de la vie courante. Dans la vérification de programmes Java utilisant la complétion d'automates d'arbres, cette explosion peut être due à l'utilisation d'entiers de Peano. L'idée de notre seconde contribution est alors d'évaluer directement le résultat d'une opération arithmétique. D'une façon plus générale, il s'agit d'intégrer les éléments d'un domaine infini dans un automate d'arbres. En s'inspirant de méthodes issues de l'interprétation abstraite, cette thèse intègre des treillis abstraits dans les automates d'arbres, constituant alors un nouveau type d'automates. Les opérations sur le domaine infini représenté sont calculées en une seule étape d'évaluation plutôt que d'appliquer de nombreuses règles de réécriture. Nous avons alors adapté la complétion d'automates d'arbres à ce nouveau type d'automate, et la généricité du nouvel algorithme permet de brancher de nombreux treillis abstraits. Cette technique a été implémentée dans un outil appelé TimbukLTA, et cette implémentation permet de démontrer l'efficacité de cette technique. / Computer systems are more and more important in everyday life, and errors into those systems can make dramatic damages. There are formal methods which can assure reliability of a system. The formal method used in this thesis is called tree automata completion and allows to analyze infinite state systems. In this representation, states of a system are represented by a term and sets of states by tree automata. The set of all reachable behaviors (or states) of the system is computed thanks to successive applications of a term rewriting system which represents the behavior of the system. The reliability of the system is assured by checking that no forbidden state is reachable by the system. But the set of reachable states is not always computable and we need to compute an over-approximation of it. This over-approximation is not always fine enough and can recognize counter examples. The first contribution of this thesis consist in characterizing by logical formulae, in an automatic way, what is a good approximation: an over-approximation which does not contain any counter example. Solving these formulae leads automatically to a good over-approximation if such an approximation exists, without any manual setting. An other problem of tree automata completion is the scaling when dealing with real life problems. In verification of Java programs using tree automata completion, this explosion may be due to the use of Peano numbers. The idea of the second contribution of this thesis is to evaluate directly the result of an arithmetic operation. Generally speaking, we integrate elements of an infinite domain in a tree automaton. Based on abstract interpretation, this thesis allows to integrate abstract lattice in tree automata. Operations on infinite domain are computed in one step of evaluation instead of probably many application of rewrite rules. Thus we adapted tree automata completion to this new type of tree automata with lattice, and genericity of the new algorithm allows to integrate many types of lattices. This technique has been implemented in a tool named TimbukLTA, and this implementation shows the efficiency of the technique.

Le but des modèles traditionnels en classification (comme les partitions et les hiérarchies de parties) est de permettre de discriminer sans ambiguïté et donc de produire des classes non empiétantes (i.e. l’intersection de deux classes est vide ou une classe est incluse dans l'autre). Cependant, cette exigence de non ambiguïté peut conduire à occulter de l’information. Dans le cas des plantes hybrides en biologie par exemple ou encore de textes appartenant à plusieurs genres en analyse textuelle. Les modèles généraux comme les hypergraphes ou les treillis permettent de prendre en compte l’empiétance entre les classes. Plus précisément, les modèles dits "totalement équilibrés" autorisent l'empiétance tout en conservant certaines contraintes utiles en classification.En apprentissage automatique, les arbres de décision, très utilisés pour leur simplicité d'utilisation et de compréhension réalisent à chaque étape un partitionnement d'un ensemble en deux sous-ensembles.Nous montrons dans ce travail différents liens entre la classification traditionnelle et l'apprentissage automatique supervisé et montrons certains apports que chacun des deux mondes peut faire à l'autre.Nous proposons deux méthodes de classification mêlant les deux univers puis étendons la notion de binarité, très utilisée dans le cas des arbres, aux hypergraphes et aux treillis. Nous montrons alors l'équivalence entre les systèmes binarisables et les systèmes totalement équilibrés, faisant de ces derniers de parfaits candidats à la réalisation de modèles de classification en classes empiétantes. Nous proposons également diverses approximations de systèmes par des systèmes totalement équilibrés. / Traditionally, classification models (such as partitions and hierarchies) aim at separating without ambiguities and produce non-overlapping clusters (i.e two clusters are either disjoint or one is included in the other). However, this non ambiguity may lead to mask information such as in the case of hybrid plants in biology or of texts which belong to two (or more) different genres in textual analysis for instance. General models like hypergraphs or lattices allow to take into account overlapping clusters. More precisely, "totally balanced" models allows class infringement and presents some useful constraints for classification.In machine learning, decision trees are a widely used model as they are simple to use and understand. They are also based on the idea of partition of sets.We show in this work different links between traditional classification and supervised machine learning and show what each world can bring to the other.We propose two methods of classification which link the two universes. We then extend the notion of binarity, widely-used for trees, to hypergraphs and lattices. We show the equivalence between binarizable systems and totally balanced systems, which makes of totally balanced structures a great candidate for classification models with class infringement. We also propose some approximation methods of any system (lattice, hypergraph, dissimilarity) by a totally balanced one.

Les comportement épistémiques, mobiles et spatiaux sont omniprésent dans les systèmes distribués aujourd’hui. La nature intrinsèque épistémique de ces types de systèmes provient des interactions des éleménts qui en font parties. La plupart des gens sont familiarisés avec des systèmes numériques où les utilisateurs peuvent partager ses croyances, opinions et même des mensonges intentionnels (des canulars). Aussi, les modèles de ces systèmes doivent tenir compte des interactions avec d’autres de même que leur nature distribués. Ces comportements spatiaux et mobiles font part d’applications où les données se déplacent dans des espaces (peut-être imbriqués) qui sont définis par, par exemple, cercles d’amis, des groupes, ou des dossiers partagés. Nous pensons donc qu’une solide compréhension des notion d’espaces, de mobilité spatial ainsi que le flux d’information épistémique est cruciale dans la plupart des modèles de systèmes distribués de nos jours.Les systèmes de contrainte (sc) fournissent les domaines et les opérations de base pour les fondements sémantiques de la famille de modèles déclaratifs formels de la théorie de la concurrence connu sous le nom de programmation concurrent par contraintes (pcc). Les systèmes des contraintes spatiales (scs) représentent des structures algébriques qui étendent sc pour raisonner sur les comportement spatiaux et épistémiques de base tel que croyance et l’extrusion. Les assertions spatiales et épistémiques peuvent être vues comme des modalités spécifiques. D’autres modalités peuvent être utilisées pour les assertions concernant le temps, les connaissances et même pour l’analyse des groupes entre autres concepts utilisés dans la spécification et la vérification des systèmes concurrents.Dans cette thèse nous étudions l’expressivité des systèmes de contraintes spatiales dans la perspective générale du comportement modal et épistémique. Nous montrerons que les systèmes de contraintes spatiales sont assez robustes pour capturer des modalités inverses et pour obtenir de nouveaux résultats pour les logiques modales. Également, nous montrerons que nous pouvons utiliser les scs pour exprimer un comportement épistémique fondamental comme connaissance. Finalement, nous donnerons une caractérisation algébrique de la notion de l’information distribuée au moyen de constructions sur scs. / Epistemic, mobile and spatial behaviour are common place in today’s distributed systems. The intrinsic epistemic nature of these systems arises from the interactions of the elements taking part of them. Most people are familiar with digital systems where users share their beliefs, opinions and even intentional lies (hoaxes). Models of those systems must take into account the interactions with others as well as the distributed quality these systems present. Spatial and mobile behaviour are exhibited by applications and data moving across (possibly nested) spaces defined by, for example, friend circles, groups, and shared folders. We therefore believe that a solid understanding of the notion of space and spatial mobility as well as the flow of epistemic information is relevant in many models of today’s distributed systems.Constraint systems (cs’s) provide the basic domains and opera- tions for the semantic foundations of the family of formal declarative models from concurrency theory known as concurrent constraint programming (ccp). Spatial constraint systems (scs’s) are algebraic structures that extend cs’s for reasoning about basic spatial and epistemic behaviour such as belief and extrusion. Both spatial and epistemic assertions can be viewed as specific modalities. Other modalities can be used for assertions about time, knowledge and even the analysis of groups among other concepts used in the specification and verification of concurrent systems.In this thesis we study the expressiveness of spatial constraint systems in the broader perspective of modal and epistemic behaviour. We shall show that spatial constraint systems are sufficiently robust to capture inverse modalities and to derive new results for modal logics. We shall show that we can use scs’s to express a fundamental epistemic behaviour such as knowledge. Finally we shall give an algebraic characterization of the notion of distributed information by means of constructors over scs’s.

Cette thèse porte sur l'exploitation des connaissances de domaine dans un processus de découvertes de sources de données biologiques sur le Web. Tout d'abord, des ontologies de domaine sont utilisées pour représenter un ensemble de connaissances qui reflètent le contenu et la qualité des sources de données. Ensuite, en s'appuyant sur ces connaissances, les sources sont organisées dans un treillis de concepts en fonction de leurs caractéristiques communes. Le treillis de concept constitue le support de la découverte qui peut être effectuée de deux manières différentes et complémentaires : par navigation et par interrogation. Dans les deux cas la découverte peut être guidée par des connaissances de domaines. Lors d'une découverte par navigation, les connaissances sont utilisées soit pour réduire l'espace de recherche soit pour orienter la navigation vers des concepts plutôt que d'autres. Lors d'une découverte par interrogation les connaissances de domaine sont soit exprimées sous la forme de préférences entre mots clés dans la requête soit utilisées pour l'enrichissement (ou reformulation) de la requête. Pour assurer une meilleure prise en compte des connaissances de domaine nous avons introduit les treillis de concepts multivalués. L'organisation des sources sous la forme d'un treillis de concepts multivalués permet de contrôler la taille de l'espace de recherche et d'augmenter la flexibilité et les performances du processus de découverte dans ses deux modes. La navigation peut être effectuée dans des treillis de différents niveaux de précision avec la possibilité d'effectuer des zooms dynamiques permettant le passage d'un treillis à l'autre. L'interrogation bénéficie d'une augmentation de l'expressivité dans les requêtes.

Il s'agit d'utiliser par la production de logiciels effectivement opérationnels, les techniques graphiques interactives dans le domaine de l'analyse structurale de système. On s'est orienté plus précisément vers une catégorie précise de représentation des systèmes: les graphes.

.

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.