Intelligence

Artificielle
COURS DE IA Dr DABONE 1
Chapitre 1: GENERALITES
SUR L’IA
▪ Définition
▪ Objectifs
▪ Historique

COURS DE IA Dr DABONE 2
IINTRODUCTION
COURS DE IA Dr DABONE 3
 OBJECTIFS

• L'objectif de l'Intelligence Artificielle est

double : le premier concerne l'analyse
théorique et pratique des processus cognitifs ;
le second s'intéresse à la réalisation (``hard'' et
``soft'') d'artéfacts intelligents.
• L’Intelligence Artificielle se place parmi les
sciences ``sociales'' (psychologie, linguistique,
philosophie), ``naturelles'' (neurobiologie,
physiologie), et a une approche oscillant entre
une méthode rigoureuse et un bricolage
effréné.
COURS DE IA Dr DABONE 4
 Définition (1)

• Artificielle: Partie facile à définir: L’IA est

artificielle à cause de ses origines et de
son mode de création. C’est le résultat
d’un processus humain plutôt que d’un
processus naturel (biologique et
évolutionnaire)

• Intelligence: Pas si facile! Qu’est-ce que

l’Intelligence? On va commencer par la
définition du dictionnaire.
COURS DE IA Dr DABONE 5
 Définition (2)

• Intelligence : Selon le Webster’s New World

Dictionary (1988), l’intelligence, c’est:
• (a) La capacité d’apprendre ou de comprendre
grâce à l’expérience.
• La capacité d’acquérir et de retenir les
connaissances.
• La capacité mentale
• (b) La capacité de répondre rapidement et de
manière appropriée à une nouvelle situation;
L’utilisation de la faculté de raisonnement pour
résoudre des problèmes, se comporter en société,
etc. de manière effective.
• (c) En Psychologie, le succès mesuré de
l’utilisation de ces capacités afin de résoudre
certaines tâches.
COURS DE IA Dr DABONE 6
 Définition (3)

• Les définitions précédentes sont un peu vagues:

Qu’est-ce qu’une nouvelle situation?
• Qu’est-ce que l’apprentissage? L’intelligence
est-elle seulement humaine ou est-ce qu’elle
existe également chez les animaux?
• Est-ce qu’une machine peut être intelligente?
• Ces questions sont intéressantes, mais nous
n’allons pas en parler: Elles appartiennent plutôt
a un cours de de philosophie.

COURS DE IA Dr DABONE 7
 Définition (4)

• Pour ce cours, définition de Marvin Minsky

(1968):
• L’IA a pour but la construction de
programmes informatiques qui s’adonnent à
des tâches qui sont, pour l’instant,
accomplies de façon plus satisfaisantes par
des êtres humains car elles demandent des
processus mentaux de haut niveau tels que
: l’apprentissage perceptuel, l’organisation
de la mémoire et le raisonnement critique.

COURS DE IA Dr DABONE 8
 Définition (5)

• Cette définition laisse la place pour des

différences de points de vue:
• Certains chercheurs voient l’IA comme une
branche de l’ingénierie [construction de robots]
• D’autres chercheurs souligne le lien avec les
Sciences de la Cognition [simulation de
l’intelligence humaine]
• D’autres chercheurs s’intéressent aux questions
Philosophiques associées aux connaissances et
à la conscience.

COURS DE IA Dr DABONE 9
 Définition de l’IA (6)

– Apprendre aux ordinateurs à être plus intelligents

permettra sans doute d’apprendre à l’homme à être
plus intelligent (P. H. Winston, 1984)
– L’IA est l’étude des idées qui permettent aux
ordinateurs d’être intelligents (P. H. Winston)
– L’IA est l’étude des facultés mentales à l’aide de
modèles de type calculatoire (McDermott & Charniak)
– L’IA a pour but de faire exécuter par l’ordinateur des
tâches pour lesquelles l’homme dans un contexte
donné est aujourd’hui meilleur que la machine (Alliot
et Schiex 1994)

COURS DE IA Dr DABONE 10
 Qu’est-ce véritablement que l’IA ?

– Plusieurs définitions possibles de l’IA

– L’IA est une méthodologie qui doit permettre de rendre
les ordinateurs plus intelligents de façon à ce qu’ils
montrent des caractéristiques normalement associées
à l’intelligence dans les comportements humains,
c’est-à-dire la compréhension du langage,
l’apprentissage, la résolution de problèmes et le
raisonnement (E. Feigenbaum)
– L’Intelligence Artificielle concerne la conception d’un
être artificiel (machine) capable de posséder ou
d’exhiber les capacités et caractéristiques propres à
un cerveau humain
– Apprendre aux machines à penser
COURS DE IA Dr DABONE 11
HISTORIQUES

COURS DE IA Dr DABONE 12
 Historique

• Cest en 1956 que le terme « intelligence artificielle »

fut crée par John McCarthy.
• En 58 prévision d’un programme pouvant battre un
champion d’échec. Deep blue en 1997.
• Rapidement on voit l’apparition de programme destiné
a la recherche dans l’IA comme STUDENT,Prolog,LISP
etc...
• 1965 : Eliza est le premier programme de
conversation.
• 1970 : SCHRDLU programme de manipulation d’objets
géométrique.

COURS DE IA Dr DABONE 13
 Historique

• La naissance de L’Intelligence Artificielle

• Dès les débuts de l’ordinateur, celui-ci est pressenti
pour reproduire l’intelligence. En témoigne la
dénomination « cerveau électronique » qui lui est alors
attribué.
• Des recherches sont menées vers 1950 à cette fin.
• Deux tendances se sont opposées jusqu’à la fin des
années soixante : les systèmes adaptatifs, dérivés de la
cybernétique, dont l’un des plus fameux a été le
perceptron, conçu par Franck Rosenblatt au Cornell
Aeronautical Laboratory, et les systèmes experts,
préconisés par Marvin Minsky et Seymour Papert, du
Massachusetts Institute of Technology (MIT).
COURS DE IA Dr DABONE 14
 Historique

• Les premiers sont une tentative de modélisation des êtres

vivants, dérivés des travaux des cybernéticiens, notamment
Norbert Wiener, dans les années 40.
• Les seconds consistent à émuler par un programme
d’ordinateur des comportements intelligents ; c’est l’approche
symbolique ou à base de connaissances, dont on peut faire
remonter l’origine au mathématicien Alan Turing en 1950.
• Cette dernière approche a fini par supplanter la première dans
les années soixante, en raison des progrès technologiques des
ordinateurs et des performances des logiciels.
• Durant cette éclipse quasi-totale de l’approche adaptative, les
systèmes experts ont connu un développement considérable,
notamment au cours des années quatre-vingt.

COURS DE IA Dr DABONE 15
 Exemples d’IA (irréalistes ?)

• Exemples (Science-Fiction)
– TRON
– La Guerre des Etoiles (Z6PO)
– IA (Spielberg)
– I, Robot
– K 2000
– Galactica (Cylons)
– 2001 L’Odyssée de l’espace
– Matrix
– Terminator
– …

COURS DE IA Dr DABONE 16
 Mécanisation du calcul

• Automatisation
– 1623 Shickard
– 1642 Pascal
– 1670 Leibnitz
– 1728 Falcon
– Automates de
Vancauson
– 1805 Jacquard
– Charles Babbage
• 1822 Machine
différentielle
• 1830 Machine
analytique

COURS DE IA Dr DABONE 17
 La Machine Analytique

• Entre 1834 et 1836 Babbage définit les

principaux concepts qui préfigurent ceux des
ordinateurs :
– Dispositif d’entrée / sorties (clavier, moniteur)
– Organe de commande pour la gestion de transfert
des nombres (unité de commande)
– Magasin pour le stockage des résultats
intermédiaires (registres) ou finaux (mémoire)
– Moulin chargé d’exécuter les opérations (unité
arithmétique et logique)
– Dispositif d’impression (imprimante)

COURS DE IA Dr DABONE 18
 Automates de Vaucanson

• Jacques Vancauson 1709 – 1782

– rival de Prométhée
– 1738 le joueur de flûte traversière
– 1739, joueur de tambourin et de
flageolet, Canard digérateur
– 1746, métier à tisser automatique

• Kempelen 1779
– supercherie du joueur d’échec

Du calcul à l’automate

COURS DE IA Dr DABONE 19
 Mécanisation du calcul

• Naissance de deux thèses paradoxales

– Thése 1 : le calcul ne fait pas partie de
l’intelligence, donc pas d’IA possible
– Thèse 2 : IA Possible car on a pu recréer
des comportements humain (calcul) /
animal (gestuelle)
• Naissance d’une rivalité entre
partisans et adversaires de l’IA

COURS DE IA Dr DABONE 20
 Mécanisation du calcul

Le calcul passe par différentes étapes technologiques

• Mécanique (engrenages)

• Electrique (diode)

• Electro-mécanique (relais)

• Electronique (Transistor)

COURS DE IA Dr DABONE 21
 Le Test de Turing
• C’est en 1950 que Alan Turing proposa un test sur l’IA
aura pour but d’imiter la conversation humaine. Le
principe est d’isoler une personne (A) d’une autre (B)
et d’un ordinateur(C).
• Via un clavier les questions/réponses devront
permettre à l’utilisateur (A) de dissocier l’homme de la
machine si tel n’est pas le cas, on peut alors dire que le
test est reussi
Personne
Personne «B»
«A»

Ordinateur,I
A«C»

COURS DE IA Dr DABONE 22
 Les applications actuelles

• Toutes sortes d’applications existes :

❖Robotique
❖Nanotechnologie
❖Gestion de données
❖Automatisation de systèmes
❖Résolutions de problèmes
complexes
❖Simulation de comportement
humain

