Spelling suggestions: "subject:"info:info:info_ai"" "subject:"info:info:info_ni""
1 |
Une approche expérimentale à la théorie algorithmique de la complexitéZenil, Hector 21 June 2011 (has links) (PDF)
Une caractéristique contraignante de la complexité de Kolmogorov-Chaitin (dénotée dans ce chapitre par K) est qu'elle n'est pas calculable à cause du problème de l'arrêt, ce qui limite son domaine d'application. Une autre critique concerne la dépendance de K à un langage particulier ou une machine de Turing universelle particulière, surtout pour les suites assez courtes, par exemple, plus courtes que les longueurs typiques des compilateurs des langages de programmation. En pratique, on peut obtenir une approximation de K(s), grâce à des méthodes de compression. Mais les performances de ces méthodes de compression s'écroulent quand il s'agit des suites courtes. Pour les courtes suites, approcher K(s) par des méthodes de compression ne fonctionne pas. On présente dans cet thèse une approche empirique pour surmonter ce problème. Nous proposons une méthode "naturelle" qui permet d'envisager une définition plus stable de la complexité de Kolmogorov-Chaitin K(s) via la mesure de probabilité algorithmique m(s). L'idée est de faire fonctionner une machine universelle en lui donnant un programme au hasard pour calculer expérimentalement la probabilité m(s) (la probabilité de produire s), pour ensuite évaluer numériquement K(s) de manière alternative aux méthodes des algorithmes de compression. La méthode consiste à : (a) faire fonctionner des machines de calcul (machines de Turing, automates cellulaires) de façon systématique pour produire des suites (b) observer quelles sont les distributions de probabilité obtenues et puis (c) obtenir K(s) à partir de m(s) par moyen du théorème de codage de Levin-Chaitin.
|
2 |
Modélisation qualitative des agro-écosystèmes et aide à leur gestion par utilisation d'outils de model-checkingZhao, Yulong 13 January 2014 (has links) (PDF)
La modélisation dans le domaine de l'agro-écologie est importante car elle permet de mieux comprendre les interactions entre l'environnement et les activités humaines. Des travaux basés sur la simulation ont été développés depuis des années. Cependant, non seulement ces outils restent difficiles à utiliser par les utilisateurs non experts, mais aussi le coût des modèles rend leur utilisation difficile à case de la complexité élevée en cas d'application réelle. Nous proposons une approche qui consiste à représenter le système étudié dans un formalisme de système à événements discrets qui est bien adapté quand la dynamique du système est liée à des interactions entre les entités concernés. Ceci permet de profiter l'efficacité du model-checking pour étudier le comportement du système modélisé et d'utiliser la synthèse de contrôleur pour générer automatiquement des stratégies optimales. Nous présentons deux contributions dans cette thèse. La première contribution concerne le projet EcoMata. Cette modélisation qualitative en automates temporisés pour un réseau trophique marin de type proie-prédateur permet d'analyser l'écosystème à l'aide de model-checking sans avoir à faire des simulations. Des scénarios de requête prédéfinis ont été développés dans un langage naturel pour que les utilisateurs non expert puissent faire des requêtes sur les réseaux trophiques sans avoir des connaissances sur la langage TCTL. Nous avons amélioré la génération automatique d'automates temporisés à partir d'une description des équation Lotka-Votera. Nous avons aussi proposé une approche de synthèse de contrôleur pour générer automatiquement des stratégies optimales de gestion de pêche. Le prototype logiciel EcoMata implémente l'ensemble des propositions incluant la recherche de stratégies optimales. Dans la seconde contribution, nous proposons une modélisation hybride en automates temporisés d'une exploitation de pâturage. Cette modélisation hybride combine un modèle numérique de la croissance d'herbe et un modèle qualitatif des activités de pâturage. Une structure hiérarchique organise les modèles dans quatre couches: la couche biologique, la couche activité, la couche décisionnelle et la couche d'horloge. Nous proposons quatre méthodes pour générer des stratégies optimales des activités de pâturage. La première méthode est appliquée à la recherche de stratégies optimales de la mise au pâturage. Trois méthodes sont dédiées à la recherche de stratégies optimales de la fertilisation. Une d'entre elles utilise la synthèse de contrôleur alors que les deux autres combinent la synthèse de contrôleur et l'apprentissage supervisé pour générer des stratégies génériques par type d'exploitation. Un prototype logiciel PaturMata a été développé implémentant cette modélisation, permettant aux utilisateurs de simuler des scénarios de pâturage et rechercher des stratégies optimales de mise au pâturage.
|
3 |
Des spécifications en langage naturel aux spécifications formelles via une ontologie comme modèle pivotSadoun, Driss 17 June 2014 (has links) (PDF)
Le développement d'un système a pour objectif de répondre à des exigences. Aussi, le succès de sa réalisation repose en grande partie sur la phase de spécification des exigences qui a pour vocation de décrire de manière précise et non ambiguë toutes les caractéristiques du système à développer.Les spécifications d'exigences sont le résultat d'une analyse des besoins faisant intervenir différentes parties. Elles sont généralement rédigées en langage naturel (LN) pour une plus large compréhension, ce qui peut mener à diverses interprétations, car les textes en LN peuvent contenir des ambiguïtés sémantiques ou des informations implicites. Il n'est donc pas aisé de spécifier un ensemble complet et cohérent d'exigences. D'où la nécessité d'une vérification formelle des spécifications résultats.Les spécifications LN ne sont pas considérées comme formelles et ne permettent pas l'application directe de méthodes vérification formelles.Ce constat mène à la nécessité de transformer les spécifications LN en spécifications formelles.C'est dans ce contexte que s'inscrit cette thèse.La difficulté principale d'une telle transformation réside dans l'ampleur du fossé entre spécifications LN et spécifications formelles.L'objectif de mon travail de thèse est de proposer une approche permettant de vérifier automatiquement des spécifications d'exigences utilisateur, écrites en langage naturel et décrivant le comportement d'un système.Pour cela, nous avons exploré les possibilités offertes par un modèle de représentation fondé sur un formalisme logique.Nos contributions portent essentiellement sur trois propositions :1) une ontologie en OWL-DL fondée sur les logiques de description, comme modèle de représentation pivot permettant de faire le lien entre spécifications en langage naturel et spécifications formelles; 2) une approche d'instanciation du modèle de représentation pivot, fondée sur une analyse dirigée par la sémantique de l'ontologie, permettant de passer automatiquement des spécifications en langage naturel à leur représentation conceptuelle; et 3) une approche exploitant le formalisme logique de l'ontologie, pour permettre un passage automatique du modèle de représentation pivot vers un langage de spécifications formelles nommé Maude.
|
4 |
Agents situés dans l'image et organisés en pyramide irrégulière: Contribution à la segmentation par une approche d'agrégation coopérative et adaptativeDuchesnay, Edouard 13 December 2001 (has links) (PDF)
Les agents situés dans l'image fournissent un cadre privilégié pour la mise en oeuvre de stratégies coopératives et localement adaptées en segmentation d'image. Ils facilitent l'intégration des connaissances a priori, expressions d'un modèle, permettant ainsi de dégager de nouvelles contraintes indispensables à toutes les étapes de la vision par ordinateur (de la segmentation à l'interprétation). Nous proposons un cadre conceptuel pour l'architecture logicielle d'un système de vision bas-niveau basée sur des agents situés dans l'image. Une telle architecture est articulée en trois niveaux d'analyse et de description : 1. Description globale et structurelle de l'organisation regroupant les agents. Cette étape de description s'attache à établir les liens entre agents. Nous proposons comme élément organisationnel la pyramide irrégulière qui impose sa structure à la population d'agents, afin de garantir un comportement globalement contrôlable et convergent de ces derniers. 2. Description locale, fonctionnelle et comportementale des agents composant le système. Nous proposons une mise en oeuvre particulière de l'architecture logicielle de vision bas-niveau. Dans cette dernière, deux familles d'agents, qui traduisent des primitives région et contour, interagissent localement au sein de la pyramide. Notre objectif est de montrer comment cette méthodologie permet une implémentation riche, flexible et distribuée des aspects précédemment identifiés; à savoir : l'adaptation locale, l'intégration et l'expression d'incertitudes dans l'information a priori et des traitements coopératifs région/région et région/contour. 3. Finalement, une analyse globale, comparative et fonctionnelle vérifie que l'ensemble des interactions locales produit une bonne segmentation des images. Nous comparons notre approche avec d'autres méthodes de segmentation sur des images médicales et des images de synthèse.
|
5 |
Association Rule Interactive Post-processing using Rule Schemas and Ontologies - ARIPSOMarinica, Claudia 26 October 2010 (has links) (PDF)
This thesis is concerned with the merging of two active research domains: Knowledge Discovery in Databases (KDD), more precisely the Association Rule Mining technique, and Knowledge Engineering (KE) with a main interest in knowledge representation languages developed around the Semantic Web. In Data Mining, the usefulness of association rule technique is strongly limited by the huge amount and the low quality of delivered rules. Experiments show that rules become almost impossible to use when their number exceeds 100. At the same time, nuggets are often represented by those rare (low support) unexpected association rules which are surprising to the user. Unfortunately, the lower the support is, the larger the volume of rules becomes. Thus, it is crucial to help the decision maker with an efficient technique to reduce the number of rules. To overcome this drawback, several methods have been proposed in the literature such as itemset concise representations, redundancy reduction, filtering, ranking and post-processing. Even though rule interestingness strongly depends on user knowledge and goals, most of the existing methods are generally based on data structure. For instance, if the user looks for unexpected rules, all the already known rules should be pruned. Or, if the user wants to focus on specific family of rules, only this subset of rules should be selected. In this context, we address two main issues: the integration of user knowledge in the discovery process and the interactivity with the user. The first issue requires defining an adapted formalism to express user knowledge with accuracy and flexibility such as ontologies in the Semantic Web. Second, the interactivity with the user allows a more iterative mining process where the user can successively test different hypotheses or preferences and focus on interesting rules. The main contributions of this work can be summarized as follows: (i) A model to represent user knowledge. First, we propose a new rule-like formalism, called Rule Schema, which allows the user to define his/her expectations regarding the rules through ontology concepts. Second, ontologies allow the user to express his/her domain knowledge by means of a high semantic model. Last, the user can choose among a set of Operators for interactive processing the one to be applied over each Rule Schema (i.e. pruning, conforming, unexpectedness, . . . ). (ii) A new post-processing approach, called ARIPSO (Association Rule Interactive Post-processing using rule Schemas and Ontologies), which helps the user to reduce the volume of the discovered rules and to improve their quality. It consists in an interactive process integrating user knowledge and expectations by means of the proposed model. At each step of ARIPSO, the interactive loop allows the user to change the provided information and to reiterate the post-processing phase which produces new results. (iii) The implementation in post-processing of the proposed approach. The developed tool is complete and operational, and it implements all the functionalities described in the approach. Also, it makes the connection between different elements like the set of rules and rule schemas stored in PMML/XML files, and the ontologies stored in OWL files and inferred by the Pellet reasoner. (iv) An adapted implementation without post-processing, called ARLIUS (Association Rule Local mining Interactive Using rule Schemas), consisting in an interactive local mining process guided by the user. It allows the user to focus on interesting rules without the necessity to extract all of them, and without minimum support limit. In this way, the user may explore the rule space incrementally, a small amount at each step, starting from his/her own expectations and discovering their related rules. (v) The experimental study analyzing the approach efficiency and the discovered rule quality. For this purpose, we used a real-life and large questionnaire database concerning customer satisfaction. For ARIPSO, the experimentation was carried out in complete cooperation with the domain expert. For different scenarios, from an input set of nearly 400 thousand association rules, ARIPSO filtered between 3 and 200 rules validated by the expert. Clearly, ARIPSO allows the user to significantly and efficiently reduce the input rule set. For ARLIUS, we experimented different scenarios over the same questionnaire database and we obtained reduced sets of rules (less than 100) with very low support.
|
6 |
Diagnostic et suivi d'état embarqués -- Une étude algorithmique.Fabien, Aratbi-Perrot 01 July 2011 (has links) (PDF)
La problématique de cette thèse a été d'étudier les systèmes pouvant (se) diagnostiquer en vue de (se) reconfigurer dans le contexte de l'amélioration de l'autonomie des systèmes spatiaux. Pour cela, nous nous sommes intéressés aux agents fondés sur un modèle du système, concept étudié en Intelligence Artificielle. Nous avons utilisé ce concept dans un but de suivi d'état, tout en prenant en compte les défauts pouvant affecter le système, effectuant ainsi la tâche de diagnostic dynamique. Pour cela, les aspects concernant les défauts du système ont été intégrés dans le modèle. Le suivi d'état est la tâche qui met à jour un état de croyance concernant le système. Nous l'avons analysé sous un angle algorithmique dans le but de répondre aux contraintes de faibles ressources de calcul présentes à bord des systèmes spatiaux. Nous avons étudié les algorithmes de suivi qui opèrent sur des modèles logiques, tels que ceux écrits en logique propositionnelle ou dans le langage des réseaux de contraintes, et sur des modèles probabilistes, tels que les réseaux Bayésiens dynamiques. Cette étude a permis de cibler le phénomène d'enchevêtrement qui rend exponentiel la représentation de l'état de croyance. Notre contribution consiste à proposer une approche algorithmique qui utilise un algorithme de recherche en profondeur d'abord dans un espace de recherche Et/Ou. Dans cet espace, le phénomène d'enchevêtrement a pu être analysé sous un nouvel angle. Nous avons proposé une solution au phénomène d'enchevêtrement en définissant, sous la forme de trois règles de calcul, un système cohérent et complet dans la théorie des ensembles. Nous avons ensuite défini des structures de données servant de représentation compacte de l'état de croyance. Ces structures de données sont appelées arbres symboliques. Nous concluons par une généralisation et des perspectives dans le domaine algorithmique et les mathématiques.
|
7 |
Fouille de données, Contributions Méthodologiques et ApplicativesCollard, Martine 16 December 2003 (has links) (PDF)
Les travaux présentés dans ce mémoire, ont été développés sur le thème de la découverte de motifs intéressants à travers la fouille de données et mis en oeuvre dans le cadre de la conception de systèmes d'information. Ils sont essentiellement consacrés aux problèmes soulevés par l'étape de fouille pour la découverte de modèles et de motifs fréquents. Ils sont à la fois d'ordre méthodologique et applicatif.
|
8 |
Apprentissage de problèmes de contraintesLopez, Matthieu 08 December 2011 (has links) (PDF)
La programmation par contraintes permet de modéliser des problèmes et offre des méthodes de résolution efficaces. Cependant, sa complexité augmentant ces dernières années, son utilisation, notamment pour modéliser des problèmes, est devenue limitée à des utilisateurs possédant une bonne expérience dans le domaine. Cette thèse s'inscrit dans un cadre visant à automatiser la modélisation. Les techniques existantes ont montré des résultats encourageants mais certaines exigences rendent leur utilisation encore problématique. Dans une première partie, nous proposons de dépasser une limite existante qui réside dans la nécessité pour l'utilisateur de fournir des solutions du problème qu'il veut modéliser. En remplacement, il nous fournit des solutions de problèmes proches, c'est-à-dire de problèmes dont la sémantique de fond est la même mais dont les variables et leur domaine peuvent changer. Pour exploiter de telles données, nous proposons d'acquérir, grâce à des techniques de programmation logique inductive, un modèle plus abstrait que le réseau de contraintes. Une fois appris, ce modèle est ensuite transformé pour correspondre au problème initial que souhaitait résoudre l'utilisateur. Nous montrons également que la phase d'apprentissage se heurte à des limites pathologiques et qui nous ont contraints à développer un nouvel algorithme pour synthétiser ces modèles abstraits. Dans une seconde partie, nous nous intéressons à la possibilité pour l'utilisateur de ne pas donner d'exemples du tout. En partant d'un CSP sans aucune contrainte, notre méthode consiste à résoudre le problème de l'utilisateur de manière classique. Grâce à un arbre de recherche, nous affectons progressivement des valeurs aux variables. Quand notre outil ne peut décider si l'affectation partielle courante est correcte ou non, nous demandons à l'utilisateur de guider la recherche sous forme de requêtes. Ces requêtes permettent de trouver des contraintes à ajouter aux modèles du CSP et ainsi améliorer la recherche.
|
9 |
Modèles de la rationalité des acteurs sociauxEl Gemayel, Joseph 25 June 2013 (has links) (PDF)
Le travail présenté dans ce mémoire s'inscrit dans le cadre du projet SocLab, qui propose une formalisation de la sociologie de l'action organisée de Crozier et Friedberg. Cette formalisation repose sur un méta-modèle de la structure des organisations sociales, à partir duquel il est possible de décrire la structure d'une organisation particulière, de développer une étude analytique de ses propriétés et surtout de calculer, par simulation, les comportements que les acteurs de cette organisation sont susceptibles d'adopter les uns vis-à-vis des autres. Selon cette approche, une organisation est vue comme un système qui, en fonction du comportement des acteurs les uns envers les autres, procure à chacun d'eux une certaine capacité d'action pour atteindre ses objectifs, sans distinguer ceux qui relèvent de son rôle et ceux qui lui sont propres. Ces comportements sont relativement stabilisés, condition indispensable à la coordination des acteurs dans l'accomplissement, au moins partiel, de ce qui constitue la raison d'être de l'organisation, et donc indispensable à l'existence même de cette organisation. Ces comportements s'avèrent de plus être globalement coopératifs, facilitant ainsi la réalisation des objectifs, aussi bien ceux propres à chacun que ceux du collectif dans son ensemble. Cette thèse porte sur la modélisation de la rationalité qui conduit un acteur social à adopter un tel comportement dans le " jeu social " que constitue un contexte d'interaction organisationnel. Selon la sociologie de l'action organisée, cette rationalité est stratégique, guidée par la recherche de son intérêt, et elle s'exerce dans le cadre d'une rationalité (très) limitée. Le modèle proposé cherche à être vraisemblable, du point de vue social et du point de vue psycho-cognitif, et il s'inscrit dans le paradigme de l'apprentissage par renforcement. Dans la mesure où la structure de l'organisation le permet, les simulations convergent donc vers des configurations que l'on peut qualifier d'optima Pareto-équitables. On étudie aussi diverses variantes de cet algorithme correspondant à des rationalités qui conduisent une organisation à se réguler vers des configurations élitistes, protectrices ou égalitaristes, ou encore vers un équilibre de Nash.
|
10 |
Self-describing objects with tangible data structuresSinha, Arnab 28 May 2014 (has links) (PDF)
Pervasive computing or ambient computing aims to integrate information systems into the environment, in a manner as transparent as possible to the users. It allows the information systems to be tightly coupled with the physical activities within the environment. Everyday used objects, along with their environment, are made smarter with the use of embedded computing, sensors etc. and also have the ability to communicate among themselves. In pervasive computing, it is necessary to sense the real physical world and to perceive its "context" ; a high level representation of the physical situation. There are various ways to derive the context. Typically, the approach is a multi-step process which begins with sensing. Various sensing technologies are used to capture low level information of the physical activities, which are then aggregated, analyzed and computed elsewhere in the information systems, to become aware of the context. Deployed applications then react, depending on the context situation. Among sensors, RFID is an important emerging technology which allows a direct digital link between information systems and physical objects. Besides storing identification data, RFID also provides a general purpose storage space on objects, enabling new architectures for pervasive computing. In this thesis, we defend an original approach adopting the later use of RFID i.e. a digital memory integrated to real objects. The approach uses the principle where the objects self-support information systems. This way of integration reduces the need of communication for remote processing. The principle is realized in two ways. First, objects are piggybacked with semantic information, related to itself ; as self-describing objects. Hence, relevant information associated with the physical entities are readily available locally for processing. Second, group of related objects are digitally linked using dedicated or ad-hoc data structure, distributed over the objects. Hence, it would allow direct data processing - like validating some property involving the objects in proximity. This property of physical relation among objects can be interpreted digitally from the data structure ; this justifies the appellation "Tangible Data Structures". Unlike the conventional method of using identifiers, our approach has arguments on its benefits in terms of privacy, scalability, autonomy and reduced dependency with respect to infrastructure. But its challenge lies in the expressivity due to limited memory space available in the tags. The principles are validated by prototyping in two different application domains. The first application is developed for waste management domain that helps in efficient sorting and better recycling. And the second, provides added services like assistance while assembling and verification for composite objects, using the distributed data structure across the individual pieces.
|
Page generated in 0.0294 seconds