Manipulation de registres

samedi 1er juin 2019
par  Alain BUSSER

Dans l’article sur Fractran, a été abordé le modèle de calculabilité de Marvin Minsky, ou machine à registres illimités. Dans le présent article, on se propose de décrire des activités où la manipulation permet de saisir le concept de registre de processeur, et au-delà celui de variable (informatique).

Voici comment on peut multiplier deux nombres selon ce modèle :

Par exemple s’il y a initialement 3 graines dans A et 4 graines dans B, il y a à la fin 12 graines dans D.

Au fait c’est quoi un registre ? C’est un contenant nommé, dont la valeur est un entier naturel (sans limite de taille, d’où le nom). Autrement dit c’est une boîte ayant un nom et une valeur entière. Autrement dit un réservoir contenant un nombre entier de graines.

Et que peut-on faire avec un registre ? Semer des graines dedans, ou en prélever. Du moment que c’est l’une après l’autre.

Anciennes ressources

L’expérience a été tentée lors de la semaine des maths et décrite en séminaire, avec cette présentation :

PDF - 161.6 ko

Et voici les fiches présentant divers algorithmes relativement simples mais trop complexes pour une activité de moins d’une heure :

Zip - 317.4 ko

Chaque fiche est suivie, à son verso, du corrigé, et les sources en LaTeX sont inclus pour personnalisation selon les besoins.

Dans cet article, on proposera des activités plus raisonnables que celles déjà tentées, et permettant plus de manipulations afin de mieux appréhender la notion de variable qui est peu maîtrisée en cycle terminal.

On va appeler A, B, C etc les différents registres qui seront idéalement représentés par des boîtes avec les lettres A, B, C etc écrites dessus. Chaque registre contient un nombre entier, représenté par des graines placées dans la boîte. Par exemple si A=8, c’est qu’on a 8 graines dans la boîte A :

A

Subitisation

Pour un être humain normal, il est immédiat de savoir que le registre U contient une graine :

U

Même le registre D, qui contient deux graines, est lui aussi rapidement apprivoisé, on voit tout de suite que D=2 :

D

Il en est d’ailleurs de même pour le registre T :

T

On voit tout de suite (quelques dixièmes de seconde) que T=3.

Mais pour savoir quelle est la valeur du registre S, c’est plus difficile [1] :

S

La théorie de la subitisation dit que, si le nombre de graines dépasse 3, il n’est pas immédiat de savoir quel est ce nombre, il faut pour cela compter les graines. Ce comptage est coûteux en énergie et on va donc autant que possible l’éviter. En fait on va laisser l’utilisateur de la machine de Minsky faire ce travail, et admettre que la machine elle-même ne sait pas compter, elle sait juste ajouter ou enlever un certain nombre de graines comme on le verra ci-dessous.

Le seul nombre de graines que la machine de Minsky sait reconnaître dans un registre, est le nombre zéro que l’on voit ici dans le registre V :

V

De fait, savoir si un registre est vide ou non, revient à calculer un booléen (dont la réponse est seulement oui ou non [2]).

Valeur d’un registre

La relative facilité de Sofus par rapport à d’autres langages de programmation, vient de ce que les affectations classiques sont plus complexes, conceptuellement, que les instructions d’incrémentation et analogues, de Sofus. Une affectation est en effet le résultat de l’injection (on force la valeur d’une variable) d’une valeur dans une variable. Or la valeur vient de l’évaluation (en Python, eval()) d’une expression algébrique. Et si l’expression algébrique comprend un nom de variable, il faut remplacer ce nom par la valeur de la variable. Comment fait-on pour connaître celle-ci ?

Pour un registre, savoir combien de graines il contient, passe par le comptage des graines. C’est long. On évitera dans la suite, autant que possible, ce décompte, et du coup

  • on comptera les graines une première fois, lorsqu’on initialise les registres (si on veut qu’au début, le registre B ait une valeur de 13, il faut mettre 13 graines dans B ; difficile de faire ça sans compter jusqu’à 13) ;
  • on recomptera les graines à la fin, l’algorithme testé ayant pour but de calculer un (ou plusieurs) nombre(s) entier(s), le résultat du calcul s’obtiendra en comptant les graines qui sont dans un (ou plusieurs) registre(s).

Le principe du modèle de Minsky est de faire en sorte qu’on calcule ce qu’on peut en évitant de compter les graines à un stade intermédiaire.

algorithmes