COURS DE IA Dr DABONE 23
 GENERATIONS EN INFORMATIQUE

1. La Génération zéro
• C’est le début de l’informatique. La notion de logiciel est
encore inexistante.
• La programmation des ordinateurs se fait manuellement,
sur le matériel, en connectant les composants
électroniques qui doivent être mis en jeu, grâce à des
fiches disposées sur un panneau à l’arrière de la
machine, à l’instar des centraux téléphoniques.
2. La 1re Génération
– Elle est marquée par l’apparition du logiciel, mais
celui-ci se présente sous forme numérique ;
– c’est le code machine, qui est directement compris
dans l’ordinateur.
COURS DE IA Dr DABONE 24
 GENERATIONS EN INFORMATIQUE

3. 2ème Génération
• Elle est encore très proche et est marque par l’apparition du
langage d’assemblage.
• C’est un langage de programmation dans lequel les
commandes du code machine ont des noms qui suggèrent
leurs usages. Un programme en assembleur doit être traduit en
code machine avant de pouvoir être exécuté par le PC
4. 3ème Génération
• C’est la génération à partir de laquelle les langages
informatiques se démaquent de la machine pour se rapprocher
de la langue naturelle.
• C’est le cas de la plupart des langages utilisés actuellement :
le Cobol, Fortran, Basic, Pascal, C… Ces langages présentent
l’avantage d’être relativement indépendants de la machine sur
laquelle ils tournent.
COURS DE IA Dr DABONE 25
 GENERATIONS EN INFORMATIQUE
5. 4ème Génération
▪ C’est la génération des langages appelés L4G.
▪ Ces langages s’adressent aux noninformaticiens qui
souhaitent développer eux-mêmes leurs applications. Ce
sont des langages déclaratifs et non des langages
procéduraux, i.e qu’ils décrivent ce qu’ils décrivent ce qui
est à faire, et non les détails de la procédure.
6. 5ème Génération
• Cette génération marque l’apparition de l’Intelligence
Artificielle. Les langages de cette génération sont donc
ceux de l’IA, c'est-à-dire Lisp et Prolog.
• On peut y ajouter les langages orientés objets. Ce sont
des langages structurés, qui se prêtent au traitement
symbolique. COURS DE IA Dr DABONE 26
 GENERATIONS EN INFORMATIQUE

7. 6ème Génération
• C’est une génération de l’informatique entamée
au Japon, après avoir annoncé dans les années
80 un programme de cinquième génération
associant traitement symbolique et parallélisme.
• Il ne s’agit plus dans cette génération là de
langage, ni de logiciel, mais plutôt d’associer des
informations de types divers (multimédia) et
connaissances à des architectures de machines
spécifiques (parallélisme massif,
connexionnisme….).

COURS DE IA Dr DABONE 27
DISCIPLINES

28
COURS DE IA Dr DABONE
 TYPES D’IA

Deux types d’approches

• IA Forte (approche cognitive)

– La machine doit raisonner à la manière de l’homme
(utiliser les mêmes mécanismes de fonctionnement)
• Approche connexionniste (réseaux
neuromimétiques)
= machine dédiée, spécialisée dans le traitement
parallèle -> « boîte noire »

COURS DE IA Dr DABONE 29
 Approche symbolique ou cognitiviste

• Les premiers théoriciens de cette approche sont John

McCarthy et Marvin Minsky.
• Le concept d’Intelligence Artificielle forte fait donc
référence à une machine capable non seulement de
produire un comportement intelligent, mais d’éprouver
une impression d'une réelle conscience de soi, de «
vrais sentiments », et une compréhension de ses
propres raisonnements.
• Plusieurs types de programmes d’IA symbolique :
❖ Systèmes experts
❖ Programmation par contraintes
❖ Raisonnement par cas

COURS DE IA Dr DABONE 30
 Système expert (1/2)

Base de faits
(entrée)

Base de Moteur
connaissances d’inférence
(base de règles)

Résultat
(sortie)

COURS DE IA Dr DABONE 31
 Système expert (2/2)

• La base de connaissance contient des règles de la

forme :
A→B (si A, alors B)
• Le moteur d’inférence enchaîne ces règles en partant
de la situation de départ P0, jusqu’à atteindre le but visé
Q:
P0 → P1 ; P1 → P2 ; P2 → P3 ; … ; Pn-1 → Pn ; Pn → Q

Chaînage avant,
arrière,
mixte

COURS DE IA Dr DABONE 32
Raisonnement par cas

COURS DE IA Dr DABONE 33
 Programmation par contraintes

= Problèmes de satisfaction de contraintes

ou CSP (Constraint Satisfaction Problem)

➢ variables ;
➢ domaine d’appartenance des valeurs des
variables ;
➢ contraintes reliant ces valeurs.

COURS DE IA Dr DABONE 34
 Limites de l’IA symbolique

Nature du Problème précis Problème imprécis

problème →

Type de
connaissances
Explicites - Planification, - Diagnostic
ordonnancement - XIAO (X = conception,
- Contrôle de processus dessin, fabrication,
guidage)
Implicites - Résolution de - Vision
problème - Compréhension du
- Preuve de théorème langage naturel
- Jeu d’échecs - Robotique
- Traduction - Interfaces homme-
automatique machine

COURS DE IA Dr DABONE 35
IA forte ou Connexionnisme : les réseaux
neuromimétiques

• Un neurone naturel
(≈ 100 milliards dans le cerveau)

• Un neurone formel (artificiel) :

une simplification extrême
(quelques dizaines dans un système)

COURS DE IA Dr DABONE 36
 IA forte ou Connexionnisme : les réseaux
neuromimétiques
• L’intelligence artificielle forte a servi de
moteur à la discipline, mais a également
suscité de nombreux débats.
• En se fondant sur le constat que la
conscience a un support biologique et
donc matériel, la plupart des scientifiques
ne voient pas d’obstacle de principe à
créer un jour une intelligence consciente
sur un support matériel autre que
biologique.
COURS DE IA Dr DABONE 37
 IA forte ou Connexionnisme : les réseaux
neuromimétiques
• Selon les tenants de l'IA forte, si à l'heure
actuelle il n'y a pas d'ordinateurs ou de robots
aussi intelligents que l'être humain, ce n'est
pas un problème d'outil mais de conception.
• Il n'y aurait aucune limite fonctionnelle
• il n'y aurait que des limites liées à l'aptitude
humaine à concevoir le programme approprié.

COURS DE IA Dr DABONE 38
Réseau de neurones simple

COURS DE IA Dr DABONE 39
Perceptron multicouches

COURS DE IA Dr DABONE 40
Réseau de neurones avec rétroaction

41
COURS DE IA Dr DABONE
Un troisième type, pas très « intelligent »

L’exploitation des « Big Data » pour réaliser des

corrélations
= Data mining

Le premier à l’utiliser : Walmart (USA)

Aujourd’hui, les données sont partout,

provenant de tous, utilisées par quelques-uns…

COURS DE IA Dr DABONE 42
 Qu’est ce qu’être intelligent ?

• Apprendre
– élaborer un système de connaissances et pouvoir
intégrer de nouvelles connaissances
• Raisonner, déduire, anticiper
– à partir du système de connaissances et des
données de l’expérience pouvoir produire de
nouvelles connaissances
• Posséder une histoire

• Posséder une conscience

• Posséder des sentiments

COURS DE IA Dr DABONE 43
 TRAITEMENT

• Contrairement à la programmation
classique, l’IA n’exige pas que l’on sache a
priori résoudre un problème.
• Le programmeur doit raisonner en termes
d’objectifs. Seul l’objectif doit être fixé ;
• un théorème à démontrer, une image à
reconnaître, une partie à gagner…
• Le programme d’IA se charge de choisir les
moyens d’atteindre cet objectif en fonction
des hypothèses qui lui sont données.

COURS DE IA Dr DABONE 44
 TRAITEMENT

▪ Il s’agit de programmation déclarative, par

opposition à la programmation procédurale
caractéristique de l’informatique classique : il
suffit de spécifier le « quoi » sans se
préoccuper du « comment », le système étant
capable de trouver lui-même la solution, en
fonction de cet objectif.

▪ la programmation en IA est-elle également

appelée heuristique ?

COURS DE IA Dr DABONE 45
 TRAITEMENT

▪ Pour permettre au système de trouver par lui-

même une solution à un problème donné, il
doit posséder des de raisonnement, sous la
forme logique (programmation logique avec
PROLOG).

▪ Au lieu d’intégrer dans le programme toutes

les étapes du raisonnement, cette logique lui
confèrera les capacités de raisonner par lui-
même à partir des données ou plutôt des
connaissances qui lui ont été fournies.

COURS DE IA Dr DABONE 46
 TRAITEMENT

▪ Langage Prolog - Préambule : un mot de de Lewis

Caroll … Olivier Boisard
▪ Soient les propositions suivantes :
• Les animaux sont toujours mortellement
offensés si je ne fais pas attention à eux
• Les seuls animaux qui m'appartiennent se
trouvent dans ce pré
• Aucun animal ne peut résoudre une devinette s'il
n'a reçu une formation convenable dans une
école
• Aucun des animaux qui se trouvent dans ce pré
n'est un raton-laveur

COURS DE IA Dr DABONE 47
 TRAITEMENT

• Quand un animal est mortellement

offensé, il se met toujours à courir en tout
sens et à hurler
• Je ne fais jamais attention à un animal
qui ne m'appartient pas
• Aucun animal qui a reçu dans une école
une formation convenable ne se met à
courir en tout sens et à hurler.
• Que peut-on déduire de l’énoncé : « cet
animal est un raton laveur » ?

COURS DE IA Dr DABONE 48
 But de l’IA

