Examen mi-session
Intelligence Artificielle II (IFT-17587)
Jeudi 1er mars 2001
De 8h30 à 11h15 en salle 3775 PLT
Les documents permis sont le livre, les acétates du cours et une double page de notes
------------------------------------------------------------------------
1) (18 pts) Donner la PAGE et les caractéristiques de l’environnement d’un agent en charge de
la mise en place des ouvrages dans une bibliothèque. On pourrait supposer qu’un tel agent
prend les livres d’une place donnée et les range à la bonne place selon les côtes des livres.
2) a) (8 pts) Donner un exemple de chacune des quatre architectures d’agent et expliquer votre
choix.
b) (4 pts) Si on veut un agent qui combinerait « but » et « utilité » qu’elle serait d’après
vous l’architecture d’un tel agent ? Donnez un exemple de ce type d’agent et justifiez le.
3) Supposons que vous voulez implémenter un programme qui joue au tic-tac-toe, L’utilisateur
humain joue toujours O et la machine toujours X. Chaque case sur le board est appelée aij
où i est la ligne et j la colonne.
a) (6 pts) Définir les états, le but (test) et les opérateurs pour ce problème, en termes
de aij. Combien d’états y a t-il ?
b) (4 pts) Quelle algorithme de recherche pensez vous utiliser pour implémenter un
tel programme ? Pourquoi ?
c) (3pts) Décrire brièvement une fonction qui évalue la valeur d’un état, tel que
décrit en a), pour le joueur-machine.
4) Dans l’espace de recherche ci-dessous, le nombre placé à côté de chaque lien dénote le coût
associé au lien entre nœuds, et h est le coût estimé du nœud jusqu’au but final G.
a) (4 pts) Donner alors l’ordre dans lequel les nœuds sont visités lorsqu’on utilise le
A*. Donner alors f(n) pour chacun des nœuds n.
b) (4 pts) Un algorithme « vorace » du type meilleur-d’abord peut-il faire mieux ?
Combien de nœuds, un tel algo traverse-t-il avant d’atteindre le but G.
c) (5 pts) Autant la largeur-d’abord que le A* consomment de la mémoire (C’est
exponentiel !). Comment pouvez vous modifier A* de façon à utiliser moins
d’espace mémoire ? Quelle est alors la complexité en espace du nouvel algo ?
d) (4 pts) Si H est aussi un but, lequel parmi largeur-d’abord, profondeur-d’abord et
le profondeur-itératif peut trouver la solution optimale ?
e) (5 pts) La fonction heuristique h pose un problème dans la mesure où elle
surestime trop le coût de C à G. Quelle propriété de A* n’est plus remplie si h a
ce problème ?.
5) (10 pts) Supposons qu’on veut céduler un problème de salles de cours. Dans ce problème,
on a c salles et k cours, chaque cours débute à Sk et finit à Ek, avec Sk et Ek des entiers
naturels. Sachant qu’aucun cours ne doit partager avec un autre la même salle, que les salles
sont seulement disponibles entre 1 :00 et 5 :00, formulez ce problème comme un CSP
(constraint solving problem). Suggérez alors une heuristique pour résoudre ce problème et
expliquer pourquoi pensez-vous que votre heuristique peut résoudre un tel problème.
6) Pour chacune des assignations suivantes, dites si KB |== α est valide
a) (3 pts) KB = (A Ú B ® C) Ù A et α = C
b) (3 pts) KB = (A ® B) et α = B
c) (3 pts) KB = (A ®B) Ù (B ® C) et α = (A ® C)
7) Donner l’axiome successeur comme il a été introduit dans le cours pour les actions
suivantes :
a) (3 pts) Cassé(x,Resultat(a,s)) où x est une variable dénotant un verre
b) (3 pts) Avoir(lait,Resultat(a,s))
8) Dans l’algorithme de rétropropagation qui est utilisée pour les réseaux de neurones, l’erreur
pour une unité de sortie est donnée par la formule suivante : δ k ¬ o k (1 - o k )(t k - o k ) . Pour
une unité cachée, l’erreur est donnée par la formule suivante : δ h ¬ o h (1 - o h ) åw
kÎsorties
kh δk .
a) (3 pts) Expliquer pourquoi on n’utilise pas la même formule pour les unités
cachées.
b) (2 pts) Expliquer l’idée derrière l’utilisation de la somme åw
kÎsorties
kh δ k pour
calculer l’erreur faite par l’unité cachée.
9) (5 pts) Dans les algorithmes génétiques, expliquer les effets du taux du mutation sur la
population. Que se passe-t-il s’il est trop grand ou trop faible ?