Médaille
N°1 pour apprendre & réviser du collège au lycée.
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.

bannière definition

Définition

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.

bannière definition

Définition

Système décimal : Le système décimal ou système en base 1010 est un système de numération (c’est-à-dire un système pour représenter les nombres) utilisant dix chiffres (00, 11, 22, 33, 44, 55, 66, 77, 88, 99).

bannière exemple

Exemple

Observons la représentation d’un nombre en base 1010 : 75187518 Chaque chiffre, en fonction de sa position, indique le nombre d’unités, de dizaines, de centaines, de milliers :
7518=7000+500+10+87518 = 7000 + 500 + 10 + 8 Ainsi, la position de chaque chiffre correspond à une puissance de dix précise : 7518=7×103+5×102+1×101+8×1007518 = 7\times10^3 + 5\times10^2 + 1\times10^1 + 8\times10^0

Pour rappel : a0=1a^0=1 et a1=aa^1=a

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 22) et, dans le prochain cours, le système hexadécimal (en base 1616).

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.

Gregor Reisch, Margarita Philosophica 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.

bannière exemple

Exemple

  • La première machine à réaliser mécaniquement des calculs est inventée par le philosophe français Blaise Pascal en 1642. La pascaline permet de réaliser automatiquement additions et soustractions en faisant tourner des roues crantées.
  • Au XVIIe siècle, le mathématicien britannique Charles Babbage conçoit la machine à différences. Cette gigantesque machine, actionnée par une manivelle, réalise une série d’additions spécifiques permettant de résoudre certaines formes d’équations. La machine à différence n’a jamais été construite du vivant de Babbage, mais un exemplaire en a été construit en 2002.

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.

bannière à retenir

À retenir

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.

bannière attention

Attention

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) :

  • Un algorithme est destiné à être compris par un être humain.
  • Un programme est destiné à être exécuté par une machine. C’est la traduction de l’algorithme en langage machine.

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

cartes perforées, machine analytique 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.

cartes perforées « 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.

bannière definition

Définition

Bit :

Un bit est une unité d’information binaire (valant 00 ou 11).

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

bannière à retenir

À retenir

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

bannière definition

Définition

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, 00 signifie faux et 11 signifie vrai. On appelle ces valeurs des valeurs booléennes ou des booléens.

Lois de base (ET\text{ET}, OU\text{OU}, NON\text{NON})

L’algèbre de Boole se fonde sur deux opérations (ET\text{ET} et OU\text{OU}) et une transformation (NON\text{NON}).

bannière propriete

Propriété

  • Soit un booléen a\text{a}. On appelle non-a\text{non-a} (ou not-a\text{not-a}) la négation de a\text{a} (autrement dit, non-vrai=faux\text{non-vrai} = \text{faux} et non-faux=vrai\text{non-faux} = \text{vrai}).
  • Soient deux booléens a\text{a} et b\text{b}.
  • Le booléen a ET b\text{a ET b} est vrai si et seulement si a\text{a} est vrai et b\text{b} est vrai.
  • Le booléen a OU b\text{a OU b} est vrai si et seulement si a\text{a} est vrai ou b\text{b} est vrai.

On utilise les notations suivantes :

  • not-a\text{not-a} est noté ¬a\neg\text{a} ou aˉ\bar{\text{a}}
  • Selon le contexte, ET\text{ET} est représenté par l’un de ces trois symboles :
  • \land
  • \cdot
  • &\&
  • Selon le contexte, OU\text{OU} est représenté par l’un de ces trois symboles :
  • \lor
  • ++
  • \Vert

Expression booléenne et table de vérité

bannière definition

Définition

Expression booléenne :

Une expression booléenne est une expression qui correspond à une valeur booléenne. En d’autres termes, c’est une phrase qui est soit vraie, soit fausse.

bannière exemple

