Exercice 4 — Fonctionnement de la mémoire d'un ordinateur Séries STI, STL, STD

Sujet

Lors de l'exécution d'un programme informatique, un ordinateur a besoin de stocker des données dans sa mémoire. Sous sa forme la plus basique, cette mémoire est accessible via des piles.

Pour comprendre son fonctionnement, nous allons utiliser l'analogie suivante :

• Une donnée (ici, les nombres et les opérateurs + et × ) est représentée par un jeton, marqué de la donnée correspondante.
• Une pile est matérialisée par un empilement de ces jetons.
• Pour accéder à un des jetons de la pile, il faut retirer tous les jetons situés au-dessus.

Les actions possibles sur une pile sont les suivantes:

• Empiler un jeton sur une pile : ajouter un jeton sur le dessus de la pile.
• Dépiler une pile : récupérer le jeton situé sur le dessus de la pile donnée. Ce jeton est alors définitivement perdu.
• Effectuer un transfert d'une pile A vers une pile B : Dépiler la pile A (on récupère donc le jeton situé au-dessus de cette pile) et l'empiler sur la pile B.
• Lire une pile : récupérer la donnée inscrite sur le jeton situé sur le dessus de cette pile (et uniquement celuici). On ne fait que lire cette donnée, le jeton reste en place. C'est la seule action qui retourne un résultat.

Pour définir une pile, plutôt qu'un dessin, nous utiliserons la syntaxe suivante ( \(a_{1}, a_{2}, \ldots, a_{n}\) représentant des jetons quelconques) : \(\left[a_{1}, a_{2}, \ldots, a_{n}\right]\) représente la pile dont les jetons sont, du bas vers le haut : \(a_{1}, a_{2}, \ldots, a_{n}\).

Dans toute la suite, les lettres minuscules représenteront des nombres.

1. Recopier et compléter le tableau cicontre :
2. Une pile \(P_{1}\) contient [ \(a, b, c\) ]. Est-il possible de lire la donnée du jeton \(b\) sans perdre aucun jeton et sans recourir à une autre pile ?
3. Même question, en ayant accès à une deuxième pile \(P_{2}\).

1. Dans cette question, on dispose de trois piles, notées \(P_{1}, P_{2}, P_{3}\). Initialement, \(P_{1}\) contient la pile [ \(a, b\) ] alors que \(P_{2}\) et \(P_{3}\) sont vides. Compléter le tableau suivant:

1. On dispose encore de trois piles \(P_{1}, P_{2}, P_{3}\) telles que \(P_{1}\) contient initialement \([a, b, c]\) et \(P_{2}\) et \(P_{3}\) sont vides. Ecrire une succession d'actions permettant de faire en sorte que \(P_{1}\) contienne \([c, b, a]\) et \(P_{2}, P_{3}\) soient vides.