Intelligence Artificielle 5ème Année G.
Info
Année 2013-2014
Devoir surveillé
Prof. R. Ezzahir
1. Encerclez les lettres correspondantes aux énoncés qui sont vrais. (3pt)
Le terme "Intelligence Artificielle" a été imaginé :
A. Par AZIMOV, auteur de science fiction dans sa série sur les robots.
B. Par ARISTOTE, philosophe des connaissances et de la description du monde.
C. Par des scientifiques réunis en séminaire aux Etats-Unis
L'objectif principal des techniques d'intelligence artificielle est :
A. Documenter correctement les connaissances des experts pour pouvoir les retrouver
facilement
B. Tenter de mimer des processus humains de résolution de problème pour affronter
les situations complexes avec des algorithmes simples
C. Construire les composants cerveau dans un dispositif plus large lié à la vie artificielle
Une heuristique, c'est :
A. Une connaissance sur un problème qui permet d'explorer un nombre de solutions
limité garantissant au mieux d'arriver à une solution correcte
B. Une technique de recherche "au hasard" dans un espace de solutions possibles en
pariant sur le fait que l'on trouvera la solution avant d'avoir épuisé toutes les
possibilités.
C. Un test de vérification qu'une solution est convenable par rapport à un problème
posé
2. Barrer les propriétés d’environnement qui sont invalides pour les agents suivants : (2pt)
Totalement Totalement
Observable Observable
Déterministe Déterministe
Épisodique Épisodique
Discret Discret
Jeux d’échec Taxi autonome
3. Algorithme de recherche graphique.
A. Notre héros intrépide, agent de recherche, est en retard pour son examen d'intelligence
artificielle et doit venir vite!
Le graphe ci-dessus représente le temps qu'il faut pour l’Agent de recherche à marcher
entre les différentes rues menant vers l’école. Pour chacune des stratégies de recherche
graphique suivantes, donner l'ordre dans lequel les Etats sont développés, ainsi que le
chemin retourné par la recherche graphique.
On suppose dans tous les cas, s’il y a conflit le premier nœud dans l’ordre alphabétique est
développé en premier. L'état de départ et l'objectif sont respectivement S et G. Rappelez-
vous que dans la recherche graphique,
graphique un état est développée qu'une seule fois.
a. Depth-First Search (1pt)
Etats développées: ……………………………………….…………………………………………
Chemin : …………………………………….……………………………………………………………………
b. Breadth-First Search (1pt)
Etats développées: ……………………………………….…………………………………………
Chemin : …………………………………….……………………………………………………………………
c. Uniform-cost Search (1pt)
Etats développées: ……………………………………….…………………………………………
Chemin : …………………………………….……………………………………………………………………
B. Le graphe suivant illustre un espace d’états S={ S0,…,S6} et une fonction de transition. Un
arc orienté d’un état si à Sj indique que Sj est un état successeur de Si. Les arcs sont
étiquetés de leur coût. La fonction but(x) retourne vrai si et seulement si x= S6.
La fonction heuristique h(x) est
définie à l’aide du tableau suivant.
Etats x S0 S1 S2 S3 S 4 S 5 S6
h(x) 3 3 2 7 1 4 0
a. La fonction heuristique h est-elle
est admissible? Justifiez (1pt)
………………………………………………
………………………………………………………………………………………………
………………………………………
………………………………………………
………………………………………………………………………………………………
………………………………………
b. Donnez une trace d’exécution de l’algorithme A* en utilisant l’espace
l’espace d’états et
les fonctions but et h définis précédemment. (4pt)
4. Problème de satisfaction de contraintes
A. - Mini-Sudoku - (4pt)
Mini-Sudoku est une variante réduite du célèbre jeu de Sudoku. En mini-Sudoku, on
est en présence d'une grille de 4x4, en outre divisé en une grille 2x2 de sous-grilles 2x2,
appelé « régions » (voir la figure ci-dessous). Chaque cellule doit être remplie avec un
nombre de 1 à 4. Étant donné un puzzle partiellement achevé, la tâche est la complétée
par des numéros soumis aux trois contraintes suivantes:
Un certain nombre ne doit apparaître qu'une seule fois dans chaque ligne
Un certain nombre ne doit apparaître qu'une seule fois dans chaque colonne
Un certain nombre ne doit apparaître qu'une seule fois dans chaque région de 2x2
Sudoku valide Suduoku invalide
a. Soit Xi, j représente la valeur des cellules (i, j), donner le modèle CSP de ce problème
(définir les variables, les domaines, et les contraintes).
Variables :……………………………………………………………………………………………………………
Domaines :…………………………………………………………………………………………………………..
Contraintes :…………………………………………………………………………………………………………
…………………………………………………………………………………………………………………………
…………………………………………………………………………………………………………………………
…………………………………… …………………………………………………………………………………
b. Considérons maintenant le Sudoku suivant partiellement rempli, en mettant l'accent
sur les variables a = X3,3, b = X3,4 et c = X4, 3 (a, b, et c sont des alias pour faire
référence à des variables).
Notez les domaines des variables a, b, c et après l'exécution de
forward-checking : ……………………………… ……………………………
……………………………………………………………………………..…………
En assignant la variable a, notez les domaines des deux variables
restantes après l'exécution du forward-checking :
…………………………………………………………..................
Quel est le critère permettant de déterminer une affectation CSP a
échoué (et le solveur doit revenir en arrière)?
……………………………… ……………………………………………………..
B. La consistance d’Arc (3pt)
Soit le problème de satisfaction de contraintes défini par le réseau de contraintes
suivant :
Appliquez l’arc-consistant sur ce problème. Qu’est ce que vous constatez.
constatez
La Queue Q Domaines Paire de variables
à ajouter dans Q
