Remerciez-le!

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

1 Programmation Logique H. Jamoussi Elkamel , FSM Programmation logique Prolog

1 Programmation Logique H. Jamoussi Elkamel , FSM Programmation logique Prolog Programmation Logique H. Jamoussi Elkamel , FSM 2 Chapitre 1: Programmation logique et Prolog 2 Programmation Logique H. Jamoussi Elkamel , FSM Pourquoi la programmation • On écrit des programmes pour résoudre des problèmes. • Un problème est spécifié par : – Les entrées : • les données (les faits), • les contraintes et les hypothèses (règles) – Les sorites : la conclusion (but) • Résoudre un problème revient à trouver un chemin de résolution à partir des entrées vers la sortie c’est- à-dire donner une démonstration de la conclusion à partir des entrées. 3 Programmation Logique H. Jamoussi Elkamel , FSM Exemple : parcours d’un graphe • Soit le graphe orienté suivant : • Dans les graphes orientés, les chemins (les arcs) sont à sens unique entre deux sommets (ou nœuds). 4 3 Programmation Logique H. Jamoussi Elkamel , FSM Exemple : parcours d’un graphe • On cherche à écrire un programme pour répondre aux questions : 1. Peut-on aller de ‘a’ vers ‘c’? 2. Comment aller de ‘a’ vers ‘e’ ? 3. Quels sont les chemins menant à ‘e’ ? 4. Comment aller de ‘a’ à ‘e’ en passant de ‘d’ ? ….. 5 Programmation Logique H. Jamoussi Elkamel , FSM Les principaux paradigmes en programmation o Programmation impérative (dire comment résoudre) ; o Programmation orientée objets o Programmation déclarative (dire quoi résoudre). 6 4 Programmation Logique H. Jamoussi Elkamel , FSM Les principaux paradigmes en programmation • La programmation impérative (procédurale) o Dire comment résoudre un problème o se traduit par une démarche algorithmique (suite d’instructions) qui décrit la façon de traiter les données pour atteindre un résultat par une série d’actions (instructions). o L’ordre d’exécution des instructions est impératif : déterminé à l’avance. o Le déroulement du programme est parfaitement déterministe. o Importance des structures de contrôle o Exemples : C, Basic, Pascal, Fortran, Java, … 7 Programmation Logique H. Jamoussi Elkamel , FSM Les principaux paradigmes en programmation • La programmation orientée objet o Décomposition d’un objet en attributs et méthodes. o Notions de classe et d’interface, de sous-classe, d’héritage, de polymorphisme o Exemples : Smalltalk, C++, Java, C#, ActionScript, VisualBasic, Ada, Python. 8 5 Programmation Logique H. Jamoussi Elkamel , FSM Les différents mode de programmation • La programmation déclarative – Dire quoi résoudre c'est-à-dire spécifier le problème et non comment faire pour le résoudre. – Par exemple, les pages HTML sont déclaratives car elles décrivent ce que contient une page (texte, titres, paragraphes, etc.) et non comment les afficher (positionnement, couleurs, polices de caractères, etc.). – C'est une forme de programmation sans effets de bord, ayant généralement une correspondance avec la logique mathématique. 9 Programmation Logique H. Jamoussi Elkamel , FSM La programmation déclarative • Il existe plusieurs formes de la programmation déclarative : – La programmation descriptive, – La programmation fonctionnelle, – La programmation logique, – la programmation par contraintes, 10 6 Programmation Logique H. Jamoussi Elkamel , FSM La programmation déclarative – La programmation descriptive, • à l'expressivité réduite, • qui permet de décrire des structures de données • (par exemple, HTML, XML, LaTex) 11 Programmation Logique H. Jamoussi Elkamel , FSM La programmation déclarative – La programmation fonctionnelle • qui effectue une description du résultat comme une composition de fonctions mathématiques • LISP, Caml, MatLab, Maple.., 12 7 Programmation Logique H. Jamoussi Elkamel , FSM La programmation déclarative – La programmation logique • Le programmeur ne s’occupe pas de la manière d’obtenir le résultat; par contre, le programmeur doit faire la description du problème à résoudre en décrivant les objets concernés, leurs propriétés et les relations qu’ils vérifient (les faits) ainsi que les règles logiques attendues d’une solution, • Cette description constitue la base de connaissance • Puis, spécifier le résultat comme une question • Ensuite, le mécanisme de résolution intégré au langage, général et universel, parcourt de façon non déterministe toutes les possibilités du problème et calcule les solutions • Exemple: ProLog, Python.. • En Prolog, la résolution s’appuie sur une déduction logique de toutes les conséquences de la base de connaissance via l’unification Programmation Logique H. Jamoussi Elkamel , FSM La programmation déclarative – la programmation par contraintes, • consiste à formuler un problème en termes d’inconnues soumises à des contraintes, énoncé dans un langage de logique du premier ordre et faisant intervenir des opérations et des relations du domaine de calcul. • Résoudre la contrainte, et par là le problème, consiste à trouver les valeurs à attribuer aux variables libres de la formule pour la rendre vraie. ce qui unifie la programmation logique et la programmation mathématique 14 8 Programmation Logique H. Jamoussi Elkamel , FSM Un programme Logique – Un programme logique • Est adapté au calcul symbolique et au raisonnement; • Permet d’exprimer de façon naturelle les textes du langage naturel ; • permet d’énoncer un problème dans un langage du premier ordre sous forme d’une suite de fait et de règles (base des connaissances). – Exécuter un programme logique revient à poser une question 15 Programmation Logique H. Jamoussi Elkamel , FSM La programmation logique • Programmation impérative Programmation logique Procédure Formule programme Ensemble (conjonction) de formules appel de procédure question exécution preuve passage de paramètres substitution (unification) Remarque: dans la programmation logique il n’y a pas d’instruction, pas d’affectation et pas de boucles implicites.. 16 9 Programmation Logique H. Jamoussi Elkamel , FSM La programmation logique 17 Démonstrateur de théorème pour une formule = Moteur d’inférence la question = but ( Une formule existentielle x Q ) Non, il n'existe pas d’instanciation pour x telle que Q soit une conséquence logique de P. le programme (Un ensemble de formules P ) = base des connaissances L'ensemble instanciations pour x telles que Q soit une conséquence logique de P. Programmation Logique H. Jamoussi Elkamel , FSM Exemple : parcours d’un graphe • Soit le graphe orienté suivant : • Dans les graphes orientés, les chemins (les arcs) sont à sens unique entre deux sommets (ou nœuds). 18 10 Programmation Logique H. Jamoussi Elkamel , FSM Exemple : parcours d’un graphe • On cherche à écrire un programme pour répondre aux questions : 1. Peut-on aller de ‘a’ vers ‘c’? 2. Comment aller de ‘a’ vers ‘e’ ? 3. Quels sont les chemins menant à ‘e’ ? 4. Comment aller de ‘a’ à ‘e’ en passant de ‘d’ ? ….. 19 Programmation Logique H. Jamoussi Elkamel , FSM Exemple : modélisation d’un graphe orienté /*base des connaissances « graph.pl » */ /* Les faits */ /* les prédicats arc(Source, Destination) pour décrire un arc entre la source et la destination */ arc(a,b). arc(a,e). arc(b,e). arc(c,e). arc(e,d). arc(d,a). 20 11 Programmation Logique H. Jamoussi Elkamel , FSM Exemple : modélisation d’un graphe orienté /*base des connaissances */ /* Les faits */ /* arc(Source, Destination) */ arc(a,b). arc(a,e). arc(b,e). arc(c,e). arc(e,d). arc(d,a). /* les règles */ /* la règle chemin(Source, Destination) pour décrire qu’il existe un chemin entre la source et la destination */ chemin(X,Y) :- arc(X,Y). chemin(X,Y):- arc(X,Z), chemin(Z,Y). 21 Programmation Logique H. Jamoussi Elkamel , FSM /*poser des questions à la base de connaissances « graph.pl» ?- consult(graph). /* charger la base de connaissance*/ true ?- chemin(e, a). true ?- arc(a,X). X=b ; X=e. ?- chemin(a,c). boucle! 22 Exemple : modélisation d’un graphe orienté 12 Programmation Logique H. Jamoussi Elkamel , FSM Syntaxe de Prolog • Les éléments de base d’un programme Prolog sont les – prédicats – et les termes. Dans chemin(a, X). – chemin est un (symbole de) prédicat. – a est un terme (une constante). – X est un terme (une variable). 23 Programmation Logique H. Jamoussi Elkamel , FSM La programmation logique • Les principales caractéristiques d’un langage de programmation logique : – Symbolique : tous les objets manipulés sont des symboles (constantes, variables, etc..) – Haut niveau: aucune gestion de la mémoire et masquage du caractère impératif de la machine; – Déclaratif : on s’intéresse plus à dire « quoi faire » , non « comment faire » – Le programmeur doit définir les faits et les règles logiques attendues d’une solution et laisser le compilateur les transformer en séquence d’instructions. 24 13 Programmation Logique H. Jamoussi Elkamel , FSM Domaines d’application de La programmation logique La programmation logique est Adaptée aux problèmes relevant de l’Intelligence Artificielle – Planification, – Raisonnement automatique (systèmes experts, diagnostic des pannes , les automates …) – Traitement de la langue naturelle (l’analyse syntaxique..) – Interrogation des bases de données déclaratives – Vérification de la correction de programme – Résolution symbolique d’équations – Web Sémantiques … 25 Programmation Logique H. Jamoussi Elkamel , FSM Rappels de Logique mathématique • La logique = Un outil pour modéliser et valider le raisonnement humain (“raisonnement naturel”) • Dans la logique classique ( Logique mathématique) on a : – La logique des propositions = la logique d’ordre 0 – La logique des prédicats = la logique de 1er ordre 26 14 Programmation Logique H. Jamoussi Elkamel , FSM uploads/Philosophie/ programmation-logique-prolog.pdf