quand le programme vas faire "palindrome(T, Out_1)", nous somme bien d'accord il peut appeler soit palindrome([X],[X]). soit palindrome([H|T], Out) en fonction de ce qu'on a mis dans le prédicat ?
j'ai mis ma clause en dernier, es ce que l'ordre des clause a une importance (je pense que non, mais c'est juste pour etre sur)
"Quand on débute, on analyse mal les problèmes, et on conçoit des solutions inefficaces en partant dans de mauvaises directions. Et c'est normal, faut bien apprendre."
Comme je le comprend, prolog c'est un langage qui permet de générer des données facilement, par exemple :
je crée des familles en 2 lignes de code par exemple
Et avec ces données, je peut ensuite interroger prolog avec des prédicats que j'assimile à des "fonctions récursives", récursive quand on traite des listes (par exemple le prédicat palindrome qui boucle en re-appelalnt le palindrome)
Une "fonction récursive" en prolog est composé de IF (se sont les clauses)
Pour coder ces clauses faut jouer entre les appeles récursif et les listes par exemple en emputant le 1er terme de la liste comme dans palindrome :
palindrome([H|T], Out) :-
palindrome(T, Out_1),
je rappelle palindrome sans le 1er élément de ma liste
J'imagine qu'avec le temps et la pratique sa sera plus naturel cette méthode de programmation.
quand le programme vas faire "palindrome(T, Out_1)", nous somme bien d'accord il peut appeler soit palindrome([X],[X]). soit palindrome([H|T], Out) en fonction de ce qu'on a mis dans le prédicat ?
Oui.
Es ce faut si dans ton code je rajoute ceci :
1
2
3
4
5
palindrome([],[]).
palindrome([X],[X]).
palindrome([H|T], Out) :-
palindrome(T, Out_1),
append([H|Out_1], [H], Out).
j'ai rajouté une clause, car je veut que si mon prédicat recoit une liste vide, je retourne une liste vide. Es ce bien correcte ?
L'avantage de la programmation logique, c'est en principe qu'on peut écrire des choses logiques qui marchent et le prouver. Pas simplement aligner des clauses et décréter que ça marche, paske.
1. le prédicat p ci-dessous fait le boulot, avec l'aide d'un prédicat auxiliaire pc
Exemple : appeler p("abc", X) unifie X et "abcba".
2. il le fait en temps linéaire
---
La question, c'est "ptain ça marche quand je teste, mais d'où qu'il sort ce bordel ?".
Ben, pas compliqué, une astuce, et un peu de raisonnement rigoureux.
Idée de base : on regarde la fonction "gen" qui génère le palindrome obtenu à partir d'une liste en la concaténant avec son miroir sans le dernier élément. exemple : gen("abc") = "abcba".
On remarque qu'elle peut se définir (par pattern matching) par
gen ([X]) = [X]
gen ([X|L]) = [X] + gen(L) + [X] // + pour la concatenation
mais il y a un petit souci sur le temps d'exécution : aller coller un truc (le second +) au bout d'une liste, ça prend un temps proportionnel à la longueur de la liste, et comme c'est dans une récursion, on voit facilement que ça nous donne un temps quadratique O(n^2).
On utilise alors une astuce : le coup du paramètre tampon (accumulating parameter technique, in english). Puisque generer-puis-concatener coute cher, on fait les deux en même temps. C'est à dire qu'on définit une fonction auxiliaire qui fait
aux(U,V) = gen(U) + V
ce qui permettra aussi de (re)définir gen à partir de aux, parce que
gen(U) = gen(U) + []
= aux(U,[])
Revenons à aux. Avec un peu de calcul, on l'exprime récursivement parce que
aux([X], V) = gen([X]) + V // par définition de aux
= [X] + V // par définition de gen([X])
= [X|V]
et que
aux( [X|U], V ) = gen([X|U]) + V // def de aux
= ([X] + gen(U) + [X]) + V
= [X] + gen(U) + ([X] + V) // assoc. de +
= [X] + aux(U, [X] + V) // def de aux
= [X | aux(U, [X|V]) ]
Après ça, il est assez facile de voir la correspondance entre la définition récursive de gen/aux (qui a été prouvée rigoureusement avec des calculs algébriques simples) et les clauses de p/pc
Equations Clauses
------------------------------------ -------------------------------------
gen ( L ) = aux(L, []) p(L,P) :- pc(L,[],P).
aux ( [X], V) = [X|V] pc([X], V, [X|V]).
aux ( [X|U], V) = [X | aux(U,[X|V])] pc([X|U], V, [X|W]) :- pc(U,[X|V],W).
Programmation logique, fonctionnelle, équationelle... comme le monde est petit....
(remarque : avec un peu d'habitude, on fait facilement le calcul de tête. Mais là, j'explique aux gens).
2. Le temps linéaire, dans les 2 sens d'utilisation
- Si le premier parametre de pc est fourni (pas une variable libre), il en est de même pour celui de pc, et le schéma de récursion
pc([X], ....).
pc([X|U], ....) :- pc(U,[....]).
fait que ça décroit bien en perdant un elément à chaque fois.
- Même raisonnement si c'est le second qui est lié
pc(.... [X|V]).
pc(.... [X|W]) :- pc( ....,W).
elle est pas belle, la vie ?
- Edité par michelbillaud 12 novembre 2017 à 20:03:58
en général, si le predicat fournit une liste finie de solutions, et qu'il n'y a pas de cut dedans, ça fournira les mêmes solutions. Dans un ordre différent, mais là, c'est déterministe, il y a une solution ou pas, mais jamais plusieurs.
Un problème moins déterministe, et plus typique des raisons d'employer prolog (backtracking), ça serait de voir les différentes manières de faire chevaucher une liste et son miroir pour obtenir un palindrome. Par exemple, en partant de "abcb", les solutions seraient "abcbbcba" (partie commune vide), "abcbcba" (chevauchement "b"), et "abcba" ("bcb").
Ca demande un peu plus de réflexion.
- Edité par michelbillaud 13 novembre 2017 à 13:41:18
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Le crayon la gomme et le papier sont les meilleurs outils du programmeur !