PRÉAMBULE : LE CODAGE

« L’information n’est pas le savoir. Le savoir n’est pas la sagesse. La sagesse n’est pas la beauté.
La beauté n’est pas l’amour. L’amour n’est pas la musique, et la musique, c’est ce qu’il y a de
mieux. » - Frank Zappa
« Les ordinateurs sont comme les dieux de l’Ancien Testament : avec beaucoup de règles, et sans
pitié. » - Joseph Campbell
« Compter en octal, c’est comme compter en décimal, si on n’utilise pas ses pouces » - Tom Lehrer
« Il y a 10 sortes de gens au monde : ceux qui connaissent le binaire et les autres » - Anonyme

C’est bien connu, les ordinateurs sont comme le gros rock qui tâche : ils sont binaires.
Mais ce qui est moins connu, c’est ce que ce qualificatif de « binaire » recouvre
exactement, et ce qu’il implique. Aussi, avant de nous plonger dans les arcanes de
l’algorithmique proprement dite, ferons-nous un détour par la notion de codage binaire.
Contrairement aux apparences, nous ne sommes pas éloignés de notre sujet principal.
Tout au contraire, ce que nous allons voir à présent constitue un ensemble de notions
indispensables à l’écriture de programmes. Car pour parler à une machine, mieux vaut
connaître son vocabulaire…

1. POURQUOI LES ORDINATEURS SONT-ILS « BINAIRES »?

De nos jours, les ordinateurs sont ces machines merveilleuses capables de traiter du
texte, d’afficher des tableaux de maître, de jouer de la musique ou de projeter des
vidéos. On n’en est pas encore tout à fait à HAL, l’ordinateur de 2001 Odyssée de
l’Espace, à « l’intelligence » si développée qu’il a peur de mourir… pardon, d’être
débranché. Mais l’ordinateur paraît être une machine capable de tout faire.
Pourtant, les ordinateurs ont beau sembler repousser toujours plus loin les limites de
leur champ d’action, il ne faut pas oublier qu’en réalité, ces fiers-à-bras ne sont toujours
capables que d’une seule chose : faire des calculs, et uniquement cela. Eh oui, ces gros
malins d’ordinateurs sont restés au fond ce qu’ils ont été depuis leur invention : de
vulgaires calculatrices améliorées !
Lorsqu’un ordinateur traite du texte, du son, de l’image, de la vidéo, il traite en réalité
des nombres. En fait, dire cela, c’est déjà lui faire trop d’honneur. Car même le simple
nombre « 3 » reste hors de portée de l’intelligence d’un ordinateur, ce qui le situe
largement en dessous de l’attachant chimpanzé Bonobo, qui sait, entre autres choses,
faire des blagues à ses congénères et jouer au Pac-Man. Un ordinateur manipule
exclusivement des informations binaires, dont on ne peut même pas dire sans être
tendancieux qu’il s’agit de nombres.
Mais qu’est-ce qu’une information binaire ? C’est une information qui ne peut avoir
que deux états : par exemple, ouvert - fermé, libre – occupé, militaire – civil, assis –
couché, blanc – noir, vrai – faux, etc. Si l’on pense à des dispositifs physiques permettant
de stocker ce genre d’information, on pourrait citer : chargé – non chargé, haut – bas,
troué – non troué.
Je ne donne pas derniers exemples au hasard : ce sont précisément ceux dont se sert
un ordinateur pour stocker l’ensemble des informations qu’il va devoir manipuler. En

KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
deux mots, la mémoire vive (la « RAM ») est formée de millions de composants
électroniques qui peuvent retenir ou relâcher une charge électrique. La surface d’un
disque dur, d’une bande ou d’une disquette est recouverte de particules métalliques qui
peuvent, grâce à un aimant, être orientées dans un sens ou dans l’autre. Et sur un CD-
ROM, on trouve un long sillon étroit irrégulièrement percé de trous.
Toutefois, la coutume veut qu’on symbolise une information binaire, quel que soit son
support physique, sous la forme de 1 et de 0. Il faut bien comprendre que ce n’est là
qu’une représentation, une image commode, que l’on utilise pour parler de toute
information binaire. Dans la réalité physique, il n’y a pas plus de 1 et de 0 qui se
promènent dans les ordinateurs qu’il n’y a écrit, en lettres géantes, « Océan Atlantique »
sur la mer quelque part entre la Bretagne et les Antilles. Le 1 et le 0 dont parlent les
informaticiens sont des signes, ni plus, ni moins, pour désigner une information,
indépendamment de son support physique.
Les informaticiens seraient-ils des gens tordus, possédant un goût immodéré pour
l’abstraction, ou pour les jeux intellectuels alambiqués ? Non, pas davantage en tout cas
que le reste de leurs contemporains non-informaticiens. En fait, chacun d’entre nous
pratique ce genre d’abstraction tous les jours, sans pour autant trouver cela bizarre ou
difficile. Simplement, nous le faisons dans la vie quotidienne sans y penser. Et à force de
ne pas y penser, nous ne remarquons même plus quel mécanisme subtil d’abstraction est
nécessaire pour pratiquer ce sport.
Lorsque nous disons que 4+3=7 (ce qui reste, normalement, dans le domaine de
compétence mathématique de tous ceux qui lisent ce cours !), nous manions de pures
abstractions, représentées par de non moins purs symboles ! Un être humain d’il y a
quelques millénaires se serait demandé longtemps qu’est-ce que c’est que « quatre » ou
« trois », sans savoir quatre ou trois « quoi ? ». Mine de rien, le fait même de concevoir
des nombres, c’est-à-dire de pouvoir considérer, dans un ensemble, la quantité
indépendamment de tout le reste, c’est déjà une abstraction très hardie, qui a mis très
longtemps avant de s’imposer à tous comme une évidence. Et le fait de faire des
additions sans devoir préciser des additions « de quoi ? », est un pas supplémentaire qui
a été encore plus difficile à franchir.
Le concept de nombre, de quantité pure, a donc constitué un immense progrès (que
les ordinateurs n’ont quant à eux, je le répète, toujours pas accompli). Mais si concevoir
les nombres, c’est bien, posséder un système de notation performant de ces nombres,
c’est encore mieux. Et là aussi, l’humanité a mis un certain temps (et essayé un certain
nombre de pistes qui se sont révélées être des impasses) avant de parvenir au système
actuel, le plus rationnel. Ceux qui ne sont pas convaincus des progrès réalisés en ce
domaine peuvent toujours essayer de résoudre une multiplication comme 587 x 644 en
chiffres romains, on leur souhaite bon courage !

Retour Haut de Page

2. LA NUMÉROTATION DE POSITION EN BASE DÉCIMALE

KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
 L’humanité actuelle, pour représenter n’importe quel nombre, utilise un système de
numérotation de position, à base décimale. Qu’est-ce qui se cache derrière cet
obscur jargon ?
Commençons par la numérotation de position. Pour représenter un nombre, aussi
grand soit-il, nous disposons d’un alphabet spécialisé : une série de 10 signes qui
s’appellent les chiffres. Et lorsque nous écrivons un nombre en mettant certains de ces
chiffres les uns derrière les autres, l’ordre dans lequel nous mettons les chiffres est
capital. Ainsi, par exemple, 2 569 n’est pas du tout le même nombre que 9 562. Et
pourquoi ? Quel opération, quel décodage mental effectuons-nous lorsque nous lisons une
suite de chiffres représentant un nombre ? Le problème, c’est que nous sommes
tellement habitués à faire ce décodage de façon instinctive que généralement nous n’en
connaissons plus les règles. Mais ce n’est pas très compliqué de les reconstituer… Et
c’est là que nous mettons le doigt en plein dans la deuxième caractéristique de notre
système de notation numérique : son caractère décimal.
Lorsque j’écris 9562, de quel nombre est-ce que je parle ? Décomposons la lecture
chiffre par chiffre, de gauche à droite :
9562, c’est 9000 + 500 + 60 + 2.
Allons plus loin, même si cela paraît un peu bébête :

 9000, c’est 9 x 1000, parce que le 9 est le quatrième chiffre en partant de

la droite
 500, c’est 5 x 100, parce que le 5 est le troisième chiffre en partant de la
droite

 60, c’est 6 x 10, parce que le 6 est le deuxième chiffre en partant de la

droite

 2, c’est 2 x 1, parce que le 5 est le premier chiffre en partant de la droite

On peut encore écrire ce même nombre d’une manière légèrement différente. Au lieu
de :
9 562 = 9 x 1 000 + 5 x 100 + 6 x 10 + 2,
On écrit que :
9 562 = (9 x 10 x 10 x 10) + (5 x 10 x 10) + (6 x 10) + (2)
Arrivés à ce stade de la compétition, je prie les allergiques de m’excuser, mais il nous
faut employer un petit peu de jargon mathématique. Ce n’est pas grand-chose, et on
touche au but. Alors, courage ! En fait, ce jargon se résume au fait que les matheux
notent la ligne ci-dessus à l’aide du symbole de « puissance ». Cela donne :
9 562 = 9 x 103 + 5 x 102 + 6 x 101 + 2 x 100
Et voilà, nous y sommes. Nous avons dégagé le mécanisme général de la
représentation par numérotation de position en base décimale.
Alors, nous en savons assez pour conclure sur les conséquences du choix de la base
décimale. Il y en a deux, qui n’en forment en fin de compte qu’une seule :

KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
  parce que nous sommes en base décimale, nous utilisons un alphabet
numérique de dix symboles. Nous nous servons de dix chiffres, pas un de plus, pas
un de moins.
 toujours parce nous sommes en base décimale, la position d’un de ces dix
chiffres dans un nombre désigne la puissance de dix par laquelle ce chiffre doit
être multiplié pour reconstituer le nombre. Si je trouve un 7 en cinquième position
à partir de la droite, ce 7 ne représente pas 7 mais 7 fois 104, soit 70 000.

Un dernier mot concernant le choix de la base dix. Pourquoi celle-là et pas une autre ?
Après tout, la base dix n’était pas le seul choix possible. Les babyloniens, qui furent de
brillants mathématiciens, avaient en leur temps adopté la base 60 (dite sexagésimale).
Cette base 60 impliquait certes d’utiliser un assez lourd alphabet numérique de 60
chiffres. Mais c’était somme toute un inconvénient mineur, et en retour, elle possédait
certains avantages non négligeables. 60 étant un nombre divisible par beaucoup d’autres
(c’est pour cette raison qu’il avait été choisi), on pouvait, rien qu’en regardant le dernier
chiffre, savoir si un nombre était divisible par 2, 3, 4, 5, 6, 10, 12, 15, 20 et 30. Alors
qu’en base 10, nous ne pouvons immédiatement répondre à la même question que pour
les diviseurs 2 et 5. La base sexagésimale a certes disparu en tant que système de
notation des nombres. Mais Babylone nous a laissé en héritage sa base sexagésimale
dans la division du cercle en soixante parties (pour compter le temps en minutes et
secondes), et celle en 6 x 60 parties (pour les degrés de la géométrie et de l’astronomie).
Alors, pourquoi avons-nous adopté la base décimale, moins pratique à bien des
égards ? Nul doute que cela tienne au dispositif matériel grâce auquel tout être humain
normalement constitué stocke spontanément une information numérique : ses doigts !

Retour Haut de Page

3. LA NUMÉROTATION DE POSITION EN BASE BINAIRE
Les ordinateurs, eux, comme on l’a vu, on un dispositif physique fait pour stocker (de
multiples façons) des informations binaires. Alors, lorsqu’on représente une information
stockée par un ordinateur, le plus simple est d’utiliser un système de représentation à
deux chiffres : les fameux 0 et 1. Mais une fois de plus, je me permets d’insister, le choix
du 0 et du 1 est une pure convention, et on aurait pu choisir n’importe quelle autre paire
de symboles à leur place.
Dans un ordinateur, le dispositif qui permet de stocker de l’information est donc
rudimentaire, bien plus rudimentaire que les mains humaines. Avec des mains humaines,
on peut coder dix choses différentes (en fait bien plus, si l’on fait des acrobaties avec ses
doigts, mais écartons ce cas). Avec un emplacement d’information d’ordinateur, on est
limité à deux choses différentes seulement. Avec une telle information binaire, on ne va
pas loin. Voilà pourquoi, dès leur invention, les ordinateurs ont été conçus pour manier
ces informations par paquets de 0 et de 1. Et la taille de ces paquets a été fixée à 8
informations binaires.

KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
Une information binaire (symbolisée couramment par 0 ou 1) s’appelle un bit
(en anglais... bit).
Un groupe de huit bits s’appelle un octet (en anglais, byte)
Donc, méfiance avec le byte (en abrégé, B majuscule), qui vaut un octet, c'est-
à-dire huit bits (en abrégé, b minsucule).
Dans combien d’états différents un octet peut-il se trouver ? Le calcul est assez facile
(mais il faut néanmoins savoir le refaire). Chaque bit de l’octet peut occuper deux états. Il
y a donc dans un octet :
2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 = 28 = 256 possibilités
Cela signifie qu’un octet peut servir à coder 256 nombres différents : ce peut être la
série des nombres entiers de 1 à 256, ou de 0 à 255, ou de –127 à +128. C’est une pure
affaire de convention, de choix de codage. Mais ce qui n’est pas affaire de choix, c’est le
nombre de possibilités : elles sont 256, pas une de plus, pas une de moins, à cause de ce
qu’est, par définition, un octet.
Si l’on veut coder des nombres plus grands que 256, ou des nombres négatifs, ou des
nombres décimaux, on va donc être contraint de mobiliser plus d’un octet. Ce n’est pas
un problème, et c’est très souvent que les ordinateurs procèdent ainsi.
En effet, avec deux octets, on a 256 x 256 = 65 536 possibilités.
En utilisant trois octets, on passe à 256 x 256 x 256 = 16 777 216 possibilités.
Et ainsi de suite, je ne m’attarderai pas davantage sur les différentes manières de
coder les nombres avec des octets. On abordera de nouveau brièvement le sujet un peu
plus loin.
Cela implique également qu’un octet peut servir à coder autre chose qu’un nombre :
l’octet est très souvent employé pour coder du texte. Il y a 26 lettres dans l’alphabet.
Même en comptant différemment les minuscules et les majuscules, et même en y
ajoutant les chiffres et les signes de ponctuation, on arrive à un total inférieur à 256. Cela
veut dire que pour coder convenablement un texte, le choix d’un caractère par octet est
un choix pertinent.
Se pose alors le problème de savoir quel caractère doit être représenté par quel état
de l’octet. Si ce choix était librement laissé à chaque informaticien, ou à chaque fabricant
d’ordinateur, la communication entre deux ordinateurs serait un véritable casse-tête.
L’octet 10001001 serait par exemple traduit par une machine comme un T majuscule, et
par une autre comme une parenthèse fermante ! Aussi, il existe un standard international
de codage des caractères et des signes de ponctuation. Ce standard stipule quel état de
l’octet correspond à quel signe du clavier. Il s’appelle l’ASCII (pour American Standard
Code for Information Interchange). Et fort heureusement, l’ASCII est un standard
universellement reconnu et appliqué par les fabricants d’ordinateurs et de logiciels. Bien
sûr, se pose le problème des signes propres à telle ou telle langue (comme les lettres
accentuées en français, par exemple). L’ASCII a paré le problème en réservant certains
codes d’octets pour ces caractères spéciaux à chaque langue. En ce qui concerne les
langues utilisant un alphabet non latin, un standard particulier de codage a été mis au

KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
point. Quant aux langues non alphabétiques (comme le chinois), elles payent un lourd
tribut à l’informatique pour n’avoir pas su évoluer vers le système alphabétique…
Revenons-en au codage des nombres sur un octet. Nous avons vu qu’un octet pouvait
coder 256 nombres différents, par exemple (c’est le choix le plus spontané) la série des
entiers de 0 à 255. Comment faire pour, à partir d’un octet, reconstituer le nombre dans
la base décimale qui nous est plus familière ? Ce n’est pas sorcier ; il suffit d’appliquer, si
on les a bien compris, les principes de la numérotation de position, en gardant à l’esprit
que là, la base n’est pas décimale, mais binaire. Prenons un octet au hasard :
11010011
D'après les principes vus plus haut, ce nombre représente en base dix, en partant de
la gauche :
1 x 2 7 + 1 x 26 + 0 x 25 + 1 x 24 + 0 x 23 + 0 x 22 + 1 x 21 + 1 x 20 =
1 x 128 + 1 x 64 + 1 x 16 + 1 x 2 + 1 x 1 =
128 + 64 + 16 + 2 + 1 =
211
Et voilà ! Ce n’est pas plus compliqué que cela !
Inversement, comment traduire un nombre décimal en codage binaire ? Il suffit de
rechercher dans notre nombre les puissances successives de deux. Prenons, par
exemple, 186.
Dans 186, on trouve 1 x 128, soit 1 x 27. Je retranche 128 de 186 et j’obtiens 58.
Dans 58, on trouve 0 x 64, soit 0 x 26. Je ne retranche donc rien.
Dans 58, on trouve 1 x 32, soit 1 x 25. Je retranche 32 de 58 et j’obtiens 26.
Dans 26, on trouve 1 x 16, soit 1 x 24. Je retranche 16 de 26 et j’obtiens 10.
Dans 10, on trouve 1 x 8, soit 1 x 23. Je retranche 8 de 10 et j’obtiens 2.
Dans 2, on trouve 0 x 4, soit 0 x 22. Je ne retranche donc rien.
Dans 2, on trouve 1 x 2, soit 1 x 21. Je retranche 2 de 2 et j’obtiens 0.
Dans 0, on trouve 0 x 1, soit 0 x 20. Je ne retranche donc rien.
Il ne me reste plus qu’à reporter ces différents résultats (dans l’ordre !) pour
reconstituer l’octet. J’écris alors qu’en binaire, 186 est représenté par :
10111010
C’est bon ? Alors on passe à la suite.

Retour Haut de Page

