Intelligence Artificielle AI - Prolog : TP 3 Les Listes
Télécharger PDFLes Listes en Prolog avec SWI-Prolog
Prolog permet de définir et manipuler des listes d'éléments de même type. Une variable de type liste peut être gérée dynamiquement pour effectuer diverses opérations : affichage, ajout, suppression, etc. Deux syntaxes principales existent pour représenter une liste.
Syntaxe 1 : Notation d'une constante liste
La syntaxe est la suivante : [e1, e2, ..., en], où les ei sont les éléments de la liste. Voici quelques exemples :
- Liste vide :
L1 = [] - Liste de caractères :
L2 = ['a', 'b', 'c'] - Liste de chaînes de caractères :
L3 = [ali, driss, hamid] - Liste de listes :
L4 = [ [ali, driss], [petit, grand], [blond] ] - Liste d'objets composés (exemple : liste de voitures) :
L5 = [voiture("Peugeot 406", "blanche"), voiture("Renault 19", "rouge")]
Syntaxe 2 : Écriture récursive d'une liste
Une liste peut être écrite sous la forme récursive : [e | Q], où e est l'élément en tête de la liste et Q est le reste des éléments. Exemple : [rouge | [vert, bleu]].
Manipulations récursives de base
Affichage des éléments d'une liste
Prédicat : afficher(L), où L est une liste.
afficher([]). afficher([X | L]) :- write(X), nl, afficher(L).
Exemple : ?- afficher([rouge, vert, bleu]).
Recherche d'un élément dans une liste
Prédicat : appartient(X, L), où X est l'élément à chercher dans la liste L.
appartient(X, [X | _]). appartient(X, [_ | L]) :- appartient(X, L).
Exemple : ?- appartient(vert, [rouge, vert, bleu]).
Insertion en tête
Prédicat : empiler(X, L1, L2), où X est l'élément à insérer en tête de la liste L1.
empiler(X, L, [X | L]).
Exemple : ?- empiler(jaune, [rouge, vert, bleu], L).
Suppression de la tête
Prédicat : dépiler(L1, L2), où L1 est la liste initiale et L2 est la liste sans le premier élément.
dépiler([], []). dépiler([_ | L], L).
Exemple : ?- dépiler([rouge, vert, bleu], L).
Insertion en queue
Prédicat : enfiler(X, L1, L2), où X est l'élément à insérer en queue de la liste L1.
enfiler(X, [], [X]). enfiler(X, [Y | L1], [Y | L2]) :- enfiler(X, L1, L2).
Exemple : ?- enfiler(jaune, [rouge, vert, bleu], L).
Suppression de la queue
Prédicat : défiler(L1, L2), où L1 est la liste initiale et L2 est la liste sans le dernier élément.
défiler([_], []). défiler([X | L1], [X | L2]) :- défiler(L1, L2).
Exemple : ?- défiler([rouge, vert, bleu], L).
Exercices sur les listes
Exercice 1 : Prédicats de base sur les listes
Définir les prédicats suivants :
vide(L): Teste si la listeLest vide.concat(L1, L2, L3): Concatène les listesL1etL2pour obtenirL3(sans utiliserappend).longueur(L, N): Calcule la longueurNde la listeL.indice(X, L, N): Calcule l'indiceNde la première occurrence deXdansL. Peut-on utiliser ce prédicat pour trouver leième élément d'une liste ?remplace(X1, X2, L1, L2): Remplace toutes les occurrences deX1parX2dans la listeL1pour obtenirL2.inserPos(X, P, L1, L2): Insère l'élémentXà la positionPdans la listeL1pour obtenirL2.inverser(L1, L2): Inverse la listeL1pour obtenirL2.dernierElem(L, X): Trouve le dernier élémentXde la listeL.saisirListe(L, N): Construit une listeLà partir deNéléments saisis au clavier. Deux versions sont demandées : insertion dans l'ordre et insertion en sens inverse.nbOccur(X, L, N): Calcule le nombre d'occurrencesNde l'élémentXdans la listeL.supprimerAllOccur(X, L1, L2): Supprime toutes les occurrences deXdans la listeL1pour obtenirL2.supprimerPos(X, P, L1, L2): Supprime l'élémentXà la positionPdans la listeL1pour obtenirL2.rechercherPos(X, L, P): Trouve la positionPde l'élémentXdans la listeL.partage(L, X, L1, L2): Divise la listeLen deux listes :L1contient les éléments inférieurs àX, etL2contient les éléments supérieurs ou égaux àX.
Exercice 2 : Tri des listes
Version 1 : Tri par sélection
minimum(L, X): Calcule le minimumXde la listeL.enleve(X, L1, L2): Construit la listeL2en supprimant la première occurrence deXdeL1.tri_min(L, Lt): Trie la listeLpar sélection pour obtenirLt.fusion(L1, L2, L3): Fusionne deux listes triéesL1etL2pour obtenirL3.
Version 2 : Tri à bulles
bulle(L1, L2): Construit la listeL2en remontant le plus petit élément en première position dansL1.tribulle(L1, L2): Implémente le tri à bulles pour obtenirL2.
FAQ
1. Comment tester si une liste est vide en Prolog ?
Utilisez le prédicat vide(L) en vérifiant si L est égal à [].
2. Peut-on trouver le ième élément d'une liste avec le prédicat indice ?
Non, le prédicat indice calcule la position de la première occurrence d'un élément. Pour trouver le ième élément, il faut utiliser une approche différente.
3. Quelle est la différence entre empiler et enfiler ?
empiler ajoute un élément au début de la liste, tandis que enfiler ajoute un élément à la fin de la liste.