Université Paris 7 - Master 1 Informatique - Intelligence Artificielle
Partiel du 9 novembre 2005 - Solutions
Exercice 1 On donne les valeurs suivantes: a = 5, b = 8, c = 3, d = 2, e = 6, f = 9. Dans un parcours gauche à droite
alpha-β coupe d et dans un parcours droite à gauche alpha-β coupe c.
Exercice 2 Pour le parcours gauche à droite, la seule coupure possible est d et pour droite à gauche c’est a. Pour que
alpha-β coupe d dans un parcours gauche à droite, on doit avoir min(a, b) ≥ c. Pour que alpha-β coupe a dans un
parcours droite à gauche, on doit avoir min(c, d) ≥ b. Puisque toutes les valeurs sont différentes, on a min(a, b) > c et
min(c, d) > b. À partir de min(a, b) > c on a b > c et à partir de min(c, d) > b on a c > b. Contradiction.
Exercice 3 Jeux (4 points)
• Si les seules valeurs possibles sont −1 et 1 on ne peut pas avoir une valeur plus grande que 1 pour un nœud max
et on ne peut pas avoir une valeur plus petite que −1 pour un nœud min. On peut donc arrêter de considérer des
fils dès qu’on a trouve 1 pour un nœud max et −1 pour un nœud min.
• On note une position comme par exemple (3, 2, 1, 1) (deux piles d’un jeton, une pile de deux jetons et une pile de
trois jetons). On indique les coupures même s’il n’y a plus de coups possibles
alpha=−1,−1,−1,−1
max (7) beta=1
−1 −1
min (4,3) 1,−1 (5,2) −1 (6,1)
1,1,−1 1,−1
−1,−1 −1,1 −1,−1 −1,−1
max (3,3,1) 1 (3,2,2) (4,2,1) (4,2,1)1
1 1
−1 −1 −1
min (3,2,1,1)1,−1 (2,2,2,1) (3,2,1,1)1,−1 (3,2,1,1)1,−1
valeur=1
max (2,2,1,1,1) (2,2,1,1,1) (2,2,1,1,1)
valeur = −1 valeur = −1 valeur = −1
• Min gagne.
Exercice 4
Pb(f rancais) = Pb (anglais) = 1/2
Pb(jeune/f rancais) = Pb (grande/f rancais) = Pb (bas/f rancais) = 2/3
Pb(vieux/f rancais) = Pb (petite/f rancais) = Pb(haut/f rancais) = 1/3
Pb(jeune/anglais) = Pb (grande/anglais) = Pb(bas/anglais) = 1/3
Pb(vieux/anglais) = Pb (petite/anglais) = Pb (haut/anglais) = 2/3
Pb(petite/f rancais) ∗ Pb (vieux/f rancais) ∗ Pb (haut/f rancais) ∗ Pb (f rancais) = 1/54
Pb(petite/anglais) ∗ Pb(vieux/anglais) ∗ Pb(haut/anglais) ∗ Pb (anglais) = 4/27
Pb(grande/f rancais) ∗ Pb (jeune/f rancais) ∗ Pb(bas/f rancais) ∗ Pb(f rancais) = 4/27
Pb(grande/anglais) ∗ Pb (jeune/anglais) ∗ Pb (bas/anglais) ∗ Pb (anglais) = 1/54
Donc, on a CN aiveBayes ((petite, vieux, haut)) = anglais et CN aiveBayes ((grande, jeune, bas)) = f rancais
Exercice 5 On calcule d’abord le temps de parcours entre les villes
A et C A,I C,D C,F D,E E,J E,B F,E F,G G,B I,J J,B
20+10+10=40 75 26 34 11 20 35 24 50 30 25 29
• L’heuristique associant X le temps de parcours du chemin à vol d’oiseau de X vers B n’est pas admissible. Par
exemple, l’heuristique pour G est 35 alors que le vrai coût est 30.
1
• On peut par exemple choisir h = le temps de parcours, si tout le chemin était descendant. Ca donne
A B C D E F G I J
55 0 39 31 20 31 25 16 16
• Recherche gloutonne: La suite des nœuds dévéloppés: (A, 55), (I, 16), (J, 16), (B, 0)
A∗ :
