Fondements de l’IA
TP 2- Les Listes
Programmation Logique sous l’environnement SWI-
Prolog
Réalisé par : YASSINE AZGUIR
Filière : GSCSI
Encadré par : [Link]
Introduction:
Ce deuxième travail pratique est consacré à l'étude des listes, une structure de données
fondamentale en programmation logique. Nous allons explorer comment Prolog
manipule les listes, en mettant l'accent sur leur création, leur accès, leur modification et
leur utilisation dans des algorithmes plus complexes. À travers une série d'exercices,
nous découvrirons la puissance et la flexibilité de Prolog pour résoudre des problèmes
liés à la gestion de données structurées.
Objectif du TP :
L'objectif de ce TP est de vous familiariser avec la manipulation des listes en Prolog.
Vous apprendrez à :
Définir des listes et les représenter en Prolog.
Accéder aux éléments d'une liste à l'aide de la notation point-virgule.
Concaténer des listes pour former de nouvelles listes.
Implémenter des fonctions récursives pour effectuer des opérations sur les listes
(par exemple, calculer la longueur d'une liste, inverser une liste, rechercher un
élément dans une liste).
Utiliser les listes pour résoudre des problèmes plus complexes, tels que la
représentation d'arbres ou de graphes.
Exercice 1:
Définir les prédicats suivants :
1. Ecrire un prédicat vide(L) pour tester si la liste L est vide.
2. Définir le prédicat concat(L1,L2,L3), où L3 est le résultat de la concaténation de L1
et L2 (sans utiliser le prédicat prédéfini append).
3. Définir le prédicat longueur(L,N), qui étant donnée la liste L calcule sa longueur N.
4. Définir le prédicat indice(X,L,N), qui étant donnés un élément X et une liste L, X
appartenant à L, calcule N l’indice de la première occurrence de X dans L. Peut-on
utiliser ce prédicat pour formuler une requête permettant de calculer le ième élément
d’une liste ?
5.Écrire le prédicat remplace(X1,X2,L1,L2) qui construit la liste L2 qui est la liste L1
dans laquelle X1 est remplacé par X2.
[Link] un prédicat inserPos(X, P, L1, L2) qui permet d’insérer l’élément X à la
position P dans la première liste L1, le résultat est dans la deuxième liste L2.
[Link] un prédicat inverser(L1, L2) qui inverser la liste L1 pour trouver la liste L2.
[Link] un prédicat dernierElem(L, X), dont X est le dernier élément de la liste L.
[Link] un prédicat saisirListe(L, N) qui construit une liste L à partir d’une suite de N
éléments saisie au clavier. On demande deux versions : une insertion d’éléments dans
l’ordre de leur saisie, et une deuxième version dans le sens inverse.
[Link] un prrédicat nbOccur( X, L, N) qui calcule dans N le nombre d’occurrence
d’un élément X dans la liste L.
[Link] un prédicat supprimerAllOccur(X, L1, L2) qui supprime toute occurrence
d’un élément X dans une liste L1, le résultat dans la liste L2.
[Link] un prédicat supprimerPos ( X, P, L1, L2) qui supprime un élément X à la
position P d’une liste L1.
[Link] un prédicat rechercherPos(X, L, P) qui recherche de la position P d’un
élément X dans une liste.
14.Définir le prédicat partage(L,X,L1,L2), qui étant donnés une liste de nombre L et un
nombre X, calcule la liste L1 des nombres de L inférieurs à X, et la liste L2 des nombres
de L supérieurs ou égaux à X.
Exercice 2 :
le tri des listes
Version 1 : le tri par sélection
L’objectif de cet exercice est de trier une liste par sélection dont le principe est le
suivant :
− On cherche le minimum de la liste à trier
− On le met au début de la liste qu’on construit
− Puis on recommence avec la liste à trier privée du minimum
1. Définir minimum(L,X) qui calcule le minimum X de la liste L.
2. Définir le prédicat enleve(X,L1,L2), qui construit la liste L2, qui est la liste L1 à
laquelle on a enlevé la première occurrence de l’élément X
3. Définir le prédicat tri_min(L,Lt) qui construit la liste triée Lt à partir de la liste de
nombres L
4. Définir un prédicat fusion(L1,L2,L3) qui construit L3, la liste triée obtenue en faisant
la fusion des deux listes triées L1 et L2.
Exemple : fusion([1,3,5,7],[1,2,5,8,12],L3) → L3 = [1,2,3,5,7,8,12]
Version 2 : Le tri à bulles
1. Définir le prédicat bulle(L1,L2) qui construit la liste L2 qui est la liste L1 dans
laquelle l’élément le plus petit est remonté en première place.
2. Définir le prédicat tribulle(L1,L2) qui implémente le tri à bulles.
Conclusion :