Exemple

  • « 5<35 < 3 » est une expression booléenne qui vaut faux\text{faux}, car 55 est plus grand que 33.
  • « 77 est un nombre premier » est une expression booléenne qui vaut vrai\text{vrai}.
  • Si a\text{a}, b\text{b} et c\text{c} sont des booléens, alors « a\text{a} ou b\text{b} ou c\text{c} » est un booléen. Sa valeur dépend de celles de a\text{a}, b\text{b} et c\text{c}.
  • « (5<35 < 3) ou (77 est un nombre premier) » est donc un booléen qui vaut vrai\text{vrai}.
bannière definition

Définition

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 :

a\text{a} ¬a\neg\text{a}
00 11
11 00

a\text{a} b\text{b} ab\text{a}\cdot\text{b} a+b\text{a}+\text{b}
00 00 00 00
00 11 00 11
11 00 00 11
11 11 11 11
bannière exemple

Exemple

On veut construire la table de vérité de (a+b)¬c(\text{a}+\text{b})\cdot\neg\text{c}. Pour s’aider, on peut construire comme intermédiaires la table de vérité de a+b\text{a}+\text{b} et celle de ¬c\neg\text{c} :

a\text{a} b\text{b} c\text{c} a+b\text{a}+\text{b} ¬c\neg\text{c} (a+b)¬c(\text{a}+\text{b})\cdot\neg\text{c}
00 00 00 00 11 00
00 00 11 00 00 00
00 11 00 11 11 11
00 11 11 11 00 00
11 00 00 11 11 11
11 00 11 11 00 00
11 11 00 11 11 11
11 11 11 11 00 00

Égalités

bannière propriete

Propriété

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 :

  • Première loi de Morgan : ¬(a+b)=¬a¬b\neg(\text{a}+\text{b})=\neg\text{a}\cdot\neg\text{b}.
  • Deuxième loi de Morgan : ¬(ab)=¬a+¬b\neg(\text{a}\cdot\text{b})=\neg\text{a}+\neg\text{b}.

a\text{a} b\text{b} a+b\text{a}+\text{b} ¬(a+b)\neg(\text{a}+\text{b}) ¬a¬b\neg\text{a}\cdot\neg\text{b} ab\text{a}\cdot\text{b} ¬(ab)\neg(\text{a}\cdot\text{b}) ¬a+¬b\neg\text{a}+\neg\text{b}
00 00 00 11 11 00 11 11
00 11 11 00 00 00 11 11
11 00 11 00 00 00 11 11
11 11 11 00 00 11 00 00
bannière propriete

Propriété

Il existe d’autres opérateurs booléens, mais ils peuvent tous s’exprimer à partir des trois opérateurs non\text{non}, et\text{et}, ou\text{ou}.

Deux autres opérateurs sont particulièrement connus :

  • OU exclusif (XOR\text{XOR}) : a XOR b\text{a XOR b} est vrai si et seulement si une seule valeur parmi a\text{a} et b\text{b} est vraie et que l’autre est fausse. On note :
    a XOR b=(a+b)¬(ab)\text{a XOR b}=(\text{a}+\text{b})\cdot\neg(\text{a}\cdot\text{b})
  • implication : a IMPLIQUE b\text{a IMPLIQUE b} est vrai si b\text{b} est vrai quand a\text{a} est vrai (quand a\text{a} est faux, b\text{b} peut être vrai ou faux). On note :
    a IMPLIQUE b=¬a+b\text{a IMPLIQUE b}=\neg\text{a}+\text{b}

a\text{a} b\text{b} a IMPLIQUE b\text{a IMPLIQUE b}
00 00 11
00 11 11
11 00 00
11 11 11

Coder des nombres en binaire

Entiers en base 22

bannière definition

Définition

Système binaire :

Le système binaire ou système en base 22 est un système de numération utilisant deux chiffres (0,1)(0,1). Chaque chiffre est donc un bit.

