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 !

0/2
0 / 10
Challenge tes acquis !
Remporte un max d’étoiles
et de school coins !
`

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 XVIIe 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 22) ;
  • 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) :
  • 00 signifie faux ;
  • 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}) :
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.
  • 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 : a+b=aˉbˉ\overline{\text{a}+\text{b}}=\bar{\text{a}}\cdot\bar{\text{b}}
  • Deuxième loi de Morgan : ab=aˉ+bˉ\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 non\text{non}, et\text{et}, ou\text{ou}.
  • Deux autres opérateurs sont particulièrement connus :
  • OU exclusif (XOR\text{XOR}), on note :a XOR b=(a+b)ab\text{a XOR b}=(\text{a}+\text{b})\cdot\overline{\text{a}\cdot\text{b}}
  • implication, on note : a IMPLIQUE b=aˉ+b\text{a IMPLIQUE b}=\bar{\text{a}}+\text{b}

Coder des nombres en binaire

Entiers en base 22

  • 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.
  • À l’inverse, pour calculer l’expression binaire d’un nombre xx exprimé en décimal, il faut suivre un l’algorithme spécifique.
  • Le bit qui correspond à 2n2n n’est pas le nn-ième bit mais le (n+1)(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 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.