Les algorithmes suivants sont à tester en séquence. Dans chaque cas, il est vivement recommandé de faire les manipulations avec des graines de haricot dans des boîtes.

Les trois blocs suivants sont disponibles :

R est un registre quelconque, on peut remplacer la lettre R par toute autre lettre. Autrement dit

  • on peut toujours ajouter une graine dans un registre (« incrémenter le registre »), quel qu’il soit ;
  • on peut toujours enlever une graine d’un registre (« décrémenter le registre ») non vide, quel qu’il soit ;
  • on peut toujours exécuter des instructions en boucle jusqu’à ce qu’un registre donné soit vide.

Vidange

Que fait cet algorithme ?

Tester avec 4 graines initialement placées dans R.

Une fois compris le principe de l’algorithme, on peut considérer qu’on a une nouvelle instruction, en se contenant de donner un mot (le verbe « vider ») à l’algorithme :

Et on peut admettre dans la suite que l’on ne vide plus un registre graine par graine, mais en versant directement la totalité de son contenu dans le réservoir de graines.

Incréments

Tester sur un registre contenant initialement 2 graines, le premier des deux blocs d’instruction ci-dessous :

On se proposera par la suite de résumer les trois incrémentations par le bloc ci-dessus« augmenter R de 3 ».

Initialisation

Qu’est-ce qui se passe si on ajoute 3 graines à un registre, après avoir vidé celui-ci ?

On dit qu’on a fait une affectation du registre R, par la constante 3. Pour affecter par une variable, il faut savoir comment on peut copier le contenu d’un registre dans un autre.

Transfert

Que fait cet algorithme ?

Tester

  • avec 3 graines dans A et B vide au début. Quel est l’effet final ?
  • avec 3 graines dans A et 5 graines dans B au début. Quel est l’effet final ?

Copie

Quel est l’effet de cet algorithme ?

Remarque : Il est possible de faire la fin d’un seul coup, en vidant toute la boîte C directement dans la boîte A :

On convient d’appeler transférer C dans B l’opération consistant à verser le registre C dans le registre B. Si B n’était pas initialement vide, que se passerait-il après transfert de C dans B ?

Addition

Que fait l’algorithme suivant ?

Tester avec les conditions initiales suivantes :

  • 3 graines initialement dans A et 5 graines initialement dans B
  • 5 graines initialement dans A et 3 graines initialement dans B
  • 3 graines initialement dans A et B initialement vide
  • A initialement vide et 3 graines initialement dans B
  • A et B initialement vides

On convient d’appeler augmenter B de A le résultat de cet algorithme.

Que fait alors l’algorithme suivant ?

Exemples

Le modèle des machines de Minsky est Turing-complet. Cela veut dire, essentiellement, que les opérations sont toutes calculables avec ce modèle. On a déjà vu l’addition et la multiplication par une constante, reste à voir les autres opérations.

Soustraction

Comme on ne modifie pas une différence en décrémentant les deux opérandes, le script suivant devrait pouvoir facilement effectuer une soustraction, par exemple en mettant 13 graines dans A et 8 graines dans B, à la fin il reste 13-8=5 graines dans A et B est vide :

Mais pour que cet algorithme effectue vraiment une soustraction A-B, il faut qu’il y ait plus de graines dans A que dans B : On n’effectue que la soustraction des entiers naturels et elle n’est définie que pour A plus grand que B.

L’algorithme suivant est une amélioration :

Mais il calcule la valeur absolue de la différence :

  • Si A est plus grand que B, A-B se retrouve dans A à la fin, et B est vide.
  • Si B est plus grand que A, B-A se retrouve dans B à la fin, et A est vide.

Dans l’onglet sur l’algorithme d’Euclide, on étudie un prolongement de cet algorithme.

Enfin voici un algorithme correspondant plutôt bien à ce qu’on attend d’une soustraction :

En effet si A contient initialement plus de graines que B, la boucle s’arrête lorsque B est vide, et à ce moment-là, A contient la différence. Si, au contraire, B contient plus de graines que A au début, lorsque A est vide, B continue à se vider et A contient 0, ne pouvant terminer sur un nombre négatif qui serait hors sujet dans le modèle de Minsky.

Comparaison

Cet algorithme est intéressant aussi pour autre chose que la soustraction :

En effet, il met A-B dans A si A>B initialement et B-A dans B si B>A au début, mais aussi il vide le plus petit des registres A et B :

  • Si au début A contient plus de graines que B alors B est vide à la fin ;
  • si au début B contient plus de graines que A alors A est vide à la fin.