➢ Le but étant que l’IA doit concevoir des sytèmes

capable de reproduire ou tout de moins se
rapprocher du comprtement humain et de ses
raisonnements, cela ressemble plus à une forme
de mimétisme que de création propre pour le
moment.

➢ L’objectif de l’intelligence artificielle est

d’expliquer les différents types d’intelligence.

COURS DE IA Dr DABONE 49
 But de l’IA

▪ Le but de l’Intelligence Artificielle est de simuler

au sens le plus large le travail de contrôle effectué
par le cerveau.
▪ Un comportement intelligent est une action
complexe, mais contrôlée.
▪ L’heuristique, c’est un raisonnement faisant appel
à l’intuition (par tâtonnements) ou qui se base sur
l’étude de cas favorables.
A la différence des algorithmes, les heuristiques
sont souvent tirées de l’expérience ou d’analogies,
plutôt que d’une analyse scientifique complexe car
recensant le maximum d’éléments, et donc difficile,
voire même impossible.
COURS DE IA Dr DABONE 50
 But de l’IA

L’heuristique est donc l’utilisation des règles

empiriques :

✓ pratiques, faciles et rapides

✓ facilitant la recherche de faits et l’analyse de

situations,

✓ dans un objectif de résolution de problèmes et de

prise de décision

✓ dans un domaine particulier

COURS DE IA Dr DABONE 51
 But de l’IA

Entre l’approche algorithmique nécessitant l’écriture

du processus à suivre pour résoudre le problème et
l’approche de l’intelligence artificielle où la
résolution du problème est confiée à un ensemble de
règles données par l’expert humain du domaine, il y
a une troisième approche qui cherche à s’inspirer du
traitement de l’information effectué par le cerveau,
celle des réseaux de neurones artificiels.

COURS DE IA Dr DABONE 52
COURS DE IA Dr DABONE 53
DOMAINES D’APPLICATIONS DE L’INTELLIGENCE
ARTIFICIELLE
• Pour résoudre un problème donné, on réalise un
modèle du système en question.

• une voiture est constituée d’une carrosserie, d’un

châssis, d’un moteur, de mécanismes de
transmission, de l’habillage

• Lorsque nous voulons raisonner sur la voiture,

nous pouvons partir de ce modèle si nous le
connaissons. Mais il est parfois plus simple de
raisonner sur la connaissance que nous avons de
ce système.

COURS DE IA Dr DABONE 54
DOMAINES D’APPLICATIONS DE L’INTELLIGENCE
ARTIFICIELLE
• La principale difficulté de l’Intelligence Artificielle
ne réside pas dans la programmation, mais dans le
fait de fournir toutes les connaissances, et sous
une forme exploitable par l’ordinateur.
• La principale forme de programmes à base de
connaissances est le système expert, bien qu’il
existe d’autres modes de traitement de
connaissances.
• En informatique classique les concepts les plus utilisés
sont : données, algorithmes, fonctions, procédures,
• En Intelligence Artificielle, on parle des connaissances,
contrôles, recherche, heuristique, inférence.

COURS DE IA Dr DABONE 55
 DOMAINES D’APPLICATIONS DE
L’INTELLIGENCE ARTIFICIELLE
• Parmi les différentes branches de l’intelligence artificielle,
nous pouvons citer :
1. Le traitement du langage naturel
2. la reconnaissance des formes et de la parole
3. La robotique
4. La représentation des connaissances
5. Jeux et résolution des problèmes
6. La conduite et le contrôle des processus
7. L’apprentissage
8. La programmation par contraintes
9. Le raisonnement basé sur le cas
10. La vision par ordinateur
11. Robots et systèmes autonomes
12. La traduction automatique
13. Les systèmes experts
14. Les réseaux de Neurones
15. COURS etc
La modélisation cognitive, DE IA Dr DABONE 56
 DOMAINES D’APPLICATIONS DE
L’INTELLIGENCE ARTIFICIELLE
• Parmi les différentes branches de l’intelligence artificielle,
nous pouvons citer :
1. Le traitement du langage naturel
2. la reconnaissance des formes et de la parole
3. La robotique
4. La représentation des connaissances
5. Jeux et résolution des problèmes
6. La conduite et le contrôle des processus
7. L’apprentissage
8. La programmation par contraintes
9. Le raisonnement basé sur le cas
10. La vision par ordinateur
11. Robots et systèmes autonomes
12. La traduction automatique
13. Les systèmes experts
14. Les réseaux de Neurones
15. COURS etc
La modélisation cognitive, DE IA Dr DABONE 57
 DOMAINES D’APPLICATIONS DE
L’INTELLIGENCE ARTIFICIELLE
Le Traitement du langage naturel
• Développement des programmes informatiques qui
sont capables.
✓ de lire, de comprendre et de générer les phases telles que
nous les utilisons dans nos conversations et nos écrits.
✓ le traitement du langage naturel,
c’est la programmation des ordinateurs en vue de la
compréhension des langues naturelles.
✓ L’objectif poursuivi dans ce domaine, est de rendre les
machines plus conviviales, de faciliter la communication
entre l’homme et la machine.
✓ Il englobe aussi la compréhension de textes et oraux

COURS DE IA Dr DABONE 58
DOMAINES D’APPLICATIONS DE L’INTELLIGENCE
ARTIFICIELLE
Le Traitement du langage naturel
Reconnaissance et compréhension de la parole continue

COURS DE IA Dr DABONE 59
DOMAINES D’APPLICATIONS DE L’INTELLIGENCE
ARTIFICIELLE
Le Traitement du langage naturel
La traduction automatique
Différentes phases de traduction doivent être
effectuées successivement ou simultanément :
➢ Translittération : convertir les caractères de la
langue source dans l’alphabet de la langue cible
(lorsque l’écriture est différente : Bissa, mooré,
dioula, fulfuldé, russe, chinois, arabe, etc.) ;
➢ traduction mot à mot, ou lexicale ;
➢ traduction syntaxique ;
➢ traduction sémantique ;
➢ traduction pragmatique ou contextuelle.
COURS DE IA Dr DABONE 60
DOMAINES D’APPLICATIONS DE L’INTELLIGENCE
ARTIFICIELLE
LA RECONNAISSANCE DES FORMES ET DE LA PAROLE

COURS DE IA Dr DABONE 61
DOMAINES D’APPLICATIONS DE L’INTELLIGENCE
ARTIFICIELLE
LA ROBOTIQUE
▪ C’est un domaine de l’intelligence artificielle qui
consiste à mettre en place ou à développer des robots
qui sont capables de manipuler des objets et réagir à
des modifications de l’environnement
▪ La robotique comme étant un ensemble de techniques
permettant la conception et la mise en œuvre des
dispositifs (dispositifs) destinés à substituer l’homme
dans ses fonctions motrices, sensorielles et
intellectuelles. Ces dispositifs peuvent être
programmés pour réaliser des actions bien
déterminées ou pour agir par apprentissage.

COURS DE IA Dr DABONE 62
 Robotique
• Chaînes de production :
– automobile,
– Informatique
– Industrie en général

• Concours de robots pour

résoudre un problème
donné

• ASIMO (Honda) site

– Reproduction du
comportement humain
(déplacement,
mouvements)

COURS DE IA Dr DABONE 63
 Robotique
• Selon Bill Gates :
– « .. les défis auxquels est
confrontée l’industrie robotique
sont très semblables à ceux que
nous avons relevés en
informatique il y a trois
décennies »,

Pour la Science, Juin 2007

• Développement de nombreux
types de robots, utilisant des LEGO Mindstorm NXT
systèmes de gestion
incompatibles

COURS DE IA Dr DABONE 64
 DOMAINES D’APPLICATIONS DE
L’INTELLIGENCE ARTIFICIELLE
L’apprentissage
• L’apprentissage est une activité très complexe et
composée de plusieurs processus qu’il est
difficile à décrire.
• Selon le dictionnaire Le Petit robert, « apprendre »
signifie :
 Etre capable de connaître, de savoir,
 Etre avisé, informé de quelque chose
 Acquérir un ensemble de connaissances par un
travail intellectuel ou par l’expérience.
 Modifier la tendance comportementale par
expérience

COURS DE IA Dr DABONE 65
 DOMAINES D’APPLICATIONS DE
L’INTELLIGENCE ARTIFICIELLE
L’apprentissage
• Donc, « apprendre est une activité concernant la
connaissance.

• Il existe deux volets d’apprentissage :

– l’apprentissage naturel et

– l’apprentissage artificiel

COURS DE IA Dr DABONE 66
 DOMAINES D’APPLICATIONS DE
L’INTELLIGENCE ARTIFICIELLE
L’apprentissage
• L’Apprentissage (artificiel) est donc un
domaine de l’intelligence artificielle ou l’on
exploite la faculté d’apprendre pour
accroître ses connaissances, améliorer ses
aptitudes et pour affiner les mécanismes
de raisonnement.
• sous branches d’apprentissage :
– L’apprentissage par mémorisation ou par implantation
– L’apprentissage par instruction ou par conseil
– L’apprentissage par résolution des problèmes
– La déduction
– L’induction

COURS DE IA Dr DABONE 67
 LA MODELISATION COGNITIVE ET XIAO

• La modélisation cognitive est un domaine de l’IA qui utilise la

simulation des processus cognitifs en vue d’expliquer les
mécanismes intellectuels.
• IA sert à simuler ou reproduire le raisonnement, mais aussi à
ressembler, conserver et rendre accessible les
connaissances disponibles dans un domaine donné.
• En particulier, toute activité de conception et même toute
activité en général peut avoir besoin de telles connaissances,
à un moment ou à un autre.
• Ces connaissances peuvent se présenter comme une «aide en
ligne», accessible sur un poste de travail, en l’occurrence un
ordinateur.
• Toutes les tâches informatiques peuvent bénéficier de l’IA, en
particulier celles que l’on désigne sous le sigle XAO ou X
(n’importe quoi) Assistée par Ordinateur, qui deviennent
désormais XIAO ou «X Intelligemment Assisté par Ordinateur»
COURS DE IA Dr DABONE 68
 LA MODELISATION COGNITIVE ET XIAO

