Algorithme -3-

La première structure d’information que nous étudierons est la structure de file séquentielle . Elle introduit la notion d’accès séquentiel à une information. On définira par la suite une file séquentielle de manière abstraite comme un collection de données dans le but de faciliter la conception d’algorithmes. Par conséquent on ne considère pas la représentation concrète de cette structure puisqu’elle dépend des langages de programmation utilisés.

On définit une file séquentielle comme 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
• Un ensemble de positions et d’éléments vides

Définitions Formelles

Une file séquentielle est:

• Un ensemble V dit de valeurs
• Un ensemble P fini de positions

Valeurs & identifiant

L’ensemble V dit ensemble des valeurs peut être composé de valeur simples ou élémentaires(numériques , booléennes ou caractères) ou peuvent se présenter sous forme de valeurs simples ou composées de valeurs simples, accessibles par un identifiant. Par exemple en ensemble de valeurs composées de (nom, numéro de sécurité sociale, numéro de téléphone) est identifié par un identificateur que l’on peut nommer par exemple personne.

Primitives d’accès

Pour donner un modèle de comportement dynamique d’une file ( lecture de tous les éléments) on définit des instructions dites primitives d’accès dont la sémantique est:

• 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
• Un file étant une suite finie on introduit une marque qui permet de détecter la fin de la file

Éléments de langage algorithmique

Pour assurer la cohérence et la validité de l’algorithme de parcours ci-dessus , il nous faut expliciter la sémantique de chaque primitives

Premier (File)

Premier est une action rendant possible l’accès aux éléments de la file. Cette action positionne le curseur au début de la file. Si la file est vide la primitive Dernier délivre la valeur VRAI pour indiquer que la fin de file est atteinte. Premier est donc une action rendant possible l’accès aux éléments de la file. Cette action positionne le curseur au début de la file pour préparer l’accès à la primitive Prendre. Note importante: le curseur pointe sur le premier élement. Son fonctionnement est le suivant:

• Positionner le curseur sur le premier élément de la file.
• Si la file ne contient aucun élément on en déduit que l’on a atteint la fin de la file.
• Cette action doit être obligatoirement exécutée pour initier le parcours d’une file.

Prendre (File,Valeur)

Prendre est une primitive d’accès à une valeur de la file, 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équentielle d’une file. Le premier paramètre est le nom de la file séquentielle, le paramètre Valeur est la variable contenant la donnée de la position courante.

• 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 (File)

Cette primitive délivre la valeur VRAI si l’action Prendre ou Premier ont essayé de lire la marque de fin de file. Il délivre FAUX dans tous les autres cas. La primitive Dernier est dite Prédicat car elle ne délivre que deux valeurs booléenne VRAI ou FAUX.

Ranger (File,Valeur)

Ranger est une primitive d’accès qui permet de ranger une valeur dans une file. à une valeur de la file. L’interprétation de cette primitive est la suivante:

• Rangement de la donnée contenue dans l’emplacement appelé Valeur dans la file à la position du curseur.
• Cette action est définie si et seulement si la primitive Premier à été exécutée

Exemple d’algorithme

Lecture d’une file séquentielle vide : Si Dernier(File) est VRAI après l’exécution de la primitive
Premier, la file séquentielle File est vide

Premier(File)
Dernier(File)

A ce niveau de formalisation nous avons défini toute les notions permettant d’établir la majorité des algorithmes présentés dans la suite d’articles et plus particulièrement l’algorithme de parcours d’une File.

• Instruction
• Valeur
• schéma de séquence d’instruction
• Schéma de choix à une alternative
• Schéma itératif

Schéma de parcours

Afin de visiter tous les éléments d’un file, 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 la file. Pour détecter la fin de la file la primitive Dernier délivre la valeur « Vrai ». Pour modéliser la répétition avec test de fin on utilise le schéma itératif TantQue et l’on en déduit l’algorithme de parcours suivant:

Premier(File)   -- le curseur pointe sur le premier élément s'il existe 
TantQue Non Dernier(File) -- On test la fin de file
Faire
    Prendre(File,Val)     -- On assigne Val avec le valeur courante 
    Avancer(File)         -- On avance d'une position 
Fin-Faire 

En résumé

• La primitive Premier doit être exécutée pour commencer la lecture des éléments d’une file.
• 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 file est atteinte ou si la file set vide.
• La primitive Avancer permet de faire avancer le curseur sur la position suivante.
• La primitive Premier modifie la valeur du prédicat Dernier à VRAI si la file est vide.
• La primitive Avancer modifie la valeur du prédicat Dernier à VRAI si le curseur atteint la fin de file.