4. LE CODAGE HEXADÉCIMAL
Pour en finir avec ce préambule (sinon, cela deviendrait de la gourmandise) , on va
évoquer un dernier type de codage, qui constitue une alternative pratique au codage
binaire. Il s’agit du codage hexadécimal, autrement dit en base seize.
Pourquoi ce choix bizarre ? Tout d’abord, parce que le codage binaire, ce n’est tout de
même pas très économique, ni très lisible. Pas très économique : pour représenter un
nombre entre 1 et 256, il faut utiliser systématiquement huit chiffres. Pas très lisible :
parce que d’interminables suites de 1 et de 0, on a déjà vu plus folichon.

KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
 Alors, une alternative toute naturelle, c’était de représenter l’octet non comme huit
bits (ce que nous avons fait jusque là), mais comme deux paquets de 4 bits (les quatre de
gauche, et les quatre de droite). Voyons voir cela de plus près.
Avec 4 bits, nous pouvons coder 2 x 2 x 2 x 2 = 16 nombres différents. En base seize,
16 nombres différents se représentent avec un seul chiffre (de même qu’en base 10, dix
nombres se représentent avec un seul chiffre).
Quels symboles choisir pour les chiffres ? Pour les dix premiers, on n’a pas été
chercher bien loin : on a recyclé les dix chiffres de la base décimale. Les dix premiers
nombres de la base seize s’écrivent donc tout bêtement 0, 1, 2, 3, 4, 5, 6, 7, 8, et 9. Là, il
nous manque encore 6 chiffres, pour représenter les nombres que nous écrivons en
décimal 10, 11, 12, 13, 14, 15 et 16. Plutôt qu’inventer de nouveaux symboles (ce qu’on
aurait très bien pu faire), on a recyclé les premières lettres de l’alphabet. Ainsi, par
convention, A vaut 10, B vaut 11, etc. jusqu’à F qui vaut 15.
Or, on s’aperçoit que cette base hexadécimale permet une représentation très simple
des octets du binaire. Prenons un octet au hasard :
10011110
Pour convertir ce nombre en hexadécimal, il y a deux méthodes : l’une consiste à faire
un grand détour, en repassant par la base décimale. C’est un peu plus long, mais on y
arrive. L’autre méthode consiste à faire le voyage direct du binaire vers l’hexadécimal.
Avec l’habitude, c’est nettement plus rapide !
Première méthode :
On retombe sur un raisonnement déjà abordé. Cet octet représente en base dix :
1 x 2 7 + 0 x 26 + 0 x 25 + 1 x 24 + 1 x 23 + 1 x 22 + 1 x 21 + 0 x 20 =
1 x 128 + 1 x 16 + 1 x 8 + 1 x 4 + 1 x 2 + 0 x 1 =
128 + 16 + 8 + 4 + 2 =
158
De là, il faut repartir vers la base hexadécimale.
Dans 158, on trouve 9 x 16, c’est-à-dire 9 x 16 1. Je retranche 144 de 158 et j’obtiens
14.
Dans 14, on trouve 14 x 1, c’est-à-dire 14 x 160. On y est.
Le nombre s’écrit donc en hexadécimal : 9E
Deuxième méthode :
Divisons 1 0 0 1 1 1 1 0 en 1 0 0 1 (partie gauche) et 1 1 1 0 (partie droite).
1 0 0 1, c’est 8 + 1, donc 9
1 1 1 0, c’est 8 + 4 + 2 donc 14
Le nombre s’écrit donc en hexadécimal : 9E. C’est la même conclusion qu’avec la
première méthode. Encore heureux !

PARTIE 1
INTRODUCTION A L’ALGORITHMIQUE
« Un langage de programmation est une convention pour donner des ordres à un ordinateur. Ce
n’est pas censé être obscur, bizarre et plein de pièges subtils. Ca, ce sont les caractéristiques de la
magie. » - Dave Small
KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
« C'est illogique, Capitaine » - Mr Spock

L’algorithmique est un terme d’origine arabe, comme algèbre, amiral ou zénith. Ce

n’est pas une excuse pour massacrer son orthographe, ou sa prononciation.
Ainsi, l’algo n’est pas « rythmique », à la différence du bon rock’n roll. L’algo n’est pas
non plus « l’agglo ».
Alors, ne confondez pas l’algorithmique avec l’agglo rythmique, qui consiste à poser
des parpaings en cadence.

1. QU’EST-CE QUE L’ALGOMACHIN ?

Avez-vous déjà ouvert un livre de recettes de cuisine ? Avez vous déjà déchiffré un
mode d’emploi traduit directement du coréen pour faire fonctionner un magnétoscope ou
un répondeur téléphonique réticent ? Si oui, sans le savoir, vous avez déjà exécuté des
algorithmes.
Plus fort : avez-vous déjà indiqué un chemin à un touriste égaré ? Avez vous fait
chercher un objet à quelqu’un par téléphone ? Ecrit une lettre anonyme stipulant
comment procéder à une remise de rançon ? Si oui, vous avez déjà fabriqué – et fait
exécuter – des algorithmes.
Comme quoi, l’algorithmique n’est pas un savoir ésotérique réservé à quelques rares
initiés touchés par la grâce divine, mais une aptitude partagée par la totalité de
l’humanité. Donc, pas d’excuses…
Un algorithme, c’est une suite d’instructions, qui une fois exécutée
correctement, conduit à un résultat donné. Si l’algorithme est juste, le résultat est le
résultat voulu, et le touriste se retrouve là où il voulait aller. Si l’algorithme est faux, le
résultat est, disons, aléatoire, et décidément, cette saloperie de répondeur ne veut rien
savoir.
Complétons toutefois cette définition. Après tout, en effet, si l’algorithme, comme on
vient de le dire, n’est qu’une suite d’instructions menant celui qui l’exécute à résoudre un
problème, pourquoi ne pas donner comme instruction unique : « résous le problème », et
laisser l’interlocuteur se débrouiller avec ça ? A ce tarif, n’importe qui serait champion
d’algorithmique sans faire aucun effort. Pas de ça Lisette, ce serait trop facile.
Le malheur (ou le bonheur, tout dépend du point de vue) est que justement, si le
touriste vous demande son chemin, c’est qu’il ne le connaît pas. Donc, si on n’est pas un
goujat intégral, il ne sert à rien de lui dire de le trouver tout seul. De même les modes
d’emploi contiennent généralement (mais pas toujours) un peu plus d’informations que
« débrouillez vous pour que ça marche ».
Pour fonctionner, un algorithme doit donc contenir uniquement des
instructions compréhensibles par celui qui devra l’exécuter. C’est d’ailleurs l’un
des points délicats pour les rédacteurs de modes d’emploi : les références culturelles, ou
lexicales, des utilisateurs, étant variables, un même mode d’emploi peut être très clair
pour certains et parfaitement abscons pour d’autres.

KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
 En informatique, heureusement, il n’y a pas ce problème : les choses auxquelles ont
doit donner des instructions sont les ordinateurs, et ceux-ci ont le bon goût d’être tous
strictement aussi idiots les uns que les autres.

Retour Haut de Page

2. FAUT-IL
ÊTRE MATHEUX POUR ÊTRE BON EN
ALGORITHMIQUE ?
Je consacre quelques lignes à cette question, car cette opinion aussi fortement
affirmée que faiblement fondée sert régulièrement d’excuse : « moi, de toute façon, je
suis mauvais(e) en algo, j’ai jamais rien pigé aux maths ». Faut-il être « bon en maths »
pour expliquer correctement son chemin à quelqu’un ? Je vous laisse juge.
La maîtrise de l’algorithmique requiert deux qualités, très complémentaires d’ailleurs :
 il faut avoir une certaine intuition, car aucune recette ne permet de savoir
a priori quelles instructions permettront d’obtenir le résultat voulu. C’est là, si l’on
y tient, qu’intervient la forme « d’intelligence » requise pour l’algorithmique. Alors,
c’est certain, il y a des gens qui possèdent au départ davantage cette intuition
que les autres. Cependant, et j’insiste sur ce point, les réflexes, cela s’acquiert. Et
ce qu’on appelle l’intuition n’est finalement que de l’expérience tellement répétée
que le raisonnement, au départ laborieux, finit par devenir « spontané ».
 il faut être méthodique et rigoureux. En effet, chaque fois qu’on écrit une
série d’instructions qu’on croit justes, il faut systématiquement se mettre
mentalement à la place de la machine qui va les exécuter, armé d'un papier et
d'un crayon, afin de vérifier si le résultat obtenu est bien celui que l’on voulait.
Cette opération ne requiert pas la moindre once d’intelligence. Mais elle reste
néanmoins indispensable, si l’on ne veut pas écrire à l’aveuglette.

Et petit à petit, à force de pratique, vous verrez que vous pourrez faire de plus en plus
souvent l’économie de cette dernière étape : l’expérience fera que vous « verrez » le
résultat produit par vos instructions, au fur et à mesure que vous les écrirez.
Naturellement, cet apprentissage est long, et demande des heures de travail patient.
Aussi, dans un premier temps, évitez de sauter les étapes : la vérification méthodique,
pas à pas, de chacun de vos algorithmes représente plus de la moitié du travail
à accomplir... et le gage de vos progrès.

Retour Haut de Page

3. L’ADN, LES SHADOKS, ET LES ORDINATEURS

Quel rapport me direz-vous ? Eh bien le point commun est : quatre mots de
vocabulaire.

KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
 L’univers lexical Shadok, c’est bien connu, se limite aux termes « Ga », « Bu », « Zo »,
et « Meu ». Ce qui leur a tout de même permis de formuler quelques fortes maximes,
telles que : « Mieux vaut pomper et qu’il ne se passe rien, plutôt qu’arrêter de pomper et
risquer qu’il se passe quelque chose de pire » (pour d’autres fortes maximes Shadok,
n’hésitez pas à visiter leur site Internet, il y en a toute une collection qui vaut le détour).
L’ADN, qui est en quelque sorte le programme génétique, l’algorithme à la base de
construction des êtres vivants, est une chaîne construite à partir de quatre éléments
invariables. Ce n’est que le nombre de ces éléments, ainsi que l’ordre dans lequel ils sont
arrangés, qui vont déterminer si on obtient une puce ou un éléphant. Et tous autant que
nous sommes, splendides réussites de la Nature, avons été construits par un
« programme » constitué uniquement de ces quatre briques, ce qui devrait nous inciter à
la modestie.
Enfin, les ordinateurs, quels qu’ils soient, ne sont fondamentalement capables de
comprendre que quatre catégories d'ordres (en programmation, on n'emploiera pas le
terme d'ordre, mais plutôt celui d'instructions). Ces quatre familles d'instructions sont :
 l’affectation de variables
 la lecture / écriture
 les tests
 les boucles

Un algorithme informatique se ramène donc toujours au bout du compte à la

combinaison de ces quatre petites briques de base. Il peut y en avoir quelques unes,
quelques dizaines, et jusqu’à plusieurs centaines de milliers dans certains programmes
de gestion. Rassurez-vous, dans le cadre de ce cours, nous n’irons pas jusque là
(cependant, la taille d’un algorithme ne conditionne pas en soi sa complexité : de longs
algorithmes peuvent être finalement assez simples, et de petits très compliqués).

Retour Haut de Page

4. ALGORITHMIQUE ET PROGRAMMATION
Pourquoi apprendre l’algorithmique pour apprendre à programmer ? En quoi a-t-on
besoin d’un langage spécial, distinct des langages de programmation compréhensibles
par les ordinateurs ?
Parce que l’algorithmique exprime les instructions résolvant un problème donné
indépendamment des particularités de tel ou tel langage. Pour prendre une
image, si un programme était une dissertation, l’algorithmique serait le plan, une fois mis
de côté la rédaction et l’orthographe. Or, vous savez qu’il vaut mieux faire d’abord le plan
et rédiger ensuite que l’inverse…
Apprendre l’algorithmique, c’est apprendre à manier la structure logique d’un
programme informatique. Cette dimension est présente quelle que soit le langage de
programmation ; mais lorsqu’on programme dans un langage (en C, en Visual Basic, etc.)
on doit en plus se colleter les problèmes de syntaxe, ou de types d’instructions, propres à
KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
ce langage. Apprendre l’algorithmique de manière séparée, c’est donc sérier les
difficultés pour mieux les vaincre.
A cela, il faut ajouter que des générations de programmeurs, souvent autodidactes
(mais pas toujours, hélas !), ayant directement appris à programmer dans tel ou tel
langage, ne font pas mentalement clairement la différence entre ce qui relève de la
structure logique générale de toute programmation (les règles fondamentales de
l’algorithmique) et ce qui relève du langage particulier qu’ils ont appris. Ces
programmeurs, non seulement ont beaucoup plus de mal à passer ensuite à un langage
différent, mais encore écrivent bien souvent des programmes qui même s’ils sont justes,
restent laborieux. Car on n’ignore pas impunément les règles fondamentales de
l’algorithmique… Alors, autant l’apprendre en tant que telle !
Bon, maintenant que j’ai bien fait l’article pour vendre ma marchandise, on va presque
pouvoir passer au vif du sujet…

Retour Haut de Page

5. AVEC QUELLES CONVENTIONS ÉCRIT-ON UN ALGORITHME ?

Historiquement, plusieurs types de notations ont représenté des algorithmes.
Il y a eu notamment une représentation graphique, avec des carrés, des losanges, etc.
qu’on appelait des organigrammes. Aujourd’hui, cette représentation est quasiment
abandonnée, pour deux raisons. D’abord, parce que dès que l’algorithme commence à
grossir un peu, ce n’est plus pratique du tout du tout. Ensuite parce que cette
représentation favorise le glissement vers un certain type de programmation, dite non
structurée (nous définirons ce terme plus tard), que l’on tente au contraire d’éviter.
C’est pourquoi on utilise généralement une série de conventions appelée « pseudo-
code », qui ressemble à un langage de programmation authentique dont on aurait
évacué la plupart des problèmes de syntaxe. Ce pseudo-code est susceptible de varier
légèrement d’un livre (ou d’un enseignant) à un autre. C’est bien normal : le pseudo-
code, encore une fois, est purement conventionnel ; aucune machine n’est censée le
reconnaître. Donc, chaque cuisinier peut faire sa sauce à sa guise, avec ses petites épices
bien à lui, sans que cela prête à conséquence.
Comme je n’ai pas moins de petites manies que la majorité de mes semblables, le
pseudo-code que vous découvrirez dans les pages qui suivent possède quelques
spécificités mineures qui ne doivent qu’à mes névroses personnelles.
Rassurez-vous cependant, celles-ci restent dans les limites tout à fait acceptables.
En tout cas, personnellement, je les accepte très bien.

PARTIE 1
INTRODUCTION A L’ALGORITHMIQUE
« Un langage de programmation est une convention pour donner des ordres à un ordinateur. Ce
n’est pas censé être obscur, bizarre et plein de pièges subtils. Ca, ce sont les caractéristiques de la
magie. » - Dave Small
KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
« C'est illogique, Capitaine » - Mr Spock

L’algorithmique est un terme d’origine arabe, comme algèbre, amiral ou zénith. Ce

n’est pas une excuse pour massacrer son orthographe, ou sa prononciation.
Ainsi, l’algo n’est pas « rythmique », à la différence du bon rock’n roll. L’algo n’est pas
non plus « l’agglo ».
Alors, ne confondez pas l’algorithmique avec l’agglo rythmique, qui consiste à poser
des parpaings en cadence.

1. QU’EST-CE QUE L’ALGOMACHIN ?

Avez-vous déjà ouvert un livre de recettes de cuisine ? Avez vous déjà déchiffré un
mode d’emploi traduit directement du coréen pour faire fonctionner un magnétoscope ou
un répondeur téléphonique réticent ? Si oui, sans le savoir, vous avez déjà exécuté des
algorithmes.
Plus fort : avez-vous déjà indiqué un chemin à un touriste égaré ? Avez vous fait
chercher un objet à quelqu’un par téléphone ? Ecrit une lettre anonyme stipulant
comment procéder à une remise de rançon ? Si oui, vous avez déjà fabriqué – et fait
exécuter – des algorithmes.
Comme quoi, l’algorithmique n’est pas un savoir ésotérique réservé à quelques rares
initiés touchés par la grâce divine, mais une aptitude partagée par la totalité de
l’humanité. Donc, pas d’excuses…
Un algorithme, c’est une suite d’instructions, qui une fois exécutée
correctement, conduit à un résultat donné. Si l’algorithme est juste, le résultat est le
résultat voulu, et le touriste se retrouve là où il voulait aller. Si l’algorithme est faux, le
résultat est, disons, aléatoire, et décidément, cette saloperie de répondeur ne veut rien
savoir.
Complétons toutefois cette définition. Après tout, en effet, si l’algorithme, comme on
vient de le dire, n’est qu’une suite d’instructions menant celui qui l’exécute à résoudre un
problème, pourquoi ne pas donner comme instruction unique : « résous le problème », et
laisser l’interlocuteur se débrouiller avec ça ? A ce tarif, n’importe qui serait champion
d’algorithmique sans faire aucun effort. Pas de ça Lisette, ce serait trop facile.
Le malheur (ou le bonheur, tout dépend du point de vue) est que justement, si le
touriste vous demande son chemin, c’est qu’il ne le connaît pas. Donc, si on n’est pas un
goujat intégral, il ne sert à rien de lui dire de le trouver tout seul. De même les modes
d’emploi contiennent généralement (mais pas toujours) un peu plus d’informations que
« débrouillez vous pour que ça marche ».
Pour fonctionner, un algorithme doit donc contenir uniquement des
instructions compréhensibles par celui qui devra l’exécuter. C’est d’ailleurs l’un
des points délicats pour les rédacteurs de modes d’emploi : les références culturelles, ou
lexicales, des utilisateurs, étant variables, un même mode d’emploi peut être très clair
pour certains et parfaitement abscons pour d’autres.

KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
 En informatique, heureusement, il n’y a pas ce problème : les choses auxquelles ont
doit donner des instructions sont les ordinateurs, et ceux-ci ont le bon goût d’être tous
strictement aussi idiots les uns que les autres.

Retour Haut de Page

