I.GENERALITES:
I.1.INTRODUCTION:
L'algorithmique est à la base de la conception des langages de programmation dits
«procéduraux», comme le langage C, Pascal, Java, Javascript, PHP et bien d'autres. Pour qui
maîtrise cette discipline, l'étude d'un de ces langage se résume la plupart du temps à
l'apprentissage de la nouvelle syntaxe, les mécanismes qui la sous-tendent étant déjà
connus pour la plupart.
D'autre part, l'algorithmique constitue un excellent outil d'analyse et de modélisation, utilisable
à tous les niveaux de la conception d'un logiciel. Elle peut s'intégrer à
la plupart des méthodologies existantes.
Intuitive et pratique, ne nécessitant aucune connaîssance particulière, si ce n'est le
sens de la logique et l'esprit d'analyse, l'algorithmique constitue donc un excellent pré-requis
pour l'étude des langages procéduraux, mais aussi pour aborder la problématique de la
conception des logiciels.
I.2.ALGORITHMES ET ALGORITHMIQUE:
I.2.1.QU'EST-CE QU'UN ALGORITHME?:
DEFINITION-ALGORITHME:
Un algorithme est une méthode opérationnelle de résolution d'un problème à
partir de ses données.
Ce type de méthode est dit "opérationnel" pour établir une distinction avec les méthodes
dites "axiomatiques":
- Une méthode de résolution dite "axiomatique" a pour but d'établir la
démonstration logique de la solution d'un problème: on essaie de prouver (par
une série de déductions appliquées aux assertions constituant les
hypothèses) la validité d'une conclusion (qui est elle-même une assertion).
La résolution axiomatique d'un problème a un caractère intemporel: elle ne
fait que démontrer la validité d'une conjecture qui était déja valide avant sa
résolution et le restera après. Elle n'entraîne aucune modification de l'environnement.
- En revanche, une méthode de résolution dite "opérationnelle" est un mode
opératoire permettant de déterminer le comportement d'un exécutant
(ou processeur) donné afin que celui-ci exécute des opérations sur son
environnement, dans le but d'aboutir au résultat recherché. Cette action est donc inscrite dans
le temps et peut entraîner une modification de l'environnement du processeur.
Une méthode de résolution opérationnelle est souvent l'application d'une méthode
de résolution axiomatique, qui en constitue la justification.
EXEMPLES:
- Dans le domaine de l'arithmétique, l'algorithme de résolution d'une division
désigne l'ensemble des opérations qui, enchaînées les unes aux autres, conduiront au
résultat de cette division. Il s'agit donc d'un mode opératoire qui, appliqué par un
exécutant à un couple de nombres donné, lui permet de trouver le quotien et le
reste de la division d'un de ces nombres par le second. Cet algorithme se fonde sur la «théorie
de la division», qui apporte la démonstration logique (axiomatique) de la validité de cet algorithme.
- Un procédé de fabrication, une recette de cuisine, un mode d'emploi, un itinéraire
se présentent sous la forme d'algorithmes (plus où moins rigoureux dans leur formalisme).
PROPRIETES CARACTERISTIQUES:
Un algorithme doit présenter les caractéristiques suivantes:
- Il est constitué d'une liste finie d'instructions destinées à un
exécutant (en anglais: processeur). Ces instructions concernent un nombre fini de
données, soit pour les créer, modifier ou supprimer, soit pour les utiliser dans
l'élaboration des traitements.
- L'exécution d'un algorithme doit conduire à la solution du problème après
exécution d'un nombre fini d'opérations.
- L'ordre dans lequel les opérations sont enchaînées par le processeur ne
dépend pas seulement de l'ordre établi par la liste d'instructions: cet ordre peut tenir
compte de l'état de l'environnement au moment de l'exécution de chaque instruction: valeur
des données, survenue d'événements, etc (par exemple, un itinéraire peut
prévoir plusieurs variantes en fonction de la météorologie ou de l'état
du trafic à un certain endroit du trajet). L'ordre d'exécution des instructions est donc
dépendant du contexte.
I.2.2.ORIGINE DU MOT:
Le mot ALGORITHME provient probablement du surnom du mathématicien et astronome persan Abu Abdullah Muhammad
Ibn Musa (780-850). En effet, celui-ci était désigné en orient par le surnom Al KHAREZMI, traduit dans le monde occidental
par le vocable latinisé Algorismus.
I.2.3.QU'EST-CE QUE L'ALGORITHMIQUE?:
L'ALGORITHMIQUE est l'étude des techniques d'élaboration des algorithmes et de leur
application à la résolution de problèmes opérationnels. Elle recouvre les
activités suivantes:
- Analyse du problème à résoudre: données initiales, résultats
à obtenir, contraintes à respecter.
- Etude du processus de traitement des données permettant d'aboutir au résultat.
- Réalisation de l'algorithme (ou des algorithmes) traduisant ce processus.
I.2.4.DOMAINE D'APPLICATION DE L'ALGORITHMIQUE:
Un algorithme représente la décomposition temporelle d'un procédé en une
succession d'instructions à exécuter. Cette démarche convient bien à l'analyse des
activités de production (développement de logiciels, procédés de
fabrication, etc...) ou à la description de savoir-faires procéduraux. Elle est, en
revanche, peu applicable aux activités de création basées sur l'intuition, la
sensibilité (concepts publicitaires ou artistiques par exemple), qui demandent une approche plus
globale et synthétique.
L'analyse algorithmique ayant pour but de définir une solution opérationnelle, elle n'est
pas directement applicable à l'analyse fonctionnelle, le but de celle-ci étant d'analyser un
besoin indépendemment de ses solutions.
I.3.ALGORITHMIQUE ET LANGAGES:
I.3.1.COMPOSANTS D'UN LANGAGE ALGORITHMIQUE:
Nous avons vu plus haut qu'un algorithme est constitué d'une liste finie d'
instructions
concernant un nombre fini de
données. Les langages d'algorithmes ont pour but de
spécifier d'une manière claire et dépourvue d'ambiguité ces différents composants
ainsi que la
logique d'enchaînement des instructions. Un langage algorithmique est donc composé
principalement de 3 types de directives:
- Des instructions de déclaration de données: ces instructions permettent de définir
et de caractériser des données
- Des instructions agissant sur les données (création, modification, suppression, entrées
et sorties de données). Ces instructions sont souvent appelées instructions d'assignation (de
données).
- Des instructions agissant sur l'ordre d'exécution des instructions (appelées aussi
instructions de contrôle). A la différence des deux types précédents, ces
instructions permettent de modifier, en fonction du contexte d'exécution, la séquence
initiale, en déroutant l'exécutant vers une instruction différente de celle qui les suit
dans la liste d'instructions
A ces 3 types de composants peuvent être adjoints des commentaires destinés à améliorer
la compréhension.
REMARQUES
- Nous retrouverons ces types de composants dans la plupart des langages informatiques procéduraux:
ceci n'a rien d'étonnant, un programme informatique n'étant pas autre chose qu'un algorithme
destiné à être exécuté par un processeur informatique.
- Les langages algorithmiques sont appelés «PSEUDO-CODES» pour les distinguer
des langages informatiques, désignés par les termes: «langage de programmation»
ou encore «codes d'ordre».
I.3.2.PROCESSEURS ET INSTRUCTIONS ELEMENTAIRES:
Lorsqu'une instruction peut être directement exécutée par le processeur, il s'agit d'une
opération élémentaire de ce processeur (On utilise aussi le terme Primitive).
Dans le cas contraire, l'instruction correspond à une action complexe qu'il faudra décomposer en
un sous-algorithme.
Le terme atomique est souvent appliqué à une entité indécomposable en
éléments plus simples (a-tome signifie "qui ne peut être coupé"). En algorithmique,
une instruction est dite "atomique" lorsqu'on ne peut pas la décomposer en instructions plus simples.
Pour un processeur donné, une opération élémentaire est donc une
instruction atomique.
I.3.3.PRINCIPES SYNTAXIQUES DES LANGAGES ALGORITHMIQUES:
Les langages algorithmiques se distinguent des langages de programmation par le fait que, contrairement
à ces derniers, leur principale utilité est de permettre, par une démarche d'analyse,
le passage de la formulation d'un problème exprimée dans un langage "humain" à une
formulation exécutable par le processeur choisi (c'est à dire n'utilisant que des primitives
compréhensibles par ce processeur). Il faut donc que les rêgles de syntaxe du pseudo-code utilisé
puissent s'adapter à tous les niveaux de cette analyse.
De ce fait, afin de traduire la problématique au niveau humain, une instruction d'un algorithme doit pouvoir
être rédigées en «texte libre». La seule contrainte est qu'elle soit compréhensible et sans ambiguité à la
fois pour le "donneur d'ordre" et le rédacteur. Ainsi pourrons-nous trouver dans un algorithme des
instructions rédigées comme suit:
<Calculer le prix de revient unitaire du produit>
<Ouvrir la vanne du réacteur n° 5>
Temperature ← <Valeur mesurée par le capteur, convertie en degrès>
etc...
Ces instructions sont tout à fait licites dans la mesure où les termes qui les composent désignent sans
ambiguité des données du problème (Remarquer l'emploi des signes < et > : il s'agit là d'une des
conventions utilisées pour délimiter ce type d'instructions libres).
D'une façon générale, les règles syntaxiques des pseudo-codes s'appliquent surtout aux déclarations de données
et aux instructions de contrôle.
I.4.PREMIERE APPROCHE A PARTIR D'UN EXEMPLE:
REMARQUE:
Ce sous-chapitre est destiné à mettre en évidence, au travers d'un exemple, les principaux
concepts communs aux langages de programmation et aux pseudo-code de description des algorithmes. Ces notion
seront, dans la suite de l'ouvrage, précisées et détaillées.
I.4.1.EXEMPLE PROPOSE: APPROCHE ALGORITHMIQUE DE L'ADDITION:
PROBLEME A RESOUDRE:
Le problème choisi est la résolution sur papier d'une addition de 2 nombres entiers positifs
décimaux de 3 chiffres au plus.
RESOLUTION ALGORITHMIQUE:
L'algorithme suivant s'adresse à un être humain muni de moyens pour écrire et ne sachant
pas faire une addition (un élève de debut du primaire, par exemple).
ALGORITHME N° 1
00 Lire au tableau la valeur des deux nombres à additionner
01 Ecrire les deux nombres l'un sous l'autre sur une feuille de papier
02 Tracer un trait en dessous des deux nombres
03 Additionner les chiffres de la colonne des unités et mémoriser le résultat
04 SI le nombre mémorisé est supérieur à 9 ALORS écrire 1 en dessus de la colonne des dizaines
05 SINON écrire 0 en dessus de la colonne des dizaines
06 Ecrire le chiffre unité du nombre mémorisé sous la colonne des unités
07 Additionner les chiffres de la colonne des dizaines et mémoriser le résultat
08 SI le nombre mémorisé est supérieur à 9 ALORS écrire 1 en dessus de la colonne des centaines
09 SINON écrire 0 en dessus de la colonne des centaines
10 Ecrire le chiffre unité du nombre mémorisésous la colonne des dizaines
11 Additionner les chiffres de la colonne des centaines et mémoriser le résultat
12 SI le nombre mémorisé est supérieur à 9 ALORS écrire 1 en dessous de la colonne des milliers
13 SINON ne rien faire
14 Ecrire le chiffre unité du nombre mémorisé sous la colonne des centaines.
I.4.2.ANALYSE DE CET EXEMPLE:
PROBLEMATIQUE LIEE AU PROCESSEUR:
Le processeur humain doit comprendre et exécuter les opérations élémentaires
qui composent cet algorithme. Il doit donc posséder les qualifications suivantes:
- Connaître les chiffres décimaux
- Connaître les notions d'unités, dizaines, centaines et milliers attachées aux
nombres entiers décimaux
- Savoir écrire deux nombres l'un dessous l'autre sur un support d'écriture et souligner
ces nombres
- Savoir écrire un chiffre en dessus ou en dessous d'une colonne de chiffres
- Additionner deux chiffres décimaux et mémoriser le résultat
- Prendre une décision en fonction d'une condition simple
- Cette liste n'est probablement pas exhaustive...
Cet algorithme semble donc bien adapté à un élève de début du primaire.
En revanche, un ordinateur serait tout à fait incapable de l'exécuter sous cette forme, car on
n'a pas utilisé un langage de programmation.
D'autre part, pour un exécutant humain plus qualifié (un élève de collège,
par exemple), cet algorithme est inutilement détaillé: il suffirait de lui dire:
ALGORITHME N° 2
Liste des données:
Premier nombre, Deuxième nombre
Liste d'opérations:
Prendre connaissance de la valeur de Premier nombre et Deuxieme nombre
Additionner ces deux nombres
Présenter le résultat par écrit
En effet, pour un élève de 6 eme, l'instruction «Additionner ces deux nombres» est
une opération élémentaire, car il maîtrise (en principe) l'algorithme de
l'addition, ce qui n'est pas le cas pour l'élève précédent.
PROBLEME DE LA QUALIFICATION DU PROCESSEUR:
Cet exemple illustre le fait que les opérations élémentaires composant le pseudo-code
d'un algorithme dépendent de la qualification du processeur auquel il est destiné. En effet,
une procédure, une consigne de travail qui s'adresse à un professionnel très
qualifié, peut employer des termes techniques ou mentionner des procédés sans les
détailler, alors que pour un débutant ou une personne peu qualifiée, il faudra entrer
beaucoup plus dans le détail des opérations à effectuer.
1.4.2.1.NOTION DE NIVEAU D'ABSTRACTION D'UN ALGORITHME:
D'autre part, au début de l'étude d'un problème, il est souvent indispensable de ne
s'attacher qu'à des concepts globaux, en faisant abstraction des détails de
réalisation. Un même exécutant humain sera donc amené à analyser un
même problème à différents NIVEAUX D'ABSTRACTION successifs (correspondant
à des descriptions de plus en plus détaillées), jusqu'à ce que le niveau de
détail soit jugé suffisant pour que la réalisation ne pose plus de problème
à l'exécutant choisi.
L'élaboration d'un algorithme destiné à un exécutant donné peut donc exiger
plusieurs étapes, chacune d'entre elles étant matérialisée par l'élaboration d'un
algorithme correspondant à un niveau d'abstraction de plus en plus faible, jusqu'à obtention d'une
procédure rédigée en pseudo-code adapté à l'exécutant.
Ainsi, dans l'exemple précédent, la directive "Additionner ces deux
nombres" correspond-t-elle à un certain niveau d'abstraction (on fait
abstraction des détails de réalisation d'une addition). L'algorithme N° 2 peut donc être
considéré comme une étape de l'élaboration de l'algorithme n° 1.
DEMARCHE PAR ABSTRACTION:
Ce qui précède constitue une première approche de la démarche par abstraction,
qui consiste à faire abstraction de détails de réalisation qui peuvent
être négligés à un certain niveau d'analyse d'un problème. Cette
démarche, très utilisée en informatique, consiste donc à "mettre de côté
certains détails d'un problème en les encapsulant dans un "objet", dont on supposera
qu'il est susceptible de renfermer les solutions de ces détails. En algorithmique, cet objet sera matérialisé
par une instruction en texte libre que l'on considèrera à ce niveau comme atomique.
Par exemple, l'operation "Additionner ces deux nombres"
de l'algorithme n° 2 encapsule les détails de réalisation matérialisés par les
opérations n° 2 à 14 de l'algorithme n° 1.
REMARQUE:
Pour pouvoir faire abstraction des détails de réalisation d'une action données
(en l'encapsulant dans une instruction), il est indispensable de connaître parfaitement les
données consommées et les données produites par cette action, et
éventuellement les contraintes liées à son exécution. Dans le cas contraire, il
est serait impossible de déterminer l'effet produit par l'instruction "encapsulante". Seules
les modalités de réalisation de cette action peuvent rester indéterminées à ce niveau.
1.4.2.2.STRUCTURES SEQUENCIELLES ET ALTERNATIVES:
STRUCTURES SEQUENCIELLES:
La majorité des instructions composant l'algorithme n° 1 s'exécutent dans l'ordre ou elles
se présentent dans la liste (par exemple: Lire au tableau.., Additionner les chiffres, Tracer un trait,
etc..), et n'agissent pas elles-même sur l'ordre d'exécution. Il s'agit là d'instructions
d'assignation de données. Une succession d'instructions de ce type constitue une STRUCTURE
SEQUENCIELLE (par exemple, les lignes de 00 à 03).
STRUCTURES ALTERNATIVES:
Nous pouvons également constater dans le premier algorithme la présence d'instructions dont
l'exécution est soumise à condition (couples d'instructions numérotées 4 et 5,
8 et 9, 12 et 13): en fonction du résultat de la condition: «le nombre mémorisé
est supérieur à 9», le processeur exécute l'une ou l'autre instruction de ces
trois couples. Ce type de structure logique ayant pour schéma:
SI <telle condition est vraie > ALORS < Traitement n° 1 >
SINON <Traitement n° 2 >
est appelé «STRUCTURE ALTERNATIVE» (On dit également
«INSTRUCTION CONDITIONNELLE», bien qu'il s'agisse plutôt d'un ensemble d'instructions).
Ces structures utilisent des instructions de contrôle ( contrôle de la séquence
d'exécution).
REMARQUES:
- Les deux alternatives d'une structure peuvent être constituées de plusieurs blocs
d'instructions, pouvant eux-même englober des alternatives.
- La satisfaction des conditions peut dépendre du contexte d'exécution, c'est à
dire des résultats d'exécution précédents. L'aptitude à interpréter
et exécuter des structures alternatives basées sur des conditions dépendante du
contexte d'exécution est une des caractéristiques fondamentales de l'architecture de
VON NEUMAN, sur laquelle se fondent la quasi totalité des processeurs informatiques .
C'est elle qui leur permet de simuler un comportement «intelligent». En cela, ils se distinguent
du simple exécutant séquenciel qu'est, par exemple, un piano mécanique.
- Certains travaux menés dans les années 1960 ont permis d'établir qu'il est
possible de résoudre tous les problèmes s'exprimant d'une manière procédurale
en employant uniquement une combinaison de structures séquencielles et alternatives.
- Nous verrons plus tard que, pour des raisons de confort et d'efficacite, l'algorithmique
définit également des structures dites «répétitives»: ce ne sont
en fait que des combinaisons de séquences et d'alternatives).
1.4.2.3.ESPACE D'EXECUTION D'UN ALGORITHME:
On peut en donner la définition suivante:
L'ensemble des données susceptibles d'être utilisées par un algorithme (c'est à dire pouvant
agir sur le déroulement d'un algorithme ou bien sur lesquelles un algorithme est susceptible
d'agir) constitue l'ESPACE D'EXÉCUTION de cet algorithme.
REMARQUE:
Le contenu de l'espace d'exécution d'un algorithme peut être modifié par l'exécution
de cet algorithme. D'autre part, il peut influer sur l'exécution de l'algorithme, par le biais des
structures d'opérations conditionnelles. Le contenu de l'espace d'exécution constitue donc un
état, qui peut être modifié par les transitions provoquées par
l'exécution des instructions de l'algorithme.
I.5.APPLICATION AU GENIE LOGICIEL:
I.5.1.INTRODUCTION:
Dans le domaine du développement de logiciels, les algorithmes sont utilisés lors des phases
de conception des logiciels. Ils conviennent parfaitement à l'analyse organique des traitements
(phase de conception détaillée)
Ils peuvent également être utilisés lors de la phase de spécification du besoin, car
bien qu'ils ne conviennent pas à l'analyse fonctionnelle, ils peuvent être utilisés comme outils de
modélisation (notamment dans la description des interfaces homme-machine, par leur aptitude à décrire les
automates d'états finis).
I.5.2.EXIGENCES CONCERNANT LES PSEUDO-CODES UTILISES:
On peut résumer ces exigences dans le tableau suivant:
EXIGENCE |
COMMENTAIRE |
Lisibilité: |
Compréhensible pour un non-informaticien |
Indépendance vis à vis de l'implémentation: |
Traduisible en n'importe quel langage de programmation, travaillant sur n'importe
quelle machine, munie de n'importe quel système d'exploitation.. |
Précision |
Pas de possibilité de confusion sur la nature des instructions |
Concision |
Pour que le lecteur puisse comprendre aisément la structure logique d'un algorithme,
il doit grader sous les yeux la totalité de son texte. Celui-ci doit donc tenir sur une
seule page (et même, si possible, un seul écran d'ordinateur). Au-delà, le
problème doit être décomposé en sous-problèmes (sous-algorithmes).
|
Structuration |
Un algorithme doit pouvoir être décomposé en différentes parties
distinctes les unes des autres et dont le rôle de chacune est facilement identifiable.
|
Il n'existe aucune norme entièrement définie pour l'écriture des algorithmes. Cependant,
un certain nombre de conventions sont très fréquemment respectées. Elles concernent
essentiellement:
- L'écriture des structures alternatives et répétitives.
- La déclaration des données
- La déclaration et l'écriture des sous-algorithmes
La présentation de ces conventions d'écriture fait l'objet du chapitre suivant.
Dans le domaine du génie logiciel, le but de l'analyse algorithmique est d'aboutir à des
programmes informatiques,exécutables par des systèmes informatiques. Cette
exigence influe beaucoup sur la syntaxe des pseudo-codes utilisés: les utilisateurs intègrent
souvent, en plus des structures alternatives et répétitives traditionnelles, des
«instructions» directement inspirées du fonctionnement des ordinateurs
(opérations d'entrée-sortie, traitement d'événements, etc..).
I.6.CONCLUSION:
De ce qui précède, on peut déduite qu'il est impossible de définir un pseudo-code
universel permettant de décrire un algorithme destiné à un processeur humain, la nature
de la plupart des opérations élémentaires dépendant soit du domaine
d'activité et de la «qualification» de l'exécutant, soit du niveau d'abstraction
auquel il se place. Cependant, nous verrons qu'il est possible de standardiser un certain nombre d'instructions
et de structures, en particulier celles qui décrivent des schémas logiques généraux
ou des notions indépendantes de tout domaine d'activité.
En définitive, un pseudo-code se présentera comme un ensemble de séquences (ou de
«blocs») d'instructions dont certaines seront écrites en langage libre, pourvu qu'elles
aient un sens (pour le rédacteur de l'algorithme, si on se trouve à un niveau d'abstraction
élevé ou pour l'exécutant, s'il s'agit de l'algorithme final),
«enchâssées» dans des structures logiques (alternatives, répétitives)
dont l'écriture obeira à des conventions plus précises.