III.L'ANALYSE ALGORITHMIQUE:
III.1.GENERALITES:
La démarche fondamentale de l''analyse algorithmique appliquée au génie logiciel est,
bien évidemment, la modélisation des problèmes sous la forme d'algorithmes écrits
suivant les conventions exposées au chapitre III. Cette démarche conduit à trouver des
solutions «procédurales», facilement traduisibles dans les langages de programmation
procéduraux tels que C, Pascal, Fortran, java, javascript, PHP, etc).
III.2.LE PRINCIPE D'ABSTRACTION:
III.2.1.RAPPELS-NIVEAUX D'ABSTRACTION:
Nous avons, dans le premier chapitre de ce cours, abordé rapidement la démarche par abstraction, qui consiste
à ne pas tenir compte ("faire abstraction") de détails de réalisation qui n'influent pas sur le "niveau
d'analyse" où on se trouve.
EXEMPLE: lorsqu'on commence à étudier un itinéraire routier de Marseille à Paris, on peut, dans un
premier temps, négliger les problèmes posés par la manière de traverser les villes ou l'alimentation en
carburant. On fait donc abstraction de ces problèmes. Ce n'est que lorsqu'on aura fixé l'itinéraire
général que l'on passera à un niveau d'étude plus fin, dans lequel on pourra réfléchir au problème de
l'itinéraire de traversée de telle ou telle agglomération.
La démarche par abstraction revient donc à analyser un problème suivant une succession de niveaux de détail,
encore appelés NIVEAUX D'ABSTRACTION: à chaque niveau, la résolution des détails de réalisation qui
peuvent y être négligés est repoussée à un niveau plus fin, jusqu'à ce que le problème soit entièrement résolu.
III.2.2.MASQUAGE ET ENCAPSULATION:
Cependant, faire abstraction des détails de réalisation d'un élément particulier d'un problème ne signifie pas
négliger complètement cet élément: en effet, celui-ci intervient dans la logique globale du niveau
d'abstraction depuis lequel on mène l'analyse. De ce fait, il est indispensable de déterminer quelle est la
contribution de cet élément à la solution globale, les données dont il a besoin et celles
qu'il fournit au niveau supérieur. En fait, il n'est fait abstraction que de la manière dont cet
élément sera élaboré.
Concrètement, un élément dont on veut faire abstraction de la réalisation sera encapsulé dans une
entité dont on définira la (ou les) fonctions ou services qu'elle est sensé fournir au niveau
d'abstraction où l'on se trouve.
EXEMPLE: Imaginons que l'étude de l'itinéraire précédent prévoie un passage par Lyon. Dans un
premier temps, les détails de la traversée de cette ville seront encapsulés dans une entité qui pourra être
appelée "Traversée de Lyon". Il suffira, à ce niveau, d'en préciser la fonction (traversée de lyon),
les interfaces (entrée par telle route, sortie par telle autre), et éventuellement, les performances
(durée maximale acceptable, par exemple).
Le schéma suivant donne un aperçu synthétique de la démarche d'analyse par abstraction:
COMMENTAIRES:
- La SOLUTION élaborée au niveau 1 invoque les éléments de solution 1.1, 1.2,..., 1.n, tout en faisant
abstraction de la manière dont ces éléments sont résolus.
- Au niveau 2, on va s'intéresser à la résolution des éléments de solution dont on a fait abstraction au
niveau précédent. Pour ce faire, on va être amené à faire abstraction d'éléments dont on va renvoyer la
solution au niveau 3;
- ...Et ainsi de suite, jusqu'à ce que l'on n'ait plus besoin de faire abstraction d'aucun
détail, car l'expression de leur solution devient évidente.
III.3.APPLICATION A L'ANALYSE ALGORITHMIQUE:
III.3.1.LA DEMARCHE PAR ABSTRACTION EN ALGORITHMIQUE:
En algorithmique, chaque niveau d'abstraction va se matérialiser par la construction d'un ou plusieurs
algorithmes. Dans ces algorithmes, l'encapsulation d'un élément de solution dont on veut faire
abstraction va se traduire soit par l'insertion d'une instruction en texte libre, soit par l'appel
d'une procédure ou fonction, dont on se contentera, à ce niveau, de définir la
fonction et les interfaces.
Dans les deux cas, il s'agit de l'encapsulation de sous-algorithmes dont on renvoie à plus tard la
réalisation. Notons que lorsqu'on utilise une instruction en texte libre, il faut que son libellé soit
suffisamment parlant et précis pour ne laisser aucune ambiguité sur son effet.
III.3.2.NOTION DE MACHINE VIRTUELLE:
Chaque niveau d'analyse produira donc un (ou des) algorithmes, qui utiliseront un certain nombre de services
sensés être fournis par des "instructions virtuelles" encapsulés par les éléments
définis à cet effet. On peut considérer que l'ensemble de ces éléments
constitue un EXECUTANT VIRTUEL (on encore: MACHINE VIRTUELLE) permettant de mettre en oeuvre les
opérations encapsulées. On peut donc considérer que la démarche par abstraction
consiste à concevoir une succession de couches de machines virtuelles, les machines d'une couche
donnée faisant appel aux machines du niveau inférieur, jusqu'au niveau correspondant à
l'exécutant final.
REMARQUES:
- Dans un ordinateur, le système d'exploitation peut être considéré comme une machine virtuelle
encapsulant les fonctions d'accès au matériel. Ces fonctions sont utilisées par les programmes
informatiques. Cette démarche permet au développeur de faire abstraction des problèmes liés à la
gestion du matériel
- En informatique, ces machines virtuelles peuvent être appelées objets, machines abstraites, etc.. Elles
encapsulent des fonctions (appelées aussi opérations externes, méthodes, etc.. ) et des données
(attributs...)
Le schéma suivant donne un aperçu synthétique de la notion de machine virtuelle
COMMENTAIRES:
- L'algorithme élaboré au niveau 1 fait appel à des sous-algorithmes dont il fait abstraction de la
manière dont ils peuvent être réalisés. Seuls les services offerts par ces sous-algorithmes et leurs
interfaces sont pris en compte.
- Les services offerts par ces sous-algorithmes peuvent être considérés comme encapsulés dans un EXECUTANT
VIRTUEL (ou encore MACHINE VIRTUELLE) capable de les exécuter comme des opérations atomiques.
- Au niveau 2, l'analyste va analyser d'analyser ces services par des algorithmes. La démarche par
abstraction va le conduire à définir une nouvelle machine virtuelle, la machine de niveau 2
- ...Et ainsi de suite, jusqu'à ce que la machine virtuelle corresponde à l'exécutant auquel s'adresse
l'algorithme global.
III.4.EXEMPLE DE DEMARCHE PAR ABSTRACTION:
Le schéma suivant représente une analyse (très simplifiée) du problème
«Bâtir une maison de N étages», menée en trois niveaux d'abstraction:
PREMIERE ETAPE:
Dans une première étape (niveau I), le modèle algorithmique sera:
DEBUT
var NombreNiveauxBatis en numerique
var NombreEtages en numerique
ENTRER NombreEtages
<Bâtir les fondations>
<Bâtir les étages>
<Construire le toit>
<Effectuer les finitions>
FIN
Remarquons que cet algorithme fait abstraction de la manière dont doivent être
réalisée les fondations, les étages, le toit ou les finitions: ces problèmes
sont repoussés à un niveau d'analyse inférieur. Ceci permet de faire ressortir la logique
qui préside à ce niveau (ici: une maison se construit obligatoirement de bas en haut !). A ce
niveau d'analyse, les instructions sont généralement libellées en texte libre, car le
niveau d'abstraction est élevé.
DEUXIEME ETAPE:
Dans la deuxième étape (niveau II), ces instructions vont être décomposées
de façon à obtenir un niveau d'analyse plus fin. Le nouvel algorithme sera:
DEBUT
var NombreNiveauxBatis en numerique
var NombreEtages en numerique
ENTRER NombreEtages
// Bâtir les fondations
<Faire les terrassements>
<Construire les fondations>
// Bâtir les étages
NombreNiveauxBatis ← 0
TANT QUE ( NombreNiveauxBatis < NombreEtages + 1 FAIRE
<Bâtir un niveau>
NombreNiveauxBatis ← NombreNiveauxBatis +1
FIN TANT QUE
// Construire le toit
<Monter la charpente>
<Placer les tuiles>
<Placer les goûtières>
// Effectuer les finitions
Installer les réseaux électricité, plomberie, chauffage>
<Monter les cloisons>
<Monter les huisseries>
FIN
A ce niveau d'analyse, les instructions du niveau I ont été décomposées en
instructions plus précises et plus parcellaires. Remarquer que les instruction du niveau I ont ici
été utilisées pour commenter le niveau II: c'est souvent une bonne pratique.
Certaines instructions sont encore constituées de texte libre, ce qui veut dire que l'on fait
abstraction du mode de réalisation, qui est renvoyé à un niveau d'analyse inférieur.
Cependant, nous voyons déjà apparaître un certain nombre de structures logiques et de
notations conventionnelles, ce qui prouve que l'analyse du problème progresse.
ETAPES SUIVANTES:
Si le problème est de faire exécuter le travail par des professionnels du bâtiment
très qualifiés, ce niveau de détail peut être suffisant. En effet, un professionnel
saura comment interprèter et exécuter <Faire les terrassements> ou <Monter les huisseries>.
En revanche, si l'on veut confier le travail à des exécutants peu qualifiés, il faudra
des niveaux de décomposition supplémentaires. On pourra alors:
- Soit décomposer les opérations du niveau II comme il a été fait pour le
niveau I, ce qui conduira peut-être à un algorithme trop long pour tenir en une seule page.
- Soit remplacer ces instructions par des appels à des procédures ou des fonctions, ce qui
permettra de conserver la lisibilité de ce niveau d'analyse. Par exemple, l'instruction
<Bâtir un niveau> pourrait être remplacé par l'appel d'une fonction ( Batir_un_niveau () ),
qui ferait l'objet de la fonction suivante:
//------------------------------------------------------------------------------
// FONCTION Batir_un_niveau
//------------------------------------------------------------------------------
// PRINCIPE: construit un niveau d'habitation
//------------------------------------------------------------------------------
FONCTION Batir_un_niveau ()
<couler une dalle>
<monter les murs maîtres>
RETOUR ''Niveau terminé''
FIN FONCTION
III.5.CONCLUSION:
De ce qui précède, on peut déduire que l'analyse algorithmique consiste en la
modélisation d'un problème sous forme d'une succession d'algorithmes se déduisant
les uns des autres par une démarche de décomposition de plus en plus fine du pseudo-code.
On appelle cette démarche un RAFFINAGE (du pseudo-code).
L'analyse algorithmique est donc une démarche globalement descendante (TOP-DOWN), bien que
la construction des algorithmes eux-mêmes soit plutôt une démarche synthétique
(BOTTOM-UP).
L'analyse s'arrète quand le niveau de détail semble suffisant pour que l'exécution ne
pose plus aucun problème. Le niveau de détail à atteindre dépend essentiellement
du type de processeur auquel le modèle algorithmique final est destiné. En informatique, ce
niveau pourra être celui qui permettra une traduction directe et sans ambiguité de l'algorithme
dans le langage de programmation qui sera utilisé en phase de réalisation.