2. FAUT-IL
ÊTRE MATHEUX POUR ÊTRE BON EN
ALGORITHMIQUE ?
Je consacre quelques lignes à cette question, car cette opinion aussi fortement
affirmée que faiblement fondée sert régulièrement d’excuse : « moi, de toute façon, je
suis mauvais(e) en algo, j’ai jamais rien pigé aux maths ». Faut-il être « bon en maths »
pour expliquer correctement son chemin à quelqu’un ? Je vous laisse juge.
La maîtrise de l’algorithmique requiert deux qualités, très complémentaires d’ailleurs :
 il faut avoir une certaine intuition, car aucune recette ne permet de savoir
a priori quelles instructions permettront d’obtenir le résultat voulu. C’est là, si l’on
y tient, qu’intervient la forme « d’intelligence » requise pour l’algorithmique. Alors,
c’est certain, il y a des gens qui possèdent au départ davantage cette intuition
que les autres. Cependant, et j’insiste sur ce point, les réflexes, cela s’acquiert. Et
ce qu’on appelle l’intuition n’est finalement que de l’expérience tellement répétée
que le raisonnement, au départ laborieux, finit par devenir « spontané ».
 il faut être méthodique et rigoureux. En effet, chaque fois qu’on écrit une
série d’instructions qu’on croit justes, il faut systématiquement se mettre
mentalement à la place de la machine qui va les exécuter, armé d'un papier et
d'un crayon, afin de vérifier si le résultat obtenu est bien celui que l’on voulait.
Cette opération ne requiert pas la moindre once d’intelligence. Mais elle reste
néanmoins indispensable, si l’on ne veut pas écrire à l’aveuglette.

Et petit à petit, à force de pratique, vous verrez que vous pourrez faire de plus en plus
souvent l’économie de cette dernière étape : l’expérience fera que vous « verrez » le
résultat produit par vos instructions, au fur et à mesure que vous les écrirez.
Naturellement, cet apprentissage est long, et demande des heures de travail patient.
Aussi, dans un premier temps, évitez de sauter les étapes : la vérification méthodique,
pas à pas, de chacun de vos algorithmes représente plus de la moitié du travail
à accomplir... et le gage de vos progrès.

Retour Haut de Page

3. L’ADN, LES SHADOKS, ET LES ORDINATEURS

Quel rapport me direz-vous ? Eh bien le point commun est : quatre mots de
vocabulaire.

KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
 L’univers lexical Shadok, c’est bien connu, se limite aux termes « Ga », « Bu », « Zo »,
et « Meu ». Ce qui leur a tout de même permis de formuler quelques fortes maximes,
telles que : « Mieux vaut pomper et qu’il ne se passe rien, plutôt qu’arrêter de pomper et
risquer qu’il se passe quelque chose de pire » (pour d’autres fortes maximes Shadok,
n’hésitez pas à visiter leur site Internet, il y en a toute une collection qui vaut le détour).
L’ADN, qui est en quelque sorte le programme génétique, l’algorithme à la base de
construction des êtres vivants, est une chaîne construite à partir de quatre éléments
invariables. Ce n’est que le nombre de ces éléments, ainsi que l’ordre dans lequel ils sont
arrangés, qui vont déterminer si on obtient une puce ou un éléphant. Et tous autant que
nous sommes, splendides réussites de la Nature, avons été construits par un
« programme » constitué uniquement de ces quatre briques, ce qui devrait nous inciter à
la modestie.
Enfin, les ordinateurs, quels qu’ils soient, ne sont fondamentalement capables de
comprendre que quatre catégories d'ordres (en programmation, on n'emploiera pas le
terme d'ordre, mais plutôt celui d'instructions). Ces quatre familles d'instructions sont :
 l’affectation de variables
 la lecture / écriture
 les tests
 les boucles

Un algorithme informatique se ramène donc toujours au bout du compte à la

combinaison de ces quatre petites briques de base. Il peut y en avoir quelques unes,
quelques dizaines, et jusqu’à plusieurs centaines de milliers dans certains programmes
de gestion. Rassurez-vous, dans le cadre de ce cours, nous n’irons pas jusque là
(cependant, la taille d’un algorithme ne conditionne pas en soi sa complexité : de longs
algorithmes peuvent être finalement assez simples, et de petits très compliqués).

Retour Haut de Page

4. ALGORITHMIQUE ET PROGRAMMATION
Pourquoi apprendre l’algorithmique pour apprendre à programmer ? En quoi a-t-on
besoin d’un langage spécial, distinct des langages de programmation compréhensibles
par les ordinateurs ?
Parce que l’algorithmique exprime les instructions résolvant un problème donné
indépendamment des particularités de tel ou tel langage. Pour prendre une
image, si un programme était une dissertation, l’algorithmique serait le plan, une fois mis
de côté la rédaction et l’orthographe. Or, vous savez qu’il vaut mieux faire d’abord le plan
et rédiger ensuite que l’inverse…
Apprendre l’algorithmique, c’est apprendre à manier la structure logique d’un
programme informatique. Cette dimension est présente quelle que soit le langage de
programmation ; mais lorsqu’on programme dans un langage (en C, en Visual Basic, etc.)
on doit en plus se colleter les problèmes de syntaxe, ou de types d’instructions, propres à
KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
ce langage. Apprendre l’algorithmique de manière séparée, c’est donc sérier les
difficultés pour mieux les vaincre.
A cela, il faut ajouter que des générations de programmeurs, souvent autodidactes
(mais pas toujours, hélas !), ayant directement appris à programmer dans tel ou tel
langage, ne font pas mentalement clairement la différence entre ce qui relève de la
structure logique générale de toute programmation (les règles fondamentales de
l’algorithmique) et ce qui relève du langage particulier qu’ils ont appris. Ces
programmeurs, non seulement ont beaucoup plus de mal à passer ensuite à un langage
différent, mais encore écrivent bien souvent des programmes qui même s’ils sont justes,
restent laborieux. Car on n’ignore pas impunément les règles fondamentales de
l’algorithmique… Alors, autant l’apprendre en tant que telle !
Bon, maintenant que j’ai bien fait l’article pour vendre ma marchandise, on va presque
pouvoir passer au vif du sujet…

Retour Haut de Page

5. AVEC QUELLES CONVENTIONS ÉCRIT-ON UN ALGORITHME ?

Historiquement, plusieurs types de notations ont représenté des algorithmes.
Il y a eu notamment une représentation graphique, avec des carrés, des losanges, etc.
qu’on appelait des organigrammes. Aujourd’hui, cette représentation est quasiment
abandonnée, pour deux raisons. D’abord, parce que dès que l’algorithme commence à
grossir un peu, ce n’est plus pratique du tout du tout. Ensuite parce que cette
représentation favorise le glissement vers un certain type de programmation, dite non
structurée (nous définirons ce terme plus tard), que l’on tente au contraire d’éviter.
C’est pourquoi on utilise généralement une série de conventions appelée « pseudo-
code », qui ressemble à un langage de programmation authentique dont on aurait
évacué la plupart des problèmes de syntaxe. Ce pseudo-code est susceptible de varier
légèrement d’un livre (ou d’un enseignant) à un autre. C’est bien normal : le pseudo-
code, encore une fois, est purement conventionnel ; aucune machine n’est censée le
reconnaître. Donc, chaque cuisinier peut faire sa sauce à sa guise, avec ses petites épices
bien à lui, sans que cela prête à conséquence.
Comme je n’ai pas moins de petites manies que la majorité de mes semblables, le
pseudo-code que vous découvrirez dans les pages qui suivent possède quelques
spécificités mineures qui ne doivent qu’à mes névroses personnelles.
Rassurez-vous cependant, celles-ci restent dans les limites tout à fait acceptables.
En tout cas, personnellement, je les accepte très bien.

PARTIE 1
LES VARIABLES
« N’attribuez jamais à la malveillance ce qui s’explique très bien par l’incompétence. » - Napoléon
Bonaparte

KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
« A l’origine de toute erreur attribuée à l’ordinateur, vous trouverez au moins deux erreurs
humaines. Dont celle consistant à attribuer l’erreur à l’ordinateur. » - Anonyme

1. A QUOI SERVENT LES VARIABLES ?

Dans un programme informatique, on va avoir en permanence besoin de stocker
provisoirement des valeurs. Il peut s’agir de données issues du disque dur, fournies par
l’utilisateur (frappées au clavier), ou que sais-je encore. Il peut aussi s’agir de résultats
obtenus par le programme, intermédiaires ou définitifs. Ces données peuvent être de
plusieurs types (on en reparlera) : elles peuvent être des nombres, du texte, etc. Toujours
est-il que dès que l’on a besoin de stocker une information au cours d’un programme, on
utilise une variable.
Pour employer une image, une variable est une boîte, que le programme (l’ordinateur)
va repérer par une étiquette. Pour avoir accès au contenu de la boîte, il suffit de la
désigner par son étiquette.
En réalité, dans la mémoire vive de l’ordinateur, il n’y a bien sûr pas une vraie boîte, et
pas davantage de vraie étiquette collée dessus (j’avais bien prévenu que la boîte et
l’étiquette, c’était une image). Dans l’ordinateur, physiquement, il y a un emplacement
de mémoire, repéré par une adresse binaire. Si on programmait dans un langage
directement compréhensible par la machine, on devrait se fader de désigner nos données
par de superbes 10011001 et autres 01001001 (enchanté !). Mauvaise nouvelle : de tels
langages existent ! Ils portent le doux nom d’assembleur. Bonne nouvelle : ce ne sont pas
les seuls langages disponibles.
Les langages informatiques plus évolués (ce sont ceux que presque tout le monde
emploie) se chargent précisément, entre autres rôles, d’épargner au programmeur la
gestion fastidieuse des emplacements mémoire et de leurs adresses. Et, comme vous
commencez à le comprendre, il est beaucoup plus facile d’employer les étiquettes de son
choix, que de devoir manier des adresses binaires.

Retour Haut de Page

2. DÉCLARATION DES VARIABLES
La première chose à faire avant de pouvoir utiliser une variable est de créer la boîte
et de lui coller une étiquette. Ceci se fait tout au début de l’algorithme, avant même
les instructions proprement dites. C’est ce qu’on appelle la déclaration des variables.
C’est un genre de déclaration certes moins romantique qu’une déclaration d’amour, mais
d’un autre côté moins désagréable qu’une déclaration d’impôts.
Le nom de la variable (l’étiquette de la boîte) obéit à des impératifs changeant selon
les langages. Toutefois, une règle absolue est qu’un nom de variable peut comporter des
lettres et des chiffres, mais qu’il exclut la plupart des signes de ponctuation, en
particulier les espaces. Un nom de variable correct commence également
impérativement par une lettre. Quant au nombre maximal de signes pour un nom de
variable, il dépend du langage utilisé.

KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
 En pseudo-code algorithmique, on est bien sûr libre du nombre de signes pour un nom
de variable, même si pour des raisons purement pratiques, et au grand désespoir de
Stéphane Bern, on évite généralement les noms à rallonge.
Lorsqu’on déclare une variable, il ne suffit pas de créer une boîte (réserver un
emplacement mémoire) ; encore doit-on préciser ce que l’on voudra mettre dedans, car
de cela dépendent la taille de la boîte (de l’emplacement mémoire) et le type de
codage utilisé.

2.1 Types numériques classiques

Commençons par le cas très fréquent, celui d’une variable destinée à recevoir des
nombres.
Si l’on réserve un octet pour coder un nombre, je rappelle pour ceux qui dormaient en
lisant le chapitre précédent qu’on ne pourra coder que 2 8 = 256 valeurs différentes. Cela
peut signifier par exemple les nombres entiers de 1 à 256, ou de 0 à 255, ou de –127 à
+128… Si l’on réserve deux octets, on a droit à 65 536 valeurs ; avec trois octets, 16 777
216, etc. Et là se pose un autre problème : ce codage doit-il représenter des nombres
décimaux ? des nombres négatifs ?
Bref, le type de codage (autrement dit, le type de variable) choisi pour un nombre va
déterminer :
 les valeurs maximales et minimales des nombres pouvant être stockés
dans la variable
 la précision de ces nombres (dans le cas de nombres décimaux).

Tous les langages, quels qu’ils soient offrent un « bouquet » de types numériques, dont le
détail est susceptible de varier légèrement d’un langage à l’autre. Grosso modo, on retrouve
cependant les types suivants :

Type Numérique Plage

Byte (octet) 0 à 255

Entier simple -32 768 à 32 767

Entier long -2 147 483 648 à 2 147 483 647

-3,40x10 à -1,40x1045 pour les valeurs négatives

38
Réel simple
1,40x10-45 à 3,40x1038 pour les valeurs positives

1,79x10308 à -4,94x10-324 pour les valeurs négatives

Réel double
4,94x10-324 à 1,79x10308 pour les valeurs positives
Pourquoi ne pas déclarer toutes les variables numériques en réel double, histoire de
bétonner et d’être certain qu’il n’y aura pas de problème ? En vertu du principe de
l’économie de moyens. Un bon algorithme ne se contente pas de « marcher » ; il
marche en évitant de gaspiller les ressources de la machine. Sur certains programmes de
grande taille, l’abus de variables surdimensionnées peut entraîner des ralentissements
notables à l’exécution, voire un plantage pur et simple de l’ordinateur. Alors, autant
prendre dès le début de bonnes habitudes d’hygiène.
KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
 En algorithmique, on ne se tracassera pas trop avec les sous-types de variables
