Vous trouverez ici une description d'un modèle de calcul abstrait, appelé machine ram. Cliquez sur ce lien pour récupérer le mémento en pdf.
Historiquement, les recherches menées autour du concept de calcul ont engendré de nombreux modèles abstraits pour en cerner les contours. Voici les plus importants :
La machine ram, acronyme de Random Access Machine — qu'il est préférable de traduire par Machine à adressage direct ou Register Adressable Memory —, a été introduit pour fournir un outil d'étude des algorithmes plus proche des ordinateurs que ne l'étaient les autres modèles de calcul. C'est un modèle de ce type qui est présenté dans ce cours.
Même si l'écriture d'algorithmes sur la machine ram reste fastidieuse, son langage de programmation s'apparente aux langages d'assemblage beaucoup plus familiers des informaticiens. La description schématique de cette machine est présentée ci-dessous.
0 | ||
1 | ||
2 | ||
3 | ||
4 | ||
5 | ||
6 | ||
7 | ||
8 | ||
9 | ||
10 |
Les 4 éléments constitutifs de ce modèle sont :
Le fonctionnement de la machine est rudimentaire. On charge*le chargement du programme et la saisie des données sont bien entendu virtuel sur ce modèle abstrait au préalable les instructions du programme dans le bloc programme et on saisit* les données à traiter sur la bande d'entrée. Ces données sont encodées sous formes d'entiers naturels suivant un schéma d'encodage et de décodage arbitraires.
Les instructions
Les données à traiter peuvent être chargées dans la mémoire à l'aide de l'instruction de lecture READ et les résultats des calculs sont renvoyés à l'utilisateur sur la bande de sortie à l'aide de l'instruction d'écriture WRITE.
Le modèle présenté ici est moins spartiate que le modèle abstrait originel, il autorise des valeurs positives ou négatives, a un jeu d'opérateurs arithmétiques plus riche ainsi que des instructions de rupture de séquence plus étendu. Il permet de se familiariser plus facilement avec le concept de modèle de calcul abstrait.
Les instructions peuvent être regroupées en 4 groupes distincts selon leur nature :
Pour la compréhension du jeu d'instruction et du fonctionnement de cette machine, nous décrivons symboliquement la bande d'entrée, la bande de sortie et la mémoire respectivement par les listes
L'accumulateur, c'est-à-dire le registre
Les lectures et écritures étant séquentielles, cela signifie qu'un fois une valeur lue sur la bande d'entrée (READ) ou écrite sur la bande de sortie (WRITE), la prochaine opération de lecture ou d'écriture se fera sur la cellule suivante sans retour possible. Dans les tables ci-dessous, l'interprétation d'une instruction est écrite sous une forme algorithmique très commune juste à côté. Par souci de concision, les instructions en tête de groupe sur fond gris servent de modèles pour celles sur fond noir qui suivent et dont seule la première déclinaison est donnée. Par exemple la décrémentation DEC n a pour autre déclinaison DEC @n.
READ | ACC ← x[i++] | copie une valeur de la bande d'entrée dans acc. |
WRITE | y[i++] ← ACC | copie le contenu de acc sur la bande de sortie. |
Chargement de l'accumulateur [load]
LOAD #n | ACC ← n | charge la valeur n dans acc. |
LOAD n | ACC ← R[n] | copie le contenu du registre d'adresse |
LOAD @n | ACC ← R[R[n]] | copie le contenu du registre d'adresse |
Rangement dans les registres [store]
STORE n | R[n] ← ACC | copie le contenu de acc dans le registre d'adresse |
STORE @n | R[R[n]] ← ACC | copie le contenu de acc dans le registre d'adresse |
Incrémentation/Décrémentation [inc|dec]
INC n | R[n] ← R[n] + 1 | incrémente le contenu du registre d'adresse |
INC @n | R[R[n]] ← R[R[n]] + 1 | incrémente le contenu du registre d'adresse |
DEC n | R[n] ← R[n] - 1 | décrémente le contenu du registre d'adresse |
Opérations arithmétiques [add|sub|mul|div|mod]
ADD #n | ACC ← ACC + n | ajoute la valeur |
ADD n | ACC ← ACC + R[n] | ajoute le contenu du registre d'adresse |
ADD @n | ACC ← ACC + R[R[n]] | ajoute le contenu du registre d'adresse |
SUB #n | ACC ← ACC - n | soustrait la valeur |
MUL #n | ACC ← ACC × n | multiplie la valeur |
DIV #n | ACC ← ACC / n | quotiente acc par la valeur |
MOD #n | ACC ← ACC % n | réduit acc modulo la valeur |
Inconditionnelles [jump|stop|nop]
JUMP n | CO ← n | saut à l'instruction |
JUMP @n | CO ← R[n] | saut à l'instruction |
STOP | arrêt du programme. | |
NOP | Instruction nulle. Ne fait rien. |
Conditionnelles [jumz|juml|jumg]
JUMZ n | IF (ACC = 0) CO ← n | saut à l'instruction |
JUMZ @n | IF (ACC = 0) CO ← R[n] | saut à l'instruction |
JUML n | IF (ACC<0) CO ← n | saut à l'instruction |
JUMG n | IF (ACC > 0) CO ← n | saut à l'instruction |
L'instruction NOP qui ne fait rien (no operation) permet, par exemple, en l'intercalant entre certaines instructions du code, de recaler correctement les instructions de saut en cas de modification du code sans avoir à changer les adresses de saut.
La description quasi matérielle de cette machine ne doit pas masquer le fait qu'il s'agit bien d'un modèle formel de la théorie des ensembles.
Dans cette théorie, une machine est confondue avec son programme, à savoir une séquence d'instructions
On peut également décrire formalement le fonctionnement d'une machine ram à travers ses configurations. Une configuration est une sorte de photographie de l'état de la machine, i.e. un septuplet
La configuration initiale de la machine est fixée à
Autrement dit, la machine s'arrête si elle ne change plus de configuration. On peut à présent définir formellement ce qu'est un algorithme :
Le temps de calcul
Ce premier algorithme que vous pouvez charger sur le simulateur, calcule la partie entière de la moyenne arithmétique des valeurs en entrée. Par convention la valeur nulle sert de marqueur pour la fin des données à lire sur la bande d'entrée. Le registre
0 LOAD #0 ; ACC ← 01 STORE 1 ; R[1] ← ACC2 STORE 2 ; R[2] ← ACC3 READ ; ACC ← ENTREE[i++]4 JUMZ 9 ; SI ACC = 0 SAUTER A L'INSTRUCTION #95 ADD 2 ; ACC ← ACC + R[2]6 STORE 2 ; R[2] ← ACC7 INC 1 ; R[1] ← R[1] + 18 JUMP 3 ; SAUTER A L'INSTRUCTION #39 LOAD 2 ; ACC ← R[2]10 DIV 1 ; ACC ← ACC / R[1]11 WRITE ; SORTIE[j++] ← ACC12 STOP ; ARRET
Les instructions #0, #1 et #2 initialisent acc et les registres
L'algorithme suivant cherche la plus grande valeur parmi celles qui sont fournies en entrée. Par convention la valeur nulle sert de marqueur pour la fin des données à lire sur la bande d'entrée. Le registre
0 READ ; ACC ← ENTREE[i++]1 STORE 1 ; R[1] ← ACC2 READ ; ACC ← ENTREE[i++]3 JUMZ 11 ; SI ACC = 0 SAUTER A L'INSTRUCTION #114 STORE 2 ; R[2] ← ACC5 LOAD 1 ; ACC ← R[1]6 SUB 2 ; ACC ← ACC - R[2]7 JUMG 2 ; SI (R[2] - R[1] > 0) SAUTER A L'INSTRUCTION #28 LOAD 2 ; ACC ← R[2]9 STORE 1 ; R[1] ← ACC10 JUMP 2 ; SAUTER A L'INSTRUCTION #211 LOAD 1 ; ACC ← R[1]12 WRITE ; SORTIE[j++] ← ACC13 STOP ; ARRET
Ce troisième algorithme prend en entrée une liste de valeurs et fait remonter la plus grande à la fin de la liste. Une valeur négative sert de balise de fin de lecture. Le principe général est simple, on compare les valeurs contiguës deux-à-deux dans l'ordre de lecture de la liste en les permutant si nécessaire, ainsi à la fin du parcours la plus grande valeur est en fin de liste. Par exemple, si la bande d'entrée contient les valeurs
L'algorithme procède en trois étapes:
0 LOAD #6 ; ACC ← 6 (IDX DU 1ER REGISTRE DE L)1 STORE 4 ; R[4] ← ACC (1ER IDX DE L DANS R[5])2 READ ; ACC ← e[i++] (LECTURE DE LA LISTE)3 STORE @4 ; R[R[4]] ← ACC (R[IDX] ← L[i] POUR IDX = i + 6)4 INC 4 ; R[4] ← R[4] + 1 (IDX ← IDX + 1)5 JUMG 2 ; SI ACC > 0 POURSUIVRE LECTURE DE L6 JUMZ 2 ; SI ACC = 0 POURSUIVRE LECTURE DE L7 LOAD 4 ; ON VA TESTER SI |L|<28 SUB #8 ; ON SOUSTRAIT 89 JUML 28 ; SI |L|<2 => AFFICHER LA LISTE10 LOAD #5 ; ACC ← 5 PREINITIALISATION11 STORE 4 ; R[4] ← 5 DE R[4]12 LOAD #6 ; ACC ← 6 PREINITIALISATION13 STORE 5 ; R[5] ← 6 DE R[5]14 INC 4 ; R[4]++ i ← i + 115 INC 5 ; R[5]++ i + 1 ← i + 216 LOAD @5 ; ACC ← R[5]17 JUML 28 ; L[i]<0 => FIN LISTE => ECRITURE18 SUB @4 ; ACC ← L[i+1] - L[i]19 JUMG 14 ; SI L[i+1] - L[i] > 0 => i++20 JUMZ 14 ; SI L[i+1] - L[i] = 0 => i++21 LOAD @4 ; SINON ACC ← L[i]22 STORE 1 ; R[1] ← L[i]23 LOAD @5 ; ACC ← L[i+1]24 STORE @4 ; L[i] ← L[i+1]25 LOAD 1 ; ACC ← R[1]26 STORE @5 ; L[i+1] ← L[i] ECHANGE L[i] ↔ L[i+1] TERMINE27 JUMP 14 ; ON PASSE AU SUIVANT28 LOAD #6 ; ACC ← 6 (ON CHARGE L'INDEX DU DEBUT DE LA LISTE)29 STORE 4 ; R[4] ← 6 (ON LE RANGE DANS R[4] = IDX)30 LOAD @4 ; ACC ← R[R[4]] (ON CHARGE R[IDX])31 JUML 35 ; SI ACC<0 => FIN DE LISTE ON ARRETE32 WRITE ; SINON ON ECRIT33 INC 4 ; IDX ← IDX + 1 (ELEMENT SUIVANT DE LA LISTE)34 JUMP 30 ; ON RECOMMENCE35 STOP ; FIN DU PROGRAMME
Le simulateur vous permet d'étudier le comportement de la machine ram avec vos programmes. L'intervalle des valeurs autorisées est fixé à
Le fichier à charger doit contenir une instruction du programme par ligne. Chaque instruction peut éventuellement être accompagnée d'un commentaire qui commence par le caractère ;. La bande d'entrée peut être initialisée par la même occasion, si la première ligne du fichier commence par le caractère > suivi d'une liste d'entiers séparés par un espace. Par exemple > -1 12 3 0 1 rangera les entiers
Modifiez l'algorithme précédent de manière à afficher également le nombre de termes qui auront été additionnés (à l'exception de la première valeur nulle rencontrée lors de la lecture de la bande d'entrée).