Remerciez-le!

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

Examen d’Intelligence Artiﬁcielle Lundi 8 Septembre 2008 ´ E. Salvat Promotion

Examen d’Intelligence Artiﬁcielle Lundi 8 Septembre 2008 ´ E. Salvat Promotion Carmack 2i` eme ann´ ee Ann´ ee 2007-2008 Modalits : – Dur´ ee : 2 heures – Aucun documents autoris´ es, ni machine ` a calculer, ni t´ el´ ephone. – Toute sortie est d´ eﬁnitive ! – Le bar` eme est donn´ e ` a titre indicatif. Exercice 1. Questions de cours - 5 points Pour les questions de cours ` a choix multiples, vous r´ epondrez sur votre copie en notant simplement le num´ ero de la question et le(s) num´ ero(s) de(s) la r´ eponse(s) correspondante(s) (les questions peuvent avoir plusieurs r´ eponses possibles). e.g. : question 0 r´ eponses c et d 1. Soit π un CSP chemin-consistant. Parmi les aﬃrmations suivantes la/les quelle(s) est/sont exacte(s) : (a) π a au moins une solution (b) π n’a pas forc´ ement une solution (c) π est forc´ ement arc consistant (d) π n’est pas forc´ ement arc consistant 2. Soient le graphe ci desous, et h une fonction heuristique ´ evaluant la distance entre chaque sommet et le sommet E. On souhaite calculer le plus court chemin de A ` a E. A C B D E 1 4 2 12 10 8 La fonction heuristique h : A B C D E 10 10 6 7 0 Donnez pour chaque algorithme ci dessous le sommet explor´ e apr` es le sommet A : (a) Glouton (b) Dijkstra (c) A* Corrig´ e de l’exercice. (a) Glouton : C, on choisit le sommet successeur de A ayant la plus faible valeur d’heuristique. (b) Dijkstra : B, on choisit le sommet successeur de A le plus proche. (c) A* : D, on choisit le sommet successeur de A dont somme de la distance ` a A plus la valeur de l’heuristique est la plus faible. 3. On consid` ere l’exploration de l’espace de recherche d’un probl` eme donn´ e par les algorithmes en lageur d’abord et en profondeur d’abord. Dans le cas o` u le facteur de branchement pour les deux algorithmes est b et la profondeur maximale est m (une valeur ﬁnie), parmi les aﬃrmations sui- vantes la/les quelle(s) est/sont exacte(s) : (a) la recherche en profondeur d’abord trouve toujours la premi` ere solution plus vite que la re- cherche en lageur d’abord 1 (b) la recherche en lageur d’abord trouve toujours la premi` ere solution plus vite que la recherche en profondeur d’abord (c) la recherche en lageur d’abord necessite plus d’espace m´ emoire que la recherche en profondeur d’abord (d) la recherche en lageur d’abord necessite moins d’espace m´ emoire que la recherche en profon- deur d’abord Corrig´ e de l’exercice. Les deux algorithmes ont dans le pire des cas la mˆ eme complexit´ e en temps : O(bm) ; mais la complexit´ e en espace est en O(bm) pour la profondeur et en O(bm) pour la largeur. Pour les exercices suivants vous prendrez soin d’expliquer tout ce que vous faites et de justiﬁer toutes vos r´ eponses. Exercice 2. α −β - 5 points Soit le jeux ` a deux jours suivant. Au commencement, on dispose d’une pile de n jetons. A tour de rˆ ole, les joueurs doivent diviser une des piles devant eux en deux piles non vides et de tailles diﬀ´ erentes. A chaque tour du jeu, on cr´ ee donc une nouvelle pile. A partir de la conﬁguration de jeu comportant trois piles respectivement ` a 2, 3 et 2 jetons, le seul coup jouable est de diviser la pile contenant 3 jetons en deux piles : une avec 2 jetons et l’autre un seul jeton. Le joueur qui ne peut plus jouer (i.e. il ne reste que des piles de 1 ou 2 jetons) a perdu. 1. Appliquez l’algorithme α −β au jeu partant d’une pile de 7 jetons. 2. Qui est le vainqueur ? Corrig´ e de l’exercice. 2 2 (−∞, +∞) 7 (−∞, +∞) 6/1 (−∞, +∞) 5/1/1 (−∞, +∞) 4/1/1/1 (−∞, +∞) 3/1/1/1/1 (−∞, +∞) 2/1/1/1/1/1 1 (1, +∞) 3/2/1/1 (1, +∞) 2/2/1/1/1 -1 (−∞, 1) 4/2/1 (−∞, 1) 3/2/1/1 (−∞, 1) 2/2/1/1/1 -1 (−1, +∞) 5/2 (−1, +∞) 4/2/1 (−1, +∞) 3/2/1/1 (−1, +∞) 2/2/1/1/1 -1 3/2/2 (−1, +∞) 4/3 (−1, +∞) 3/3/1 (−1, +∞) 3/2/1/1 (−1, +∞) 2/2/1/1/1 -1 4/2/1 1 α = 1 1 β = 1 1 α = 1 -1 β = −1 -1 1 β = 1 -1 β = −1 -1 α = −1 -1 β = −1 -1 α = −1 -1 β = −1 -1 α = −1 -1 -1 β = −1 -1 α = −1 -1 Exercice 3. A* - 5 points Soit le graphe suivant, la valeur port´ ee sur chaque arc correspond au coˆ ut de passage d’une extr´ emit´ e de l’arc ` a l’autre. On souhaite calculer le plus court chemin de A ` a H. A B C D E F G H I J 3 2 5 4 5 4 1 4 9 3 12 11 8 2 2 7 6 9 8 On a de plus la fonction heuristique h qui estime le coˆ ut pour atteindre H depuis chaque sommet. h est donn´ ee par le tableau ci dessous. 3 A B C D E F G H I J 9 7 3 2 6 1 2 0 4 6 1. Appliquez l’algorithme A* avec la fonction h sur ce graphe. 2. Donnez le plus court chemin de A ` a H ainsi que sa valeur que vous avez trouv´ es dans la question pr´ ec´ edente. Exercice 4. Il y a bien longtemps dans une galaxie lointaine, tr` es lointaine.... - 5 points Il y a bien longtemps dans une galaxie lointaine, tr` es lointaine.... , les codes de s´ ecurit´ e du Faucon Millenium ont ´ et´ e d´ erob´ es. L’inspecteur Skywalker a pu extraire 5 photos de 5 suspects capt´ ees par les cam´ eras de surveillance. (a) Photo 1 (b) Photo 2 (c) Photo 3 (d) Photo 4 (e) Photo 5 Fig. 1: Les photos des suspects Apr` es une longue enquˆ ete pour identiﬁer les 5 suspects, notre inspecteur a r´ euni 5 t´ emoignages, chacun aﬃrmant reconnaˆ ıtre deux des suspects. Mais, comme rien n’est jamais tr` es simple dans cette galaxie, une seule des aﬃrmations, et exactement une, de chaque t´ emoin est vraie (et l’autre est par cons´ equent fausse). Voici les d´ eclarations de chaque t´ emoin : – t´ emoin n ˚ 1 : Le personnage de la photo 2 est C3PO et celui de la photo 3 est Chewbaka – t´ emoin n ˚ 2 : Le personnage de la photo 1 est Yoda et celui de la photo 2 est Palpatine – t´ emoin n ˚ 3 : Le personnage de la photo 3 est Palpatine et celui de la photo 5 est Yoda – t´ emoin n ˚ 4 : Le personnage de la photo 2 est C3PO et celui de la photo 4 est Dark Vador – t´ emoin n ˚ 5 : Le personnage de la photo 4 est Dark Vador et celui de la photo 1 est Chewbaka Bien ´ evidemment, chaque photo ne correspond qu’` a un seul suspect (autrement dit, 2 photos diﬀ´ erentes correspondent obligatoirement ` a 2 suspects diﬀ´ erents). Aﬁn d’aider l’inspecteur Skywalker ` a identiﬁer les 5 suspects, et faire ainsi correspondre chaque photo ` a un nom : 1. Proposez un CSP qui permette de repr´ esenter le probl` eme. 2. R´ esolvez le CSP que vous avez propos´ e pr´ ec´ edemment ` a l’aide de l’algorithme du Forward Checking. 4 uploads/Science et Technologie/ partiel-ia-2a-sept-08-corrige.pdf