Questionnaire

Université de Sherbrooke
Département d'informatique
IFT 615
Intelligence artificielle
Examen périodique
Hiver 2009 Le vendredi 27 février, 10 h 30 à 12 h 20, au D3-2037
Professeur
Froduald Kabanza
http://www.usherbrooke.ca/~kabanza
instructions L'examen dure une heure et cinquante minutes (10 h 30 à 12 h 20). Les notes du cours (copie des présentations), le manuel (livres de
référence) et les calculatrices sont autorisés. Les appareils électroniques
(à part les calculatrices) sont strictement interdits, en particulier tout
appareil muni d'un moyen de communication. L'examen comporte quatre questions pour vingt points au total. Répondez sur ce questionnaire qui sert en même temps de cahier de réponses
dans les endroits indiqués. Des feuilles de brouillon vous sont fournies. Ne détachez aucune feuille de ce questionnaire. Écrivez votre nom, prénom et matricule ci-dessous. NoM : ____________________________________
Prénom :_________________________________ MATRICULE : ____________________________ SIGNATURE
:______________________________ | |Q1 / 5|Q2 /5 |Q3 / 5|Q4 / 5|Total / |
| | | | | |20 |
|Note | | | | | |
Question 1 (5 points) - Satisfaction des contraintes On vous demande de concevoir un programme pour assigner des sièges lors
d'une réception d'un mariage. Nous avons N invités et M tables
circulaires, chacune avec une capacité de C (nombres de personnes maximales
par table). On suppose que le nombre de tables est suffisant pour le nombre
d'invités (MC ? N). Répondez le plus clairement possible aux questions
suivantes dans l'espace indiqué. a. (1 point) Supposons qu'on a des contraintes sur les personnes qui
doivent s'asseoir aux mêmes tables ou aux tables adjacentes (par exemple
des parents avec leurs enfants) et des paires de personnes qui ne peuvent
s'asseoir aux mêmes tables ou à des tables adjacents (par exemple les ex-
conjoints). Expliquez comment vous formaliseriez ce problème comme un
problème de satisfaction de contraintes.
| |
| |
| |
| |
| |
| |
b. (1 point) Proposez une technique (algorithme) pour résoudre ce
problème tel que formulé dans votre réponse précédente.
| |
| |
| |
| |
c. (1 point) Tel qu'énoncé au point (a), les contraintes sont « dures »
(elles doivent être absolument satisfaites) et le problème pourrait ne
pas avoir de solution. Proposez un énoncé différent pour le problème
d'assignations de places dans un mariage, avec des contraintes plus
souples, tel que le problème puisse tout le temps avoir une solution.
| |
| |
| |
| |
d. (1 point) Expliquez comment vous formaliseriez le nouveau problème, tel
qu'énoncé dans votre réponse au point c, comme un problème de
satisfaction de contraintes.
| |
| |
| |
| |
| |
e. (1 point) Proposez une technique (algorithme) pour résoudre le
nouveau problème tel que formulé dans votre réponse précédente.
| |
| |
| |
| |
Question 2 (5 points) - Alpha-Beta Pruning (5 points) Soit l'espace d'états suivant modélisant les actions de deux
joueurs (MAX et MIN). Les feuilles correspondent aux états terminaux du
jeu. Les valeurs des états terminaux sont indiquées en bas de chaque état.
Dessinez la partie de l'espace d'états qui serait explorée par l'algorithme
alpha-beta pruning, en supposant qu'il explore l'espace d'états de la
gauche vers la droite. Dessinez seulement les états explorés et les
transitions correspondantes. Indiquez, à côté de chaque état exploré, la
valeur correspondante à la terminaison de l'algorithme. | |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
Question 3 (5 points) - Réseaux bayésiens Soit le réseau bayésien (RB) suivant pour quatre variables booléennes
aléatoires (A, B, C et D) avec les tables de probabilité conditionnelle
correspondantes.
a. (1 point) Combien de valeurs indépendantes faudrait-il pour stocker la
distribution jointe des probabilités?
| |
| | b. (1 point) Pour ce réseau, est-ce vrai ou faux que P(A,C,D)=P(A)P(C)P(D)?
Justifiez votre réponse. | |
| |
| | c. (1 point) Pour ce réseau, est-ce vrai ou faux que P(D|C)=P(D|A,C)?
Justifiez votre réponse.
| |
| |
| | d. (1 point) Pour ce réseau, est-ce vrai ou faux que D est
conditionnellement indépendant de A étant donné B et C? Justifiez votre
réponse.
| |
| |
| | e. (1 point) Calculez P(+C | A, B).
| |
|P(+C | A, B) = |
Question 4 (5 points) Planification par les processus de décision de
Markov Soit le processus de décision markovien suivant, dont les transitions sont
étiquetées par les noms des actions et les probabilités de transitions; les
états sont étiquetés par les récompenses correspondantes (exprimant une
fonction d'utilité). a. (2 points) En utilisant une approche par processus de décision
markoviens, indiquez comment calculer la valeur du plan {S0 > a1, S1 >
a3, S2 > a4} dans l'état S2 (en supposant que l'exécution du plan
commence dans cet état). Soyez le plus précis possible dans l'espace
alloué. Utilisez un facteur d'atténuation (discount factor) de 0.2.
| |
| |
|