Données, machines, algorithmes, langages

Dénombrer: du comptage au calcul mécanique

1. Ecriture des nombres: (Bordas p9)

mots clés: le statut de nombre, base 10, 2, 16, Leibniz et le binaire

2. Les abaques et le boulier

Comment additionne t-on deux nombres avec un abaque?

Un abaque est le nom donné à tout instrument mécanique plan facilitant le calcul.

Au départ, une opération aussi simple que l’addition demande de la mémoire, d’utiliser les doigts de la main, ou des artefacs (petits cailloux ou des petits jetons en argile) : jusqu’à 3300 ans avant JC, voire plus tard selon les civilisations.

Puis les abaques ont permi d’exploiter la numération de position en base 10 en séparant les unités des dizaines, centaines, et plus, avec des jetons en colonnes.

La colonne la plus à droite étant celle des unités, celle à sa gauche, les dizaines, …

• On dispose les billes dans chaque colonne (centaine à gauche, puis dizaine et unité à gauche). Les nombres à additionner sont écrits sur 2 rangées, l’une sous l’autre.

• On deplace les billes dans l’une des rangées

• On rassemble les billes par 10 lorsqu’il y a un depassement dans l’une des colonnes, et on les remplace par une retenue dans la colonne plus à gauche.

• On peut alors exprimer le résultat: 104 + 17 = 121

• Représenter les étapes de la soustraction de 15 à 103 à l’aide de ce même abaque.

Le boulier

Le boulier est un dispositif mécanique d’aide au calcul. Il est lié au système de numération décimale.

• Représenter les étapes de la multiplication de 6 par 4 avec un boulier à 10 unités.
• Représenter les étapes de la division de 32 par 8 avec ce même boulier.
• Pourquoi l’auteur de la video avance t-il que le disque mécanique est une amélioration importante par rapport aux colonnes droites de billes?
• Quel est le problème qui survient lorsque l’on compte avec le disque numéroté?

3. Circuits électroniques à 2 états

• La numération binaire: Leibnitz (1646-1716) archives ouvertes

Ce manuscrit exceptionnel, écrit par Leibniz à 33 ans mais non publié, fait le lien entre deux de ses travaux majeurs, paraissant a priori indépendants : son idée du calcul binaire et son idée de machine à calculer décimale. Ce manuscrit apparaît à ce jour comme la plus ancienne évocation d’un calculateur binaire.

• Comprendre la frontière entre le matériel et le logiciel: blog couleur-science.eu

Cours: Représentation des entiers positifs

Numération additive

Pour la numération additive, la lecture d’un nombre se fait en additionnant les valeurs de chacun des chiffres-caractères.

Numération de position

La numération de position permet d’écrire un nombre avec les mêmes symboles pour les rangs 0, 1, 2, etc… Le rang zero étant le plus à droite. Le poids d’un chiffre dépend de son rang:

$$Poids = Base^{rang}$$

La numération de position implique d’utiliser un symbole pour le zero.

Base

Une base est un nombre qui permet de décomposer un nombre entier dans une numération de position:

• Base 10:

Le resultat de la conversion en base 2 est la série de valeur obtenues pour les restes. Le dernier reste obtenu est celui de poids le plus fort:

Exemples et visuels

Visuels:

• principe de gestion mecanique de la retenue

• Overflow avec un compteur mécanique

Mémoires

Les différents supports de stokage utilisés pour les ordinateurs modernes sont présentés [ici (wikipedia, mémoires informatiques)(https://fr.wikipedia.org/wiki/M%C3%A9moire_(informatique)#Mat%C3%A9riel_informatique)

Le codage binaire (2 états) se fait à l’aide:

• d’une piste pouvant avoir 2 polarités magnétiques (disque dur, disquette)
• un creux ou une bosse sur un support (DVD, CD-ROM)
• materiaux reflechissant ou non reflechissant (CD-ROM à graver)
• condensateur chargé ou déchargé (mémoire RAM, registres)

Les techniques de stockage mécaniques, par exemple par rubans perforés ont été largement utilisés dès le début de l’informatique, puis abandonnés au profit de supports plus pratiques et plus rapides

TP et outils

Simulateur de circuit électronique en ligne: https://logic.ly/demo/

1. Prise en main du logiciel

Représenter les 3 circuits ci-dessous avec l’editeur logic.ly

Questions: Pour chacun des circuits:

1.a. Le circuit permet-il une interaction avec l’utilisateur?

1.b. Pour chaque circuit: Quels sont les composants utilisés?

1.c. Expliquer le comportement du circuit, pourquoi la lampe s’allume (ou pas)?

Toute fonction logique peut se décomposer en fonctions NON, ET, OU. Les exemples suivants ont pour but de se familiariser avec ces combinaisons de portes logiques, et d’aboutir à la construction d’un ADDITIONNEUR à 2 bits.

2. Simulation d’une porte logique NON

Voici le schéma formel représentant la fonction NON, réalisée à l’aide d’une porte logique NAND (NON ET):

Vous allez adapter ce schéma pour réaliser sur le circuit suivant sur le simulateur:

Les 2 entrées de la portes NAND sont reliées au même interrupteur. L’interrupteur fournit une tension au circuit, à 2 état (Allumé / Eteint).

Une lampe est aussi mise en entrée, sur l’interrupteur, afin de visualiser l’état d’entrée.

2.a. Représenter la table des états pour ce dispositif. S’agit-il de la même table que celle de l’opérateur NON?

La formule logique associée au schéma que vous avez réalisé est:

$$NOT(x) = NAND(x,x)$$

2.b. Commentez cette formule. Identifiez chacun des termes par rapport au circuit.

3. Simulation d’une porte logique ET

Voici le schéma formel représentant la fonction ET, réalisée à partir des portes logiques NOT et NAND:

Réalisez le circuit correspondant sur logic.ly

3.a. Représenter la table des états pour ce dispositif. S’agit-il de la même table que celle de l’opérateur ET?

La formule correspondant à cette association est:

$$AND(x,y) = NOT(NAND(x,y))$$

3.b. Commentez cette formule. Identifiez chacun des termes par rapport au circuit.

4. Porte logique OR

Sachant que: $$NOT(OR(x,y)) = AND(NOT(x),NOT(y))$$

4.a. Construire et représenter le schéma électronique de $AND(NOT(x),NOT(y))$ à partir des portes AND et NOT.

4.b. Ce circuit est-il équivalent à $NOT(OR(x,y))$?

4.c. Conclure: Comment réaliser la fonction $OR(x,y)$ à partir des portes NOT et AND?

5. Additionneur 1 bit

Un additionneur 1 bit est vu comme deux fonctions booléennes s le chiffre des unités et cout la retenue de sortie dépendant de trois entrées:

• 3 entrées : deux bits a et b et une retenue d’entrée cin

• 2 sorties : Le bit de résultat s et une retenue de sortie cout

5.a. Créer un circuit add1 qui implémente l’additionneur 1 bit à partir du schéma ci-dessous

5.b. Compléter la table de vérité des fonctions s et cout

5.c. Expliquez en quoi le circuit suivant est bien un additionneur de 2 bits, avec retenue.

Le TP est inspiré de mathly.fr

autres

• flash-cards
• autre logiciel de simulation electronique en ligne : https://www.lucidchart.com/pages/fr/exemple/logiciel-schema-electrique
• Enoncé original sur: mathly.fr