Poly
Poly
Benjamin Monmege
2022/2023
Manuscrit relu par Sébastien Delecraz et les étudiants du cours à distance depuis 2018.
Cours enseigné en présentiel par Antonio E. Porreca, Sylvain Sené et Alessia Milani.
Licence CC-BY-NC-SA : Attribution - Pas d’Utilisation
Commerciale - Partage dans les Mêmes Conditions
2
Préface
Description de l’enseignement
L’objectif de cette unité d’enseignement est de découvrir différents aspects de la science
informatique, tant dans ces aspects de traitement de l’information que de l’étude du calcul.
Le cours sera illustré par l’étude de problèmes complexes concrets qu’on décompose en tâches
plus simples.
Compétences à acquérir
— Se servir aisément des bases de la logique pour valider ou réfuter un raisonnement.
— Être familiarisé avec les concepts fondamentaux de complexité et calculabilité.
— Utiliser les concepts fondamentaux de l’informatique (langages formels, logique, et
graphes) pour la programmation et la modélisation.
— Évaluer la complexité et la correction d’une solution algorithmique.
— Modéliser un problème concret sous la forme d’un problème algorithmique connu.
— Concevoir le traitement informatisé d’informations de différentes natures, telles que du
texte, des images et des nombres.
avec examen terminal de deux heures, sans document ni calculatrice. La note de contrôle
continu contient le résultat de deux devoirs à la maison :
— devoir 1 : envoi le 6 décembre 2021, à rendre avant le 11 février 2022
— devoir 2 : envoi le 14 février 2022, à rendre avant le 15 avril 2022
3
4
Table des matières
1 Introduction 7
1.1 Mais la ≪ science informatique ≫, c’est quoi ? . . . . . . . . . . . . . . . . . . 9
1.2 Codage de l’information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3 La science du calcul . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.4 Algorithmes... ou algo-rythmes ? . . . . . . . . . . . . . . . . . . . . . . . . . 27
5
6 TABLE DES MATIÈRES
7 Arbres 121
7.1 Exemples d’arbres déjà rencontrés . . . . . . . . . . . . . . . . . . . . . . . . 121
7.2 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
7.3 Arbres binaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
7.4 Affichage d’une arborescence de fichiers : parcours préfixe . . . . . . . . . . . 128
7.5 Expressions arithmétiques et parcours postfixe . . . . . . . . . . . . . . . . . 132
7.6 Parcours infixe : affichage d’une expression . . . . . . . . . . . . . . . . . . . 138
7.7 Arbres binaires de recherche . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
8 Calculabilité 145
8.1 Arbres de décision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
8.2 Automates finis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
8.3 Applications des automates finis . . . . . . . . . . . . . . . . . . . . . . . . . 154
8.4 Langage non accepté par un automate fini . . . . . . . . . . . . . . . . . . . . 157
8.5 Des automates vers les machines . . . . . . . . . . . . . . . . . . . . . . . . . 158
8.6 Machines de Turing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
8.7 Lien entre machines de Turing et pseudo-code . . . . . . . . . . . . . . . . . . 170
8.8 Peut-on tout calculer ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
9 Conclusion 177
Chapitre 1
Introduction
la ≪ science informatique ≫
la ≪ pensée calculatoire ≫ (ou ≪ computational thinking ≫ en anglais)
Afin de clarifier l’objectif du cours, commençons par noter que l’informatique c’est à la fois
une technologie et une discipline scientifique. C’est une technologie en ce sens qu’elle abrite le
développement de logiciels (conception, développement, test...), d’ordinateurs (architecture,
stockage...), le tout rendu possible grâce à des matériaux (silicium) et beaucoup d’électronique
(micro-composants). Mais c’est aussi une discipline scientifique à part entière : c’est la science
de l’information et du calcul. C’est une discipline proche, mais différente, des mathématiques.
Voici une image pour mieux appréhender la distinction entre la technologie et la discipline
scientifique :
≪ Demander à un·e chercheur·se en informatique de réparer la souris d’un ordi-
nateur, c’est comme demander à un·e chercheur·se en mécanique des fluides de
réparer des toilettes bouchées. ≫
Comme toute discipline scientifique, l’informatique a donc des savant·e·s clés : quelques-
un·e·s d’entre eux·elles sont représenté·e·s en Figure 1.1. En haut à gauche, George Boole
1. dont je suis également l’enseignant responsable, à partir de la rentrée 2022
7
8 Les savants clés CHAPITRE 1. INTRODUCTION
est le père de la logique binaire (avec deux valeurs 0/faux et 1/vrai), à la base du codage
informatique. En haut à droite, Ada Lovelace est souvent reconnue comme l’auteure du pre-
mier programme informatique lors de son travail sur l’ancêtre de l’ordinateur, la machine
analytique de Charles Babbage. Au milieu, Alan Turing a posé les bases de la calculabilité
à travers la mise en place d’un modèle théorique de machines, ensuite appelés la machine de
Turing : il a aussi joué un rôle majeur dans la cryptanalyse de la machine Enigma pendant
la seconde guerre mondiale. En bas à gauche, John Von Neumann a travaillé à l’axiomati-
sation logique des mathématiques, mais il a aussi donné son nom à une architecture (unité
de contrôle, mémoire, unité arithmétique et logique) utilisée dans la quasi-totalité des ordi-
nateurs modernes. Il est également à l’origine du concept d’automates cellulaires, un modèle
de calcul inspiré par la biologie. En bas à droite, Claude Shannon est le père fondateur de la
théorie de l’information qui régit la communication d’information entre deux machines : il a
popularisé l’usage du mot bit comme mesure élémentaire de l’information numérique.
Les premiers ordinateurs modernes datent !è de la seconde guerre mondiale et de ses be-
soins accrus en calcul (cryptanalyse, calculs de trajectoires...). Trois ordinateurs sont ainsi
représentés en Figure 1.2 : observez la taille importante de ces ordinateurs qui remplissaient
alors des pièces entières. Notez également la présence de femmes sur les photographies, qui
rappelle que les premières à programmer des ordinateurs étaient des femmes, ce qui s’est
malheureusement perdu au fil du temps. Le film Hidden Figures (en français, Les figures
de l’ombre) de Theodore Melfi illustre bien ce fait historique au travers de l’histoire de la
mathématicienne et ingénieure spatiale américaine Katherine Johnson, ayant permis d’auto-
matiser les calculs de trajectoires à l’aide de machines.
stocker
recevoir Information émettre
traiter
(cf,
Quels sont les points
Figure 1.3 – La science de l’information, telle que vue par Michel
Serres par exemple, [Link]
communs entre…?
communication-de-m-michel-serres)
— on dit à son téléphone ≪ Dis Siri, définis calculer ≫ et on veut que le téléphone aille
chercher dans un dictionnaire la définition du verbe ≪ calculer ≫ pour nous l’imprimer
sur l’écran, ou mieux, nous la lise à haute voix ;
— on tape ≪ restaurant Marseille ≫ dans la barre de Google et on s’attend à voir s’afficher
une carte avec les meilleurs restaurants de la cité Phocéenne.
Nous verrons plus tard une définition plus détaillée de calcul, mais pour l’instant, cela nous
suffira. En tout cas, cela nous permet de nous poser la question suffisante : mais comment un
ordinateur sait ce que ≪ vingt-trois ≫ veut dire ?
La représentation décimale est pratique pour nous, puisque nous avons 10 doigts : nous
pouvons donc nous aider de nos mains pour compter. Mais d’ailleurs, jusqu’à combien peut-on
compter sur une main ? Une réponse naturelle consiste à répondre 5. Une autre réponse, a
priori moins naturelle, consiste à préférer 31 en utilisant davantage de combinaisons de nos
doigts levés ou pas. . . Pour cela, on doit passer d’une représentation décimale des entiers, à
une représentation binaire, c’est-à-dire en base 2. Suivons la figure 1.5 pour compter de 0 à
31 :
— naturellement, on part de 0 qu’on représente avec la main fermée ;
— tout aussi naturellement, on représente 1 en levant le pouce ;
— un peu d’originalité : représentons 2 en abaissant le pouce, mais en relevant l’index ;
— puis 3 est obtenu en relevant le pouce ;
— la représentation de 4 n’est pas des plus élégantes, avec le seul majeur levé ;
— et 5 s’obtient en levant à nouveau le pouce.
On continue ainsi en passant d’un entier à l’autre
— en levant le pouce s’il est baissé,
12 CHAPITRE 1. INTRODUCTION
317 = 300 + 10 + 7
= 3 × 102 + 1 × 101 + 7 × 100
C’est donc tout naturellement que la séquence 100111101 représente en binaire l’entier :
1 × 28 + 1 × 25 + 1 × 24 + 1 × 23 + 1 × 22 + 1 × 20
= 256 + 32 + 16 + 8 + 4 + 1
= 317
Définition 1. Un bit est l’unité d’information la plus simple, pouvant prendre deux valeurs
communément notée 0 et 1. On représente l’entier naturel 0 avec le bit 0. On représente un
entier naturel non nul a ∈ N∗ = {1,2,3, . . .} par une suite de bits an−1 an−2 · · · a1 a0 , avec
a0 ,a1 , . . . ,an−2 ,an−1 ∈ {0,1}, telle que an−1 = 1 et
n−1
X
n−1 n−2 1 0
a = an−1 × 2 + an−2 × 2 + · · · + a1 × 2 + a0 × 2 = ai 2i
i=0
Cette suite est unique, grâce à la condition sur an−1 : on l’appelle la représentation binaire
de l’entier a.
n 0 1 2 3 4 5 6 7 8 9 10
n
2 1 2 4 8 16 32 64 128 256 512 1024
Lorsqu’on fait des calculs en puissance de 2, on approche donc souvent 210 avec 103 .
Exercice 1
Exercice 2
Un ordinateur sait calculer des opérations arithmétiques sur les représentations binaires
d’entiers.
1. Saurez-vous additionner les représentations binaires 101001 et 1111010 ? Vérifier
votre calcul en convertissant les représentations en entiers.
2. Poser de même la multiplication des représentations binaires 10110 et 1011.
3. Effectuer à l’aide des représentations binaires le calcul de 15 × 15.
Exercice 3
Soit n un entier dont la représentation binaire est de la forme 100 · · · 001 (des bits 0
encadrés par deux bits 1). Quelles sont les représentations binaires des entiers n2 et
n3 ?
Exercice 4
Incrémenter, c’est ajouter un à un compteur. Par exemple, lorsqu’on incrémente un
compteur dont la valeur est 13, on obtient la valeur 14. Lorsque le compteur est
représenté en binaire, on passe ainsi de 1101 à 1110. Il existe une méthode infaillible
pour incrémenter la représentation binaire d’un compteur :
(i) commencer par le bit de poids faible (celui qui est le plus à droite) ;
(ii) inverser le bit ;
(iii) tant que ce bit est à zéro, recommencer l’étape (ii) avec le bit situé à sa gauche ;
(iv) si on arrive au bout de la représentation binaire, ajouter un bit 1.
1. Exécuter cette méthode sur les représentations binaires 11011, 1000 et 11111.
2. Sachant que décrémenter, c’est retirer un d’un compteur ayant une valeur stric-
tement positive, décrire une méthode qui réalise cette opération.
3. Décrire de même une méthode pour multiplier par deux la valeur d’un compteur.
Transcendants
Algébriques
Constructibles
Rationnels sin(1)
ψ
1,2 √
3 2
5
√
−7 1+ 5 cos(π/9)
0 2
e
√
3
5
entiers relatifs (cf Figure 1.6). Coder un nombre rationnel r ∈ Q n’est pas très compliqué,
une fois qu’on se rappelle qu’il s’agit d’un quotient r = a/b avec a ∈ Z un entier relatif et
b ∈ N∗ un entier naturel non nul. On a donc vu comment représenter a et b précédemment :
fort de cette abstraction, on peut donc représenter le rationnel r comme une paire (a,b).
Mais on utilise finalement assez peu les nombres rationnels, et on préfèrerait pouvoir écrire
des ≪ nombres à virgule ≫ plus généraux en binaire. Par exemple, de même que le nombre 3,14
vaut 3+ 1011 + 1042 , en binaire on peut écrire le nombre à virgule 1,011 valant 1+ 201 + 212 + 213 . On
est cependant encore limité. Par exemple, les physiciens ont souvent besoin de pouvoir encoder
des grands entiers ou des nombres rationnels sous la forme de leur notation scientifique, tel
que le nombre d’Avogadro par exemple qui décrit le nombre d’entités élémentaires (atomes,
molécules ou ions) dans une mole de matières :
s m × 2k
— 8 bits pour l’exposant k : l’exposant est un entier relatif entre −126 et 127 qu’on
représente par l’entier naturel k + 127 qui est donc compris entre 1 et 254 (avec 8 bits,
on peut aussi représenter les deux exposants 0 et 255, qui sont cependant réservés pour
des situations exceptionnelles telles que +∞, −∞, etc.) ;
— et 23 bits pour le nombre m qu’on appelle mantisse : puisqu’on représente m en binaire
et qu’on le choisit dans l’intervalle [1; 2[, le nombre avant la virgule vaut toujours 1 et
on ne le stocke donc pas en machine, utilisant ainsi les 23 bits pour les chiffres après
la virgule.
10101001111001000110000000000000
1 1 1 1 1 210 + 29 + 28 + 25 + 2 + 1 1827
1+ + 2 + 5 + 9 + 10 = =
2 2 2 2 2 210 1024
Mais pourquoi fait-on ce décalage de +127 pour calculer l’exposant ? On a vu que l’ex-
posant est codé sur 8 bits : on a donc toutes les possibilités entre 00000000 et 11111111,
c’est-à-dire entre 0 et 255. On a ainsi 256 codages possibles pour l’exposant. Puisqu’on veut
pouvoir avoir des exposants positifs et d’autres négatifs, on répartit ces 256 codages possibles
entre les négatifs et les positifs : on choisit arbitrairement d’aller de −127 à 128. Oui mais
voilà, la convention IEEE-754, qui a en charge de mettre tout le monde d’accord sur le format
des nombres flottants, en a décidé autrement : elle s’est réservée les deux extrémités (−127 et
128) pour des usages exceptionnels, en particulier pour écrire le nombre 0,0 (on décide alors
de l’encoder avec 32 bits à 0), des flottants qui ne sont pas des nombres (lorsqu’on vient de
faire une division par zéro interdite par exemple) et + ou − l’infini... Ainsi, on se restreint
à l’intervalle [−126; 127]. Maintenant, il faut représenter ça sur 8 bits : pour faire simple, on
décale tout de 127, pour arriver à l’intervalle [1,254] qui est donc codé par les codages binaires
de 00000001 à 11111110 (réservant les codes extrémaux 00000000 et 11111111 pour les usages
exceptionnels).
Exercice 5
Trouver le réel représenté par la séquence 01001110001100110100000000000000.
Exercice 6
Comment représente-t-on en binaire le réel 2−126 (qui est proche de 1,18 × 10−38 ) sur
32 bits ? Et l’entier 7 ? Et le réel 7,0 sur 32 bits ?
position : l’écriture commence donc par 0,0001... et l’imprécision restante est de 0,1−0,0625 =
0,0375. Puisque 215 = 0,03125, la prochaine puissance de 2 doit être prise : l’écriture binaire
commence donc par 0,00011... et il reste 0,0375 − 0,03125 = 0,00625 = 0,1 × 214 . On voit
réapparaı̂tre le nombre 0,1 duquel on était parti, signe qu’on s’apprête à écrire un nombre
infini de chiffres après la virgule (comme lorsqu’on essaie d’écrire le rationnel 1/3 comme un
chiffre à virgule en décimal...). Pour être plus précis, résumons nos calculs précédents avec
l’équation
1 1 1
0,1 = 4 + 5 + 0,1 × 4
2 2 2
dans laquelle on peut remplacer le 0,1 à droite par cette même écriture
1 1 1 1 1 1 1 1 1 1 1
0,1 = 4 + 5 + 4
+ 5 + 0,1 × 4 × 4
= 4 + 5 + 8 + 9 + 0,1 × 8
2 2 2 2 2 2 2 2 2 2 2
0,00011001100110011 . . .
1,1001100110011001100110011 . . . × 2−4
0 01111011 10011001100110011001100
1. Quel est le plus grand entier qu’on peut représenter en binaire sur 32 bits ?
2. Quel est le plus grand réel qu’on peut représenter sur 32 bits ? Et le plus petit
(négatif) ?
3. Quel est le plus petit réel strictement positif qu’on peut représenter sur 32 bits ?
04/10/2018 18(16
18 CHAPITRE 1. INTRODUCTION
Decimal Hex Char Decimal Hex Char Decimal Hex Char Decimal Hex Char
68 101 115 115 105 110 101 45 109 111 105 32 117 110 32 109 111 117 116 111 110 46
En réalité, évidemment, on ne stocke pas des entiers en décimal, mais bien des entiers
codés en binaire, chacun sur 7 bits : par exemple, le tiret ≪ - ≫ est donc codé par la séquence
de bits 0101101, où on a donc ajouté un 0 en premier pour utiliser les 7 bits à disposition.
Puisque chaque caractère est codé sur 7 bits, on a donc pas besoin de ≪ séparer ≫ les codages
de chaque caractère (comme ci-dessus).
1.2. CODAGE DE L’INFORMATION 19
Il existe d’autre façons de coder des caractères : citons par exemple d’autres tables, telles
que l’UTF-8 (ou UTF-16, ou UTF-32) ou sa généralisation, l’Unicode, permettant de coder
bien davantage de caractères (les caractères accentués ou les caractères d’autres alphabets
que l’alphabet latin).
Exercice 8
Dans cet exercice, nous allons considérer les deux codages de la Figure 1.8 pour les 27
symboles d’un texte (les 26 lettres de l’alphabet plus l’espace) qui associent à chaque
symbole un mot binaire. Par exemple le mot ≪ patate ≫ se code 01000 1010 0110 1010
0110 110 avec le codage variable et 01111 00000 10011 00000 10011 00100 avec le codage
fixe. Il est à noter que les espaces entre les codes des différentes lettres sont présents
uniquement pour la lisibilité et ne font pas partie du code.
1. Coder votre nom avec les deux codages. Quel est le codage qui utilise le plus de
bits ?
20 CHAPITRE 1. INTRODUCTION
coder un entier entre 0 et 255, on a donc besoin de 8 bits. Cette quantité de bits se retrouve
souvent en informatique :
Définition 3. Une séquence de 8 bits s’appelle un octet.
On utilise les octets pour rendre également plus lisible la représentation des entiers. Par
exemple, l’entier 108 a pour représentation binaire 101111101011110000100000000. C’est bien
difficile à lire ! De la même façon qu’on peut séparer les chiffres par groupes de 3 dans
l’écriture décimale d’un nombre (par exemple, 100 000 000), on choisit de séparer les bits
de la représentation binaire par groupes de 8 : 101 11110101 11100001 00000000. On utilise
souvent l’octet comme unité de capacité mémoire de disques dans le commerce : 256 Go si-
gnifie ainsi 256 Giga octets, soit 256 milliards d’octets, ce qui représente donc 256 × 8 = 2048
milliards de bits.
Exercice 9
Environ 25 000 étudiants sont inscrits à l’UFR Sciences de l’université d’Aix-Marseille.
Un numéro est attribué à chaque étudiant. Bien évidemment, deux étudiants différents
ne doivent pas avoir le même numéro.
1. Combien de bits sont nécessaires pour coder un de ces numéros ?
2. Les logiciels utilisés ont l’octet comme unité de mémoire. Combien d’octets sont
nécessaires pour coder un numéro d’étudiant ?
3. L’administration de l’université souhaite que les programmes mis au point pour
gérer l’inscription et la scolarité des étudiants puissent servir 10 ans. Si l’on
pense que la fréquentation de l’université peut augmenter au plus de 20% chaque
année, combien d’octets faut-il réserver pour coder les numéros des étudiants ?
Exercice 10
Le cerveau humain a environ 100 milliards de neurones qui ont chacun en moyenne
10 000 synapses transmettant environ 100 impulsions binaires par seconde. Calculer la
quantité d’information maximale transmise par seconde dans un cerveau, en octets.
Revenons au codage des images. Stocker une image de 1920 par 1200 pixels nécessite de
représenter 1920 × 1200 = 2 304 000 pixels, chacun prenant 3 octets en mémoire : au total,
cette image prend donc 6 912 000 octets, soit 55 296 000 bits, ce qui équivaut à 55 Mégabits.
C’est beaucoup pour une simple image... En pratique, on ne stocke donc que rarement les
images en format bitmap : on utilise plutôt des formats compressés qui essaient d’épargner de
la mémoire en profitant de redondances dans l’image ou en supprimant des détails invisibles
à l’œil nu.
Exercice 11
On souhaite effectuer des dessins sur une grille carrée comprenant 64x64 cases (ou
pixels). Chaque point est repéré par un couple d’entiers (x,y) où x et y sont compris
entre 0 et 63. On supposera que x et y sont écrits en binaire.
1. Combien faut-il de bits pour coder un point ?
On suppose que les dessins seront composés de trois types d’éléments : des
segments, des rectangles dont les côtés sont parallèles aux axes et qui pourront
être pleins ou vides. Ainsi, le dessin de la Figure 1.10 est composé d’un rectangle
vide ADJI, d’un rectangle plein BCF E et de deux segments GK et KH.
22 CHAPITRE 1. INTRODUCTION
63
I J
G E F H
AB C D
0
0 63
— Un segment AB dont les extrémités ont pour coordonnées (xA ,yA ) et (xB ,yB )
sera représenté par 4 octets 01xA 01yA 01xB 01yB .
— Un rectangle vide ABCD dont deux sommets opposés sont A et C sera
représenté par 4 octets 10xA 10yA 10xC 10yC .
— Un rectangle plein ABCD dont deux sommets opposés sont A et C sera
représenté par les 4 octets 11xA 11yA 11xC 11yC .
— Un dessin est représenté par la suite des représentations des éléments qui le
compose.
On remarque donc qu’on peut savoir si un octet code un élément d’un segment
s’il commence par 01, un élément d’un rectangle vide s’il commence par 10 et
un élément d’un rectangle plein s’il commence par 11.
2. Combien faut-il de bits pour représenter le dessin de la figure ? Combien cela
fait-il en octets ?
3. Indiquez quel dessin est représenté par le codage suivant 10001111 10001111
10101111 10101111 01001111 01001111 01101111 01101111 01001111 01101111
01101111 01001111
On suppose que les 64 × 64 = 4096 pixels de la grille sont numérotés selon un
ordre conventionnel (par exemple de gauche à droite et de haut en bas). Dans
une représentation bitmap, un dessin (en noir et blanc) est représenté par une
suite de bits b1 · · · bn dont le i-ième bit bi est égal à 0 si le i-ième pixel du dessin
est blanc et 1 s’il est noir.
4. Combien faut-il d’octets pour représenter le dessin de la figure dans une
représentation bitmap ?
On souhaite enrichir les codages possibles en représentant directement des lignes
brisées A1 A2 . . . Ak (c’est-à-dire des réunions de segments A1 A2 , A2 A3 , . . .,
Ak−1 Ak ).
5. Indiquez comment on pourrait étendre le codage ci-dessus pour représenter
de telles lignes brisées ? (Indication : les extrémités de la ligne pourront être
1.3. LA SCIENCE DU CALCUL 23
repérées par 01 et les points intérieurs par 00. Combien faudrait-il alors de bits
pour représenter le dessin de la figure ? )
≪ Étant donné un problème avec des entrées et des opérations élémentaires auto-
risées, peut-on calculer le résultat ? ≫
Il y a des résultats qu’on peut calculer... et d’autres non !
Mais y a-t-il vraiment des problèmes interessants qui sont incalculables (on dit aussi
indécidables) ? La réponse est oui, et beaucoup même ! C’est ce qu’on verra à la fin de ce
cours. Un exemple célèbre est celui du problème de l’arrêt d’une machine de Turing (le même
Turing que celui dont nous avons parlé plus tôt) : on ne peut pas décider si une machine de
Turing (ou un programme) termine ou tourne en boucle.
3
5 6 5 6
8 cercles et 4 segments 8 cercles et 4 segments 8 cercles et 4 segments
Figure 1.14 – Trois méthodes pour obtenir un carré 4 fois plus grand : le carré initial est en
noir, le carré final est surligné en jaune
— si on veut trier un tableau de 30 entiers, il faut calculer 2,65 × 1032 permutations dans
le pire des cas, ce qui demande 3 × 1015 ans environ sur un ordinateur de fréquence 3
GHz, déjà plus long que l’âge de l’univers ;
— si on veut trier un tableau de 100 entiers (par exemple, si on veut trier les 100 res-
taurants à Marseille par distance croissante à notre position, lors de notre recherche
sur internet), il faut calculer 9,33 × 10157 permutations dans le pire des cas, ce qui
demande 10141 ans environ sur un ordinateur de fréquence 3 GHz.
On voit bien sur cet exemple qu’il nous faut mesurer la complexité de notre solution afin
d’en trouver une meilleure pour trier un tableau d’entiers : nous étudierons de meilleures
méthodes pour cela, plus tard dans ce cours.
•
1.4. ALGORITHMES...
Résoudre lesOU ALGO-RYTHMES
tâches ?
simples et ciblées avec des algorithmes 27
Figure 1.15 – Tricot d’un pull tricolore à partir de brins de laine emmêlés
démêler les brins pour ne considérer que des pelotes de laine de différentes couleurs : c’est la
phase d’abstraction. On décompose ensuite la tâche complexe de tricot d’un pull bicolore en
tâche plus simples : il faudra ainsi tricoter une manche bleue, un corps gris et une manche
rouge, avant de coudre le tout ensemble.
Des tâches complexes plus réalistes, en terme d’informatique, sont décrites en Figure 1.16
et 1.17. On ajoute à la phase d’abstraction et à l’algorithme à proprement parler une phase
de visualisation qui est le résultat observé par l’utilisateur : un plus court chemin du cam-
pus St Charles au Vieux Port, ou le tri des restaurants de Marseille par leur note moyenne
décroissante.
n
io
ct
vis
ra
st
ua
« Aller du campus St Charles
ab
lis
au Vieux Port »
ati
Durée en
on
minutes 6
10 7
Figure 1.16 – Calcul du plus court chemin dans Google Maps : on abstrait le problème à
l’aide d’un graphe avec des nœuds représentant les intersections de rue et des arcs reliant ces
nœuds avec la durée en minutes du trajet correspondant
n
io
vis
ct
ra
ua
lis
ab
( )
PN : 4,5
C : 4,6
D : 4,55
Figure 1.17 – Tri des restaurants par note moyenne décroissante : la seule information
pertinente à conserver ici est le nom du restaurant et sa note moyenne. La visualisation
consiste alors à réordonner effectivement les restaurants une fois qu’ils ont été triés
1.4. ALGORITHMES... OU ALGO-RYTHMES ?Algorithmes… ou algo-rythmes
29 ?
Un algorithme est
2. définition précise
3. entrées : données
1.4.1 Dénombrement
Illustrons le concept d’algorithme à l’aide d’un problème concret, celui de compter le
nombre de personnes dans une salle (par exemple une salle de concert ou un amphithéâtre à
l’université). Il existe de multiples méthodes pour opérer ce dénombrement. Le plus simple est
qu’une personne compte un par un les personnes de la salle. Il peut aussi choisir de compter
les personnes deux par deux, ou même cinq par cinq. Le nombre d’opérations élémentaires
qu’il effectue diffère dans ces trois cas :
— lorsqu’il compte un par un, il effectue autant d’additions qu’il y a de personnes dans
la salle, disons n personnes ;
— lorsqu’il compte deux par deux, il effectue n/2 additions ;
— lorsqu’il compte cinq par cinq, il effectue n/5 additions.
Au prix de savoir faire des additions deux par deux ou cinq par cinq rapidement, on
voit bien qu’on effectue moins de calculs en comptant cinq par cinq qu’en comptant deux
par deux, et que cette dernière technique effectue moins de calculs que celle qui consiste à
compter un par un. Une représentation du nombre d’opérations en fonction de n peut être
vue en Figure 1.19.
Une autre méthode de dénombrement consiste, si les personnes sont assises, à compter le
nombre R de rangées de sièges et à estimer le nombre M moyen de personnes par rangée :
il ne reste alors plus qu’à effectuer la multiplication R × M pour obtenir une estimation
du nombre de personnes. Contrairement aux méthodes précédentes, celle-ci n’apporte qu’une
réponse approximative : elle n’est pas (absolument) correcte. Par contre, elle est bien plus
30 CHAPITRE 1. INTRODUCTION
n/5
rapide encore.
Dans les méthodes précédentes, plutôt que de tout faire tout seul, la personne en charge
du comptage pourrait se faire aider : plus on est nombreux à travailler, moins de temps la
tâche prendra. En informatique, c’est l’utilisation des multiples cœurs d’un processeur que
nous pouvons utiliser en parallèle pour accélérer la résolution d’un problème.
Une autre façon de paralléliser, beaucoup plus massive, consiste à distribuer le calcul sur
les personnes présentes dans la salle. Considérons ainsi l’algorithme suivant :
Entrée : des personnes debout dans une salle
— Chaque personne a en tête le nombre 1
— Tant qu’il reste au moins deux personnes debout :
• chaque personne encore debout cherche du regard une autre per-
sonne debout
• les deux personnes s’échangent le nombre qu’ils ont en tête
(indépendamment des autres personnes)
• l’une des deux personnes s’assoit ; l’autre additionne les deux
nombres et reste debout
Sortie : la dernière personne debout crie son nombre
Cet algorithme est correct au sens où il se termine avec une seule personne encore debout,
et que le nombre crié est effectivement le nombre de personnes dans la salle. Combien de temps
prend-il pour terminer ? Cette fois-ci, plutôt que le nombre total d’additions effectuées, une
meilleure estimation du temps d’exécution consiste à compter le nombre d’itérations effectuées
par l’algorithme. Dis autrement, si on suppose que toutes les secondes, chaque personne encore
debout en a trouvé une autre et que l’une des deux s’est assise, alors il s’agit de compter le
nombre de secondes avant la fin de l’algorithme. Il n’est pas très difficile de se convaincre
qu’à chaque seconde, la moitié environ des personnes encore debout s’assoit. Par conséquent,
après k secondes, le nombre de personnes encore debout a été divisé par 2k . Lorsque k devient
supérieur à log2 (n), le nombre de personnes debout a été divisé par 2log2 (n) = n : il ne reste
alors plus qu’une seule personne encore debout. Ainsi, il faut log2 (n) secondes pour que cet
1.4. ALGORITHMES... OU ALGO-RYTHMES ? 31
n/5
temps nécessaire n n/2
n
log2 (n)
Figure 1.20 – Comparaison des fonctions linéaires (en rouge, vert et bleu) avec la fonction
logarithme (en orange)
algorithme termine. La fonction logarithme croit beaucoup plus lentement que les fonctions
linéaires trouvées précédemment. Dans la Figure 1.20, on peut observer que lorsque n est
suffisamment grand, la courbe de la fonction log2 passe en dessous des courbes des fonctions
n 7→ n, n 7→ n/2 et n 7→ n/5. En particulier, s’il y a 200 personnes dans la salle et que chaque
opération élémentaire (addition ou itération) nécessite une seconde :
— la méthode consistant à compter un par un nécessite 200 secondes, soit 3 minutes et
20 secondes ;
— la méthode consistant à compter deux par deux nécessite 100 secondes, soit 1 minutes
et 40 secondes ;
— la méthode consistant à compter cinq par cinq nécessite 40 secondes ;
— la méthode distribuée nécessite log2 (200) secondes, soit 7 secondes environ : imbat-
table !
3 1
2 2
4 3
1 4
Figure 1.21 – Un réseau de tri (à gauche) et une des ses exécutions (à droite) : un réseau
de tri est composé de fils horizontaux dans lesquels des entiers glissent de gauche à droite, et
des fils verticaux, appelés comparateurs, qui permettent d’échanger les deux valeurs si jamais
celle du haut est supérieure à celle du bas. Ce réseau est un réseau de tri dans le sens où tout
quadruplet d’entiers placé à gauche ressort à droite du réseau de façon triée.
Chapitre 2
Nous allons décrire les algorithmes à l’aide du langage Python dans la suite, sans être
très strict, à l’écrit, sur une syntaxe parfaite. 1 Nous utiliserons des variables, chaque instruc-
tion élémentaire sera écrite sur une ligne séparée, le code sera indenté et nous découperons
notre code en fonctions. Commençons par décrire dans ce chapitre les structures de contrôle
permettant de structurer le pseudo-code.
Sortons du labyrinthe…
1. Jusqu’à l’an dernier, ce cours utilisait du pseudo-code pour écrire les algorithmes. Nous préférons changer
à partir de maintenant, pour faciliter le lien avec l’UE de Mise en œuvre informatique.
opérations élémentaires :
avancer de 50
avancer de 100
tourner de 90 degrés
tourner de 90 degrés
33
34 CHAPITRE 2. DESCRIPTION DES ALGORITHMES
avancer de 100
tourner de 90 degrés
avancer de 50
tourner de 90 degrés
avancer de 100
tourner de 90 degrés
avancer de 50
tourner de 90 degrés
avancer de 100
tourner de 90 degrés
avancer de 50
tourner de 90 degrés
avancer de 100
Ce code n’est que moyennement lisible et réutilise trois fois la même séquence d’opérations.
On peut le simplifier grandement en utilisant une boucle permettant de répéter un certain
nombre de fois la même séquence d’opérations :
répéter 3 fois
avancer de 100
tourner de 90 degrés
avancer de 50
tourner de 90 degrés
avancer de 100
répéter indéfiniment
stop tout
2.1. STRUCTURES DE CONTRÔLE : UNE INTRODUCTION EN SCRATCH 35
avancer de 100
tourner de 90 degrés
avancer de 50
tourner de 90 degrés
avancer de 100
Le code principal se raccourcit alors beaucoup. Si de plus on fait dire au chat une petite
phrase une fois qu’il a atteint la cible avant de repartir, le code devient
faire des L 3
Il se peut que l’utilisateur ne veuille pas que ce code tourne indéfiniment, et donc avoir
une possibilité de l’arrêter. Par exemple, on pourrait demander à l’utilisateur son avis, puis
attendre sa réponse pour prendre une décision. En utilisant une conditionnelle supplémentaire
pour tester sa réponse (qui est automatiquement stocké dans un bloc réponse ) et réagir
différemment si l’utilisateur souhaite continuer ou non, le code devient
36 CHAPITRE 2. DESCRIPTION DES ALGORITHMES
répéter indéfiniment
faire des L 3
sinon
stop tout
Finalement, équipons le chat d’un podomètre, comptant le nombre de pas qu’il a effectué
au total depuis le début de l’exécution du programme. Pour ce faire, il nous faut stocker ce
nombre de pas dans ce qu’on appelle une variable : nommons-là ≪ distance parcourue ≫ pour
clarifier sa signification. Une fois la variable créée, on peut la modifier et ajouter à son contenu
une valeur entière, par exemple. Cela permet donc de modifier la fonction ≪ faire des L ≫ pour
qu’elle enregistre dans la variable les modifications :
départ
répéter n fois
avancer de 100
tourner de 90 degrés
avancer de 50
tourner de 90 degrés
avancer de 100
faire des L 3
Maintenant que nous avons vu l’utilité des différentes structures de contrôle en Scratch,
2.2. VARIABLES 37
2.2 Variables
L’utilisation de variables permet l’écriture de programmes stockant des données. Atten-
tion, le mot variable a deux sens, selon qu’on l’utilise dans son acception mathématique ou
informatique :
— En mathématiques, une variables est une grandeur dont la valeur est (provisoirement)
indéterminée, sur laquelle on effectue une combinaison d’opérations avec des constantes
et d’autres variables. Par exemple, on peut considérer la variable x dans l’équation
x2 − 3x + 2 = 0. Elle n’a pas de valeurs, mais pourra en avoir une ou plusieurs une fois
l’équation résolue : en l’occurrence, l’équation à deux solutions x = 1 ou x = 2.
— En informatique, une variable est un identifiant désignant un emplacement de la
mémoire et son contenu peut donc évoluer au cours du temps. Si une variable n’est
pas initialisée, sa valeur est temporairement non définie. Par exemple, on dénote par
x = 1
l’affectation de la valeur 1 dans la variable x.
Considérons ainsi un programme qui enchaı̂ne plusieurs affectations sur trois variables a, b
et c :
a = 7
b = 3
c = b−a
a = a−c
Au début de l’exécution du programme, le contenu de chaque variable est indéfini :
a b c
a b c
7 indéfini indéfini
a b c
7 3 indéfini
La troisième instruction c = b − a s’exécute alors en deux temps : d’abord les valeurs des
variables b et a sont extraites, puis on effectue l’opération de soustraction avant de modifier
le contenu de la variable c :
a b c
7 3 -4
a b c
11 3 -4
Notez que cela n’a donc rien à voir avec la résolution de l’équation mathématique
a=a−c
qui se résoudrait en c = 0...
Considérons un deuxième exemple de code :
a = 9
c = a+b
b = c
c = 2
Une fois la première ligne exécutée, on est dans la situation suivante :
a b c
9 indéfini indéfini
2.3. FONCTIONS 39
2.3 Fonctions
Considérons un autre exemple nécessitant l’usage de variables. On se donne ainsi les coor-
données GPS d’un restaurant et d’un client (en train de faire sa recherche Google Maps pour
trouver un restaurant à Marseille...). Pour simplifier, supposons ici que ces coordonnées GPS
sont données par une abscisse et une ordonnée dans un repère bidimensionnel orthonormé.
On note ainsi x restaurant et y restaurant les coordonnées du restaurant, x client et
y client celles du client. En se rappelant que la distance entre un point de coordonnées
(x1 , y1 ) et un point de coordonnées (x2 , y2 ) est donné par la formule
p
d((x1 , y1 ),(x2 , y2 )) = (x1 − x2 )2 + (y1 − y2 )2
on peut écrire le code suivant pour obtenir la distance entre le restaurant et le client :
dx = x_restaurant - x_client
dy = y_restaurant - y_client
distance_carr é e = dx * dx + dy * dy
distance = sqrt ( distance_carr é e )
dans lequel on a utilisé les opérations arithmétiques -, +, * et sqrt pour la soustraction, l’addi-
tion, la multiplication et le calcul de racine carrée (accessible après l’import de la bibliothèque
math en Python).
S’il y a 100 restaurants dont on veut connaı̂tre la distance au client, il faut donc répéter
100 fois ces mêmes quatre lignes, en modifiant les coordonnées du restaurant. Ce serait bien
répétitif, source d’erreurs et difficilement maintenable si on décide désormais de changer de
représentation pour les coordonnées GPS. À la place, il vaut mieux utiliser une fonction.
Attention, comme pour le mot variable, le mot fonction a deux sens selon qu’on l’utilise
dans son acception mathématique ou informatique :
— En mathématiques, une fonction est une relation entre un ensemble d’entrées et un
ensemble de sorties avec la propriété que chaque entrée est reliée à au plus une sor-
tie. La fonction peut souvent être décrite par une expression utilisant des variables
représentant les entrées. Par exemple, on peut considérer la fonction f qui a un entier
x associe f (x) = x2 + 2x.
— En informatique, une fonction est une portion de code représentant un sous-programme,
qui effectue une tâche ou un calcul relativement indépendant du reste du programme.
Une fonction peut avoir des arguments représentés par des variables que le code de la
fonction peut utiliser, et peut renvoyer un résultat.
Ainsi, on peut écrire une fonction qui calcule la distance entre un restaurant et un client :
— il prend en entrée les coordonnées du restaurant et du client
— et produit en sortie la distance attendue.
En Python, on déclarera une fonction de la façon suivante :
def calcule_distance ( x_restaurant , y_restaurant , x_client , y_client ) :
dx = x_restaurant - x_client
dy = y_restaurant - y_client
distance_carr é e = dx * dx + dy * dy
distance = sqrt ( distance_carr é e )
return distance
40 CHAPITRE 2. DESCRIPTION DES ALGORITHMES
Le mot clé def est suivi du nom de la fonction qu’on définit, ainsi que ses arguments en
parenthèses et deux points en fin de ligne : les arguments sont des variables dont la valeur est
donnée lors de l’utilisation de la fonction et qu’on peut utiliser dans le corps de la fonction.
On utilise le mot clé return pour renvoyer le résultat attendu. Cela arrête l’exécution de la
fonction : on ne peut donc retourner qu’au plus une fois par fonction.
On peut alors calculer la distance entre plusieurs restaurants et plusieurs clients en appe-
lant la fonction préalablement définie :
distance1 = calcule_distance ( x_restaurant1 , y_restaurant1 ,
x_client , y_client )
distance2 = calcule_distance ( x_restaurant2 , y_restaurant2 ,
x_client2 , y_client )
distance3 = calcule_distance (5.12 , 145.1 , 5.45 , 148.3)
Noter l’utilisation d’un point pour séparer la partie entière et décimale des flottants en
Python, plutôt qu’une virgule dans la notation traditionnelle française.
2.4 Conditionnelles
Comment faire exécuter deux choses différentes à notre code selon qu’un restaurant est à
moins de deux kilomètres d’un client ou pas ?
distance ≤ 2km ?
oui non
Il nous faut écrire une condition dans le pseudo-code, suivie de deux possibilités suivant
que la condition est satisfaite ou non :
if distance <= 2:
# afficher restaurant ...
else :
# masquer restaurant ...
On a utilisé au-dessus des lignes commençant par le symbole # : il s’agit de commentaires
permettant d’inscrire du texte qui ne sera pas utilisé lors de l’exécution du code. Ici, cela
permet de cacher les détails d’implémentation permettant l’affichage ou le masquage d’un
restaurant. Notez l’utilisation des deux points après le test et après le else, ainsi que l’in-
dentation qui suit. Le test en lui-même est obtenu par une comparaison de la valeur d’une
variable et de la constante entière 2. On utilise le symbole <= pour la comparaison ≪ inférieur
ou égal ≫.
Quelles sont les conditions que l’on peut tester ?
— Comparaisons : on peut comparer une variable avec une valeur ou une autre variable
distance <= 2
distance > 3
distance == 2.5
x != y
2.5. ITÉRATIONS 41
— Combinaison de tests : on peut combiner les tests avec les opérateurs and, or et not.
Si on cherche à n’afficher que les restaurants proches et ayant au moins 1 étoile, on
exécute
(distance <= 2) and (nombre_étoiles >= 1)
Si on préfère ne voir que les restaurants qui sont très proches ou alors qui peuvent être
plus éloignés mais ont au moins 2 étoiles, on utilisera plutôt
(distance < 1) or (nombre_étoiles >= 2)
2.5 Itérations
On l’a vu en Scratch, il est souvent utile de répéter une séquence d’opérations plusieurs
fois. Plutôt que de copier-coller le morceau de code, on utilise des boucles permettant d’itérer
ce morceau de code. Contrairement à l’exemple simpliste en Scratch, on a souvent besoin
de connaı̂tre le nombre i d’itérations qui ont été déjà exécutées avant pour exécuter un code
différent, dépendant de ce nombre i. Par exemple, essayons d’écrire le code calculant la somme
des entiers de 1 à 1000. La façon naı̈ve consiste à utiliser le code suivant (qu’on n’a pas écrit
en entier...) :
somme = 0
somme = somme + 1
somme = somme + 2
somme = somme + 3
...
somme = somme + 1000
Le nombre d’opérations élémentaires (si on compte l’addition comme une opération élémen-
taire et l’affectation comme une autre opération élémentaire) effectuées par ce code est 2001,
puisqu’il y a 1000 sommes et 1001 affectations. C’est long et pénible à écrire. À la place, on
peut utiliser une boucle for qui exécute la même instruction pour toutes les valeurs de la
variable décrite dans la boucle :
42 CHAPITRE 2. DESCRIPTION DES ALGORITHMES
somme = 0
for n in range (1 , 1001) :
somme = somme + n
La fonction range prend deux arguments a et b et permet de générer tous les entiers de a
jusqu’à b − 1 (attention ! on s’arrête un coup avant la borne). Il est possible de n’écrire qu’un
seul argument si l’on souhaite générer plutôt les entiers de 0 à b − 1 : range(b).
Notez qu’on exécute exactement le même nombre d’opérations élémentaires, 2001 dans ce
cas, mais ce code est bien plus court et lisible que le code précédent.
Évidemment il existe une solution bien plus simple pour réaliser ce calcul, puisqu’on
connaı̂t une formule mathématique pour calculer la somme des premiers termes d’une suite
arithmétique de raison 1 et de premier terme 1 :
1000
X 1000 × 1001
1 + 2 + · · · + 1000 = n= = 500 × 1001 = 500500
2
n=1
Cependant, la boucle s’avère indispensable lorsqu’on ne connaı̂t pas de telles formules.
Par exemple, si on souhaite calculer la somme des entiers de 1 à 1000 qui sont divisibles par
3 ou par 5, on pourra utiliser le code
somme = 0
for n in range (1 , 1001) :
if ( n % 3 == 0) or ( n % 5 == 0) :
somme = somme + n
Notez l’absence de else dans la condition précédente : puisqu’on a rien à faire dans ce
cas, Python nous permet de ne pas écrire le mot-clé.
Le nombre d’opérations élémentaires est un peu plus important dans ce cas. Pour chaque
itération de la boucle for, on exécute 2 tests sur n suivi d’une disjonction (or), suivi, dans
le pire des cas, d’une somme et d’une affectation : au total, chaque itération exécute donc au
plus 5 opérations élémentaires. Puisqu’il y a 1000 itérations dans la boucle, le nombre total
d’itérations est de 5000, auquel on ajoute la toute première affectation.
Exercice 13
On cherche à calculer la somme des n premières puissances de 2. Par exemple, si n = 6,
le résultat est 20 + 21 + 22 + 23 + 24 + 25 = 1 + 2 + 4 + 8 + 16 + 32 = 63.
1. Écrire une première fonction réalisant ce calcul, en s’autorisant le calcul des
puissances de 2 comme opération élémentaire (en Python, on écrit par exemple
2**i pour calculer 2i ), écrire un algorithme calculant et affichant la somme des
n premières puissances de 2.
2. Combien d’opérations élémentaires effectue votre fonction lorsqu’elle est appelée
avec un entier n en argument (en fonction de n) ?
3. Comment modifier votre code si on ne s’autorise plus l’utilisation de 2**i comme
opération élémentaire ? Calculer à nouveau le nombre d’opérations en fonction
de n.
n−1
X
0 1
4. En calculant explicitement la valeur de S = 2 + 2 + · · · + 2 n−1 = 2i en
i=0
déduire une façon de calculer S avec un seul calcul de puissance et un nombre
constant d’opérations élémentaires (additions, soustractions, multiplications...)
supplémentaires.
2.6. LECTURE ET ÉCRITURE 43
On a parfois besoin d’écrire des boucles for qui égrène les éléments en sens inverse, ou
qui saute d’un pas de plus de 1. Par exemple, si on veut réaliser des opérations pour tous les
entiers entre 1 et 100 en commençant par le plus grand, on utilisera :
for n in range (100 , 0 , -1) :
...
On utilise donc toujours la même fonction range mais avec trois arguments : le premier est
le début de l’énumération, le second est l’entier suivant la fin de l’énumération voulue, et le
troisième est le pas. Dans le cas d’un pas p négatif, range(a, b, p) permet donc de générer
les entiers a, a − p, a − 2p, jusqu’au dernier entier a − kp qui est strictement supérieur à b.
Si on souhaite ne visiter que les entiers pairs entre 2 et 200 (c’est-à-dire 2, 4, 6, . . . , 198, 200),
on utilisera :
for n in range (2 , 201 , 2) :
...
On ne peut cependant pas utiliser directement ce genre de boucles lorsqu’on ne connaı̂t
pas à l’avance le nombre de tours de boucles à exécuter 2 . Un exemple typique est illustré par
le calcul du nombre d’étapes avant de tomber sur la face 5, lors de tirages répétés d’un dé.
En supposant qu’on dispose d’une fonction lancer dé() ne prenant aucun argument (d’où
les parenthèses vides) et renvoyant une face entre 1 et 6 tirée de manière aléatoire, on peut
trouver le nombre d’étapes attendues avec le code suivant :
nombre_ é tapes = 0
face = lancer_d é ()
while face != 5:
face := lancer_d é ()
nombre_ é tapes = nombre_ é tapes + 1
On utilise donc une boucle while qui continue à exécuter le contenu de la boucle tant que
la condition entre parenthèse reste vérifiée : ici, on continue tant qu’on n’est pas tombé sur la
face 5. De manière générale, on sort donc de la boucle lorsque la condition n’est pas satisfaite
au début d’une itération de la boucle.
Structures de contrôle
itérations fonctions
def abc(arguments):
for .. in range(..):
..
..
return ..
écriture/lecture variables
x = 3
print(« .. »)
y = 2
réponse := input()
x = x + y
Figure 2.2 – Syntaxe pour les structures de contrôle, dans les pseudo-codes de ce cours
permet d’afficher la consigne, d’attendre que l’utilisateur écrive un entier, et on affiche alors
l’entier auquel on a ajouté 2 en expliquant auparavant à l’utilisateur ce qu’on va afficher. Si
l’utilisateur entre l’entier 8, il verra alors s’afficher le message :
En résumé, les structures de contrôle que nous utiliserons dans ce cours sont rappelées en
Figure 2.2.
Exercice 14
Écrivons du code Python pour jouer au jeu du juste prix.
1. Écrire un algorithme qui :
— choisit aléatoirement un nombre entier entre 0 et 1000 de manière parfai-
tement opaque pour l’utilisateur, à l’aide de la fonction randint (qu’on
suppose inclus en Python depuis la bibliothèque random) prenant deux ar-
guments entiers a et b et renvoyant un nombre aléatoire dans l’intervalle
[a,b] ;
— demande à l’utilisateur d’entrer des nombres entiers jusqu’à ce que ce der-
nier trouve le nombre préalablement choisi, en indiquant à chaque tentative
2.6. LECTURE ET ÉCRITURE 45
Exercice 15
Rappelons-nous qu’un nombre premier est un nombre entier supérieur ou égal à 2 qui
n’est divisible que par 1 et par lui-même.
1. Écrire une fonction est premier prenant en argument un entier n et qui renvoie
un booléen qui est True si n est premier, False sinon. Si besoin, la partie entière
d’un entier peut être calculée à l’aide de la fonction floor en Python.
2. Écrire une fonction qui prend un entier i en argument et retourne le i-ième
nombre premier, qu’on appellera pi dans la suite, en s’aidant de la fonction
précédente (sachant que 2 est le premier nombre premier, que 3 est le second,
etc.) : lorsque i > 1, vous utiliserez une boucle qui énumère tous les entiers
impairs (en effet, inutile d’essayer les entiers pairs, puisque le seul premier pair
est 2).
3. Jusqu’en 1536, on croyait que les nombres de Mersenne, c’est-à-dire les nombres
de la forme 2p − 1, avec p premier, étaient premiers. À partir des fonctions
écrites en réponse aux deux questions ci-dessus, écrire un algorithme qui montre
l’invalidité de la conjecture d’avant 1536. L’algorithme devra écrire :
— à partir de quel nombre premier pm la conjecture est fausse (c’est-à-dire tel
que 2pm − 1 n’est pas premier) ;
— à quel rang m se trouve pm dans la liste des nombres premiers.
46 CHAPITRE 2. DESCRIPTION DES ALGORITHMES
Chapitre 3
Pour écrire des algorithmes, il faut des structures de contrôle telles que définies dans le
chapitre précédent et des structures de données permettant de stocker des données de manière
lisible. Illustrons ce concept au travers de quatre exemples représentés en Figure 3.1 :
— si les données à stocker sont des cartes à jouer, on préfèrera par exemple les ranger dans
un certain ordre dans sa main : on utilise alors un tableau (comme dans un tableau
Excel) pour les stocker de gauche à droite ;
— si les données sont des clients attendant d’être servis, on préfèrera les placer dans une
file d’attente : c’est aussi une structure de tableau comme précédemment, mais avec la
propriété fonctionnelle supplémentaire que le premier arrivé dans la file sera le premier
servi ;
— si les données sont des assiettes dans un meuble de cuisine, on préfèrera les stocker
dans une pile : contrairement à la file (d’attente), c’est l’assiette rangée en dernier (en
haut de la pile) qui sera réutilisée la première ;
— finalement, si les données sont des pièces du jeu d’échec, pour pouvoir jouer, on
préfèrera les ranger sur un échiquier qui est une matrice (un tableau bidimensionnel)
de 8 rangées sur 8 colonnes.
Dans ce cours, nous n’étudierons en détail que la structure de tableau, et nous utiliserons
à l’occasion la structure de matrice.
17 64 5 1 38
’a’ ’l’ ’g’ ’o’ ’r’ ’i’ ’t’ ’h’ ’m’ ’e’
47
Pour écrire des algorithmes,
matrice
tableau bidimensionnel
t = [5, 6, 8, 1, 0]
C’est pour
cela qu’on notera les tableaux de la façon suivante : t[0], t[1], t[2], t[3], . . . , t[n−
2], t[n − 1] . Classiquement, on commence à numéroter les cases d’un tableau à partir de 0,
de sorte que la dernière case a le numéro n − 1 (et pas n) : la i-ième case du tableau t
(avec 0 ≤ i ≤ n − 1) contient une valeur qu’on note t[i]. On peut donc voir un tableau de
longueur n contenant des éléments d’un ensemble E (des entiers, des caractères, etc.) comme
une application t : {0, 1, . . . , n − 2, n − 1} → E associant à chaque indice i une valeur notée
t[i] dans E.
Dans les algorithmes que nous allons écrire, on pourra :
— récupérer la longueur (length en anglais) d’un tableau t à l’aide de
n = len ( t )
— initialiser un tableau de longueur n rempli d’une constante (par exemple 0) à l’aide de
t = [0] * n
— accéder au contenu de la i-ème case d’un tableau t à l’aide de t[i]
— modifier le contenu de la i-ème case d’un tableau t à l’aide de
t[i] = x
Exercice 16
1. On se donne trois variables entières a, b et c. Quel algorithme (on ne demande
pas d’écrire une fonction, jusque quelques lignes de Python) permet d’effectuer
une permutation circulaire vers la droite de ces trois variables, c’est-à-dire de
faire en sorte qu’à la fin, a contienne la valeur originelle de c, b la valeur de a
et c la valeur de b ?
2. Comment faire de même avec un tableau t = t[0], t[1], . . . , t[n − 1] de n entiers,
plutôt que trois variables ?
3. Combien d’opérations élémentaires (affectations, opérations arithmétiques) sont
exécutées par votre algorithme en fonction de la longueur n du tableau ?
’a’ ’l’ ’g’ ’o’ ’r’ ’i’ ’t’ ’h’ ’m’ ’e’
permet de représenter la chaı̂ne de caractères ≪ algorithme ≫. Grâce à cela, nous allons être en
mesure d’écrire des algorithmes manipulant des chaı̂nes de caractères. Un domaine d’applica-
tion où c’est très utile est la cryptologie (étymologiquement, science du secret), un domaine
50 CHAPITRE 3. ALGORITHMES SUR LES STRUCTURES LINÉAIRES
Cela nous permet de revenir sur le codage de César (cf exercice 3.2) de manière un peu
plus précise. On peut donc stocker le message en clair, ainsi que le message chiffré, à l’aide
de tableaux de caractères. Comment peut-on écrire un algorithme procédant au chiffrement
d’un message ?
Tout d’abord, comme on l’a vu précédemment, on code les caractères (’a’, ’b’, . . ., ’z’) avec
des entiers. Supposons ici que la lettre ’a’ est codée par l’entier 0, la lettre ’b’ par l’entier 1,
etc. On se donne alors une fonction code(c) permettant de connaı̂tre le code d’un caractère
c et une fonction caractère(p) renvoyant le caractère dont le code est p (seulement s’il est
entre 0 et 25). On a par exemple
À l’aide de ces deux fonctions, on peut donc écrire un algorithme procédant au chiffrement
d’un message :
def c hiffre ment_C esar ( message , cl é ) :
n = len ( message )
chiffr é = [ ’a ’] * n
for i in range ( n ) :
p = code ( message [ i ])
p_d é cal é = ( p + cl é ) % 26 # on d é cale puis on revient
# dans l ’ intervalle [0 ,25]
chiffr é [ i ] = caract è re ( p_d é cal é )
return chiffr é
Cette fonction prend en entrée le message à chiffrer, ainsi que la clé de César qui est un entier
correspondant au nombre de lettres pour le décalage. Elle commence par stocker dans la
variable n la longueur du message. Elle crée ensuite un autre tableau de caractères, chiffré,
3.2. TABLEAUX ET CHAÎNES DE CARACTÈRES : APPLICATION À LA CRYPTOLOGIE51
pour contenir le message chiffré qui est donc de longueur n. Elle l’initialise avec des caractères
arbitraires. Ensuite, chiffrer un message consiste à parcourir les caractères du message les uns
après les autres et, pour chacun d’entre eux, appliquer le décalage donné par la clé, avant de
mettre le caractère chiffré dans la case correspondante du tableau chiffré : pour parcourir
le message, on utilise une boucle for avec un range permettant à l’indice i de prendre les
valeurs de 0 à n − 1. À la sortie de la boucle, on retourne le tableau chiffré.
Exercice 18
1. Exécuter l’algorithme précédent pour trouver ce que retourne l’appel
chiffrement Cesar([’i’,’n’,’t’,’o’,’x’], 3). Pour exécuter la boucle
for, on utilisera le tableau suivant :
i message[i] p p décalé chiffré
avant la boucle [’a’, ’a’, ’a’, ’a’, ’a’]
0 ’i’ 8 ?? ??
1 ?? ?? ?? ??
2 ?? ?? ?? ??
..
.
2. L’algorithme précédent ne prend pas en charge les espaces auxquels
on ne souhaite pas apporter de décalage. Ainsi, on aimerait que
chiffrement Cesar([’u’,’n’,’ ’,’d’,’e’,’u’,’x’], 3) renvoie le tableau
[’x’, ’q’, ’ ’, ’g’, ’h’, ’x’, ’a’]. Modifier l’algorithme précédent
pour y parvenir.
3. Proposez un algorithme de déchiffrement, prenant en entrée le message chiffré et
une clé et renvoyant le message décodé. À titre d’exemple, déchiffrez le message
≪ kajex ≫ sachant que la clé de chiffrement vaut 9.
sans avoir recours formellement aux tableaux. Ces exercices sont donc plutôt d’ordre culturel
et peuvent donc être passés lors d’une lecture rapide du chapitre.
Exercice 20
Dans l’armée de Spartes (autour du Vème siècle avant J.-C.), les militaires étaient
parfois amenés à se transmettre des messages chiffrés. Pour ce faire, ils utilisaient un
bâton, appelé bâton de Plutarque (ou scytale). L’émetteur du message prenait une fine
lanière de tissu ne pouvant contenir qu’une seule lettre dans sa largeur, l’enroulait en
spirale autour d’un bâton, et écrivait son message ligne par ligne dans la longueur du
bâton de façon à avoir toutes les lignes remplies sauf éventuellement la dernière ligne :
Une fois déroulée, la lanière contenait le message chiffré. Pour déchiffrer ce message,
le récepteur devait posséder un bâton de même diamètre (ayant le même nombre de
circonvolutions) que celui de l’émetteur. Ce type de codage est un chiffrement par
transposition.
À titre d’exemple, considérons le message suivant : ≪ La vie c’est comme une boı̂te
de chocolats, on ne sait jamais sur quoi on va tomber. ≫ (Forrest Gump, de Ro-
bert Zemeckis) Considérons un bâton dont le périmètre permet 6 circonvolutions
(nous dirons pour simplifier que la clé du chiffrement est 6). Le message chiffré
est alors ≪ Lo moamdoan meni ve svi cn aeuhes no utcecsro’ oa mebliqbsoatuetı̂
t or [Link],a ≫
1. Chiffrez la phrase ≪ Les cons ça ose tout. ≫ (Les tontons flingueurs, Michel
Audiard) avec la clé 4 en vous aidant d’un ruban de papier que vous enroulerez
autour d’un stylo par exemple. (C’est plus facile à faire à deux...)
2. Proposez une méthode décrivant ce procédé de chiffrement. En particulier, com-
ment déterminer le nombre de colonnes à utiliser sur le bâton ? Illustrez votre
méthode en chiffrant la phrase de la question précédente avec les clés 3 et 5.
3. Étant donné un message chiffré m de longueur n et une clé c, donnez un algo-
rithme permettant de découvrir le message d’origine.
4. Déchiffrez les messages suivants :
— “Ce’e’ oceànos ntçln aeam siêq tmur.” avec c = 4 ;
— “Càq s’ up emea ?so r titl ue ” avec c = 5 ;
— “L, snru s [Link]̀ ” avec c = 6.
5. À présent, vous recevez un message chiffré m sans la clé de chiffrement. Don-
nez un algorithme permettant de retrouver le message d’origine et évaluez-en
l’efficacité en termes de temps.
3.2. TABLEAUX ET CHAÎNES DE CARACTÈRES : APPLICATION À LA CRYPTOLOGIE53
a b c d e f g h i j k l m n o p q r s t u v w x y z
a a b c d e f g h i j k l m n o p q r s t u v w x y z
b b c d e f g h i j k l m n o p q r s t u v w x y z a
c c d e f g h i j k l m n o p q r s t u v w x y z a b
d d e f g h i j k l m n o p q r s t u v w x y z a b c
e e f g h i j k l m n o p q r s t u v w x y z a b c d
f f g h i j k l m n o p q r s t u v w x y z a b c d e
g g h i j k l m n o p q r s t u v w x y z a b c d e f
h h i j k l m n o p q r s t u v w x y z a b c d e f g
i i j k l m n o p q r s t u v w x y z a b c d e f g h
j j k l m n o p q r s t u v w x y z a b c d e f g h i
k k l m n o p q r s t u v w x y z a b c d e f g h i j
l l m n o p q r s t u v w x y z a b c d e f g h i j k
m m n o p q r s t u v w x y z a b c d e f g h i j k l
n n o p q r s t u v w x y z a b c d e f g h i j k l m
o o p q r s t u v w x y z a b c d e f g h i j k l m n
p p q r s t u v w x y z a b c d e f g h i j k l m n o
q q r s t u v w x y z a b c d e f g h i j k l m n o p
r r s t u v w x y z a b c d e f g h i j k l m n o p q
s s t u v w x y z a b c d e f g h i j k l m n o p q r
t t u v w x y z a b c d e f g h i j k l m n o p q r s
u u v w x y z a b c d e f g h i j k l m n o p q r s t
v v w x y z a b c d e f g h i j k l m n o p q r s t u
w w x y z a b c d e f g h i j k l m n o p q r s t u v
x x y z a b c d e f g h i j k l m n o p q r s t u v w
y y z a b c d e f g h i j k l m n o p q r s t u v w x
z z a b c d e f g h i j k l m n o p q r s t u v w x y
Exercice 21
Revenons sur le codage de César. Le principal point faible de ce codage par décalage
provient justement du type de décalage qui est identique quelle que soit la position de
la lettre décalée dans le message d’origine.
1. Comment pourrait-on transformer le codage de César pour qu’il soit plus difficile
à casser ?
L’objectif du codage de Vigenère est justement de remédier à ce défaut. Il a été décrit
pour la première fois au XVIème siècle C’est également un chiffrement par décalage,
mais la substitution est cette fois-ci poly-alphabétique. Cela signifie qu’une même lettre
dans le message d’origine peut, selon sa position dans ce dernier, être remplacée par
différentes lettres dans le message chiffré.
Plus précisément, ce nouveau chiffrement va utiliser une notion de clé différente des
précédents. Ici, la clé va être une suite de caractères, qui prend généralement la forme
d’un mot ou d’une phrase. Pour procéder au chiffrement, il faut parcourir le message
d’origine lettre après lettre tout en parcourant circulairement les lettres de la clé pour
effectuer la substitution. Bien sûr, plus la clé est longue et variée, plus le chiffrement est
solide. La substitution à opérer est donnée par la table illustrée en Figure 3.2 page 53,
appelée table de Vigenère, dans laquelle la première ligne correspond aux lettres du
message d’origine et la première colonne à celles de la clé.
Ainsi, on remplace chaque lettre ℓ du message m d’origine par celle contenue dans la
case (k,ℓ), avec k la lettre de la clé c correspondant à la position de ℓ dans m, modulo
|c|.
À titre d’exemple, le message “Peu lui importe de quoi demain sera fait” associé à la
clé “petit frère” sera chiffré de la manière suivante (en supprimant les accents) :
ce qui mène au message chiffré “Ein tnn zqgsgxx lx vlsz htqtqg xvvr jpmm”.
2. Soit le message d’origine “Chacun voit sa voie de toi à moi”. Chiffrez ce message avec
les deux clés suivantes : “ntm” et “de personne je ne serai la cible”. Qu’observez-
vous ?
3. Étant donné un message d’origine m et une clé c, donnez un algorithme de chiffre-
ment de m selon c.
4. Étant donné un message chiffré m et une clé c, donnez un algorithme de
déchiffrement de m selon c. Continuez en déchiffrant le message “Diepe dorr n’owg
naj k vrnnvr” avec la clé “keny arkana”.
3.3. RECHERCHER DANS UN TABLEAU 55
peu précise car pas nécessairement reproductible : l’humain ou l’ordinateur qui exécute l’al-
gorithme ne mettra pas toujours le même temps, selon qu’il est plus ou moins en forme, qu’il
a plus ou moins d’autres choses à penser ou à faire en même temps. De plus, on arriverait
alors pas à comparer les complexités d’algorithmes dont l’un serait exécuté par un humain et
l’autre par un ordinateur, ou par deux ordinateurs différents.
Pour remédier à ce problème, on utilise une autre méthode pour estimer la complexité d’un
algorithme : on compte plutôt le nombre d’opérations élémentaires que l’algorithme exécute
dans le pire des cas pour des entrées de taille fixée.
— Une opération élémentaire, cela correspond grosso modo à une ligne de pseudo-code :
de manière générale, il est important de se fixer un ensemble d’opérations élémentaires
qu’on comptabilise ensuite une par une lors de l’exécution de l’algorithme.
— La définition précise dans le pire des cas puisqu’on voudrait pouvoir décrire la com-
plexité de l’algorithme sur toutes les entrées possibles d’une taille fixée : mais il se peut
que, pour certaines entrées, le résultat soit très rapide à calculer, et que, pour d’autres,
ce soit beaucoup plus long. Pour régler ce problème, on considère donc le pire des cas
possibles, qui borne donc la complexité de toutes les instances d’une taille fixée.
Dans l’algorithme de recherche séquentielle, l’affectation de la longueur du tableau dans la
variable n peut être vue comme une opération élémentaire, de même que le test d’égalité entre
le contenu de la case d’indice i et l’élément à chercher, ou le fait de retourner un résultat.
On cherche donc à estimer le nombre de telles opérations élémentaires lorsque l’algorithme
s’exécute sur un tableau de longueur n arbitraire (n étant supposé grand).
— Dans tous les cas, on affecte à la variable n la longueur du tableau, ce qui coûte une
opération élémentaire.
— Une itération de la boucle for effectue une opération élémentaire (test d’égalité), et
au plus une fois au total le retour de la valeur de sortie True.
— Puisque dans le pire des cas (c’est-à-dire lorsqu’on cherche un élément qui n’apparait
pas dans le tableau), on exécute cette boucle n fois (une fois par case du tableau), au
total, on exécute donc n opérations (sans compter le retour).
— Finalement, dans tous les cas, on exécute soit le retour (de True) au sein de l’itération,
ou le retour (de Faux) en dehors de l’itération, qui coûte donc toujours une opération
élémentaire.
Au total, on exécute donc 1+n+1 opérations élémentaires dans le pire des cas, c’est-à-dire
n + 2 opérations élémentaires.
Considérons désormais le point de vue d’un tableau ≪ très long ≫, c’est-à-dire avec n
très grand. Dans ce cas, il n’est pas très intéressant de distinguer n + 2 de n : on préfère
donc conserver uniquement l’ordre de grandeur de la complexité. À ce titre, introduisons la
notation de Landau (du nom d’Edmund Landau qui l’a introduite) permettant de comparer
deux telles suites.
Définition 4. Soient u = (un )n∈N et v = (vn )n∈N deux suites à valeurs entières : les entiers un
et vn décrivent donc des nombres d’opérations élémentaires pour l’exécution d’un algorithme
dans le pire des cas sur une entrée de taille n. On dit que u est en O(v) (qui se lit ≪ grand o
de v ≫, comme la lettre de l’alphabet...) s’il existe un entier N et une constante c > 0 tels que
pour tout n ≥ N , on a un ≤ cvn . Dans la suite, on s’autorise à écrire que un est en O(vn ).
Par exemple, on obtient alors bien que n + 2 est en O(n) : en effet, pour N = 2 et c = 2,
on a bien que pour tout entier n ≥ 2, n + 2 ≤ n + n = 2n = cn.
3.3. RECHERCHER DANS UN TABLEAU 57
Dans ce cours, on considèrera donc que ≪ n + 2 ou n, c’est pareil ! ≫. On peut aller plus
loin et montrer qu’en fait, ≪ 2n ou n, c’est pareil ! ≫ : en effet, pour N = 0 et c = 2, on obtient
trivialement que pour tout n ≥ 0, 2n ≤ cn. En terme d’informatique, cela veut dire qu’un
algorithme A et un autre algorithme B qui va deux fois plus vite que A ne sont généralement
pas distingué en terme de complexité dans le pire des cas : fondamentalement, c’est parce
qu’il suffit d’avoir une machine deux fois plus puissante pour que B devienne aussi performant
que A.
Au contraire, n2 n’est pas en O(n), c’est-à-dire que n2 grossit beaucoup plus vite que n.
Vous pouvez le vérifier en montrant que vous ne pouvez pas trouver N et c vérifiant la
définition lorsque un = n2 et vn = n. Par contre, on a bien que n est en O(n2 ), mais ce n’est
pas très intéressant : cela veut juste dire que n grossit moins vite que n2 , mais on y perd donc
beaucoup en faisant cette approximation... L’ordre de grandeur d’une complexité de la forme
ak nk + ak−1 nk−1 + · · · + a2 n2 + a1 n + a0 (avec k fixé et ak ̸= 0) est donc en O(nk ), à savoir
le plus grand terme dans l’écriture polynomiale de la complexité.
Revenons alors à l’algorithme de recherche séquentielle dont on a vu qu’il exécutait dans
le pire des cas n + 2 opérations élémentaires. On dira donc qu’il a une complexité en O(n),
linéaire en la longueur du tableau en entrée. Si l’on recherche un mot dans un dictionnaire
contenant 32 000 mots par exemple, cela demande donc un nombre d’opérations de l’ordre de
32 000 : si on le fait ≪ à la main ≫, même si on pouvait exécuter 10 opérations à la seconde,
il nous faudrait alors 53 minutes pour rechercher un mot dans le dictionnaire...
On souhaite donc faire mieux en utilisant l’information qu’un dictionnaire, ou un annuaire,
n’est pas un tableau quelconque. En effet, les mots du dictionnaire, ou les noms de l’annuaire,
sont triés par ordre alphabétique croissant. On dit donc d’un tableau qu’il est trié si ses
éléments sont classés par ordre croissant : le tableau [1,4,5,8] est donc trié, contrairement au
tableau [8,3,4,5].
Exercice 23
d’un tableau trié et on commence par comparer l’élément qu’on recherche avec l’élément qui
se trouve au milieu (environ) du tableau. Partons du tableau trié d’entiers
1 4 5 7 8 9 10 14 17 25 26 27 38 47 56 64
et cherchons-y l’élément 26. On commence par regarder la case du milieu : le tableau étant de
longueur 16, le milieu du tableau correspond à la case d’indice 7 (les cases sont indexées de 0
à 15), qui héberge l’élément 14. Il est différent de 26 : il faut donc continuer notre recherche.
Par ailleurs, 14 est strictement inférieur à 26 : puisque le tableau est trié, cela implique que
l’élément 26 ne peut pas se trouver dans la portion du tableau à gauche de l’élément 14. On
peut donc se restreindre à rechercher 26 dans la partie non grisée du tableau :
1 4 5 7 8 9 10 14 17 25 26 27 38 47 56 64
Parmi les 8 éléments restants, on poursuit en comparant 26 avec l’élément du milieu du
tableau restant, la case contenant 27. Ces deux éléments sont toujours différents, mais cette
fois, la comparaison nous apprend que l’élément 26 ne peut pas se trouver dans la portion du
tableau à droite de l’élément 27. On se restreint ainsi à la portion non grisée du tableau
1 4 5 7 8 9 10 14 17 25 26 27 38 47 56 64
Il reste une portion de longueur 3, dont 25 est l’élément du milieu. Une fois de plus, on
supprime la partie de gauche de la portion restante pour ne laisser plus qu’une seule case qui
abrite l’élément 26 que nous recherchions :
1 4 5 7 8 9 10 14 17 25 26 27 38 47 56 64
Sur le même tableau en entrée, si l’on recherche l’élément 6, voici les étapes par lesquelles
on passe :
1 4 5 7 8 9 10 14 17 25 26 27 38 47 56 64
1 4 5 7 8 9 10 14 17 25 26 27 38 47 56 64
1 4 5 7 8 9 10 14 17 25 26 27 38 47 56 64
1 4 5 7 8 9 10 14 17 25 26 27 38 47 56 64
1 4 5 7 8 9 10 14 17 25 26 27 38 47 56 64
Cela nous permet de répondre avec certitude que le tableau de contient pas l’élément 6.
Voici une écriture sous forme de pseudo-code de l’algorithme que nous venons d’exécuter :
def r e c h e r c h e r _ d i c h o t o m i q u e ( tableau , é l é ment ) :
n = len ( tableau )
d é but = 0
fin = n - 1
while d é but <= fin :
milieu := ( d é but + fin ) // 2
if tableau [ milieu ] == é l é ment :
return True
elif tableau [ milieu ] < é l é ment :
# l ’é l é ment est à droite
d é but = milieu + 1
else : # l ’é l é ment est à gauche
fin = milieu - 1
return False
3.3. RECHERCHER DANS UN TABLEAU 59
Terminaison
La définition insiste sur la finitude : un algorithme doit terminer après un nombre fini
d’étapes. Est-on bien sûr que c’est le cas ici ? Dans cet algorithme, c’est l’utilisation d’une
boucle while qui pourrait faire échouer cette condition de terminaison de l’algorithme : il
se pourrait en effet que la condition d’arrêt de la boucle ne soit jamais vérifiée, l’algorithme
bouclant alors à l’infini. Pourquoi est-on certain ici que cela n’arrivera pas ? Il s’agit de
s’assurer que la boucle while termine, c’est-à-dire que le test début <= fin finit par devenir
faux. Autrement dit, il faut s’assurer qu’à un moment de l’algorithme, on finit par avoir
début > fin. C’est le cas, puisqu’à chaque étape de la boucle while :
— soit début augmente strictement ;
— soit fin diminue strictement.
Ainsi, à chaque itération fin − début diminue strictement : puisque c’est un entier, il finit
par devenir négatif. Le test début <= fin finit donc par être faux.
En général, prouver la terminaison d’une boucle while se fait par la mise au jour d’un
variant de boucle, c’est-à-dire une quantité entière positive ou nulle (dépendant des données
de l’algorithme) qui décroit strictement à chaque tour de boucle. Comme il n’existe pas de
suite infinie d’entiers strictement décroissante, on assure la terminaison de la boucle. Pour la
recherche dichotomique, le variant de boucle est fin − début.
Correction
L’utilisation d’une boucle while complique également notre intuition sur la correction de
l’algorithme : est-on sûr qu’il trouve bien un élément dès lors que celui-ci apparaı̂t dans le
60 CHAPITRE 3. ALGORITHMES SUR LES STRUCTURES LINÉAIRES
tableau et qu’il renvoie False uniquement lorsque l’élément ne s’y trouve pas ? S’assurer que
l’algorithme est correct, c’est montrer qu’il fait bien ce qu’il est sensé faire :
— si l’élément qu’on cherche se trouve dans le tableau trié, alors l’algorithme doit renvoyer
True ;
— si l’élément qu’on cherche ne se trouve pas dans le tableau trié, alors l’algorithme doit
renvoyer False : ceci est facile à montrer puisque l’algorithme ne peut renvoyer True
que s’il a trouvé un indice du tableau hébergeant l’élément recherché.
Concentrons-nous donc sur la première propriété. Pour s’assurer de cette propriété, on
écrit un invariant de boucle, c’est-à-dire une propriété qui est vraie initialement, et qui reste
vraie tout au long de l’algorithme. Ici, l’invariant de boucle est le suivant : si on suppose que
le tableau en entrée est trié par ordre croissant et contient l’élément recherché, alors à tout
moment de l’exécution de l’algorithme on est sûr qu’il existe un indice i entre début et fin
tel que tableau[i] = élément.
C’est vrai en début de boucle puisque début = 0 et fin = n − 1 donc la portion est le
tableau tout entier. On peut ensuite se convaincre que l’exécution d’une itération de la boucle
Tant que préserve la propriété, puisqu’on a simplement retiré une portion du tableau où l’on
est sûr que l’élément ne se trouve pas (c’est ici qu’on utilise le fait que le tableau est trié !).
Par le principe de récurrence (sur le nombre de tours de boucle), l’invariant de boucle est
donc vrai pendant toute l’exécution : en particulier, il est vrai lorsque l’on sort de la boucle
while (ce qui est sûr d’arriver puisque l’algorithme termine). Mais si l’on sort de la boucle
sans avoir jamais renvoyé True, on a alors début > fin et il n’existe plus aucun indice i entre
début et fin, contredisant la propriété qu’on a démontré.
Complexité
Pour terminer l’étude de cet algorithme, il ne nous reste plus qu’à trouver sa complexité,
pour la comparer avec celle de la recherche séquentielle qu’on a étudiée avant.
Supposons que le tableau a une longueur n = 2p pour simplifier le calcul. On cherche donc
le nombre d’opérations élémentaires exécutées par l’algorithme dans le pire des cas sur un
tableau de longueur 2p . Le pire des cas intervient lorsqu’on ne trouve pas l’élément dans le
tableau puisque la recherche ne s’interrompt alors pas prématurément. Ensuite, remarquons
que chaque itération de la boucle while exécute 5 opérations élémentaires dans le pire des
cas :
1. le test début <= fin ;
2. le calcul du nouveau milieu pour l’affectation de la variable milieu ;
3. le test tableau[milieu] == élément : le pire des cas se produit si ce test n’est pas
satisfait ;
4. le test tableau[milieu] < élément ;
5. l’affectation de la nouvelle valeur de début ou fin selon le cas.
Il reste donc à connaı̂tre le nombre d’itérations de la boucle while. On peut la déduire
en fonction de la longueur de la portion restante du tableau à explorer : cette longueur vaut
toujours fin − début + 1. À chaque itération, la taille de la portion restante de tableau est
au moins divisée par deux (d’où le nom de dichotomie !). Par conséquent,
— après 0 itération (au début), la longueur de la portion restante est 2p ;
— après 1 itération, la longueur de la portion restante est au plus 2p−1 ;
— après 2 itérations, la longueur de la portion restante est au plus 2p−2 ;
3.4. TRI D’UN TABLEAU 61
— ...
— après k itérations, la longueur de la portion restante est au plus 2p−k ;
— ...
— après p + 1 itérations, la longueur de la portion restante est au plus 2p−(p+1) = 1/2, et
puisqu’elle est entière, la longueur est nulle ; autrement dit le tableau est vide.
On est donc assuré qu’il y a au plus p + 1 itérations de la boucle while. Le nombre
d’opérations élémentaires exécutées par la boucle dans le pire des cas est donc d’au plus
5 × (p + 1).
Par ailleurs, en dehors de la boucle, l’algorithme exécute au plus 4 opérations élémentaires :
1. l’affectation de n ;
2. l’affectation de début ;
3. l’affectation de fin ;
4. le retour de la valeur True ou False.
Le nombre total d’opérations élémentaires est donc au plus 4 + 5 × (p + 1). Puisque n = 2p ,
on a p = log2 n, donc la complexité est en 4 + 5 × (log2 n + 1). Pour n supérieur à 2 (de sorte
que 1 ≤ log2 n), on a 4 + 5 × (log2 n + 1) ≤ 14 × log2 n. Ainsi, la complexité de la recherche
dichotomique est de l’ordre de O(log2 n), logarithmique en la longueur n du tableau.
Pour s’apercevoir de la différence cruciale entre une complexité linéaire (comme la re-
cherche séquentielle) et une complexité logarithmique (comme la recherche dichotomique),
observons que log2 (32 000) ≈ 15 ce qui veut dire que la méthode de la recherche dicho-
tomique permet de trouver n’importe quel mot du dictionnaire contenant 32 000 mots en
regardant au plus 15 pages du dictionnaire : à raison d’une page par seconde, cela donne le
mot en 15 secondes au plus (à comparer aux 53 minutes qu’on avait calculé précédemment
pour la recherche séquentielle). Lorsque n devient encore plus grand, l’écart est de plus en
plus important, puisque la suite (log2 n)n∈N∗ croit exponentiellement moins vite que la suite
(n)n∈N∗ . Même pour un tableau (trié) comprenant autant de cases que le nombre d’atomes
dans l’univers visible (environ 1079 ), on parvient tout de même à rechercher un élément en
un nombre d’opérations élémentaires de l’ordre de log2 (1079 ) ≈ 263.
Je décris ici ma façon de faire lorsqu’il s’agit de trier un nombre conséquent de cartes. Je
laisse le tas de cartes à trier face contre la table et prend les cartes les unes après les autres.
Je prends la première carte dans ma main. Je retourne ensuite la seconde carte que je viens
placer au bon endroit (avant ou après la première carte) dans ma main. Je retourne alors la
troisième carte que je dois de même insérer au bon endroit dans ma main. Lorsque j’arrive
à la treizième carte, il devient plus difficile de savoir où je dois l’insérer : si je décompose à
nouveau ma routine, je vois que je scanne la suite des cartes de droite à gauche jusqu’à trouver
l’endroit où je dois insérer la nouvelle carte. Essayez d’imiter ma méthode afin de classer un
paquet de treize cartes de carreau, en décomposant bien chaque étape en opérations les plus
simples possibles.
Cette procédure de tri s’appelle le tri par insertion du fait qu’on ne fait qu’insérer les
éléments les uns après les autres au bon endroit dans la portion triée. On peut également
l’appliquer pour trier un tableau. On suppose donc qu’on a en entrée de l’algorithme un
tableau non trié, par exemple, le tableau [10,8,2,5,13]. On considère les éléments de gauche à
droite, en cherchant à chaque fois à les placer au bon endroit dans la portion triée qui sera la
partie gauche du tableau. Initialement, on considère donc le premier élément du tableau (10)
qui est bien placé puisque c’est le seul élément considéré jusqu’alors. La portion triée est donc
[10,... et il reste le tableau ...8,2,5,13] à considérer. On regarde ensuite le second élément (8)
puis on le compare à l’élément à sa gauche, afin de l’insérer au bon endroit dans la portion
triée : ici 8 < 10 donc il faut échanger les deux éléments, ce qui termine l’insertion de 8 à sa
place. On se retrouve alors avec la portion triée [8,10,... et le reste du tableau ...2,5,13]. Au
coup suivant, on doit considérer l’élément 2 : il est inférieur à 10, donc on doit échanger sa
place avec 10 (temporairement on obtient donc le tableau [8,2,10,5,13]), puis on le compare
avec l’élément à sa gauche (8) pour arriver à la situation où la portion triée est [2,8,10,... et
le reste ...5,13]. L’insertion de 5 se fait alors en deux étapes : on échange les éléments 10 et
5, puis les éléments 8 et 5, avant de voir que 2 < 5 ce qui achève l’insertion de l’élément 5.
Finalement, on considère l’élément 13 qui est directement supérieur à l’élément à sa gauche
(10) stoppant dès le début son insertion. On termine donc avec le tableau trié [2,5,8,10,13].
Exécutez l’algorithme sur le tableau [8,2,10,5,13] pour bien comprendre comment il fonc-
tionne : vous verrez qu’il ne fait pas exactement ce qui est dit au-dessus en s’épargnant des
échanges de cases inutiles...
3.4. TRI D’UN TABLEAU 63
Exercice 24
Notons également que cet algorithme ne retourne aucun résultat : on a effectivement choisi
de faire un tri en place, c’est-à-dire qu’on ne renvoie pas un nouveau tableau, mais qu’on a
modifié le tableau donné en entrée directement... Il est donc inutile de le retourner, puisqu’on
a directement modifié le tableau dans la mémoire. Notons qu’en Python, le passage d’un
tableau en argument d’une fonction se fait bien ≪ par référence ≫ et donc la modification au
sein de la fonction se répercute bien sur la mémoire globale : attention, ce n’est pas le cas
dans tous les langages de programmation !
Pour mieux comprendre cet algorithme (puis le comparer avec d’autres algorithmes, dans
la suite), estimons sa complexité dans le pire des cas. Comme pour les algorithmes de recherche
étudiés auparavant, il faut donc comptabiliser les opérations élémentaires.
Vu l’imbrication de boucles de cet algorithme, il convient de commencer par considérer les
boucles les plus internes, c’est-à-dire le code qui est le plus ≪ décalé à droite ≫. Considérons
donc d’abord la boucle while qui exécute deux opérations élémentaires à chaque itération
(une affectation dans tableau[j] et une décrémentation de j), auxquelles il faut ajouter
les opérations élémentaires nécessaires pour tester si l’on doit continuer la boucle ou pas : ce
test (j > 0) and (x < tableau[j-1]) requiert deux comparaisons qu’on comptabilise donc
comme deux opérations élémentaires. Une itération réclame donc 4 opérations élémentaires.
Il faut aussi considérer le dernier test qui fait sortir de la boucle while, qui nécessite aussi 2
tests dans le pire des cas. Pour totaliser la complexité de cette boucle interne, il nous suffit
donc de savoir le nombre de fois que cette boucle s’exécute. Dans le pire des cas, l’élément x
est inférieur à tous les éléments de la portion triée, ce qui pousse alors à le décaler jusqu’au
tout début du tableau : la variable j prend alors toutes les valeurs de i à 1, avant d’être égale
à 0, auquel cas on sort de la boucle. Dans le pire des cas, on exécute donc i fois la boucle,
générant donc au total 4i + 2 opérations élémentaires.
On peut ensuite passer à la boucle for :
— on y affecte la variable x
— ainsi que la variable j ;
— on exécute la boucle while, coûtant donc 4i + 2 opérations élémentaires dans le pire
des cas ;
— finalement, on modifie la valeur de tableau[j].
Lors de l’itération correspondant à une valeur particulière de i, on exécute donc 1+1+4i+2+
1 = 4i + 5 opérations élémentaires. Ce nombre dépend de l’itération i : on ne peut donc pas
simplement multiplier le nombre d’opérations par le nombre d’itérations. À la place, on fait la
somme de toutes les contributions des itérations : le nombre total d’opérations élémentaires
exécutées au sein de la boucle for vaut donc
(4 × 1 + 5) + (4 × 2 + 5) + · · · + (4 × (n − 1) + 5)
64 CHAPITRE 3. ALGORITHMES SUR LES STRUCTURES LINÉAIRES
qu’on peut écrire sous la forme d’une somme qu’on décompose en deux sommes indépendantes :
n−1
X n−1
X n−1
X n−1
X
(4i + 5) = 4i + 5=4 i + 5 × (n − 1)
i=1 i=1 i=1 i=1
Il ne reste plus qu’à calculer la somme de gauche, qui n’est rien d’autre que la somme des
n − 1 premiers entiers dont on sait par ailleurs qu’elle vaut (n − 1)n/2. On obtient donc un
nombre d’opérations élémentaires égal à 2(n − 1)n + 5(n − 1) = 2n2 + 3n − 5.
Finalement, il faut aussi comptabiliser les opérations élémentaires en dehors de la boucle
for : il n’y en a qu’une, l’affectation de la variable n. In fine, on exécute donc, dans le pire
des cas, 2n2 + 3n − 4 opérations élémentaires. L’ordre de grandeur est donc en O(n2 ) (pour
s’en convaincre ici, il suffit de remarquer que pour tout n supérieur à 3, 2n2 + 3n − 4 ≤
2n2 + 3n × n = 5n2 ). L’algorithme de tri par insertion est donc un algorithme de complexité
quadratique en la longueur du tableau à trier.
Exercice 25
On vient de voir que, dans le pire des cas, la complexité du tri par insertion est en
O(n2 ). On peut raisonnablement se poser la question de savoir si on a surestimé le
nombre d’opérations élémentaires. En fait, il n’en est rien. Trouver donc une suite de
tableaux (tn )n∈N avec tn un tableau de longueur n telle que le nombre Cn d’opérations
élémentaires effectuées lors du tri du tableau tn est de la forme an2 + bn + c avec a, b, c
des constantes et a > 0.
Avant d’étudier un autre algorithme de tri, avec une meilleure complexité, l’exercice sui-
vant propose l’étude d’un autre tri très célèbre en informatique, car particulièrement visuel.
Exercice 26
Intéressons-nous à un autre algorithme de tri, fondé sur la méthode dite “des bulles”.
Il s’agit d’une méthode qui opère par permutations successives sur le tableau à trier.
On trie ainsi le tableau de gauche à droite, comme pour le tri par insertion. Voilà la
situation, une fois qu’on a trié les i premiers éléments, avec 1 ≤ i < n − 1 :
portion triée portion non traitée
0 i−1 i n−1
Pour augmenter la longueur de la portion triée, on crée une bulle qui enserre la case n−1
du tableau : il faut désormais imaginer que le tableau est dessiné de manière verticale,
la case n − 1 étant le fond d’un aquarium, alors que la séparation entre les cases i − 1
et i représente le niveau de l’eau à l’heure actuelle. La bulle va donc remonter du fond
de l’aquarium jusqu’au niveau de l’eau : mais attention, lorsqu’elle passe d’une case
à l’autre, si les deux éléments consécutifs ne sont pas ordonnés, la bulle fait remonter
la case qu’elle enserre et les éléments sont donc permutés. Au contraire, si les deux
éléments consécutifs sont dans le bon ordre, la bulle remonte sans entraı̂ner avec elle
de permutation de cases. À titre d’exemple, si l’on prend le tableau [B,A,T,E,A,U,X]
(qu’on écrit BATEAUX dans la suite de cet exercice pour raccourcir les notations), la
méthode des bulles le trie selon l’ordre alphabétique de la manière suivante :
3.4. TRI D’UN TABLEAU 65
i trié / non traité min. partie non traitée après “remontée des bulles”
0 / BATEAUX A A / BATEUX
1 A / BATEUX A AA / BETUX
2 AA / BETUX B AAB / ETUX
3 AAB / ETUX E AABE / TUX
4 AABE / TUX T AABET / UX
5 AABET / UX U AABETU / X
6 AABETU / X
Attention, notez bien ce qu’il s’est passé lors de la remontée de la première bulle :
— le niveau de l’eau est pour l’instant tout à gauche du tableau et la bulle com-
mence autour de la lettre X ;
— la bulle remonte et puisque U est une lettre inférieure (dans l’ordre alphabétique)
à X, la bulle passe de X à U sans permuter les éléments ;
— il en va de même lorsqu’elle passe de U à A ;
— par contre, la bulle entraı̂ne la lettre A avec elle puisque E est supérieure à A :
les lettres A et E sont donc permutées ;
— la lettre suivante est un T, qui est supérieure au contenu de la bulle (A) donc
les deux cases sont aussi permutées ;
— la bulle rencontre une autre lettre A sur son passage, et continue donc à monter
sans besoin de permuter les cases ;
— finalement, B étant inférieur à A, la bulle entraı̂ne la lettre A avec elle et la fait
passer au-dessus du niveau de l’eau.
On obtient donc le tableau ABATEUX : on a fait sortir la lettre A, tout en faisant
remonter la seconde lettre A au niveau de la première... Lors de la deuxième étape,
cela explique pourquoi on obtient le tableau AABETUX (et pas AABTEUX !).
1. Exécuter le tri à bulles sur le tableau [I,N,F,O,R,M,A,T,I,Q,U,E] (vous
représenterez le résultat sous forme d’un tableau tel que celui donné ci-dessus).
2. Écrire (sous forme de pseudo-code) l’algorithme décrivant le tri à bulles.
3. Évaluer la complexité de cet algorithme, en donnant un ordre de grandeur du
nombre d’opérations élémentaires réalisées dans le pire des cas sur un tableau
de longueur n.
4. En regardant à nouveau l’exécution de l’algorithme sur BATEAUX et INFOR-
MATIQUE, qu’observez-vous ? Pourrait-on l’améliorer afin d’éviter des compa-
raisons inutiles ?
5. Proposer un nouvel algorithme de tri à bulles qui améliore significativement le
précédent en tenant compte de vos observations précédentes. Il est possible de
faire s’arrêter une fonction en plaçant l’instruction return, qui ne renvoie rien,
mais stoppe l’exécution où elle en est...
6. Bien que cet algorithme améliore en moyenne le temps d’exécution, il n’en est
rien dans le pire cas : vous pouvez ainsi vérifier qu’une estimation rapide de
la complexité fournit toujours une borne en O(n2 ) sur le nombre d’opérations.
Pour s’en convaincre, pouvez-vous trouver une suite de tableaux (tn )n∈N avec
tn de longueur n telle que le nombre d’opérations élémentaires effectuées par
66 CHAPITRE 3. ALGORITHMES SUR LES STRUCTURES LINÉAIRES
La question reste cependant entière : comment fait-on pour trier les deux petits tableaux
[3, 16, 14, 1, 12, 7] et [10, 4, 5, 11, 15] ? La réponse est simple : ≪ on recommence ! ≫. En effet, la
tactique décrite ci-dessus pour trier le grand tableau peut être aussi utilisée pour traiter ces
deux petits tableaux, de manière indépendante. On peut ainsi visualiser dans la Figure 3.3
le cheminement complet pour trier le grand tableau : la division en deux sous-tableaux est
marquée par l’éclair rouge et les deux flèches bleues, puis la fusion des deux tableaux triés est
représentée par les flèches orange.
Comment écrire dans du pseudo-code la formule magique ≪ on recommence ! ≫ ? ! ? La
manière la plus simple de faire est la suivante :
def tri_fusion ( tableau ) :
n = len ( tableau )
if n <= 1:
return tableau
else :
gauche = tableau [0 : n //2] # portion gauche
droite = tableau [ n //2 : n ] # portion droite
gauche_tri é := tri_fusion ( gauche )
droite_tri é := tri_fusion ( droite )
retourner ( fusionner ( gauche_tri é , droite_tri é ) )
FinSi
On a utilisé la notation Python t[a : b] qui permet de renvoyer un nouveau tableau
contenant les éléments t[a], t[a + 1], . . . , t[b − 1] d’indice a (inclus) à b (exclus). Lorsque a = 0
3.4. TRI D’UN TABLEAU 67
3 16 14 1 12 7 10 4 5 11 15
« Diviser… »
3 16 14 1 12 7 10 4 5 11 15
3 16 14 1 12 7 10 4 5 11 15
3 16 14 1 12 7 10 4 5 11 15
3 16 1 12 10 4 11 15
3 16 1 12 4 10
3 14 16 1 7 12 4 5 10
1 3 7 12 14 16 4 5 10 11 15
« … Fusionner» 1 3 4 5 7 10 11 12 14 15 16
(comme c’est le cas pour la portion gauche), on peut simplifier en t[:b]. Lorsque b est égal
à la longueur du tableau (comme c’est le cas pour la portion droite), on peut simplifier en
t[a:]. Contrairement au tri par insertion, cette fonction retourne un tableau : elle n’est pas
en place. On a également utilisé une fonction fusionner dont on ne fournit pas le code : c’est
la fonction qui prend deux petits tableaux triés en entrée et doit les fusionner pour produire
un grand tableau trié, comme expliqué ci-dessus. Finalement, le ≪ on recommence ! ≫ est
écrit par l’appel de la fonction tri fusion elle-même au sein de sa propre définition : on
appelle cela des appels récursifs ; la fonction elle-même s’appelle une fonction récursive. Nous
reverrons plus loin ce mécanisme.
En terme de complexité, il n’est pas très difficile de se convaincre que la fusion de deux
tableaux triés peut s’exécuter en temps linéaire (O(n)) en la taille du grand tableau. Par
ailleurs, comme on peut le voir en Figure 3.3, on fait assez peu d’appels récursifs finalement :
comme pour la recherche dichotomique, l’intérêt de la méthode est qu’à chaque appel récursif,
on a divisé par deux la longueur du tableau à trier. On ne peut donc faire qu’au plus O(log2 n)
appels récursifs imbriqués. Ceci explique pourquoi la complexité du tri par fusion est en
O(n log2 n), ce qu’on admet dans ce cours.
On est donc passé d’un tri de complexité O(n2 ) à un tri de complexité O(n log2 n) :
c’est évidemment bien mieux de la même façon que la recherche dichotomique de complexité
O(log2 n) est bien meilleure que la recherche séquentielle de complexité O(n). Mais peut-
on encore mieux faire ? En fait, on peut montrer qu’il n’est pas possible de mieux faire,
dès lors qu’on ne considère que des tris qui procèdent par comparaison des éléments deux
par deux, comme c’est le cas pour les tris qu’on a étudiés jusque-là. Cependant, si on lève
cette restriction, il est possible d’obtenir une meilleure complexité, comme on l’étudie dans
l’exercice suivant.
Exercice 27
Dans une crêperie du Vieux Port, deux crêpiers se relaient en cuisine. Toutes les crêpes
n’ont pas exactement le même diamètre. Au moment du changement de crêpier, s’il
reste des crêpes déjà précuites, le crêpier sur le départ, un peu psychorigide sur les
bords, veut laisser à son collègue une pile de crêpes triée de la plus grande en bas,
jusqu’à la plus petite en haut. Oui, mais voilà : la cuisine est minuscule ! La seule
possibilité pour le crêpier psychorigide est d’utiliser sa grande spatule, de la planter
entre deux crêpes de la pile de crêpes et de retourner la totalité de la pile de crêpes
au-dessus, le tout sur la même pile de crêpe. Par exemple, dans la pile de crêpes à
gauche ci-dessous, si le crêpier plante sa spatule à l’endroit des pointillés et retourne
la pile du dessus, il obtient la pile de crêpes de droite.
=⇒
1. Comment le crêpier doit-il s’y prendre pour trier sa pile de crêpes ? Décrire une
méthode que le crêpier peut utiliser facilement : en particulier, notez qu’il est
facile pour le crêpier de trouver la plus grande crêpe dans une pile de crêpes...
2. Décrire votre algorithme en Python en supposant que la pile de crêpe est
représentée par le tableau t des diamètres des crêpes en commençant par la
crêpe la plus basse. Vous pourrez utiliser
3.4. TRI D’UN TABLEAU 69
71
72 CHAPITRE 4. ALGORITHMES SUR LES ENTIERS ET LES FLOTTANTS
1 1 0 0 1 1 1 1
L’incrément peut alors s’écrire de la manière suivante en pseudo-code qui prend en entrée
un tableau de bits et le modifie (la fonction ne renvoie donc rien, comme lors du tri par
insertion dans le chapitre précédent) :
def incr é menter ( n_en_binaire ) :
i = len ( n_en_binaire ) -1
while ( i > 0) and ( n_en_binaire [ i ] == 1) :
n_en_binaire [ i ] = 0
i = i - 1
n_en_binaire [ i ] = 1
Par exemple, sur le tableau précédent, représentant 207, on initialise la variable i à 7 (la
longueur du tableau valant 8, c’est-à-dire qu’on a codé l’entier sur un octet). On commence
par s’apercevoir que la case d’indice 7 héberge un bit à 1, vérifie la condition de la boucle
while qui permet de passer ce bit à 0 et de passer la valeur de i à 6. Le tableau est donc
devenu
1 1 0 0 1 1 1 0
On fait de même pour les trois bits à 1 suivants, arrivant à la situation où i vaut 3 et le
tableau est
1 1 0 0 0 0 0 0
1 1 0 1 0 0 0 0
1 1 1 1 1 1 1 1
Cette fois-ci, le test n en binaire[i]= 1 n’échoue jamais, mais le test i> 0 finit par échouer,
lorsque la variable i devient égale à 0. On sort alors du tableau (rempli de 0) et on passe la
première case à 1 de sorte qu’on termine avec le tableau suivant :
1 0 0 0 0 0 0 0
4.1. ADDITION D’ENTIERS 73
Clairement, le résultat n’est pas correct puisque 11111111 est le codage binaire de l’entier
28 − 1 = 255, alors que 10000000 est le codage binaire de l’entier 27 = 128. La raison de
l’échec est ce qu’on appelle un dépassement de capacité : 11111111 est le plus grand entier
naturel qu’on peut stocker sur 8 bits, de sorte qu’ajouter 1 est impossible sans dépasser les 8
bits autorisés.
Exercice 28
Il n’est pas franchement satisfaisant, même dans le cas d’un dépassement de capacité
que l’entier 128 suive l’entier 255, lorsqu’on incrémente un entier stocké sur 8 bits (pour
simplifier, puisqu’en réalité, on stocke les entiers sur 32 ou 64 bits dans les ordinateurs
modernes). Essayons donc de faire mieux.
1. Supposons désormais qu’on stocke sur 8 bits des entiers relatifs, avec un bit
de signe (1 pour les nombres négatifs et 0 pour les nombres positifs). Exécuter
l’algorithme d’incrémentation précédent sur les deux codes de l’entier 0 (à savoir
00000000 et 10000000), le code d’un entier strictement positif différent du plus
grand entier qu’on peut coder sur 8 bits et le code d’un entier strictement négatif
différent du plus petit entier qu’on peut coder sur 8 bits. Est-ce correct ?
2. La situation semble encore moins favorable qu’avec les entiers naturels. Pour
arranger cela, on utilise en fait un autre codage des entiers relatifs, basé sur
la technique du complément à deux. On ne modifie pas le codage d’un entier
positif : on commence par le bit de signe 0 puis le codage de l’entier sur les 7
bits restants. En revanche, voici la méthode pour coder un entier négatif −n
avec n ∈ N :
— on commence par coder sur 8 bits l’entier naturel n ;
— on inverse tous ses bits (les 1 deviennent des 0 et vice versa) ;
— puis on ajoute 1 (en utilisant l’algorithme d’incrémentation vu plus haut).
Par exemple, la représentation de l’entier −4 est obtenu en partant de la
représentation de 4 sur 8 bits, à savoir 00000100, en inversant les bits, pour
obtenir 11111011, puis en ajoutant 1 : c’est donc 11111100.
Donner la représentation en complément à deux sur 8 bits des entiers +10, −17,
−76.
3. Notez que le nombre 0 a désormais un unique codage en complément à deux
(00000000 sur 8 bits). Reprendre les exemples trouvés à la question 1 et utili-
ser l’algorithme vu plus haut pour les incrémenter : est-ce que le résultat est
désormais correct ?
4. Quel est le plus grand entier positif qu’on peut coder en complément à deux sur
8 bits ? Et le plus petit entier négatif ? Essayer désormais d’ajouter 1 au plus
grand entier positif. Vous devriez alors comprendre pourquoi l’on peut dire que
le codage par complément à deux est dit cyclique.
0 0 10 11 10 1 0 0
+ 0 0 1 1 1 1 0 1
0 1 0 1 0 0 0 1
74 CHAPITRE 4. ALGORITHMES SUR LES ENTIERS ET LES FLOTTANTS
Exercice 29
1. Compléter la fonction suivante pour qu’elle renvoie le tableau contenant la
somme des entiers m et n représentés par les tableaux en entrée, sans faire
attention à d’éventuels dépassements de capacité ?
def additionner ( m_en_binaire , n_en_binaire ) :
N = len ( n_en_binaire )
r é sultat = [0] * N
retenue = 0
for i in range (........) :
....
return r é sultat
2. Tester cet algorithme en additionnant 63 et 42. Tester ensuite cet algorithme en
additionnant les représentations en complément à deux sur 8 bits (cf exercice
précédent) des entiers 63 et −42. Qu’obtient-on ?
On suppose donc à partir de maintenant qu’on sait effectuer des additions et des sous-
tractions d’entiers. On s’abstrait dans la suite du chapitre de la représentation en binaire des
entiers.
4.2 Divisibilité
4.2.1 Division euclidienne
Une autre opération très courante qu’on exécute souvent consiste à calculer le quotient
q et le reste r dans la division euclidienne d’un entier naturel n par un entier naturel m,
c’est-à-dire l’unique paire (q,r) ∈ N × {0,1, . . . ,m − 1} tel que
n=m×q+r
Cette fois-ci, par souci de simplicité, on donne un algorithme qui ne suit pas la méthode
à la main qu’on exécute habituellement. Par exemple, si on cherche à diviser 382 par 27,
généralement, voilà comment on procède :
— d’abord on se demande combien de fois on peut mettre 27 dans 38 : c’est une fois donc
on pose 1, et il reste 11 ;
— on fait descendre le chiffre 2 des unités dans 382 et on se demande combien de fois on
peut mettre 27 dans 112 : c’est quatre fois donc on pose 4, et il reste 4.
On a donc le diagramme suivant :
3 8 2 2 7
− 2 7 1 4
1 1 2
− 1 0 8
4
C’est une façon compacte et efficace de mener à bien une division euclidienne : elle est
cependant plus délicate à écrire sous forme de code Python. On utilise à la place une méthode
plus élémentaire, mais moins efficace. Elle consiste à soustraire de 382 le nombre 27 autant de
4.2. DIVISIBILITÉ 75
fois que nécessaire jusqu’à trouver un entier strictement inférieur à 27 : le nombre de fois qu’il
a fallu soustraire 27 est le quotient et l’entier restant finalement est le reste. Par exemple,
21 = 14 × 1 + 7
puis on remplace le dividende par 14 et le diviseur par 7 pour obtenir la deuxième division
euclidienne :
14 = 7 × 2 + 0
Le reste devient nul et on en déduit alors que le pgcd de 21 et 14 est le dernier reste non nul,
à savoir 7 : pgcd(21,14) = 7.
76 CHAPITRE 4. ALGORITHMES SUR LES ENTIERS ET LES FLOTTANTS
Exercice 30
Calculer le pgcd de 799 et 345 à la main, par divisions euclidiennes successives.
NON
r = 0?
OUI
pgcd = b
Cette représentation graphique illustre qu’on doit faire une action (donner à a la valeur
de b et à b la valeur de r, puis calculer le reste r de la division euclidienne de a par b) tant
que r est non nul. On peut donc écrire tout naturellement le code Python suivant :
def pgcd (a , b ) :
# a > b deux entiers non nuls
r = a % b
while r > 0:
a = b
b = r
r = a % b
return b
La correction de cet algorithme provient du fait qu’à tout moment dans l’algorithme le
pgcd des variables a et b reste inchangé, ce qui tient du fait que si r est le reste dans la division
euclidienne de a par b on a
pgcd(a,b) = pgcd(b,r)
La preuve de ce théorème est simple : il suffit de démontrer que les diviseurs communs de a
et b sont les mêmes que ceux de b et r. Notons q le quotient dans la division euclidienne de a
par b de sorte que a = b × q + r.
— Soit d un diviseur commun de a et b. Alors d divise a et d divise b, donc d divise
a − b × q = r. Donc d est un diviseur commun de b et r.
— Soit d un diviseur commun de b et r. Alors d divise b × q + r = a donc d est un diviseur
commun de a et b.
La terminaison de l’algorithme est également simple à démontrer puisque le long d’une
itération de la boucle while la valeur de la variable r passe à b % r c’est-à-dire le reste dans
C’est vraiment utile ?…
4.2. DIVISIBILITÉ 77
4.2 – Applications
Communication
Figure du test de
sécurisée enprimalité réciproque
ligne : https
la division euclidienne de b par r, qui par définition est strictement inférieur à r. La valeur r
est donc un variant de boucle. Puisque la boucle while s’arrête dès lors que r devient négatif
ou nul, on est sûr qu’on ne peut boucler qu’un nombre fini de fois.
Charlie
Alice Bob
Communication sécurisée
mot de passe
message chiffré
message déchiffré
=
=
=
chiffrement déchiffrement
« maman13 » « Xyf92!j » « maman13 »
tographie. Alice et Bob veulent ainsi communiquer des informations de manière sécurisée,
c’est-à-dire sans qu’un intrus, Charlie, puisse récupérer les informations. Par exemple, Alice
peut vouloir se connecter à son compte Twitter en envoyant son mot de passe à Bob (qui est
alors ici le serveur de Twitter...), comme en Figure 4.3.
Nous avons déjà vu dans les exercices des chapitres précédents des méthodes de chiffre-
ment, que ce soit le chiffrement de César ou de Vigenère. À chaque fois, on s’est aperçu
que ces techniques de chiffrement souffraient d’un lourd défaut : on peut rapidement casser
le chiffrement en réalisant une cryptoanalyse (en essayant toutes les clés possibles ou bien
en guidant sa recherche via l’utilisation de statistiques sur la langue du message à chiffrer).
On n’utilise donc pas ces méthodes en réalité. À la place, on utilise des systèmes basés sur
l’arithmétique, tels que le cryptosystème RSA (du nom de ses créateurs Ronald Rivest, Adi
Shamir et Leonard Adleman). Il s’agit d’un système de chiffrement asymétrique, c’est-à-dire
qu’Alice et Bob n’ont pas la même clé de chiffrement/déchiffrement (contrairement aux codes
de César ou Vigenère où les différents participants partagent la même clé de décalage). C’est
un système basé sur l’utilisation de grands entiers premiers qui implique que les messages eux-
mêmes soient d’abord transformés en entiers : c’est facile en utilisant par exemple la table
ASCII transformant chaque caractère en entier. La clé d’Alice est une paire d’entiers (e,n),
celle de Bob une paire d’entiers (d,n). La procédure de chiffrement, illustrée en Figure 4.4,
consiste, pour Alice, à partir d’un message M et de le chiffrer grâce à l’opération M e mod n.
Symétriquement, la procédure de déchiffrement d’un chiffré C consiste, pour Bob, à calculer
C d mod n.
Mais comment sont choisis les clés d’Alice et Bob pour rendre robuste et correct ce pro-
tocole de chiffrement ?
1. Tout d’abord, on choisit deux grands entiers premiers distincts p et q.
2. On calcule ensuite leur produit n = p × q.
3. On calcule également φ(n) = (p − 1)(q − 1).
Chiffrer/déchiffrer un message
chiffrement asymétrique,
Cryptosystème
4.3. EXPONENTIATION RSA basé sur des grands entiers premiers
79
(e, n) (d, n)
Alice Bob
M∈N chiffrement
M e mod n
C∈N déchiffrement
C d mod n
Figure 4.4 – Cryptosystème RSA
d × e ≡ 1 [φ(n)]
Il est très facile de calculer l’entier d à l’aide de l’algorithme d’Euclide (étendu). En effet, le
fait que e et φ(n) soient premiers entre eux (c’est-à-dire que leur pgcd soit égal à 1) garantit
l’existence d’une paire de Bézout (d,k) tels que de + kφ(n) = 1. L’algorithme d’Euclide,
légèrement enrichi, permet de calculer une telle paire (d,k).
Une fois crées les clés (e,n) et (d,n), on peut oublier p et q. La propriété clé qui garantit
que le cryptosystème RSA est correct est le théorème suivant, qu’on admet dans ce cours
(mais dont vous pourrez facilement trouver une preuve sur Internet si cela vous intéresse) :
Théorème 1. Pour tout message M ∈ N, (M e )d ≡ M [n], c’est-à-dire que si on déchiffre le
message chiffré obtenu à partir du clair M , on retombe sur le message M initial.
On le voit, l’arithmétique des entiers premiers (et premiers entre eux) est donc indis-
pensable pour chiffrer efficacement et sûrement des messages qu’on s’échange à longueur de
journée.
4.3 Exponentiation
Une question se pose cependant au vu de la procédure de chiffrement et de déchiffrement
RSA qu’on vient de découvrir : comment la machine fait-elle pour calculer M**e % n ? Plus
généralement, comment la machine fait-elle pour calculer l’élévation à une puissance entière
positive, par exemple pour calculer 2132 ou e23 ?
Étant donné un nombre x (cela peut-être un entier ou un réel, qu’on représente alors en
machine à l’aide d’un flottant) et un entier naturel n, on souhaite donc calculer le nombre
xn = |x × x ×
{z· · · × x}
n fois
80 CHAPITRE 4. ALGORITHMES SUR LES ENTIERS ET LES FLOTTANTS
Si on suppose que la machine sait réaliser une multiplication (ce qui est du même genre
que le calcul d’une addition qu’on a étudié plus tôt), on a donc un algorithme très simple qui
consiste à multiplier n − 1 fois le nombre x avec lui-même. La fonction suivante réalise ces
multiplications.
def puissance (x , n ) :
r é sultat = x
for i in range ( n - 1) :
r é sultat = r é sultat * x
return r é sultat
L’opération coûteuse dans ce calcul est clairement la multiplication. Combien en effectue-
t-on au cours de cet algorithme ? Autant qu’il y a de tours de la boucle for, c’est-à-dire n − 1.
Peut-on faire mieux ?
Par exemple, pour calculer x8 , l’algorithme précédent revient aux 7 multiplications
x8 = x × x × x × x × x × x × x × x
x8 = ((x2 )2 )2
x13 = x × x × x × x × x × x × x × x × x × x × x × x × x
ou bien on peut remarquer que x13 = x6 × x6 × x. Si on sait calculer x6 , il faut alors ajouter
deux multiplications supplémentaires pour obtenir x13 . De même, x6 = x3 ×x3 et x3 = x2 ×x,
avec x2 = x × x. On obtient donc x13 à l’aide de 5 multiplications seulement
On voit qu’on ne réalise donc pas le même découpage selon que la puissance n est paire ou
impaire, ce qui nous amène à considérer l’algorithme suivant, qu’on appelle d’exponentiation
rapide.
4.4. RECHERCHE D’UN ZÉRO D’UNE FONCTION 81
def puissance_rapide (x , n ) :
a = 1
b = x
m = n
while m > 0:
if m % 2 == 1:
a = a * b
m = m // 2
b = b * b
return a
Exercice 31
1. Exécuter l’algorithme d’exponentiation rapide lors du calcul de 210 , en précisant
la valeur des variables lors de chaque étape de la boucle while.
2. Donner une preuve du fait que l’algorithme termine toujours.
3. Pour prouver que l’algorithme est correct, c’est-à-dire qu’il renvoie bien xn , une
méthode consiste à vérifier qu’à tout moment de l’algorithme on a xn = a × bm .
Montrer que c’est vrai avant de rentrer dans la boucle while, puis que si c’est
vrai au début d’une itération de la boucle while, alors c’est vrai à la fin de cette
itération. Conclure alors à l’aide d’un raisonnement par récurrence.
4. Combien de multiplications sont effectuées par l’algorithme lors du calcul de 210 .
Plus généralement, pouvez-vous donner un ordre de grandeur du nombre de
multiplications effectuées pour calculer xn par l’algorithme d’exponentiation
rapide, en fonction de n ? Comparer avec l’algorithme puissance étudié plus
haut.
5. Comme on l’a vu, le cryptosystème RSA demande de savoir calculer des puis-
sances modulaires, c’est-à-dire le reste de xn dans la division euclidienne par k.
Sachant que
si a ≡ b [k] alors an ≡ bn [k]
on a intérêt à calculer les puissances en prenant les restes dans la division eucli-
dienne par k à chaque étape. Modifier alors la fonction puissance rapide, en
ajoutant un troisième argument k, afin qu’elle calcule le reste de xn dans la di-
vision euclidienne par k. : on s’autorise à utiliser comme opération élémentaire
supplémentaire le calcul de y % k, le reste dans la division euclidienne de y
par k.
En l’absence de calculatrices, en effet, les sommes sont bien plus simples à réaliser à la main
que des multiplications. En revanche, cela demandait à savoir passer aisément d’une valeur
à son logarithme et vice versa. Pendant trois siècles, cela s’est fait à l’aide de tables de
logarithmes qui étaient regroupées dans des petits livres, comme l’illustre la Figure 4.5.
Évidemment, il n’est plus question de telles tables de logarithmes aujourd’hui, les calcula-
trices et ordinateurs faisant le travail pour nous. Mais comment font-ils ? En fait, ils utilisent
des techniques mathématiques un peu plus avancées que celles que vous connaissez sans
doute à l’heure actuelle (développements limités, séries numériques, résolutions d’équations
différentielles...), mais on peut déjà étudier une méthode simple pour faire de tels calculs, en
supposant simplement qu’on sait calculer l’exponentielle de n’importe quel nombre flottant
(et pas seulement d’un nombre entier positif comme on l’a fait dans la section précédente).
En effet, une fois qu’on sait calculer l’exponentielle, on peut remarquer que
x = ln(14) ⇐⇒ ex = 14
Si on sait trouver un antécédent par la fonction exponentielle d’un nombre, 14 par exemple,
alors on a trouvé son logarithme népérien ln(14). De manière similaire, pour le logarithme en
base 2 :
x = log2 (152) ⇐⇒ 2x = 152
Remarquons désormais que résoudre ex = 14 revient à résoudre ex − 14 = 0. On se ramène
donc à rechercher un réel x tel que ex − 14 = 0 ou 2x − 152 = 0, c’est-à-dire le zéro d’une
fonction mathématique f , comme illustré en Figure 4.6.
Ce problème ressemble beaucoup au problème de la recherche d’un élément dans un ta-
bleau, qu’on a étudié dans le chapitre précédent. La différence est qu’on est face à un tableau
infini ne permettant pas de réaliser la recherche séquentielle consistant à visiter tous les
4.4. RECHERCHE D’UN ZÉRO D’UNE FONCTION 83
y
f
zéro de la fonction
x
0 z
éléments du tableau de gauche à droite. En revanche, rien n’empêche d’utiliser une technique
de recherche dichotomique (cf Figure 4.7). On commence par encadrer un des zéros de la fonc-
tion qu’on suppose continue : on suppose donc connu un intervalle [a,b] tel que f est continue
sur cet intervalle et change de signe, c’est-à-dire f (a) × f (b) < 0. Par le théorème des valeurs
intermédiaires, on est assuré de l’existence d’un zéro z dans l’intervalle [a,b]. Considérons le
milieu de l’intervalle a+b2 . Deux cas se présentent :
— si f ((a + b)/2) < 0 (comme dans la figure), alors on sait, toujours grâce au théorème
des valeurs intermédiaires, que la fonction f possède un zéro sur l’intervalle [ a+b 2 ,b] ;
— si f ((a + b)/2) > 0, alors on sait que la fonction f possède un zéro sur l’intervalle
[a, a+b
2 ].
On continue donc ainsi à resserrer l’intervalle encadrant un zéro de la fonction f : sur la
figure, on considère ensuite m le milieu de l’intervalle [ a+b ′
2 ,b], puis m le milieu de l’intervalle
[ a+b
2 ,m]. Quand s’arrête-t-on ? On s’arrête si on finit par tomber exactement sur un zéro,
ou alors après avoir obtenu un intervalle [x,x′ ] suffisamment petit pour avoir obtenu une
approximation suffisante du zéro recherché.
Outre cet algorithme de recherche dichotomique, d’autres solutions simples existent. L’une
d’entre elles est l’algorithme de Newton qui consiste à ≪ descendre le long de la courbe ≫. Cette
fois-ci, on suppose de plus que la fonction f est dérivable, de sorte qu’on connait une équation
de la tangente à la courbe de f en le point d’abscisse x0 : y = f (x0 ) + f ′ (x0 ) × (x − x0 ). La
méthode de Newton se base sur l’idée qu’on peut approcher la courbe d’une fonction par sa
tangente : si x est suffisamment proche de x0 alors f (x) est proche de f (x0 ) + f ′ (x0 )(x − x0 ).
En particulier, si on calcule l’abscisse du point d’intersection de la tangente à la courbe
en x0 avec l’axe des abscisses, on espère obtenir une nouvelle abscisse x1 plus proche du zéro
comme le montre la Figure 4.8.
On résout donc l’équation 0 = f (x0 ) + f ′ (x0 )(x − x0 ) afin de trouver (si la dérivée f ′ (x0 )
est non nulle) l’abscisse x1 = x0 − ff′(x 0)
(x0 ) . Plus généralement, on construit donc la suite (xn )n∈N
84 CHAPITRE 4. ALGORITHMES SUR LES ENTIERS ET LES FLOTTANTS
f
y
a+ b
a 2 b
0 m′ m
x
f((a + b)/2) < 0 f(m) > 0
y
f(x0)
x
0 x0 x1
tangente en x0
On peut donc écrire un algorithme qui calcule les valeurs successives de la suite (xn )n∈N
qu’on stocke dans une variable a évoluant au cours du temps, nécessitant d’avoir en argument
non seulement la fonction f , mais aussi sa dérivée f ′ .
def a p p r o x i m a t i o n _ z e r o _ N e w t o n (f , f ’ , x0 ) :
a = x0
while f ( a ) != 0:
a = a - f ( a ) / f ’( a )
return a
Comme précédemment dans la recherche dichotomique, cet algorithme n’a aucune raison
de terminer a priori, puisqu’on n’est pas garanti de finir par trouver un zéro exactement. On
modifie donc cet algorithme pour qu’il ait plus de chances de terminer (même si ce n’est pas
encore garanti !), en lui ajoutant une précision ε > 0 (on utilise traditionnellement la lettre
grecque ≪ epsilon ≫ pour décrire ce paramètre d’erreur) en dessous de laquelle on se satisfait
de l’approximation trouvée, c’est-à-dire qu’on cherche une abscisse z telle que |f (z)| ≤ ε.
On continue donc la boucle while si on n’a pas cette condition vérifiée, c’est-à-dire tant que
|f (a)| > ε :
def a p p r o x i m a t i o n _ z e r o _ N e w t o n (f , f ’ , x0 , epsilon ) :
a = x0
while abs ( f ( a ) ) > epsilon :
a = a - f ( a ) / f ’( a )
return a
où l’on a utilisé la fonction abs de Python pour calculer la valeur absolue.
C’est un algorithme très utilisé qui fonctionne plutôt bien en pratique, mais il faut bien
voir qu’il n’est pas correct en général : il se peut que l’algorithme termine et renvoie un
résultat qui ne soit pas ≪ proche ≫ d’un zéro de la fonction f . C’est le cas dans l’exemple de
la Figure 4.9 où l’algorithme s’arrête à la fin de la première itération, loin du zéro de f .
Exercice 33
On propose un autre critère d’arrêt pour l’algorithme de Newton en remarquant que
lorsque l’on s’approche du zéro de f , les abscisses xn deviennent de plus en plus proches :
précisément, la distance de xn à xn+1 tend alors vers 0 lorsque n tend vers l’infini.
1. Comment modifier l’algorithme pour que la condition d’arrêt porte ainsi sur
cette distance entre deux abscisses successives ?
2. Pouvez-vous trouver un exemple montrant que ce nouvel algorithme est
également incorrect ? On demande donc de dessiner le graphe d’une fonction f
et de choisir x0 et un paramètre d’erreur tels que le nouvel algorithme termine
(sans échouer du fait d’une dérivée nulle) en renvoyant un résultat ≪ loin ≫ du
zéro de la fonction f .
86 CHAPITRE 4. ALGORITHMES SUR LES ENTIERS ET LES FLOTTANTS
y
f(x0)
ε
x
0 x0 x1
Nous savons désormais mieux comment on (ou une machine) peut calculer avec des algo-
rithmes, sur des ensembles d’objects stockés dans des tableaux ou des données numériques.
En particulier, on a vu comment trier des tableaux, ce qui permet de répondre à l’un des
problèmes posé dans le chapitre d’introduction (cf Figure 1.17). Un autre problème que nous
posions alors, dans la Figure 1.16, est le calcul du plus court chemin dans Google Maps :
on avait dit alors qu’on pouvait abstraire le problème à l’aide d’un graphe avec des nœuds
représentant les intersections de rue et des arcs reliant ces nœuds avec la durée en minutes du
trajet correspondant. Ce chapitre et le suivant ont pour objectif de mieux comprendre cette
structure de données supplémentaire que sont les graphes. Dans ce premier chapitre, nous
allons voir que les graphes sont partout et nous allons répondre à la question que pose Google
Maps. Le chapitre suivant permettra d’étudier d’autres problèmes en lien avec les graphes.
87
88 CHAPITRE 5. GRAPHES : MODÉLISATION ET PARCOURS
Internet
Figure 5.3 – Graphes tirés des connexions entre utilisateurs de réseaux sociaux tels que
Twitter (à gauche) ou Instagram (à droite)
90 CHAPITRE 5. GRAPHES : MODÉLISATION ET PARCOURS
Définition 5. Un graphe est la donnée d’un ensemble fini S de sommets (ou nœuds) et d’un
ensemble fini A de paires de sommets qu’on appelle arêtes : si u et v sont deux sommets,
l’arête {u,v} représente le fait que les sommets u et v sont reliés dans le graphe. On note
parfois G = (S,A) le graphe.
1 2
3 4
Un chemin (on dit parfois aussi chaı̂ne) dans un tel graphe G = (S,A) est une suite de
sommets s1 ,s2 ,s3 , . . . ,sn−1 ,sn qui sont reliés par une arête, c’est-à-dire tel que {s1 ,s2 } ∈ A,
{s2 ,s3 } ∈ A, . . ., et {sn−1 ,sn } ∈ A. La longueur d’un chemin est le nombre d’arêtes qu’il
emprunte. Par exemple 0,1,2,4,2,3 est un chemin de longueur 5 dans le graphe précédent.
Un graphe non orienté permet, par exemple, de représenter les relations de connaissance
ou d’amitié dans un réseau social (de telles relations sont généralement symétriques : Marc
est ami avec Sarah si et seulement si Sarah est amie avec Marc...). La Figure 5.5 donne un
Réseau social (symétrique)
5.2. GRAPHES : APPLICATION AU DIAMÈTRE DES RÉSEAUX SOCIAUX 91
" #
!
&
$ %
Figure 5.5 – Aperçu du graphe d’un réseau social
petit aperçu d’un tel réseau social : les sommets sont les utilisateurs du réseau social et les
arêtes représentent les liens de connaissance ou d’amitié.
Modéliser un tel réseau social sous la forme d’un graphe permet de visualiser le réseau
(comme dans les figures du début du chapitre...), mais aussi de raisonner sur le réseau. Par
exemple, des recherches ont montré qu’≪ Un utilisateur de Facebook (parmi les 1,59 mil-
liards d’utilisateurs) est connecté à n’importe quelle autre personne par le biais de 3,5 per-
sonnes en moyenne ≫ (voir le post en anglais de Facebook Research [Link]
com/three-and-a-half-degrees-of-separation/) : cela veut dire que sur Facebook par
exemple, il y a de fortes chances que Madonna soit amie avec un des amis des amis de vos amis.
Cela fait référence à l’expérience que le psychologue social Stanley Milgram avait conduite
dans les années 60, montrant qu’en moyenne, deux individus américains ne sont séparés que
par 6 degrés de connaissance en moyenne.
Formellement, la distance entre deux sommets est la longueur minimale d’un chemin qui
les relie. La distance moyenne entre deux sommets du graphe de Facebook est donc estimée
à 3,5. Cela permet d’en déduire des informations sur le diamètre du graphe de Facebook :
le diamètre d’un graphe est la distance maximale séparant deux sommets quelconques du
graphe.
Exercice 35
Du temps de Pagnol, une bergère veut traverser la rivière Durance avec un chou,
un mouton et un loup. Malheureusement, pas de pont à l’horizon et elle ne possède
qu’une minuscule barque dans laquelle elle peut naviguer avec un seul de ses ≪ compa-
gnons ≫ d’aventure. En sa présence, le mouton n’ose pas manger le chou, pas plus que
le loup n’ose manger le mouton, mais ils n’hésiteraient pas à satisfaire leurs appétits si
la bergère tournait le dos. Comment doit-elle s’y prendre pour amener tout le monde
de l’autre côté de la rivière ? Utilisons un graphe pour l’aider !
1. Quelles sont les configurations possibles de cette aventure ? On pourra les décrire
en observant les personnages qui peuvent se trouver sur la rive de départ et la
rive d’arrivée.
92 Plan d’une ville
CHAPITRE 5. GRAPHES : MODÉLISATION ET PARCOURS
2. Modéliser alors le problème sous la forme d’un graphe dont les sommets sont les
configurations possibles et les arêtes représentent l’évolution possible de l’aven-
ture.
3. Résoudre le problème à l’aide du graphe précédent. Décrire à la bergère les
allers-retours qu’elle doit faire. Combien de traversées la bergère doit-elle faire ?
Existe-t-il plusieurs solutions avec ce nombre minimal de traversées ? Les donner
toutes.
Définition 6. Un graphe orienté est la donnée d’un ensemble fini S de sommets (ou nœuds)
Plan d’une ville
5.3. GRAPHES ORIENTÉS : APPLICATION AUX GRAPHES DE CONFIGURATION93
et d’un ensemble fini A de couples de sommets qu’on appelle arcs : si u et v sont deux
sommets, l’arc (u, v) représente le fait qu’il existe un arc partant du sommet u et allant au
sommet v. On note parfois G = (S, A) le graphe.
Notez qu’on utilise la notation {u, v} pour une paire de sommets (différents), une arête
dans un graphe non orienté, alors qu’on utilise la notation (u, v) pour un couple de sommets
(potentiellement le même sommet deux fois), un arc dans un graphe orienté. En particulier,
si 1 et 2 sont deux sommets du graphe, les arêtes {1, 2} et {2, 1} sont les mêmes, alors que
les arcs (1, 2) et (2, 1) sont différents. Pour les rues dans un plan, une rue à sens unique sera
représentée par un arc dans un seul sens, alors qu’une rue à double-sens est représentée par
deux arcs, un pour chaque sens.
Voici un exemple de graphe orienté pour lequel l’ensemble de sommets est S = {0, 1, 2, 3, 4}
et l’ensemble d’arcs (qu’on représente par des liens avec des flèches) est A = {(0, 1), (1, 0), (1, 2),
(1, 4), (2, 4), (3, 0), (3, 2), (3, 3)} :
94 CHAPITRE 5. GRAPHES : MODÉLISATION ET PARCOURS
1 2
3 4
Un chemin dans un tel graphe orienté G = (S,A) est une suite de sommets s1 ,s2 ,s3 , . . . ,
sn−1 ,sn qui sont reliés par un arc, c’est-à-dire tel que (s1 ,s2 ) ∈ A, (s2 ,s3 ) ∈ A, . . ., et
(sn−1 ,sn ) ∈ A. La longueur d’un chemin est le nombre d’arcs qu’il emprunte. Par exemple
3,3,0,1,4 est un chemin de longueur 4 dans le graphe orienté précédent.
Les graphes orientés permettent de représenter des graphes des configurations qu’on utilise
dans diverses applications. Si on cherche à modéliser un système qui évolue dans le temps, on
appelle configuration d’un tel système son état à un instant donné : l’évolution du système,
sa dynamique, peut alors parfois être représentée comme un graphe dans lequel les sommets
abritent les configurations et un arc relie une configuration c1 à une configuration c2 s’il est
possible de passer de manière élémentaire de c1 à c2 lors de l’évolution du système.
Exercice 36
Dans le film Die Hard 3 (Une journée en enfer ), les deux héros, John McClane et
Zeus Carver, doivent résoudre l’énigme de Simon Gruber pour arrêter le compte à
rebours d’une bombe. Voici l’énigme : ≪ Sur la fontaine, il y a deux bidons : l’un a
une contenance de 5 gallons, l’autre de 3 gallons. Remplissez l’un des bidons de 4
gallons d’eau exactement et placez-le sur la balance. La minuterie s’arrêtera. Soyez
extrêmement précis : un gramme de plus ou de moins et c’est l’explosion ! ≫. Les nerfs
de John McClane sont alors mis à rude épreuve pour trouver une solution. Il commence
par remarquer très justement qu’on ne peut pas remplir le bidon de 3 gallons avec 4
gallons d’eau. Il faut donc trouver le moyen de mettre exactement 4 gallons d’eau dans
le bidon de 5 gallons. Dans la scène du film (que vous pouvez consulter en français sur
[Link] John commence par donner une
première idée peu convaincante puisqu’elle termine par la nécessité de remplir le bidon
de 3 gallons au tiers, ce qu’on ne sait faire précisément... Le film propose ensuite une
solution très partielle, coupée au montage. Appliquons donc des méthodes de graphes
orientés pour retrouver la meilleure solution possible que les héros appliquent pour
s’en sortir.
1. Une configuration du système correspond au volume d’eau contenu dans chacun
des deux bidons. On peut donc représenter une telle configuration par une paire
(a,b) où a est le volume d’eau contenu dans le bidon de 5 gallons et b le volume
d’eau contenu dans le bidon de 3 gallons, avec 0 ≤ a ≤ 5 et 0 ≤ b ≤ 3. Les
actions élémentaires possibles du système sont de remplir un des deux bidons
(qu’il soit initialement vide ou pas), vider un des deux bidons (qu’il soit ini-
5.4. CODAGE D’UN GRAPHE 95
tialement plein ou pas) et transférer le contenu d’un des bidons dans l’autre
jusqu’à ce que ce dernier soit plein. En partant de la configuration initiale (0,0),
construire le graphe orienté décrivant entièrement l’ensemble des configurations
et la dynamique du système. Attention, certains mouvements ne sont possibles
que dans un seule sens, raison pour laquelle nous utilisons un graphe orienté
dans ce cas.
2. En déduire une solution la plus courte possible permettant d’aller de la configu-
ration (0,0) à une configuration de la forme (4,b) où exactement 4 gallons d’eau
se trouvent dans le gros bidon. Décrire à John McClane la suite d’opérations
qu’il doit effectuer pour arrêter la bombe au plus vite.
3. Imaginons la suite de l’énigme désormais. Dans une autre fontaine, le terroriste
a placé deux bidons, l’un de 6 gallons et l’autre de 15 gallons. S’il demande à
John McClane de remplir l’un des deux bidons avec exactement 5 gallons d’eau,
pourra-t-il éviter l’explosion de la bombe ?
Exercice 38
1. Écrire un algorithme en pseudo-code, qui prend en entrée la matrice d’adjacence
d’un graphe orienté, et renvoie le nombre d’arcs dans le graphe.
2. Comment modifier votre algorithme pour qu’il compte le nombre d’arêtes d’un
graphe non orienté ?
depuis s : au fur et à mesure où le ballon se gonfle, il voit de plus en plus de sommets du
graphe, ceux qui sont de plus en plus éloignés du sommet s. Sur le cours Ametice en ligne,
une activité vous est proposé pour découvrir le parcours en largeur, à l’aide d’une vidéo et
d’exercices associés. Si vous pouvez y accéder, faites-le avant ou en même temps que vous lisez
la suite... Sinon, toutes les informations sont redonnées dans la suite et fin de ce chapitre.
Pour exécuter le parcours en largeur, nous allons utiliser une des structures de données
dont nous avons parlé au début du chapitre 3, les files qui permettent de stocker un ensemble
de clients en se souvenant de l’ordre dans lequel ils sont arrivés afin de servir les clients dans
leur ordre d’arrivée. Dans le cas du parcours en largeur, les clients seront les sommets du
graphe. Considérons ainsi le graphe ci-dessous qu’on souhaite parcourir à partir de la source
s=0:
1 2 5
3 4 6
On va colorier les sommets avec la couleur rouge (en plus du blanc initial) pour enregistrer
de l’information. La première chose qu’on fait est d’ailleurs de colorer en rouge la source
s = 0 et de l’insérer dans la file d’attente. Ensuite, on traite l’unique sommet dans la file
d’attente. Traiter un sommet u signifie regarder tous ses voisins, c’est-à-dire considérer tous les
sommets v tels que (u, v) est un arc du graphe. En l’occurrence, puisqu’on traite le sommet 0,
on va donc considérer ses voisins 1 et 3. Pour chacun de ses voisins, s’ils sont blancs, on
les colorie en rouge et on les insère dans la file d’attente. Après avoir traité entièrement
le sommet 0, on arrive donc dans la situation suivante, dans laquelle on colorie également
en rouge les arcs qui nous ont permis d’aller de la source 0 aux différents sommets déjà
découverts :
1 2 5
File : 1, 3 0
3 4 6
1 2 5
File : 3, 2 0
3 4 6
On traite ensuite le sommet inséré il y a le plus longtemps dans la file d’attente, c’est-à-dire
le sommet 3. Il n’a qu’un seul voisin, le sommet 4, qu’on colorie donc en rouge :
1 2 5
File : 2, 4 0
3 4 6
On traite ensuite le sommet 2, qui n’a aucun voisin. Il ne reste ensuite que le sommet 4
dans la file d’attente. Il a deux voisins blancs, les sommets 5 et 6, qu’on traite donc pour
obtenir la situation
1 2 5
File : 5, 6 0
3 4 6
Il reste ensuite les sommets 5 et 6 à traiter, dans cet ordre, mais tous les sommets étant
déjà rouges, on ne fait rien de plus. Le graphe précédent est donc la situation finale sur
laquelle on s’arrête. Observons qu’on a bien découvert tous les sommets du graphe qu’on
pouvait atteindre via un chemin depuis le sommet 0. De plus, si on ne regarde que les arêtes
colorées en rouge :
1 2 5
3 4 6
on obtient une représentation d’un chemin possible pour aller de la source s = 0 à n’importe
quel sommet rouge : pour aller de 0 à 5 par exemple, il faut suivre le chemin 0, 3, 4, 5. Notons
5.5. PARCOURS DE GRAPHE 99
qu’il s’agit d’un plus court chemin (en terme du nombre d’arcs visités) pour aller de 0 à 5.
C’est une propriété toujours satisfaite par le parcours en largeur : il permet de construire les
plus courts chemins issus de la source s.
Voici une façon de décrire, à l’aide d’un pseudo-code, l’algorithme de parcours en largeur,
dans lequel on suppose que les n sommets du graphe sont numérotés {0, 1, 2, . . . , n−1} comme
dans les exemples précédents :
def p a rc o u rs _ e n_ l a rg e u r (M , s ) :
n = len ( M )
H = graphe_vide ( n ) # graphe sans arcs avec n sommets
F = file_vide ()
couleur = [ " blanc " ] * n
couleur [ s ] = " rouge "
ins é rer (F , s )
while not est_vide ( F ) :
u = extraire ( F )
for v in range ( n ) :
if ( M [ u ][ v ] == 1) and ( couleur [ v ] == " blanc " ) :
couleur [ v ] = " rouge "
H [ u ][ v ] = 1
ins é rer (F , v )
return H # graphe des chemins minimaux
Exercice 39
1. Exécuter l’algorithme de parcours en largeur sur le graphe G représenté ci-
dessous à partir du sommet s = 0, en montrant toutes les étapes de l’algorithme
(avec la coloration des sommets et l’état de la file dans les configurations in-
termédiaires). Représenter aussi le graphe H retourné par la fonction.
100 CHAPITRE 5. GRAPHES : MODÉLISATION ET PARCOURS
1 2
0 3
5 4
L’algorithme de parcours en largeur permet donc de trouver des plus courts chemins dans
des graphes. Ici, plus court veut dire ≪ qui utilise le moins d’arcs/arêtes possible ≫. C’est
suffisant pour résoudre le problème de Pagnol et de Die Hard 3, mais pas pour trouver des
plus courts chemins dans un plan, puisqu’alors ce n’est pas tant le nombre d’arcs qui compte
que le temps ou la distance parcourue au total le long de l’itinéraire choisi.
Pour résoudre ce problème, il faut donc incorporer dans la modélisation en graphe une
information supplémentaire, que ce soit le temps pour parcourir l’arc (c’est-à-dire le temps
qu’il faut pour aller en voiture d’une intersection à une autre), ou plus simplement la longueur
de l’arc (c’est-à-dire la distance qui sépare les deux intersections). On utilise pour cela la notion
de graphe pondéré.
Définition 7. Un graphe pondéré est la donnée d’un graphe orienté (S, A) et d’une fonction
p : A → N associant un poids (qu’on suppose entier naturel ici) à chaque arc du graphe. On le
représente à l’aide d’une matrice d’adjacence M à coefficients dans N ∪ {+∞} dans laquelle
le coefficient M [u][v] vaut p(u, v) si (u, v) ∈ A, et vaut +∞ sinon.
Voici un exemple de graphe pondéré dans lequel on fait apparaı̂tre le poids de l’arc à côté
de celui-ci :
5.6. PLUS COURTS CHEMINS DANS DES GRAPHES PONDÉRÉS : ALGORITHME DE DIJKSTRA101
1
1 2
10
9
0 2 3 4 6
3 4
2
7
On a ainsi, par exemple, p(0, 1) = 10 et p(4, 0) = 7. On peut coder ce graphe pondéré avec la
matrice d’adjacence
+∞ 10 +∞ 5 +∞
+∞ +∞ 1 2 +∞
M =
+∞ +∞ +∞ +∞ 4
+∞ 3 9 +∞ 2
7 +∞ 6 +∞ +∞
Pour un chemin s1 , s2 , s3 , . . . , sn−1 , sn dans le graphe (S, A), le poids du chemin est la
somme des poids des arcs empruntés, c’est-à-dire p(s1 , s2 ) + p(s2 , s3 ) + · · · + p(sn−1 , sn ). Un
plus court chemin d’un sommet u à un sommet v est un chemin de poids minimal parmi
tous les chemins allant de u à v (s’il existe un tel chemin). Par exemple, le chemin 0, 1, 2 est
un chemin de 0 à 2, mais ce n’est pas un plus court chemin car le chemin 0, 3, 1, 2 est plus
court en terme de poids : c’est d’ailleurs un plus court chemin pour aller de 0 à 2. On appelle
distance de u à v le poids d’un plus court chemin de u à v. Par exemple, la distance de 0 à 2
est donc 9, alors que la distance de 0 à 4 vaut 7.
On cherche donc un algorithme qui permet de calculer la distance d’une source s à tout
autre sommet, de la même manière que le parcours en largeur permettait de trouver tous les
sommets qu’on peut atteindre à partir de s. En plus des distances, on aimerait aussi pouvoir
trouver des plus courts chemins. Clairement l’algorithme de parcours en largeur n’est plus
correct, puisqu’il renvoie le résultat suivant pour le graphe pondéré précédent, à partir de la
source s = 0 :
102 CHAPITRE 5. GRAPHES : MODÉLISATION ET PARCOURS
1
1 2
10
9
0 2 3 4 6
3 4
2
7
ce qui est incorrect puisqu’alors on en déduirait que la distance de 0 à 1 vaut 10, alors même
qu’elle vaut 8.
On doit donc corriger l’algorithme. C’est Edsger Wybe Dijkstra (né en 1939 et mort en
2002) qui a proposé une façon élégante de corriger l’algorithme de parcours en largeur pour
qu’il fonctionne dans des graphes pondérés. Son idée : plutôt que de stocker les sommets à
traiter dans une file d’attente, utilisons donc plutôt une file de priorité. Il a donc utilisé le
concept de file prioritaire à la caisse d’un magasin, dans le contexte des graphes pondérés...
Ici, chaque sommet u aura donc une priorité qui correspond à l’estimation courante qu’on a de
la distance de la source s à u. Au début, on part avec une estimation très pessimiste associant
une distance +∞ à tout sommet u, sauf la source à qui on associe la distance 0. À chaque
étape, on traite le sommet qui a la plus faible priorité dans la file d’attente, c’est-à-dire celui
dont on pense qu’il est le plus proche de la source possible.
1
10 1 2 +∞
10
9
File : 3 (5), 1 (10) 0 0 2 3 4 6
5 3 4 +∞
2
7
Bien qu’on ait sans doute traiter le voisin 1 avant le voisin 3, la priorité de 3 est plus faible
que celle de 1 : c’est donc avec ce sommet qu’on continue. On considère donc les voisins de
3, à savoir 1, 2 et 4. C’est là que l’algorithme se distingue du parcours en largeur. Ici, même
si le sommet 1 est rouge, il faut mettre à jour l’information de distance, puisqu’on a trouvé
un chemin 0, 3, 1 de poids 8, plus petit que l’estimation courante de la distance. On doit donc
mettre à jour les distances et les priorités dans la file (cela revient à dire qu’on a une file
à la caisse d’un magasin dans laquelle les priorités des clients peuvent changer au cours du
temps...). On met également à jour la coloration des arcs, puisqu’on souhaite que les arcs
colorés en rouge représentent les plus courts chemins. On traite ensuite les voisins 2 et 4 en
les insérant dans la file d’attente. On arrive donc à la situation suivante :
1
8 1 2 14
10
9
File : 4 (7), 1 (8), 2 (14) 0 0 2 3 4 6
5 3 4 7
2
7
Le sommet prioritaire dans la file est désormais le sommet 4. Rien à faire avec son voi-
sin 0, puisque l’estimée courante de la distance, 0, est imbattable. Par contre, on met à jour
l’estimation de la distance pour le voisin 2 :
104 CHAPITRE 5. GRAPHES : MODÉLISATION ET PARCOURS
1
8 1 2 13
10
9
File : 1 (8), 2 (13) 0 0 2 3 4 6
5 3 4 7
2
7
1
8 1 2 9
10
9
File : 2 (9) 0 0 2 3 4 6
5 3 4 7
2
7
Il reste le sommet 2 à traiter qui n’induit aucun changement : le graphe précédent est
donc la situation finale. Ce graphe contient les informations des distances de 0 à chacun des
sommets et on peut également reconstituer des plus courts chemins, en ne considérant que
les arcs rouges.
Afin d’écrire cet algorithme 1 , il nous faut disposer d’une file de priorité. On peut l’ini-
tialiser à l’aide d’une fonction file priorité vide() qui renvoie une file de priorité vide F .
Par rapport à une file d’attente, les éléments de F seront associés à une priorité (un entier
naturel). On suppose connue les opérations suivantes :
— on peut insérer un nouvel élément u dans la file, en précisant sa priorité p ∈ N à l’aide
de la fonction insérer priorité(F, u, p) ;
— est vide(F) qui teste si la file de priorité F est vide ;
— l’élément prioritaire est celui de plus petite priorité : on peut récupérer cet élément
à l’aide de la fonction extraire prioritaire(F) qui supprime au passage l’élément
renvoyé ;
1. Rassurez-vous, ce sera l’algorithme le plus difficile de ce cours, il n’est donc pas impossible qu’il vous
donne quelques sueurs froides...
5.6. PLUS COURTS CHEMINS DANS DES GRAPHES PONDÉRÉS : ALGORITHME DE DIJKSTRA105
— on peut mettre à jour la priorité d’un élément u de la file pour lui attribuer la nouvelle
priorité p dans F , à l’aide de la fonction mettre à jour priorité(F, u, p).
Une autre différence notable entre le parcours en largeur et l’algorithme de Dijkstra réside
dans la nécessité de maintenir les estimations des distances (on utilise un tableau distance
pour cela) et de mettre à jour les arcs rouges : pour cela, plutôt que de maintenir un graphe H
comme précédemment, on utilise plutôt un tableau prédécesseur qui associe à chaque som-
met v rouge son prédécesseur dans le graphe H, c’est-à-dire l’unique sommet u tel que (u, v) est
un arc rouge de H. Si le sommet est blanc (ou pour la source qui n’a pas de tel prédécesseur), on
utilise le symbole ⊥ pour dénoter l’absence de prédécesseur. Ces transformations permettent
d’obtenir l’algorithme suivant :
def dijkstra (M , s ) :
n = len ( M )
distance = [+∞] * n
pr é d é cesseur = [⊥] * n
F = file_priorit é _vide ()
couleur = [ " blanc " ] * n
couleur [ s ] = " rouge "
distance [ s ] = 0
ins é rer_priorit é (F , s , 0)
while not est_vide ( F ) faire
u = extraire_prioritaire (F)
d = distance [ u ]
for v in range ( n ) :
if ( couleur [ v ] == " blanc " ) and ( M [ u ][ v ] != +∞) :
couleur [ v ] = " rouge "
pr é d é cesseur [ v ] = u
distance [ v ] = d + G [ u ][ v ]
ins é rer_priorit é (F , v , distance [ v ])
elif d + G [ u ][ v ] < distance [ v ]:
pr é d é cesseur [ v ] = u
distance [ v ] = d + G [u , v ]
mettre_ à _jour_priorit é (F , v , distance [ v ])
return pr é d é cesseur
Exercice 40
1. Exécuter l’algorithme de Dijkstra sur l’exemple ci-dessous en partant de la
source s = 0 :
2
2 3
10 1
9
0 2 1 6 4 1
5 2
4 5
1
7
106 CHAPITRE 5. GRAPHES : MODÉLISATION ET PARCOURS
1
5 1
0 −4 3
7 −2
2
On l’a vu dans le chapitre précédent, les graphes sont très utiles pour représenter des
situations dans lesquelles on se pose une question d’accessibilité d’un sommet à un autre : un
algorithme de parcours (ou l’algorithme de Dijkstra dans le cas des graphes pondérés) permet
alors de résoudre cette question.
Il existe d’autres problèmes pertinents qu’on peut se poser sur les graphes, nous amenant
à raisonner sur les graphes, avant de produire à nouveau des algorithmes pour résoudre
automatiquement ces problèmes. Dans ce chapitre, nous allons en étudier deux bien différents :
les graphes eulériens et la coloration de graphe.
107
108CHAPITRE 6. THÉORIE DES GRAPHES : CHEMINS EULÉRIENS ET COLORATION
Un guide touristique se pose alors la question, pour attirer une foule de touristes toujours
plus grande dans ses visites, de savoir s’il est possible de faire visiter la ville en faisant un
circuit passant une fois par chaque pont, mais sans passer deux fois par le même pont. On
veut donc partir d’un endroit dans la ville, faire un tour qui passe par chaque pont une et
une seule fois, puis être revenu au point de départ.
On voit bien que la carte précédente recèle bien trop de détails qu’on peut ignorer pour
Problème des sept ponts
répondre à la question. Il suffit de ne garder que les ponts et la façon dont ils sont reliés entre
eux, par les rives et les ı̂les de Königsberg, comme représenté en Figure 6.2.
de Königsberg
Si on ne garde que le graphe représenté en rouge, on arrive à la modélisation suivante :
Notez que ce graphe est un peu particulier. C’est un graphe non orienté ayant quatre
sommets, mais il y a plusieurs arêtes reliant la même paire de sommets : on appelle souvent
ce genre de graphe des multi-graphes, signifiant qu’on s’autorise à mettre plusieurs arêtes
plutôt qu’une seule entre certaines paires de sommets. Dans un tel graphe non orienté, on
appelle cycle eulérien tout cycle (un chemin qui revient à son point de départ) qui traverse
chaque arête du graphe une et une seule fois. Partez donc de n’importe quel sommet, puis
essayez de créer un cycle eulérien dans le graphe précédent.
Vraisemblablement, vous n’y arriverez pas : il vous restera toujours une arête au moins
non visitée alors que vous serez coincé dans un sommet d’où vous avez déjà visité toutes
les arêtes y arrivant... Rassurez-vous, ce n’est en rien de votre faute. Leonhard Euler lui-
même s’est fait la même réflexion et a fini par se convaincre que, dans ce graphe, il n’y a
pas de cycle eulérien. Il en a même déduit une recette miraculeuse permettant de décider
6.1. GRAPHES EULÉRIENS : LE PROBLÈME DES SEPT PONTS DE KÖNIGSBERG109
en un instant s’il y a un cycle eulérien ou pas dans un graphe. Pour cela, notons dans un
premier temps que la présence d’un cycle visitant toutes les arêtes du graphe n’est possible
que si le graphe est en un seul morceau, c’est-à-dire qu’il est possible de relier toute paire
de sommets par un chemin (une suite d’arêtes consécutives) : on parle alors de graphes
connexes. Le graphe de Königsberg est connexe. Sa recette miraculeuse consiste à compter,
pour un sommet quelconque, le nombre d’arêtes arrivant dans ce sommet, qu’on appelle le
degré du sommet. Dans le graphe de Königsberg, trois sommets ont degré 3 et le sommet
représentant l’ı̂le centrale a degré 5. Euler remarqua que s’il existe un cycle eulérien, alors
celui-ci visite toutes les arêtes du graphe (par définition) : pour chaque sommet, on doit donc
rentrer autant de fois dedans qu’on en sort. Autrement dit, le degré de chaque sommet doit
être pair. Ce qui est intéressant, c’est que cette condition est aussi suffisante :
Cette condition permet tout de suite d’affirmer qu’il n’y a donc pas de cycle eulérien dans
le graphe de Königsberg, puisque les quatre sommets ont un degré impair.
Exercice 41
En utilisant la caractérisation précédente, dites pour chacun des graphes suivants s’ils
admettent un cycle eulérien. Attention, on ne demande pas de trouver un tel cycle
eulérien s’il existe, mais vous pouvez bien sûr essayer si vous le voulez !
G1 A G2 A B
E B
D C
D C
G3 A
B
H
F
C
E
D
I
G
C’est l’algorithme de Hierholzer qui nous permet de construire un cycle eulérien (s’il en
existe un). On peut le décrire de manière informelle ainsi :
— Choisir n’importe quel sommet initial v
— Suivre un chemin arbitraire d’arêtes jusqu’à retourner à v, obtenant ainsi un cycle c
— Tant qu’il y a des sommets u dans le cycle c avec des arêtes qu’on n’a pas encore
choisies :
— Suivre un chemin à partir de u, n’utilisant que des arêtes pas encore choisies, jusqu’à
retourner à u, obtenant un cycle c′
Algorithme de Hierholzer
— Prolonger le cycle c par c′
Voici une exécution de l’algorithme sur le graphe suivant :
Algorithme de Hierholzer
On choisit arbitrairement un sommet initial Algorithme
(marqué par lade Hierholzer
flèche rouge), puis on suit un
chemin arbitraire d’arêtes jusqu’à être retourné au sommet initial :
Algorithme de Hierholzer
Algorithme de Hierholzer
1 1
2
2
Algorithme de Hierholzer
Algorithme de Hierholzer 3
1 1
2 2
5
3
3
4
4
Algorithme
6.1. GRAPHES EULÉRIENS de DES
: LE PROBLÈME Hierholzer
SEPT PONTS DE KÖNIGSBERG111
2
6
On a obtenu un cycle c, mais ce n’est pas encore un cycle eulérien puisque certaines arêtes
ne sont pas visitées. Dans ce cycle, trois sommets (marqués par les flèches bleues ci-dessous)
ont des arêtes qu’on n’a pas encore choisies :
Algorithme de Hierholzer
2
6
1 1
2 2
6 6
1
5 5
Algorithme de Hierholzer
Algorithme de Hierholzer
3 3
4 4
1 1
2 2
6 3
6
2 2
1 1
5 5
3 3
4 4
Algorithme
112CHAPITRE 6. THÉORIE DES GRAPHES : CHEMINSde
EULHierholzer
ÉRIENS ET COLORATION
Algorithme de Hierholzer
4 1
4 1
3 5 2
3 2 6
6
2
2 1
1
5
5
3 3
4 4
Il reste à insérer le cycle c′ au sein du cycle c, c’est-à-dire qu’après avoir visité les deux
premières arêtes de c, on se met en pause pour visiter le cycle c′ entièrement, avant de terminer
avec les quatre dernières arêtes de c. Pour faire cela, il suffit d’ajouter au numéro des quatre
Algorithme
dernières arêtes de c la longueur de c′ : de Hierholzer
4 1
3 5 2
6+5
2
1
5+5
3+5
4+5
Algorithme de Hierholzer
Algorithme de Hierholzer
puis de décaler les numéros des arêtes du cycle c de deux pour l’insérer au bon endroit :
4+2 1 6 1
5+2 2 7 2
3+2 5
11 11
2+2 4
1+2 3
10 10
8 8
9 9
On obtient donc un cycle un peu plus long qui ne visite pas deux fois la même arête. Ce
n’est toujours pas un cycle eulérien : deux sommets dans le cycle ont encore des arêtes non
visitées Algorithme de Hierholzer
6 1
5 7 2
11
4
3
10
9
6.1. GRAPHES EULÉRIENS : LE PROBLÈME DES SEPT PONTS DE KÖNIGSBERG113
6 1 6 1
5 7 2 5 7 2
11 11
1
4 4
3 3
10 10
Algorithme de Hierholzer
Algorithme de Hierholzer 8 8
9 9
6 1
6 1
5 7 2
11
5 7 2
11
1
4
3 1
4
3 3
10
10
Algorithme de Hierholzer
Algorithme de Hierholzer
8
2 8
9 2
9
6+3 1 9 1
7+3 2 10 2
5 5
11 + 3 14
1 1+5
4 4
3 3 3+5 3
10 + 3 13
8+3 11
2 2+5
9+3 12
Algorithme de Hierholzer
On obtient finalement le cycle eulérien suivant :
9 1
5 10 2
14
6
4
8 3
13
11
7
12
y entrer). Ces arguments sont encore vrai pour la recherche du cycle autour de u, ce qui fait
que l’algorithme de Hierholzer termine. Il produit bien un cycle qui visite toutes les arêtes
du graphe, sinon, par connexité, au moins un des sommets devraient avoir encore une arête
non visitée. Finalement, il ne peut pas visiter deux fois la même arête, par construction : il
produit donc bien un cycle eulérien. Cela prouve donc le théorème d’Euler.
Exercice 42
1. Pour les graphes de l’exercice 41 qui admettent un cycle eulérien, trouver un tel
cycle en appliquant l’algorithme de Hierholzer.
2. La notion de cycle eulérien peut être étendue : un chemin eulérien est un chemin
(pas nécessairement un cycle) qui traverse chaque arête du graphe une et une
seule fois. Parmi les graphes suivants, quels sont ceux pour lesquels vous pouvez
trouver un chemin eulérien ?
G4 A G5 A G6 A
B C B C B C
F H F
D E D E D E
G
3. À partir de vos observations, conjecturer une caractérisation des graphes
possédant des chemins eulériens en termes de degrés des sommets du graphe
(ressemblant à la caractérisation des graphes possédant des cycles eulériens).
Théorème 3. On peut colorer n’importe quelle carte avec un maximum de quatre couleurs
de sorte que les zones adjacentes reçoivent toujours deux couleurs distinctes.
la main. L’utilisation de l’ordinateur s’avère donc indispensable mais a alors partagé la com-
munauté scientifique pour savoir si cela pouvait effectivement encore s’appeler une preuve.
Ce qui est sûr, c’est que le problème de prouver le théorème se déplace (comme dans le cas
de l’algorithme de Hierholzer pour le théorème d’Euler) sur la preuve de correction de l’al-
gorithme qui sert à vérifier les ≪ petits ≫ graphes. À l’heure actuelle, on ne connait toujours
pas de preuve entièrement à la main de ce théorème pourtant simple à énoncer.
Mais quel rapport avec les graphes ? Si on zoome un peu sur la carte, on peut modéliser le
problème avec un graphe non orienté dont les sommets seront les pays à colorier et les arêtes
sont les frontières reliant ces pays :
Coloration de graphes
Colorier la carte revient donc à colorier les sommets du graphe, de sorte que deux sommets
reliés par une arête ne sont pas coloriés avec la même couleur :
116CHAPITRE 6. THÉORIE DES GRAPHES : CHEMINS EULÉRIENS ET COLORATION
Coloration de graphes
On appelle graphe planaire tout graphe qu’on peut obtenir par cette méthode à partir
Graphes
d’une carte quelconque : c’est quiqu’on
donc un graphe ne peut
semblent
dessiner sur un plan (une feuille de
papier) sans qu’aucune arête n’en croise une autre. Attention, certains graphes ne semblent
pas planaires, comme celui-ci... pas planaires
Théorème 4. On peut colorer les sommets de tout graphe non orienté planaire avec un
maximum de quatre couleurs de sorte que les sommets adjacents (c’est-à-dire reliés par une
arête) reçoivent toujours deux couleurs distinctes.
Ce théorème permet de se convaincre que certains graphes ne sont pas planaires. Il suffit
pour cela de montrer qu’ils ne sont pas coloriables avec quatre couleurs. C’est par exemple
le cas du graphe complet (c’est-à-dire tel que toute paire de sommets est une arête) à cinq
sommets (ou plus) :
Graphes non planaires
6.2. COLORATION DE GRAPHES ET DES CARTES 117
On ne peut pas le colorier avec quatre couleurs puisque chaque sommet a quatre sommets
adjacents qui sont eux-même reliés entre eux. Par contre, noter que le théorème des quatre
Graphes non planaires
couleurs ne donne pas une condition nécessaire et suffisante pour être un graphe planaire. Le
graphe suivant n’est pas planaire, mais il peut être colorié avec deux couleurs :
Le théorème des quatre couleurs a une grosse lacune : il dit qu’il est possible de colorer un
graphe planaire avec quatre couleurs, mais ne donne pas de méthode pour faire cela. Comment
donc colorer effectivement un graphe planaire, ou une carte de géographie, à partir de là ?
Une première méthode naı̈ve pourrait consister à essayer toutes les possibilités de coloriage.
Dans le pire des cas, cela demande à essayer toutes les possibilités de coloriage des sommets
du graphe avec quatre couleurs. Un coloriage est une fonction de l’ensemble S des sommets
dans un ensemble de couleurs {0,1,2,3} à quatre éléments : ces fonctions sont au nombre
de 4|S| , qui est exponentiel en fonction du nombre de sommets. Il n’est donc clairement pas
envisageable d’essayer toutes les possibilités, dès lors que le graphe est un peu gros.
À la place, on étudie l’algorithme de Welsh-Powell, qu’on peut écrire de la manière sui-
vante :
— Trier les sommets du graphe par ordre de degré décroissant
— couleur ← 0 (couleur initiale)
— Tant qu’il y a encore des sommets non colorés
— Parcourir la liste triée des sommets et colorer en couleur les sommets non colorés
qui ne sont pas connectés à d’autres sommets de la même couleur
— couleur ← couleur + 1 (choisir une nouvelle couleur )
L’idée est donc très simple : on colorie les uns après les autres les sommets du graphe, en
le traitant dans l’ordre décroissant de leur degré, et on essaie d’attribuer à un maximum de
sommets la couleur 0, puis la couleur 1, puis la couleur 2, etc. Considérons par exemple le
graphe suivant dont les sommets sont les lettres de A à K :
Algorithme de Welsh-Powell
G
F
Algorithme de Welsh-Powell
118CHAPITRE 6. THÉORIE DES GRAPHES : CHEMINS EULÉRIENS ET COLORATION
H
G
F
K E
A H
J K E
A I
J
I
D
D
B C
B C
Tri des sommets par degré décroissant :
On commence par trier les sommets par ordre décroissant de degrés :
A
2
H K D G I J A B E F C
5 5 4 3 3 3 2 2 2 2 1
On commence par vouloir attribuer la couleur 0, disons rouge. On parcourt ainsi la liste
Algorithme de Welsh-Powell
précédente des sommets et on colorie le sommet en rouge, dès lors qu’aucun de ses voisins n’a
déjà cette couleur. On peut donc colorer les sommets H, D et E :
G
F
K E
A
J
I
B C
Algorithme de Welsh-Powell
colorés, et on colorie le sommet en bleu dès lors qu’aucun de ses voisins n’a déjà cette couleur.
5
On peut alors colorer les5sommets
4 3
K, 3
I, A, 3
F et C :2 2 2 2 1
G
F
K E
A
J
I
B C
H K D G I J A B E F C
5 5 4 3 3 3 2 2 2 2 1
6.2. COLORATION DE GRAPHES ET DES CARTES 119
On fait de même avec la couleur suivante, le vert par exemple, pour colorer les sommets
restants G, J et B :
Algorithme de Welsh-Powell
G
F
K E
A
J
I
B C
H K D G I J A B E F C
On a donc réussi à colorer ce graphe planaire avec trois couleurs seulement. Notons qu’il n’est
5 5 4 3 3 3 2 2 2 2 1
pas possible de faire mieux, c’est-à-dire de n’utiliser que deux couleurs seulement. En effet, ce
graphe possède un triangle, c’est-à-dire trois sommets reliés les uns aux autres, par exemple
les sommets H, I et J : un tel triangle nécessite trois couleurs puisque chaque sommet est relié
à deux autres sommets reliés entre eux. Sur ce graphe, l’algorithme de Welsh-Powell renvoie
donc une coloration optimale, c’est-à-dire avec le nombre minimal de couleurs possible.
Ce n’est malheureusement pas toujours le cas. Par exemple, sur le graphe suivant, où tous
les sommets ont degré 2, si on suit l’ordre alphabétique de traitement des sommets, on arrive
A A
C C
F F
D D
E B E B
A
En fait, ce graphe neB nécessite
C D
que EdeuxF couleurs, puisqu’on
A B C
peut D E
colorer lesF sommets A, D
et E d’une même2 couleur,
2 2puis 2B, C2 et F2 d’une autre2 même
2 couleur.
2 2 2 2
Exercice 43
À chaque fois que deux sommets ont le même degré, on les suppose triés par ordre
alphabétique. Par exemple, si les sommets A, D, B sont tous de degré 3, on suppose
qu’ils seront triés dans l’ordre A, B, D.
1. Colorier les graphes suivants à l’aide de l’algorithme de Welsh-Powell.
120CHAPITRE 6. THÉORIE DES GRAPHES : CHEMINS EULÉRIENS ET COLORATION
A B C D
A B C
E F G
C H
G1 G2 D E C
F
I J K
C L
G H I
M N O
C P
Exercice 44
1. Dessiner une carte pour chacun des graphes suivants.
A B
A B A D
A B C
D C
C B E
C A
F I D
G E
B
J
Arbres
Passons à l’étude de graphes très particuliers, les arbres. Eux aussi, nous les retrouvons un
peu partout dans notre vie quotidienne, et nous allons voir que leur étude permet de résoudre
des problèmes informatiques intéressants.
001000110100010011101000100100
11010010100100000101110
121
122 CHAPITRE 7. ARBRES
Répertoires et fichiers
/
[Link]
Users Applications System
bmonmege jdupont
Firefox
2 tirages
sans remise
3/4
2 3 3 1 3
× + × =
1/2 5 4 5 2 5
3/5
1/2
soit 23 bits. Nous avions vu alors que souvent le codage variable permet d’obtenir un code
plus court pour les mots de la langue française. En revanche, un des points négatifs était que
le décodage semble plus difficile. Si on donne simplement la suite de bits, par exemple,
100010010111100000001010010110100110100000001001
7.2 Définitions
Qu’ont en commun les arbres qu’on a vus jusque-là ? Ce sont des graphes non orientés
particuliers. De plus, ils sont tous d’un seul tenant : nous avons vu dans le chapitre précédent le
124 CHAPITRE 7. ARBRES
En revanche, l’exemple ci-dessous n’est pas un arbre puisque ce graphe n’est pas connexe : il
est en deux morceaux détachés
126 CHAPITRE 7. ARBRES
Pas un arbre : pas connexe
1
5
Finalement, ce dernier exemple ci-dessous est bien connexe, mais possède un cycle : ce n’est
donc pas non plus un arbre Pas un arbre : avec cycle
1
5
Une autre particularité des graphes vus précédemment est qu’ils ont un sommet ayant un
statut particulier : c’est la racine de l’arbre. Il s’agit simplement d’un sommet désigné que l’on
dessine généralement tout en haut de l’arbre (tout en bas dans le cas de l’arbre généalogique,
tout à gauche dans le cas de l’arbre de probabilités). Un arbre possédant une racine s’appelle
souvent un arbre enraciné. On peut donc reprendre l’arbre précédent, choisir 1 comme sommet
Arbres enracinés
racine, puis comme si on remontait le sommet 1 tout en haut en le tenant entre nos doigts,
on obtient la représentation du même arbre :
1 racine de l’arbre
enfants
enfants de laracine
de la racine
6 4 5
2 3
enfant du nœud 4
feuilles
Dans ce cas, les sommets 4, 5 et 6 sont les enfants du sommet 1. De même, le sommet 3 est
l’unique enfant du sommet 4. Les sommets 2, 3 et 5 n’ont pas d’enfants : on dit qu’ils sont
des feuilles, pour conserver l’analogie botanique. On dit d’ailleurs qu’un chemin allant de la
racine à une feuille est une branche de l’arbre.
7.3. ARBRES BINAIRES 127
2
Arbres binaires 3 2 3
4 5 6 7 4 5
1
nil nil nil nil nil nil nil nil
nil nil nil nil nil nil nil nil
Arbre dont chaque nœud a 1 ou 2 enfants Arbre dont chaque nœud a 1 ou 2 enfants
2 3
4 6
A A
B E B E
C D F nil C D F
La racine de cet arbre est le nœud A qui a deux enfants : l’enfant gauche a B pour racine,
et l’enfant droit a E pour racine. Les enfants du nœud C sont deux arbres vides nil. Une
feuille est un nœud qui possède l’arbre vide comme enfants gauche et droit : les feuilles de
l’arbre du dessus sont C, D et F .
128 CHAPITRE 7. ARBRES
Considérons désormais des problèmes de la vie réelle que l’on va pouvoir traiter à l’aide
d’arbres. Reprenons l’exemple de l’arborescence de fichiers de la Figure 7.2. Parfois, on a
besoin d’afficher cette arborescence sous forme d’une liste de fichiers. Un outil permet de faire
cela sous un système d’opérations Unix, tel que Linux ou Mac : l’utilitaire ls qui lorsqu’on
l’exécute dans un terminal avec l’option -R pour signifier qu’on souhaite rentrer récursivement
dans les sous-répertoires, on obtient le résultat suivant
$ ls -R
liste de fichiers
System
./Users:
bmonmege
jdupont
./Users/bmonmege:
Documents
Downloads
./Users/bmonmege/Documents:
pré[Link]
[Link]
./Users/bmonmege/Downloads:
[Link]
./Users/jdupont:
Documents
./Users/jdupont/Documents:
./Applications:
Firefox
On parcourt l’arborescence de fichiers…
./System:
Le programme ls commence par imprimer les noms des fichiers et répertoires contenus di-
rectement dans le répertoire racine. Ensuite, il imprime le contenu du premier répertoire
entièrement, avant de passer au second répertoire, puis le troisième répertoire. L’impression
du premier répertoire /Users est longue puisque, de même, il faut commencer par imprimer
le nom des deux répertoires, puis le contenu de chacun, et ainsi de suite.
Remis dans le contexte d’un arbre binaire (plutôt qu’un arbre quelconque comme pour
l’arborescence de fichiers), cela revient à considérer le parcours suivant
Parcours d’arbres binaires
Parcours d’arbres binaires
7.4. AFFICHAGE D’UNE ARBORESCENCE DE FICHIERS : PARCOURS PRÉFIXE129
2 3
2 3
4 5 6 7
4 5 6 7
1 2 4 5 3 6 7
Un tel parcours, qu’on appelle parcours préfixe puisqu’il traite chaque nœud avant de
traiter ses enfants, peut être implémenté par un algorithme récursif (nous avons déjà vu un
algorithme récursif lorsque nous avons étudié le tri par fusion) :
def parcours_pr é fixe ( nœud ) :
if nœud != nil :
afficher ( valeur [ nœud ])
parcours_pr é fixe ( enfant_gauche [ nœud ])
parcours_pr é fixe ( enfant_droit [ nœud ])
Parcours préfixe
Testons-le sur l’arbre précédent pour mieux comprendre comment s’exécute un algorithme
récursif. On commence par faire réapparaı̂tre les arbres vides :
2 3
4 5 6 7
2 3
4 5 6 7
On commence par le test nœud != nil qui est vrai puisque le nœud 1 n’est pas l’arbre vide.
On exécute donc les trois lignes internes, en commençant par afficher la valeur du nœud. On
appelle ensuite récursivement le même algorithme sur l’enfant gauche. Cela veut dire qu’on
met en pause l’exécution courante et qu’on démarre une exécution indépendante depuis le
début sur le nœud 2 :
Parcours préfixe
fonction parcourir_préfixe(nœud):
si nœud ≠ nil alors
fonction parcourir_préfixe(nœud): afficher(valeur[nœud])
si nœud ≠ nil alors parcourir_préfixe(enfant_gauche[nœud])
afficher(valeur[nœud])
parcourir_préfixe(enfant_gauche[nœud])
1 parcourir_préfixe(enfant_droit[nœud])
parcourir_préfixe(enfant_droit[nœud])
2 3
4 5 6 7
1
De même, on commence par imprimer le contenu du nœud 2, puis on fait l’appel récursif dans
l’enfant gauche :
Parcours préfixe
fonction parcourir_préfixe(nœud):
si nœud ≠ nil alors
fonction parcourir_préfixe(nœud): afficher(valeur[nœud])
si nœud ≠ nil alors parcourir_préfixe(enfant_gauche[nœud])
afficher(valeur[nœud])
parcourir_préfixe(enfant_gauche[nœud])
1 parcourir_préfixe(enfant_droit[nœud])
parcourir_préfixe(enfant_droit[nœud])
fonction parcourir_préfixe(nœud):
si nœud ≠ nil alors
2 3
afficher(valeur[nœud])
parcourir_préfixe(enfant_gauche[nœud])
parcourir_préfixe(enfant_droit[nœud])
4 5 6 7
parcourir_préfixe(enfant_droit[nœud])
fonction parcourir_préfixe(nœud):
si nœud ≠ nil alors
2 3
afficher(valeur[nœud])
parcourir_préfixe(enfant_gauche[nœud])
parcourir_préfixe(enfant_droit[nœud])
4 5 6 7
1 2 4
Cette fois, ce nœud est l’arbre vide. Le test nœud ̸= nil est donc faux ce qui implique que la
fonction s’arrête tout de suite, sans rien faire. On revient donc dans l’algorithme mis en pause
sur le nœud 4 : c’est comme si vous aviez le contrôle du direct sur plusieurs télévisions en
parallèle, dès qu’une émission se termine sur l’une, le programme se remet en route sur une
autre... La prochaine ligne de l’algorithme demande à exécuter l’algorithme sur le sous-arbre
droit, vide également :
7.4. AFFICHAGE D’UNE ARBORESCENCE DE FICHIERS : PARCOURS PRÉFIXE131
Parcours préfixe
fonction parcourir_préfixe(nœud):
si nœud ≠ nil alors
fonction parcourir_préfixe(nœud): afficher(valeur[nœud])
si nœud ≠ nil alors parcourir_préfixe(enfant_gauche[nœud])
afficher(valeur[nœud])
parcourir_préfixe(enfant_gauche[nœud])
1 parcourir_préfixe(enfant_droit[nœud])
parcourir_préfixe(enfant_droit[nœud])
fonction parcourir_préfixe(nœud):
si nœud ≠ nil alors
2 3
afficher(valeur[nœud])
parcourir_préfixe(enfant_gauche[nœud])
parcourir_préfixe(enfant_droit[nœud])
4 5 6 7
parcourir_préfixe(enfant_droit[nœud])
2 3
4 5 6 7
parcourir_préfixe(enfant_droit[nœud])
2 3
4 5 6 7
2 3
4 5 6 7
2 3
4 5 6 7
Parcours préfixe
du parcours d’arbre, on traite donc les nœuds la première fois qu’on les a visités, c’est-à-dire
sur les étoiles dans le diagramme suivant :
2 3
4 5 6 7
1 2 4 5 3 6 7
7.5 Expressions arithmétiques et parcours postfixe
Les arbres sont partout...
même dans vos calculatrices. Lorsque vous tapez un calcul, par
exemple (5 − 3) + 7 × 2, la calculatrice, elle, stocke un arbre binaire en mémoire. Pour cela,
elle essaie de décomposer le calcul en deux tant que c’est possible. Au début, elle trouve donc
l’opération la plus prioritaire, le produit, pour décomposer le calcul en le produit de (5−3)+7
et de 2. À nouveau, elle décompose le sous-calcul (5 − 3) + 7 comme la somme de 5 − 3 et de 7,
et ainsi de suite jusqu’à ce que les sous-calculs soient tous des constantes. On obtient donc la
((5 – 3) + 7) × 2
représentation par l’arbre ci-dessous, qu’on résume à droite en conservant dans chaque nœud
uniquement l’opération qui permet la décomposition :
((5 – 3) + 7) × 2 ×
(5 – 3) + 7 2 + 2
5–3 7 – 7
5 3 5 3
7.5. EXPRESSIONS ARITHMÉTIQUES ET PARCOURS POSTFIXE 133
Arbre pour (4 + 5) × (9 ÷ 3) ?
Exercice 45
Quelle est l’expression arithmétique dont l’arbre est le suivant ?
×
(4 + 5) × (9 ÷ 3)
4+5 9÷3 + ÷
4 5 9 3 4 5 9 3
Qu’est-ce qu’un calcul pour une calculatrice ? Considérons, pour simplifier la présentation,
une calculatrice très simple avec uniquement les opérations de somme, de soustraction, de
produit et de division. Ainsi, ce que reçoit la calculatrice de l’utilisateur est une expression
arithmétique qui est :
— soit un nombre n ;
— soit une somme (e1 + e2 ) ;
— soit une soustraction (e1 − e2 ) ;
— soit un produit (e1 × e2 ) ;
— soit une division (e1 ÷ e2 ) ;
avec, à chaque fois, e1 et e2 deux expressions arithmétiques. On retrouve ici une définition
par récurrence, où on utilise la notion d’expression arithmétique pour définir une expres-
sion arithmétique. C’est parce que cette définition est récursive qu’elle se prête bien à la
représentation par un arbre :
sans utiliser de propriétés sur les opérateurs arithmétiques, est le sous-calcul 5 − 3, qui vaut 2.
On peut donc remplacer dans le calcul originel et obtenir (2 + 7) × 2. À nouveau, on exécute
le sous-calcul le plus à l’intérieur, soit 2 + 7, dont on sait que cela vaut 9. On obtient alors
9 × 2 qui s’évalue en 18.
Il se trouve que ce calcul consistant à d’abord évaluer les sous-calculs les plus à l’intérieur
est à nouveau un parcours de l’arbre. On commence donc à la racine de l’arbre.
134
Évaluer ((5 – 3) + 7) ×CHAPITRE
2 7. ARBRES
+ 2
– 7
5 3
Mais contrairement au parcours préfixe, on affiche rien et on part directement dans l’enfant
gauche. Petit à petit, appel récursif après appel récursif, on atterrit donc la feuille 5 qui
s’évalue directement en 5 sans avoir besoin d’appels récursifs :
Évaluer ((5 – 3) + 7) × 2
×
+ 2
– 7
5 3
5
Évaluer ((5 – 3) + 7) × 2
×
+ 2
– 7
5 3
5
Comme pour le parcours préfixe, on passe ensuite à l’appel récursif sur l’enfant droit :
Évaluer ((5 – 3) + 7) × 2
7.5. EXPRESSIONS ARITHMÉTIQUES ET PARCOURS POSTFIXE 135
+ 2
– 7
5 3
5 3
puis on remonte une dernière fois vers le nœud − où on a désormais toutes les informations
Évaluer ((5 – 3) + 7) × 2
pour pouvoir évaluer l’opération 5 − 3 :
+ 2
– 7
2
5 3
5 3
On continue donc à remonter dans l’arbre, sur le nœud + où, à nouveau, on n’a pas encore
Évaluer ((5 – 3) + 7) × 2
tous les éléments pour effectuer le calcul :
+ 2
– 7
2
5 3
5 3
+ 2
– 7
2 7
5 3
5 3
Évaluer ((5 – 3) + 7) × 2
puis revenir pour évaluer le calcul 2 + 7 :
+ 2
9
– 7
2 7
5 3
5 3
Évaluer ((5 – 3) + 7) × 2
On repart à la racine de l’arbre, pour ensuite aller évaluer son enfant droit :
+ 2
9 2
– 7
2 7
5 3
5 3
18
×
+ 2
9 2
– 7
2 7
5 3
5 3
Voici l’opération qu’on a effectué, en admettant écrite une fonction testant si un nœud est
une feuille (c’est-à-dire si son enfant gauche et son enfant droit sont égaux à nil ) :
def é v aluer_ expres sion ( nœud ) :
if est_feuille ( nœud ) :
return valeur [ nœud ]
else :
m = é value r_expr ession ( enfant_gauche [ nœud ])
n = é value r_expr ession ( enfant_droit [ nœud ])
if valeur [ nœud ] == " + " :
return m + n
elif valeur [ nœud ] == " -" :
return m - n
elif valeur [ nœud ] == " * " :
return m * n
else : # dans ce cas valeur [ nœud ] = "/"
return m / n
Notons que les appels récursifs sont désormais exécutés avant de traiter plus longuement
le nœud (traitement qui consiste en l’occurrence à prendre le résultat de l’enfant gauche et
de l’enfant droit et d’exécuter le calcul élémentaire demandé).
Parcours postfixe
En matière d’affichage d’un arbre binaire, l’évaluation d’une expression arithmétique
consiste en le parcours suivant :
2 3
4 5 6 7
dans lequel on affiche chaque nœud lors du dernier passage par celui-ci, après le traitement
de ses enfants gauche4 et droit.
5 2
En opposition 6 au parcours
7 3
préfixe 1
précédent, on appelle ce
parcours le parcours postfixe. On peut l’écrire de la manière suivante à l’aide d’un algorithme
récursif :
138 CHAPITRE 7. ARBRES
Parcours infixe
traitement de l’enfant gauche et celui de l’enfant droit : on appelle cela le parcours infixe. Il
peut se visualiser ainsi
2 3
4 5 6 7
Exercice 46
1. Exécuter l’algorithme affichage d’une expression
sur l’arbre correspondant à
l’expression arithmétique (5 + 3) × (7 + 2) en vous assurant que vous retrouvez
bien l’expression attendue.
2. Écrire l’algorithme récursif permettant d’afficher une expression arithmétique
stockée sous la forme d’un arbre binaire.
Exercice 47
1. Appliquer les trois algorithmes de parcours depuis la racine des arbres binaires
suivants, en montrant les valeurs affichées.
A
A A
B
B C B C
C
D E D E
D
Albert
Camille
Dany
Jenny
Karim
Younis
Ajout de
Basile est un nouvel abonné qu’il nous faut ajouter Basile
dans dans l’annuaire
l’annuaire. On peut utiliser la re-
Basile
Dany
Jenny
Karim
Younis
00129876 00451092
00982730 00238684 00109283 00137492 00347591
Albert
Basile
Camille
Dany
Jenny
Karim
Younis
l’annuaire : c’est donc très coûteux ! Pour un bottin, cela veut dire qu’il faut refaire toute la
les noms
mise en page des pages qui suivent celle où on l’a ajouté.les
Même
nomspour un tableau stocké dans
la mémoire d’un ordinateur, avant
celaDany
demande de après
déplacer
Dany
Dany
d’une case vers la droite le contenu
de toutes les cases de la dernière jusqu’à 00238684
la case qu’on doit libérer pour insérer Basile : cet
Albert
insérer un
00129876 00982730 00451092 00238684 00109283 00137492 00347591
nouvel abonné en tête duBasile
tableau). Karim
00982730 00137492
À la place, nous allons proposer une nouvelle structure de données pour stocker un an-
nuaire (ou un dictionnaire) dont l’insertion d’un nouvel élément sera, comme la recherche, de
complexité O(log n). Il s’agit d’un
Albert
arbre binaire :
Camille
Jenny
Younis
Basile
Karim
00982730 00137492
Albert
Camille
Jenny
Younis
Plus précisément, c’est un arbre binaire de recherche (ABR). Il s’agit d’un arbre tel que
chaque nœud x de l’arbre vérifie la propriété suivante : toutes les valeurs des nœuds dans
l’enfant gauche de x sont inférieures à la valeur de x, et toutes les valeurs des nœuds dans
l’enfant droit de x sont supérieures à la valeur de x. Sur l’exemple précédent, tous les noms
avant Dany dans l’annuaire sont à gauche de la racine, et tous les noms après Dany dans
l’annuaire sont à sa droite. Mais aussi, parmi tous les noms à gauche de Dany, ceux avant
Basile sont à sa gauche et ceux après Basile sont à sa droite. Voici un autre ABR où les nœuds
sont des entiers :
Arbres binaires
La valeur de chaque nœud est :
- supérieure à la valeur de tous les
7.7.
de recherche
ARBRES BINAIRES DE RECHERCHE
nœuds de son enfant gauche
- inférieure à la valeur de tous les
141
nœuds de son enfant droit
2 6
1 3 5 7
4 5 5
1 7 3 8 4 6
5 8 4 6 2 7
Comment rechercher une valeur dans un ABR, comme par exemple un nom dans l’an-
nuaire ? On peut utiliser un algorithme récursif qui descend dans l’arbre en partant de la
racine et en continuant à gauche ou à droite à l’aide d’une comparaison entre la valeur à cher-
cher et le nœud courant. Notez la proximité entre cet algorithme et la recherche dichotomique
qui décidait aussi de continuer dans la moitié gauche ou droite du tableau restant, à l’aide
d’une comparaison entre la valeur cherchée et le milieu du tableau : c’est la racine de l’ABR
qui joue le rôle du milieu du tableau.
def est_pr é sent_abr ( nœud , x ) :
if nœud == nil :
return False
elif x == valeur [ nœud ]:
return True
elif x < valeur [ nœud ]:
return est_pr é sent_abr ( enfant_gauche [ nœud ] , x )
else :
retourner est_pr é sent_abr ( enfant_droit [ nœud ] , x )
Dans l’ABR précédemment donné en exemple, la recherche de la valeur 3 se déroule comme
suit :
— à la racine, on compare 3 et 4 : puisque 3 < 4, on continue la recherche dans l’enfant
gauche, le nœud 2 ;
— puisque 2 < 3, on continue la recherche dans l’enfant droit ;
— c’est le nœud 3 et la recherche s’arrête donc avec succès.
Si on recherche la valeur 8, voici l’exécution :
— à la racine, on a 4 < 8, donc on continue la recherche dans l’enfant droit, le nœud 6 ;
— puisque 6 < 8, on continue à nouveau la recherche à droite, dans le nœud 7 ;
— à nouveau 7 < 8, on continue donc la recherche à droite ;
142 CHAPITRE 7. ARBRES
— c’est désormais l’arbre vide nil : nous n’avons pas trouvé la valeur 8 dans l’arbre et
on peut s’arrêter sur cet échec.
Exercice 49
Appliquer l’algorithme de recherche pour tester la présence des valeurs 15, 7, 2,
11, 3 dans l’ABR suivant, en donnant la liste des nœuds où l’algorithme s’appelle
récursivement.
5 12
1 7 10 15
2 9 13 17
Quelle est la complexité de cet algorithme ? À chaque appel récursif, on plonge dans
l’enfant gauche ou l’enfant droit, donc on descend d’un niveau à chaque appel. Ainsi, les
appels récursifs suivent une branche (un chemin de la racine à l’une des feuilles de l’arbre)
de l’arbre et la complexité est donc proportionnelle à la longueur maximale d’une de ses
Temps de recherche
branches. Par analogie avec nos dessins, on appelle hauteur cette longueur maximale d’une
branche de l’arbre. Par exemple, l’ABR suivant a hauteur 2, de sorte qu’un arbre réduit à sa
racine aura hauteur 0 par convention :
hauteur
Comment la hauteur d’un ABR se compare-t-elle au nombre n de nœuds que l’arbre contient ?
Malheureusement pas toujours très bien : la hauteur peut être de l’ordre de n dans le pire
des cas. Mais si l’ABR est équilibré (comme c’est le cas au-dessus), c’est-à-dire qu’on essaie
de conserver autant de nœuds dans l’enfant gauche et l’enfant droit de n’importe quel nœud
de l’arbre, alors la hauteur devient proportionnelle à log2 n. Dans ce cas, la complexité de
l’algorithme de recherche dans un ABR a complexité O(log n), comme pour la recherche
dichotomique.
Attelons-nous finalement au problème initial : l’ajout de nouveaux abonnés dans l’an-
nuaire ! Cela correspond à l’insertion d’une nouvelle valeur dans un ABR. En fait, nous n’avons
pas beaucoup à faire, le principal étant de savoir chercher la position où devrait se trouver
l’élément à insérer. De deux choses l’une :
— soit on trouve l’élément à insérer : dans ce cas, on renvoie une erreur puisqu’on ne
souhaite pas avoir deux occurrences de la même valeur dans l’ABR ;
7.7. ARBRES BINAIRES DE RECHERCHE 143
— soit on ne le trouve pas, ce qui veut dire que l’algorithme de recherche s’est retrouvé
en-dessous d’une feuille, dans un arbre vide nil (comme lorsqu’on a recherché 8 dans
l’ABR précédemment) : il ne reste plus alors qu’à remplacer cet arbre vide par une
nouvelle feuille avec la valeur à insérer. On obtient bien un nouvel ABR avec tous les
nœuds de l’ABR initial auquel s’ajoute la valeur à insérer.
L’algorithme se résumant finalement à une recherche dans l’ABR, sa complexité est du même
ordre que la complexité de la recherche : O(n) dans le pire des cas, et O(log n) dans le cas
d’un ABR équilibré.
Exercice 50
1. Construire un ABR en insérant une par une (à partir de l’arbre vide) les valeurs
9, 5, 12, 2, 15, 7, 11 dans l’ordre. Ensuite, construire un autre ABR en insérant
les mêmes valeurs, mais dans l’ordre 2, 5, 7, 9, 11, 12, 15. Quelle est la hauteur
des deux arbres et quelle différence y aura-t-il du point de vue de la complexité
lors d’une recherche dans le pire des cas ?
2. Appliquer l’algorithme de parcours infixe aux arbres binaires construits dans la
question précédente. Dans quel ordre l’algorithme affiche-t-il les valeurs ?
3. En déduire un algorithme de tri de tableau (qu’on pourra décrire avec des
phrases) qui utilise un ABR comme structure de données auxiliaire.
144 CHAPITRE 7. ARBRES
Chapitre 8
Calculabilité
Nous avons vu dans le dernier chapitre de nombreuses applications des arbres, ces graphes
particuliers qui ne possèdent pas de cycles. Dans ce chapitre, nous allons étudier des arbres
(puis des graphes) particuliers servant de modèle de calcul. Jusqu’à maintenant, nous avons
surtout étudié des algorithmes et des structures de données permettant de résoudre des
problèmes concrets. Mais, dans l’introduction, nous avons évoqué le problème de savoir si
un problème possède une solution : nous avons vu le problème géométrique de la quadrature
du cercle qui s’est avéré ne pas avoir de solution. Existe-t-il de telles impossibilités en infor-
matique également, c’est-à-dire des problèmes tels qu’aucun calcul, aucun algorithme n’est
capable de le résoudre ? Pour pouvoir répondre à cette question, il nous est nécessaire de
préciser ce que nous entendons par impossible, et donc ce qui est possible également, à savoir
calculable. Ce chapitre évoque dans un premier temps une notion assez faible de calculabilité,
les arbres de décision, que nous enrichirons ensuite avec les automates, puis finalement avec
les machines de Turing.
à l’abdomen
non
à la gorge
oui
non oui non
oui non
Grippe Angine
145
146 Qui est-ce ?CHAPITRE 8. CALCULABILITÉ
un médecin qui doit diagnostiquer un patient entrant dans son cabinet. Comment procède-
t-il ? Une façon de faire est de commencer par poser une première question, par exemple
≪ Avez-vous des douleurs ? ≫ : suivant la réponse, le médecin apprend de l’information et il
peut continuer à poser des questions, jusqu’à avoir appris suffisamment d’informations pour
prendre une décision, c’est-à-dire déclarer si le patient est malade et si oui, quelle maladie il
a probablement. Les différents états de connaissance du médecin au cours du diagnostic sont
reliés par des arcs selon les réponses aux questions qu’il pose : cela forme un arbre (en effet, un
cycle dans ce diagramme de diagnostic n’aurait pas beaucoup de sens puisque cela voudrait
dire que le médecin pose deux fois la même question), qu’on appelle arbre de décision. Un
exemple très simplifié de tel arbre de décision est représenté en Figure 8.1.
Lorsque nous jouons au jeu du Qui est-ce ? (cf Figure 8.2), nous procédons par élimination
successive de personnages en posant à l’autre joueur des questions auxquelles il répond par
oui ou non. On peut à nouveau représenter une stratégie de l’un des joueurs à l’aide d’un arbre
de décision : chaque nœud de l’arbre est à nouveau une question qu’il pose à son adversaire et
selon la réponse apportée (oui ou non), on continue dans le sous-arbre gauche ou le sous-arbre
droit. Le début d’un arbre de décision possible pour ce jeu est représenté en Figure 8.3 : les
feuilles de cet arbre sont les situations où un seul visage reste possible auquel cas le joueur a
deviné (sauf erreur ou tricherie de l’adversaire...) le personnage choisi par l’adversaire.
Un dernier exemple d’arbre de décision que nous utilisons tous les jours sans le savoir
consiste en la détection de spams dans les applications d’emails. Par exemple, considérons les
deux emails suivants :
Salut Benoı̂t,
Bravo, Demain je joue contre Bruno. Si je gagne
Vous venez de gagner à notre grand ti- la partie, je me qualifie directement. Si je
rage internet. Cliquez ici pour recevoir ne gagne pas demain mais que je gagne la
1.000.000 de dollars ! ! ! Et pour gagner suivante, je monte en pool 3 l’année pro-
d’autres cadeaux, cliquez ici. chaine !
Bises, Sandra
Comment détecter si ce sont des spams ou des messages réguliers qu’il ne faut pas filtrer ? La
méthode la plus simple, très efficace, consiste à utiliser des arbres de décision. Les questions
sont des critères qu’on peut vérifier sur chaque email, par exemple la comparaison du nombre
d’occurrences d’un mot (ou sa fréquence d’apparition dans l’email) avec une constante. Un
tel arbre de décision simplifié est donné en Figure 8.4.
8.1. ARBRES DE DÉCISION 147
Ton personnage
est-il un homme ?
oui non
A-t-elle un
Est-il blond ?
chapeau ?
…
Joe Charles Tom Robert Maria Claire Anne Susan
Figure 8.3 – Un extrait de l’arbre de décision pour représenter une stratégie au Qui est-ce ?
Détection de spams
Message 1
Bravo,
# Gagner > 2 ?
Vous venez de gagner à notre
grand tirage internet.
Message 2
Salut Benoît,
# Partie > 0 ? # Cliquer > 1 ?
Demain je joue contre Bruno.
Si je gagne la partie, je me
qualifie directement. Si je ne
oui non oui non
gagne pas demain mais que
je gagne la suivante, je monte
en pool 3 l’année prochaine !
Régulier Spam Spam Régulier
Bises, Sandra
Pour le message de gauche, le nombre de fois que le mot ≪ gagner ≫ apparaı̂t est inférieur
ou égal à 2, mais le mot ≪ cliquer ≫ (sous une forme conjuguée) apparaı̂t strictement plus
d’une fois : l’arbre de décision conclut donc que c’est un spam (la troisième feuille en partant
de la gauche). Pour le second message en revanche, le mot ≪ gagner ≫ apparaı̂t strictement
plus de deux fois, mais le mot ≪ partie ≫ apparaı̂t aussi, donc l’arbre de décision permet
de détecter qu’il s’agit probablement d’un email régulier. En pratique, les arbres de décision
utilisées pour détecter les spams sont bien plus grands et ils sont mis au point à l’aide de
méthodes d’apprentissage automatique, à partir d’une grande quantité d’emails qui sont déjà
classifiés comme étant réguliers ou spams : on parle d’apprentissage supervisé.
un arbre de décision ?
calcul qui prend en entrée des réponses (oui ou non) aux questions qu’il pose, et les utilise
afin de produire une sortie, la décision attendue (régulier/spam, malade/pas malade, le nom
du personnage du Qui est-ce ? ) :
Entrées
Arbre de Sorties
décision
réponses
décision
aux questions
Régulier Spam
oui oui non …
Rien Maladie
Si on s’abstrait un peu des exemples, on peut considérer qu’on prend en entrée une
Un peu d’abstraction pour y voir plus clair…
séquence de réponses prises dans un ensemble fini de réponses possibles, et qu’on prend une
Automate
décision ≪ OK ≫ ou ≪ pas OK ≫, suite à la séquence de réponses observée. Cette étape de
généralisation de ce que peut prendre un arbre de décision en entrée nous invite à changer
de nom : désormais, nous appellerons un tel processus prenant des séquences en entrée et
renvoyant ≪ OK ≫/≪ pas OK ≫ en sortie un automate :
séquence décision
bonjour_!_ça_va_?
00110101001010
« OK » ou « pas OK »
•• –• ••–• –––
oui non oui oui
En entrée, Un automate
on peut décritque
donc imaginer unl’automate
ensemble dedes
prend séquences « valides »,
caractères pour lire des séquences
de caractères (du texte, celles
donc), ou bienlaquelle
pour des séquences de 0 « OK »
il décide et de 1 (pour représenter des
entiers en binaire par exemple), ou bien encore des points et des traits, éléments de base
8.1. ARBRES DE DÉCISION 149
du code Morse. Les arbres de décision sont donc des automates particuliers, qui lisent des
séquences de ≪ oui ≫/≪ non ≫. Dans le cas général, les sommets de l’arbre de décision portent
le nom d’états dans les automates : l’état d’où l’on part au début du processus (la racine de
l’arbre de décision) est appelé état initial. Les éléments qu’on lit (des caractères, des 0/1, des
oui/non...) sont appelés des lettres et les arcs d’un état à l’autre, étiquetés par une lettre,
sont appelés des transitions. Certains états sont les états où l’automate prend une décision :
certains sont acceptants (ceux où on déclare la séquence de lettres lues comme étant ≪ OK ≫)
et les autres sont non acceptants.
Voici un premier exemple d’automate sur l’alphabet {a, b, c, d} :
0
a b
1 2
c a d c
3 4 5 6
Cet automate possède sept états numérotés de 0 à 6. L’état 0 est l’état initial. Seuls les états 3
et 6 sont acceptants (parmi les feuilles {3, 4, 5, 6}) : on les représente par un double cercle.
Un automate décrit un ensemble de séquences ≪ valides ≫, c’est-à-dire celles pour laquelle il
décide ≪ OK ≫. Pour l’exemple ci-dessus, seules deux séquences de lettres permettent d’aller
de l’état initial à un état acceptant : la séquence ac et la séquence bc. Les séquences aa et bd
parviennent à des feuilles mais ne sont tout de même pas acceptées par l’automate. On dit
que le langage reconnu par l’automate est {ac,bc}. Notez que la séquence a n’est pas reconnue
par l’automate, mais on peut l’étendre de façon à atteindre un état acceptant. En revanche,
non seulement aa n’est pas reconnue, mais aucune suite possible ne mène à un état acceptant.
C’est la même chose que pour la séquence c ou d : elles ne sont pas acceptées et aucune suite
possible ne permet d’atteindre un état acceptant. C’est la raison pour laquelle on ne les a
même pas représentées sur le dessin. De même, on peut donc ignorer les transitions menant
de 1 à 4 et de 2 à 5. L’automate ci-dessous est donc équivalent au précédent, au sens où il
accepte le même langage :
0
a b
1 2
c c
3 6
Maintenant qu’on a supprimé des états inutiles, il apparait qu’on peut encore simplifier
cet automate. En effet, on peut essayer de partager des états, quitte à ne plus insister sur
le fait que l’arbre de décision soit un arbre. Par exemple, il ne rime à rien de distinguer les
150 CHAPITRE 8. CALCULABILITÉ
états 3 et 6 qui sont tous deux acceptants mais ne permettent pas de continuer à lire des
lettres. On peut donc les fusionner sans crainte :
0
a b
1 2
c c
3
Mais alors, on s’aperçoit qu’il est aussi inutile de distinguer les états 1 et 2 qui sont tous
deux non acceptants, mais permettent de lire uniquement la lettre c en se rendant dans le
même état 3 : ils réagissent de la même manière dans le futur, donc on peut sans crainte les
fusionner également. On obtient donc l’automate suivant :
a b
Cela n’a plus rien d’un arbre, mais on appelle toujours cela un automate. Voyons donc une
définition formelle de ces automates finis (car on se concentre sur les automates qui possèdent
un ensemble fini d’états).
A
0 1
B C
1 0 1
D 1 E
1
0
F
Ses états sont A, B, C, D, E et F . L’état initial est A, distingué par une flèche entrante.
Les états acceptants sont E et F distingués par un double cercle. Cet automate possède 8
transitions : par exemple, il y en a une de l’état A vers l’état B étiquetée par la lettre 0, et
une autre de l’état E à l’état F étiquetée par la lettre 1.
Notons que tous les automates vus jusqu’alors vérifient la propriété suivante :
≪ Pour tout état e de l’automate et pour toute lettre ℓ de l’alphabet, il
existe au plus une transition sortant de l’état e étiquetée par la lettre ℓ. ≫
On dit que l’automate est déterministe en cela qu’à tout moment il n’y a aucun choix pour
continuer la lecture d’une séquence de lettres fixée à l’avance : soit on bloque car il n’y a
pas de transition étiquetée par la lettre voulue (par exemple, si on veut lire deux lettres 0
dans l’automate du dessus, on bloque en B qui ne peut pas lire une lettre 0 en suivant une
transition), soit on suit l’unique transition étiquetée par la lettre voulue. Dans ce cours, on
considèrera uniquement des automates déterministes.
Un automate accepte un langage, qui est un ensemble de séquences. Une séquence s est
acceptée par l’automate s’il existe un chemin (et s’il existe, il est unique) de l’état initial
à un état acceptant dont la séquence des étiquettes des transitions visitées (dans l’ordre)
est s. Ainsi, la séquence 011 est acceptée par l’automate A ci-dessus, mais pas la séquence
01 qui ne termine pas dans un état acceptant, ni la séquence 110 pour laquelle il n’y a pas
de chemin avec cette étiquette (on bloque en E lorsqu’il s’agit de lire la lettre 0). L’ensemble
des séquences acceptées par l’automate A est {010, 011, 10, 11, 101, 111} : ce sont l’ensemble
des codages binaires sur moins de 3 bits représentant des entiers premiers (2, 3, 5, 7).
Jusque-là, nous n’avons vu que des automates qui acceptent un langage fini de séquences.
Comment peut-on accepter un langage infini ? 1 Prenons un exemple : peut-on trouver un
automate acceptant toutes les séquences sur l’alphabet {a, b} qui ne contiennent que des a
sauf la dernière lettre qui doit être un b, c’est-à-dire le langage {b, ab, aab, aaab, aaaab, . . .}.
Clairement, ce langage contient un ensemble infini de séquences. Notre première tentative
1. Attention, c’est bien le langage dont on veut qu’il contienne un ensemble infini de séquences, pas les
séquences elles-même qui sont toujours finies dans ce cours.
152 CHAPITRE 8. CALCULABILITÉ
pourrait être de dessiner un arbre de décision : depuis l’état initial, soit on lit un b et on
accepte directement, soit on lit un a et on va dans un nouvel état qui, à nouveau soit lit un b
et accepte directement, soit lit un a et poursuit une étape de plus, etc.
b a
b a
b a
..
.
Malheureusement, cet automate n’est pas fini : il possède un nombre infini d’états. Plus
précisément, il a un état acceptant par séquence à accepter... Comme précédemment ce-
pendant, on se rend compte que tous les états acceptants peuvent être aisément fusionnés
puisqu’ils sont tous acceptants et ne permettent de lire aucune lettre supplémentaire. Une
fois qu’on a fait cela, on peut se rendre compte que tous les états non acceptants sont alors
≪ similaires ≫ : il permettent tous de partir vers l’unique état acceptant en lisant un b, ou
continuer vers eux en lisant un a. On peut donc tous les fusionner et on obtient finalement
l’automate fini (car il possède un nombre fini d’états) suivant :
Dans les dessins, il n’est pas toujours nécessaire de donner des noms aux états, comme dans
l’exemple de l’automate B. Mais on peut évidemment donner des noms si on le souhaite, pour
aider à comprendre la signification de l’état : ici, l’état de gauche de B pourrait s’appeler
≪ que des a ≫ et l’état de droite ≪ b à la fin ≫, ou simplement ≪ A ≫ et ≪ B ≫ si on veut des
On lit n’importe quelle séquence de 0 et de 1 en restant dans l’état de gauche, avant de passer
dans l’état de droite en lisant un 0. Malheureusement, cet automate n’est pas déterministe :
dans l’état de gauche, en lisant un 0, l’automate a le choix entre rester dans l’état de gauche,
ou passer dans l’état de droite. On ne s’autorise pas de tels automates à choix dans ce cours.
Il nous faut donc modifier notre premier essai. En fait, notons qu’une fois qu’on vient de lire
un 0, on doit nécessairement se trouver dans un état acceptant puisqu’il se pourrait que ce 0
soit le dernier bit du codage binaire. Par contre, lorsqu’on vient de lire un 1, on doit se trouver
dans un état non acceptant. Cela nous amène directement à cette seconde tentative :
1 0
1
Cet automate est déterministe et il accepte bien toutes les séquences de bits qui terminent
par un 0, c’est-à-dire les codages binaires des entiers pairs.
Exercice 51
Pour chacun des trois automates A1 , A2 , A3 ci-dessous, décrire l’alphabet ainsi que
le langage de toutes les séquences acceptées : lorsque le langage est infini, on peut le
décrire avec une phrase à défaut de pouvoir énumérer toutes les séquences.
A3
0 x x
0 y
b a
A1 0 1 2 A2
2 b a
1 y
2
Exercice 52
Dessiner un automate qui accepte l’ensemble des séquences sur l’alphabet {0, 1}
possédant un nombre de 1 multiple de 3 : à titre d’exemple, la séquence 0011010 doit
être acceptée, mais pas la séquence 1101011.
Exercice 53
On se place, dans cet exercice, sur l’alphabet {0, 1}.
1. Dessiner un arbre de décision qui accepte l’ensemble des séquences de longueur
au plus 4 qui possède autant de 0 que de 1 (dans n’importe quel ordre).
2. Simplifier l’arbre de décision précédent pour obtenir un automate avec un
154 CHAPITRE 8. CALCULABILITÉ
Exercice 54
L’alphabet Morse donne un code pour les 26 lettres de l’alphabet composé d’impulsions
courtes ( ) et longues ( ) :
A B C D E F
G H I J K L
M N O P Q R
S T U V W X
Y Z
Trouver un automate, ayant le plus petit nombre d’états possibles, qui accepte exacte-
ment l’ensemble des codes Morse.
• Thé à 50 centimes €
8.3.
• On peut
APPLICATIONS DESinsérer
AUTOMATES FINIS€ maximum dans la machine
50 centimes 155
• On peut annuler à tout moment (et récupérer la monnaie)
Cancel
Cancel
Cancel
Cancel
Cancel
début en vert pour signifier qu’il pourrait être considéré comme état acceptant de l’automate,
c’est-à-dire un état où l’on peut sans souci éteindre le distributeur sans léser un consommateur
qui a déjà inséré de l’argent dedans.
Exercice 55
L’objectif de l’exercice est de modéliser le comportement des portes automatiques de
bus par le biais d’un automate. On peut demander à ouvrir la porte grâce à un bou-
ton. La porte est aussi équipée d’un capteur de proximité qui permet d’empêcher la
fermeture de la porte si une personne est proche. Le principe est que la porte ne doit
pas s’ouvrir si un individu passe simplement devant mais s’il l’indique explicitement en
appuyant sur le bouton. Le bouton est soit dans l’état relâché si personne ne le touche,
soit dans l’état appuyé si quelqu’un est en train d’appuyer sur le bouton. Le système
possède 4 états possibles :
— Etat 0 : personne n’est à proximité de la porte. La porte est fermée.
— Etat 1 : un individu est à proximité de la porte (le capteur de proximité le
détecte) et la porte est fermée.
— Etat 2 : un individu a appuyé sur le bouton. La porte est ouverte et le capteur
de proximité détecte la personne.
— Etat 3 : un individu est à proximité de la porte (le capteur de proximité le
détecte), il n’a pas la main sur le bouton mais la porte est ouverte. Ce cas
survient si l’individu appuyait auparavant sur le bouton.
Les événements qui permettent la transition entre états sont :
— présence : le capteur de proximité détecte un individu à proximité mais celui-ci
ne touche encore pas le bouton.
156 CHAPITRE 8. CALCULABILITÉ
Une autre application possible des automates concerne la recherche de motif dans un texte.
Par exemple, dans un navigateur web ou dans un traitement de texte, vous avez toujours la
possibilité de rechercher un mot dans le document. Cette tâche est exécutée très efficacement
par un automate (à tel point que c’est souvent à l’aide d’automates que les algorithmes de
recherche sont effectivement décrits en pratique). Trouver un mot dans un texte, cela revient
à décrire un automate qui accepte la partie initiale du texte qui termine par le mot recherché.
Typiquement, considérons le texte :
Du journal ≪ Le petit bachelier ≫ : comme les professeurs
se plaisent à le rabâcher, le baccalaureat est important... !
Si on recherche le mot ≪ bac ≫ dans ce texte, en ignorant les majuscules et les accents, on
trouve trois occurrences :
Du journal ≪ Le petit bachelier ≫ : comme les professeurs
se plaisent à le rabâcher, le baccalaureat est important... !
Un automate à qui l’on donnerait ce texte devrait donc accepter les trois préfixes suivant du
texte, tous ceux qui finissent par le motif ≪ bac ≫ :
— Du journal ≪ Le petit bac
— Du journal ≪ Le petit bachelier ≫ : comme les professeurs se plaisent à le rabâc
— Du journal ≪ Le petit bachelier ≫ : comme les professeurs se plaisent à le rabâcher, le
bac
Repérer une occurrence du motif revient donc à accepter dans l’automate le préfixe du texte
qui termine sur cette occurrence.
Considérons toujours la recherche du motif ≪ bac ≫ mais dans des textes sur l’alphabet
simplifié {a,b,c}, pour éviter d’obtenir un automate difficile à représenter visuellement. Dans
ce cas, les mots aabbbac et aabacbbac doivent être acceptés, mais pas les mots aabacbba (même
s’il contient bac puisqu’il ne termine pas par bac), acababbaa ou babc. L’automate doit accepter
le mot bac lui-même donc il est raisonnable de commencer par créer quatre états permettant
de lire successivement les lettres b, a puis c. Le premier état doit être initial, et le dernier
acceptant. Il faut ensuite compléter les autres transitions de l’automate en maintenant sa
correction. Par exemple, dans l’état initial, il faut pouvoir également lire les lettres a et c :
celles-ci ne font pas avancer dans la reconnaissance d’une occurrence du motif, donc, en les
lisant, on boucle sur l’état initial. De même, si on lit un c dans le second état, on remet à
8.4. LANGAGE NON ACCEPTÉ PAR UN AUTOMATE FINI 157
zéro notre avancée dans la recherche du motif bac, donc on retourne dans l’état initial. En
revanche, si on lit un b dans le second état, on doit rester dans cet état, puisqu’on continue
à voir la première lettre du motif bac. En continuant de compléter les transitions jusqu’au
dernier état, on obtient l’automate suivant :
a b b
c b
ε b ba c bac
b a
a
c
c
Exercice 56
On se place, dans cet exercice, sur l’alphabet {a,b,c}.
1. Dessiner un automate qui accepte l’ensemble des séquences qui se terminent par
cca : ainsi, le mot bacbcca doit être accepté, mais pas le mot bccba, ni le mot
bccab.
2. Dessiner un automate qui accepte l’ensemble des séquences qui se terminent par
abba : attention, le mot abbabba doit être accepté !
Théorème 5. Le langage L des mots sur l’alphabet {0, 1} qui possèdent autant de 0 que de 1
ne peut pas être accepté par un automate fini. C’est aussi le cas du langage {0n 1n | n ∈ N\{0}}.
Figure 8.6 – À gauche : image illustrant le concept de machine de Turing. À droite : Alan
Turing (1912-1954).
Exercice 57
Écrire un algorithme en Python, qui prend en entrée un tableau contenant des lettres
0 et 1, et renvoie True si ce tableau contient autant de 0 que de 1, et False sinon.
Le modèle d’automates finis, aussi intéressant et puissant soit-il, ne peut donc pas représenter
ce qui est calculable, puisqu’un algorithme très simple reconnaı̂t un langage qu’un automate
ne peut pas accepter. Enrichissons donc ce modèle d’automates finis pour parer à ce problème.
A A A B A B B A B B
1 1 0 1 0 0 1 0 0
1 0
1
A B
0
8.5. DES AUTOMATES VERS LES MACHINES 159
Des automates…
Des automates…
L’état A est l’état initial donc on place le ruban sur la tête de lecture dans l’état A :
A A A B A B B A B B
A A A B A B 1 B1 0A1 B
0 0B1 0 0
OK
1 qu’elle
1 À partir
0 1 1.0L’automate
0 1 nous0dit 0
de là, la machine doit savoir ce qu’elle doit faire lorsqu’elle est dans l’état A et
lit la lettre 1 qu’elle doit rester dans l’état A, et elle continue en
0
lisant la lettre suivante du ruban.
1 On peut représenter les quatre transitions possibles de la
manière suivante : A B
Des automates…
Ainsi, on arrive dans la situation suivante après une étape :
A A A B A B B A B B
1 1 0 1 0 0 1 0 0
Des automates…
On continue ainsi, via les étapes suivantes :
Etat Symbole Nouvel état
1 0
A 1 A
A 1A A B A B B A B B
A B
Des automates…
1 01 0 1 0 0 1 0 0
A A A B A B BEtat A B B
Symbole Nouvel état
1 0
A 1 A
A
Des automates…
1 11 0 1 0 0 1 0 0
B
A A A B A B BEtat A B B
Symbole Nouvel état
1 0
A 1 A
1 1 1 0 1 0 0 1A 0 0 0 B
A B
A A A B A B B A B B
Des
1 1 automates…
0 1 0 0 1 0 0
A A A B A B BEtat A B B
Symbole Nouvel état
1 0
A 1 A
A
Des
1 1 automates…
1
0 1 0 0 1 0 0
B
A 0 B
B 1 A
0
A A A B A B BEtat A B B
Symbole Nouvel état
1 0
A 1 A
A
Des
1 1 automates…
1
0 1 0 0 1 0 0
B
A 0 B
B 1 A
0
B 0 B
A A A B A B BEtat A B B
Symbole Nouvel état
1 0
A 1 A
1 1 1 0 1 0 0 1A 0 0 0 B
A B
Des automates…
B 1 A
0
B 0 B
La prochaine étape sort du ruban de lecture : Etat Symbole Nouvel état
1 0
A 1 A
A A A B A B BA A B 0 B
1
OK B
A B
B 1 A
1 01 0 1 0 0 1 0 0
B 0 B
Il n’y a plus rien à lire et on est dans l’état B quiEtatest acceptant : la machine accepte et on
Symbole Nouvel état
déclare la séquence 110100100 comme acceptée par la machine.
Des automates…
1 0
A 1 A
Si on reprend l’exécution de1 la machine au début, avec la séquence 1101001 sur le ruban,
A 0 B
on arrive à la situation
A suivante : B
B 1 A
0
A A A B A B B
B A pas
0 OK B
1 1 0 1 0 0 1
Si état = A et on lit 1 alors
état := A
Il n’y a plus rien à lire et on est dans l’état A non acceptant : la machine rejette donc et on
se déplacer à droite
Sinon Si état = A et on lit 0 alors Etat Symbole Nouvel état
déclare la séquence 1101001 comme rejetée par la machine.
état 1
:= B 0
A
Ajoutons donc désormais des caractéristiques supplémentaires
se déplacer à droite 1 à cesAmachines très simples,
1 lit 1 alors
Sinon Si état = B et on
en commençant par la possibilité de changer de sens de
état := A A lecture.
0 Désormais,
B lorsque la machine
se A
déplacer à droite B
lit une lettre dans un certain état, elle peut soit continuer
Sinon Si état = B et on lit 0 alors B
en1allant lireA
la lettre à droite sur
état := B 0
le ruban, soit aller lire la lettre à gauche sur le ruban. On représentera ce sens par une flèche
se déplacer à droite B 0 B
dans les tables de transition.
Sinon s’arrêter !
FinSi
Exécutons par exemple la machine dont un extrait de la table est
… qui peuvent changer de sens …
Bc OK Bc Bc BcBc Bc B A
a d x d b x c
8.5. DES AUTOMATES VERS LES MACHINES 161
Accepte si le
A a,b,c,…,z
→ A
dernier symbole de
A
← B
la séquence est
B a
← Ba
autres symboles B c
← Bc
… … … …
B z
← Bz
Bc a,b,d,…,z
← Bc
Bc
→ OK
Elle utilise comme alphabet l’ensemble des caractères latins minuscules {a,b,c, . . . ,z} ainsi
qu’un caractère blanc. Elle a pour états {A, B, Ba, Bb, Bc, . . . , Bz, OK}. La première ligne
signifie que lorsque la machine est dans l’état A, si elle lit une lettre différente du blanc, elle
continue sur la case de droite sur le ruban, toujours dans l’état A. Si on lance la machine avec
… qui peuvent changer de sens …
la séquence adxdbxc sur le ruban, on passe donc par les configurations suivantes :
Bc A A A A A A A A
a d x d b x c
… qui peuvent changer de sens …
Bc A A A A A A A A
a d x d b x c
… qui peuvent changer de sens …
Etat Symbole Sens Nouvel état
Bc A A A A A A A A →
A a,b,c,…,z A
a d x d b x c
… qui peuvent changer de sens …
Etat Symbole Sens Nouvel état
Bc A A A A A A A A →
A a,b,c,…,z A
a d x d b x c
… qui peuvent changer de sens …
Etat Symbole Sens Nouvel état
Bc A A A A A A A A →
A a,b,c,…,z A
a d x d b x c
Etat Symbole Sens Nouvel état
A a,b,c,…,z
→ A
162 CHAPITRE 8. CALCULABILITÉ
… qui peuvent changer de sens …
Bc A A A A A A A A
a d x d b x c
… qui peuvent changer de sens …
Etat Symbole Sens Nouvel état
Bc A A A AA A a,b,c,…,z
A A A→ A
a d x d b x c
Etat Symbole Sens Nouvel état
À ce point, la tête de lecture va vouloir aller Aà droite, mais le ruban semble s’arrêter. Pour
a,b,c,…,z
→ A
éviter qu’une telle situation ne se produise, on étend le ruban à droite en le remplissant de
… qui peuvent changer de sens …
cases blanches. La prochaine configuration est donc
Bc Bc Bc Bc BcBc Bc B A
a d x d b x c
Bc Bc Bc Bc BcBc Bc B A
a d x d b x c
Etat Symbole Sens Nouvel état
Les lignes suivantes de la table diffèrent suivant la lettre lue. Ici, le ruban contient la lettre c,
… qui peuvent changer de←sens …
on passe donc dans l’état Bc et on continue
A
à
a,b,c,…,z
gauche : → A
A B
Bc Bc Bc Bc BcBc Bc B A
a d x d b x c
Etat Symbole Sens Nouvel état
Désormais, on continue à aller à gauche tant qu’on lit une des lettres a,b,d, . . . ,z, c’est-à-dire
toutes les lettres sauf c ou un blanc. UneA autre transition→permet Bcependant de traiter le cas
A a,b,c,…,z A
a d x d b x c
Etat Symbole Sens Nouvel état
Comme avant, on est arrivé au bout de la partie écrite du ruban, mais on suppose qu’on
A a,b,c,…,z
→ en ajoutant
est en fait sur un ruban infini (à gaucheA comme à droite),
A
des cases blanches à
gauche : ← B
B a Ba
←
B b
← Bb
B c
← Bc
… … … …
B z
← Bz
Bc a,b,d,…,z
← Bc
8.6. MACHINES DE TURING 163
… qui peuvent changer de sens …
Bc Bc Bc Bc BcBc Bc B A
a d x d b x c
Etat Symbole Sens Nouvel état
… qui peuvent changer de→sens …
Après avoir lu la lettre a, on arrive donc dans Ala configuration
a,b,c,…,z A
Bca B A ←
A B
Bc Bc Bc Bc BcBc
B
← Ba
B b
← Bb
a d x dB b x c c ← Bc
… … … …
Bcb B A ←
B a Ba
Bc OK Bc Bc BcBc B
← Bb
B c
← Bc
a d x d b x c … … … …
B z
← Bz
Bc
Etat
a,b,d,…,z
Symbole ← Nouvel
Sens
Bc
état
Cette machine vérifie donc que la dernière lettre de la séquence est différente de toutes les
A
autres lettres de la séquence : la table de transitions
a,b,c,…,z
donnée →plus haut
A
n’est pas complète,
A
puisqu’elle ne traite que le cas où la dernière lettre ← B
seraita un c mais il est Ba
aisé de la compléter...
B
Il est bien plus agréable de pouvoir faire un aller-retour sur
←ruban, pour aller chercher le
le
B b
← Bb
dernier symbole puis vérifier qu’il est différentB de tousc les autres. Cependant, il est possible
← Bc
d’accepter ce langage avec un automate fini, même
… si …le nombre
… d’états
… nécessaires est bien
Alan Turing va considérer que le champ visuel du calculateur est limité à un unique symbole.
À propos des états, il énonce :
≪ Le comportement du calculateur à chaque moment est déterminé par le
symbole qu’il observe et son état d’esprit à ce moment. ≫
Typiquement, lorsqu’un calculateur doit additionner 12932 et 19, il commence par mémoriser
le symbole 2 (le chiffre des unités du premier nombre), puis le symbole 9 (le chiffre des unités
du second nombre), il sait que leur somme fait 11 et qu’il doit donc écrire comme résultat
un 1 et qu’il doit retenir une retenue égale à 1. Il mémorise ensuite les chiffres des dizaines, 3
et 1, qu’il additionne en ajoute la retenue : il peut donc écrire 5 comme résultat, et poursuivre
son calcul.
≪ On suppose également que le nombre d’états d’esprit qu’on doit prendre
en compte est fini. Les raisons pour cela sont de la même nature que celles
qui restreignent le nombre de symboles. ≫
De la même manière que des symboles trop proches visuellement sont indiscernables – justi-
fiant qu’un nombre fini de symboles suffit – Alan Turing nous convainc que des états (d’esprit)
trop proches ne peuvent être distingués – justifiant donc qu’un nombre fini d’états suffit. Il fi-
nit de nous convaincre en précisant qu’on peut utiliser le ruban comme brouillon, pour retenir
plus de choses :
≪ On peut éviter l’utilisation d’états d’esprit plus compliqués en écrivant
Cette nouvelle machine a cinq états : Droite0, Droite1, Gauche0, Gauche1 et un état ≪ OK ≫ pour
signifier que la machine accepte. On supposera qu’elle démarre dans l’état Droite0 avec un
166 CHAPITRE 8. CALCULABILITÉ
ruban contenant une séquence de 0 et de 1, ainsi que des cases blanches à droite et à gauche,
de sorte que le ruban est en fait infini (même si à tout moment nous n’aurons besoin que d’une
portion finie de celui-ci). La machine utilisera des symboles supplémentaires, en s’autorisant
de barrer les lettres présentes sur le ruban. Les premières lignes de la table de transitions
doivent donc se lire comme le pseudo-code suivant, utilisant une variable état se rappelant
de l’état courant de la machine de Turing :
Si é tat = Droite0 et on lit 0 alors
é tat := Droite1
écrire X 0 sur le ruban
se d é placer à droite
Sinon Si é tat = Droite1 et on lit 0 ou 1 alors
se d é placer à droite
Sinon Si é tat = Droite1 et on lit une case blanche alors
é tat := Gauche1
se d é placer à gauche
Sinon ...
Exécutons la machine sur la séquence 000111 pour comprendre son fonctionnement. On
Droite0
0 0 0 1 1 1
Nouveau
Etat Symbole Sens Nouvel état
Droite1
0 0 0 1 1 1
X
Nouveau
Etat Symbole Sens Nouvel état
symbole
Les lignes 2 et 3 de la table de transition ne font que se déplacer vers la droite tant qu’on lit
… et écrire sur la bande
Droite0 0 → 0
X Droite1
des 0 et des 1 :
Droite1
0 0 0 1 1 1
X
… et écrire sur la bande
Etat Symbole Sens
Nouveau
symbole
Nouvel état
0 Droite1
0
Droite0
→ X Droite1
Droite1 0 → 0 Droite1
0 0 0 1 1 1
X
… et écrire sur la bande
Etat Symbole Sens
Nouveau
symbole
Nouvel état
0 0 Droite1
Droite0
→ X Droite1
Droite1 0 → 0 Droite1
0 0 0 1 1 1
X
Nouveau
Etat Symbole Sens Nouvel état
symbole
Droite0 0 → 0
X Droite1
Droite1 0 → 0 Droite1
Droite1 1 → 1 Droite1
… et écrire sur la bande
8.6. MACHINES DE TURING 167
Droite1
0 0 0 1 1 1
X
… et écrire sur la bande
Etat Symbole Sens
Nouveau
symbole
Nouvel état
0 Droite1
0
Droite0
→ X Droite1
Droite1 0 → 0 Droite1
Droite1
0
X 10 0 →
1 1 11 Droite1
Nouveau
Etat Symbole Sens Nouvel état
symbole
Lorsqu’on voit une case Droite0
blanche, la0 quatrième ligne deX la table
0 de transitions demande à
→ la gauche Droite1
… et écrire →
passer dans l’état Gauche1 en
Droite1
sur la bande
→
se
Droite1
déplaçant
0
1
vers 0 :
1
Droite1
Droite1
Gauche1
0 0 0 1 1 1
X
Nouveau
Etat Symbole Sens Nouvel état
0 0 0 1 1 X
X 1
Nouveau
Etat Symbole Sens Nouvel état
Gauche1 0 10 0 ←
X 1 1 X
1 1X Gauche0
Droite0 0 Gauche0
→ 0
X Droite1
Droite1 0 → 0 Droite1
Droite1
0
X 10 0 → 1 1 11
X Droite1
… et écrire ←
sur la bande
Droite1
←
Gauche1
Etat 1
Symbole Sens
Nouveau
1X
symbole
Gauche1
Gauche0
Nouvel état
Gauche0 1
Gauche0
0 ← 1
0
Gauche0
Droite0
→ X Droite1
Droite1 0 → 0 Droite1
Droite1
0 0 0 →
X 1 1 1 11
X Droite1
Gauche1
Etat 1
Symbole
←
←
Sens
Nouveau
1X
symbole
Gauche1
Gauche0
Nouvel état
Gauche0 1
Droite0 Gauche0
0 ← 1
0 Gauche0
→ X Droite1
Droite1 0 → 0 Droite1
Droite1
0 10 0 →
X 1 1 X11 Droite1
Droite1
← Nouveau
Gauche1
Gauche1
Etat 1
Symbole
←
Sens 1X
symbole
Gauche0
Nouvel état
Gauche0 1
0 ← 1
0 Gauche0
Droite0
→ X Droite1
Gauche0
Droite1 0
0 ←
→ 0
0 Gauche0
Droite1
Droite1 1 → 1 Droite1
Droite1
← Gauche1
Gauche1 1 ← 1X Gauche0
Gauche0 1 ← 1 Gauche0
168 CHAPITRE 8. CALCULABILITÉ
jusqu’à rencontrer un 0 barré, auquel cas la huitième ligne de la table prescrit de passer à
… et écrire sur la bande
nouveau dans l’état initial Droite0 en se déplaçant d’une case vers la droite :
Droite0
0 0 0 1 1 X
X 1
Nouveau
Etat Symbole Sens Nouvel état
symbole
On se retrouve ainsi presque dans la configuration initiale et onDroite1
effectue à nouveau un aller-
Droite0 0 0
→aller barrer
X
retour consistant à barrerDroite1
le 0 tout à gauche et le 1 pas encore barré tout à droite
… et écrire →sur la bande →
0 0 Droite1
du ruban : Droite1 1 1 Droite1
Droite1
Droite1← Gauche1
Gauche1 1 ← 1X Gauche0
1 1
0 ←
Gauche0 Gauche0
0
X 0X0 1 1 X10
Gauche0
← Gauche0
0 Droite1 0
Droite0
→ X Droite1
Droite1 0 → 0 Droite1
Droite1
0
X 1X0 0 → 1 1 X 11 Droite1
1 Droite1 1
Gauche0
Droite0 0 ←
→ 0X Gauche0
Droite1
Gauche0
Droite1 0
0 ←
→ 0
0 Gauche0
Droite1
Gauche0
Droite1
0 X
X 0
X
1 0 0 →→1 1 X 1 01X
Droite0
Droite1
1 Droite1
1
Gauche0
Droite0 0 ←
→ 0X Gauche0
Droite1
Gauche0
Droite1 0
0 ←
→ 0
0 Gauche0
Droite1
0
X
0 0 → 1 01X
Gauche0 Droite0
Droite1
0 X
X 1 →1 1 X Droite1
1 Gauche1 1
Gauche0
Droite0 0 ←
→ 0X Gauche0
Droite1
Gauche0
Droite1 0
0 ←
→ 0
0 Gauche0
Droite1
Gauche0
Droite1
0 X
X 0
X
1 0 0 →→1 1 X 1 10X
Droite0
Droite1
1 Gauche0 1
Gauche0
Droite0 0 ←
→ 0X Gauche0
Droite1
Gauche0
Droite1 0
0 ←
→ 00 Gauche0
Droite1
Gauche0
Droite1
0 X
X 0
X
1 →
0 0 1 1 X X 1 10X
Droite0
Droite1
Gauche1
Etat 1
Symbole
←
←
Sens
Nouveau
1X
symbole
Gauche1
Gauche0
Nouvel état
Gauche0 1 Gauche0
0 ← 10 Gauche0
Droite0
→ X Droite1
Gauche0
Droite1 0
0 ←
→
00
Gauche0
Droite1
Gauche0
Droite1
0 10X X
X
X
0 0 →→1 1 X X 1 01X
X Droite0
Droite1
Droite1
Droite1 1 ←
←
1 Gauche1
Gauche1
Nouveau
Gauche1
Etat 1
Symbole
←
Sens 1X
symbole
Gauche0
Nouvel état
Gauche0 1
0 ← 1
0 Gauche0
Droite0
→ X Droite1
Gauche0
Droite1 0
0 ←
→ 0
0 Gauche0
Droite1
Gauche0
Droite1 0
X
1 →
→ 0
1X Droite0
Droite1
Droite1 1
X 1X Gauche1
Droite1
← Gauche1
Gauche1 1 ← 1X Gauche0
Gauche0 1 ← 1 Gauche0
… et écrire sur la bande
8.6. MACHINES DE TURING 169
Gauche0
0 X
X 0 0 1 1 1
X X
… et écrire sur la bande
Etat Symbole Sens
Nouveau
symbole
Nouvel état
Droite0
Droite0 0 → 0X Droite1
Droite1 0 → 0 Droite1
Droite1
0
X 1X0 0 → 1 1 X X 11 Droite1
Droite1
← Nouveau
Gauche1
Etat
Gauche1 1
Symbole
←
Sens 1X
symbole
Nouvel
Gauche0 état
Gauche1
Etat 1
Symbole
←
←
Sens
Nouveau
1X
symbole
Gauche1
Gauche0
Nouvel état
1 Gauche1 1
Gauche0
Droite0 0 ←
→ 0X Gauche0
Droite1
Gauche0
Droite1 0
0 ←
→ 0
0 Gauche0
Droite1
Gauche0
Droite1
0
X 0
X
1 0
X 0
X →
1
→ 1
X 1
X 0
1X Droite0
Droite1
Gauche1
Etat 1
Symbole
←
Sens 1X
symbole
Gauche0
Nouvel état
1 Gauche0 1
Gauche0
Droite0 0 ←
→ 0X Gauche0
Droite1
Gauche0
Droite1 0
0 ←
→ 0
0 Gauche0
Droite1
Gauche0
Droite1
0 1X
X 0
X
0 X 0 → →
X
1 1 X X 110X Droite0
Droite1
1 Droite0 1
Gauche0
Droite0 0 ←
→ 0X Gauche0
Droite1
Gauche0
Droite1 0
0 ←
→ 0
0 Gauche0
Droite1
0
X 0X
Gauche0
Droite1
0
X 1 0
X 0
X X
1
→ 1
X 1
X 1 Droite0
Droite1
Droite1
Droite1 1
X
← 1 X
Nouveau
Gauche1
Gauche1
Etat
Gauche1 1
Symbole
←
Sens 1X
symbole
Nouvel
Gauche0 état
La machine accepte donc la séquence 000111. On peut en fait montrer que cette machine
accepte exactement toutes les séquences de la forme 0n 1n (avec n > 0), c’est-à-dire toutes les
séquences de 0 suivies de 1 avec autant de 0 que de 1 : nous avons vu au Théorème 5 que ce
langage ne peut pas être accepté par un automate fini, ni même par une machine qui peut se
déplacer dans les deux sens sans pouvoir écrire sur le ruban (par le Théorème 6). Voici donc
un langage que seule une machine de Turing qui peut écrire sur son ruban peut accepter.
Notons cependant qu’elle accepte ce langage d’une façon bien différente de la manière dont
vous avez dû vous y prendre dans l’exercice 57...
Exercice 58
Exécuter cette machine de Turing, depuis l’état initial Droite0, sur les séquences 00011,
00111, 10 puis 0011 pour se convaincre sur quelques exemples qu’elle reconnaı̂t bien le
langage {0n 1n | n ∈ N \ {0}}.
— Finalement, il nous reste à savoir faire un peu d’arithmétique pour pouvoir, par
Incrémentation
exemple, incrémenter un compteur i, c’est-à-dire transformer une portion du ruban
contenant le codage binaire d’un entier i, en cette même portion de ruban qui abritera
le codage binaire de i + 1. Vous devriez facilement être convaincu qu’une machine de
OK Gfaire
Turing va pouvoir Gça,D
Gde G
D G
D G
la même Dmanière
D D
G G
que Dnous l’avons fait en début de
Chapitre 4. L’exercice suivant vous permet de le vérifier.
Exercice 59
1 0d’une
Voici la table de transitions 0 machine
0 0 de0Turing 0 0 ayant trois états (D, G et OK),
dont l’état D est l’état initial, et OK l’état acceptant :
Nouveau Nouvel
Etat Symbole Sens
symbole état
D 0
→ 0 D
D 1
→ 1 D
D
← G
G 1
← 0 G
G 0
← 1 OK
G
← 1 OK
Cela donne donc l’intuition (il existe évidemment des preuves plus formelles de ce résultat,
bien au-delà de l’ambition de ce cours) que tout pseudo-code peut être exécuté par une
machine de Turing. C’est finalement exactement la façon dont le code Python qu’on écrit
s’exécute : il est transformé en une séquence d’opérations très simples qui peuvent être com-
prises par le processeur de l’ordinateur.
Réciproquement, il est aussi facile de se convaincre qu’on peut écrire un pseudo-code qui
exécute n’importe quelle machine de Turing. Nous avons déjà vu précédemment que la table
de transition d’une machine de Turing pouvait être encodée dans du pseudo-code utilisant une
variable état pour maintenir l’état courant et un tableau pour stocker le contenu du ruban
(avec une variable supplémentaire pour se souvenir de la position courante de la tête de lecture
sur le ruban). Il ne reste plus qu’à observer que la répétition des étapes d’exécution d’une
machine de Turing peut être obtenue par une boucle while... comme illustré en Figure 8.8.
Machines de Turing et pseudo-code ont donc le même pouvoir d’expression : c’est la raison
pour laquelle on dit que les machines de Turing sont une version idéalisée des ordinateurs
programmables qui seront inventés par la suite.
Nouveau Nouvel
Etat Symbole Sens
symbole état
A 0 → 1 B
A 1 ← A A
A ← OK B
séquences) sur un alphabet fini est calculable s’il existe une machine de Turing qui acceptent
Nouveau Nouvel
Etat Symbole Sens
symbole état
G
→ 0 D
G 0
← 0 G
G 1
← 1 G
D
← 1 G
D 0
→ 0 D
D 1
→ 1 D
Exécuter cette machine à partir du ruban ne contenant que des cases blanches. Observer
que cette machine ne s’arrête pas.
Maintenant qu’on a une définition claire de ce qui est calculable, nous pouvons enfin
revenir à la question initiale : ≪ peut-on tout calculer ? ≫. La réponse est négative et nous
8.8. PEUT-ON TOUT CALCULER ? 173
Problème de l’arrêt
allons même pouvoir exhiber un problème qu’on ne peut pas résoudre avec une machine de
Turing (et donc un ordinateur). Il s’agit du problème de l’arrêt :
Entrées Sorties
Avec les maigres outils dont nous disposons, nous sommes déjà en mesure de prouver ce
résultat (contrairement à la preuve de l’impossibilité de la quadrature du cercle qui fait appel
à des structures mathématiques assez complexes). Raisonnons par l’absurde en supposant
qu’il existe une machine de Turing qui résolve le problème de l’arrêt : cette machine prend
Problème de l’arrêt
donc en entrée la table de transitions d’une machine M et un ruban d’entrée, et décide si, oui
ou non, M s’arrête.
Machine M
Décide l’arrêt ! M s’arrête ?
+ ruban
Construisons
Construisons alors une
une nouvelle
nouvelle machine de Turing à partir de celle-ci. On la définit plutôt à
machine
qui suitfonction
l’aide d’une le pseudo-code
Pythonsuivant : sait que cela est équivalent d’après la section précédente) :
(mais on
def fonction diagonale(M
diagonale( M): : machine):
if Si M s’arrête
M s’arr^ete sursur un un ruban
ruban de de départ
départ contenant
contenant la le pseudo-code
table de M: de M alors
x x= :=
0 0
Tant que x ≥ 0 faire
while x x:=>=x+10 faire
x = x + 1
FinTantQue Entrées diagonale Sorties
else :
Sinon
retourner(OK)
return OK
Le testFinSi
sur l’arrêt de M (en rouge) est réaliséqui
Machine pars’arrête
la machine de Turing donten
Tourne onboucle
a supposé
l’existence préalablement. Cette nouvelle machine peut être schématisée ainsi :
Machine qui
OK
ne s’arrête pas
+ ruban
Machine qui
OK
ne s’arrête pas
Notons en effet que si la machine M donnée en entrée s’arrête sur un ruban de départ qui
contient sa propre table de transitions, alors la machine diagonale ne s’arrête pas puisqu’on
entre dans une boucle infinie. Au contraire, si on déduit que la machine M ne s’arrête pas,
alors la machine diagonale s’arrête et accepte.
Parvenons désormais à une contradiction en donnant à manger à la machine diagonale
la table de transitions de la machine diagonale elle-même. Que donne alors l’exécution de
diagonale(diagonale) ? Deux cas sont possibles :
— si diagonale s’arrête lorsqu’on lui donne en entrée la table de transitions de la machine
diagonale, alors on entre dans la boucle infinie donc on ne s’arrête pas ;
— au contraire, si diagonale ne s’arrête pas lorsqu’on lui donne en entrée la table de
transitions de la machine diagonale, alors on retourne OK donc on s’arrête en accep-
tant.
Ainsi, diagonale(diagonale) s’arrête si et seulement si diagonale(diagonale) ne s’arrête
pas ! Ce qui est évidemment une contradiction à l’existence d’une machine de Turing résolvant
le problème de l’arrêt. On a ainsi prouvé par l’absurde qu’une telle machine ne pouvait pas
exister.
Un tel problème qu’aucune machine de Turing ne peut résoudre est souvent dit indécidable.
Le fait que le problème de l’arrêt soit indécidable est une très mauvaise nouvelle pour la science
informatique : cela veut dire qu’on ne peut pas écrire d’algorithme qui conclut si un autre
algorithme termine ou non. Or, nous avons vu qu’il est crucial de savoir si un algorithme
se termine (et même ensuite de déterminer sa complexité) : aucun espoir qu’un ordinateur
puisse jamais répondre à coup sûr à cette question cependant !
D’autres problèmes très importants sont aussi indécidables :
— Est-ce qu’une machine de Turing donnée atteint un certain état (par exemple, un
état acceptant) ? Ce problème, et en fait tout problème non trivial sur les machines
de Turing (c’est le théorème de Rice, énoncé par Henry Gordon Rice en 1951), est
indécidable, ce qui se montre par réduction à partir du problème de l’arrêt.
— Est-ce qu’une proposition mathématique donnée est un théorème (c’est-à-dire, peut-
on en trouver une preuve) ? Une proposition mathématique est une formule avec des
quantificateurs et des opérateurs logiques : par exemple, la formule
∀x ∈ R ∀y ∈ R x ̸= y =⇒ ∃z ∈ R x < z < y
est vraie, puisqu’entre deux réels différents, on peut toujours trouver un autre réel (on
dit que l’ensemble des réels est dense). La recherche d’une preuve pour une proposition
mathématique est le problème de la décision énoncé par David Hilbert (Entsheidung-
sproblem en allemand) qui motiva initialement Alan Turing lorsqu’il mit au point ses
machines éponymes dans son article de 1936 dont le titre complet est On Computable
Numbers, with an Application to the Entscheidungsproblem.
8.8. PEUT-ON TOUT CALCULER ? 175
— David Hilbert (1862-1943, né à Königsberg, ville dont nous avons déjà évoqué l’exis-
tence avec le problème des graphes eulériens) a listé 23 problèmes mathématiques
en 1900 dont certains sont encore non résolus à ce jour. Le 10ème problème était
de trouver un algorithme déterminant si une équation diophantienne a des solutions.
Une équation diophantienne est une équation polynomiale à coefficients entiers, à une
ou plusieurs inconnues, dont on cherche des solutions entières. Par exemple, voici un
système d’équations diophantiennes :
(
x3 y − 3y 2 z = 20
−7y 4 + 4yz 3 = 0
C’est en 1970 que Iouri Matiassevitch (né en 1947) démontra l’indécidabilité du 10ème
problème de Hilbert.
176 CHAPITRE 8. CALCULABILITÉ
Chapitre 9
Conclusion
177
Exemple
Étiqueter des images (ou des vidéos) avec les objets qu’elles contiennent
Figure 9.1 – Segmentation et étiquetage d’images
Ludovic DENOYER - [Link]@[Link] Cours Apprentissage 1 : Introduction
des ordinateurs actuels, les méthodes d’apprentissage statistique ont permis de résoudre des
problèmes jusqu’alors hors de portée des ordinateurs. De tels algorithmes, basés sur l’étude
statistique de masses de données, permettent par exemple de segmenter et étiqueter des
images ou des vidéos avec les objets qu’elles contiennent (cf Figure 9.1), de reconnaitre des
écritures manuscrites ou la voix dans les assistants vocaux, de prédire l’évolution de la bourse,
d’explorer Mars, de jouer aux échecs ou au Go, ou de conduire des voitures autonomes.
Différentes méthodes d’intelligence artificielle et d’apprentissage statistique permettent de
résoudre ces problèmes : la dernière en date, ayant montré le plus de résultats époustouflants
récemment, consiste en l’utilisation de réseaux de neurones artificiels, imitant la structure
cérébrale d’un cerveau humain pour décomposer un problème complexe en sous-problèmes de
plus en plus spécialisés. L’application de telles méthodes statistiques pour des applications
telles que la conduite de voitures autonomes pose des questions éthiques puisque des vies
humaines sont en jeu : se satisfera-t-on d’intelligences artificielles mises au point par des
méthodes d’apprentissage statistique, sans que quiconque ne comprenne vraiment comment
ces intelligences prennent leurs décisions ? En cas d’accident, qui sera déclaré responsable ?
Et accepterons-nous que nos données personnelles soient utilisées par des compagnies privées
afin d’alimenter les algorithmes d’apprentissage statistique ? Voici autant de questions qui
sont les challenges d’aujourd’hui et de demain dans ce domaine.