• XIA
L’enseignement assisté par ordinateur (EAO)
La conception assistée par ordinateur (CAO)
Conception Assistée par Intelligence
Artificielle (CAIA)

COURS DE IA Dr DABONE 69
 LA MODELISATION COGNITIVE ET XIAO

LES RESEAUX DE NEURONES

• Le neurone est l’unité de base du système nerveux.
• Composé d’un petit corps de cellules avec des
longues extensions fibreuses appelées Axones et
dendrites.
• Les terminaisons des axones d’un neurone
rencontrent les terminaisons des dendrites de
nombreux autres neurones et forment dans le
cerveau un réseau complexe et changeant.

COURS DE IA Dr DABONE 70
 LA MODELISATION COGNITIVE ET XIAO

LES RESEAUX DE NEURONES

• L'objectif des réseaux de neurones artificiels, c’est
d'essayer de récupérer tout ou une partie des
fonctionnalités d'un cerveau humain telles que :
• architecture massivement parallèle,
• calcul et mémoire massivement distribués,
• capacité d'apprentissage,
• capacité de généralisation,
• capacité d'adaptation,
• forte tolérance aux pannes,
• faible consommation énergétique.

COURS DE IA Dr DABONE 71
 LA MODELISATION COGNITIVE ET XIAO

LA PROGRAMMATION PAR CONTRAINTES

▪ Supposons que nous ayons à élaborer l’emploi de
temps des différentes classes d’un complexe
scolaire, comprenant plusieurs classes de 6e, de
5e, de 4e et de 3e, en tenant compte de contraintes
concernant les professeurs, les salles de cours, les
horaires, etc.
▪ Le problème s’énonce en termes de données et de
contraintes, avec des inconnues.

COURS DE IA Dr DABONE 72
 LA MODELISATION COGNITIVE ET XIAO

LA PROGRAMMATION PAR CONTRAINTES

• La résolution consiste à poser des questions de ces
inconnues.
• Le résultat est fourni par une solution de ce système
d’équations. Dans l’exemple suivant, nous avons omis la
question des salles, le problème étant bien assez
complexe ainsi.
• On pourrait ajouter, par exemple, qu’un salle est affectée
à chaque classe, à l’exception de l’éducation physique, du
dessin et de la technologie.
Ou qu’un professeur est attaché
à une salle, pour simplifier le problème.

COURS DE IA Dr DABONE 73
 LA MODELISATION COGNITIVE ET XIAO

LA PROGRAMMATION PAR CONTRAINTES

• Le résultat est fourni par une solution de ce
système d’équations.
• Dans l’exemple suivant, nous avons omis la
question des salles, le problème étant bien assez
complexe ainsi.
• On pourrait ajouter, par exemple, qu’un salle est
affectée à chaque classe, à l’exception de
l’éducation physique, du dessin et de la
technologie.
• Ou qu’un professeur est attaché à une salle, pour
simplifier le problème.

COURS DE IA Dr DABONE 74
 LA MODELISATION COGNITIVE ET XIAO

LA PROGRAMMATION PAR CONTRAINTES

• Données :
• 14 classes (6eA, 6eB, 6eC, 6eD, 5eA, 5eB, 5eC,
5eD, 4eA, 4eB, 4eC, 3eA, 3eB, 3eC)
• 15 professeurs ( 3 profs de math + 3 profs de
français + 2 profs d’anglais + 1 prof d’allemand + 1
prof de technologie + 3 profs d’éducation physique
+ 1 prof de dessin + 1 prof de musique)
• 8 matières (mathématiques, français, anglais,
allemand, technologie, éducation physique, dessin,
musique)
• 5 journées de classe, de 7 heures maximum

COURS DE IA Dr DABONE 75
 LA MODELISATION COGNITIVE ET XIAO

LA PROGRAMMATION PAR CONTRAINTES

▪ Inconnues
▪ L’affectation des différentes matières aux différentes
classes.
Contraintes :Contraintes de bon sens
▪ Un professeur donne un seul cours à la fois
▪ Les matières doivent être réparties équitablement sur la
semaine
▪ L’éducation physique et la technologie ne peuvent excéder
2 heures dans la mêle journée
▪ Les heures d’éducation physique sont si possible,
regroupées par deux
▪ Les professeurs sont spécialisés par programmes, donc
par classes
▪ Les horaires des professeurs ne sont pas extensibles
COURS DE IA Dr DABONE 76
 LA MODELISATION COGNITIVE ET XIAO

RAISONNEMENT BASE SUR LE CAS ou CBR (Case Based

Reasoning).
➢ Contrairement aux systèmes experts classiques, qui
mettent en œuvre principalement le raisonnement
déductif, le mode de raisonnement utilisé par le CBR est
du type inductif ;
➢ la généralisation se fait par approximation ou analogie.
➢ Ce type de raisonnement est au fond plus « naturel », plus
intuitif.
➢ Il reproduit trois facultés fondamentales de l’esprit humain
✓ mémoriser,
✓ se souvenir,
✓ adapter.
COURS DE IA Dr DABONE 77
 LA MODELISATION COGNITIVE ET XIAO

RAISONNEMENT BASE SUR LE CAS ou CBR (Case Based

Reasoning).
➢ Principe du raisonnement basé sur le cas
Le CBR comprend six phases de traitement :
 retrouver dans la mémoire des cas les expériences les
mieux adaptées à la situation courante ;

 sélectionner le(s) cas le(s) plus pertinent (s) à partir de

l’ensemble construit à l’étape précédente ;

 tester et critiquer la solution précédemment élaborée ;

 évaluer les conséquences de la solution ;

 modifier la mémoire par intégration de la nouvelle

expérience COURS DE IA Dr DABONE 78
LA MODELISATION COGNITIVE ET XIAO

RAISONNEMENT BASE SUR LE CAS ou CBR (Case Based

Reasoning).

COURS DE IA Dr DABONE 79
PRINCIPES DE BASE DE
L’INTELLIGENCE
ARTIFICIELLE

COURS DE IA Dr DABONE 80
 ACQUISITION DES CONNAISSANCES

❖ C’est l’une des difficultés majeures dans la

construction des systèmes issus de l’intelligence
artificielle.
❖ Cette phase correspond à la phase d’extraction
des connaissances
❖ Les objectifs de ces outils sont les suivants :
✓ résoudre les problèmes concrets rencontrés par les entreprises,
✓ s’adapter au problème à résoudre, grâce à la définition de
formalismes de représentation des connaissances,
✓ et faciliter l’acquisition et la validation des connaissances,
✓ améliorer la communication entre l’utilisateur et le système, grâce
à la définition d’interfaces homme-machine conviviales

COURS DE IA Dr DABONE 81
 Représentation de connaissances
Considérons la proposition « Milou est le chien de Tintin » (ou « Tintin
est le maître de Milou ») ; « Milou » et « Tintin » peuvent être considérés
comme des nœuds du réseau sémantique, entre lesquels il existe une
relation d’appartenance et/ou de fidélité.

COURS DE IA Dr DABONE 82
Représentation de connaissances
La représentation sous forme d’objets structurés

COURS DE IA Dr DABONE 83
REPRÉSENTATION
LOGIQUE

COURS DE IA Dr DABONE 84
 DÉFINITION

• L'Univers du Discours est représenté par un

ensemble de formules logiques, les règles sont le

modus ponens qui peut s'exprimer par

(((p→q)˄p)→q),

et le modus tollens qui s'exprime en logique par

(((p→q)→˄¬q)→¬p).

COURS DE IA Dr DABONE 85
 Mathématiques et logique

• Avant le XXe siècle : les mathématiques sont considérées

comme « divines »
• Apparition des paradoxes : crise
– Cantor : ensembles non dénombrables
– Russell : ensembles qui ne se contiennent pas

• Problèmes de Hilbert
– Construire un Système Formel des mathématiques
(1908 à 1920)

• Cercle de Vienne 1924

– recherche d’un langage commun à toutes les sciences
– Mécanisation et automatisation du raisonnement
– Système de POST (Système Formel)
COURS DE IA Dr DABONE 86
 Système Formel (Système de POST)

• Système de génération de mots (mécanique)

• Exemple : le MU-puzzle
– Alphabet V = { M, I, U }
– Langage : ensemble des mots commençant par M suivi par des U
et de I
– Axiome MI
– Régles : pour tout ,   V*
• [R1] I → IU
Système de production
• [R2] M → M
• [R3] III → U
• [R4] UU → 

• Peut on obtenir le mot MU ?

COURS DE IA Dr DABONE 87
 Le MU Puzzle

MIU R2 MIUIU R2 MIUIUIUIU

R1

MIIU R2 MIIUIIU
MI R1
R1 MIIIIU
R2 MII R2 MIIII R2 MIIIIIIII
R3 MUI
MIU

COURS DE IA Dr 88
DABONE
 Limites des Systèmes Formels

• Gödel 1931 : L’arithmétique de PEANO est incomplète

• Théorème Gödel/Rosser 1936

– Pour tout système formel non contradictoire qui est une
modélisation de l'arithmétique récursive, il existe des
propositions indécidables (ni prouvable, ni réfutable).

• Tout système formel est donc soumis a des limitations

intrinsèques sur la quantité de "vérité" qu'il est capable
de fournir

COURS DE IA Dr DABONE 89
 Limites des Systèmes formels

