Remerciez-le!

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

M1cpiisirmsesifia td corrige

Département d ? Informatique de Tizi-Ouzou Année Universitaire Fondements de l ? intelligence arti ?cielle Stratégies de recherche Exercice n Choix d ? une représentation Soit le système de règles de transformations portant sur l ? alphabet A B C R B ? B C R A ? A R B B B ? C R 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 Peut-on représenter le graphe des états possibles du problème Pourquoi Une première ré exion 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 Une autre représentation consiste à poser k b mod a Reformuler le problème précédent b Quels sont alors les états possibles pour k Conclure Exercice n 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 R B ? B C R A ? A R B B B ? C R 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 R Ahmed-Ouamer Fondements de l ? Intelligence Arti ?cielle CDépartement d ? Informatique de Tizi-Ouzou Année Universitaire Peut-on représenter le graphe des états possibles du problème Pourquoi ère représentation Tracé du graphe des états possibles ABC R ABCBC R R ABCBCBCBC AB R ABBC R R R R ABB ABBBB R ABBCBBC ABBBBC ABBBBBBBB R ABC ACB Ce graphe est in ?ni puisque les règles R et R permettent d ? allonger les séquences ème représentation Une première ré exion 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 R b ? b R b ? b ?? R et R sans e ?et sur b avec pour donnée de départ b et pour but b Un examen des valeurs de b montre que le but n ? est pas atteignable Pour le prouver il faut s ? intéresser aux congruences ème representation Une autre représentation consiste à poser k b mod a Reformuler le problème précédent b Quels sont alors les états possibles pour k Conclure La règle R est sans e ?et sur k Le problème reformulé comporte une seule règle R k ? k Avec pour donnée initiale k mod Les seules états possibles pour k sont mod et - mod Le but k mod