Un simple test de vacuité permet donc de savoir lequel des deux nombres était le plus grand au début : C’est celui qui était dans le registre non vide à la fin.

Si les deux registres étaient égaux au début, ils sont vides tous les deux à la fin.

Division par 2

Cet algorithme divise par deux le contenu d’un registre :

Quand l’algorithme a terminé, B contient la moitié de la valeur initiale de A et A contient 0 ou 1 graine selon la parité de cette valeur initiale :

  • B est le quotient euclidien de la valeur initiale par 2
  • A est le reste euclidien de la division de la valeur initiale par 2.

Cette opération est utile pour la formule de Pick et pour la suite de Collatz

Cet algorithme effectue la division euclidienne par 3 :

Là encore le reste est ce qui reste dans A, et le quotient est ce qui a été compté dans B.

De même on peut effectuer la division euclidienne par 4 :

ou par tout autre entier non nul (mais constant : pour la division par une variable voir plus loin)

Multiplication

Une multiplication est une addition itérée :

Les mouvements de graines dans la boucle reviennent à

  • vider B
  • en même temps, copier son contenu initial dans C (« C » comme « copie »)
  • mais aussi ajouter le contenu initial dans D qui contiendra donc finalement A copies du registre B (enfin de sa valeur initiale).

Ensuite, il est donc nécessaire de retransférer C dans B afin de pouvoir effectuer la boucle.

Simuler cet algorithme en manipulant les graines de haricot est une excellente initiation à la programmation, parce qu’on touche un peu à toutes les notions fréquentes en programmation :

  • A est un compteur (par décrémentation) qui permet de répéter les opérations dans la boucle ;
  • D est un accumulateur qui contiendra in fine le produit des valeurs initiales de A et de B ;
  • C sert à contenir une copie de B et simule donc une mémoire ;
  • A et B sont modifiées ; si on veut les rendre non mutables (comme on le fait en programmation fonctionnelle) il faut les copier avant tout dans d’autres registres temporaires et retransférer ceux-ci dans A et B à la fin.

Voici l’algorithme de multiplication, un peu plus détaillé :

Division

La division euclidienne de A par B peut s’effectuer par des soustractions successives :

On suppose qu’initialement A contient plus de graines que B et on veut calculer le quotient (qui vaut donc au moins 1) et le reste dans la division euclidienne de A par B.

D est un compteur qui va compter (c’est son rôle) le nombre de fois qu’on peut soustraire B à A. Ce nombre est le quotient.

Dans la boucle, on soustrait B à A mais en vidant B. Pour récupérer son contenu initial, on en fait donc une copie dans C. Ensuite on retransfère C dans B. Dans le détail cela se fait ainsi :

Que se passe-t-il si B est vide au début ? Qu’en conclure ?

pgcd

L’algorithme d’Euclide permet par soustractions successives d’obtenir le pgcd de deux nombres initialement stockés dans A et dans B :

Le pgcd se trouve finalement dans C, lorsque A et B sont vides tous les deux.

puissances

Comme la multiplication est une addition itérée, Minsky propose d’aller au stade suivant, avec des multiplications itérées, c’est-à-dire une exponentiation. Cela, conjugué à la divisibilité, permet de faire du codage et du décodage de Gödel, et ainsi, de démontrer que le modèle de Minsky est Turing-complet. Ce n’est pas ainsi que Marvin Minsky a prouvé la Turing-complétude : Il a simulé une machine de Turing universelle avec des registres.