Mots sur un alphabet Langage du SF

(théorèmes)

Non théorèmes
MU MI
IMU

Mots générés par un SF

COURS DE IA Dr DABONE 90
 Test de Turing

• Test de Turing
– Un ordinateur peut-il tromper un humain ?

– Deux personnes X, Y (un homme, une femme) interrogées

par Z

– Z doit déterminer qui de X et Y est l’homme ou la femme

– Même test avec un homme (ou une femme) et une

machine

COURS DE IA Dr DABONE 91
 Chambre Chinoise

• Searle (s’oppose à Turing)

– La syntaxe est insuffisante
pour produire le sens

Meilleur moyen : lire un ouvrage et en faire la synthèse

COURS DE IA Dr DABONE 92
 Les Premiers Calculateurs

• 1941 Z3 (Conrad Zuse)

• 1943 Mark I (Howard Aïken,
Harvard)
• 1943 Colossus (Angleterre)
• 1945 ENIAC (Mauchly,
Eckert, Von Neumann)
• 1948 Invention du
transistor (Brattain,
Bardeen et Shockley)
• 1958 Invention du Circuit
intégré (Kilby, TI)

COURS DE IA Dr DABONE 93
 Naissance de l’IA

• Débuts pendant la 2nde guerre mondiale

– décryptage → traduction
– Mise au point d’un traducteur automatique en 5 ans
– Comment représenter les connaissances ?
– Comment les extraire d’un individu ?

• 1956 John McCarthy, Darmouth College

• Objectifs ambitieux
– Traduction automatique
– Jouer aux échecs et battre les grands maîtres

COURS DE IA Dr DABONE 94
 Premiers programmes d’IA

• Newell, Shaw et Simon

– LOGIC THEORIST 1956
– GPS (General Problem Solver)
– NSS (programme de jeu d’échec)

• Physical Symbol System Hypothesis

– Manipuler des symboles = comportement intelligent
– Simon prédit en 1958 la défaite d’un GMI

• Euphorie puis déception

– Recherche dans de multiples directions

COURS DE IA Dr DABONE 95
 Résolution de problèmes

• Exemple de la suite de
Fibonacci
– Fib(0)=1
– Fib(1)=1
– Fib(n)=Fib(n-1)+Fib(n-2)
pour n > 1
Algorithme récursif

fonction Fib(n : entier) : entier

debut
si n <= 1 alors
retourne 1
sinon
retourne Fib(n-1) + Fib(n-2)
fin

COURS DE IA Dr DABONE 96
 Suite de Fibonacci

• On peut donner une version itérative

Algorithme itératif
n Récursif Itératif

fonction Fib(n : entier) :

30 1s < 1s <
entier
Var tab : array[1..100] 40 10s 1s <
d’entiers
Debut 50 20 m 1s <
tab[0]=1;
tab[1]=1; 60 42h27m 1s <

pour i=2 à n faire

tab[i]=tab[i-1]+tab[i-2]
fin pour
retourne tab[n]
fin COURS DE IA Dr DABONE 97
 La Résolution de Problèmes

• La recherche de solutions pour certains problèmes

s’apparente à une recherche arborescente

X X
… X

2 1 2
X O X 1 3 1
…
O 2 1 2

Aide à la sélection du prochain coup

COURS DE IA Dr DABONE 98
 Le Parcours d’Arbre

• Pour gagner :
– Recherche les situations de jeux gagnantes dans l’arbre
• Parcours en profondeur d’abord (depth first search)
• Parcours en largeur d’abord (breadth first search)
• Parcours par approfondissements successifs (depth-first iterative
deepening)
• backtrack

a abcdefghijklm
abefgchijdklm

c d
b

e f g h i j k l m
COURS DE IA Dr DABONE 99
 Parcours d’arbre

• Dans le cas du morpion :

– 9! situations à examiner

• Dans le cas des échecs :

– 10120 situations

• Utilisation de techniques
– d’élagage
• Mini, max
• Alpha, bêta
– heuristiques
COURS DE IA Dr DABONE 100
 Technique Minimax

• Jeux à 2 joueurs

3
Ordinateur maximiser
2 3 1
Joueur minimiser

3 2 5 3 4 5 1 4 5

/

COURS DE IA Dr DABONE 101

Graphe d'état

COURS DE IA Dr DABONE 102

 Jeu de taquin (puzzle)

Proposez les étapes pour aller de l’état initial à l’état final

COURS DE IA Dr DABONE 103

 EXERCICE

COURS DE IA Dr DABONE 104

 Heuristiques admissibles

E.g., Pour 8-puzzle:

• h1(n) = nombre de tuiles mal placés
• h2(n) = distance Manhattan totale
(i.e., nb. de carrées pour arriver à la place désirée pour chaque
tuile)

• h1(S) = ?
• h2(S) = ?

COURS DE IA Dr DABONE 105

 Algorithme de recherche A* et ses
concepts de base
• L'algorithme A* fonctionne sur la base de méthodes
heuristiques, ce qui permet d'atteindre l'optimalité.
• A* est une forme différente de l'algorithme du meilleur
premier.
• L'optimalité permet à un algorithme de trouver la meilleure
solution possible à un problème.
• De tels algorithmes offrent également l'exhaustivité ; s'il
existe une solution possible à un problème existant,
l'algorithme la trouvera certainement.
• Lorsque A* entre dans un problème, premièrement, il calcule
le coût pour se rendre aux nœuds voisins et choisit le nœud
avec le coût le plus bas.
• Si Le f(n) désigne le coût, A* choisit le nœud avec la valeur
f(n) la plus faible. Ici, 'n' désigne les nœuds voisins.

COURS DE IA Dr DABONE 106

 Algorithme de recherche A* et ses
concepts de base
• Le calcul de la valeur peut être effectué comme
indiqué :
• f(n)=g(n)+h(n))
– g(n) = affiche la valeur du chemin le plus court du nœud de
départ au nœud n
– h(n) = L'approximation heuristique de la valeur du nœud
• La valeur heuristique a un rôle important dans
l'efficacité de l'algorithme A*.
• Trouver la meilleure solution, utiliser différentes
fonctions heuristiques en fonction du type de
problème.
– la création de ces fonctions est une tâche difficile, et c'est le
problème fondamental auquel nous sommes confrontés en IA.

COURS DE IA Dr DABONE 107

 Fonction heurstque

• Une heuristique est simplement appelée une

fonction heuristique qui aide à classer les
alternatives données dans un algorithme de
recherche à chacune de ses étapes.
• Il peut soit produire un résultat par lui-même, soit
travailler en conjugaison avec un algorithme donné
pour créer un résultat.
• Essentiellement, une fonction heuristique aide les
algorithmes à prendre la meilleure décision plus
rapidement et plus efficacement.

COURS DE IA Dr DABONE 108

 Fonction heurstque

• Ce classement est basé sur les meilleures

informations disponibles et aide l'algorithme à
décider de la meilleure branche possible à suivre.
• L'admissibilité et la cohérence sont les deux
propriétés fondamentales d'une fonction
heuristique.

COURS DE IA Dr DABONE 109

 Fonction heurstque

• Déterminer le chemin le plus rentable pour aller de

AàG

COURS DE IA Dr DABONE 110

 Fonction heurstque

• Déterminer le chemin le plus rentable pour aller de

AàJ

COURS DE IA Dr DABONE 111

COURS DE IA Dr DABONE 112
 Faire raisonner une machine

• Raisonnement logique

– Calcul des propositions

– Calcul des prédicats

Permet de représenter des connaissance et de

raisonner sur ces connaissances

COURS DE IA Dr DABONE 113

 Calcul Propositionnel

• La logique (Calcul Propositionnel) permet

– de représenter des connaissances
– de raisonner sur ces connaissances
– On utilise des variables propositionnelles (vrai, faux) ainsi que
des connecteurs logiques (et, ou, implique, équivalent) :
• Si il fait beau et qu’on n’est pas samedi
alors je fais du vélo
• Si je fais du vélo alors il y a du vent
• Donc si il fait beau et qu’on est pas
samedi alors il y a du vent
(b s) → f f→v  (b s) → v
COURS DE IA Dr DABONE 114
 Modus Ponens / Principe de résolution

• Règle d’inférence qui permet de produire de nouvelles

connaissances

XY
 YZ
XZ

 (b s)  f
 (b s)  f
  (b s) → v
fv fv

COURS DE IA Dr 115
DABONE
 Problème des pigeons

• Le problème des pigeons :

– Un pigeonnier peut accueillir au plus un pigeon. Etant donné N
pigeons et M pigeonniers chaque pigeon pourra t-il trouver un
pigeonnier pour l’accueillir ?

• Pour un humain : résolution facile

– Abstraction des mots : pigeon, pigeonnier
– Si N <= M alors il existe une ou plusieurs solutions
– Si N > M alors il n’existe pas de solution

• Pour un ordinateur
– Archétype des problèmes NP-complets
– Si N <= M alors résolution facile
– Si N > M alors étudier tous les cas possibles

Si N=30 et P=29 alors 2870  10261

COURS DE IA Dr DABONE 116
 Calcul des prédicats

• Extension du Calcul Propositionnel

– Syllogisme : hommes
• Socrate est un homme
• Tout homme est mortel
• Donc Socrate est mortel

• homme(socrate)
socrate
• X homme(X) → mortel(X)

homme(socrate)
Principe de
Unification résolution mortel(socrate)
homme(X)  mortel(X)

• Démonstration automatique de théorèmes

COURS DE IA Dr DABONE 117

 Constraint Satisfaction Problems

• Beaucoup de problèmes industriels peuvent se

modéliser sous la forme de Problèmes de
Satisfaction de Contraintes (CSP)