numériques (sachant qu'on aura toujours assez de soucis comme ça, allez). On se
contentera donc de préciser qu'il s'agit d'un nombre, en gardant en tête que dans un vrai
langage, il faudra être plus précis.
En pseudo-code, une déclaration de variables aura ainsi cette tête :
Variable g en Numérique
ou encore
Variables PrixHT, TauxTVA, PrixTTC en Numérique
2.2 Autres types numériques
Certains langages autorisent d’autres types numériques, notamment :
 le type monétaire (avec strictement deux chiffres après la virgule)
 le type date (jour/mois/année).

Nous n’emploierons pas ces types dans ce cours ; mais je les signale, car vous ne
manquerez pas de les rencontrer en programmation proprement dite.

2.3 Type alphanumérique

Fort heureusement, les boîtes que sont les variables peuvent contenir bien d’autres
informations que des nombres. Sans cela, on serait un peu embêté dès que l’on devrait
stocker un nom de famille, par exemple.
On dispose donc également du type alphanumérique (également appelé type
caractère, type chaîne ou en anglais, le type string – mais ne fantasmez pas trop vite,
c’est loin d’être aussi excitant que le nom le suggère…).
Dans une variable de ce type, on stocke des caractères, qu’il s’agisse de lettres, de
signes de ponctuation, d’espaces, ou même de chiffres. Le nombre maximal de
caractères pouvant être stockés dans une seule variable string dépend du langage
utilisé.
Un groupe de caractères (y compris un groupe de un, ou de zéro caractères), qu’il soit
ou non stocké dans une variable, d’ailleurs, est donc souvent appelé chaîne de
caractères.
En pseudo-code, une chaîne de caractères est toujours notée entre guillemets
Pourquoi diable ? Pour éviter deux sources principales de possibles confusions :
 la confusion entre des nombres et des suites de chiffres. Par exemple, 423
peut représenter le nombre 423 (quatre cent vingt-trois), ou la suite de caractères
4, 2, et 3. Et ce n’est pas du tout la même chose ! Avec le premier, on peut faire
des calculs, avec le second, point du tout. Dès lors, les guillemets permettent
d’éviter toute ambiguïté : s’il n’y en a pas, 423 est quatre cent vingt trois. S’il y en
a, "423" représente la suite des chiffres 4, 2, 3.
 …Mais ce n'est pas le pire. L'autre confusion, bien plus grave - et bien plus
fréquente – consiste à se mélanger les pinceaux entre le nom d'une variable et
son contenu. Pour parler simplement, cela consiste à confondre l'étiquette d'une
boîte et ce qu'il y a à l'intérieur… On reviendra sur ce point crucial dans quelques
instants.
KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
2.4 Type booléen
Le dernier type de variables est le type booléen : on y stocke uniquement les valeurs
logiques VRAI et FAUX.
On peut représenter ces notions abstraites de VRAI et de FAUX par tout ce qu'on veut :
de l'anglais (TRUE et FALSE) ou des nombres (0 et 1). Peu importe. Ce qui compte, c'est
de comprendre que le type booléen est très économique en termes de place mémoire
occupée, puisque pour stocker une telle information binaire, un seul bit suffit.
Le type booléen est très souvent négligé par les programmeurs, à tort.

Il est vrai qu'il n'est pas à proprement parler indispensable, et qu'on pourrait écrire à peu
près n’importe quel programme en l'ignorant complètement. Pourtant, si le type booléen
est mis à disposition des programmeurs dans tous les langages, ce n'est pas pour rien. Le
recours aux variables booléennes s'avère très souvent un puissant instrument de
lisibilité des algorithmes : il peut faciliter la vie de celui qui écrit l'algorithme, comme de
celui qui le relit pour le corriger.

Alors, maintenant, c'est certain, en algorithmique, il y a une question de style : c'est

exactement comme dans le langage courant, il y a plusieurs manières de s'exprimer pour
dire sur le fond la même chose. Nous verrons plus loin différents exemples de variations
stylistiques autour d'une même solution. En attendant, vous êtes prévenus : l'auteur de
ce cours est un adepte fervent (mais pas irraisonné) de l'utilisation des variables
booléennes.

Retour Haut de Page

3. L’INSTRUCTION D’AFFECTATION
3.1 Syntaxe et signification
Ouf, après tout ce baratin préliminaire, on aborde enfin nos premières véritables
manipulations d’algorithmique. Pas trop tôt, certes, mais pas moyen de faire autrement !
En fait, la variable (la boîte) n'est pas un outil bien sorcier à manipuler. A la différence
du couteau suisse ou du superbe robot ménager vendu sur Télé Boutique Achat, on ne
peut pas faire trente-six mille choses avec une variable, mais seulement une et une
seule.
Cette seule chose qu’on puisse faire avec une variable, c’est l’affecter, c’est-à-dire
lui attribuer une valeur. Pour poursuivre la superbe métaphore filée déjà employée, on
peut remplir la boîte.
En pseudo-code, l'instruction d'affectation se note avec le signe ←
Ainsi :
Toto ← 24
Attribue la valeur 24 à la variable Toto.

KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
 Ceci, soit dit en passant, sous-entend impérativement que Toto soit une variable de
type numérique. Si Toto a été défini dans un autre type, il faut bien comprendre que
cette instruction provoquera une erreur. C’est un peu comme si, en donnant un ordre à
quelqu’un, on accolait un verbe et un complément incompatibles, du genre « Epluchez la
casserole ». Même dotée de la meilleure volonté du monde, la ménagère lisant cette
phrase ne pourrait qu’interrompre dubitativement sa tâche. Alors, un ordinateur, vous
pensez bien…
On peut en revanche sans aucun problème attribuer à une variable la valeur d’une
autre variable, telle quelle ou modifiée. Par exemple :
Tutu ← Toto
Signifie que la valeur de Tutu est maintenant celle de Toto.
Notez bien que cette instruction n’a en rien modifié la valeur de Toto : une
instruction d’affectation ne modifie que ce qui est situé à gauche de la flèche.
Tutu ← Toto + 4
Si Toto contenait 12, Tutu vaut maintenant 16. De même que précédemment, Toto
vaut toujours 12.
Tutu ← Tutu + 1
Si Tutu valait 6, il vaut maintenant 7. La valeur de Tutu est modifiée, puisque Tutu est
la variable située à gauche de la flèche.
Pour revenir à présent sur le rôle des guillemets dans les chaînes de caractères et sur
la confusion numéro 2 signalée plus haut, comparons maintenant deux algorithmes
suivants :
Exemple n°1
Début
Riri ← "Loulou"
Fifi ← "Riri"
Fin

Exemple n°2
Début
Riri ← "Loulou"
Fifi ← Riri
Fin
La seule différence entre les deux algorithmes consiste dans la présence ou dans
l’absence des guillemets lors de la seconde affectation. Et l'on voit que cela change tout !
Dans l'exemple n°1, ce que l'on affecte à la variable Fifi, c'est la suite de caractères R
– i – r - i. Et à la fin de l’algorithme, le contenu de la variable Fifi est donc « Riri ».
Dans l'exemple n°2, en revanche, Riri étant dépourvu de guillemets, n'est pas
considéré comme une suite de caractères, mais comme un nom de variable. Le sens de la
ligne devient donc : « affecte à la variable Fifi le contenu de la variable Riri ». A la fin de
l’algorithme n°2, la valeur de la variable Fifi est donc « Loulou ». Ici, l’oubli des
guillemets conduit certes à un résultat, mais à un résultat différent.
A noter, car c’est un cas très fréquent, que généralement, lorsqu’on oublie les
guillemets lors d’une affectation de chaîne, ce qui se trouve à droite du signe
KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
d’affectation ne correspond à aucune variable précédemment déclarée et affectée. Dans
ce cas, l’oubli des guillemets se solde immédiatement par une erreur d’exécution.
Ceci est une simple illustration. Mais elle résume l’ensemble des problèmes qui
surviennent lorsqu’on oublie la règle des guillemets aux chaînes de caractères.

3.2 Ordre des instructions

Il va de soi que l’ordre dans lequel les instructions sont écrites va jouer un rôle
essentiel dans le résultat final. Considérons les deux algorithmes suivants :
Exemple 1
Variable A en Numérique
Début
A ← 34
A ← 12
Fin

Exemple 2
Variable A en Numérique
Début
A ← 12
A ← 34
Fin
Il est clair que dans le premier cas la valeur finale de A est 12, dans l’autre elle est 34 .
Il est tout aussi clair que ceci ne doit pas nous étonner. Lorsqu’on indique le chemin à
quelqu’un, dire « prenez tout droit sur 1km, puis à droite » n’envoie pas les gens au
même endroit que si l’on dit « prenez à droite puis tout droit pendant 1 km ».
Enfin, il est également clair que si l’on met de côté leur vertu pédagogique, les deux
algorithmes ci-dessus sont parfaitement idiots ; à tout le moins ils contiennent une
incohérence. Il n’y a aucun intérêt à affecter une variable pour l’affecter différemment
juste après. En l’occurrence, on aurait tout aussi bien atteint le même résultat en
écrivant simplement :
Exemple 1
Variable A en Numérique
Début
A ← 12
Fin

Exemple 2
Variable A en Numérique
Début
A ← 34
Fin
Tous les éléments sont maintenant en votre possession pour que ce soit à vous de
jouer !
[Link]

KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
 Exercice 1.1
Exercice 1.2
Exercice 1.3
Exercice 1.4
Exercice 1.5
Exercice 1.6
Exercice 1.7

Retour Haut de Page

4. EXPRESSIONS ET OPÉRATEURS
Si on fait le point, on s’aperçoit que dans une instruction d’affectation, on trouve :
 à gauche de la flèche, un nom de variable, et uniquement cela. En ce
monde empli de doutes qu’est celui de l’algorithmique, c’est une des rares règles
d’or qui marche à tous les coups : si on voit à gauche d’une flèche d’affectation
autre chose qu’un nom de variable, on peut être certain à 100% qu’il s’agit d’une
erreur.
 à droite de la flèche, ce qu’on appelle une expression. Voilà encore un
mot qui est trompeur ; en effet, ce mot existe dans le langage courant, où il revêt
bien des significations. Mais en informatique, le terme d’expression ne désigne
qu’une seule chose, et qui plus est une chose très précise :

Une expression est un ensemble de valeurs, reliées par des opérateurs, et

équivalent à une seule valeur
Cette définition vous paraît peut-être obscure. Mais réfléchissez-y quelques minutes,
et vous verrez qu’elle recouvre quelque chose d’assez simple sur le fond. Par exemple,
voyons quelques expressions de type numérique. Ainsi :
7
5+4
123-45+844
Toto-12+5-Riri
…sont toutes des expressions valides, pour peu que Toto et Riri soient bien des
nombres. Car dans le cas contraire, la quatrième expression n’a pas de sens. En
l’occurrence, les opérateurs que j’ai employés sont l’addition (+) et la soustraction (-).
Revenons pour le moment sur l’affectation. Une condition supplémentaire (en plus des
deux précédentes) de validité d’une instruction d’affectation est que :
 l’expression située à droite de la flèche soit du même type que la variable
située à gauche. C’est très logique : on ne peut pas ranger convenablement des
outils dans un sac à provision, ni des légumes dans une trousse à outils… sauf à
provoquer un résultat catastrophique.

KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
 Si l’un des trois points énumérés ci-dessus n’est pas respecté, la machine sera
incapable d’exécuter l’affectation, et déclenchera une erreur (est-il besoin de dire que si
aucun de ces points n’est respecté, il y aura aussi erreur !)
On va maintenant détailler ce que l’on entend par le terme d’ opérateur.
Un opérateur est un signe qui relie deux valeurs, pour produire un résultat.
Les opérateurs possibles dépendent du type des valeurs qui sont en jeu. Allons-y,
faisons le tour, c’est un peu fastidieux, mais comme dit le sage au petit scarabée, quand
c’est fait, c’est plus à faire.

4.1 Opérateurs numériques :

Ce sont les quatre opérations arithmétiques tout ce qu’il y a de classique.
+ : addition
- : soustraction
* : multiplication
/ : division
Mentionnons également le ^ qui signifie « puissance ». 45 au carré s’écrira donc 45 ^
2.
Enfin, on a le droit d’utiliser les parenthèses, avec les mêmes règles qu’en
mathématiques. La multiplication et la division ont « naturellement » priorité sur
l’addition et la soustraction. Les parenthèses ne sont ainsi utiles que pour modifier cette
priorité naturelle.
Cela signifie qu’en informatique, 12 * 3 + 5 et (12 * 3) + 5 valent strictement la même
chose, à savoir 41. Pourquoi dès lors se fatiguer à mettre des parenthèses inutiles ?
En revanche, 12 * (3 + 5) vaut 12 * 8 soit 96. Rien de difficile là-dedans, que du
normal.

4.2 Opérateur alphanumérique : &

Cet opérateur permet de concaténer, autrement dit d’agglomérer, deux chaînes de
caractères. Par exemple :
Variables A, B, C en Caractère
Début
A ← "Gloubi"
B ← "Boulga"
C←A&B
Fin
La valeur de C à la fin de l’algorithme est "GloubiBoulga"

4.3 Opérateurs logiques (ou booléens) :

Il s’agit du ET, du OU, du NON et du mystérieux (mais rarissime XOR). Nous les
laisserons de côté… provisoirement, soyez-en sûrs.
Exercice 1.8
Exercice 1.9

KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
 Retour Haut de Page

5. DEUX REMARQUES POUR TERMINER

Maintenant que nous sommes familiers des variables et que nous les manipulons les
yeux fermés (mais les neurones en éveil, toutefois), j’attire votre attention sur la
trompeuse similitude de vocabulaire entre les mathématiques et l’informatique. En
mathématiques, une « variable » est généralement une inconnue, qui recouvre un
nombre non précisé de valeurs. Lorsque j’écris :
y=3x+2
les « variables » x et y satisfaisant à l’équation existent en nombre infini
(graphiquement, l’ensemble des solutions à cette équation dessine une droite). Lorsque
j’écris :
ax² + bx + c = 0
la « variable » x désigne les solutions à cette équation, c’est-à-dire zéro, une ou deux
valeurs à la fois…
En informatique, une variable possède à un moment donné une valeur et une
seule. A la rigueur, elle peut ne pas avoir de valeur du tout (une fois qu’elle a été
déclarée, et tant qu’on ne l’a pas affectée. A signaler que dans certains langages, les
variables non encore affectées sont considérées comme valant automatiquement zéro).
Mais ce qui est important, c’est que cette valeur justement, ne « varie » pas à
proprement parler. Du moins ne varie-t-elle que lorsqu’elle est l’objet d’une instruction
d’affectation.
La deuxième remarque concerne le signe de l’affectation. En algorithmique, comme on
l’a vu, c’est le signe ←. Mais en pratique, la quasi totalité des langages emploient le signe
égal. Et là, pour les débutants, la confusion avec les maths est également facile. En
maths, A = B et B = A sont deux propositions strictement équivalentes. En informatique,
absolument pas, puisque cela revient à écrire A ← B et B ← A, deux choses bien
différentes. De même, A = A + 1, qui en mathématiques, constitue une équation sans
solution, représente en programmation une action tout à fait licite (et de surcroît
extrêmement courante). Donc, attention ! ! ! La meilleure des vaccinations contre cette
confusion consiste à bien employer le signe ← en pseudo-code, signe qui a le mérite de
ne pas laisser place à l’ambiguïté. Une fois acquis les bons réflexes avec ce signe, vous
n’aurez plus aucune difficulté à passer au = des langages de programmation.

PARTIE 2
LECTURE ET ECRITURE
« Un programme est un sort jeté sur un ordinateur, qui transforme tout texte saisi au clavier en
message d’erreur. » - Anonyme

« Un clavier Azerty en vaut deux » - Anonyme

KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
1. DE QUOI PARLE-T-ON ?
Trifouiller des variables en mémoire vive par un chouette programme, c’est vrai que
c’est très marrant, et d’ailleurs on a tous bien rigolé au chapitre précédent. Cela dit, à la
fin de la foire, on peut tout de même se demander à quoi ça sert.
En effet. Imaginons que nous ayons fait un programme pour calculer le carré d’un
nombre, mettons 12. Si on a fait au plus simple, on a écrit un truc du genre :
Variable A en Numérique
Début
A ← 12^2
Fin
D’une part, ce programme nous donne le carré de 12. C’est très gentil à lui. Mais si
l’on veut le carré d’un autre nombre que 12, il faut réécrire le programme. Bof.
D’autre part, le résultat est indubitablement calculé par la machine. Mais elle le garde
soigneusement pour elle, et le pauvre utilisateur qui fait exécuter ce programme, lui, ne
saura jamais quel est le carré de 12. Re-bof.
C’est pourquoi, heureusement, il existe des d’instructions pour permettre à la machine
de dialoguer avec l’utilisateur (et Lycée de Versailles, eût ajouté l’estimé Pierre Dac, qui
en précurseur méconnu de l’algorithmique, affirmait tout aussi profondément que « rien
ne sert de penser, il faut réfléchir avant »).
Dans un sens, ces instructions permettent à l’utilisateur de rentrer des valeurs au
clavier pour qu’elles soient utilisées par le programme. Cette opération est la lecture.
Dans l’autre sens, d’autres instructions permettent au programme de communiquer
des valeurs à l’utilisateur en les affichant à l’écran. Cette opération est l’écriture.
Remarque essentielle : A première vue, on peut avoir l’impression que les
informaticiens étaient beurrés comme des petits lus lorsqu’ils ont baptisé ces opérations ;
puisque quand l’utilisateur doit écrire au clavier, on appelle ça la lecture, et quand il doit
lire sur l’écran on appelle çà l’écriture. Mais avant d’agonir d’insultes une digne
corporation, il faut réfléchir un peu plus loin. Un algorithme, c’est une suite d’instructions
qui programme la machine, pas l’utilisateur ! Donc quand on dit à la machine de lire une
valeur, cela implique que l’utilisateur va devoir écrire cette valeur. Et quand on demande
à la machine d’écrire une valeur, c’est pour que l’utilisateur puisse la lire. Lecture et
écriture sont donc des termes qui comme toujours en programmation, doivent être
compris du point de vue de la machine qui sera chargée de les exécuter. Et là, tout
devient parfaitement logique. Et toc.

Retour Haut de Page

2. LES INSTRUCTIONS DE LECTURE ET D’ÉCRITURE
Tout bêtement, pour que l’utilisateur entre la (nouvelle) valeur de Titi, on mettra :
Lire Titi
Dès que le programme rencontre une instruction Lire, l’exécution s’interrompt,
attendant la frappe d’une valeur au clavier

KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
 Dès lors, aussitôt que la touche Entrée (Enter) a été frappée, l’exécution reprend. Dans
le sens inverse, pour écrire quelque chose à l’écran, c’est aussi simple que :
Ecrire Toto
Avant de Lire une variable, il est très fortement conseillé d’écrire des libellés à
l’écran, afin de prévenir l’utilisateur de ce qu’il doit frapper (sinon, le pauvre utilisateur
passe son temps à se demander ce que l’ordinateur attend de lui… et c’est très
désagréable !) :
Ecrire "Entrez votre nom : "
Lire NomFamille
Lecture et Ecriture sont des instructions algorithmiques qui ne présentent pas de
difficultés particulières, une fois qu’on a bien assimilé ce problème du sens du dialogue
(homme → machine, ou machine ← homme).
Et ça y est, vous savez d’ores et déjà sur cette question tout ce qu’il y a à savoir…
Exercice 2.1
Exercice 2.2
Exercice 2.3
Exercice 2.4

PARTIE 3
LES TESTS
« Il est assez difficile de trouver une erreur dans son code quand on la cherche. C’est encore bien
plus dur quand on est convaincu que le code est juste. » - Steve McConnell

« Il n’existe pas, et il n’existera jamais, de langage dans lequel il soit un tant soit peu difficile
d’écrire de mauvais programmes ». - Anonyme

« Si le déboguage est l’art d’enlever les bogues, alors la programmation doit être l’art de les
créer. » - Anonyme

Je vous avais dit que l’algorithmique, c’est la combinaison de quatre structures

élémentaires. Nous en avons déjà vu deux, voici la troisième. Autrement dit, on a
quasiment fini le programme.
Mais non, je rigole.

1. DE QUOI S’AGIT-IL ?
Reprenons le cas de notre « programmation algorithmique du touriste égaré ».
Normalement, l’algorithme ressemblera à quelque chose comme : « Allez tout droit
jusqu’au prochain carrefour, puis prenez à droite et ensuite la deuxième à gauche, et
vous y êtes ».
Mais en cas de doute légitime de votre part, cela pourrait devenir : « Allez tout droit
jusqu’au prochain carrefour et là regardez à droite. Si la rue est autorisée à la circulation,
alors prenez la et ensuite c’est la deuxième à gauche. Mais si en revanche elle est en

KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
sens interdit, alors continuez jusqu’à la prochaine à droite, prenez celle-là, et ensuite la
première à droite ».
Ce deuxième algorithme a ceci de supérieur au premier qu’il prévoit, en fonction d’une
situation pouvant se présenter de deux façons différentes, deux façons différentes d’agir.
Cela suppose que l’interlocuteur (le touriste) sache analyser la condition que nous avons
fixée à son comportement (« la rue est-elle en sens interdit ? ») pour effectuer la série
d’actions correspondante.
Eh bien, croyez le ou non, mais les ordinateurs possèdent cette aptitude, sans laquelle
d’ailleurs nous aurions bien du mal à les programmer. Nous allons donc pouvoir parler à
notre ordinateur comme à notre touriste, et lui donner des séries d’instructions à
effectuer selon que la situation se présente d’une manière ou d’une autre. Cette structure
logique répond au doux nom de test. Toutefois, ceux qui tiennent absolument à briller en
société parleront également de structure alternative.

Retour Haut de Page

2. STRUCTURE D’UN TEST
Il n’y a que deux formes possibles pour un test ; la première est la plus simple, la
seconde la plus complexe.
Si booléen Alors
Instructions
Finsi
Si booléen Alors
Instructions 1
Sinon
Instructions 2
Finsi
Ceci appelle quelques explications.
Un booléen est une expression dont la valeur est VRAI ou FAUX. Cela peut donc être
(il n’y a que deux possibilités) :
 une variable (ou une expression) de type booléen
 une condition

Nous reviendrons dans quelques instants sur ce qu’est une condition en

informatique.
Toujours est-il que la structure d’un test est relativement claire. Dans la forme la plus
simple, arrivé à la première ligne (Si… Alors) la machine examine la valeur du booléen. Si
ce booléen a pour valeur VRAI, elle exécute la série d’instructions. Cette série
d’instructions peut être très brève comme très longue, cela n’a aucune importance. En
revanche, dans le cas où le booléen est faux, l'ordinateur saute directement aux
instructions situées après le FinSi.
Dans le cas de la structure complète, c'est à peine plus compliqué. Dans le cas où le
booléen est VRAI, et après avoir exécuté la série d'instructions 1, au moment où elle

KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
arrive au mot « Sinon », la machine saute directement à la première instruction située
après le « Finsi ». De même, au cas où le booléen a comme valeur « Faux », la machine
saute directement à la première ligne située après le « Sinon » et exécute l’ensemble des
« instructions 2 ». Dans tous les cas, les instructions situées juste après le FinSi seront
exécutées normalement.
En fait, la forme simplifiée correspond au cas où l’une des deux « branches » du Si est
vide. Dès lors, plutôt qu’écrire « sinon ne rien faire du tout », il est plus simple de ne rien
écrire. Et laisser un Si... complet, avec une des deux branches vides, est considéré
comme une très grosse maladresse pour un programmeur, même si cela ne constitue pas
à proprement parler une faute.
Exprimé sous forme de pseudo-code, la programmation de notre touriste de tout à
l’heure donnerait donc quelque chose du genre :
Allez tout droit jusqu’au prochain carrefour
Si la rue à droite est autorisée à la circulation Alors
Tournez à droite
Avancez
Prenez la deuxième à gauche
Sinon
Continuez jusqu’à la prochaine rue à droite
Prenez cette rue
Prenez la première à droite
Finsi

Retour Haut de Page

3. QU’EST CE QU’UNE CONDITION ?
Une condition est une comparaison
Cette définition est essentielle ! Elle signifie qu’une condition est composée de trois
éléments :
 une valeur
 un opérateur de comparaison
 une autre valeur

Les valeurs peuvent être a priori de n’importe quel type (numériques, caractères…).
Mais si l’on veut que la comparaison ait un sens, il faut que les deux valeurs de la
comparaison soient du même type !
Les opérateurs de comparaison sont :
 égal à…
 différent de…
 strictement plus petit que…
 strictement plus grand que…
 plus petit ou égal à…
 plus grand ou égal à…

KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
 L’ensemble des trois éléments constituant la condition constitue donc, si l’on veut, une
affirmation, qui a un moment donné est VRAIE ou FAUSSE.
A noter que ces opérateurs de comparaison peuvent tout à fait s’employer avec des
caractères. Ceux-ci sont codés par la machine dans l’ordre alphabétique (rappelez vous le
code ASCII vu dans le préambule), les majuscules étant systématiquement placées avant
les minuscules. Ainsi on a :
“t” < “w” VRAI
“Maman” > “Papa“ FAUX
“maman” > “Papa” VRAI
Remarque très importante

En formulant une condition dans un algorithme, il faut se méfier comme de la peste de

certains raccourcis du langage courant, ou de certaines notations valides en
mathématiques, mais qui mènent à des non-sens informatiques. Prenons par exemple la
phrase « Toto est compris entre 5 et 8 ». On peut être tenté de la traduire par : 5 < Toto
< 8
Or, une telle expression, qui a du sens en français, comme en mathématiques, ne veut
rien dire en programmation. En effet, elle comprend deux opérateurs de comparaison,
soit un de trop, et trois valeurs, soit là aussi une de trop. On va voir dans un instant
comment traduire convenablement une telle condition.
Exercice 3.1

Retour Haut de Page

4. CONDITIONS COMPOSÉES
Certains problèmes exigent parfois de formuler des conditions qui ne peuvent pas être
exprimées sous la forme simple exposée ci-dessus. Reprenons le cas « Toto est inclus
entre 5 et 8 ». En fait cette phrase cache non une, mais deux conditions. Car elle revient
à dire que « Toto est supérieur à 5 et Toto est inférieur à 8 ». Il y a donc bien là deux
conditions, reliées par ce qu’on appelle un opérateur logique, le mot ET.
Comme on l’a évoqué plus haut, l’informatique met à notre disposition quatre
opérateurs logiques : ET, OU, NON, et XOR.
 Le ET a le même sens en informatique que dans le langage courant. Pour
que "Condition1 ET Condition2" soit VRAI, il faut impérativement que Condition1
soit VRAI et que Condition2 soit VRAI. Dans tous les autres cas, "Condition 1 et
Condition2" sera faux.
 Il faut se méfier un peu plus du OU. Pour que "Condition1 OU Condition2"
soit VRAI, il suffit que Condition1 soit VRAIE ou que Condition2 soit VRAIE. Le point
important est que si Condition1 est VRAIE et que Condition2 est VRAIE aussi,
Condition1 OU Condition2 reste VRAIE. Le OU informatique ne veut donc pas dire «
ou bien »
 Le XOR (ou OU exclusif) fonctionne de la manière suivante. Pour que
"Condition1 XOR Condition2" soit VRAI, il faut que soit Condition1 soit VRAI, soit
KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
 que Condition2 soit VRAI. Si toutes les deux sont fausses, ou que toutes les deux
sont VRAI, alors le résultat global est considéré comme FAUX. Le XOR est donc
l'équivalent du "ou bien" du langage courant.
J’insiste toutefois sur le fait que le XOR est une rareté, dont il n’est pas strictement
indispensable de s’encombrer en programmation.
 Enfin, le NON inverse une condition : NON(Condition1)est VRAI si Condition1
est FAUX, et il sera FAUX si Condition1 est VRAI. C'est l'équivalent pour les
booléens du signe "moins" que l'on place devant les nombres.
Alors, vous vous demandez peut-être à quoi sert ce NON. Après tout, plutôt
qu’écrire NON(Prix > 20), il serait plus simple d’écrire tout bonnement Prix=<20.
Dans ce cas précis, c’est évident qu’on se complique inutilement la vie avec le
NON. Mais si le NON n'est jamais indispensable, il y a tout de même des situations
dans lesquelles il s'avère bien utile.

On représente fréquemment tout ceci dans des tables de vérité (C1 et C2

représentent deux conditions, et on envisage à chaque fois les quatre cas possibles)

C1 et C2 C2 Vrai C2 Faux
C1 Vrai Vrai Faux
C1 Faux Faux Faux

C1 ou C2 C2 Vrai C2 Faux
C1 Vrai Vrai Vrai
C1 Faux Vrai Faux

C1 xor C2 C2 Vrai C2 Faux

C1 Vrai Faux Vrai
C1 Faux Vrai Faux

Non C1
C1 Vrai Faux
C1 Faux Vrai
LE GAG DE LA JOURNÉE...

...Consiste à formuler dans un test une condition qui ne pourra jamais être vraie, ou
jamais être fausse. Si ce n’est pas fait exprès, c’est assez rigolo. Si c’est fait exprès,
c’est encore plus drôle, car une condition dont on sait d’avance qu’elle sera toujours
fausse n’est pas une condition. Dans tous les cas, cela veut dire qu’on a écrit un test qui
n’en est pas un, et qui fonctionne comme s’il n’y en avait pas.
Cela peut être par exemple : Si Toto < 10 ET Toto > 15 Alors… (il est très difficile de
trouver un nombre qui soit à la fois inférieur à 10 et supérieur à 15 !)
Bon, ça, c’est un motif immédiat pour payer une tournée générale, et je sens qu’on ne
restera pas longtemps le gosier sec.

KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
 Exercice 3.2
Exercice 3.3

Retour Haut de Page

5. TESTS IMBRIQUÉS
Graphiquement, on peut très facilement représenter un SI comme un aiguillage de
chemin de fer (ou un aiguillage de train électrique, c’est moins lourd à porter). Un SI
ouvre donc deux voies, correspondant à deux traitements différents. Mais il y a des tas de
situations où deux voies ne suffisent pas. Par exemple, un programme devant donner
l’état de l’eau selon sa température doit pouvoir choisir entre trois réponses
possibles (solide, liquide ou gazeuse).
Une première solution serait la suivante :
Variable Temp en Entier
Début
Ecrire "Entrez la température de l’eau :"
Lire Temp
Si Temp =< 0 Alors
Ecrire "C’est de la glace"
FinSi
Si Temp > 0 Et Temp < 100 Alors
Ecrire "C’est du liquide"
Finsi
Si Temp > 100 Alors
Ecrire "C’est de la vapeur"
Finsi
Fin
Vous constaterez que c’est un peu laborieux. Les conditions se ressemblent plus ou
moins, et surtout on oblige la machine à examiner trois tests successifs alors que tous
portent sur une même chose, la température de l'eau (la valeur de la variable Temp). Il
serait ainsi bien plus rationnel d’imbriquer les tests de cette manière :
Variable Temp en Entier
Début
Ecrire "Entrez la température de l’eau :"
Lire Temp
Si Temp =< 0 Alors
Ecrire "C’est de la glace"
Sinon
Si Temp < 100 Alors
Ecrire "C’est du liquide"
Sinon
Ecrire "C’est de la vapeur"
Finsi
Finsi
Fin

KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
 Nous avons fait des économies : au lieu de devoir taper trois conditions, dont une
composée, nous n’avons plus que deux conditions simples. Mais aussi, et surtout, nous
avons fait des économies sur le temps d’exécution de l’ordinateur. Si la température est
inférieure à zéro, celui-ci écrit dorénavant « C’est de la glace » et passe directement à
la fin, sans être ralenti par l’examen d’autres possibilités (qui sont forcément fausses).
Cette deuxième version n’est donc pas seulement plus simple à écrire et plus lisible,
elle est également plus performante à l’exécution.
Les structures de tests imbriqués sont donc un outil indispensable à la simplification et
à l’optimisation des algorithmes.
Exercice 3.4
Exercice 3.5
Exercice 3.6

Retour Haut de Page

6. DE L’AIGUILLAGE À LA GARE DE TRI
« J'ai l'âme ferroviaire : je regarde passer les vaches » (Léo Ferré)
Cette citation n’apporte peut-être pas grand chose à cet exposé, mais je l’aime bien,
alors c’était le moment ou jamais.
En effet, dans un programme, une structure SI peut être facilement comparée à un
aiguillage de train. La voie principale se sépare en deux, le train devant rouler ou sur
l’une, ou sur l’autre, et les deux voies se rejoignant tôt ou tard pour ne plus en former
qu’une seule, lors du FinSi. On peut schématiser cela ainsi :

Mais dans certains cas, ce ne sont pas deux voies qu’il nous faut, mais trois, ou même
plus. Dans le cas de l’état de l’eau, il nous faut trois voies pour notre « train », puisque
l’eau peut être solide, liquide ou gazeuse. Alors, nous n’avons pas eu le choix : pour deux
voies, il nous fallait un aiguillage, pour trois voies il nous en faut deux, imbriqués l’un
dans l’autre.
Cette structure (telle que nous l’avons programmée à la page précédente) devrait être
schématisée comme suit :

KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
 Soyons bien clairs : cette structure est la seule possible du point de vue logique
(même si on peut toujours mettre le bas en haut et le haut en bas). Mais du point de vue
de l’écriture, le pseudo-code algorithmique admet une simplification supplémentaire.
Ainsi, il est possible (mais non obligatoire, que l’algorithme initial :
Variable Temp en Entier
Début
Ecrire "Entrez la température de l’eau :"
Lire Temp
Si Temp =< 0 Alors
Ecrire "C'est de la glace"
Sinon
Si Temp < 100 Alors
Ecrire "C’est du liquide"
Sinon
Ecrire "C’est de la vapeur"
Finsi
Finsi
Fin
devienne :
Variable Temp en Entier
Début
Ecrire "Entrez la température de l’eau :"
Lire Temp
Si Temp =< 0 Alors
Ecrire "C’est de la glace"
SinonSi Temp < 100 Alors
Ecrire "C’est du liquide"
Sinon
Ecrire "C’est de la vapeur"
Finsi
Fin
Dans le cas de tests imbriqués, le Sinon et le Si peuvent être fusionnés en un
SinonSi. On considère alors qu’il s’agit d’un seul bloc de test, conclu par un
seul FinSi
Le SinonSi permet en quelque sorte de créer (en réalité, de simuler) des aiguillages à
plus de deux branches. On peut ainsi enchaîner les SinonSi les uns derrière les autres
pour simuler un aiguillage à autant de branches que l’on souhaite.

KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
 Retour Haut de Page
7. VARIABLES BOOLÉENNES
Jusqu’ici, pour écrire nos des tests, nous avons utilisé uniquement des conditions.
Mais vous vous rappelez qu’il existe un type de variables (les booléennes) susceptibles de
stocker les valeurs VRAI ou FAUX. En fait, on peut donc entrer des conditions dans ces
variables, et tester ensuite la valeur de ces variables.
Reprenons l’exemple de l’eau. On pourrait le réécrire ainsi :
Variable Temp en Entier
Variables A, B en Booléen
Début
Ecrire "Entrez la température de l’eau :"
Lire Temp
A ← Temp =< 0
B ← Temp < 100
Si A Alors
Ecrire "C’est de la glace"
SinonSi B Alors
Ecrire "C’est du liquide"
Sinon
Ecrire "C’est de la vapeur"
Finsi
Fin
A priori, cette technique ne présente guère d’intérêt : on a alourdi plutôt qu’allégé
l’algorithme de départ, en ayant recours à deux variables supplémentaires.
 Mais souvenons-nous : une variable booléenne n’a besoin que d’un seul bit
pour être stockée. De ce point de vue, l’alourdissement n’est donc pas
considérable.
 dans certains cas, notamment celui de conditions composées très lourdes
(avec plein de ET et de OU tout partout) cette technique peut faciliter le travail du
programmeur, en améliorant nettement la lisibilité de l’algorithme. Les variables
booléennes peuvent également s’avérer très utiles pour servir de flag, technique
dont on reparlera plus loin (rassurez-vous, rien à voir avec le flagrant délit des
policiers).

PARTIE 4
ENCORE DE LA LOGIQUE
« La programmation peut être un plaisir ; de même que la cryptographie. Toutefois, il faut éviter de
combiner les deux. » - Kreitzberg et Sneidermann

1. FAUT-IL METTRE UN ET ? FAUT-IL METTRE UN OU ?

KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
 Une remarque pour commencer : dans le cas de conditions composées, les
parenthèses jouent un rôle fondamental.
Variables A, B, C, D, E en Booléen
Variable X en Entier
Début
Lire X
A ← X > 12
B←X>2
C←X<6
D ← (A ET B) OU C
E ← A ET (B OU C)
Ecrire D, E
Fin
Si X = 3, alors on remarque que D sera VRAI alors que E sera FAUX.
S’il n’y a dans une condition que des ET, ou que des OU, en revanche, les parenthèses
ne changent strictement rien.
Dans une condition composée employant à la fois des opérateurs ET et des
opérateurs OU, la présence de parenthèses possède une influence sur le
résultat, tout comme dans le cas d’une expression numérique comportant des
multiplications et des additions.
On en arrive à une autre propriété des ET et des OU, bien plus intéressante.
Spontanément, on pense souvent que ET et OU s’excluent mutuellement, au sens où
un problème donné s’exprime soit avec un ET, soit avec un OU. Pourtant, ce n’est pas si
évident.
Quand faut-il ouvrir la fenêtre de la salle ? Uniquement si les conditions l’imposent, à
savoir :
Si il fait trop chaud ET il ne pleut pas Alors
Ouvrir la fenêtre
Sinon
Fermer la fenêtre
Finsi
Cette petite règle pourrait tout aussi bien être formulée comme suit :
Si il ne fait pas trop chaud OU il pleut Alors
Fermer la fenêtre
Sinon
Ouvrir la fenêtre
Finsi
Ces deux formulations sont strictement équivalentes. Ce qui nous amène à la
conclusion suivante :
Toute structure de test requérant une condition composée faisant intervenir
l’opérateur ET peut être exprimée de manière équivalente avec un opérateur
OU, et réciproquement.
Ceci est moins surprenant qu’il n’y paraît au premier abord. Jetez pour vous en
convaincre un œil sur les tables de vérité, et vous noterez la symétrie entre celle du ET et

KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
celle du OU. Dans les deux tables, il y a trois cas sur quatre qui mènent à un résultat, et
un sur quatre qui mène au résultat inverse. Alors, rien d’étonnant à ce qu’une situation
qui s’exprime avec une des tables (un des opérateurs logiques) puisse tout aussi bien
être exprimée avec l’autre table (l’autre opérateur logique). Toute l’astuce consiste à
savoir effectuer correctement ce passage.
Bien sûr, on ne peut pas se contenter de remplacer purement et simplement les ET par
des OU ; ce serait un peu facile. La règle d’équivalence est la suivante (on peut la vérifier
sur l’exemple de la fenêtre) :
Si A ET B Alors
Instructions 1
Sinon
Instructions 2
Finsi

équivaut à :

Si NON A OU NON B Alors

Instructions 2
Sinon
Instructions 1
Finsi

Cette règle porte le nom de transformation de Morgan, du nom du mathématicien

anglais qui l'a formulée.
Exercice 4.1
Exercice 4.2
Exercice 4.3
Exercice 4.4
Exercice 4.5

Retour Haut de Page

2. AU-DELÀ DE LA LOGIQUE : LE STYLE
Ce titre un peu provocateur (mais néanmoins justifié) a pour but d’attirer maintenant
votre attention sur un fait fondamental en algorithmique, fait que plusieurs remarques
précédentes ont déjà dû vous faire soupçonner : il n’y a jamais une seule manière juste
de traiter les structures alternatives. Et plus généralement, il n’y a jamais une seule
manière juste de traiter un problème. Entre les différentes possibilités, qui ne sont parfois
pas meilleures les unes que les autres, le choix est une affaire de style.
C’est pour cela qu’avec l’habitude, on reconnaît le style d’un programmeur aussi
sûrement que s’il s’agissait de style littéraire.

KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
 Reprenons nos opérateurs de comparaison maintenant familiers, le ET et le OU. En fait,
on s’aperçoit que l’on pourrait tout à fait s’en passer ! Par exemple, pour reprendre
l’exemple de la fenêtre de la salle :
Si il fait trop chaud ET il ne pleut pas Alors
Ouvrir la fenêtre
Sinon
Fermer la fenêtre
Finsi
Possède un parfait équivalent algorithmique sous la forme de :
Si il fait trop chaud Alors
Si il ne pleut pas Alors
Ouvrir la fenêtre
Sinon
Fermer la fenêtre
Finsi
Sinon
Fermer la fenêtre
Finsi
Dans cette dernière formulation, nous n’avons plus recours à une condition composée
(mais au prix d’un test imbriqué supplémentaire)
Et comme tout ce qui s’exprime par un ET peut aussi être exprimé par un OU, nous en
concluons que le OU peut également être remplacé par un test imbriqué supplémentaire.
On peut ainsi poser cette règle stylistique générale :
Dans une structure alternative complexe, les conditions composées,
l’imbrication des structures de tests et l’emploi des variables booléennes
ouvrent la possibilité de choix stylistiques différents. L’alourdissement des
conditions allège les structures de tests et le nombre des booléens nécessaires
; l’emploi de booléens supplémentaires permet d’alléger les conditions et les
structures de tests, et ainsi de suite.
Exercice 4.6
Exercice 4.7
Exercice 4.8
Si vous avez compris ce qui précède, et que l'exercice de la date ne vous pose plus
aucun problème, alors vous savez tout ce qu'il y a à savoir sur les tests pour affronter
n'importe quelle situation. Non, ce n'est pas de la démagogie !
Malheureusement, nous ne sommes pas tout à fait au bout de nos peines ; il reste une
dernière structure logique à examiner, et pas des moindres…

PARTIE 5
LES BOUCLES
KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
« Les premiers 90% du code prennent les premiers 90% du temps de développement. Les 10%
restants prennent les autres 90% du temps de développement » - Tom Cargill

Et ça y est, on y est, on est arrivés, la voilà, c’est Broadway, la quatrième et dernière

structure : ça est les boucles. Si vous voulez épater vos amis, vous pouvez également
parler de structures répétitives, voire carrément de structures itératives. Ca calme,
hein ? Bon, vous faites ce que vous voulez, ici on est entre nous, on parlera de boucles.
Les boucles, c'est généralement le point douloureux de l'apprenti programmeur. C'est
là que ça coince, car autant il est assez facile de comprendre comment fonctionnent les
boucles, autant il est souvent long d'acquérir les réflexes qui permettent de les élaborer
judicieusement pour traiter un problème donné.
On peut dire en fait que les boucles constituent la seule vraie structure logique
caractéristique de la programmation. Si vous avez utilisé un tableur comme Excel, par
exemple, vous avez sans doute pu manier des choses équivalentes aux variables (les
cellules, les formules) et aux tests (la fonction SI…). Mais les boucles, ça, ça n'a aucun
équivalent. Cela n'existe que dans les langages de programmation proprement dits.
Le maniement des boucles, s'il ne différencie certes pas l'homme de la bête (il ne faut
tout de même pas exagérer), est tout de même ce qui sépare en informatique le
programmeur de l'utilisateur, même averti.
Alors, à vos futures – et inévitables - difficultés sur le sujet, il y a trois remèdes : de la
rigueur, de la patience, et encore de la rigueur !

1. A QUOI CELA SERT-IL DONC ?

Prenons le cas d’une saisie au clavier (une lecture), où par exemple, le programme
pose une question à laquelle l’utilisateur doit répondre par O (Oui) ou N (Non). Mais tôt ou
tard, l’utilisateur, facétieux ou maladroit, risque de taper autre chose que la réponse
attendue. Dès lors, le programme peut planter soit par une erreur d’exécution (parce que
le type de réponse ne correspond pas au type de la variable attendu) soit par une erreur
fonctionnelle (il se déroule normalement jusqu’au bout, mais en produisant des résultats
fantaisistes).
Alors, dans tout programme un tant soit peu sérieux, on met en place ce qu’on appelle
un contrôle de saisie, afin de vérifier que les données entrées au clavier correspondent
bien à celles attendues par l’algorithme.
A vue de nez, on pourrait essayer avec un SI. Voyons voir ce que ça donne :
Variable Rep en Caractère
Début
Ecrire "Voulez vous un café ? (O/N)"
Lire Rep
Si Rep <> "O" et Rep <> "N" Alors
Ecrire "Saisie erronnée. Recommencez"
Lire Rep
FinSi
Fin

KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
 C’est impeccable. Du moins tant que l’utilisateur a le bon goût de ne se tromper
qu’une seule fois, et d’entrer une valeur correcte à la deuxième demande. Si l’on veut
également bétonner en cas de deuxième erreur, il faudrait rajouter un SI. Et ainsi de
suite, on peut rajouter des centaines de SI, et écrire un algorithme aussi lourd qu’une
blague des Grosses Têtes, on n’en sortira pas, il y aura toujours moyen qu’un acharné
flanque le programme par terre.
La solution consistant à aligner des SI… en pagaille est donc une impasse. La seule
issue est donc de flanquer une structure de boucle, qui se présente ainsi :
TantQue booléen
…
Instructions
…
FinTantQue
Le principe est simple : le programme arrive sur la ligne du TantQue. Il examine alors
la valeur du booléen (qui, je le rappelle, peut être une variable booléenne ou, plus
fréquemment, une condition). Si cette valeur est VRAI, le programme exécute les
instructions qui suivent, jusqu’à ce qu’il rencontre la ligne FinTantQue. Il retourne ensuite
sur la ligne du TantQue, procède au même examen, et ainsi de suite. Le manège
enchanté ne s’arrête que lorsque le booléen prend la valeur FAUX.
Illustration avec notre problème de contrôle de saisie. Une première approximation de
la solution consiste à écrire :
Variable Rep en Caractère
Début
Ecrire "Voulez vous un café ? (O/N)"
TantQue Rep <> "O" et Rep <> "N"
Lire Rep
FinTantQue
Fin
Là, on a le squelette de l’algorithme correct. Mais de même qu’un squelette ne suffit
pas pour avoir un être vivant viable, il va nous falloir ajouter quelques muscles et organes
sur cet algorithme pour qu’il fonctionne correctement.
Son principal défaut est de provoquer une erreur à chaque exécution. En effet,
l’expression booléenne qui figure après le TantQue interroge la valeur de la variable Rep.
Malheureusement, cette variable, si elle a été déclarée, n’a pas été affectée avant
l’entrée dans la boucle. On teste donc une variable qui n’a pas de valeur, ce qui provoque
une erreur et l’arrêt immédiat de l’exécution. Pour éviter ceci, on n’a pas le choix : il faut
que la variable Rep ait déjà été affectée avant qu’on en arrive au premier tour de boucle.
Pour cela, on peut faire une première lecture de Rep avant la boucle. Dans ce cas, celle-ci
ne servira qu’en cas de mauvaise saisie lors de cette première lecture. L’algorithme
devient alors :
Variable Rep en Caractère
Début
Ecrire "Voulez vous un café ? (O/N)"
Lire Rep

KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
TantQue Rep <> "O" et Rep <> "N"
Lire Rep
FinTantQue
Fin
Une autre possibilité, fréquemment employée, consiste à ne pas lire, mais à affecter
arbitrairement la variable avant la boucle. Arbitrairement ? Pas tout à fait, puisque cette
affectation doit avoir pour résultat de provoquer l’entrée obligatoire dans la boucle.
L’affectation doit donc faire en sorte que le booléen soit mis à VRAI pour déclencher le
premier tour de la boucle. Dans notre exemple, on peut donc affecter Rep avec n’importe
quelle valeur, hormis « O » et « N » : car dans ce cas, l’exécution sauterait la boucle, et
Rep ne serait pas du tout lue au clavier. Cela donnera par exemple :
Variable Rep en Caractère
Début
Rep ← "X"
Ecrire "Voulez vous un café ? (O/N)"
TantQue Rep <> "O" et Rep <> "N"
Lire Rep
FinTantQue
Fin
Cette manière de procéder est à connaître, car elle est employée très fréquemment.
Il faut remarquer que les deux solutions (lecture initiale de Rep en dehors de la boucle
ou affectation de Rep) rendent toutes deux l’algorithme satisfaisant, mais présentent une
différence assez importante dans leur structure logique.
En effet, si l’on choisit d’effectuer une lecture préalable de Rep, la boucle ultérieure
sera exécutée uniquement dans l’hypothèse d’une mauvaise saisie initiale. Si l’utilisateur
saisit une valeur correcte à la première demande de Rep, l’algorithme passera sur la
boucle sans entrer dedans.
En revanche, avec la deuxième solution (celle d’une affectation préalable de Rep),
l’entrée de la boucle est forcée, et l’exécution de celle-ci, au moins une fois, est rendue
obligatoire à chaque exécution du programme. Du point de vue de l’utilisateur, cette
différence est tout à fait mineure ; et à la limite, il ne la remarquera même pas. Mais du
point de vue du programmeur, il importe de bien comprendre que les cheminements des
instructions ne seront pas les mêmes dans un cas et dans l’autre.
Pour terminer, remarquons que nous pourrions peaufiner nos solutions en ajoutant des
affichages de libellés qui font encore un peu défaut. Ainsi, si l’on est un programmeur
zélé, la première solution (celle qui inclut deux lectures de Rep, une en dehors de la
boucle, l’autre à l’intérieur) pourrait devenir :
Variable Rep en Caractère
Début
Ecrire "Voulez vous un café ? (O/N)"
Lire Rep
TantQue Rep <> "O" et Rep <> "N"
Ecrire "Vous devez répondre par O ou N. Recommencez"
Lire Rep

KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
FinTantQue
Ecrire "Saisie acceptée"
Fin
Quant à la deuxième solution, elle pourra devenir :
Variable Rep en Caractère
Début
Rep ← "X"
Ecrire "Voulez vous un café ? (O/N)"
TantQue Rep <> "O" et Rep <> "N"
Lire Rep
Si Rep <> "O" et Rep <> "N" Alors
Ecrire "Saisie Erronée, Recommencez"
FinSi
FinTantQue
Fin
Le Gag De La Journée
C’est d’écrire une structure TantQue dans laquelle le booléen n’est jamais VRAI. Le
programme ne rentre alors jamais dans la superbe boucle sur laquelle vous avez tant sué
!
Mais la faute symétrique est au moins aussi désopilante.
Elle consiste à écrire une boucle dans laquelle le booléen ne devient jamais FAUX.
L’ordinateur tourne alors dans la boucle comme un dératé et n’en sort plus. Seule
solution, quitter le programme avec un démonte-pneu ou un bâton de dynamite. La
« boucle infinie » est une des hantises les plus redoutées des programmeurs. C’est un
peu comme le verre baveur, le poil à gratter ou le bleu de méthylène : c’est éculé, mais
ça fait toujours rire.
Cette faute de programmation grossière – mais fréquente - ne manquera pas d’égayer
l’ambiance collective de cette formation… et accessoirement d’étancher la soif
proverbiale de vos enseignants.
Bon, eh bien vous allez pouvoir faire de chouettes algorithmes, déjà rien qu’avec ça…
Exercice 5.1
Exercice 5.2
Exercice 5.3

Retour Haut de Page

2. BOUCLER EN COMPTANT, OU COMPTER EN BOUCLANT
Dans le dernier exercice, vous avez remarqué qu’une boucle pouvait être utilisée pour
augmenter la valeur d’une variable. Cette utilisation des boucles est très fréquente, et
dans ce cas, il arrive très souvent qu’on ait besoin d’effectuer un nombre déterminé de
passages. Or, a priori, notre structure TantQue ne sait pas à l’avance combien de tours de
boucle elle va effectuer (puisque le nombre de tours dépend de la valeur d’un booléen).
C’est pourquoi une autre structure de boucle est à notre disposition :

KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
Variable Truc en Entier
Début
Truc ← 0
TantQue Truc < 15
Truc ← Truc + 1
Ecrire "Passage numéro : ", Truc
FinTantQue
Fin
Equivaut à :
Variable Truc en Entier
Début
Pour Truc ← 1 à 15
Ecrire "Passage numéro : ", Truc
Truc Suivant
Fin
Insistons : la structure « Pour … Suivant » n’est pas du tout indispensable ; on
pourrait fort bien programmer toutes les situations de boucle uniquement avec un « Tant
Que ». Le seul intérêt du « Pour » est d’épargner un peu de fatigue au programmeur, en
lui évitant de gérer lui-même la progression de la variable qui lui sert de compteur (on
parle d’incrémentation, encore un mot qui fera forte impression sur votre entourage).
Dit d’une autre manière, la structure « Pour … Suivant » est un cas particulier de
TantQue : celui où le programmeur peut dénombrer à l’avance le nombre de tours de
boucles nécessaires.
Il faut noter que dans une structure « Pour … Suivant », la progression du compteur
est laissée à votre libre disposition. Dans la plupart des cas, on a besoin d’une variable
qui augmente de 1 à chaque tour de boucle. On ne précise alors rien à l’instruction
« Pour » ; celle-ci, par défaut, comprend qu’il va falloir procéder à cette incrémentation
de 1 à chaque passage, en commençant par la première valeur et en terminant par la
deuxième.
Mais si vous souhaitez une progression plus spéciale, de 2 en 2, ou de 3 en 3, ou en
arrière, de –1 en –1, ou de –10 en –10, ce n’est pas un problème : il suffira de le préciser à
votre instruction « Pour » en lui rajoutant le mot « Pas » et la valeur de ce pas (Le « pas »
dont nous parlons, c’est le « pas » du marcheur, « step » en anglais).
Naturellement, quand on stipule un pas négatif dans une boucle, la valeur initiale du
compteur doit être supérieure à sa valeur finale si l’on veut que la boucle tourne ! Dans
le cas contraire, on aura simplement écrit une boucle dans laquelle le programme ne
rentrera jamais.
Nous pouvons donc maintenant donner la formulation générale d’une structure
« Pour ». Sa syntaxe générale est :
Pour Compteur ← Initial à Final Pas ValeurDuPas
…
Instructions
…
Compteur suivant

KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
 Les structures TantQue sont employées dans les situations où l’on doit procéder à un
traitement systématique sur les éléments d’un ensemble dont on ne connaît pas
d’avance la quantité, comme par exemple :
 le contrôle d’une saisie
 la gestion des tours d’un jeu (tant que la partie n’est pas finie, on
recommence)
 la lecture des enregistrements d’un fichier de taille inconnue(cf. Partie 9)

Les structures Pour sont employées dans les situations où l’on doit procéder à un
traitement systématique sur les éléments d’un ensemble dont le programmeur connaît
d’avance la quantité.
Nous verrons dans les chapitres suivants des séries d’éléments appelés tableaux
(parties 7 et 8) et chaînes de caractères (partie 9). Selon les cas, le balayage
systématique des éléments de ces séries pourra être effectué par un Pour ou par un
TantQue : tout dépend si la quantité d’éléments à balayer (donc le nombre de tours de
boucles nécessaires) peut être dénombrée à l’avance par le programmeur ou non.

Retour Haut de Page

3. DES BOUCLES DANS DES BOUCLES
(« TOUT EST DANS TOUT... ET RÉCIPROQUEMENT »)
On rigole, on rigole !
De même que les poupées russes contiennent d’autres poupées russes, de même
qu’une structure SI … ALORS peut contenir d’autres structures SI … ALORS, une boucle
peut tout à fait contenir d’autres boucles. Y a pas de raison.
Variables Truc, Trac en Entier
Début
Pour Truc ← 1 à 15
Ecrire "Il est passé par ici"
Pour Trac ← 1 à 6
Ecrire "Il repassera par là"
Trac Suivant
Truc Suivant
Fin
Dans cet exemple, le programme écrira une fois "il est passé par ici" puis six fois de
suite "il repassera par là", et ceci quinze fois en tout. A la fin, il y aura donc eu 15 x 6 =
90 passages dans la deuxième boucle (celle du milieu), donc 90 écritures à l’écran du
message « il repassera par là ». Notez la différence marquante avec cette structure :
Variables Truc, Trac en Entier
Début
Pour Truc ← 1 à 15
Ecrire "Il est passé par ici"
Truc Suivant
Pour Trac ← 1 à 6

KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
 Ecrire "Il repassera par là"
Trac Suivant
Fin
Ici, il y aura quinze écritures consécutives de "il est passé par ici", puis six écritures
consécutives de "il repassera par là", et ce sera tout.
Des boucles peuvent donc être imbriquées (cas n°1) ou successives (cas n°2).
Cependant, elles ne peuvent jamais, au grand jamais, être croisées. Cela n’aurait aucun
sens logique, et de plus, bien peu de langages vous autoriseraient ne serait-ce qu’à écrire
cette structure aberrante.
Variables Truc, Trac en Entier
Pour Truc ← …
instructions
Pour Trac ← …
instructions
Truc Suivant
instructions
Trac Suivant
Pourquoi imbriquer des boucles ? Pour la même raison qu’on imbrique des tests. La
traduction en bon français d’un test, c’est un « cas ». Eh bien un « cas » (par exemple,
« est-ce un homme ou une femme ? ») peut très bien se subdiviser en d’autres cas (« a-t-
il plus ou moins de 18 ans ? »).
De même, une boucle, c’est un traitement systématique, un examen d’une série
d’éléments un par un (par exemple, « prenons tous les employés de l’entreprise un par
un »). Eh bien, on peut imaginer que pour chaque élément ainsi considéré (pour chaque
employé), on doive procéder à un examen systématique d’autre chose (« prenons
chacune des commandes que cet employé a traitées »). Voilà un exemple typique de
boucles imbriquées : on devra programmer une boucle principale (celle qui prend les
employés un par un) et à l’intérieur, une boucle secondaire (celle qui prend les
commandes de cet employé une par une).
Dans la pratique de la programmation, la maîtrise des boucles imbriquées est
nécessaire, même si elle n’est pas suffisante. Tout le contraire d’Alain Delon, en quelque
sorte.

Retour Haut de Page

4. ET ENCORE UNE BÊTISE À NE PAS FAIRE !
Examinons l’algorithme suivant :
Variable Truc en Entier
Début
Pour Truc ← 1 à 15
Truc ← Truc * 2
Ecrire "Passage numéro : ", Truc
Truc Suivant
Fin

KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
 Vous remarquerez que nous faisons ici gérer « en double » la variable Truc, ces deux
gestions étant contradictoires. D’une part, la ligne
Pour…
augmente la valeur de Truc de 1 à chaque passage. D’autre part la ligne
Truc ← Truc * 2
double la valeur de Truc à chaque passage. Il va sans dire que de telles manipulations
perturbent complètement le déroulement normal de la boucle, et sont causes, sinon de
plantages, tout au moins d’exécutions erratiques.
Le Gag De La Journée
Il consiste donc à manipuler, au sein d’une boucle Pour, la variable qui sert de compteur
à cette boucle. Cette technique est à proscrire absolument… sauf bien sûr, si vous
cherchez un prétexte pour régaler tout le monde au bistrot.
Mais dans ce cas, n’ayez aucune inhibition, proposez-le directement, pas besoin de
prétexte.
Exercice 5.4
Exercice 5.5
Exercice 5.6
Exercice 5.7
Exercice 5.8
Exercice 5.9
Exercice 5.10

PARTIE 6
LES TABLEAUX
« Si on ment à un compilateur, il prendra sa revanche. » - Henry Spencer.

Bonne nouvelle ! Je vous avais annoncé qu’il y a avait en tout et pour tout quatre
structures logiques dans la programmation. Eh bien, ça y est, on les a toutes passées en
revue.
Mauvaise nouvelle, il vous reste tout de même quelques petites choses à apprendre…

1. UTILITÉ DES TABLEAUX

Imaginons que dans un programme, nous ayons besoin simultanément de 12 valeurs
(par exemple, des notes pour calculer une moyenne). Evidemment, la seule solution dont
nous disposons à l’heure actuelle consiste à déclarer douze variables, appelées par
exemple Notea, Noteb, Notec, etc. Bien sûr, on peut opter pour une notation un peu
simplifiée, par exemple N1, N2, N3, etc. Mais cela ne change pas fondamentalement
notre problème, car arrivé au calcul, et après une succession de douze instructions
« Lire » distinctes, cela donnera obligatoirement une atrocité du genre :
Moy ← (N1+N2+N3+N4+N5+N6+N7+N8+N9+N10+N11+N12)/12

KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
 Ouf ! C’est tout de même bigrement laborieux. Et pour un peu que nous soyons dans
un programme de gestion avec quelques centaines ou quelques milliers de valeurs à
traiter, alors là c’est le suicide direct.
Cerise sur le gâteau, si en plus on est dans une situation on l’on ne peut pas savoir
d’avance combien il y aura de valeurs à traiter, là on est carrément cuits.
C’est pourquoi la programmation nous permet de rassembler toutes ces variables
en une seule, au sein de laquelle chaque valeur sera désignée par un numéro. En bon
français, cela donnerait donc quelque chose du genre « la note numéro 1 », « la note
numéro 2 », « la note numéro 8 ». C’est largement plus pratique, vous vous en doutez.
Un ensemble de valeurs portant le même nom de variable et repérées par un
nombre, s’appelle un tableau, ou encore une variable indicée.
Le nombre qui, au sein d’un tableau, sert à repérer chaque valeur s’appelle – ô
surprise – l’indice.
Chaque fois que l’on doit désigner un élément du tableau, on fait figurer le nom
du tableau, suivi de l’indice de l’élément, entre parenthèses.

Retour Haut de Page

2. NOTATION ET UTILISATION ALGORITHMIQUE
Dans notre exemple, nous créerons donc un tableau appelé Note. Chaque note
individuelle (chaque élément du tableau Note) sera donc désignée Note(0), Note(1), etc.
Eh oui, attention, les indices des tableaux commencent généralement à 0, et non à 1.
Un tableau doit être déclaré comme tel, en précisant le nombre et le type de valeurs
qu’il contiendra (la déclaration des tableaux est susceptible de varier d'un langage à
l'autre. Certains langages réclament le nombre d'éléments, d'autre le plus grand indice...
C'est donc une affaire de conventions).
En nous calquant sur les choix les plus fréquents dans les langages de
programmations, nous déciderons ici arbitrairement et une bonne fois pour toutes que :
 les "cases" sont numérotées à partir de zéro, autrement dit que le plus
petit indice est zéro.
 lors de la déclaration d'un tableau, on précise la plus grande valeur de
l'indice (différente, donc, du nombre de cases du tableau, puisque si on veut 12
emplacements, le plus grand indice sera 11). Au début, ça déroute, mais vous
verrez, avec le temps, on se fait à tout, même au pire.

Tableau Note(11) en Entier

On peut créer des tableaux contenant des variables de tous types : tableaux de
numériques, bien sûr, mais aussi tableaux de caractères, tableaux de booléens, tableaux
de tout ce qui existe dans un langage donné comme type de variables. Par contre, hormis
dans quelques rares langages, on ne peut pas faire un mixage de types différents de
valeurs au sein d’un même tableau.

KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
 L’énorme avantage des tableaux, c’est qu’on va pouvoir les traiter en faisant des
boucles. Par exemple, pour effectuer notre calcul de moyenne, cela donnera par
exemple :
Tableau Note(11) en Numérique
Variables Moy, Som en Numérique
Début
Pour i ← 0 à 11
Ecrire "Entrez la note n°", i
Lire Note(i)
i Suivant
Som ← 0
Pour i ← 0 à 11
Som ← Som + Note(i)
i Suivant
Moy ← Som / 12
Fin
NB : On a fait deux boucles successives pour plus de lisibilité, mais on aurait tout aussi
bien pu n’en écrire qu’une seule dans laquelle on aurait tout fait d’un seul coup.
Remarque générale : l’indice qui sert à désigner les éléments d’un tableau peut être
exprimé directement comme un nombre en clair, mais il peut être aussi une variable, ou
une expression calculée.
Dans un tableau, la valeur d’un indice doit toujours :
 être égale au moins à 0 (dans quelques rares langages, le premier
élément d’un tableau porte l’indice 1). Mais comme je l'ai déjà écrit plus haut,
nous avons choisi ici de commencer la numérotation des indices à zéro, comme
c’est le cas en langage C et en Visual Basic. Donc attention, Truc(6) est le
septième élément du tableau Truc !
 être un nombre entier Quel que soit le langage, l’élément Truc(3,1416)
n’existe jamais.
 être inférieure ou égale au nombre d’éléments du tableau (moins 1,
si l’on commence la numérotation à zéro). Si le tableau Bidule a été déclaré
comme ayant 25 éléments, la présence dans une ligne, sous une forme ou sous
une autre, de Bidule(32) déclenchera automatiquement une erreur.

Je le re-re-répète, si l’on est dans un langage où les indices commencent à zéro, il faut
en tenir compte à la déclaration :
Tableau Note(13) en Numérique
...créera un tableau de 14 éléments, le plus petit indice étant 0 et le plus grand 13.
LE GAG DE LA JOURNEE
Il consiste à confondre, dans sa tête et / ou dans un algorithme, l’indice d’un élément
d’un tableau avec le contenu de cet élément. La troisième maison de la rue n’a pas
forcément trois habitants, et la vingtième vingt habitants. En notation algorithmique, il
n’y a aucun rapport entre i et truc(i).
Holà, Tavernier, prépare la cervoise !
KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
 Exercice 6.1
Exercice 6.2
Exercice 6.3
Exercice 6.4
Exercice 6.5
Exercice 6.6
Exercice 6.7

Retour Haut de Page

3. TABLEAUX DYNAMIQUES
Il arrive fréquemment que l’on ne connaisse pas à l’avance le nombre d’éléments que
devra comporter un tableau. Bien sûr, une solution consisterait à déclarer un tableau
gigantesque (10 000 éléments, pourquoi pas, au diable les varices) pour être sûr que « ça
rentre ». Mais d’une part, on n’en sera jamais parfaitement sûr, d’autre part, en raison de
l’immensité de la place mémoire réservée – et la plupart du temps non utilisée, c’est un
gâchis préjudiciable à la rapidité, voire à la viabilité, de notre algorithme.
Aussi, pour parer à ce genre de situation, a-t-on la possibilité de déclarer le tableau
sans préciser au départ son nombre d’éléments. Ce n’est que dans un second temps, au
cours du programme, que l’on va fixer ce nombre via une instruction de
redimensionnement : Redim.
Notez que tant qu’on n’a pas précisé le nombre d’éléments d’un tableau,
d’une manière ou d’une autre, ce tableau est inutilisable.
Exemple : on veut faire saisir des notes pour un calcul de moyenne, mais on ne sait
pas combien il y aura de notes à saisir. Le début de l’algorithme sera quelque chose du
genre :
Tableau Notes() en Numérique
Variable nb en Numérique
Début
Ecrire "Combien y a-t-il de notes à saisir ?"
Lire nb
Redim Notes(nb-1)
…
Cette technique n’a rien de sorcier, mais elle fait partie de l’arsenal de base de la
programmation en gestion.
Exercice 6.8
Exercice 6.9
Exercice 6.10
Exercice 6.11
Exercice 6.12

KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
 Exercice 6.13
Exercice 6.14

PARTIE 7
TECHNIQUES RUSEES
« Informatique : alliance d'une science inexacte et d'une activité humaine faillible » - Luc Fayard

Une fois n’est pas coutume, ce chapitre n’a pas pour but de présenter un nouveau
type de données, un nouveau jeu d’instructions, ou que sais-je encore.
Son propos est de détailler quelques techniques de programmation qui possèdent
deux grands points communs :
 leur connaissance est parfaitement indispensable
 elles sont un rien finaudes

Et que valent quelques kilos d’aspirine, comparés à l’ineffable bonheur procuré par la
compréhension suprême des arcanes de l’algorithmique ? Hein ?

1. TRI D’UN TABLEAU : LE TRI PAR INSERTION

Première de ces ruses de sioux, et par ailleurs tarte à la crème absolue du
programmeur, donc : le tri de tableau.
Combien de fois au cours d’une carrière (brillante) de développeur a-t-on besoin de
ranger des valeurs dans un ordre donné ? C’est inimaginable. Aussi, plutôt qu’avoir à
réinventer à chaque fois la roue, le fusil à tirer dans les coins, le fil à couper le roquefort
et la poudre à maquiller, vaut-il mieux avoir assimilé une ou deux techniques solidement
éprouvées, même si elles paraissent un peu ardues au départ.
Il existe plusieurs stratégies possibles pour trier les éléments d’un tableau ; nous en
verrons deux : le tri par insertion, et le tri à bulles. Champagne !
Commençons par le tri par insertion.
Admettons que le but de la manœuvre soit de trier un tableau de 12 éléments dans l’ordre
croissant. La technique du tri par sélection est la suivante : on met en bonne position l’élément
numéro 1, c’est-à-dire le plus petit. Puis en met en bonne position l’élément suivant. Et ainsi
de suite jusqu’au dernier. Par exemple, si l’on part de :

45 122 12 3 21 78 64 53 89 28 84 46

On commence par rechercher, parmi les 12 valeurs, quel est le plus petit élément , et où il
se trouve. On l’identifie en quatrième position (c’est le nombre 3), et on l’échange alors avec
le premier élément (le nombre 45). Le tableau devient ainsi :

KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
 3 122 12 45 21 78 64 53 89 28 84 46

On recommence à chercher le plus petit élément, mais cette fois, seulement à partir
du deuxième (puisque le premier est maintenant correct, on n’y touche plus). On le trouve
en troisième position (c’est le nombre 12). On échange donc le deuxième avec le troisième :

3 12 122 45 21 78 64 53 89 28 84 46

On recommence à chercher le plus petit élément à partir du troisième (puisque les deux
premiers sont maintenant bien placés), et on le place correctement, en l’échangeant, ce qui
donnera in fine :

3 12 21 45 122 78 64 53 89 28 84 46

Et cetera, et cetera, jusqu’à l’avant dernier.

En bon français, nous pourrions décrire le processus de la manière suivante :
 Boucle principale : prenons comme point de départ le premier élément,
puis le second, etc, jusqu’à l’avant dernier.
 Boucle secondaire : à partir de ce point de départ mouvant, recherchons
jusqu’à la fin du tableau quel et le plus petit élément. Une fois que nous l’avons
trouvé, nous l’échangeons avec le point de départ.

Cela s’écrit :
boucle principale : le point de départ se décale à chaque tour
Pour i ← 0 à 10
on considère provisoirement que t(i) est le plus petit élément
posmini ← i
on examine tous les éléments suivants
Pour j ← i + 1 à 11
Si t(j) < t(posmini) Alors
posmini ← j
Finsi
j suivant
A cet endroit, on sait maintenant où est le plus petit élément. Il ne reste plus qu'à effectuer la
permutation.
temp ← t(posmini)
t(posmini) ← t(i)
t(i) ← temp
On a placé correctement l'élément numéro i, on passe à présent au suivant.
i suivant
KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
 Retour Haut de Page

2. UN EXEMPLE DE FLAG : LA RECHERCHE DANS UN TABLEAU

Nous allons maintenant nous intéresser au maniement habile d’une variable
booléenne : la technique dite du « flag ».
Le flag, en anglais, est un petit drapeau, qui va rester baissé aussi longtemps que
l’événement attendu ne se produit pas. Et, aussitôt que cet événement a lieu, le petit
drapeau se lève (la variable booléenne change de valeur). Ainsi, la valeur finale de la
variable booléenne permet au programmeur de savoir si l’événement a eu lieu ou non.
Tout ceci peut vous sembler un peu fumeux, mais cela devrait s’éclairer à l’aide d’un
exemple extrêmement fréquent : la recherche de l’occurrence d’une valeur dans un
tableau. On en profitera au passage pour corriger une erreur particulièrement fréquente
chez le programmeur débutant.
Soit un tableau comportant, disons, 20 valeurs. L’on doit écrire un algorithme
saisissant un nombre au clavier, et qui informe l’utilisateur de la présence ou de
l’absence de la valeur saisie dans le tableau.
La première étape, évidente, consiste à écrire les instructions de lecture / écriture, et
la boucle – car il y en a manifestement une – de parcours du tableau :
Tableau Tab(19) en Numérique
Variable N en Numérique
Début
Ecrire "Entrez la valeur à rechercher"
Lire N
Pour i ← 0 à 19
???
i suivant
Fin
Il nous reste à combler les points d'interrogation de la boucle Pour. Évidemment, il va
falloir comparer N à chaque élément du tableau : si les deux valeurs sont égales, alors
bingo, N fait partie du tableau. Cela va se traduire, bien entendu, par un Si … Alors …
Sinon. Et voilà le programmeur raisonnant hâtivement qui se vautre en écrivant :
Tableau Tab(19) en Numérique
Variable N en Numérique
Début
Ecrire "Entrez la valeur à rechercher"
Lire N
Pour i ← 0 à 19
Si N = Tab(i) Alors
Ecrire "N fait partie du tableau"
Sinon
Ecrire "N ne fait pas partie du tableau"
FinSi

KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
i suivant
Fin
Et patatras, cet algorithme est une véritable catastrophe.
Il suffit d'ailleurs de le faire tourner mentalement pour s'en rendre compte. De deux
choses l'une : ou bien la valeur N figure dans le tableau, ou bien elle n'y figure pas. Mais
dans tous les cas, l'algorithme ne doit produire qu'une seule réponse, quel que
soit le nombre d'éléments que compte le tableau. Or, l'algorithme ci-dessus
envoie à l'écran autant de messages qu'il y a de valeurs dans le tableau, en
l'occurrence pas moins de 20 !
Il y a donc une erreur manifeste de conception : l'écriture du message ne peut se
trouver à l'intérieur de la boucle : elle doit figurer à l'extérieur. On sait si la valeur était
dans le tableau ou non uniquement lorsque le balayage du tableau est
entièrement accompli.
Nous réécrivons donc cet algorithme en plaçant le test après la boucle. Faute de
mieux, on se contentera de faire dépendre pour le moment la réponse d'une variable
booléenne que nous appellerons Trouvé.
Tableau Tab(19) en Numérique
Variable N en Numérique
Début
Ecrire "Entrez la valeur à rechercher"
Lire N
Pour i ← 0 à 19
???
i suivant
Si Trouvé Alors
Ecrire "N fait partie du tableau"
Sinon
Ecrire "N ne fait pas partie du tableau"
FinSi
Fin
Il ne nous reste plus qu'à gérer la variable Trouvé. Ceci se fait en deux étapes.
 un test figurant dans la boucle, indiquant lorsque la variable Trouvé doit
devenir vraie (à savoir, lorsque la valeur N est rencontrée dans le tableau). Et
attention : le test est asymétrique. Il ne comporte pas de "sinon". On reviendra là
dessus dans un instant.
 last, but not least, l'affectation par défaut de la variable Trouvé, dont la
valeur de départ doit être évidemment Faux.

Au total, l'algorithme complet – et juste ! – donne :

Tableau Tab(19) en Numérique
Variable N en Numérique
Début
Ecrire "Entrez la valeur à rechercher"
Lire N
Trouvé ← Faux
KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
Pour i ← 0 à 19
Si N = Tab(i) Alors
Trouvé ← Vrai
FinSi
i suivant
Si Trouvé Alors
Ecrire "N fait partie du tableau"
Sinon
Ecrire "N ne fait pas partie du tableau"
FinSi
Fin
Méditons un peu sur cette affaire.
La difficulté est de comprendre que dans une recherche, le problème ne se formule
pas de la même manière selon qu'on le prend par un bout ou par un autre. On peut
résumer l'affaire ainsi : il suffit que N soit égal à une seule valeur de Tab pour
qu'elle fasse partie du tableau. En revanche, il faut qu'elle soit différente de
toutes les valeurs de Tab pour qu'elle n'en fasse pas partie.
Voilà la raison qui nous oblige à passer par une variable booléenne , un « drapeau »
qui peut se lever, mais jamais se rabaisser. Et cette technique de flag (que nous
pourrions élégamment surnommer « gestion asymétrique de variable booléenne ») doit
être mise en œuvre chaque fois que l’on se trouve devant pareille situation.
Autrement dit, connaître ce type de raisonnement est indispensable, et savoir le
reproduire à bon escient ne l'est pas moins.

Retour Haut de Page

3. TRI DE TABLEAU + FLAG = TRI À BULLES

Et maintenant, nous en arrivons à la formule magique : tri de tableau + flag = tri à
bulles.
L’idée de départ du tri à bulles consiste à se dire qu’un tableau trié en ordre croissant,
c’est un tableau dans lequel tout élément est plus petit que celui qui le suit. Cette
constatation percutante semble digne de M. de Lapalisse, un ancien voisin à moi. Mais
elle est plus profonde – et plus utile - qu’elle n’en a l’air.
En effet, prenons chaque élément d’un tableau, et comparons-le avec l’élément qui le
suit. Si l’ordre n’est pas bon, on permute ces deux éléments. Et on recommence jusqu’à
ce que l’on n’ait plus aucune permutation à effectuer. Les éléments les plus grands
« remontent » ainsi peu à peu vers les dernières places, ce qui explique la charmante
dénomination de « tri à bulle ». Comme quoi l’algorithmique n’exclut pas un minimum
syndical de sens poétique.
En quoi le tri à bulles implique-t-il l’utilisation d’un flag ? Eh bien, par ce qu’on ne sait
jamais par avance combien de remontées de bulles on doit effectuer. En fait, tout ce
qu’on peut dire, c’est qu’on devra effectuer le tri jusqu’à ce qu’il n’y ait plus d’éléments

KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
qui soient mal classés. Ceci est typiquement un cas de question « asymétrique » : il suffit
que deux éléments soient mal classés pour qu’un tableau ne soit pas trié. En revanche, il
faut que tous les éléments soient bien rangés pour que le tableau soit trié.
Nous baptiserons le flag Yapermute, car cette variable booléenne va nous indiquer si
nous venons ou non de procéder à une permutation au cours du dernier balayage du
tableau (dans le cas contraire, c’est signe que le tableau est trié, et donc qu’on peut
arrêter la machine à bulles). La boucle principale sera alors :
Variable Yapermute en Booléen
Début
…
TantQue Yapermute
…
FinTantQue
Fin
Que va-t-on faire à l’intérieur de la boucle ? Prendre les éléments du tableau, du
premier jusqu’à l’avant-dernier, et procéder à un échange si nécessaire. C’est parti :
Variable Yapermute en Booléen
Début
…
TantQue Yapermute
Pour i ← 0 à 10
Si t(i) > t(i+1) Alors
temp ← t(i)
t(i) ← t(i+1)
t(i+1) ← temp
Finsi
i suivant
Fin
Mais il ne faut pas oublier un détail capital : la gestion de notre flag. L’idée, c’est que
cette variable va nous signaler le fait qu’il y a eu au moins une permutation effectuée. Il
faut donc :
 lui attribuer la valeur Vrai dès qu’une seule permutation a été faite (il suffit
qu’il y en ait eu une seule pour qu’on doive tout recommencer encore une fois).
 la remettre à Faux à chaque tour de la boucle principale (quand on
recommence un nouveau tour général de bulles, il n’y a pas encore eu d’éléments
échangés),
 dernier point, il ne faut pas oublier de lancer la boucle principale, et pour
cela de donner la valeur Vrai au flag au tout départ de l’algorithme.

La solution complète donne donc :

Variable Yapermute en Booléen
Début
…
Yapermut ← Vrai
TantQue Yapermut

KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
 Yapermut ← Faux
Pour i ← 0 à 10
Si t(i) > t(i+1) alors
temp ← t(i)
t(i) ← t(i+1)
t(i+1) ← temp
Yapermut ← Vrai
Finsi
i suivant
FinTantQue
Fin
Au risque de me répéter, la compréhension et la maîtrise du principe du flag font
partie de l’arsenal du programmeur bien armé.

Retour Haut de Page

4. LA RECHERCHE DICHOTOMIQUE
Je ne sais pas si on progresse vraiment en algorithmique, mais en tout cas, qu'est-ce
qu'on apprend comme vocabulaire !
Blague dans le coin, nous allons terminer ce chapitre migraineux par une technique
célèbre de recherche, qui révèle toute son utilité lorsque le nombre d'éléments est très
élevé. Par exemple, imaginons que nous ayons un programme qui doive vérifier si un mot
existe dans le dictionnaire. Nous pouvons supposer que le dictionnaire a été
préalablement entré dans un tableau (à raison d'un mot par emplacement). Ceci peut
nous mener à, disons à la louche, 40 000 mots.
Une première manière de vérifier si un mot se trouve dans le dictionnaire consiste à
examiner successivement tous les mots du dictionnaire, du premier au dernier, et à les
comparer avec le mot à vérifier. Ca marche, mais cela risque d'être long : si le mot ne se
trouve pas dans le dictionnaire, le programme ne le saura qu'après 40 000 tours de
boucle ! Et même si le mot figure dans le dictionnaire, la réponse exigera tout de même
en moyenne 20 000 tours de boucle. C'est beaucoup, même pour un ordinateur.
Or, il y a une autre manière de chercher, bien plus intelligente pourrait-on dire, et qui
met à profit le fait que dans un dictionnaire, les mots sont triés par ordre alphabétique.
D'ailleurs, un être humain qui cherche un mot dans le dictionnaire ne lit jamais tous les
mots, du premier au dernier : il utilise lui aussi le fait que les mots sont triés.
Pour une machine, quelle est la manière la plus rationnelle de chercher dans un
dictionnaire ? C'est de comparer le mot à vérifier avec le mot qui se trouve pile poil au
milieu du dictionnaire. Si le mot à vérifier est antérieur dans l'ordre alphabétique, on sait
qu'on devra le chercher dorénavant dans le première moitié du dico. Sinon, on sait
maintenant qu'on devra le chercher dans la deuxième moitié.

KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
 A partir de là, on prend la moitié de dictionnaire qui nous reste, et on recommence : on
compare le mot à chercher avec celui qui se trouve au milieu du morceau de dictionnaire
restant. On écarte la mauvaise moitié, et on recommence, et ainsi de suite.
A force de couper notre dictionnaire en deux, puis encore en deux, etc. on va finir par
se retrouver avec des morceaux qui ne contiennent plus qu'un seul mot. Et si on n'est pas
tombé sur le bon mot à un moment ou à un autre, c'est que le mot à vérifier ne fait pas
partie du dictionnaire.
Regardons ce que cela donne en terme de nombre d'opérations à effectuer, en
choisissant le pire cas : celui où le mot est absent du dictionnaire.
 Au départ, on cherche le mot parmi 40 000.
 Après le test n°1, on ne le cherche plus que parmi 20 000.
 Après le test n°2, on ne le cherche plus que parmi 10 000.
 Après le test n°3, on ne le cherche plus que parmi 5 000.
 etc.
 Après le test n°15, on ne le cherche plus que parmi 2.
 Après le test n°16, on ne le cherche plus que parmi 1.

Et là, on sait que le mot n'existe pas. Moralité : on a obtenu notre réponse en 16
opérations contre 40 000 précédemment ! Il n'y a pas photo sur l'écart de performances
entre la technique barbare et la technique futée. Attention, toutefois, même si c'est
évident, je le répète avec force : la recherche dichotomique ne peut s'effectuer que sur
des éléments préalablement triés.
Eh bien maintenant que je vous ai expliqué comment faire, vous n'avez plus qu'à
traduire !
Au risque de me répéter, la compréhension et la maîtrise du principe du flag font
partie du bagage du programmeur bien outillé.
Exercice 7.1
Exercice 7.2
Exercice 7.3
Exercice 7.4
Exercice 7.5

PARTIE 8
TABLEAUX MULTIDIMENSIONNELS
« Le vrai problème n’est pas de savoir si les machines pensent, mais de savoir si les hommes
pensent » - B.F. Skinner

« La question de savoir si un ordinateur peut penser n'est pas plus intéressante que celle de savoir
si un sous-marin peut nager » - Edgar W. Dijkstra

KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
 Ceci n’est pas un dérèglement de votre téléviseur. Nous contrôlons tout, nous savons
tout, et les phénomènes paranormaux que vous constatez sont dus au fait que vous êtes
passés dans… la quatrième dimension (musique angoissante : « tintintin… »).
Oui, enfin bon, avant d’attaquer la quatrième, on va déjà se coltiner la deuxième.

1. POURQUOI PLUSIEURS DIMENSIONS ?

Une seule ne suffisait-elle pas déjà amplement à notre bonheur, me demanderez-
vous ? Certes, répondrai-je, mais vous allez voir qu’avec deux (et davantage encore) c’est
carrément le nirvana.
Prenons le cas de la modélisation d’un jeu de dames, et du déplacement des pions sur
le damier. Je rappelle qu’un pion qui est sur une case blanche peut se déplacer (pour
simplifier) sur les quatre cases blanches adjacentes.
Avec les outils que nous avons abordés jusque là, le plus simple serait évidemment de
modéliser le damier sous la forme d’un tableau. Chaque case est un emplacement du
tableau, qui contient par exemple 0 si elle est vide, et 1 s’il y a un pion. On attribue
comme indices aux cases les numéros 1 à 8 pour la première ligne, 9 à 16 pour la
deuxième ligne, et ainsi de suite jusqu’à 64.
Arrivés à ce stade, les fines mouches du genre de Cyprien L. m'écriront pour faire
remarquer qu'un damier, cela possède 100 cases et non 64, et qu'entre les damiers et les
échiquiers, je me suis joyeusement emmêlé les pédales. A ces fines mouches, je ferai une
double réponse de prof :
1. C'était pour voir si vous suiviez.

2. Si le prof décide contre toute évidence que les damiers font 64 cases, c'est
le prof qui a raison et l'évidence qui a tort. Rompez.

Reprenons. Un pion placé dans la case numéro i, autrement dit la valeur 1 de Cases(i),
peut bouger vers les cases contiguës en diagonale. Cela va nous obliger à de petites
acrobaties intellectuelles : la case située juste au-dessus de la case numéro i ayant
comme indice i-8, les cases valables sont celles d’indice i-7 et i-9. De même, la case
située juste en dessous ayant comme indice i+8, les cases valables sont celles d’indice
i+7 et i+9.
Bien sûr, on peut fabriquer tout un programme comme cela, mais le moins qu’on
puisse dire est que cela ne facilite pas la clarté de l’algorithme.
Il serait évidemment plus simple de modéliser un damier par… un damier !

Retour Haut de Page

2. TABLEAUX À DEUX DIMENSIONS
L’informatique nous offre la possibilité de déclarer des tableaux dans lesquels les
valeurs ne sont pas repérées par une seule, mais par deux coordonnées.
Un tel tableau se déclare ainsi :
Tableau Cases(7, 7) en Numérique

KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
 Cela veut dire : réserve moi un espace de mémoire pour 8 x 8 entiers, et quand j’aurai
besoin de l’une de ces valeurs, je les repèrerai par deux indices (comme à la bataille
navale, ou Excel, la seule différence étant que pour les coordonnées, on n’utilise pas de
lettres, juste des chiffres).
Pour notre problème de dames, les choses vont sérieusement s’éclaircir. La case qui
contient le pion est dorénavant Cases(i, j). Et les quatre cases disponibles sont Cases(i-1,
j-1), Cases(i-1, j+1), Cases(i+1, j-1) et Cases(i+1, j+1).
REMARQUE ESSENTIELLE :
Il n’y a aucune différence qualitative entre un tableau à deux dimensions ( i, j )
et un tableau à une dimension ( i * j ). De même que le jeu de dames qu’on
vient d’évoquer, tout problème qui peut être modélisé d’une manière peut
aussi être modélisé de l’autre. Simplement, l’une ou l’autre de ces techniques
correspond plus spontanément à tel ou tel problème, et facilite donc (ou
complique, si on a choisi la mauvaise option) l’écriture et la lisibilité de
l’algorithme.
Une autre remarque : une question classique à propos des tableaux à deux dimensions
est de savoir si le premier indice représente les lignes ou le deuxième les colonnes, ou
l’inverse. Je ne répondrai pas à cette question non parce que j’ai décidé de bouder, mais
parce qu’elle n’a aucun sens. « Lignes » et « Colonnes » sont des concepts
graphiques, visuels, qui s’appliquent à des objets du monde réel ; les indices des tableaux
ne sont que des coordonnées logiques, pointant sur des adresses de mémoire vive. Si
cela ne vous convainc pas, pensez à un jeu de bataille navale classique : les lettres
doivent-elles désigner les lignes et les chiffres les colonnes ? Aucune importance !
Chaque joueur peut même choisir une convention différente, aucune importance !
L’essentiel est qu’une fois une convention choisie, un joueur conserve la même tout au
long de la partie, bien entendu.
Exercice 8.1
Exercice 8.2
Exercice 8.3
Exercice 8.4
Exercice 8.5
Exercice 8.6
Exercice 8.7

Retour Haut de Page

3. TABLEAUX À N DIMENSIONS
Si vous avez compris le principe des tableaux à deux dimensions, sur le fond, il n’y a
aucun problème à passer au maniement de tableaux à trois, quatre, ou pourquoi pas neuf
dimensions. C’est exactement la même chose. Si je déclare un tableau Titi(2, 4, 3, 3), il

KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
s’agit d’un espace mémoire contenant 3 x 5 x 4 x 4 = 240 valeurs. Chaque valeur y est
repérée par quatre coordonnées.
Le principal obstacle au maniement systématique de ces tableaux à plus de trois
dimensions est que le programmeur, quand il conçoit son algorithme, aime bien faire des
petits gribouillis, des dessins immondes, imaginer les boucles dans sa tête, etc. Or,
autant il est facile d’imaginer concrètement un tableau à une dimension, autant cela
reste faisable pour deux dimensions, autant cela devient l’apanage d’une minorité
privilégiée pour les tableaux à trois dimensions (je n’en fais malheureusement pas partie)
et hors de portée de tout mortel au-delà. C’est comme ça, l’esprit humain a du mal à se
représenter les choses dans l’espace, et crie grâce dès qu’il saute dans l’hyperespace
(oui, c’est comme ça que ça s’appelle au delà de trois dimensions).
Donc, pour des raisons uniquement pratiques, les tableaux à plus de trois dimensions
sont rarement utilisés par des programmeurs non matheux (car les matheux, de par leur
formation, ont une fâcheuse propension à manier des espaces à n dimensions comme qui
rigole, mais ce sont bien les seuls, et laissons les dans leur coin, c’est pas des gens
comme nous).

PARTIE 9
LES FONCTIONS PRÉDÉFINIES
« Il y a deux méthodes pour écrire des programmes sans erreurs. Mais il n’y a que la troisième qui
marche » - Anonyme

Certains traitements ne peuvent être effectués par un algorithme, aussi savant soit-il.
D’autres ne peuvent l’être qu’au prix de souffrances indicibles.
C’est par exemple le cas du calcul du sinus d’un angle : pour en obtenir une valeur
approchée, il faudrait appliquer une formule d’une complexité à vous glacer le sang.
Aussi, que se passe-t-il sur les petites calculatrices que vous connaissez tous ? On vous
fournit quelques touches spéciales, dites touches de fonctions, qui vous permettent
par exemple de connaître immédiatement ce résultat. Sur votre calculatrice, si vous
voulez connaître le sinus de 35°, vous taperez 35, puis la touche SIN, et vous aurez le
résultat.
Tout langage de programmation propose ainsi un certain nombre de fonctions ;
certaines sont indispensables, car elles permettent d’effectuer des traitements qui
seraient sans elles impossibles. D’autres servent à soulager le programmeur, en lui
épargnant de longs – et pénibles - algorithmes.

1. STRUCTURE GÉNÉRALE DES FONCTIONS

Reprenons l’exemple du sinus. Les langages informatiques, qui se doivent tout de
même de savoir faire la même chose qu’une calculatrice à 19F90, proposent
généralement une fonction SIN. Si nous voulons stocker le sinus de 35 dans la variable A,
nous écrirons :
A ← Sin(35)
Une fonction est donc constituée de trois parties :
KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK
  le nom proprement dit de la fonction. Ce nom ne s’invente pas ! Il doit
impérativement correspondre à une fonction proposée par le langage. Dans notre
exemple, ce nom est SIN.
 deux parenthèses, une ouvrante, une fermante. Ces parenthèses sont
toujours obligatoires, même lorsqu'on n'écrit rien à l'intérieur.
 une liste de valeurs, indispensables à la bonne exécution de la fonction.
Ces valeurs s’appellent des arguments, ou des paramètres. Certaines fonctions
exigent un seul argument, d’autres deux, etc. et d’autres encore aucun. A noter
que même dans le cas de ces fonctions n’exigeant aucun argument, les
parenthèses restent obligatoires. Le nombre d’arguments nécessaire pour une
fonction donnée ne s’invente pas : il est fixé par le langage. Par exemple, la
fonction sinus a besoin d’un argument (ce n’est pas surprenant, cet argument est
la valeur de l’angle). Si vous essayez de l’exécuter en lui donnant deux
arguments, ou aucun, cela déclenchera une erreur à l’exécution. Notez également
que les arguments doivent être d’un certain type, et qu’il faut respecter ces
types.

Et d'entrée, nous trouvons :

LE GAG DE LA JOURNEE
Il consiste à affecter une fonction, quelle qu'elle soit.
Toute écriture plaçant une fonction à gauche d'une instruction d'affectation est
aberrante, pour deux raisons symétriques.
 d'une part, parce que nous le savons depuis le premier chapitre de ce cours
extraordinaire, on ne peut affecter qu'une variable, à l'exclusion de tout autre
chose.
 ensuite, parce qu'une fonction a pour rôle de produire, de renvoyer, de
valoir (tout cela est synonyme), un résultat. Pas d'en recevoir un, donc.

L'affectation d'une fonction sera donc considérée comme l'une des pires fautes
algorithmiques, et punie comme telle.
Tavernier...
Exercice 9.1

KASEREKA KITIKYOLO
Tél : 0990598347
UNILUK