Support de cours
Programmation et IA
Université de Kairouan
Dr. Imen JDEY
[Link]@[Link]
2023/2024
Séance 1 29/01/2024 2
Paradigmes de programmation
Historique
3
• Survol des langages de programmation:
• C : programmation de système, langage non restrictif, prés de la
machine
• C++ : version orientée objet de C
• Pascal : conçu pour l’enseignement
• Simula : introduction de la notion de classe
• Java : langage ressemblant au C++ mais avec une meilleure
adhérence au paradigme OO
• Prolog : programmation logique
• Lisp: intelligence artificielle (preuve de théorème), une seule
structure de donnée: la liste.
• COMMONLISP: dialecte de LISP, amalgame de différents
dialectes, tentative de création d’un standard.
• SmallTalk: premier langage orienté objet mature,
environnement graphique (fenêtres).
Paradigmes de programmation 4
Paradigmes de programmation
Les différents paradigmes de programmation
Deux grandes approches dans la programmation
• Une approche impérative: on décrit à la machine,
exactement ce qu’elle doit faire (un programme = suite
d’instruction à exécuter par la machine).
• Une approche déclarative: on décrit à la machine ce que l’on
veut qu’elle calcule (c’est à elle de trouver l’algorithme).
5
Exemples de programmation déclarative
• HTML (Hyper Text Markup Language) utilisé pour la description
de pages Web
• SQL (Structured Query Language)
utilisé pour manipuler et interroger des bases de données
relationnelles
Exemple
SELECT * FROM employees
WHERE (statut=’stagiaire’);
6
Exemples de programmation déclarative
• La programmation logique
Prolog : Ensemble de
• règles de logique
• faits élémentaires
Les faits et règles sont exploités par un démonstrateur de théorème
ou moteur d’inférence , en réaction à une question ou requête
• La programmation fonctionnelle
Traite le calcul comme l’évaluation de fonctions mathématiques
7
Programmation LOGIQUE
8
Programmation Logique
• Le programme est une description du problème (ex : base
de connaissance).
• L’utilisateur interroge le programme.
• On est, d’une manière générale, indépendant de la
machine.
• Les langages utilisés, d’une façon générale, permettent de
décrire le problèmes sous forme de faits et de relations
(exemple PROLOG).
9
Le formalisme logique
Aspects syntaxiques :
Vocabulaire + Syntaxe
Aspects sémantiques :
Valeur de Vérité
Signification logique : valeur de vérité (vrai ou faux)
10
Syntaxe de la logique des prédicats
Alphabet: l’alphabet de la logique des prédicats est constitué de:
• Constantes: Symboles commençant par une lettre minuscule
a, ali, un , ...
• Variables: Symboles commençant par une lettre majuscule
A, Ali,…
• Prédicats: Symboles commençant par une lettre majuscule
P, Q, Homme, Mortel, …
• Fonctions: Symboles commençant par une lettre minuscule
f, g, père-de, plus, …
• Connecteurs: ┐, ∨, ∧, → et ↔
11
Syntaxe de la logique des prédicats
• Quantificateurs :
• Existentiel
Exemple: Il y a quelqu’un de bizarre dans l’amphi
∃X Est-dans(X, amphi) ∧ Bizarre (X)
• Universel
Exemple: Toute personne dans cet amphi est intelligente
∀ X Est-dans(X, amphi) → Intelligent(X)
• Séparateurs: { (, ) }
12
Règles d’inférence
Définition
Une règle d’inférence est la représentation d’un procédé pour, à
partir d’une ou de plusieurs fbfs dériver d’autres fbfs.
• La règle d’inférence appelée modus ponens
→ à partir de deux fbfs P et P→Q, on peut dériver la fbf Q.
If today is Tuesday, then John will go to work.
Today is Tuesday. Therefore, John will go to work.
• La règle d’inférence appelée modus tollens
→ à partir de deux fbf respectivement de la forme (┐Q) et
(P→Q), dérive la fbf (┐P).
If I am happy, then I smile. I am not smiling, therefore I am not happy.
13
Forme normale prénexe d’une fbf
c’est une formule dérivée en appliquant la séquence des quatre
transformations a, b, c, d, ci-après :
a. Éliminer les connecteurs → et ↔
pour ce faire utiliser les lois d’équivalence entre : (G↔H) et
((G →H) ∧(H→G)) d’une part et (G→H) et (┐G ∨H) d’autre part.
b. Accoler les connecteurs ┐ aux atomes concernés pour ce faire
utiliser les lois d’équivalence entre :
• ┐┐G et G
14
Forme Clausale
Forme normale prénexe d’une fbf
• ┐(G ∨H) et ┐G∧┐H
• (┐((∃X) P(X))) et (∀X) (┐P(X))
• (┐((∀X) P(X))) et ((∃X) (┐P(X))
c. Distinguer les variables, (de sorte que chaque connecteur
gouverne une variable originale)
pour ce faire utiliser les lois d’équivalence entre :
(∀X) P(X) et (∀Y) P(Y)
(∃X) P(X) et (∃Y) P(Y)
d. Déplacer tous les quantificateurs à gauche de la formule (sans
changer leur ordre relatif)
15
Exemples:
(∀X) P(X) → (∃X) Q(X)
(∃X (P(X) → Q(X))) → (∀X P(X) → ∃X Q(X))
G: ((∀X) ((P(X) ∧ Q(X,a))→ (R(X,b) ∧ ((∀Y)((∀Z) R(Y,Z) →
T(X,Y))))) ∨ ((∀X) S(X))
16
Forme Normale Prénexe
Exemples:
(∀X) P(X) → (∃X) Q(X)
≅ (¬((∀X) P(X))) ∨ (∃X) Q(X)
≅ (∃X) ¬P(X)) ∨ (∃X) Q(X)
≅ (∃X) (¬P(X) ∨ Q(X))
(∃X (P(X) → Q(X))) → (∀X P(X) → ∃X Q(X))
≅ (¬(∃X (P(X) → Q(X))) ∨ ((∀X) P(X) → ∃X Q(X))
≅ (¬(∃X (¬P(X) ∨ Q(X))) ∨ ((¬(∀X P(X))) ∨ ∃X Q(X))
≅ (∀X (P(X) ∧ ¬Q(X))) ∨ (∃X (¬P(X)) ∨ ∃X Q(X))
≅ (∀X (P(X) ∧ ¬Q(X))) ∨ (∃X (¬P(X) ∨ Q(X)))
≅ (∀X (P(X) ∧ ¬Q(X))) ∨ (∃Y (¬P(Y) ∨ Q(Y)))
≅ ∀X ∃Y ((P(X) ∧ ¬Q(X)) ∨ (¬P(Y) ∨ Q(Y)))
17
Soit la fbf:
G: ((∀X) ((P(X) ∧ Q(X,a))→ (R(X,b) ∧ ((∀Y)((∀Z) R(Y,Z) →
T(X,Y))))) ∨ ((∀X) S(X))
Après l’étape a), on obtient:
((∀X) ((┐(P(X) ∧ Q(X,a)))∨ (R(X,b) ∧ ((∀Y)((┐(∀Z) R(Y,Z))
∨T(X,Y))))) ∨ ((∀X) S(X))
Après les étapes b) et c), on obtient:
((∀X) ((┐(P(X) ∨┐Q(X,a)))∨ (R(X,b) ∧ ((∀Y)(((∃Z) ┐R(Y,Z))∨
T(X,Y))))) ∨ ((∀U) S(U))
Après l’étape d), on obtient une fnp de G:
(∀X) (∀Y) (∃Z) (∀U) (((┐P(X) ∨┐Q(X,a)) ∨ (R(X,b) ∧ (┐R(Y,Z)
∨T(X,Y))))∨S(U))
18
