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° 1 : (Corrigé) L’importance d’une bonne représentation du problème pour faciliter sa résolution est donnée par de nombreux exemples, en particulier celui-ci. 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 → ε (α 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. Département d’Informatique de Tizi-Ouzou Année Universitaire 2019 / 2020 _______________________________________________________________________________________________ _______________________________________________________________________________________________ R.Ahmed-Ouamer 2 Fondements de l’Intelligence Artificielle 1) Peut-on représenter le graphe des états possibles du problème ? Pourquoi ? 1ère représentation : Tracé du graphe des états possibles Ce graphe est infini, puisque les règles R1 et R2 permettent d’allonger les séquences. 2ème représentation : 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 ? On peut reposer le problème suivant : R2: b → 2b R3: b → b – 3 R1 et R4 sans effet sur b. avec pour donnée de départ b = 1 et pour but b = 0 Un examen des valeurs de b montre que le but n’est pas atteignable. Pour le prouver, il faut s’intéresser aux congruences. 3ème representation : 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. La règle R3 est sans effet sur k. Le problème reformulé comporte une seule règle R2: k → 2k Avec pour donnée initiale k = 1 (mod 3) Les seules états possibles pour k sont : 1 (mod 3) et -1 (mod 3) Le but k = 0 (mod 3) n’est pas atteignable Ainsi deux changements de représentation successifs transforment une recherche apparemment infinie en une question évidente. AB ABC R2 ABB R1 R2 ABCBC R2 ABCBCBCBC R1 ABBC R2 ABBCBBC ABBBB R2 R2 ABBBBBBBB R1 ABBBBC R3 ABC ACB Département d’Informatique de Tizi-Ouzou Année Universitaire 2019 / 2020 _______________________________________________________________________________________________ _______________________________________________________________________________________________ R.Ahmed-Ouamer 3 Fondements de l’Intelligence Artificielle 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° 2 : (Corrigé) 1) La représentation en espace d’états consiste à chercher la solution en décrivant la situation (état) de l’univers considéré, et l’ensemble des opérateurs qui permettent de transformer cette situation. La représentation en espace de problèmes consiste à décrire le problème et à utiliser des opérateurs de transformations du problème. Ces opérateurs décomposent le problème en plusieurs sous-problèmes plus simples (réduction de problème). 2) Exemple : Tours de Hanoi Soit à déplacer tous les disques, 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. Description en espace d’états possible : disque 1 disque 2 … disque n Le plus petit … le plus grand (A A … A) → Etat initial (B B … B) → Etat final Département d’Informatique de Tizi-Ouzou Année Universitaire 2019 / 2020 _______________________________________________________________________________________________ _______________________________________________________________________________________________ R.Ahmed-Ouamer 4 Fondements de l’Intelligence Artificielle Pour seulement trois disques, les opérateurs de transformation sont : R1 : Le petit disque peut toujours être déplacé R1 ∀X, Y, Z (X Y Z) → (T Y Z) R2 : Le disque moyen peut être déplacé, s’il n’est pas sous le petit disque (X ≠ Y), sur une autre tige que celle qui accueille ce dernier (T ≠ X) R2 ∀X ≠ Y (X Y Z) → (X T Z) ∀T ≠ X R3 : Le grand disque ne peut être déplacé que s’il est seul sur sa tige (X ≠ Y), les deux autres sont sur la même tige (X), sur laquelle il ne peut aller (Z ≠ X) R3 ∀X ≠ Y (X X Y) → (X X Z) ∀Z ≠ X Cette représentation deviendrait vite lourde avec l’accroissement du nombre de disque. 3) a) Dans le cas des tours de Hanoï, le problème est décrit ainsi : (A A… A) ---> (B B… B) L’opérateur de décomposition (défini pour une liste de longueur quelconque) est : (X X…X) ---> (Y Y…Y)  (X X…X) ---> (Z Z…ZX) ---> (Z Z…ZY) ---> (Y Y…Y) Cet opérateur réduit le problème initial, sur n disques, à deux problèmes identiques au premier, mais pour n-1 disques, et à un mouvement élémentaire (déplacement du grand disque) On peut aussi le représenter avec le formalisme des hyperarcs : b) Pour 3 disques : i.e. (AAA) ---> (BBB)  (AAA) ---> (CCA) ---> (CCB) ---> (BBB)  (AAA) → (BAA) → (BCA) → (CCA) → (CCB) → (ACB) → (ABB) → (BBB) (X X…X) ---> (Y Y…Y) (X X… X) ---> (Z Z…ZX) (Z Z…ZX) ---> (Z Z…ZY) (Z Z…ZY) ---> (Y Y… Y) (A A A) ---> (B B B) (A A A) ---> (C C A) (C C A) ---> (C C B) (C C B) ---> (B B B) (A A A) ---> (B A A) (B A A) ---> (B C A) (B C A) ---> (C C A) (C C B) ---> (A C B) (A C B) ---> (A B B) (A B B) ---> (B B B) Département d’Informatique de Tizi-Ouzou Année Universitaire 2019 / 2020 _______________________________________________________________________________________________ _______________________________________________________________________________________________ R.Ahmed-Ouamer 5 Fondements de l’Intelligence Artificielle 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 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° 3 : (Corrigé) 1) Définition des opérateurs : Opérateurs Prendre(x) Poser(x) Empiler(x,y) Dépiler(x,y) Préconditions PinceVide ∧ Libre(x) ∧ SurTable(x) Tenu(x) Tenu(x) ∧ Libre(y) Libre(x) ∧ Sur(x,y) ∧ PinceVide Ajouts Tenu(x) Libre(x) ∧ SurTable(x) ∧ PinceVide Libre(x) ∧ Sur(x,y) ∧ PinceVide Tenu(x) ∧ Libre(y) Retraits PinceVide ∧ Libre(x) ∧ SurTable(x) Tenu(x) Tenu(x) ∧ Libre(y) Libre(x) ∧ Sur(x,y) ∧ PinceVide 2) Etat initial : PinceVide ∧ SurTable(B) ∧ SurTable(C) ∧ Sur(A, B) ∧ Libre(A) ∧ Libre(C) Etat final : PinceVide ∧ SurTable(A) ∧ SurTable(C) ∧ Sur(B,C) ∧ Libre(A) ∧ Libre(B) Département uploads/Geographie/ m1cpiisirmsesifia-td-corrige.pdf