• Paradigme des CSP :

– Un ensemble de variables X = { X1, …, Xn}
– Un ensemble de domaines D = { D1, …., Dn }
– Un ensemble de contraintes C = { C1, …, Ck }
– Minimiser ou maximiser une fonction f(X)

• Exemples :
– système d’équation, problème du sac à dos

COURS DE IA Dr DABONE 118

 Exemple de CSP simple

• Les puzzles : SEND + MORE = MONEY

R 4 R3 R2 R1 Contraintes :
SEND
+MORE D+E=10R1+Y
R1+N+R = 10R2+E
=MONEY R2+E+O = 10R3+N
R3+S+M = 10R4+O
M= R4

Domaines D = (D1={0,..,9}, D2={0,1})

Variables X = (S,E,N,D,O,R,Y,M,R1,R2,R3, R4)

COURS DE IA Dr DABONE 119

 Le Problème des Pigeons (CSP)

• On peut donner une version CSP du problème des

pigeons (n pigeons, m pigeonniers):
– Domaine : { 0, 1 } = { faux, vrai}
– Variables : matrice p[NxM], pi,j = 1 signifie que le pigeon i
est dans le pigeonnier j p ,…, p 1,1 1,m

pn,1,…,pn,m
– Contraintes: Modélisation par opérateur de cardinalité
• (,, p1, …, pn) au moins  et au plus  littéraux doivent être vrais
parmi p1 à pn

(1,1, p1,1, …, p1,m) (0,1, p1,1, …, pn,1)

… …
(1,1, pn,1, …, pn,m) (0,1, p1,m, …, pn,m)
Un pigeon doit se trouver dans Un pigeonnier accueille au plus
un pigeonnier (N contraintes) Un pigeon (M contraintes)
COURS DE IA Dr DABONE 120
 Problème des Pigeons (CSP)

• Régles
– addition : (1,1, L) + (2,2, M) => (1 + 2 ,1+ 2, LM)
si L  M  
– Inconsistance : (1,1, L) et (2,2, L) => inconsistance
si [1,1]  [2,2]= 

(1,1, p1,1, …, p1,m) (0,1, p1,1, …, pn,1)

… …
(1,1, pn,1, …, pn,m) (0,1, p1,m, …, pn,m)
+ +
(n,n,L) (0,m,L)

Inconsistance si n > m
Résolution en un temps linéaire par rapport aux données
COURS DE IA Dr DABONE 121
 Problème de coloriage

• Le problème de Ramsey consiste à trouver un

coloriage des arcs d’un graphe complet de N sommets
avec 3 couleurs (Rouge, Vert, Bleu) sans qu’il existe de
triangle monochromatique

Solutions pour N=3 à 16

COURS DE IA Dr DABONE 122

 Résolution du problème de Ramsey

• Pour N=3 à 16 on peut résoudre le problème en un

temps raisonnable

• Pour N>17, cela peut demander plusieurs jours ou

semaines

• Utilisation des symétries du problème afin d’éviter

de retester des cas infructueux déjà découverts

COURS DE IA Dr DABONE 123

 Les échecs

• Probablement le problème le plus étudié en IA

– Etudes psychologiques des GMI (De Groot)
• Positions pensées (non calculées)
• Recherche sélective
• Profondeur faible (quelques coups)
• Fonction d’évaluation floue (protéger une tour, un fou)

COURS DE IA Dr DABONE 124

 Les Systèmes Experts

• Très en vogue dans les années 70

– Base de connaissances
– Base de règles

– MYCIN : diagnostic médical

– DENDRAL : analyse chimique
– PROSPECTOR : prospective géologique
– R1/XCON (Digital Equipment Corporation) : configuration
optimale d’une machine

• Aujourd’hui : systèmes d’aide à la résolution de

problèmes (informatique)

COURS DE IA Dr DABONE 125

 La Programmation Evolutive

• Algorithmes génétiques
– Population initiale de configurations d’un problème
– Fonction d’évaluation d’une configuration
– Opérateurs
• Croisement (des parents)
• Mutation (des enfants)
• Sélection (des enfants de meilleure qualité)

Parents Croisement

Mutation

Sélection
COURS DE IA Dr DABONE 126
 La Reconnaissance de Formes / Sons

• Image :
– Imagerie médicale
– Environnement (déforestation, inondations)
– Espionnage militaire
– Sécurité (reconnaissance du visage)

• Son
– Ecriture
– Domotique
– Sécurité (reconnaissance de la voix)

• Biométrie

COURS DE IA Dr DABONE 127

RESEAUX
DE
NEURONE
COURS DE IA Dr DABONE 128
 LES RÉSEAUX NEURONAUX
• McCulloch et Pitts en 1943
• Kohonen 1984
• Intelligence = calcul ?
• Reconnaissance de forme,
de la parole

COURS DE IA Dr DABONE 129

MODÈLE DE NEURONE FORMEL

COURS DE IA Dr DABONE 130

MODÈLE DE NEURONE FORMEL

COURS DE IA Dr DABONE 131

MODÈLE DE NEURONE FORMEL

COURS DE IA Dr DABONE 132

RESEAU MULTICOUCHE

COURS DE IA Dr DABONE 133

RESEAU A CONNEXIONS LOCALES

COURS DE IA Dr DABONE 134

RESEAU A CONNEXIONS RECURRENTES

COURS DE IA Dr DABONE 135

RESEAU A CONNEXIONS COMPLETES

COURS DE IA Dr DABONE 136

FONCTIONNEMENT

❑ Perceptron
▪ Les connexions des deux
entrées e1 et e2 au
neurone sont pondérées
par les poids w1 et w2.
▪ La valeur de sortie du
neurone est notée x.
▪ Elle est obtenue après
somme pondérée des
entrées (a) et comparaison
à une valeur de seuil S.
COURS DE IA Dr DABONE 137
 FONCTIONNEMENT
• Question : Sachant que les poids du Perceptron
à deux entrées sont les suivants : w1 = 0,5 ;
w 2 = 0,2 et que la valeur de seuil est S = 0.0.
• Déterminer son comportement, sachant que les
comportements du ET logique, OU logique et OU
exclusif sont rappelés dans la table suivante :

COURS DE IA Dr DABONE 138

 APPRENTISAGE
▪ Loi de Hebb
• i est le neurone amont , j le neurone aval et wij le poids de la
connexion.
• La loi de Hebb s’exprime de la manière suivante : « Si 2 cellules
sont activées en même temps alors la force de la connexion
augmente ».
• La modification de poids dépend de la co-activation des
neurones pré synaptique et post synaptique, ainsi que le
montre la table suivante. xi et x j étant respectivement les
valeurs d’activation des neurones i et j, et wij ( dérivée partielle
du poids ) correspondant à la modification de poids réalisée.

COURS DE IA Dr DABONE 139

 APPRENTISAGE
▪ Table de Hebb

▪ Modélisation de la loi de Hebb

COURS DE IA Dr DABONE 140

APPRENTISAGE

COURS DE IA Dr DABONE 141

APPRENTISAGE

COURS DE IA Dr DABONE 142

 APPRENTISAGE
▪ Algorithme de Hebb
Exercice
Soit le réseau composé de 4
neurones d’entrée et d’un neurone
de sortie ( w1 = w2 = w3 = w4 = S = 0)
et la base d’apprentissage :
On demande de recherche les valeurs
des poids qui résolvent le problème avec = 1.
Remarque
Il existe une possibilité de calculer les valeurs des connexions à partir
des exemples, sans utiliser l’algorithme itératif.
Si l’on initialise les poids à zéro et que l’on présente les exemples de la
base d’apprentissage, la valeur des poids à l’issue de l’apprentissage
est donnée par :
wij = ||xil .x jl || 0ù l est l’indice de l’exemple dans la base
d’apprentissage. COURS DE IA Dr DABONE 143
 Chapitre 5 :
INTELLIGENCE
ARTIFICIELLE
DISTRIBUEE (IAD)
COURS DE IA Dr DABONE 144
 DEFINITION

• L’intelligence artificielle distribuée (IAD) est une

discipline de l’informatique qui se propose de distribuer
l’intelligence parmi plusieurs agents, non soumis à un
contrôle centralisé.
• Pourquoi distribuer l'intelligence ?
• Les problèmes sont physiquement distribués : les
problèmes complexes le sont souvent
• Les problèmes sont fonctionnellement distribués
• Les réseaux imposent une vision distribuée
• La complexité impose une vision locale
• Les systèmes doivent pouvoir s'adapter à des
modifications de structures ou d'environnement
• Le génie logiciel va dans le sens d'une conception en
termes d'unités autonomes en interactions : langages
objets COURS DE IA Dr DABONE 145
 Applications de l’IAD
• L’intelligence Artificielle Distribuée a plusieurs applications
dans plusieurs domaines :
1. Dans le domaine de management et de surveillance des
réseaux de télécommunication. :
L’approche intelligence artificielle distribuée consiste à
exploiter la distribution matérielle des différents centres qui
constituent le réseau.
Alors que l’intelligence artificielle classique cherche à
représenter par un modèle unique le fonctionnement de
l’ensemble. En IAD, chaque centre est considéré comme un «
agent » autonome interagissant avec d’autres agents (centres).
2. Dans les problèmes de gestion d’un réseau hétérogène
d’ordinateurs
3. Dans les problèmes de gestion des réseaux de transport
4. Dans les problèmes de gestion des réseaux de distribution de
l’énergie COURS DE IA Dr DABONE 146
 Applications de l’IAD
• Dans tous ces quatre problèmes, chaque centre est
considéré comme un agent autonome.
• L’objectif d’un tel système est de planifier au
mieux le fonctionnement de l’ensemble et son
exploitation en respectant l’architecture et le
matériel existant.
5. Pilotage de navires tels que les supers tankers ou
les porte – avions
• 6. Planification des missions spatiales