[1C’est essentiellement le phénomène évoqué à la page 21 de cet article de 1936 : S’il y a plus de 3 objets à compter cela prend du temps et plus il y a d’objets, plus cela prend du temps de les compter

[2En Python , la fonction bool() transforme tout entier en un booléen, et de fait elle ne donne la valeur False que pour l’entier 0. Du coup le simple fait d’écrire

def est_vide(registre):
    return not(bool(registre))

permet de tester si un registre est vide ou pas.


Commentaires

Annonces

Prochains rendez-vous de l’IREM

Colloque EDIM-IREM

- Mercredi 5 juin 2019, 9h-12h et 14h-17h, salle S23.6, PTU, Saint-Denis.


Brèves

Python au bac 2019

vendredi 31 mai

C’est une brève de MathemaTICE

La question 4b de l’exercice 3 du bac S Amérique du Nord ne pouvait être résolue sans utiliser Python.

Elwyn Berlekamp

jeudi 18 avril

Elwyn Berlekamp, connu des lecteurs de ce site pour son jeu des interrupteurs, était un spécialiste du jeu de Go ainsi que de la Pipopipette, d’Édouard Lucas que Berlekamp admirait énormément.

Notation au bac

lundi 11 décembre 2017

Une nouvelle notation sera pratiquée à partir de la session 2018 pour les algorithmes au bac. Elle est décrite avec de nombreux exemples, ici.

Décès de Roger Mohr

mardi 27 juin 2017

On sait bien que Nicolas Bourbaki n’était pas le nom d’une personne mais le pseudonyme d’un groupe. L’équivalent en informatique théorique est Claude Livercy, auteur de la théorie des programmes. Roger Mohr était un des membres de Claude Livercy.

À travers les labyrinthes : algorithmes et fourmis

dimanche 1er septembre 2013

Quand les chercheurs mettent au point des modèles d’optimisation et de recherche de plus court chemin qui s’inspirent du comportement de masse de colonies de fourmis...
À écouter : Sur les Épaules de Darwin, émission diffusée sur France Inter samedi 31 août 2013.

Rencontres Mondiales du Logiciel Libre à St-Joseph

mardi 20 août 2013

Les RMLLd se dérouleront pour la 2e fois à Saint-Joseph du 22 au 25 août.
C’est une opportunité pour les élèves qui suivent la spécialité ISN et les passionnés d’informatique.

Voici pour le samedi et le dimanche quelques interventions choisies :
- http://2013.d.rmll.info/Raspberry-votre-ordinateur-au-format-carte-de-credit?lang=fr
- http://2013.d.rmll.info/Materiel-libre-et-DIY?lang=fr
- http://2013.d.rmll.info/Arduino-de-l-electronique-libre?lang=fr

Noter aussi les conférences Art et Culture du dimanche, ainsi qu’une conférence plus engagée.

Le programme complet se trouve ici. Une radio sera ouverte pour l’occasion.
Des plaquettes à distribuer se trouvent ici.

Hyper-vidéos pour l’algorithmique au lycée

dimanche 19 août 2012

Olivier Roizès, à la demande de l’ADIREM, a réalisé une collection d’hyper-vidéos de présentation de logiciels et environnements de programmation. Ces hyper-vidéos, c’est-à-dire des vidéos contenant des éléments clicables, devraient être utiles aux enseignants désireux de se familiariser avec Python, CaRMetal, R, Rurple, Scilab ou Xcas.

Ouverture du SILO

mardi 1er novembre 2011

Le SILO (Science Informatique au Lycée : Oui !) est un espace collaboratif documentaire de partage et de formation collégiale, à destination des professeurs appelés à enseigner l’informatique au lycée.

Une initiative du CNDP, de l’INRIA et de Pasc@line, à laquelle se sont associés SPECIF, fuscia, EPI et ePrep.

Sur le Web : Site du SILO

Introduction à la science informatique

lundi 12 septembre 2011

Le CRDP de Paris publie le premier ouvrage destiné aux professeurs chargés d’enseigner la nouvelle spécialité « Informatique et sciences du numérique » en Terminale S à la rentrée 2012. Cet ouvrage a été coordonné par Gilles Dowek, directeur de recherche à l’INRIA.

Sur la création de la spécialité ISN, on pourra également consulter l’interview donnée au Café pédagogique par l’inspecteur général Robert Cabanne.

Sur le Web : CRDP de Paris

Deux publications sur l’algorithmique

samedi 17 octobre 2009

L’IREM d’Aix-Marseille publie une brochure de 73 pages, téléchargeable librement, intitulée Algorithmes et logique au lycée. Ces notions sont illustrées et déclinées sur des exercices du programme de spécialité mathématique en série L, mais sont adaptables aux programmes à venir.

Le hors série thématique n° 37 du magazine Tangente, disponible actuellement en kiosque, s’intitule « Les algorithmes. Au cœur du raisonnement structuré ». Extrait de l’éditorial : « La rédaction de Tangente a conçu la quasi-totalité de ce hors série thématique pour qu’il puisse être lu par des élèves de Seconde ».

Statistiques

Dernière mise à jour

dimanche 16 juin 2019

Publication

841 Articles
Aucun album photo
140 Brèves
11 Sites Web
145 Auteurs

Visites

1621 aujourd'hui
1112 hier
2864158 depuis le début
8 visiteurs actuellement connectés