La seule structure d’information nécessaire et suffisante utilisée pour élaborer la plupart des algorithmes écrits en Schema est le type abstrait Ensemble. Les primitives d’accès séquentiel ou indexé vues précédemment nous permettent de construire tous les styles de parcours d’un ensemble.
Parcours séquentiel
Le moyen le plus simple pour réaliser le parcours d’un ensemble est de mettre en œuvre l’itération conditionnelle qui est généralement implémentée dans un langages de programmation par l’instruction while suivie par une expression booléenne.
Modèle programmatique de parcours
while expression booléenne instructions
Modèle algorithmique de parcours
expression booléenne instructions Fin
L’algorithme de parcours séquentiel d’un ensemble , étudié précédemment:
- Premier: Initialise la lecture au début de la file
- Prendre: Lit l’élément courant
- Dernier: Signale la fin de la lecture
- Suivant: Déplace le curseur d’une position
Ces primitives ont été définie pour rendre simple, générale et implémentable la définition d’un algorithme de parcours séquentiel. Ce modèle d’algorithme de parcours pourra être traduit dans tous les langages de programmation impérative.
Description Objectif: Présenter un algorithme générique de parcours séquentiel Résultat: Énumération de tous les éléments de l'ensemble Remarque: L'ensemble n'est pas modifiée Algoritme Parcours ensemble >- [10 20 40] Premier(ensemble) NON Dernier(ensemble) element >- Prendre(ensemble) Afficher element #element Suivant(ensemble) Fin Fin
Traduction Swift
func Parcours() { let ensemble = File(10,20,40) Premier(ensemble) while !Dernier(ensemble) { let element = Prendre(ensemble) print("element \(element)") Suivant(ensemble) } }
Parcours indexé
Les deux seule primitives nécessaires pour construire le parcours d’un ensemble sont:
- PremierIndex(ensemble)
- DernierIndex(ensemble)
D’un point de vue purement algorithmique il n’y a pas de différence entre un parcours séquentiel pour un ensemble à accès indexé ou séquentiel. Le niveau d’abstraction de la représentation algorithmique nous permet de modéliser un parcours séquentiel ou indexé de la même façon car les changements de comportement sont implémentés dans les primitives d’accès.
- Chaque élément de l’ensemble est accessible par un indice ou index.
- On peut rechercher un élément sans avoir à examiner tous les élément à partir du premier grâce à l’accès direct ce qui n’est pas possible avec un structure d’ensemble séquentiel.
Pour énumérer les éléments d’un ensemble à accès direct on peut réutiliser le schéma d’algorithme précédent à condition de redéfinir les primitives d’accès suivantes:
- Premier: Initialise l’index avec la valeur du premier index
- Prendre: Lit l’élément courant ensemble[index ]
- Dernier: Signale la fin de la lecture quand la valeur de l’index est supérieure au nombre d’éléments de l’ensemble
- Suivant: Ajoute 1 à l’index courant
Pour mieux appréhender ce qui se passe lors d’un parcours séquentiel d’un vecteur, écrivons le schéma qui va nous permettre d’expliciter la sémantique des primitives d’accès.
Algorithme Parcours index <- PremierIndex(ensemble) index <= DernierIndex(ensemble) element >- ensemble[index] Afficher element #element index <- index + 1 Fin Fin
Traduction Swift
func Parcours() { let ensemble = File(10,20,40) var index = PremierIndex(ensemble) while index <= DernierIndex(ensemble) { let element = ensemble[index] print("element \(element)") index = index + 1 } }
Parcours par intervalle
Pour réaliser le parcours d’un ensemble sur un intervalle on introduit une syntaxe particulière
implémentée dans la plupart des langages de programmation impératif. En Schema on notera un intervalle de la façon suivante:
borneInférieure -> bornesupérieure
Modèle de de parcours sur un intervalle intervalle
Algorithme
Parcours ensemble >- [10 20 40] index <- PremierIndex(ensemble) premierIndex <- index premierIndex -> DernierIndex(ensemble) element >- ensemble[index] Afficher element #element index <- index + 1 Fin Fin
Traduction swift
func Parcours() { let ensemble = File(10,20,40) var index = PremierIndex(ensemble) let premierIndex = index for _ in premierIndex...DernierIndex(ensemble) { let element = ensemble[index] print("element \(element)") index = index + 1 } }
Parcours sur ensemble itérable
Un ensemble est dit itérable lorsque l’on peut parcourir ses éléments sans recourir à une itération par expression conditionnelle ou par une expression bornée de type intervalle.
En Schema on notera le parcours sur un ensemble itérable de la façon suivante
Algorithme
Parcours ensemble >- [10 20 40] ensemble : element Afficher element #element Fin Fin
Parcours ensemble >- [10 20 40] boucle <- 1 ensemble Afficher boucle #boucle boucle <-boucle + 1 Fin Fin
Traduction swift
func Parcours() { let ensemble = "hello" for element in ensemble { print("element \(element)") } } func Parcours() { let ensemble = File(10,20,40) var boucle = 1 for _ in ensemble { print("boucle \(boucle)") boucle = boucle + 1 } }
Parcours récursif sur ensemble
Un algorithme récursif est un algorithme qui s’appelle lui même.
Algorithme
Parcours ensemble Ensemble Si NON Dernier(ensemble) element >- Prendre_Element(ensemble) Afficher element #element Parcours(ensemble) Fin Fin
Traduction Swift
Version générique et récursive (on explicitera cette version dans un prochain article)
func Parcours <Element>(_ ensemble: Ensemble<Element>) { if !Dernier(ensemble) { let element = Prendre_Element(ensemble) print("element \(element)") Parcours(ensemble) } }
copyright A rchitectures A pplicatives A vancées A3-Soft