Faculté des Arts et Sciences - Département d'Informatique et de ...

Faculté des Arts et Sciences - Département d'Informatique et de
Recherche opérationnelle TITRE DU COURS: Intelligence Artificielle: Introduction
SIGLE: IFT3330 / 6330 PROFESSEUR: Jian-Yun Nie
EXAMEN: INTRA-A2000 DATE: le 17 oct. 2000
LIEU: G715 HEURES: 17h30-19h30
_________________________________________________________________________ Directive pédagogique: Les documentations sont permises.
_________________________________________________________________________
Question 1. (10 points) Est-ce que chaque groupe d'expressions suivant est unifiable? Si oui,
donnez les substitutions.
1. p(a), p(X) oui a/X
2. X, p(a,b), p(Z) non
3. X, p(Y,c), p(d,X) non
4. p(f(X), g(y)), p(a,b) non
5. p(X, f(X)), p(a, Z) oui a/X, f(a)/Z
Question 2. (20 points) a) Exprimez les phrases suivantes en logique de prédicats:
1. Il y a des gens qui parlent.
2. Les gens qui parlent n'écoutent pas.
b) Donnez les formes clausales de ces expressions.
c) Étant donné les deux phrases de a), est-ce qu'on peut prouver les
phrases suivantes respectivement par la méthode de résolution par
réfutation?
Aucune personne n'écoute.
Certaines personnes n'écoutent pas.
Si oui, montrez votre preuve.
Similaire à la question dans l'intra A99.
Question 3. (10 points)
Décrivez votre compréhension du principe de résolution par réfutation,
notamment, expliquez les points suivants:
1. Que signifie l'adéquation (soundness) d'une règle d'inférence comme
celle-ci:
A ( B, (A ( C
--------------------
B( C
Comment justifierez-vous intuitivement l'adéquation de cette
règle?
Cette règle revient à la forme équivalente suivante:
(B=>A, A=>C
--------------------
(B=>C
C'est donc la transitivité de l'implication. On peut expliquer cette
transitivité.
2. Pourquoi quand on arrive à la contradiction (() dans une procédure de
résolution, la conclusion est prouvée?
Parce qu'on part de la négation de la conclusion. Si on arrive à la
conclusion, ça signifie que la négation de la conclusion n'est pas
cohérente avec les expressions acceptées. Donc, la conclusion doit être
vraie. Elle est donc une conséquence logique. Question 4 (20 points)
Le problème de missionnaires et de cannibales est comme suit: 3
missionnaires et 3 cannibales doivent traverser une rivière. Il y a
juste un bateau qui peut contenir au plus 2 personnes, et il ne peut
pas voyager seul sans au moins une personne abord. Si à un endroit, le
nombre de cannibales dépasse celui des missionnaires, les cannibales
mangent les missionnaires. Le but est de trouver un plan permettant aux
missionnaires et aux cannibales de traverser la rivière sain et sauf.
On voudrait résoudre ce problème par une recherche dans un espace
d'états. 1. Énumérez les caractéristiques à tenir compte dans la définition
d'état dans ce problème et définissez une représentation.
2. Exprimez l'état initial et l'état but dans cette représentation.
3. Dessinez les deux premiers niveaux de l'espace d'états après l'état
initial.
4. Est-ce qu'une recherche heuristique est possible à ce problème? Si
oui, comment?
Expliqué pendant la révision.
Question 5. (15 points) Soit les règles suivantes dans le système MYCIN :
IF (a and b) THEN (c, 0.6).
IF (c and d) THEN (f, 0.9).
IF (a and e) THEN (f, 0.4).
et les faits qu'on observe sont les suivants:
(a, 0.5)
(b, 0.9)
(d, 0.4)
(e, 0.7)
1. Quelle est la conclusion que MYCIN arrive à trouver, et à quel facteur
de certitude?
Semblable à l'exemple de beau temps/mauvais temps de l'intra A99.
2. Peut-on interpréter ces facteurs de certitude comme des probabilités
comme suit:
P(c|a,b) = 0.6
P(f|c,d) = 0.9
P(f|a,e) = 0.4
P(a) = 0.5
P(b) = 0.9
P(d) = 0.4
P(e) = 0.7
et pouvoir calculer P(f)? Expliquez pourquoi.
Non. Parce qu'on ne connaît pas les dépendances entre c/ et a/e. Question 6. (10 points)
Comment peut la logique de prédicat être utilisée pour raisonner dans
une application réelle? Expliquez cela pour l'approche syntaxique et
l'approche sémantique de la logique. Notamment, vous devez expliquer ce
que la logique doit faire, étant donné un ensemble de faits et un
ensemble de connaissances, pour obtenir des conclusions.
Expliqué aujourd'hui pendant la révision.
Question 7. (15 points) Supposons qu'on a déjà défini les prédicats suivants en Prolog:
valeur_heuristique(A, V): Il donne la valeur heuristique V pour
l'état A.
enfants(A, L): Il donne la liste d'enfants L de l'état A.
trier(L1, L2): Il trie la liste de doublets L1 en L2. Un doublet est
une liste de deux éléments dont le premier est un état, et le
deuxième est une valeur numérique. Le prédicat trier/2 trie la
liste L1 dans l'ordre décroissant de la valeur numérique.
Exemple, trier([[a,3],[b,1],[c,2]], [[a,3],[c,2],[b,1]]).
membre(A,L): Il détermine si l'élément A fait partie de la liste L.
Exemple: membre(b, [a,b,c]).
append(L1, L2, L3): Il relie deux listes L1 et L2 pour obtenir L3.
evaluer(L1, L2): Il évalue chaque état A de L1 par
valeur_heuristique/2, et constitue une liste de doublets d'états
et de valeurs. Par exemple: evaluer([a,b], [[a,2],[b,4]]).
enlever(A, L1, L2): Il enlève l'élément A de la liste L1, et met le
résultat dans L2. Exemple, enlever([b,1], [[a,3],[b,1],[c,2]],
[[a,3],[c,2]]). On voudrait faire un prédicat best_first(Goal, Open, Closed) pour
explorer un espace d'états selon l'algorithme Best-First. Les arguments
dans ce prédicat sont: Goal - liste des états buts; Open - liste des
états à évaluer, triés dans l'ordre décroissant de leurs valeurs
heuristiques; Closed - liste des états déjà examinés.
Le programme suivant réalise la recherche Best-First dans un espace en
forme d'un arbre. best_first(Goal, [[A,_]|_], _) :- membre(A, Goal).
best_first(Goal, [[A,V]|B], Closed) :- enfants(A, Enfants),
evaluer(Enfants, Enfants_valeurs),
append(B, Enfants_valeurs, B1),
trier(B1, Open1),
best_first(Goal, Open1, [[A,V]|Closed]).
1. Pour que ce programme fonctionne pour la recherche Best-First dans un
graphe quelconque, qu'est-ce qu'il est nécessaire de modifier? Décrivez
les modifications en pseudo-codes.
2. Implantez ces modifications en Prolog.