Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Département d’Informatique de Tizi-Ouzou Année Universitaire 2019 / 2020 ______

Département d’Informatique de Tizi-Ouzou Année Universitaire 2019 / 2020 _______________________________________________________________________________________________ _______________________________________________________________________________________________ R.Ahmed-Ouamer 1 Fondements de l’Intelligence Artificielle Fondements de l’intelligence artificielle Stratégies de recherche Exercice n° 1 : (Choix d’une représentation) Soit le système de règles de transformations portant sur l’alphabet A, B, C: R1: α B → α B C R2: A α → A α α R3: B B B → C R4: C C → ε (Par convention, α désigne une chaîne quelconque de lettres de l’alphabet initial et ε la chaîne vide). La donnée de départ est A B, et le but à atteindre est A C. 1) Peut-on représenter le graphe des états possibles du problème ? Pourquoi ? 2) Une première réflexion conduit à constater que le problème se ramène ici à supprimer un B. a) En désignant par b le nombre de B dans les chaînes formées, reformuler le problème précédent. b) Le but est-il atteignable ? 3) Une autre représentation consiste à poser k = b (mod 3). a) Reformuler le problème précédent. b) Quels sont alors les états possibles pour k ? Conclure. Exercice n° 2 : 1) Une décomposition classique des modes de représentation consiste à distinguer les représentations en espace d’états et celles en espace de problèmes. Expliquer ces deux notions. 2) En utilisant la représentation en espace d’états, spécifier une base de faits, des règles et une condition d’arrêt pour un système de production qui résout le problème des tours de Hanoï dont l’énoncé est : ''Soit à déplacer tous les disques (trois), empilés par tailles décroissantes de la tige A à la tige B. Les règles sont les suivantes: - on ne déplace qu’un disque à la fois, d’une tige sur une autre ; - on ne peut placer un disque sur un autre de taille inférieure''. 3) a) Donner la représentation en espace de problèmes du problème des tours de Hanoï pour n disques. b) En utilisant la représentation en espaces de problèmes, résoudre le problème des tours de Hanoï pour trois disques. Exercice n° 3 : (Génération de plan d’actions) On veut engendrer le plan d’actions permettant de passer de la situation 1) à la situation 2) décrites sur le schéma ci-dessous : Situation 1 Situation 2 A A C C B B Département d’Informatique de Tizi-Ouzou Année Universitaire 2019 / 2020 _______________________________________________________________________________________________ _______________________________________________________________________________________________ R.Ahmed-Ouamer 2 Fondements de l’Intelligence Artificielle Où : SurTable(A) s’interprète : A est sur la table. Sur(A, B) s’interprète : A sur B. Tenu(A) s’interprète A est dans la pince du robot. Libre(A) lorsqu’il n’y a pas de bloc sur A. PinceVide : la pince est vide. On dispose des opérateurs suivants : Prendre(x) : Prendre x sur la table. Poser(x) : Poser x sur la table. Empiler(x, y): Empiler x sur y. Dépiler(x, y) : Prendre x initialement sur y. 1) Définir les opérateurs précédents en termes de préconditions (applicabilité) et d’effets. 2) Déterminer les états initial et final de ce problème. 3) Donner le plan d’actions. Exercice n° 4 : (Planification hiérarchique) STRIPS (STanford Research Institute Problem Solver) est un générateur de plans pour un robot agissant dans un monde élémentaire. Il utilise des opérateurs qui décrivent les actions de base avec leurs préconditions, et deux listes de modifications apportées par l’opérateur : - delete list (liste des faits qui sont supprimés) ; - add list (liste des faits qui sont introduits dans l’univers par l’application de l’opérateur). Sont donnés un état du monde, et le ou les but(s) à atteindre. Sa stratégie de recherche en espace d’états reprend le principe de « means-ends analysis ». Illustrer son fonctionnement sur l’exemple suivant : L’objectif est de boire un café. Les éléments disponibles sont : une cafetière, de l’eau, une banque, une épicerie (marchand de café en grains), un café-bar ; le robot est dans la cuisine. Les opérateurs sont : - Pour avoir ''quelque chose'': acheter ''quelque chose'' préconditions: - être chez un marchand de ''quelque chose'' - avoir de l’argent add list : ''quelque chose'' delete list : (le problème se pose ici de valoriser le ''quelque chose'', et de supprimer la quantité d’argent correspondante. Nous ne considérons pas cette difficulté). - Pour avoir du café (boisson): faire du café préconditions: - être dans la cuisine - avoir du café en grains - avoir un moulin à café - avoir de l’eau - avoir une cafetière add list : du café (boisson) - Pour avoir du café (boisson): acheter du café préconditions: - être dans un café-bar - avoir de l’argent add list : du café (boisson) - Pour avoir de l’argent: prendre de l’argent préconditions: être à la banque add list : de l’argent - Pour être ''quelque part'': aller ''quelque part'' préconditions: avoir ce ''quelque part'' (le lieu existe) add list : être ''quelque part'' delete list : être ''où on était'' Note: Pour boire un café, le robot a le choix entre deux solutions: le faire ou aller l’acheter. Pour les besoins de la démonstration, on suppose qu’il choisit d’abord de le faire. Département d’Informatique de Tizi-Ouzou Année Universitaire 2019 / 2020 _______________________________________________________________________________________________ _______________________________________________________________________________________________ R.Ahmed-Ouamer 3 Fondements de l’Intelligence Artificielle Exercice n° 5 : (Cours) Une recherche de solution à un problème peut se faire, entre autres, en chaînage avant ou arrière. En chaînage avant, on part d’un état (description de faits) et on cherche à le transformer pour obtenir un état ''terminal'' (situation satisfaisante). Le chaînage arrière part du but à atteindre et cherche les opérateurs qui permettent d’atteindre ce but. Les conditions de ces opérateurs deviennent de nouveaux buts à réaliser, et ainsi de suite. 1) Quels sont les facteurs qui déterminent le choix entre ces deux stratégies ? 2) On considère la base de connaissances suivante : R1: SI griffes ET dents-pointues ET yeux-frontaux ALORS carnivore R2: SI mange-viande ALORS carnivore R3: SI carnivore ET rapide ALORS Félin R4: SI félin ET tacheté ALORS guépard R5: SI guépard ET amérique-du-sud ALORS jaguar Et les faits initiaux suivants : mange-viande, rapide, tacheté. Soit à démontrer le but guépard. a) Donner la trace du raisonnement en chaînage avant. b) Donner la trace du raisonnement en chaînage arrière. Exercice n° 6 : (TD) Nous considérons un monde avec 4 pions (A, B, C, D) non superposables. Ils peuvent être arrangés dans n’importe quel ordre, sauf A qui ne peut pas être plus à droite que D. Par exemple, ABCD et CBAD sont deux états possibles du monde, tandis que DCBA et CDAB ne sont pas possibles. Le monde peut être manipulé par une action de la forme echange(x, y) qui échange les pions des positions x et y. Par exemple echange(1, 2) transforme BCAD dans CBAD. Seules les actions echange(1, 2), echange(2, 3) et echange(2, 4) sont autorisées. Elles donnent un successeur uniquement si la situation atteinte est possible. 1) Dessinez le graphe d’états. 2) On suppose que l’état de départ est ADBC et l’état que l’on veut atteindre est CBAD. Donnez une heuristique pour ce problème. Le principe de l’heuristique devrait être suffisamment général pour pouvoir s’appliquer à des problèmes similaires. 3) Appliquez la recherche avec votre heuristique. Département d’Informatique de Tizi-Ouzou Année Universitaire 2019 / 2020 _______________________________________________________________________________________________ _______________________________________________________________________________________________ R.Ahmed-Ouamer 4 Fondements de l’Intelligence Artificielle Systèmes de raisonnement logique par résolution Exercice n° 7 : (TD) Soit les faits suivants : - Jean affirme : « Si Bernard est coupable, Sophie l’est aussi ». - Bernard dit : « Jean est coupable et Sophie ne l’est pas ». - Sophie assure : « Elle n’est pas coupable mais au moins l’un des deux autres protagonistes l’est ». On suppose que chacune des personnes ment si et seulement si elle est coupable. 1) Représenter en calcul propositionnel les trois affirmations. 2) Existe-il une interprétation qui satisfait les trois affirmations ? Exercice n° 8 : (Cours) 1) Représenter à l’aide de règles de production les assertions suivantes : A1: des entreprises publiques sont privatisées A2: Si des entreprises publiques sont privatisées Alors le trésor est à l’aise A3: Si le trésor est à l’aise Alors les impôts ne sont pas augmentés A4: Si il faut donner la priorité à la formation Alors les impôts sont augmentés A5: Si il faut développer le pays Alors il faut donner la priorité à la formation 2) Propager par inférences les connaissances du système. Exercice n° 9 : (Le club Ecossais) (TD) Il existe en Ecosse un club très fermé qui obéit aux règles suivantes : R1 : tout membre non écossais porte des chaussettes rouges. R2 : tout membre portant des chaussettes rouges porte un kilt. R3 : les membres mariés ne sortent pas le dimanche. R4 : un membre sort le dimanche si et seulement s'il est écossais. R5 : tout membre qui porte un kilt est écossais et est marié. R6 : tout membre écossais porte un kilt. 1) Traduire les règles de ce club écossais en logique propositionnelle. On utilisera exclusivement les propositions suivantes : e : « est écossais » c : « porte des uploads/Finance/ m1cpiisirmsesifia-td.pdf