Déjà plus de
1 million
d'inscrits !
Une machine à calculer : le bit
Déjà plus de
1 million
d'inscrits !
Introduction :
Dans cette première partie, nous répondons à une question qui pourrait paraître simple, mais qui ne l’est pas : qu’est-ce qu’au juste un ordinateur ? Pour le comprendre, nous allons voir les ancêtres successifs des ordinateurs d’aujourd’hui.
Dans ce premier cours, nous remontons aux premières machines à calculer mécaniques, pour comprendre les concepts clés d’algorithme, de donnée et d’instruction. Nous découvrons aussi, avec le concept de bit, les bases de l’algèbre booléenne et du système de numération binaire.
Mathématiques et mécanique
Algorithmes et système décimal
Dès le primaire, on apprend des algorithmes mathématiques : ce sont des méthodes automatiques pour « calculer » des additions, des soustractions, des multiplications et des divisions entières en les posant. On trouve en réalité des algorithmes depuis les débuts de l’histoire des mathématiques, comme l’algorithme d’Euclide, que nous apprenions au collège, pour calculer le plus grand diviseur commun (PGCD) de deux entiers.
Algorithme :
Un algorithme est une séquence d’instructions décrivant de manière précise les étapes de la résolution d’un problème mathématique.
Le mot « algorithme » vient du mathématicien perse Muhammad Al-Khwarizmi, membre de la Maison de la sagesse de Bagdad (IXe siècle), considéré comme le fondateur de l’algèbre. C’est grâce aux travaux d’Al-Khwarizmi qu’ont été popularisés en Europe les chiffres arabes et le système décimal, qui permettent de réaliser les calculs arithmétiques (additions, soustractions, multiplication, divisions entières) vus en primaire.
Système décimal : Le système décimal ou système en base est un système de numération (c’est-à-dire un système pour représenter les nombres) utilisant dix chiffres : , , , , , , , , , .
Observons la représentation d’un nombre en base :
Chaque chiffre, en fonction de sa position, indique le nombre d’unités, de dizaines, de centaines, de milliers :
Ainsi, la position de chaque chiffre correspond à une puissance de dix précise :
Pour rappel : et
Comme nous allons le voir, on peut bâtir sur ce principe des systèmes de numération utilisant n’importe quelle autre valeur entière comme base. Nous verrons plus loin le système binaire (en base ) et, dans le prochain cours, le système hexadécimal (en base ).
Calculs mécaniques
Pendant des siècles, les algorithmes, permettant les opérations mathématiques de base, étaient exécutés à la main par des scribes ou des comptables, parfois avec l’aide d’outils intermédiaires (comme des bouliers) que l’on appelle les abaques.
Mathématiciens en plein calcul. Celui de droite utilise un abaque, celui de gauche pose le calcul à la façon arabe. « Gregor Reisch : Margarita Philosophica, Gregor Reish », 1508, domaine public.
Au XVIIe siècle, avec les progrès de la mécanique et de l’horlogerie, les premières machines à calculer mécaniques apparaissent, permettant un gain de temps et réduisant les risques d’erreur par rapport au calcul manuel.
Programmer des machines
La première machine mécanique programmable n’est pas une machine à calculer, mais un métier à tisser. Les métiers Jacquard, inventés en 1801, lisent des instructions sur des cartons perforés pour réaliser automatiquement les motifs des tapisseries.
C’est à partir de la machine à différence, et en s’inspirant des métiers Jacquard, que Charles Babbage et la mathématicienne Ada Lovelace vont inventer la machine analytique, la toute première machine à calculer programmable, l’ancêtre de l’ordinateur.
Les machines que nous avons vues jusqu’à présent réalisent une certaine séquence d’opérations sur les nombres qu’on leur donne : les additionner, les soustraire, etc. On appelle ces nombres des données.
Ada Lovelace est l’autrice du premier programme informatique : une suite d’instructions destinée à être exécutée sur des données par une machine.
La machine analytique reçoit à la fois des données et des instructions (sur cartes perforées) indiquant quelles opérations doivent être faites sur les données.
Ne pas confondre algorithme et programme, même si ces deux idées sont très proches (ce sont tous les deux des suites d’instructions pour résoudre un problème) :
Le double usage du bit
Les instructions et les données devaient être passées à la machine analytique sous la forme de cartes perforées, comme pour les métiers Jacquard. Les cartes perforées ont été utilisées dans de nombreux contextes depuis pour coder de l’information par la présence ou l’absence de trous (0 ou 1).
Des cartes perforées pour la machine analytique. Devant : les cartes d’instructions, der-rière : les données. « Punched cards for programming the Analytical Engine », Karoly Loren-tey, 1834-71, Science Museum, London, CC-BY 2.0.
« Archivage de cartons de cartes perforées, archivés au service du NARA en 1959. Chaque carton peut contenir 2 000 cartes d'une ligne de 80 colonnes chacune », NARA, 1959, domaine public.
Bit :
Un bit (binary digit) est une unité d’information binaire, ne pouvant prendre que valeurs : ou .
Les cartes perforées seront très utilisées pour stocker de l’information jusque dans les années 1970. Elles sont encore utilisées aujourd’hui pour certains usages spécifiques (machines à voter, péages autoroutiers, etc.).
Même avec l’apparition de nouveaux supports (par exemple magnétiques, optiques ou électroniques) utilisés pour le coder, les ordinateurs utilisent encore aujourd’hui le code binaire (à l’insu de l’utilisateur).
Ada Lovelace, la première, réalise que ce codage binaire permet de représenter et manipuler à la fois des nombres (avec un système en base ) et des concepts logiques (vrai ou faux). C’est ce que nous allons voir dans la suite de ce cours : la deuxième partie est consacrée à la logique binaire, et la troisième partie au système numérique binaire.
Algèbre booléenne
Le mathématicien britannique George Boole (1815-1864) est considéré comme le fondateur de la logique moderne.
Algèbre booléenne :
L’algèbre booléenne (ou algèbre de Boole) est une théorie mathématique qui s’intéresse aux opérations sur les valeurs de vérité (vrai et faux).
En algèbre booléenne :
Lois de base (, , )
L’algèbre de Boole se fonde sur deux opérations et et une transformation .
On utilise les notations suivantes :
Expression booléenne et table de vérité
Expression booléenne :
Une expression booléenne est une expression qui correspond à une valeur booléenne.
Table de vérité :
La table de vérité d’une expression booléenne exprime sa valeur en fonction des valeurs prises par les booléens qui la composent.
Les tables de vérité des opérations de base sont les suivantes :
On veut construire la table de vérité de . Pour s’aider, on peut construire comme intermédiaires la table de vérité de et celle de :
Égalités
Deux expressions booléennes sont égales si elles ont la même table de vérité.
On peut vérifier, en comparant leurs tables de vérités, les égalités suivantes, connues sous le nom du théorème de Morgan :
Il existe d’autres opérateurs booléens, mais ils peuvent tous s’exprimer à partir des trois opérateurs , , .
Deux autres opérateurs sont particulièrement connus :
Coder des nombres en binaire
Entiers en base
Système binaire :
Le système binaire ou système en base est un système de numération utilisant deux chiffres : ou . Chaque chiffre est donc un bit.
Dans le système binaire, chaque bit représente une puissance de (celle correspondant à sa position dans le nombre). La valeur du nombre se calcule en additionnant les puissances de correspondants à chaque bit valant .
Coder en base 2 :
À l’inverse, pour calculer l’expression binaire d’un nombre exprimé en décimal, on suit l’algorithme suivant :
Le bit qui correspond à n’est pas le - ième bit mais le - ième bit !
Exprimer en binaire en base . Nous utilisons successivement la division euclidienne :
Addition binaire
L’algorithme d’addition, utilisé en primaire avec le système décimal, fonctionne également pour le système binaire.
Additionnons et (soit et en décimal).
On pose l’addition :
Le résultat est donc , ce qui correspond bien à en décimal.
En effet,
Conclusion :
Nous savons maintenant faire la distinction entre algorithme et programmation. Nous avons également vu dans ce cours les principaux usages du bit ( ou ) : il peut représenter des concepts logiques, dans le cadre l’algèbre booléenne, ou des nombres entiers dans le cadre du système binaire.
Dans le prochain cours, nous allons voir comment l’on peut représenter en binaire des nombres relatifs ou réels. Puis nous continuerons notre histoire de l’informatique avec l’apparition des premiers ordinateurs électroniques.