Le problème d’accès à un élément d’un ensemble, classique en gestion, est formulé habituellement de deux manières:
- Soit on connait la position de l’élément à trouver, on recherche , depuis le début de l’ensemble jusqu’au ixième élément.
- Soit on ne connait pas la position de l’ élément et l’on recherche le premier élément dont la valeur est la valeur donnée.
On distingue donc deux types de recherche dans une file séquentielle:
- Un accès par position
- Un accès par valeur ou associatif
Accès Associatif
On veut parcourir un ensemble depuis le début pour trouver le plus petit index d’une élément dont on cherche une valeur égale à une valeur donnée. Le schéma de programme est un prédicat délivrant Vrai si la valeur choisie appartient à l’ensemble des valeurs de la file, Faux sinon.
Objectif: Recherche par valeur lors d'un parcours séquentiel d'un ensemble d'éléments non triés. Lecture de tous les éléments de l'ensemble Elément: L'élément valeur est de type Element Ensemble L'élément ensemble est de type Ensemble Remarque: L'ensemble n'est pas modifié Résultat: l'algorithme retourne Vrai si le valeur est trouvée Faux sinon
Traductions: Swift, Julia, Python
Recherche avec itèration conditionnelle dans un ensemble non trié:
rechercheParValeur_1 ensemble Ensemble,valeur Element -> Bool existe <- Faux Initialiser(ensemble) Enumerer ensemble ET NON existe element >- Element(ensemble) existe <- Egal(valeur,element) Fin <- existe Fin
L’élément existe indique que l’on a trouvé une valeur correspondant à la condition de recherche. La cohérence du schéma est assurée par l’initialisation de existe à Faux avant le test d’itération. Ceci permet de ne pas entrer dans la boucle itérative si l’ensemble est vide. Par conséquent l’instruction Prendre ne sera exécutée que si la variable existe a la valeur Faux.
Recherche dans le cas d’un ensemble itérable
Dans cette version de recherche d’un élément, la boucle de parcours de l’ensemble est une instruction itérative sur un itérable. Un itérable est une séquence d’éléments que l’on va parcourir sans expression conditionnelle. Le type Ensemble de Schema permet d’écrire une boucle itérative de type itérable de type for .. In .. que l’on retrouve dans le plupart des langages de programmation impératifs. Il s’agit d’une variable d’itération , qui prend successivement la valeur de chacun des éléments de l’itérable.
rechercheParValeur_2 (ensemble Ensemble,valeur Element) -> Bool existe <- Faux ensemble : element Si Egal(valeur,element) existe <- Vrai Sortie Fin Fin <- existe Fin
Si l’on considère une file dont les éléments sont munis d’une relation d’ordre, le schéma ci-dessus peut être optimisé. Les deux principales relation d’ordre couramment utilisées sont représentées par:
- une fonction croissante, l’ensemble est ordonné en ordre croissant
- une fonction décroissante, la file est ordonnée en ordre décroissant
Dans le cas de l’accès associatif la relation d’ordre permet d’éviter un énumération complète des éléments de l’ensemble pour trouver une occurrence de la valeur cherchée.
rechercheParValeur_3 ensemble Ensemble,valeur Element -> Bool existe <- Faux ensemble : element Si valeur < element Sortie Si valeur = element existe <- Vrai Sortie Fin Fin <- existe Fin
Recherche avec boucle infinie
rechercheParValeur_4(ensemble Ensemble,valeur Element) -> Bool existe <- Faux Initialiser(ensemble) Vrai Si Dernier(ensemble) Sortie element >- Element(ensemble) Si valeur < element Sortie Si Egal(valeur,element) existe <- Vrai Sortie Fin Fin <- existe Fin
copyright A rchitectures A pplicatives A vancées A3-Soft