Parcours dans un ensemble

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