En programmation , un Type Abstrait définit un type de données et les opérations sur les données de ce type, indépendamment de toute implémentation. C’est la spécification formelle:
- d’un type de données que le programme devra manipuler
- des opérations que l’on devra pouvoir effectuer sur les données de ce type.
Le langage algorithmique Schema définit le type Abstrait Ensemble. Les opérations associées à ce type sont appelées Primitives. C’est la spécification formelle:
- du type des éléments qu’un algorithme devra manipuler
- de l’abstraction des structures de données classiques
- des primitives définies sur un ensemble
la première structure d’information que nous étudierons est la structure d’ensemble séquentiel .
Un ensemble séquentiel est une suite finie d’éléments ayant les caractéristiques suivantes:
- Un ensemble de positions organisé de telle façon que l’on peut distinguer le premier élément, les suivants et le dernier
- Un ensemble d’éléments rangés dans chaque position
- Un parcours séquentiel de tous les éléments permet de trouver la position du dernier élément donc de détecter la dernière place.
- Un parcours séquentiel débute par la détection de la première place
Notion d’accès à une information
Un ensemble est une collection d’éléments rangés suivant un ordre donné. On distingue principalement deux types d’accès
- Accès séquentiel
- Accès direct.
Prenons l’exemple de la recherche d’information dans un parchemin ou dans un dictionnaire. L’accès à une information dans un dictionnaire est directe ou presque puisque principalement réalisée par une recherche dichotomique alors qu’il nous faut dérouler le rouleau de parchemin pour trouver une information se trouvant au bas de celui-ci.
Il faut donc organiser un ensemble en fonction des accès possibles pour rendre, réalisables, les primitives couramment pratiquées sur ces ensembles parmi lesquelles:
- Accès à une élément
- Recherche d’un élément
- Insertion d’un élément
- Suppression d’un élément
- Copie d’une partie d’un ensemble
- Éclatement de l’ensemble en plusieurs sous-ensemble
- Fusion de plusieurs ensemble en un seul
- Tri (ordonner les élément de l’ensemble suivant une relation d’ordre)
Primitives de création d’un ensemble
Le mot réservé File ou [] de Schema représente une file séquentielle indexée, Liste représente une liste chainée.
Ensemble vide:
ensemble <- EnsembleVide
Ensemble File avec éléments de type Texte
ensemble <- File("1" "2" "3")
ensemble File avec éléments de type Entier
ensemble <- [1 2 3]
ensemble liste chainée avec éléments de type Reel
ensemble <- Liste(1.0 2.6 3.5
Accès aux éléments d’un ensemble
Pour donner un modèle de comportement dynamique d’un ensemble, on définit
des primitives d’accès séquentiel:
- Par analogie avec une bande magnétique défilant devant une tête de lecture: On n’a accès à une valeur que lorsque l’élément correspondant est en position de lecture.
- L’élément en position d’être lu est dit élément courant
- Seul l’accès à l’élément courant à un instant donné est possible
- Une file étant une suite finie on introduit une marque qui permet de détecter la fin de cette file
des primitives d’accès direct ou indexé
Pour rendre chaque élément d’un ensemble, accessible par un indice ou index.
Pour un ensemble E de longueur N, l’opération d’indexation notée E(i) délivre la valeur de l’élément d’indice i, à condition que l’ensemble des valeurs de i soit inclus dans l’intervalle [1,N]. L’accès direct permet de rechercher un élément d’un ensemble directement sans avoir à examiner tous les éléments à partir du premier
Primitives d’accès de Schema
Accès sequentiel
- Premier(ensemble) est une action rendant possible l’accès aux éléments de l’ensemble. Cette action positionne le curseur au début de l’ensemble. Si l’ensemble est vide la primitive Dernier délivre la valeur VRAI pour indiquer que la fin de l’ensemble est atteinte. Premier est donc une action rendant possible l’accès aux éléments de l’ensemble. Cette action positionne le curseur au début pour préparer l’accès à la primitive Prendre. Cette action doit être obligatoirement exécutée pour initier le parcours de l’ensemble.
- Prendre(ensemble ) est une primitive d’accès à un élément de l’ensemble, ce qui permet de lire la valeur de la donnée pointée par le curseur. En d’autres termes, elle délivre la valeur de l’élément courant lors du parcours séquentiel. Le premier paramètre est le nom de l’ensemble, elle retourne la valeur de l’élément à la position courante.
- Suivant(ensemble) est une primitive permettant de faire avancer sur la position suivante. Son fonctionnement est le suivant:
- Positionner le curseur sur l’élément suivant de la file.
- Si la fin de file est atteinte, la valeur du prédicat Dernier devient Vrai.
- Cette action est définie si et seulement si la primitive Premier ou la primitive Prendre à été exécutée
- Dernier(ensemble) délivre la valeur VRAI si l’action Prendre ou Premier ont essayé de lire la marque de fin de l’ensemble. Il délivre FAUX dans tous les autres cas. La primitive Dernier est un prédicat qui ne délivre que deux valeurs booléenne VRAI ou FAUX.
- Ranger(ensemble,element) est une primitive d’accès qui permet de ranger un élément dans un ensemble. L’interprétation de cette primitive est la suivante:
- Rangement d’un élément dans l’ensemble à la position courante.
- Cette action est définie si et seulement si la primitive Premier à été exécutée
En résumé
- La primitive Premier permet la lecture des éléments d’un ensemble.
- La primitive Prendre est définie uniquement si la primitive Premier a été exécutée.
- La primitive Dernier délivre VRAI si la fin de l’ensemble est atteinte ou l’ensemble est vide.
- La primitive Suivant permet de marquer la position suivante.
- La primitive Premier assigne VRAI au prédicat Dernier si l’ensemble est vide.
- La primitive Suivant assigne VRAI au prédicat Dernier sei la fin de l’ensemble est atteinte
Ces primitives nous permettent de proposer un modèle général de parcours séquentiel dans un ensemble. Pour visiter tous les éléments d’un ensemble, on prépare la lecture avec la primitive Premier et on répète la primitive Prendre tant que l’on a pas atteint la fin de l’ensemble. Pour détecter la fin de l’ensemble la primitive Dernier délivre la valeur VRAI.
Accès indexé ou direct
- PremierIndex(ensemble) est une action qui retourne l’index du premier élément d’un ensemble.
- DernierIndex(ensemble) est une action qui retourne l’index du dernierr élément d’un ensemble.
L’action de Prendre un élément à une position marqué par son index est réalisée par une instruction d’affectation d’un element indexé de l’ensemble
ensemble >- [11 12 16] index <- 1 element <- ensemble[index] element <- ensemble[2] Afficher element #element
Parcours dans un ensemble
Modèle de parcours séquentiel
Parcours ensemble Ensemble
Premier(ensemble)
NON Dernier(ensemble)
element <- Prendre(ensemble)
Afficher element #element
Suivant(ensemble)
Fin
Fin
Note: la condition de sortie de l’itération est égale à la négation e la condition sur laquelle porte l’itération.
Modèle de parcours indexé
Parcours ensemble Ensemble
index <- PremierIndex(ensemble)
index <= DernierIndex(ensemble)
element <- ensemble[index]
Afficher element #element
index <- index + 1
Fin
Fin
- Action Prendre est: element<- ensemble[index]
- Action Suivant est: index <- index + 1
- Action de contrôle de l’itération est l’expression booléenne index <= DernierIndex(ensemble)
- Action Ranger un élément dans un ensemble à l’index 2: ensemble[2] <- element
Calcul du nombre d’éléments d’un ensemble
L’algorithme de calcul du cardinal d’un ensemble est composé:
- d’un élément en entrée de type Ensemble: ensemble
- du type de élément à retourne: Entier
- de deux instructions d’affectation
- d’une instruction répétitive
- de primitives de parcours de ensemble
Cardinal ensemble Ensemble -> Entier
Premier(ensemble)
nbElement <- 0
NON Dernier(ensemble)
nbElement <- nbElement + 1
Suivant(ensemble)
Fin
<- nombre
Fin
L’algo de test est
test_Cardinal ensemble >- [3 7 9 2] nbElement >- Cardinal(ensemble) Afficher nombre d'éléménts #nbElement Fin
copyright A rchitectures A pplicatives A vancées A3-Soft