III.L'ANALYSE ALGORITHMIQUE:

Chapitre précédent. Evaluation. Chapitre suivant.

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.

Chapitre précédent. Evaluation. Chapitre suivant.