COURS DE IA Dr DABONE 147

 CONCEPTS SUR LES AGENTS
• Un agent c’est une entité plus ou moins autonome
qui est définie par :
– Ses connaissances c’est à dire les objets qu’il
manipule (une base d’objets) ainsi que les
contraintes correspondantes.
– Ses accointances c’est à dire l’ensemble des
autres agents qu’il connaît avec les contraintes
qui s’y rattachent et qui sont notamment liés
aux aspects organisationnels.
– Ses buts
– Ses compétences formées d’opérateurs et de
contraintes sur ces opérateurs tels leur
agencement dans un plan.
COURS DE IA Dr DABONE 148
 CONCEPTS SUR LES AGENTS
– Ses interactions comportant les connaissances nécessaires
à l’agent pour communiquer avec
les autres agents.
• Ces connaissances portent sur :
– Les conventions de l’interaction de l’agent avec ses
accointances qui son aussi liés contraintes
organisationnelles appelées protocoles, et les contrôles
regroupant les règles de gestion ces protocoles.
– Les mécanismes de raisonnement qui lui permettent de
prendre des décisions ou de planifier actions
• La structure d’un agent est ainsi axée autour de trois
fonctions principales :
– Celle de percevoir ;
– Celle de décider ;
– Celle d’agir.
COURS DE IA Dr DABONE 149
 langages de
l’Intelligence
Artificielle
COURS DE IA Dr DABONE 150
 DEFINITION

• Les langages de programmation traditionnels sont dits impératifs

ou procéduraux. Ils peuvent traduire des opérations telles que « lire
», « écrire », « additionner », « transférer », « compare », etc.
• Ce sont des instructions correspondant à des séquences de
langage machine.
• En IA, le problème se présente tout autrement, puisqu’il s’agit là de
représenter des connaissances et de simuler des raisonnements.
• Pour résoudre ces problèmes particuliers, il faut des outils et
langages particuliers.
• Les objectifs de ces outils sont les suivants :
Résoudre les problèmes concrets rencontrés par les entreprises,
S’adapter au problème à résoudre, grâce à la définition de
formalismes de représentation des connaissances, et faciliter
l’acquisition et la validation des connaissances,
• Améliorer la communication entre l’utilisateur et le système, grâce
à la définition d’interfaces homme-machines

COURS DE IA Dr DABONE 151

Conclusion

COURS DE IA Dr DABONE 152

 Conclusion

• Ce que l’IA n’est pas :

– AAAI 1999, Patrick Henry Winston
– [Link]

• Une IA est elle possible ?

– Différents points de vue
– Partisans et adversaires de l’IA
– Une grande illusion ?
– Systèmes intelligents ?

• Un ordinateur dirigé à la voix est-il intelligent ?

COURS DE IA Dr DABONE 153

 Conclusion

• Objections :

– Théologique (Matrix)

– Mathématique (Gödel)

– Conscience

– Continuité du système nerveux

– Difficulté de la formalisation du comportement

COURS DE IA Dr DABONE 154

 Un dernier mot

Les ordinateurs ne sont pas

intelligents, toute l’ingéniosité
du chercheur en IA consiste à
vous faire croire qu’ils le sont

COURS DE IA Dr DABONE 155

 Conclusion

• Point de vue personnel :

• Dans l’état actuel de nos connaissances une INTELLIGENCE artificielle basée
sur l’informatique est impossible

• Informatique :
– Traitement automatique de l’information
– Calcul
– Un ordinateur sait donc :
• Représenter des informations simples
• Effectuer des calculs sur ces informations
– Si un problème peut se modéliser par une information simple et
qu’il demande de faire des calculs pour être résolu alors il peut
être traité par un ordinateur

• Une véritable Intelligence possède une conscience de sa

propre existence (Je pense donc je suis)
• Un ordinateur n’apprend pas, il est programmé pour exécuter

COURS DE IA Dr DABONE 156

 Langages de programmation pour l’IA ?

• LISP (origine américaine)

• PROLOG (France ! Colmerauer)
• SmallTalk (Langage objet)
• Les langages de Frame
– YAFOOL (Yet Another Frame based Object Oriented Language)
– KL-ONE (Knowledge Language)
• Langage de logique de description

COURS DE IA Dr DABONE 157

Chapitre 2 : Algorithmes de
parcours d’un espace de
recherche
 [Link]ème général de recherches

COURS IA Dr DABONE
 Problème général de recherches

◼ Construction de l’arbre de recherche :

◼ Exploration simulée de l'espace d'états (graphe d’états) en générant
les états successeurs des états déjà explorés
◼ Les noeuds sont étudiés puis développés ou étendus par un
processus appelé "expansion" d'états
◼ Chaque chemin correspond à un chemin de raisonnement qui conduit
soit à une solution soit à un échec

COURS IA Dr DABONE
 2. Terminologie

◼ États
◼ “Places” que la recherche peut visiter
◼ Espace de recherche
◼ L’ensemble des états possibles
◼ Chemin de recherche
◼ Les états visités par un agent
◼ Solution
◼ Un état avec une propriété particulière
• Qui résout le problème
• Possibilité de solutions multiples
◼ Stratégie
◼ Comment choisir l’étape suivante dans un état donné

COURS IA Dr DABONE
 3. Spécification d’un problème de
recherche
◼ Trois considérations importantes

1. État initial

2. Opérateurs

3. Test du But

COURS IA Dr DABONE
Spécification d’un problème de recherche

1. État initial
◼ La ville où vous êtes Liverpool Leeds
2. Opérateurs
◼ Conduire d’une cité à une autre Nottingham
3. Test du but Manchester

◼ L’état courant est la ville destination Birmingham

London

COURS IA Dr DABONE
4. Exemples de problèmes de recherche

◼ Échecs

◼ Recherche du plus court itinéraire

◼ Démonstration de théorème

◼ Apprentissage

COURS IA Dr DABONE
4. Algorithmes de parcours d’un espace
de recherche
◼ Recherche en profondeur d’abord (DFS) et en largeur (BFS)
◼ Hill Climbing (descente de gradient)
◼ Recherche heuristique : Best-First search
◼ en profondeur ordonnée, en faisceau, du meilleur premier
◼ Algorithme A*, IDA*, SMA*
◼ Recherche concurrentielle : jeux
◼ MIN-MAX, élagage a−b, approfondissement progressif

◼ Propriétés
◼ Complétude
◼ Complexité en temps
◼ Complexité en espace
◼ Optimum

COURS IA Dr DABONE
 5. Critères d’évaluation

Les méthodes de recherche sont évaluées selon :

◼ Optimalité
◼ c'est la caractéristique d’un algorithme de recherche qui trouve la
meilleure solution (pour un problème qui en admet plusieurs)
◼ Complétude
◼ si une solution existe l’algorithme garantit qu’elle sera trouvée
◼ Complexité en temps
◼ estimation du temps nécessaire pour résoudre un problème
◼ Complexité en espace
◼ estimation de l’espace mémoire nécessaire à l’algorithme pour
résoudre le problème

COURS IA Dr DABONE
 Exemple

◼ Trouver un chemin de S à G

COURS IA Dr DABONE
 6. Parcours en profondeur

• Le parcours en profondeur suit le chemin courant le plus longtemps

possible.
• Il est facile à implémenter : il faut tout simplement mettre des
successeurs du nœud courant au début de la liste de nœuds à traiter.
• Le parcours en profondeur n’est pas complet parce que l’algorithme
peut continuer sur un chemin infini, ignorant complètement un état
but qui se trouve sur un autre chemin.
• Si par contre, nous n’avons qu’un nombre fini de chemins possibles, le
parcours en profondeur sera complet.
• L’algorithme n’est pas optimal : il n’y a rien qui garantie que le premier
état but trouvé sera le bon. Considérons maintenant la complexité.

COURS IA Dr DABONE 168

COURS IA Dr DABONE 169
Le parcours en profondeur pour un arbre binaire simple. En gris
le chemin en cours d’examen, en blanc les nœuds non-
explorés, et en noir les nœuds explorés et rejetés.

COURS IA Dr DABONE 170

 7. Parcours en profondeur

• Si nous avons s successeurs et une profondeur maximale de m

actions, dans le pire des cas nous aurions besoin d’examiner tous
les 𝒔𝒎 nœuds pour trouver une solution.
• Sur ces trois premiers critères, il est évident que le parcours en
largeur sort gagnant.
• Alors pourquoi s’intéresser au parcours en profondeur ?
• Le principal avantage du parcours en profondeur reste en sa faible
complexité en espace.

COURS IA Dr DABONE 171

 Parcours en profondeur (Depth-First
Search)
◼ Exemple

COURS IA Dr DABONE
 Parcours en profondeur (Depth-First
Search)
◼ Algorithme

COURS IA Dr DABONE
 Parcours en largeur (Breadth-First
Search)
◼ Exemple

COURS IA Dr DABONE
 7. Parcours en largeur

• Le parcours en largeur est un algorithme de recherche très simple :

nous examinons d’abord l’état initial, puis ses successeurs, puis les
successeurs des successeurs, etc.
• Tous les nœuds d’une certaine profondeur sont examinés avant les
nœuds de profondeur supérieure.
• Pour implémenter cet algorithme, il suffit de placer les nouveaux
nœuds systématiquement à la fin de la liste de nœuds à traiter.

COURS IA Dr DABONE 175

 Parcours en largeur

Le parcours en largeur pour un arbre binaire simple. Nous

commençons par l’état initial A, puis nous examinons les nœuds B
et C de profondeur 1, puis les nœuds D, E, F, et G de profondeur 2.

