Fiche de révision : Une machine à calculer : le bit

Mathématiques et mécanique

• Le mot « algorithme » vient du mathématicien Muhammad Al-Khwarizmi, fondateur de l’algèbre. C’est grâce à ces travaux que les chiffres arabes et le système décimal sont arrivés en Europe.
• La première machine à réaliser mécaniquement des calculs est inventée par Blaise Pascal en 1642 : la pascaline.
• Au XVII^e siècle, le mathématicien Charles Babbage conçoit la machine à différences.
• 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.
• Ada Lovelace est l’autrice du premier programme informatique.
• La machine analytique reçoit à la fois des données et des instructions indiquant quelles opérations doivent être faites sur les données.
• Les ordinateurs utilisent encore aujourd’hui le code binaire (à l’insu de l’utilisateur).
• Ada Lovelace réalise que ce codage binaire permet de représenter et manipuler à la fois :
• des nombres (avec un système en base $2$) ;
• des concepts logiques (vrai ou faux).

Algèbre booléenne

• L’algèbre booléenne est une théorie mathématique qui s’intéresse aux opérations sur les valeurs de vérité (vrai et faux) :
• $0$ signifie faux ;
• $1$ signifie vrai.
• On appelle ces valeurs des valeurs booléennes ou des booléens.
• Lois de base ($\text{ET}$, $\text{OU}$, $\text{NON}$) :

Propriété

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

• Une expression booléenne est une phrase qui est soit vraie, soit fausse.
• 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.
• Égalités : deux expressions booléennes sont égales si elles ont la même table de vérité.
• Les égalités du théorème de Morgan :
• Première loi de Morgan : $\overline{\text{a}+\text{b}}=\bar{\text{a}}\cdot\bar{\text{b}}$
• Deuxième loi de Morgan : $\overline{\text{a}\cdot\text{b}}=\bar{\text{a}}+\bar{\text{b}}$
• Il existe d’autres opérateurs booléens, mais ils peuvent tous s’exprimer à partir des trois opérateurs $\text{non}$, $\text{et}$, $\text{ou}$.
• Deux autres opérateurs sont particulièrement connus :
• OU exclusif ($\text{XOR}$), on note :$$\text{a XOR b}=(\text{a}+\text{b})\cdot\overline{\text{a}\cdot\text{b}}$$
• implication, on note : $$\text{a IMPLIQUE b}=\bar{\text{a}}+\text{b}$$

Coder des nombres en binaire

Entiers en base $2$

• Dans le système binaire, chaque bit représente une puissance de $2$ (celle correspondant à sa position dans le nombre).
• La valeur du nombre se calcule en additionnant les puissances de $2$ correspondants à chaque bit valant $1$.
• À l’inverse, pour calculer l’expression binaire d’un nombre $x$ exprimé en décimal, il faut suivre un l’algorithme spécifique.
• Le bit qui correspond à $2n$ n’est pas le $n$-ième bit mais le $(n+1)$-ième bit.

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 $0$, $1$ ou $2$.
• Si la somme vaut $0$ ou $1$, on l’inscrit sous la colonne.
• Si elle vaut $2$, on inscrit $0$ et on met $1$ en retenue.
• Avec une retenue, il se peut que la somme vaille $3$.
• Si c’est le cas, on inscrit $1$ et on met $1$ en retenue.