Module 04 - Program Mat Ion Logique

Programmation logique

Campus-Booster ID : XXX

www.supinfo.com Copyright © SUPINFO.

All rights reserved

Programmation logique

Votre formateur… Titre: Professeur Référent en IA Distinctions & expérience: Enseignement et recherche en Intelligence Artificielle, Informatique et Electronique. Participation à des congrès internationaux en Intelligence Artificielle Formation: Doctorat en Intelligence Artificielle. Ingénieur en télécommunications. Publications: 60 articles, communications et livres dont 48 sur l’IA

Marianne Belis

Contact: [email protected] SUPINFONE: 1 317

Programmation logique

Votre formateur… Titre: Professeur Référent en Algorithmique, Théorie des Graphes et Intelligence Artificielle. Distinction: Mastaire en Recherche Opérationnelle et Intelligence Artificielle. Formation: Ingénieur en Informatique, Conception et Développement, (modélisation, optimisation, simulation, complexité et algorithmique). Qualifié en Gestion des Risques (spécialisé en modélisation et Systèmes d'Information)

Arnaud CUEILLE

Publication: « La simulation des flux de transports de marchandises en agglomération » (2002). Contact: [email protected] SUPINFONE: 1 50087

Programmation logique

Objectifs de ce module En suivant ce module vous allez:  Aborder la programmation logique, déclarative.

 Comprendre les mécanismes fondamentaux de Prolog.

 Tester des programmes avancés écrits en SWI-PROLOG.

Programmation logique

Plan du module Voici les parties que nous allons aborder:

 Eléments de base

 Spécificités et mécanismes fondamentaux

 Récursivité et listes

 Applications

Eléments de base

Plan de la partie Voici les chapitres que nous allons aborder:  Généralités  Structure du programme  Les termes  L’arithmétique  Les entrés/sorties  Utilisation de SWI Prolog

Eléments de base

Généralités PROLOG (PROgrammation en LOGique) Langage déclaratif fondé sur la logique du premier ordre (calcul des prédicats) - Alain Colmerauer Marseille -1972. - W.F.Clocksin and C.S.Mellish: programming in Prolog 1981

Eléments de base

Généralités

 Outil de base en intelligence artificielle grâce :

- à sa puissance déductive - à l’utilisation des variables - au mécanisme de la remontée qui permet de chercher toutes les solutions existantes.

Eléments de base

Généralités  Ses applications pratiques sont nombreuses. Il peut :

 contrôler des processus industriels,  traduire un langage en un autre,  construire des systèmes expert,  démontrer des théorèmes, etc …

Eléments de base

Structure du programme

Un programme est constitué de clauses: FAITS et REGLES qui sont déclarés dans la BASE DE DONNEES (ou base de connaissances)

Eléments de base

Structure du programme  LES FAITS Un fait est une vérité non conditionnée.

Exemples :  blanche (maison). --> (la maison est blanche)  aime (jean, prolog). --> (Jean aime le prolog)  voiture (ford, rouge, 3, 5.000). --> (la voiture est une ford rouge de trois ans et coûte 5.000 euros)

Eléments de base

Structure du programme LES REGLES  Une règle est une vérité conditionnée.  Règle à une seule condition :  La règle est formée d'une tête (la conclusion) et d'un corps (la condition).  La conclusion est prouvée si la condition est vraie.  Exemple :

achète(jean, voiture) if gagne(jean, loterie).

Eléments de base

Structure du programme Règles à plusieurs conditions  Les conditions sont liées par la conjonction « and » : relation (objet, objet) if relation (objet, objet) and relation (objet, objet) and relation (objet, objet).

Exemple :

grand-père(jean, yves) :père(jean, paul) and père(paul, yves).

Eléments de base

Structure du programme

 La conclusion est prouvée si toutes les conditions sont vraies.

 Pour prouver une condition on cherche à l’unifier* - soit avec un fait de la base de données - soit avec une tête de règle (chaînage arrière)**

Eléments de base

Structure du programme Plusieurs règles ayant la même conclusion (paquet de clauses).  Exemple: achète(jean, voiture) :- hérite(jean, fortune). achète(jean, voiture) :- gagne(jean, loterie).

Cela peut s’écrire aussi: achète(jean voiture) :- hérite(jean, fortune) OU gagne(jean, loterie).

Eléments de base

Structure du programme  Ensemble de clauses qui ont la même conclusion (la même tête de clause) :  a (X) : - b (X,Y).  a (X) : - c (X), e (X).  a (X) : - f (X,S).

Cela peut s’écrire aussi:  a (X) :- b (X,Y ); c (X) , e (X) ; f (X,S). (; => « OU »)

Eléments de base

Structure du programme Paquet de clauses (suite)  Les clauses ayant la même tête sont liées par « or »  Les conditions d'une clause sont liées par « and »  Chaque clause est une solution du problème.  L'ordre des clauses est sans importance.  Prolog les traite une à une dans l'ordre d'écriture.  Si une seule est vraie --> VRAI  Si toutes sont fausses --> FAUX

Eléments de base

Structure du programme Conventions d'écriture.  La programmation en Prolog implique les normes suivantes :

 Les clauses de même prédicat sont groupées ensemble  Les clauses sont parcourues de haut en bas  Toute clause (fait ou règle) se termine par un point  Dans l’écriture courante on préfère les notations:  or ≡ ;  and ≡ ,  if ≡ :-

Eléments de base

Les termes  Prolog comprend quatre types de termes:

- les atomes - les nombres - les variables - les termes complexes

Eléments de base

Les termes  Représentation arborescente des termes: termes termes simples

variables

termes complexes

constantes

atomes

nombres

Eléments de base

Les termes  Les caractères qui composent les termes sont:

- les majuscules:

A, B, ..., Z;

- les minuscules:

a, b, ..., z;

- les digits:

1, 2, ..., 9;

- les caractères spéciaux: +, -, *, /, <, >, =, :, ., &, ~, _.

Eléments de base

Les termes  Les atomes :  suite continue de caractères qui commencent par une minuscule (pas de blancs)  suite de caractères entre apostrophes (si les symboles contiennent des blancs ou des majuscules au début).  suite de caractères spéciaux élève ticket_de_métro  Exemples d’atomes ‘ticket de métro’ ‘Jean est sportif’ @+:>:-

:

Eléments de base

Les termes  Les nombres  Entiers (tout nombre entier)  Flottants (les nombres décimaux)

Ce sont surtout les entiers qui vont être utilisés par la suite.

Eléments de base

Les termes  Les variables: Suite de caractères commençant par - une majuscule - par un tiret-bas (underscore)

Exemples: X, _4156, Jean, MoDem, _jean,

Eléments de base

Les termes  Les termes complexes (structures) se composent: - d’un foncteur (le prédicat en logique) - d’un ou plusieurs arguments - le nombre d’arguments = arité

Exemple: aime(jean, prolog) aime= foncteur ; jean, prolog = arguments

Eléments de base

Les termes  Termes complexes (imbriqués): Exemple: possède(X, comptebancaire(5000)). possède = foncteur à deux arguments: - la variable X - le terme complexe « comptebancaire(5000) » comptebancaire = foncteur à un argument

Eléments de base

Les termes  Prédicats de comparaison de termes: == et \==  Exemples: ?- a == a.

 Yes

?- a == b.  No ?- a \== b.  Yes ?- 5 == 5.  Yes ?- 3+2 == 4+1.  No ?- f(a, b) == f(a, b).  Yes

%n’évalue pas ses arguments

Eléments de base

L’arithmétique En Prolog les symboles:

+, -, *, /, mod

ne permettent pas d’effectuer des calculs. Ce sont des foncteurs avec des arguments. Ex:

?- X = +(3, 5).

% ou bien X = 3 + 5. (plus habituel)

Réponse: X = 3 + 5 La variable X a été liée à l’expression non évaluée ?- 5+7*3 = X. Réponse: X = 5+7*3

Eléments de base

L’arithmétique  Pour calculer il faut utiliser l‘opérateur « is » *

?- X is 3 + 4.  X =7 ?- X is 5 – 2.  X = 3 ?- X is 9*2.

 X = 18

?- X is 11/2.  X = 5.5 ?- X is mod(5,2).  X = 1 ?- 1 is mod(5,2).  yes

Eléments de base

L’arithmétique  Prolog connaît la priorité des opérations:  ?- X is (3 + 5) + 4.  12  ?- X is 3 + 5 * 4.

 23

 ?- X is (3 + 5) + 4 * (9 - 6) / 3.

 12

 On peut utiliser aussi des prédicats:  calculer(X, Y) :- Y is (X+2)*(X+1).  ?- calculer(3, Y).  Y = 20

Eléments de base

L’arithmétique  Les opérateurs de comparaison d’entiers sont:

 <

 inférieur à

 <=

 inférieur ou égal à

 >

 supérieur à

 >=

 supérieur ou égal à

 =:=

 (yes si égalité)

 =\=

 (yes si différents)

Eléments de base

L’arithmétique  Exemple de comparaisons: ?- 3+2 < 9.  Yes ?- 2+2=:=1+3 ?- 5 =< 5.

 Yes*

 Yes

?- 2 =\= 9.  Yes ?- X = 5, X > 12.  No ?- X > 6.

 erreur: arguments non instanciés

Eléments de base

L’arithmétique  Tableau des différents prédicats à deux arguments  =

prédicat d’unification (unifie ses arguments)

 \=

échoue si l’unification ne réussit pas

 ==

prédicat d’identité (compare tous les types de

termes mais n’évalue pas ses arguments)

 \==

la négation du prédicat d’identité

 =:=

prédicat d’égalité arithmétique (réussit si les

arguments sont évalués à des entiers identiques)

 =/=

prédicat d’inégalité arithmétique

Eléments de base

Les entrées - sorties  PREDICATS D'ECRITURE

 Le prédéfini write/1 écrit à l’écran  Exemples:

?- X=a, write(X).  a ?- write(a), write(‘ ‘), write(b).  a b

(un espace blanc)

?- write(a), tab(6), write(b).  a

(six espaces blancs)

?- write(a), nl, write(b).  a b

b

(saut de ligne)

Eléments de base

Les entrées - sorties  writef( ‘chaîne’, liste d’arguments) – produit une sortie formatée.

Exemples: ?- writef(‘ %w est le père de %w ’, [jules, jim]). Affiche: jules est le père de jim ?- writef('%w\n%w%5c', [tableau,a, b]). Affiche: tableau a

b

Eléments de base

Les entrées - sorties  PREDICATS DE LECTURE :  read(Term).  Lit le caractère du flux d’entrée courant et l’unifie avec « Term ».  Exemple: question(X,Y):- writef('%w est-il le père de %w ?\n', [tom, jim]), read(Réponse), writef('%w %w est bien le père de %w', [Réponse, tom, jim]).

Eléments de base

Utilisation de SWI Prolog  Pour installer SWI-Prolog aller à: http://www.swi-prolog.org/  Consult( nom fichier).  charge le fichier et le compile  Après le prompt « ?- » on peut poser des questions  Toutes les questions finissent par un point.  Pour obtenir toutes les réponses (suite à la remontée), tapez ENTER ou bien « ; ».  Tous les prédicats commencent avec une minuscule.

 Ne laissez pas un blanc après un prédicat.  Après une parenthèse, des blancs et des lignes sont admises  Fermez autant de parenthèses que vous avez ouvertes.

Eléments de base

Utilisation de SWI Prolog  ?- listing.  affiche les clauses du programme ou le contenu de la base de données dynamiques  ?- listing(nom du prédicat).  affiche les clauses du prédicat  ?- trace. active la commande « pas à pas » sur le programme qui va être lancé  ?- trace(nom du prédicat). s’applique sur le prédicat  ?- notrace.  désactive le trace  ?- help.  explications générales  ?- help(sujet).  explications sur le sujet

Eléments de base

Pause-réflexion sur cette 1ère partie Avez-vous des questions ?

Programmation logique

Spécificités et mécanismes fondamentaux

Spécificités et mécanismes fondamentaux

Plan de la partie Voici les chapitres que nous allons aborder:  L’unification  Interrogation de la base de données  La remontée  Les prédéfinis FAIL et CUT  Paquet de clauses  La négation  Bases de données dynamiques  Le mode TRACE  Le prédéfini FINDALL

Spécificités et mécanismes fondamentaux

L’unification L’utilisateur pose des QUESTIONS Prolog RAISONNE En cherchant à unifier les questions aux données de la base de données (faits et règles)

Spécificités et mécanismes fondamentaux

L’unification  Les règles de l’unification: - Une variable libre est unifiable à n’importe quel terme - Une constante (atome ou entier) est unifiable à ellemême - Deux termes complexes sont unifiables si: - même foncteur - même nombre d’arguments (même arité) - les arguments correspondants sont unifiables

Spécificités et mécanismes fondamentaux

L’unification  Exemples d’unification  ami(jean, X) s’unifie avec ami(jean, tom) en liant X = tom  ami(jean, tom) ne s’unifie pas avec ami(tom, jean)  ami(jean, X) ne s’unifie pas avec ami(X, tom) (la même variable ne peut pas être liée à deux valeurs différentes)  f(a(4), plus(3,9)) s’unifie avec f(X,Y) et retourne: X = a(4) et Y = plus(3,9)  ?- a(b, X) = a(b, c(Y, e)), Y = hello. X = c(hello, e)

Y = hello

Spécificités et mécanismes fondamentaux

L’unification  Le prédicat « = » est utilisé pour l’unification  C’est un prédicat à deux arguments: =/2 (arité 2) qui teste si ses deux arguments s’unifient.  Exemples: ?- =(a, a).  Yes

(un atome s’unifie à lui même)

?- a = a.

 Yes

(expression infixée courante)

?- 5 = 5.

 Yes

?- ‘ 5 ’ = 5.  No* ?- ‘tom’ = tom.  Yes**

Spécificités et mécanismes fondamentaux

L’unification  Exemples d’unification (suite)

?- X = Y.  X = Y ?- toto = X.  X = toto (la variable est instanciée) ?- f(m(g), Z) = f(Y, s(m)).  Y = m(g)

Z = s(m)

(les foncteurs sont égaux et les arguments s’unifient)

Spécificités et mécanismes fondamentaux

Interrogation de la BDD  Questions (buts) élémentaires

 Structure de la question:  même syntaxe qu'un fait.  Prolog cherche à unifier la question avec un fait.  Réponse :  yes: l'unification a lieu (même prédicat et mêmes arguments dans le même ordre).  no : l'unification n'a pas lieu.

Spécificités et mécanismes fondamentaux

Interrogation de la BDD Unification avec un fait (les faits de la diapo 11):  -? aime(jean, prolog).

% jean aime-t-il le prolog?

 Prolog répond: yes

 -? blanche(maison).

-> yes

 -? blanche(voiture). -> no

Spécificités et mécanismes fondamentaux

Interrogation de la BDD  Unification avec une tête de règle:

gagne(jean, loterie). achète(jean, voiture) :- gagne(jean, loterie). -? achète(jean, voiture).

% la question

yes

% la réponse

Spécificités et mécanismes fondamentaux

Interrogation de la BDD Règle à plusieurs conditions

père(jean, paul). père(paul, yves). grand-père(jean, yves) :père(jean, paul), père(paul, yves).

?- grand-père(jean, yves). yes

Spécificités et mécanismes fondamentaux

Interrogation de la BDD  Questions (buts) multiples

Prolog cherche à unifier successivement chacun des buts avec un des faits de la base de faits. Les buts sont traités de gauche à droite. La base de faits est explorée de haut en bas.

Spécificités et mécanismes fondamentaux

Interrogation de la BDD  Exemple de questions multiples : clauses: a_écrit (hugo, ruy-blas). a_écrit (hugo, hernani). questions: ?a_écrit(hugo, hernani), a_écrit (hugo, ruy-blas).

 Chaque but est unifié avec une des clauses  Réponse : yes

Spécificités et mécanismes fondamentaux

Interrogation de la BDD  Questions avec des variables

 X = variable qui peut prendre diverses valeurs Exemple : clauses: a_écrit (hugo, hernani). a_écrit (hugo, ruy-blas). question: ?a_écrit (hugo, X). % qu’est-ce qu’il a écrit V.H?

 Réponse: X=hernani

X=ruy-blas

Spécificités et mécanismes fondamentaux

Interrogation de la BDD  Questions multiples et utilisation de variables.

 Exemple :

clauses: a_écrit (hugo, hernani). a_écrit (hugo, ruy-blas). Question: ?a_écrit (X, hernani), a_écrit (X, ruy-blas).

 Quel est l’auteur commun de hernani et de ruy-blas ?  X = hugo

Spécificités et mécanismes fondamentaux

Interrogation de la BDD Détail sur l'unification.  Première étape :  Prolog cherche à instancier X de la première question :  a_écrit (X, hernani) --> il lie X à hugo.  Deuxième étape :  Prolog « remonte » avec X=hugo et cherche un fait qui s'unifie avec : a_écrit (hugo, ruy-blas).  il trouve --> affiche : X = hugo

Spécificités et mécanismes fondamentaux

La remontée  Procédé de recherche par « retour en arrière » (backtracking) : clauses ami (jacques, yves). ami (jean, yves). ami (pierre, luc). ami (pierre, tom). ami (pierre, yves). ami (jean, tom). ami (jean, serge). goal ?- ami (jean, X), ami (pierre, X).

(quels sont les amis communs de Jean et de Pierre ?)

Spécificités et mécanismes fondamentaux

La remontée  X est liée à yves (première instanciation)  Prolog cherche : ami (pierre, yves), il trouve et affiche X = yves  X est déliée de yves et la recherche recommence : remontée (1)  X est liée à tom (deuxième instanciation)  Prolog cherche : ami (pierre, tom), il trouve et affiche X = tom  X est déliée de tom et nouvelle recherche : remontée (2)  X est liée à serge (troisième instanciation)  Prolog cherche : ami,(pierre, serge), ne trouve pas --> STOP

 Réponse: X=yves, X=tom.

Spécificités et mécanismes fondamentaux

La remontée

a l : e u q à Remar t e m r e p e é t n o m e r r e v u o r t e d g Prolo s r u e l a v s e l toutes . e l b a i r a v e n u d'

Spécificités et mécanismes fondamentaux

Raisonnement PROLOG  Comment « raisonne » PROLOG :

 Afin de répondre à la question posée (satisfaire le but), Prolog raisonne sur les faits et les règles de la base de données.

 Il cherche à unifier la question (le but) avec un fait ou une tête de règle (chaînage arrière)

Spécificités et mécanismes fondamentaux

Raisonnement PROLOG  Le principe du « chaînage arrière » :

 Il cherche la règle dont la tête est compatible avec le but et cherche à prouver les conditions de cette règle.

 Prolog utilise la « remontée », à savoir, la reprise de la recherche d’une solution, à chaque fois qu’un succès ou qu’un blocage a eu lieu, jusqu’à épuisement des possibilités.

Spécificités et mécanismes fondamentaux

Raisonnement PROLOG  Les buts d’une suite sont satisfaits de gauche à droite:  Si le but est formé de plusieurs questions (conjonction de buts), Prolog s’attaque au but le plus à gauche de la suite, puis il passe au suivant, etc..

 Les clauses d’un prédicat sont testées de haut en bas:  Selon l’ordre d’apparition dans le programme, Prolog cherche un fait de la BDD ayant le même prédicat que le but à prouver, en vue de l’unification.  S’il n’en trouve pas, il s’attaque aux « règles » et cherche à unifier le but avec la tête de la règle.

Spécificités et mécanismes fondamentaux

Les prédéfinis FAIL et CUT fail Prédicat prédéfini qui signifie l'échec d'un but et force la remontée. Utilisé lorsque l'on veut connaître toutes les solutions d'un problème et que la remontée n'agit pas.

Spécificités et mécanismes fondamentaux

Les prédéfinis FAIL et CUT

Question sans variable: clauses père (jean, yves). père (jules, marie). père (jules, ève). tous_présents:- père(X,Y), writef( '%w est le père de %w', [X,Y] ). Question (but ou goal): ?- tous_présents. %question sans variables

Réponse: jean est le père de yves (une seule réponse car la remontée n’agit pas)

Spécificités et mécanismes fondamentaux

Les prédéfinis FAIL et CUT  Pour forcer la remontée on a deux solutions:

1 - Ajouter « fail » à la fin de la clause: tous_présents :-père(X,Y),

writef(‘%w est le père de %w',[X,Y]),fail. 2 – Ajouter « fail » à la fin de la question: ?-

tous_présents, fail.

Spécificités et mécanismes fondamentaux

Les prédéfinis FAIL et CUT

cut - Le « coupe-choix » est un prédicat prédéfini (noté "!") qui empêche la remontée. - Utilisé lorsqu'on est intéressé seulement dans certaines solutions du problème (pas toutes). - Evite des explorations inutiles. - Permet un contrôle plus fin sur le déroulement d'un programme.

Spécificités et mécanismes fondamentaux

Les prédéfinis FAIL et CUT  Exemple :

 si dans le programme de la diapo 63 on ne veut que la première solution, on écrit :  père (jean, yves) :- ! .

 Le (!) arrête la recherche des autres solutions à la question :  père (X,Y).

Spécificités et mécanismes fondamentaux

Les prédéfinis FAIL et CUT Programme pour détecter le maximum de deux nombres

 max(X,Y,Y) :- X =< Y.  max(X,Y,X) :- X > Y.

% Ajoutez un CUT à la fin de la première clause et vérifiez en TRACE la différence.

Spécificités et mécanismes fondamentaux

Paquet de clauses Action du CUT dans un paquet de clauses  Soient les clauses (sans CUT): a(X,Y) :- b(X), e(Y). a(X,Y) :- c(X), e(Y).  Et les faits: b(1). b(2). c(3). e(4).

 Le but: a(X,Y).  Réponses: X=1, Y=4; X=3, Y=4; X=2, Y=4

Spécificités et mécanismes fondamentaux

Paquet de clauses  Mêmes clauses (avec CUT):  a(X,Y) :- b(X), !, e(Y).  a(X,Y) :- c(X), e(Y).  b(1). b(2). c(3). e(4).

 But: a(X,Y).  Réponse: X=1, Y=4

 Variante: a(X,Y) :- !, b(X), e(Y).  Réponse?

Spécificités et mécanismes fondamentaux

Paquet de clauses L’action du CUT dans un paquet de clauses: - l'action du CUT s'exerce seulement sur le prédicat qui le précède.

- les instanciations faites pour les variables de ce prédicat sont fixées et ne sont pas remises en cause lors d'une remontée.

Spécificités et mécanismes fondamentaux

La négation en Prolog

NOT Utilisation de la négation en PROLOG

Spécificités et mécanismes fondamentaux

La négation en Prolog  Soit le programme: courageux(jean). courageux(pierre). chétif(pierre). explorateur (X) :- courageux (X), not (chétif (X)). (un explorateur doit être courageux et pas chétif) Le but: ?- explorateur(X). X=jean

%qui est explorateur?

Spécificités et mécanismes fondamentaux

La négation en Prolog  L'usage du NOT est soumis à deux restrictions :  1. Le NOT ne peut intervenir que dans le corps d'une règle et non pas dans sa tête.  Exemple : explorateur (X) :- courageux (X), not (chétif (X))

--> correct  Mais : not (explorateur (X)) :-chétif (X)

--> incorrect

Spécificités et mécanismes fondamentaux

La négation en Prolog  2. Pour prouver une condition du type not( ) il faut que toutes les variables impliquées dans la négation soient liées (remplacées par des constantes).

 Explication :soit le but : "explorateur (X)" (qui est explorateur ?)  Prolog cherche une règle dont la tête est compatible avec ce but (en chaînage arrière) et trouve :  explorateur (X) :- courageux (X), not (chétif (X)).

Spécificités et mécanismes fondamentaux

La négation en Prolog  Il cherche à prouver la première condition de cette règle (courageux (X)) ce qui l'amène à lier X à une valeur trouvée dans la base de faits: courageux(jean).  Lorsqu'il s'attaque à "not (chétif (X))", la variable X est donc liée et il vérifie si « chétif(jean)» existe*  Si la règle avait été écrite sous la forme : explorateur (X) :- not (chétif (X)), courageux (X).  La première condition à prouver aurait été « not (chétif (X)) » dans laquelle X est libre ce qui empêche de continuer.

Spécificités et mécanismes fondamentaux

La négation en Prolog

: n o i s u Concl s r u o j u o t t u a II f s e l t n a v e d r e s plac e d , s é i n s t a prédic s n a s s t a c i d pré i u q " T r "NO e i l e d t n e t t perme . s e l b a i r a v s le

Spécificités et mécanismes fondamentaux

Bases de données dynamiques  Prédicats prédéfinis pour manipuler une B.D.D. :

 ASSERT: insère un nouveau fait dans la BDD  ASSERTA : insère un fait en tête des faits existants  ASSERTZ : insère un fait en queue des faits existants.  RETRACT : retranche un fait de la B.D.D.

Spécificités et mécanismes fondamentaux

Bases de données dynamiques Exemples : On entre dans la BDD les données: ?- assert(père (a, b)). ?- assert(père (b, c)). On vérifie leur existance dans la BDD: ?- listing. père(a,b). père(b,c). On peut entrer aussi une règle: ?- asserta((père(a,b):- fils(b,a))). ?- listing. père(a,b):- fils(b,a). père(a,b). père(b,c).

Spécificités et mécanismes fondamentaux

Bases de données dynamiques  On retire un fait de la B.D.D. avec : ?- retract (père (a, b)).

 On efface tous les pères avec ?- retract (père (X, Z)). Ou bien: ?- retractall(père(_, _)).

Spécificités et mécanismes fondamentaux

Bases de données dynamiques  % La BDD peut stocker les résultats des calculs

 :- dynamic stocker/3.

%prédicat dynamique

 calculer(X,Y,Res):- stocker(X,Y,Res), !.  calculer(X,Y,Res):- Res is (X+2)*Y, assert(stocker(X,Y,Res)).

?- calculer(3,4,X). X = 20

Spécificités et mécanismes fondamentaux

Mode TRACE  TRACE permet de suivre pas a pas le déroulement du programme ?- trace. Yes

% on est en mode

trace

?- lancement d’un programme... Call:... Exit...

?- notrace.

% pour sortir de

trace

Spécificités er mécanismes fondamentaux

Le prédéfini FINDALL Le prédéfini « FINDALL » (trouver tous) affiche la Liste des Objets qui satisfont le but Goal Syntaxe:

findall (Objet, Goal, Liste)

-Objet peut être une variable ou un terme complexe qui contient la variable -Le Goal instancie la variable à chaque remontée

-Liste est la liste des valeurs prises par la variable

Spécificités er mécanismes fondamentaux

Le prédéfini FINDALL

Exemple:

qui (‘Jean Dupont’, ’23, rue de Sèvres’, 34). qui (‘Anne Vigier’, ‘7, Bd. Davout’, 20). qui (‘Jules Durand’, ‘6, rue Rollin’, 25).

?-

findall (Age, qui ( _,

Réponse:

_,

Liste = [34, 20, 25]

Age), Liste).

Les structures de contrôle

Pause-réflexion sur cette 2ème partie Avez-vous des questions ?

Programmation logique

Récursivité et listes

Récursivité et listes

Plan de la partie Voici les chapitres que nous allons aborder:  Le schéma récursif  Programmes récursifs  Chemins dans un graphe  Les listes: structure et unification  Programmes récursifs sur les listes

Récursivité et listes

Le schéma récursif  Pour comprendre la nécessité du schéma récursif considérons la base de règles suivante :  père (a, b).  père (b, c).  père (c, d).  père (d, e).  qui indique une filiation descendante de a vers e.

Récursivité et listes

Le schéma récursif  Pour définir la notion d'ancêtre, il nous faut une règle du type:  ancêtre (X, Y) :- père (X, Y). pour l'ancêtre le plus proche, ou bien pour le deuxième rang,  ancêtre (X, Z) :- père (X, Y), père (Y, Z). ou encore  ancêtre (X, V) :- père (X, Y), père (Y, Z), père (Z, V).

 Mais, en écriture récursive, cela donne la règle suivante :  ancêtre (X, V) :- père (X, Y), ancêtre (Y, V). soit : un ancêtre, c'est le père d’un ancêtre*

Récursivité et listes

Le schéma récursif  La récursivité correspond à une règle qui fait appel à elle-même  Dans cet exemple, la recherche s'arrête lorsqu'on arrive au dernier rejeton, qui n'a plus de fils, et qui donc ne peut être ancêtre.  La recherche s'arrête donc sur la clause d'arrêt :  ancêtre (Z, V) :- père (Z, V).

Récursivité et listes

Programmes récursifs

%Programme récursif pour afficher tous les descendents père(jean,pierre) . père(pierre,jules) . père(jules,gaspard). père(gaspard,leon). ancêtre(X,Y) :père(X,Y). ancêtre(X,Y):père(X,Z), ancêtre(Z,Y).

% clause d’arrêt

Récursivité et listes

Programmes récursifs % Programme récursif avec FINDALL pour afficher %la liste des descendants de jean pere(jean,pierre). pere(pierre,jules). pere(jules,gaspard). ancetre(X,Y):- pere(X,Y). ancetre(X,Y):- pere(X,Z), ancetre(Z,Y). ?- findall(X, ancetre(jean,X), Z). Z = [pierre, jules, gaspard]

Récursivité et listes

Programmes récursifs

%Programme pour le calcul de la factorielle factorielle(1, 1). factorielle(N, R):N > 1, N1 is N - 1, factorielle( N1, R1), R is N * R1. ?- factorielle (3, Résultat). Résultat=6

% 5! = 5*4!

Récursivité et listes

Chemins dans un graphe  Un graphe en Prolog représente une relation entre des sommets :  arc (X, Y) signifie qu'il existe une relation (un arc) entre les sommets X et Y.  Exemple :  arc (a, b)

c

a

 arc (b ,c)  arc (c, d)  arc (c, e)

d e

 arc (a, e) b

Récursivité et listes

Chemins dans un graphe

/* Programme pour trouver un chemin entre deux sommets */ arc(a, arc(b, arc(c, arc(c, arc(a,

b). c). d). e). e).

chemin(X,Y):- arc(X,Y). chemin(X,Y):- arc(X, Z), chemin(Z, Y).

Récursivité et listes

Les listes: structure et unification  Une liste est une suite finie d’éléments délimités par des crochets et séparés par des virgules.  Exemples :  [jean, chaise, ab]

%les éléments sont des atomes

 [jean, X, 23, ami(tom, pierre)] %mélange de termes  []

%liste vide

 [ [ ], jean, [3, [a, b]], X, [ ], ami(tom, jules)] %listes imbriquées

Une liste peut contenir tous les types de termes (atomes, nombres, termes complexes, variables), des listes imbriquées, des listes vides et des doublets.

Récursivité et listes

Les listes: structure et unification  Une liste en Prolog peut se séparer en deux parties:  la tête (le premier élément)  la queue (le reste de la liste)  Exemples :  [1, 9, 3]

la tête = 1, la queue = [9, 3] - une liste

 [jean]

la tête = jean, la queue = [ ] -une liste vide

 Prolog sépare la tête et la queue par l’opérateur ‘|’ (barre verticale).  [X | Y] la tête = X, la queue = Y

 La queue d'une liste est toujours une liste

Récursivité et listes

Les listes: structure et unification Exemples (suite): ?- [X | Y] = [jean, ami(jules), ab]. X = jean Y = [ami(jules), ab]

?- [X, Y | Z] = [jean, ami(jules), [ ], ab, W]. X = jean Y = ami(jules) Z = [ [ ], ab, _2300] W = _2300

Prolog a lié W à la variable interne de nom _2300

Récursivité et listes

Programme récursif sur les listes

/* L’appartenance à une liste */ membre(X, [X | ‫)[ـ‬. %condition d’arrêt membre(X, [‫ | ـ‬Z]) :- membre(X, Z). goal membre (c,[a, b, c, d,]). réponse: Yes

Récursivité et listes

Programmes récursifs sur les listes Explications:

 Prolog parcourt la liste, élément par élément :  Première étape :  On compare l’élément recherché avec la tête de la liste  Si faux, deuxième étape :  On compare l’élément recherché avec la tête de la sous liste  Si faux, troisième étape :  On compare l’élément avec la tête de la sous sous liste …  On applique la récursivité jusqu'à épuisement de la liste.

Récursivité et listes

Programme récursif sur les listes %Affiche les nombres pairs d'une liste membre(X,[X  ‫)[ـ‬. membre(X,[‫ ـ‬ Y]) :- membre(X,Y). pair(X,Liste) :- membre(X,Liste), (X mod 2) =:= 0. goal pair(X,[1,2,3,4,5,6,7]). réponse: X=2 X=4 X=6

Récursivité et listes

Programmes récursifs sur les listes Explication du programme précédent.

 La fonction « membre » donne à X la valeur de chaque élément de la liste (X est lié successivement à chaque élément de la liste)

 Ensuite on vérifie que cet élément est pair (si le reste de sa division par 2 est nul). Le comparateur arithmétique =:= évalue ses deux arguments.

Récursivité et listes

Programme récursif sur les listes

% Nombre d'éléments d'une liste longueur([], 0). %condition d’arrêt longueur([_|Queue], L) :- (remplace le cdr) longueur(Queue, L1), L = L1 + 1. %goal longueur([a, b, c, d, e, f], L). %réponse: L=6

Récursivité et listes

Pause-réflexion sur cette 3ème partie Avez-vous des questions ?

Programmation logique

Applications

Applications

Plan de la partie Voici les chapitres que nous allons aborder:  Recherche opérationnelle  Systèmes Expert  La méthode P.E.R.T.  Les fractales

Applications

Recherche opérationnelle Par « recherche opérationnelle » on comprend l’analyse et l’évaluation d’un processus (industriel, économique, de transport etc) en rapport avec un critère d’optimum. On va appliquer ce principe, en Prolog, dans les cas suivants: 5. Trouver le chemin le plus court entre deux villes (programme « le plus court chemin »). 7. Trouver la liste des villes de nombre donné dont le trajet est minimal (programme « voyageur de commerce »).

Applications

Systèmes Expert On rappelle le principe des deux types de chaînages: - le chaînage arrière (la règle est déclenchée par la conclusion) - le chaînage avant (la règle est déclenchée par la prémisse) Le chaînage arrière est connu depuis Le_Lisp. Le programme en SWIprolog se trouve dans les TPs. Le programme en chaînage avant se trouve dans l’Annexe.

Applications

La méthode P.E.R.T. La méthode PERT (Programm for Evaluation and Research Tasks) permet un ordonnancement optimal des tâches d’un processus. Le programme donné en TP assure la fabrication et le lancement d’un nouveau produit (NP) dans un délai imposé de dix-sept semaines. On distingue deux phases dans l’élaboration du nouveau produit:

1ère phase: analyse détaillée des tâches (durée, succession). 2ème phase: formation des groupes de tâches qui peuvent se dérouler en parallèle. On considère quatre groupes de tâches qui vont être détaillées par la suite.

Applications

La méthode P.E.R.T. Groupe n°1: fabrication et distribution du NP 1.1 – Fabrication du NP (9 semaines) 1.2 – Contrats avec les transporteurs (1 semaine) 1.3 – Approvisionnement des détaillants (NP + affichettes – 3 semaines)

Groupe n°2: prospection du marché 2.1 – Présentation du nouveau produit aux vendeurs (formation -1 sem) 2.2 – Prises de commandes (6 semaines) 2.3 – Enregistrement des commandes (2 semaines)

Groupe n°3: campagne publicitaire 3.1 – Réservation des emplacements publicitaires (10 semaines) 3.2 – Affichage sur les emplacements réservés (1 semaine)

Applications

La méthode P.E.R.T. Groupe n° 4: production des affiches et des affichettes 4.1 – Elaboration des textes et dessins publicitaires (4 semaines) 4.2 – Elaboration des maquettes (3 semaines) 4.3 – Evaluation et choix d’une maquette (2 semaines) 4.4/1 – Impression des affiches murales (5 semaines) 4.4/2 – Impression des affichettes (1 semaine) 4.5 – Distribution des affiches aux entreprises d’affichage (2 semaines) Toutes ces données sont synthétisées dans un tableau à trois colonnes que les élèves sont invités à remplir. Exemple: Tâche 1.1 1.2 1.3 2.1 ….

Durée (semaines) 9 1 3 1 …..

Tâches précédentes Départ 1.1 1.2 – 4.4/2 – 2.3 Départ ….

Applications

La méthode P.E.R.T. A partir de ce tableau on peut élaborer le « graphe PERT » dans lequel les nœuds représentent des tâches et les arc (orientés) leur succession. Les élèves sont invités à dessiner ce graphe en notant sur les arcs le numéro de la tâche et le nombre de semaines qu’elle implique. La convention graphique adoptée pour les nœuds est la suivante:

X

X représente la date

Y

de début au plus tôt de la tâche* Y représente la date de début au plus tard de la tâche*

Applications

La méthode P.E.R.T. Début des tâches – Marge de manœuvre – Chemin critique -début « au plus tôt » (la tâche ne peut commencer avant cette date car il faut que toutes les tâches précédentes soient finies) - début « au plus tard » (la tâche ne peut commencer après cette date sous peine de retarder les autres tâches) - la marge de manœuvre est la différence entre ces deux dates (le délai dans lequel on peut retarder le début de la tâche) - les tâches à marge nulle doivent commencer à un moment précis* - le chemin critique est la suite des tâches avec une marge nulle (c’est la durée maximale du processus – dans notre cas 17 semaines)

Applications

La méthode P.E.R.T. Calcul de la date de début au plus tôt C’est le maximum des durées des tâches précédentes. Exemple: la tâche 1.3 (approvisionnement des détaillants avec le NP et les affichettes) est précédée par les tâches des groupes 1, 2 et 4: -1.2 – contrats transp (1 sem) + 1.1 – fabrication du NP (9 sem)  10 sem mais aussi, par le groupe 2 qui comprend la prospection du marché: - 2.1 (1 sem) + 2.2 (6 sem) + 2.3 (2 sem)  9 sem mais aussi, par le groupe 4 vu que les affichettes doivent être prêtes: -4.1 (4 sem) + 4.2 (3 sem) + 4.3 (2 sem) + 4.4/2 (1 sem)  10 sem Donc la date de début au plus tôt de la tâche 1.3 est de 10 semaines: max (10, 9, 10)

Applications

La méthode P.E.R.T. Calcul de la date de début au plus tard On part de la fin du processus (durée maximale imposée ou chemin critique) et l’on soustrait la durée maximale des tâches suivantes: Exemple: la tâche 1.3 dure 3 semaines et finit le processus. La durée totale (imposée) du processus (chemin critique) = 17 semaines Le début au plus tard de la tâche 1.3 est donc: 17 – 3 = 14 Elle doit débuter donc au plus tard la 14ème semaine depuis le début. Son début au plus tôt étant à la 10ème semaine, la marge de manœuvre de la tâche 1.3 est: Marge de manœuvre (1.3) = 14 – 10 = 4 semaines.

Applications

La méthode P.E.R.T. Dates de fin de tâches: En fonction du début tôt ou tard de chaque tâche on peut définir une fin au plus tôt ou au plus tard:

Fin tôt = début tôt + durée Fin tard = début tard + durée Exemple pour la tâche 1.3 qui dure 3 semaines: Fin tôt = 10 + 3 = 13 semaines Fin tard = 14 + 3 = 17 semaines

Applications

Les fractales Définition Une fractale est un objet mathématique qui se crée par répétition d’un motif initial. Le mot fractal (du latin « fractus » – brisé) a été forgé par

Benoît Mandelbrot (1974) Son livre: « The Fractal Geometry of Nature – 1982 met en évidence la variété des manifestations fractales dans la nature (la forme des nuages, des flocons de neiges, des cours des rivières, des côtes de la Bretagne etc. Applications dans l’étude de la formation des corps naturels et des formes virtuelles en informatique.

Applications

Pause-réflexion sur cette 4ème partie Avez-vous des questions ?

Programmation logique

Résumé du module Le principe de l'unification

Le principe de la remontée

Applications: Système expert La méthode P.E.R.T. Les Fractales

Le raisonnement Prolog

La gestion des bases de données dynamiques

Programmation déclarative - Turbo Prolog -

Pour aller plus loin… Si vous voulez approfondir vos connaissances: Livres Programmation en PROLOG pour l'intelligence artificielle de Ivan BRATKO (InterEditions)

Learn Prolog Now de Patrick Blackburn Johan Bos Kristina Striegnitz

512 problèmes corrigés en Pascal, C++, Lisp, Prolog Louis GACOGNE (Ellipses)

Félicitations Vous avez suivi avec succès le module de cours n°4 Programmation déclarative - Turbo Prolog -

Programmation logique

Fin

 Examinez à nouveau la syntaxe de ce langage, les principaux prédicats, ainsi que le concept récursif. Et imprégnez-vous du principe de fonctionnement de PROLOG et de son approche raisonnement simulé.