Site A.T.L.A.N.T.I.C-83
COURS = Algorithmique (Chapitre_1) - VERSION: 1.0 (M.A.J: 14/04/09)
- AUTEUR(s): Bernard GIACOMONI
Ecran large mobile
Retour
sommaire cours

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).


addition a trois chiffres

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.


Retour accès aux cours Retour sommaire cours