Controle Session 1 [PDF]

Zitiervorschau

UNIVERSITE HASSAN II DE CASABLANCA Faculté des Sciences Ben M’Sick Département de Mathématiques et Informatique * Contrôle session 1 IA : Master DSBD Durée 1h30H //Année 2020-2021 Exercice 1 : (5 points) Soit les formules suivantes : A1 :x (P(x) y (R(y)  Q(x, y))) A2 : x P(x) C : x y Q(x, y) Nous voulons montrer que C est conséquence de A1 et A2 par instanciation et par résolution, pour cela on va montrer que A = A1 ∧ A2 ∧ ¬ C est une formule inconsistante. 1) Mettre A1 , A2 ¬ C en forme Prenex. 2) Mettre A1 , A2 ¬ C en forme Skolen. 3) Donner la FNC de A1 , A2 ¬ C et déduire l’ensemble F des clauses final obtenu. 5) Donner la signature de Herbrand de F, l’univers de Herbrand H0, et H 7) Donner le système de Herbrand S (les instances de F) associé à F sur H0 8) Prouver que S est inconsistant Exercice 2 : (5 points) Soit un système à base de connaissance dont la base initiale de faits est : {A, D, J, K, L} et les règles sont les suivantes. R1: A→B, R2: C, D →E, R3: B, F, G →H R4: A, L→ C, R5: D, E→ H, R6: C, D →I, R7: J, K→ F, R8: G, J, F → K On veut prouver le fait H par chaînage arrière en profondeurs d’abord. Donner à l’aide d’un graphe et/ou les étapes des règles essayées. On indiquera si chaque règle essayée a été un succès ou un échec. Exercice 3 : (5 points) Dans l’espace de recherche suivant, l’état S est l’état de départ et les états G1 et G2 sont des états qui satisfont le test de but. Le nombre au-dessus d’un arc représente le coût pour le parcourir. La valeur de la fonction heuristique h est inscrite dans le cercle. Pour chacune des méthodes de recherche suivantes : indiquez quel but est atteint et. 1) utilisez la méthode de recherche A* pour arriver à un des buts et donnez la liste, dans l’ordre, de tous les états qui ont été choisis pour être explorés. (utiliser un tableau pour cela). 2) L’heuristique donnée est-elle admissible ? Expliquez pourquoi.

1

Exercice 4: (5 points) Dans cette question nous allons résoudre un problème avec l’algorithme de Hill-Climbing. Le problème est représenté par un ensemble d’état ui i=1,… ,16. La fonction objective (qu’on veut maximiser) associée à chaque nœud est la suivante : u u1 u2 u3 u4 u5 u6 u7 u8 u9 u10 u11 u12 u13 u14 u15 u16 f(u) 4 6 15 2 3 2 4 5 6 7 8 10 9 8 7 3 a. Quelle est la solution de ce problème sachant que les voisins de ui sont définis par par ui-1 ui-2 et ui+1 ui+2 sauf pour u1 qui a u2 et u3 comme voisins et u16 qui a u14 u15 comme voisins. Expliciter les étapes de l’algorithme( utiliser un tableau y mettre les successeurs de l’état courant et le meilleur choisi). L’état initial choisi aléatoirement est u6. b. La solution trouvée est -elle optimale? Expliquer pourquoi.

Aide-mémoire Algorithme Hill Climbing : l’algorithme s’arrête lorsqu’on ne peut plus améliorer la solution.

Chainage arrière : La partie « conclusions » des règles est unifiée avec ce but. En cas de succès, les prémisses de la règle unifiée sont les nouveaux buts assignés. Puis à appliquer récursivement le même mécanisme aux faits contenus dans ces listes. Algorithme A*

2