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 est basé sur 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 ou opérations 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, un élément quelconque et le dernier
- Un ensemble d’éléments rangés dans une position nommée index
- Un parcours séquentiel permet de trouver chaque élément.
- Un parcours séquentiel débute par la détection de la première position
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 à un élément:
- 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 dans le cas d’une recherche séquentielle. 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)
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
d’accès direct ou indexé
- L’accès à un élément est réalisé grâce à un index indiquant sa position dans l’ensemble.
- 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
Parcours d’un ensemble
il consiste à lire tous les élément d’un ensemble. Pour parcourir tous les éléments d’un ensemble on définit un objet particulier appelé itérateur. Un itérateur permet de parcourir tous les éléments contenus dans un autre objet, le plus souvent une structure de données (file, liste, arbre, etc). On dit qu’un ensemble est itérable lorsqu’il est possible de parcourir ses éléments au moyen d’un itérateur .
En Schema un itérateur de parcours séquentiel se compose de 4 primitives:
- Initialiser: permet l’accès aux éléments
- Enumerer: contrôle le parcours
- Element_Suivant: permet l’accès à un élément dit courant
- Element_Courant : délivre la valeur de élément courant
Accès sequentiel
- Initialiser 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 Enumerer délivre la valeur « FAUX » pour indiquer que la fin de l’ensemble est atteinte. Cette primitive positionne le curseur au début pour préparer l’accès à un élément de l’ensemble. Cette action doit être obligatoirement exécutée pour initier le parcours de l’ensemble.
- Element_Courant est une primitive d’accès à un élément de l’ensemble, ce qui permet de prendre la valeur de la donnée pointée par Element_Suivant.
- Element_Suivant est une primitive permettant de faire avancer vers la position suivante. Son fonctionnement est le suivant:
- Positionner le curseur sur l’élément suivant de l’ensemble.
- Si la fin de l’ensemble est atteinte, la valeur de la primitive Enumerer devient Faux.
- Cette action est définie si et seulement si la primitive Enumerer ou la primitive Element_Courant à été exécutée.
- Enumerer délivre la valeur FAUX si les primitives Element_Courant ou Initialiser ont essayé de lire la marque de fin de l’ensemble. Il délivre VRAI dans tous les autres cas.
Note sur la syntaxe des primitives
En langage Schema les primitives d’accès séquentiel aux éléments d’un ensemble s’écrivent de la façon suivante pour une collection de données nommée ensemble.
- Initialiser ensemble
- element >- Element_Courant ensemble
- Element_Suivant -> ensemble
- Enumerer ensemble
Accès indexé ou direct
- PremierIndex(ensemble) retourne l’index du premier élément d’un ensemble.
- DernierIndex(ensemble) retourne l’index du dernier élément d’un ensemble.
- Accéder à un élément retourne la valeur d’un element marqué par son index ou sa position dans l’ensemble.
AccesIndexé ensemble >- [11 12 16] index <- 1 element <- ensemble[index] Afficher element #element element <- ensemble[2] Afficher element #element Fin
Primitives de création d’un ensemble
Les mots réservés pour la création d’un ensemble File, Liste et []
- File ou [] pour la création d’un ensemble dont la structure est une file séquentielle indexée
- Liste pour la création d’un ensemble dont la structure représente une liste chainée.
Ensemble d'éléments de type Texte: ensemble <- File("1" "2" "3")
ensemble d'éléments de type Entier: ensemble <- [1 2 3]
ensemble d'éléments de type Reel:ensemble <- Liste(1.0 2.6 3.5
Parcours dans un ensemble
Modèle de parcours séquentiel
Parcours_1 ensemble Ensemble
Initialiser -> ensemble
Enumerer -> ensemble
element >- Element_Courant ensemble
Afficher -> element = #element
Element_Suivant -> ensemble
Fin
Fin
Note: l'itération s'arrête lorsque la condition booléenne Enumerer est "Faux"
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
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 nombreElement <- 0 Initialiser ensemble Enumerer ensemble nombreElement <- nombreElement + 1 Element_Suivant ensemble Fin <- nombreElement Fin
copyright A rchitectures A pplicatives A vancées A3-Soft