Dans le système binaire, chaque bit représente une puissance de 22 (celle correspondant à sa position dans le nombre). La valeur du nombre se calcule en additionnant les puissances de 22 correspondants à chaque bit valant 11.

bannière exemple

Exemple

10111011 code pour :
1×23+1×22+0×21+1×201\times2^3 + 1\times2^2 + 0\times2^1 + 1\times2^0
=8+4+0+1= 8 + 4 + 0 + 1
=13= 13

À l’inverse, pour calculer l’expression binaire d’un nombre xx exprimé en décimal, on suit l’algorithme suivant :

  • chercher la plus grande puissance de 22 plus petite ou égale à xx ;
  • passer le bit correspondant à 11 ;
  • soustraire cette grandeur à xx, puis reprendre du début ;
  • ainsi de suite, jusqu’à ce que x=0x = 0 ;
  • tous les bits qui n’ont pas été passés à 11 sont à 00.
bannière attention

Attention

Le bit qui correspond à 2n2n n’est pas le nn - ième bit mais le (n+1)(n+1) - ième bit !

bannière exemple

Exemple

Exprimer 2727 en binaire :

  • On observe que 24=162^4 = 16 et 25=322^5 = 32. On passe à 11 le cinquième bit.
  • 2716=1127-16 = 11
  • On observe que 23=82^3 = 8 et 24=162^4 = 16. On passe à 11 le quatrième bit.
  • 118=311-8 = 3
  • On observe que 21=22^1 = 2 et 22=42^2 = 4. On passe à 11 le deuxième bit.
  • 32=13-2 = 1
  • On observe que 20=12^0 = 1 et 21=22^1 = 2. On passe à 11 le premier bit.
  • 11=01-1 = 0
  • Le nombre décimal 2727 s’exprime donc par 1101111\,011 en binaire.

Addition binaire

L’algorithme d’addition, utilisé en primaire avec le système décimal, fonctionne également pour le système binaire.

  • On pose l’addition comme en primaire et on additionne les chiffres colonne par colonne.
  • La somme de deux bits vaut toujours 00, 11 ou 22.
  • Si la somme vaut 00 ou 11, on l’inscrit sous la colonne.
  • Si elle vaut 22, on inscrit 00 et on met 11 en retenue.
  • Avec une retenue, il se peut que la somme vaille 33.
  • Si c’est le cas, on inscrit 11 et on met 11 en retenue.
bannière exemple

Exemple

Additionnons 1110011\,100 et 11101110 (soit 2828 et 1414 en décimal).
On pose l’addition :

 \  \ 11 11 11 00 00
++  \  \ 11 11 11 00
==  \  \  \  \  \  \

  • Première colonne :

 \  \ 11 11 11 00 00
++  \  \ 11 11 11 00
==  \  \  \  \  \ 00
  • Deuxième colonne :

 \  \ 11 11 11 00 00
++  \  \ 11 11 11 00
==  \  \  \  \ 11 00
  • Troisième colonne :

 \  \ 11 11 (1)^{(1)} 11 00 00
++  \  \ 11 11 11 00
==  \  \  \ 00 11 00
  • Quatrième colonne :

 \  \ 11 (1)^{(1)} 11 (1)^{(1)} 11 00 00
++  \  \ 11 11 11 00
==  \  \ 11 00 11 00
  • Cinquième colonne :

 \ (1)^{(1)} 11 (1)^{(1)} 11 (1)^{(1)} 11 00 00
++  \  \ 11 11 11 00
== 11 00 11 00 11 00

Le résultat est donc 101010101\,010, ce qui correspond bien à 4242 (28+14)(28+14) en décimal. En effet, 1×25+0×24+1×23+1×21+0×20=421\times{2^5}+0\times{2^4}+1\times{2^3}+1\times{2^1}+0\times{2^0}=42

Conclusion :

Nous savons maintenant faire la distinction entre algorithme et programmation. Nous avons également vu dans ce cours les principaux usages du bit (00 ou 11) : 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.