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-99A DATE: le 19 oct. 1999
LIEU: Z-300 HEURES: 17h30-19h30
_________________________________________________________________________ Directive pédagogique: Toute documentation est permise.
_________________________________________________________________________
Question 1. (10%) La logique est depuis longtemps un outil privilégié pour modéliser
l'intelligence humaine. Expliquez en moins de 10 lignes le rôle que la
logique a joué dans l'intelligence artificielle.
Question 2. (20%) a) Est-ce que vous pouvez prouver que la phrase 2 suivante est une
conséquence logique de la phrase 1 par la résolution par réfutation?
Vous devez traduire d'abord ces phrases en expressions logiques, puis
les transformer en forme clausale, et tenter de faire la preuve. Si
vous avez une preuve, montrez votre preuve; sinon, expliquer pourquoi.
(Ici, on considère que "pauvre" est la négation de "riche".)
1. Les pauvres ne sont pas heureux.
2. Les heureux sont riches.
b) Admettons les phrases 1 et 2. Est-ce qu'on peut prouver la phrase 3?
Vous devez faire la même chose que dans la question a).
3. Les riches sont heureux.
Question 3. (20%) a) Parmi les expressions suivantes, quels sont des termes légaux en
Prolog?
1. a(b,X) 2. f([a, b|_], _a) 3. _m(a) 4. 'X'(X)
5. X
6. a=>b 7. if_then(a, b) 8. a 9. '>='(2,3) 10.
[1,2,3]
b) Que fait le programme suivant en Prolog?
a([],0).
a([X|Y],Z) :- a(Y,Z1), Z=Z1+X.
c) Faites un programme pour trier une liste dans l'ordre alphabétique. Question 4. (15%) Puisque l'algorithme largeur-d'abord est un algorithme qui garantie de
trouver la meilleure solution (ou le chemin le plus court), pourquoi on
utilise profondeur-d'abord qui ne le garantie pas?
Expliquez en votre propre langage pourquoi un algorithme A* est
admissible.
Expliquez pourquoi on préfère, entre deux algorithmes A*, celui qui
est plus informé? Question 5. (20%)
a) On pose le problème de recherche dans Prolog. Soit le programme en
Prolog suivant:
a :- b.
a :- c.
b :- d.
b :- e.
b :- f.
d :- i.
d :- j.
c :- g.
c :- h.
g :- k.
g :- l.
i.
j.
h. Ce programme correspond à l'arbre à droite où * marque des prédicats
directement satisfaits. Donnez la séquence des prédicats évalués par
Prolog suite à la requête |?- a.
Si on modifie Prolog de telle façon qu'il utilise une stratégie de Best-
first avec la fonction suivante pour choisir d'abord n dont f(n) est la
plus basse, quelles est la nouvelle séquence de prédicats pour la même
requête?
f(n) = g(n) + h(n)
où g(n) est le nombre d'appels aux phrases Prolog nécessaires pour
que n soit inscrit dans la liste Open (e.g. on a besoin de 2 appels
pour que d soit dans Open, c'est-à-dire aux phrases a :- c. et b :-
d.);
(0, si n est un prédicat directement satisfait (e.g. i)
h(n) = (?, si aucune phrase existe pour satisfaire n (e.g.
e);
(1, autrement.
h(n) donne une estimation de nombres de phrases à appeler pour
satisfaire n.
Si on change le programme en le suivant:
a :- b.
a :- c.
b :- d, e, f.
d :- i.
d :- j.
c :- g.
c :- h.
g :- k, l.
i.
j.
h.
c-1. Donnez le nouveau graphe correspondant à ce programme.
c-2. Comment peut-on estimer la fonction h(n) dans ce nouveau
programme? Vous pouvez la définir par des formules ou par des phrases.
c-3. Donnez la séquence de prédicats évalués en utilisant la fonction
f(n) avec votre définition de h(n).
Question 6. (15%)
Expliquez en 5 lignes comment un système expert résout un problème.
Formulez les "connaissances" suivantes en des règles expertes pour
l'organisation des activités d'un groupe:
S'il fait beau, on fera une marche (avec une préférence de 0.8), ou de
la natation (avec une préférence de 0.3).
S'il pleut, on fera de la gymnastique (préférence 0.8), ou de la
lecture (préférence 0.2), ou de la natation (préférence 0.5).
Le météo prévoit une probabilité de 60% de pluie pour demain, et 40% de
chance pour un beau temps. Que doit le groupe planifier comme activité
pour demain? Expliquez votre démarche.
-----------------------
[pic]