Intelligence Artificielle AI - Prolog : TD 6 Prolog
Télécharger PDFMaster Informatique 1 – Module BIA – TD 6 Prolog
Nadia Kabachi, Damien Cram, Alain Mille
I. Manipulation de Listes
Soit L une liste.
1. Écrire un prédicat element, de deux manières : avec et sans le cut (!), permettant de savoir si X est un élément de la liste L. Expliquer la différence et tracer l’arbre de résolution correspondant.
2. Écrire un prédicat reverse permettant de renverser la liste L.
3. Écrire un prédicat compresser permettant de supprimer des doublons consécutifs dans une liste L pour obtenir une liste L1. Nota : L’ordre des éléments doit être respecté.
Exemple :
?- compresser([a,a,a,a,b,c,c,a,a,d,e,e,e,e],L1).
L1 = [a,b,c,a,d,e]II. Arbre Généalogique
Voici le programme Prolog décrivant un arbre généalogique :
homme(albert).
homme(marc).
homme(charles).
femme(sara).
pere(albert, marc).
pere(albert, charles).
pere(albert, sara).Définir les prédicats généraux suivants :
- enfant(X, Y) : exprime que X est un enfant de Y
- fils(X, Y) : exprime que X est un fils de Y
- fille(X, Y) : exprime que X est une fille de Y
- frere_ou_sœur(X, Y) : exprime que X est frère ou sœur de Y. Il est à noter qu’un individu n’est pas son propre frère ou sa propre sœur.
III. Coloriage d’une Carte
On se propose de définir un prédicat permettant de colorier une carte selon les règles suivantes :
- On dispose de trois couleurs : vert, jaune et rouge.
- Deux zones contiguës doivent avoir des couleurs différentes.
Écrire un prédicat coloriage(C1, C2, C3, C4) qui comportera deux parties :
- La première génère toutes les valeurs possibles de C1, C2, C3 et C4.
- La seconde vérifie si les colorations obtenues sont conformes à la carte.
Modifier ce prédicat en déplaçant les tests de différence de couleurs dès que celles-ci sont instanciées. Expliquer la conséquence.
FAQ
1. Comment écrire un prédicat element en Prolog sans utiliser le cut (!) ?
Voici une solution possible :
element(X, [X|_]).
element(X, [_|L]) :- element(X, L).2. Pourquoi le cut (!) améliore-t-il la performance du prédicat element ?
Le cut (!) évite de continuer à explorer des solutions alternatives après avoir trouvé la première occurrence de X. Cela réduit le nombre d’arbres de résolution et optimise l’exécution.
3. Comment vérifier la contiguïté des zones dans le prédicat coloriage ?
Les tests de contiguïté doivent être intégrés dès que les couleurs sont assignées pour éviter des calculs inutiles. Par exemple, si C1 et C2 sont contiguës, ajouter immédiatement C1 \= C2 dans la clause.