Algorithmique et programmation avec exercices corrigés

Préambule : Le Codage

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 !

2. La numérotation de position en base décimale
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.

3. La numérotation de position en base binaire
Les ordinateurs, eux, comme on l’a vu, ont 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.

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. 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.

Introduction a l’Algorithmique

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…

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é ».