Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Prolog et Fibonacci par Trap D Date de publication : 10/08/2008 Dernière mise à

Prolog et Fibonacci par Trap D Date de publication : 10/08/2008 Dernière mise à jour : Cet article est destiné à montrer les possibilités de Prolog pour envisager le calcul des nombres de Fibonacci. D'abord les algorithmes classiques sont montrés. Ensuite d'autres méthodes sont évoquées, "mémoïsation", streams en liaison avec les "Open Lists", enfin les "DCG". Prolog et Fibonacci par Trap D - 2 - http://jfoutelet.developpez.com/ I - Les algorithmes classiques.................................................................................................................................... 3 I-A - Un petit rappel historique.............................................................................................................................. 3 I-B - La définition mathématique de la suite......................................................................................................... 3 I-C - Les algorithmes de base...............................................................................................................................3 I-C-1 - L'algorithme naïf................................................................................................................................... 3 I-C-2 - L'algorithme itératif................................................................................................................................3 I-D - Implémentation Prolog des algorithmes de base..........................................................................................4 I-D-1 - L'algorithme naïf................................................................................................................................... 4 I-D-2 - L'algorithme itératif................................................................................................................................4 I-E - Conclusion..................................................................................................................................................... 5 II - Utilisation de la mémoïsation................................................................................................................................ 6 II-A - Qu'est-ce que la mémoïsation ?...................................................................................................................6 II-B - Une première méthode de mémoïsation......................................................................................................7 II-C - Une seconde méthode de mémoïsation...................................................................................................... 8 III - Utilisation des "Open Lists"..................................................................................................................................9 III-A - Que sont les Open Lists ?.......................................................................................................................... 9 III-B - Simulation d'un stream par une Open List..................................................................................................9 III-C - Le calcul des nombres de Fibonacci avec les Open Lists et les streams.................................................10 IV - Utilisation des DCG............................................................................................................................................11 IV-A - Exemple de DCG......................................................................................................................................11 IV-B - La version naïve en DCG......................................................................................................................... 12 IV-C - Une méthode itérative de calcul des nombres de Fibonacci avec les DCG.............................................12 IV-C-1 - Amélioration de la méthode............................................................................................................. 13 IV-D - Le calcul des nombres de Fibonacci avec mémorisation des résultats....................................................13 IV-D-1 - Le mécanisme des différences de listes..........................................................................................13 IV-D-2 - Le calcul des nombres de Fibonacci avec mémorisation.................................................................14 IV-E - Le calcul des nombres de Fibonacci avec mémoïsation.......................................................................... 15 V - Conclusion...........................................................................................................................................................17 VI - Téléchargements................................................................................................................................................19 VII - Remerciements................................................................................................................................................. 20 Prolog et Fibonacci par Trap D - 3 - http://jfoutelet.developpez.com/ I - Les algorithmes classiques. I-A - Un petit rappel historique. Ce rappel est extrait d'un article de Wilkipedia La suite de Fibonacci est l'une des suites mathématiques les plus connues. Elle doit son nom au mathématicien italien Leonardo Pisano, plus connu sous le pseudonyme de Fibonacci (1175 - 1250). Dans un problème récréatif posé dans un de ses ouvrages, le Liber Abaci, Fibonacci décrit la croissance d'une population de lapins : « Possédant initialement un couple de lapins, combien de couples obtient-on en douze mois si chaque couple engendre tous les mois un nouveau couple à compter du second mois de son existence ? » Ce problème est à l'origine de la suite dont le -ème terme correspond au nombre de paires de lapins au -ème mois. Dans cette population (idéale), on suppose que : • le premier mois, il y a juste une paire de lapereaux ; • les lapereaux ne sont pubères qu'à partir du deuxième mois ; • chaque mois, toute paire susceptible de procréer engendre effectivement une nouvelle paire de lapereaux ; • les lapins ne meurent jamais (donc la suite de Fibonacci est strictement croissante). I-B - La définition mathématique de la suite. Mathématiques fibonacci(n) = n si n < 2 fibonacci(n) = fibonacci(n-1)+fibonacci(n-2) I-C - Les algorithmes de base. Dans cette section, nous abordons les deux algorithmes de base, le premier récursif particulièrement inefficace, et le second itératif, très performant. I-C-1 - L'algorithme naïf. Le premier algorithme de calcul dérive directement de la définition mathématique : Algorithme fonction Fibonacci_naive(n : entier) : entier variable retour : entier début si n < 2 alors retour <- n sinon retour <- Fibonacci_naive(n-1) + Fibonacci_naive(n-2) fin si retourner retour fin I-C-2 - L'algorithme itératif. Bien évidement, une version itérative nettement plus efficace a été élaborée. Elle se base sur la construction du nombre à partir de 0 et 1, un nombre de la suite étant la somme des deux nombres le précédant. Algorithme fonction Fibonacci_iter(n : entier) : entier variable compteur, val1, val2, val3, retour : entier debut Prolog et Fibonacci par Trap D - 4 - http://jfoutelet.developpez.com/ Algorithme si n < 2 alors retour <- n sinon val1 <- 0 val2 <- 1 pour compteur de 2 à n par pas de 1 faire val3 <- val1 + val2 val1 <- val2 val2 <- val3 fin pour retour <- val2 fin si retourner retour fin I-D - Implémentation Prolog des algorithmes de base. I-D-1 - L'algorithme naïf. Les fonctions n'existant pas en Prolog, on utilisera un prédicat naive_fib/2 le premier étant l'indice du second dans la suite des nombres de Fibonacci. Prolog naive_fib(X, X) :- X < 2, !. naive_fib(X, Y) :- Idx1 is X - 1, Idx2 is X - 2, naive_fib(Idx1, A), naive_fib(Idx2, B), Y is A + B. Cette version n'est pas très performante, on obtient ce résultat pour le calcul de Fibonacci(40) : Console Prolog 14 ?- time(naive_fib(40,N)). % 1,159,060,982 inferences, 340.16 CPU in 362.57 seconds (94% CPU, 3407437 Lips) N = 102334155 ; soit plus de 1 100 000 000 inférences et plus de 5 minutes 40 secondes pour calculer Fibonacci(40) ! I-D-2 - L'algorithme itératif. La boucle pour de l'algorithme est remplacée par un appel récursif terminal. Le prédicat posséde 4 arguments. L'indice de boucle est décrémenté à partir de N pour pouvoir arrêter la boucle à 1 et éviter ainsi un cinquième argument, le maximum de l'indice de boucle. Prolog fib_iter(N, F) :- % si N est plus petit que 2, pas de calcul N < 2 -> F = N ; % Sinon il est lancé fib_iter_cal(0, 1, N, F). % arg1 : l'avant dernier calcul % arg2 : le dernier calcul % arg3 : Indice de boucle de calcul en cours (arrêt à 1) % arg4 : résultat final fib_iter_cal(_F, F, 1, F) :- !. fib_iter_cal(TT1, TT2, N, F) :- Prolog et Fibonacci par Trap D - 5 - http://jfoutelet.developpez.com/ Prolog TT3 is TT1 + TT2, N1 is N - 1, fib_iter_cal(TT2, TT3, N1, F). Ce code est nettement plus performant : Console Prolog time(fib_iter(100000, N)). % 299,999 inferences, 0.67 CPU in 1.15 seconds (58% CPU, 446510 Lips) Je vous épargne le résultat, il s'écrit avec 20 900 chiffres ! I-E - Conclusion. Bien évidemment, l'algorithme itératif est nettement plus performant que l'algorithme naïf. Aucune autre méthode ne peut faire mieux en Prolog. Cependant, la puissance d'expression du langage permet d'utiliser d'autres concepts pour le calcul. Ces concepts sont exposés dans les chapitres suivants. Prolog et Fibonacci par Trap D - 6 - http://jfoutelet.developpez.com/ II - Utilisation de la mémoïsation. II-A - Qu'est-ce que la mémoïsation ? Observons le développement du calcul de Fibonacci(5), les calculs les plus à gauches sont effectués en premier. Graphe de calcul de Fibonacci(5) fib(5) | _________________________________+______________________________ fib(4) fib(3) | | __________________+__________________ _________ +___________ fib(3) fib(2) fib(2) fib(1) = 1 | | | _________+___________ _____________+_____________ ____________+____________ fib(2) fib(1) = 1 fib(1) = 1 fib(0) = 0 fib(1) = 1 fib(0) = 0 | ____________+____________ fib(1) = 1 fib(0) = 0 On constate que de nombreux calculs sont répétés inutilement, et si on peut les mémoriser, un important gain de temps est effectué. Cette technique s'appelle la mémoïsation, dès qu'un résultat est connu, il est mémorisé pour pouvoir être récupéré plus tard. Observons ce que celà donne, mémo indique que le résultat est mémorisé. Graphe de calcul de Fibonacci(5) fib(5) | _________________________________+_________________________________ fib(4) mémo fib(3)= 2 | __________________+___________________ fib(3) mémo fib(2)= 1 | _________+_______________ fib(2) mémo fib(1) = 1 | ____________+____________ fib(1) = 1 fib(0) = 0 Dans le calcul, on devra s'assurer d'abord que le résultat n'est pas déjà connu, et s'il ne l'est pas, le calculer et le mémoriser. On obtient cet algo : Algorithme fonction fibonacci_memo(N : entier) : entier variable retour : entier variable existe : booleen début existe <- existence de Fibonacci(N) dans la base de données si existe = vrai alors retour <- Fibonacci(N) sinon retour <- fibonacci_memo(N-1) + fibonacci_memo(N-2) // Maintenant Fibonacci(N) est connu, il faut l'enregistrer dans la base de données memoriser le couple (N, Fibonacci(N)) fin si retourner retour Prolog et Fibonacci par Trap D - 7 - http://jfoutelet.developpez.com/ Algorithme fin II-B - Une première méthode de mémoïsation. Prolog possède un mécanisme très simple de mémorisation, les prédicats dynamiques qui permettent d'ajouter "à runtime" des faits dans la base de données Prolog. On peut le faire par l'intermédiaire de 3 prédicats : assert/1, asserta/1 et assertz/1 (mais qui est équivalent à assert/1). Un petit exemple permet de mieux comprendre : Prolog % déclaration des prédicats dynamiques (nom/arité) :- dynamic pred1/2, pred2/2. test :- % insertion normale dans la base de données assert(pred1(0,0)), assert(pred1(2,4)), assert(pred1(3,5)), % insertion en tête de base de données asserta(pred2(0,0)), asserta(pred2(2,4)), asserta(pred2(3,5)). On obtient, entre autres, le contenu de la base de données Prolog par le prédicat listing/0. Après avoir enlevé certains renseignements ici inutiles, on obtient comme résultat : Console Prolog 5 ?- listing. :- dynamic pred1/2. pred1(0, 0). pred1(2, 4). pred1(3, 5). :- dynamic pred2/2. pred2(3, 5). pred2(2, 4). pred2(0, 0). Yes On constate bien que les couples pred2 sont mémorisés dans l'ordre inverse de l'insertion dans la base de données. Cependant, il n'y a aucune différence au point de vue temps d'accès entre les deux uploads/Litterature/fibonacci.pdf