COURS IA Dr DABONE 176

8. Méthode de recherche heuristique

◼ Les algorithmes de recherche heuristique utilisent

l’information disponible pour rendre le processus de
recherche plus efficace.

◼ Heuristique : une règle ou une méthode qui permet

d’évaluer la chance qu’un chemin allant du nœud courant
au noeud solution soit meilleure que les autres.

COURS IA Dr DABONE
 9. Algorithme A*

◼ Idée : minimiser le coût total f(n) du chemin passant par un noeud

f(n) = d(déjà parcouru) + d(à parcourir) = g(n) + h(n)

◼ Sous-estimation h(n)
n h(n) <= h*(n) avec h*(n) = coût réel depuis n jusqu’au but

◼ Variantes de A*
◼ IDA* =>A* avec approfondissement itératif
(étend tous les noeuds à l’intérieur d’un contour délimité par la valeur courante
de la limite)

Exemple : [Link]

COURS IA Dr DABONE
 Algorithme A*

◼ Cette heuristique estime le coût total du chemin entre l’état

initial et l’état solution qui passe par n : = f(n)
◼ On remarque qu’il s’agit d’une estimation f(n) obtenue par la
somme :
◼ d’une valeur exacte g(n) issue du chemin parcouru de l’état initial
jusqu’au noeud n
◼ et d’une estimation h(n) du coût du chemin optimal qui lie le noeud n
avec le noeud solution
◼ Pour chaque noeud exploré n, on va étendre le successeur
x qui minimise la fonction heuristique f
f(x) = min {f(s) / s dans Successeurs( n )}

COURS IA Dr DABONE
 Algorithme A*

◼ Exemples de fonctions heuristiques : puzzle-8

COURS IA Dr DABONE
 Example

◼ Pour un puzzle-8
◼ h(n) = nombre de plaquettes
mal placées
◼ g(n) = longueur du chemin
parcouru (+1 à chaque
niveau)

COURS IA Dr DABONE Zahia Guessoum

 Algorithme A*

COURS IA Dr DABONE
COURS IA Dr DABONE
 Algorithme A*

Lexique
◼ Q : liste des noeuds en attente de traitement, triés par f croissant,
◼ extratListe prendra à chaque fois le noeud le moins cher par
rapport à f
◼ C : liste des noeuds traités
◼ n : noeud courant
◼ napppartientpas : fonction qui vérifie que n∉ C ou a un coût
inférieur au même nC (atteint par un autre chemin)
◼ extraSucceurs : fonction qui extrait du graphe d’état tous les
successeurs d’un noeud
◼ trierListe(S,f) : trie S par rapport à f(n) = g(n)+h(n)
◼ mergeListe(Q,S,f) : fusionne Q et S en triant Q/f

COURS IA Dr DABONE
 Algorithme A*

◼ Complétude : oui sauf s’il y a un nombre infini de noeuds

avec une valeur de f<=(G), G:but
◼ Complexité en temps : exponentielle
◼ Complexité en en espace : garde tous les nœuds en
mémoire
◼ Optimalité : oui

COURS IA Dr DABONE
 Exemple

◼ Écrire l’algorithme puis le programme permettant trouver le

chemin optimal de sortie d’un labyrinthe
◼ Trouver une représentation du labyrinthe en termes
d’espace d’état, puis appliquer à la recherche une
heuristique

COURS IA Dr DABONE
Chapitre 3: Algorithme
Pour jeux
 1. Caractéristiques des jeux

◼ Les deux adversaires (O et H) jouent à tour de rôle,

◼ La situation globale du jeu est connue de chacun des
joueurs,
◼ La chance n’intervient pas,
◼ Le jeux sont dits ”`a somme nulle” : les gains d’un joueur
représentent exactement les pertes de l’autre joueur.

COURS IA Dr DABONE
 2. Les algorithmes et les jeux

◼ Complexité : dimension de l’espace d’ états

◼ Morpion : facteur de branchement ≈ 3, nb de demi-coups = 9
au plus dimension ≈ 39 = 19683
◼ Echec : facteur de branchement ≈ 35, nb de demi-coups ≈ 30

dimension ≈ 3530 ! !
◼ Nécessité d’une profondeur maximale de résolution
◼ Nécessité d’une fonction d’ évaluation pour estimer les
noeuds non feuilles
◼ Evaluation `a partir d’un joueur fixe : convention minimax
◼ Evaluation `a partir du joeur ayant le trait : convention

negamax
◼ Chaque joueur joue le coup de gain maximal pour lui, en
sachant que, et en prenant en compte que, l’adversaire fera
de mêmeDr DABONE
COURS IA
 Les algorithmes et les jeux

Le déroulement de la partie peut être vu comme un arbre :

◼ la racine correspond à l'état actuel du jeu ;
◼ les noeuds à profondeur paire correspondent aux noeuds
où J1 doit jouer, à profondeur impaire les noeuds où c'est à
J2 ;
◼ chaque arc correspond à un coup joué et lie un état où ce
coup est autorisé à l'état résultant de l'application du coup ;
◼ aux feuilles, nous trouvons les fins de partie : les états
gagnants ou perdants pour J1, ou encore les états bloqués
(matches nuls) ;
◼ un chemin allant de la racine à une feuille décrit une partie
possible.

COURS IA Dr DABONE
 3. Algorithme Min-Max

On prend la convention suivante :

◼ une situation gagnante pour J1 vaut +1 ;
◼ une situation perdante pour J1 vaut -1 ;
◼ une situation nulle vaut 0.

◼ On développe complètement l'arbre de jeu, on note chaque

feuille avec sa valeur, puis on fait remonter ces valeurs
avec l'hypothèse que chaque joueur choisit le meilleur coup
pour lui. Cela signifie en pratique que :
◼ J1 choisit le coup amenant à l'état de plus grande valeur ;
◼ J2 choisit le coup amenant à l'état de plus petite valeur.

COURS IA Dr DABONE
 Algorithme Min-Max

◼ Exemple : Jeu de Nim pour 3 allumettes

COURS IA Dr DABONE
 Algorithme Min-Max

◼ Remonter les évaluations depuis les feuilles jusqu'à la

racine (en bleu le Max, en vert le Min)

COURS IA Dr DABONE
 Algorithme Min-Max

◼ Combien le premier joueur doit enlever?

COURS IA Dr DABONE
 Algorithme Min-Max

◼ Insérer ici algorithme

COURS IA Dr DABONE
 Algorithme Min-Max

◼ L'algorithme MinMax effectue une exploration complète de

l'arbre de recherche jusqu'à un niveau donné, alors qu'une
exploration partielle de l'arbre est généralement suffisante :
lors de l'exploration, il n'est pas nécessaire d'examiner les
sous-arbres qui conduisent à des configurations dont la
valeur ne contribuera sûrement pas au calcul du gain à la
racine de l'arbre.
◼ Interrompre l'exploration de l'arbre avant d'avoir atteint des
fins de partie implique de pouvoir évaluer l'état du jeu à un
instant quelconque. Cela est rendu possible par l'utilisation
d'une fonction heuristique h(e,J) qui évalue la situation e
pour le joueur J.

COURS IA Dr DABONE
Zahia Guessoum
 6. Algorithme Alpha-Beta

◼ L'élagage alpha-beta est une technique permettant de

réduire le nombre de nœuds évalués par l’algorithme
Min_Max
◼ L’élagage αβ évite d'évaluer des nœuds de l'arbre de
recherche dont on est sûr que leur qualité sera inférieure à
un nœud déjà évalué.
◼ L'élagage αβ permet d'optimiser grandement l'algorithme
MinMax sans en modifier le ré[Link] est très utilisé dans le
cas des jeux à 2 joueurs, comme par exemple les échecs.

COURS IA Dr DABONE
 Algorithme Alpha-Beta

◼ L'élagage alpha-beta est une technique permettant de

réduire le nombre de nœuds évalués par l’algorithme
Min-Max
◼ L’élagage αβ évite d'évaluer des nœuds de l'arbre de
recherche dont on est sûr que leur qualité sera
inférieure à un nœud déjà évalué.
◼ L'élagage αβ permet d'optimiser grandement
l'algorithme MinMax sans en modifier le résultat. Il est
très utilisé dans le cas des jeux à 2 joueurs, comme par
exemple les échecs.

COURS IA Dr DABONE
 Algorithme Alpha-Beta

◼ On distingue deux types de coupures, alpha et bêta,

illustrées ci-dessous.
◼ Exemple : arbre avec une racine max

COURS IA Dr DABONE
 Algorithme Alpha-Beta
◼ La valeur de la racine sera >= 25, en aucun cas elle ne
peut être inférieure car nous sommes sur un noeud MAX.
Or, la valeur remontée par son troisième fils<=17. La
valeur de la racine ne viendra pas de cette branche et on
peut se dispenser d'aller voir les derniers noeuds. Il s'agit
d'une coupe alpha.

COURS IA Dr DABONE
 Algorithme Alpha-Beta

◼ Coupe Beta

COURS IA Dr DABONE
 Algorithme Alpha-Beta
[Link]
◼ Exemple

COURS IA Dr DABONE
 Algorithme Alpha-Beta : Quelques
applications
◼ Les dames : Le programme Chinook basé sur un alpha-
bêta est devenu champion des Éts-Unis en 1992, puis
champion du monde en 1994. Ce joueur utilise également
une bibliothèque de fins de partie (tous les damiers
comportant 8 pièces ou moins).

◼ Les échecs : DeepBlue bat Kasparov en 1997. Depuis,

toutes les confrontations tournent systématiquement à
l'avantage de la machine. Utilisation de l'algorithme alpha-
bêta, le facteur de branchement vaut ici 40.

COURS IA Dr DABONE