> Quelques cours > Algorithmique et Analyse > 1. Introduction

sommaire

version imprimable

1. Introduction

1.1. Pourquoi un cours d'algorithmique

" Avant donc que d'écrire apprenez à penser "
Boileau "Art Poétique"

1.1.1. Le mot Algorithme

" L'objet de l'algorithmique est la conception, l'évaluation et l'optimisation des méthodes de calcul [ de traitement de l'information] en mathématique et en informatique. Un algorithme consiste en la spécification d'un schéma de calcul, sous forme d'une suite [ finie ] d'opérations élémentaires obéissant à un enchaînement déterminé.

Le terme algorithme tire lui-même son origine du nom du mathématicien persan Al Khwärismi (env. 820) dont le traité d'arithmétique servit à transmettre à l'Occident les règles de calcul sur la représentation décimale des nombres antérieurement découvertes par les mathématiciens de l'Inde "

(article "Algorithmique" in Encyclopædia Universalis)

1.1.2. quels sont les besoins

On constate que le débutant commence en général par des cours de "programmation". Que ce soit en Basic, C, Fortran ou Pascal, ces cours sont en fait des cours de langage illustrés par l'écriture de programmes. Un tel type d'enseignement ne constitue pas à proprement parler un cours de programmation dont l'objet devrait être plus orienté vers les méthodes essentielles : comment construire un programme, comment faire pour que ce programme soit juste.

D'autre part, quand on apprend à programmer en utilisant un langage particulier (mais comment faire autrement?) les possibilités de ce langage paraissent au novice représenter la totalité de ce que l'on peut exprimer avec un langage de programmation. Or les solutions conçues en restreignant la pensée du concepteur à l'usage de structures disponibles dans un langage particulier risquent d'être déformées par ces restrictions. Le résultat est que des programmes ainsi développés sont difficilement transposables lorsqu'il faut réécrire l'application dans un autre langage. Les influences perverses du "langage maternel" peuvent être plus nombreuses que l'on imagine ; même l'influence des notations mathématiques usuelles peut être pernicieuse ; par exemple, si coder (-1)^k dans le calcul d'une série alternée n'est en général qu'une maladresse qui a un effet ralentisseur sur l'exécution du programme, écrire comme il est habituel en mathématique X x Y < 0 pour exprimer que les deux quantités X et Y sont de signes opposés peut très facilement conduire à des erreurs (si les valeurs de X et Y sont suffisamment petites) dans la recherche d'une racine par la méthode de la dichotomie.

De plus, dans la quasi-totalité des cas, la partie des langages de programmation proposée aux débutants diffère peu des langages d'assemblage (langage machine) en ce sens que la plupart des opérations considérées sont des opérations "atomiques" : lire le contenu d'une variable simple, l'additionner au contenu d'une autre variable, ranger le résultat dans une troisième... La manipulation d'entités sensiblement plus complexes, outre qu'elle n'est pas possible par tous les langages, ne peut que rarement être envisagée au niveau de l'apprentissage1.

Cet aspect élémentaire des possibilités du langage fait que, si on n'y prend pas garde, écrire un programme d'une certaine importance devient une tâche inextricablement compliquée. Or notre esprit est irrémédiablement borné, en particulier il ne nous permet pas d'envisager, dans leur totalité, des objets trop complexes, si bien que l'écriture sans méthode d'un programme important se conclut souvent par un échec ou, "au mieux", par un programme faux.

Il faut donc apprendre à construire une solution non plus à partir des toutes petites briques que sont ces opérations atomiques, mais à partir de modules (qu'il faut le cas échéant bâtir à partir de briques plus petites). La démarche est la même que pour la construction d'appareils électroniques : actuellement, la plupart d'entre eux sont réalisés à partir de circuits intégrés spécialisés et non plus à partir de composants élémentaires (résistances, transistors) comme c'était le cas il y a quelques dizaines d'années.

1.2. Buts de ce cours

Les principaux buts de ce cours sont, d'une part, de faire découvrir un certain nombre de structures de données et d'algorithmes qui n'ont pu être envisagés au niveau d'une initiation et d'autre part, d'apprendre à construire la solution d'un problème, puis à prouver la justesse de la solution et enfin d'étudier comment évaluer l'efficacité de cette solution.

La démarche fondamentale est d'apprend à exprimer la solution d'un problème dans les termes du problème et non dans ceux du langage ou de l'ordinateur utilisé pour le résoudre.

C'est pourquoi nous développerons un ensemble raisonnable de concepts - structures de données et structures de contrôle - qui corresponde aux besoins d'une programmation propre. Cet ensemble de structures n'est presque jamais disponible en totalité dans les langages de programmation usuels.

La structuration d'un programme (aussi bien des données que du code) est l'illustration du fameux "diviser pour conquérir2" : on décompose un traitement à réaliser, de grande ampleur, en un certain nombre de "sous-traitement" plus simples portant sur des objets moins complexes ; bien sûr, cette décomposition peut être répétée en cascade. A toutes les étapes de cette décomposition, chaque sous-traitement est défini en tant que "quoi" (c.-à-d. quelles actions doivent être réalisées), le "comment3" (ces actions sont effectivement réalisées) n'ayant pas à être connu de celui qui demande ce sous-traitement. L'objectif est que, grâce à cette décomposition, chaque étape du traitement soit suffisamment simple pour que son exactitude4 soit indubitable.

Nous ne nous intéresserons pas au problème d'optimisation d'algorithmes (rappelons cependant que les "trucs" proposés par les débutants sont dans leur immense majorité, au mieux, inefficaces ou, au pire, désastreux). Par contre nous nous intéresserons à la question de l'efficacité des algorithmes en étudiant la complexité (en n, n² ...).

Lors de l'exposition des algorithmes, l'accent sera mis sur des techniques de construction très simples, techniques qui ne sont pas innées pour un débutant mais dont la possession aide grandement au succès. En effet, la lecture d'un algorithme ou d'un programme n'apprend rien sur le processus de sa construction : il est rarissime qu'on puisse écrire un algorithme comme on le lit, en commençant à la première ligne et en terminant à la dernière ligne. L'écriture commence par la définition précise du problème à traiter et par une description détaillée des principales données à manipuler. Lors de l'écriture de l'algorithme, on commencera par traiter les cas "ordinaires" (c.-à-d. quand "tout se passe bien"), le traitement des cas particuliers ou exceptionnels n'est à envisager que lorsqu'on en a terminé avec les cas ordinaires. En particulier, les itérations (boucles) ne sont jamais écrites en écrivant le premier ordre de boucle (il est rare qu'on sache comment débuter) : on écrit d'abord les instructions qui doivent être répétées en précisant, en commentaires, les conditions logiques vérifiées en début de chaque itération (et dont la validité, après une itération, est la condition pour déclencher l'itération suivante) ce sont les "invariants de boucle" ; ce n'est qu'après la spécification de ces invariants que peuvent être écrites les instructions d'initialisation de la boucle (et c'est alors beaucoup plus facile!). Les tâches complexes, dont les détails alourdiraient la lecture du programme (ou qui dépendent des structures intimes des données manipulées) seront avantageusement déléguées à des sous-programmes dont on spécifie le comportement, l'écriture de ces sous-programmes étant reportée à une autre étape du développement.

Il est bien évident que ce cours n'a aucune vocation à l'exhaustivité5, il serait vain de vouloir répéter d'excellents ouvrages qui y prétendent. Notre but est plus modestement d'apprendre à construire simplement des algorithmes simples. Cette simplicité est, répétons le, un gage d'efficacité, tant en rapidité de développement, qu'en fiabilité6 des résultats.

1.3. Langage

" Ce que l'on conçoit bien s'énonce clairement
Et les mots pour le dire arrivent aisément "
(Boileau ibid)

Un langage de programmation7 permet de spécifier les actions ou opérations que l'on applique à des objets, passifs, les "données8".

Peut on se servir d'un langage informatique existant pour concevoir des algorithmes ? Ce langage doit servir d'interface entre le raisonnement humain et la machine, à ce titre il doit en priorité être destiné à l'être humain (en tenant compte des imperfections de son cerveau). Ceci pose la question des qualités requises d'un langage pour exprimer un raisonnement informatique :

• non ambiguïté : Si Jean dit à Pierre : "je vois Michel moins souvent que toi", cette phrase peut être comprises de deux manières différentes : une telle situation devraient être impossible avec un langage de programmation ;
• lisibilité (par l'humain ! puisque c'est l'auteur et le re-lecteur du programme)
• simplicité, pour tenir compte de nos capacités intellectuelles limitées ;
• conformité aux habitudes intellectuelles (ou principe de "moindre étonnement"), il y a déjà des problèmes avec des expressions courantes du type "si A et B sont positifs" qu'il faut en général traduire par "si (A est positif) et (B est positif)" mais un langage qui permet que l'expression if (0 < n < 100) ne signifie pas "si n est compris entre 0 et 100" ne répond pas à ce critère ;
• souplesse, pour faciliter la créativité (il faut que le langage facilite l'expression de notre pensée au lieu de nous contraindre à torturer cette pensée pour tenter de l'exprimer avec les mots insuffisants du langage) ;
• cohérence : similitude des comportements dans des situations semblables, par exemple en C (encore!) la conversion d'une quantité de type float vers le type int n'est pas toujours réalisée de la même manière que la conversion de type double vers le type int (arrondi dans un cas, troncature dans l'autre) ;
• abstraction : possibilité de créer des objets adaptés aux besoins et aussi complexes qu'il est nécessaire, par exemple, une "fiche d'étudiant" comportant des rubriques : Nom, prénom, âge, groupe, liste de notes... ou encore, pour faire des constructions graphiques à 2 dimensions, il est commode de considérer diverses structures abstraites, le "point" (ensemble de coordonnées x et y d'un point), le "rectangle", (ensemble de 2 points, définissant des sommets opposés, et d'un angle donnant l'orientation d'un côté) ;
• expressivité : manipuler simplement des objets complexes dans leur ensemble (par exemple, copier le contenu d'un tableau dans un autre, dupliquer une "fiche d'étudiant") ;
• modularité : création de modules (ou "unit", "libraries"), boîtes à outils dont les composants sont définis par leurs fonctionnalités (ce qu'ils font) et dont l'utilisateur n'a pas à connaître les procédés utilisés pour réaliser ces fonctionnalités (comment ils font) ;
• encapsulation : que les données ne puissent pas être manipulées par n'importe quel opérateur mais seulement par des outils spécifiques, ce qui évite au programmeur d'avoir à connaître leur implémentation (et met à l'abri de modifications indues). Modularité et encapsulation figurent parmi les techniques de base de la structuration ; bien utilisées, ces propriétés permettent en outre de changer, si cela est nécessaire, la structure de certaines données manipulées par un programme sans que le reste du programme soit concerné par ces changements : seuls les modules directement concernés par la manipulation de la structure intime de ces données ont besoin d'être modifiés ;
• pour les langages réels, résistance aux erreurs accidentelles (orthographe, ponctuation) ; nombre de langages permettent des constructions "périlleuses"; par exemple if then else en Pascal dont chaque branche ne contrôle qu'une seule instruction, ou encore la boucle "DO" du Fortran qui a permis l'erreur de programmation de la sonde Mariner : DO 15 i = 1.24 au lieu de DO 15 i = 1,24

Certaines de ces qualités sont incompatibles entre elles et avec tout langage existant9

C'est pourquoi nous emploierons des "Notations Algorithmiques" destinées à l'humain ; elles seront souples : la présentation fait partie des notations, des commentaires peuvent en préciser le sens, elles sont donc par essence non implémentables (à la différence d'ALGOL).

1.4. Structure des données

1.4.1. types de données

Les types de données sont caractérisés par leur description et par la liste des opérations qu'on peut appliquer aux données de ce type. L'ensemble des types de données, et des opérations disponibles, ainsi que la possibilité de créer des types nouveaux (cf propriété d'abstraction du langage), varie d'un langage à l'autre (on parle des "primitives" du langage), on peut citer :

• +- sur des petits entiers,
• +-x/ sur des entiers plus grands,
• les 4 opérations sur des flottants,
• les 4 opérations sur les rationnels, par exemple : 57/23 + 32/128 → 251/92
• calcul matriciel, calcul littéral,
• gestion des piles, queues, listes, arbres, graphes : localiser, ajouter, ôter les éléments
• opérateurs graphiques : dessiner, peindre courbes et polygones,
• opérateurs "ensemblistes" : intersection, union, "soustraction" ...

Dans ce cours, nous séparerons les types de données en :

• les objets10 atomiques (qui ne peuvent contenir qu'une seule valeur à la fois), souvent dénommés "scalaires11" :
  

  10. Précisons encore que, dans ce cours, le mot "objet" est utilisé au sens ordinaire et qu'il n'a rien à voir avec la "programmation par objets".

  fermer cette précision

  11. Voir en appendice 1.8.2

  fermer cette précision

  • numériques, sans distinguer réels et entiers (en fait, nous utiliserons presqu'exclusivement les entiers),
  • logiques, ou "booléens" (qui peuvent prendre 2 valeurs vrai et faux)
  • textuels (alias "chaînes de caractères")
  • types définis pour la clarté de la conception, en général à partir d'énumérations, par exemple :
    type_jour = (lundi, mardi, mercredi, jeudi, vendredi, samedi, dimanche) ;
    type_etat_du_stock = (vide, plein, normal) ;
  • adresses, ou pointeurs12, ils n'ont de sens que si on connait le type d'objets pointé (étant donné le risque d'erreurs13 dans leur manipulation, il est recommandé d'en "user avec modération") ;
    

    12. Voir en appendice 1.8.5

    fermer cette précision

    13. Voir en appendice 1.8.5

    fermer cette précision

• les objets "poly-atomiques" (ils peuvent contenir, en même temps, plus d'une valeur); parler du type de tels objets n'a, comme pour les pointeurs, de sens qu'une fois connus les types des composants (par exemple tableaux de nombres ou tableaux de chaînes de caractères); à noter que les composants d'objets poly-atomiques peuvent eux-mêmes être des objets poly-atomiques. Nous allons décrire les méthodes de regroupement pour la construction de types d'objets poly-atomiques :
  
  • les objets composés (à accès direct) :
    
    • tableaux, objets homogènes (toutes les composantes, ou éléments, sont du même type); dans un tableau, chaque élément est repéré par un ou plusieurs indices, les indices ne sont pas nécessairement des entiers mais l'ensemble des indices est isomorphe à un sous-ensemble des entiers. Il faut remarquer que rien n'oblige les tableaux à avoir des dimensions fixées (même si c'est l'usage dans beaucoup de langages),
    • agrégats (record en Pascal et en Ada, struct en C, type en Fortran 90), objets hétérogènes (les composants, ou champs, peuvent être de types différents), par exemple : fiche_d_étudiant avec des champs nom, prénom, âge etc. Les différentes composantes d'un agrégat sont désignées par le nom du champ correspondant;
  • les collections d'objets (à accès séquentiel ou à accès indirect) :
    
    • linéaires (une seule dimension) : listes, files, piles, et aussi les fichiers,
    • ramifiées : arbres, graphes
    • informes : le tas14 (heap), c'est dans cette structure que sont allouées les "variables dynamiques15".
      

      14. Nous verrons plus tard une autre signification possible de ce mot (tri par "tas").

      fermer cette précision

      15. Voir en appendice 1.8.2

      fermer cette précision

1.4.2. les données

Ce sont les objets manipulés, elles constituent la réalisation (instanciation) de types de données. Elles sont distinguées par leur nature : variables, constantes (à noter qu'on peut faire des distinctions subtiles : une variables peut avoir dans certaines parties du programme les attributs d'une constante, ce qui rend localement sa modification impossible).

Dans le cadre d'un programme, elles sont caractérisées par :

• leur désignateur (soit un nom : l'identificateur, soit un "pointeur" vers cette donnée, on peut dans ce cas parler de variable "anonyme"),
• leur type,
• leur statut : entrée, sortie, locale, globale, temporaire, permanente ...
• leur rôle : ici on touche à la signification (sémantique) des constructions réalisées, domaine beaucoup plus difficile à formaliser que la présentation et de la description des règles de grammaire (syntaxe), c'est pourquoi ces dernières indications sont fournies sous forme de commentaires.

1.5. Structures de contrôle

Ce sont elles qui permettent de diriger l'exécution d'un programme. Le fondement de la structuration consiste à considérer un groupe d'instructions comme s'il s'agissait d'une instruction unique dont la complexité interne et masquée ; il s'ensuit que pour pouvoir faire cette assimilation le groupe d'instructions doit n'avoir qu'un seul point d'entrée et un seul point de sortie16 (la notion de sous-programme représente de façon exemplaire cet aspect de la structuration).

Les structures de base (qui semblent les plus naturelles) sont la séquence, le choix, la répétition :

• exécution strictement séquentielle, c'est le mode normal d'exécution17 : chaque instruction est exécutée après celles qui la précèdent dans le texte du programme et avant celles qui la suivent,
  

  17. Voir en appendice 1.8.1

  fermer cette précision

  

  Exécution séquentielle

  (le cadre, en pointillé, illustre comment le groupe d'instructions
  peut être regardé comme une instruction unique)

• exécutions alternative et conditionnelle
  

  exécution alternative		exécution conditionnelle

• exécutions à choix multiples, cette structure peut être ambiguë : l'exemple en est donné par la différence de comportement entre le case (du Pascal), où l'exclusion des autres actions n'est pas automatique (on peut dependant l'obtenir en codant l'instruction break à la fin des actions); avec cette dernière forme, on conçoit bien qu'il peut être malaisé de déterminer l'état atteint par le programme après l'exécution de cette structure (d'autre part, l'erreur de programmation est facile : break oublié ou disparu!). autre sujet d'ambiguïté : quel doit être le comportement de l'instruction si plusieurs cas sont possibles simultanément, ou si un cas possible ne figure pas dans la liste des choix offerts? Le grand nombre de restrictions attachées à cette construction, dans les différents langages, reflète bien les ambiguïtés sémantiques.
  

  structure "switch" de C		structure "case" de Pascal

• exécutions répétitive ou boucle, la répétition peut être contrôlée par des conditions multiples, ces contrôles pouvant être disposés selon les besoins ; malheureusement, la plupart des langages ne connaissent que des structures plus rudimentaires et on doit pallier à ces insuffisances, à l'aide de "GOTO" ; cette forme générale n'est implantée que dans quelques langages (Ada, Fortran 90),
  
  
• exécutions de sous-programmes (ou routines) ; les sous-programmes (procedure, subroutine, function) permettent de regrouper les séquences plus ou moins complexes d'instructions et de les faire apparaître dans le corps du programme comme une seule instruction ; c'est pourquoi ils correspondent aux besoins : abstraction, lisibilité, modularité, encapsulation et non duplication de l'information-code (principe de "unicité de l'information), a priori rien n'interdit qu'ils soient récursifs (voir plus loin). On distingue souvent les fonctions qui calculent une "valeur" associée à leur nom (à l'exemple des fonctions mathématiques) et les procédures qui réalisent des actions sans rendre de valeur spécifique. Il est souvent admis que les fonctions ne doivent pas modifier les valeurs de leurs arguments18 (toujours comme les fonctions mathématiques) alors que c'est le mode de fonctionnement normal des procédures ; cependant, il est souvent utile que des sous-programmes renvoient à la fin de leur exécution un "code de retour" qui rend compte des opérations réalisées, il peut alors être commode que de tels sous-programmes soient écrits sous forme de fonctions modifiant leurs arguments et rendant comme valeur celle du code de retour.
  

  18. Un langage comme C, qui ne possède que des fonctions, oblige à pratiquer l'art de la dissimulation à grande échelle :

  1. les fonctions de type "void" ne rendent pas de valeurs (ce sont en fait des procédures),

  2. tous les arguments étant transmis "par valeur" (voir l'Appendice 1.8.6), chaque sous-programme semble ne pas pouvoir modifier ses arguments ; ces modifications sont dissimulées en transmettant au sous-programme les valeurs de pointeurs sur les arguments effectifs et non les valeurs de ces arguments (noter que C++ permet une syntaxe un peu plus évoluée).

  fermer cette précision

  

1.6. "Notations agorithmiques"

Les notations utilisées dans ce cours sont assez semblables à celles de Pascal ; cependant elles sont "complètement parenthésées" (c.à-d. que à chaque mot-clé définissant le début d'une structure - de données ou de contrôle - correspond un autre mot-clé indiquant la fin de cette structure), ce qui évite certaines ambiguïté d'écriture. Elles sont sans contraintes formelles, par contre la présentation (identations) aide à préciser la signification. En cas de doute, des commentaires doivent permettre de lever les ambiguïtés. Il faut noter que ces notations ne cherchent à "coller" à aucun lanagage (ce n'est pas parce qu'une structure existe ou n'existe pas dans un langage particulier qu'elle est intrinsèquement bonne ou mauvaise). Le but est de faciliter l'expression simple des besoins ; pour faciliter la compréhension, nous nous appliquons à n'employer que des termes du vocabulaire français (anglais à la rigueur ...). Pour éviter les "faux amis", nous éviterons, autant que possible19, d'utiliser dans ces notations des termes ayant une signification précise dans un langage particulier.

Les commentaires

/*   ...   */   (qu'il ne faut pas confondre avec les annotations à vocation explicative et pédagogique)

En bonne programmation, les commentaires s'écrivent en même temps, ou mieux avant, le reste du programme (jamais après, ce ne sont pas des décorations) : " c'est parce qu'on écrit en premier ce qu'on veut faire, qu'on sait ensuite ce qu'on doit écrire dans le programme. "

Les déclarations

variables numériques : x, y, z ;
N.B. il est indifférent d'écrire : x, y, z : variables numériques;
ou variables : x, y, z : numériques;

variables textuelle : nom_d_étudiant ;

variables tableau numérique indice [1..15] : x, y, z ;
(les limites des indices d'un tableau sont précisées explicitement ; la forme des parenthèses () {} ou [] est a priori sans importance, cependant du fait de leur commodité nous emploierons en général les parenthèses ordinaires () et nous réserverons l'usage des crochets pour désigner des intervalles - presque comme en mathématiques - par exemple [1..15])

Si besoin est, on peut définir des types nouveaux (comme en Pascal), en particulier on utilisera fréquemment le constructeur "agrégat" :

A chaque fois qu'apparaîtra une variable de type "pointeur", c'est à cette variable ou à sa valeur qie les expressions feront référence20 (comme en Pascal ou en C) et non à l'objet pointé (comme en Fortran 90) ; lorsqu'on voudra faire référence à l'objet désigné par le pointeur on notera : objet(pointeur).

Pour désigner un champ d'un agrégat on utilisera une notation qui ressemble à ce que l'on dit spontanément21 : nom(candidat). Pour désigner un champ d'un objet pointé on écrira nom(p), en effet on a déclaré, par exemple, que p pointe sur une variable de type fiche_étud (remarquons que la notation fiche_étud(p) pour désigner l'objet pointé par p est donc quelque peu redondante).

Fréquemment, le type exact de certains objets sera de peu d'importance pour la conception de l'algorithme, aussi on emploiera souvent des types génériques passe-partout comme "ty_valeur_clé22", "ty_élem_liste" ou "ty_valeur_à_trier23"

Les instructions exécutables et de contrôle

• l'affectation :

  Il faut bien comprendre la signification24 : la valeur de ce qui est à droite du symbole est stockée dans l'objet dont l'identificateur figure à gauche.

  24. Voir en appendice 1.8.4

  fermer cette précision

• les choix (exécutions conditionnelle, alternative)

  si condition_logique alors

  action_"vrai" ...

  sinon (clause optionnelle)

  action_"faux" ...

  fin_si

  Cette construction peut être étendue en construction à choix multiple (chaque cas est exclusif de tous les autres, c.-à-d. que à chaque exécution de l'instruction une seule voie sera empruntée et que si plusieurs des condition_logique peuvent être simultanément vraies, c'est la première dans le texte qui sera choisie.

  si condition_logique_1 alors

  action_1 ...

  sinon_si condition_logique_2 alors (clause optionnelle)

  action_2 ...

  sinon_si condition_logique_3 alors (clause optionnelle)

  action_3 ...

  sinon (clause optionnelle)

  action_"autre" ...

  fin_si

• la boucle on délimite le groupe des instructions à répéter et on indique les conditions qui déterminent le déroulement ou l'interruption de la boucle :

  répéter

  ...

  tant que condition_logique

  ...

  jusqu'à_ce_que condition_logique

  ...

  pour compteur variant_de départ à fin

  ...

  si condition_logique alors cesser_de_répéter

  ...

  fin_répéter

• les sous-programmes : procédures et fonctions sont écrits à peu près comme en Pascal (ou mieux Fortran 90), on précise dans l'en-tête les natures, type, statut25 et rôle des arguments ainsi que le rôle du sous-programme. La valeur calculée par une fonction est retournée par le nom de la fonction (comme en Fortran et en Pascal). Le retour au programme appelant coïncide avec la rencontre de l'un des délimiteurs fin_de_procédure ou fin_de_fonction (comme en Pascal) : il n'est pas besoin d'indiquer explicitement return comme en Fortran ou en C. Le problème de la récursion sera traité plus loin dans ce cours (N.B. si un sous-programme doit être récursif cela sera précisé dans l'en-tête, comme en Fortran 90).

  25. Voir en appendice 1.8.6

  fermer cette précision

  fonction max (x, y, "ty_valeur_à_comparer": Entrées)

  : résultat : "ty_valeur_à_comparer"

  si x < y alors

  max x

  sinon

  max y

  fin_si

  fin_fonction

1.7. Bibliographie (non exhaustive)

• Structured Programming, O.-J DAHL, E.W. DIJKSTRA, C.A.R. HOARE, A.P.I.C. Studies in Data Processing n°8, Academic Press (1972)
• The Art of Computer Programming, Volume 1 Second Edition / Fundamental Algorithms, Donald E. KNUTH, Addison Wesley (1973)
• Systematic Programming, An Introduction, Niklaus WIRTH, PRENTICE-HALL (1976)
• The Elements of Programming Style, Brian W. KERNIGHAN, P.J. PLAUGER, Mc GRAW-HILL BOOK (1974)
• Algorithms + Data Structures = Programs, Niklaus WIRTH, PRENTICE-HALL (1976)
• Première leçons de programmation, J. ARSAC, CEDIC/FERNAND NATHAN (1980)
• Méthodes de programmation, Bernard MEYER, Claude BAUDOIN, Eyrolles (1984)
• Types de données et algorithmes, Christine FROIDEVAUX, Marie-Claude GAUDEL, Michèle SORIA, Mc GRAW-HILL (1990)
• Introduction to algorithms, Thomas H. CORMEN, Charles E. LEISERSON, Ronald L. RIVEST, The MIT Press & Mc GRAW-HILL Book Company (1990)
• Conception et Programmation par Objets. Pour du logiciel de qualité, Bertrand MEYER, InterEditions (1990)
• Les langages à Objets, Principes de base, techniques de programmation, Michel BEAUDOUIN-LAFON, Armand COLIN (1992)
• Concepts fondamentaux de l'informatique, Alfred AHO, Jeffrey ULLMAN, DUNOD (1993)
• Langages de programmation comparés, Leslie B. WILSON, Robert G. CLARK, Addison WESLEY (1993)
• Précis de génie logiciel, Marie-Claude GAUDEL, Bruno MARRE, Françoise SCHLIENGER, Gilles BERNOT, MASSON (1996)
• Les Shadoks, Jacques ROUXEL, Circonflexe (1994)
• Les poules du couvent couvent, Thierry LEGUAY, Mots et Cie (1999)

1.8. Appendices

1.8.1. Exécution séquentielle

Dans un langage impératif, les instructions sont exécutées dans l'ordre où elles figurent dans le texte du programme (sauf directive contraire : choix, boucle, appel de sous-programme).

Si ce n'était pas le cas, il serait très difficile - pour ne pas dire impossible - de prévoir le résultat d'une suite d'instructions (étudier l'exemple ci-dessous).

Ce comportement est communément admis par chacun ; cependant, il n'est pas rare de voir les débutants s'étonner de ne pas obtenir le résultat espéré (parce que les instructions ne sont pas écrites dans l'ordre correct) :

1.8.2. Contenants

En simplifiant, on peut dire que ce sont les mots-mémoires où le programme stocke les données qu'il manipule. Le problème est de pouvoir désigner chacun de ces mots (ou groupe de mots)-mémoire.

En langage machine on les désigne par leurs adresses.

Dans les langages un peu plus évolués, on les désigne par un "nom symbolique" (identificateur), par exemple x, t, delta, le système du compilateur établissant la correspondance entre le nom symbolique et l'adresse réelle en mémoire.

Cette pratique n'est pas toujours possible : par exemple, quand le nombre et l'organisation des données que devra stocker le programme ne peut être connu au moment de l'écriture et de la compilation du programme, mais seulement au cours de l'exécution. On aura alors besoin de faire allouer "dynamiquement" (pendant l'exécution du programme) des mots-mémoire pour y stocker les données. Ces mots ne pourront pas être "référencés" par des noms qui leur soient propres (on parle de variables "anonymes") puisque de tels noms sont donnés par le programmeur avant la compilation (et donc l'exécution) du programme : on ne pourra les désigner qu'à l'aide de "structures dynamiques" (listes chaînées par exemple) dont les éléments comporteront un champ "pointeur" (contenant en fait l'adresse réelle en mémoire du/des mots-mémoire que l'on veut désigner).

1.8.3. Contenu

Le contenu d'un mot mémoire est une suite ordonnée de bits (0 ou 1). Le nombre de ces bits est la taille du mot. Le contenu d'un mot n'a aucune signification intrinsèque, sa signification est une affaire de codage liée au type. Cette "interprétation" dépend de ce que l'on a décidé que ce mot contenait : par exemple, un entier, un flottant ou une suite de caractères (codage ASCII, EBCDIC, UNICODE ...).

Diverses interprétations du contenu d'un mot-mémoire de 32 bits : selon qu'on le regarde comme une suite de bits (affichage binaire, octal, hexadécimal), ou une suite de caractères codés en ASCII, ou comme un entier, ou encore comme un flottant (sur une machine particulière).

Il ne faut jamais perdre de vue que les bits d'un mot ont toujours une valeur, que le programme y ait déposé une valeur ou non. Si le programme n'a encore rien déposé dans un mot, le contenu est, en général, imprévisible. Il s'en suit que la notion de mot "vide" n'a a priori, aucun sens (sauf si on a convenu qu'une configuration particulière correspondrait à cet état, convention qui a le défaut d'éliminer cette configuration de la liste des valeurs utiles).

1.8.4. Contenant et contenu

Un problème de compréhension fréquent réside dans la distinction contenant-contenu, ce qui conduit souvent à des erreurs de programmation. C'est le problème de distinction entre "adresse" et "valeur", problème bien connu des programmeurs débutant en assembleur.

Ce problème est déjà visible avec des notations usuelles : dans l'affectation A B + C, le symbole A (dans certains ouvrages on le désigne sous le terme de "l_value") représente un contenant alors que les symboles B et C désignent des contenus (l'expression B + C est alors appelée "r_value").

La facilité de confusion entre adresse et valeur peut engendrer des effets pervers sur le raisonnement : de la valeur NIL donnée à un pointeur qui ne pointe sur rien (qui se représente en général par une adresse invalide) on est facilement conduit à passer à la valeur "rien" ou "cellule vide" qui n'est aisément représentable en machine.

1.8.5. En avoir ou pas26 : les pointeurs

" Lorsque le Maître de la Sagesse pointe son doigt vers la lune
l'imbécile ne regarde que le doigt "
proverbe chinois (?)

Un pointeur est un objet essentiellement ambigu : il est à la fois une variable et le désignateur27 d'une autre variable.

On dit que le pointeur "fait référence" à l'objet pointé ; lorsqu'on utilise le pointeur pour accéder à la valeur de l'objet pointé, on parle de "déréférenciation" du pointeur28.

L'ambiguïté sémantique est exemplaire dans l'affectation pA pB, où pA et pB sont respectivement des pointeurs vers deux variables A et B (de même type!) :

• dans de nombreux langages, cela signifie que, après l'affectation pA pB, le contenu de la variable pA est le même que le contenu de la variable pB (donc que pA pointe aussi vers B),
• dans certains langages, par contre, la déréférenciation est la règle et, après l'affectation pA pB, le contenu de la variable A est le même que le contenu de la variable B (il existe alors un opérateur spécifique pour amener pA à pointer vers la même cible que pB).

En conclusion, "les pointeurs sont aux structures de données, ce que le GOTO est aux structures de contrôle" (Wirth), c'est à dire que grâce à eux, le programmeur peut retrouver la liberté de création du langage machine (où tout est permis et où rien ne protège le programmeur contre les erreurs les plus folles). Il est donc prudent de les cantonner29 dans les mêmes emplois que le GOTO : créer des structures naturelles qui ne sont pas prévues dans le langage utilisé.

1.8.6. "Arguments d'Entrée", "Argument de Sortie"... comment matérialiser ces notions

Entre programme appelant et sous-programme appelé, la communication des données est spécifiée par une liste d'arguments30 (quelques appelés paramètres). La liste d'arguments écrite dans le sous-programme est souvent appelée liste d'arguments formels (parfois dénommés aussi arguments "muets", dummy en anglais) elle permet de fixer les natures, types et statuts des arguments. Lors de l'appel, le programme appelant doit fournir une liste d'arguments (appelés arguments "vrais" ou "réels") en accord avec la liste spécifiée dans le sous-programme.

• Exemple : on veut écrire la procédure Min_Max qui reçoit 2 valeurs numériques x et y et rend dans l'argument min la plus petite de ces valeurs et dans max la plus grande. Avec nos notations algorithmiques nous écrirons :

  procédure Min_Max (x, y : numériques, Entrée; min, max : numériques, Sortie);

  si x > y alors

  min y; max x

  sinon

  min x; max y

  fin_si

  fin_procédure Min_Max

  Cette simplicité d'écriture facilite l'expression de notre pensée. Nous allons voir comment quelques langages peuvent rendre compte de ces spécifications de statut.

  Il faut savoir qu'il existe deux procédés principaux pour "passer" des arguments entre un programme appelant et un sous-programme appelé :

  • le passage "par valeur", où les valeurs des arguments d'appel sont recopiés dans l'espace de travail du sous-programme appelé,
  • le passage "par adresse", où ce sont les adresses des arguments d'appel qui sont communiquées au sous-programme appelé.

• en Pascal :

  Sans précision supplémentaire, tout argument est argument d'entrée ; pour qu'un argument soit considéré comme argument d'entrée-sortie, il faut précéder sa déclaration du mot-clé var.

  procedure Min_Max (x, y : real; var min, max : real);

  begin

  if x > y then

  begin

  min := y; max := x

  end

  else

  begin

  min := x; max := y

  end

  end ; { Min_Max }

  appel :Min_Max (u, v, petit, grand);

  x, y sont des variables locales à la procédure, elles reçoivent, lors de l'appel, les valeurs des arguments d'appel u et v ; les adresses des variables grand et petit correspondant aux arguments max et min sont transmises à la procédure qui va travailler sur grand et petit. A noter que Pascal ne gère pas le statut Sortie (seule). Il faut aussi remarquer que, puisque x, y sont des variables locales à la procédure, rien n'interdit au programmeur d'en modifier la valeur, d'où de possibles déconvenues si le programmeur souhaitait faire part de ces modifications au programme appelant...

• en FORTRAN 77 :

  Il n'y a aucun moyen de spécifier les statuts : tous les arguments sont passés par adresse, c'est-à-dire que le sous-programme travaille directement sur les objets du programme appelant, il a donc la possibilité de les modifier (délibérément ou non!).

  SUBROUTINE Min_Max (x, y, min, max)

  REAL x, y, min, max

  IF (x .GT. y) THEN

  min = y

  max = x

  ELSE

  min = x

  max = y

  END IF

  RETURN

  END

  appel :CALL Min_Max (u, v, petit, grand);

• en FORTRAN 90 :

  Ce sont encore les adresses des arguments d'appel qui sont passées. Le statut est précisé par les mots-clés IN, OUT, INOUT de l'attribut INTENT. x, y sont considérées par le compilateur comme des constantes, il refusera donc toute tentative d'en modifier les valeurs (soit que le programmeur les ait mis à gauche du signe =, soit qu'il les ait mis dans la liste des arguments d'appel à une procédure où elles auraient le statut OUT ou INOUT).

  SUBROUTINE Min_Max (x, y, min, max)

  REAL, INTENT (IN) :: x, y

  REAL, INTENT (OUT) :: min, max

  if (x > y) THEN

  min = y

  max = x

  ELSE

  min = x

  max = y

  END IF

  RETURN

  END

  appel :CALL Min_Max (u, v, petit, grand);

• en C :

  La situation se complique : les objets atomiques (ainsi que les structures) sont passés par valeur (les tableaux par adresse!). Pour qu'un argument soit retourné en sortie, il faut forcer le compilateur à passer au sous-programme l'adresse de l'argument de sortie et bien sûr, en tenir compte dans la rédaction du sous-programme...

  void min_max (float x, float y, float *min, float *max)

  {

  if (x > y)

  {

  *max = x; *min = y;

  }

  else

  {

  *max = y; *min = x;

  }

  }

  appel :min_max (u, v, &petit, &grand);

  (Lors de l'appel, ne pas oublier de passer au sous-programme l'adresse de ces arguments.

• en C++ :

  On peut continuer d'utiliser la syntaxe du C. Cependant, la situation s'améliore avec l'apparition du concept de référence : les arguments dont le nom est précédé de & dans la liste des arguments formels ont un comportement comparable à ceux dont le nom est précédé de var en Pascal.

  void min_max (float x, float y, float & min, float & max)

  {

  if (x > y)

  {

  max = x; min = y;

  }

  else

  {

  max = y; min = x;

  }

  }

  appel :min_max (u, v, petit, grand);

1.9. Compléments : exemples numériques "surprenants"

Ecrire et tester ces exemples sur les machines du LEI ainsi que sur toutes les machines, et dans tous les langages à votre disposition

1.9.1. Nombre de racines d'une équation du second degré

N.B. Si vous obtenez toujours Δ nul, ce n'est pas normal! Plusieurs raisons peuvent expliquer ce comportement, en particulier le processeur des opérations flottantes peut avoir stocké dans les registres les résultats intermédiaires avec une précision beaucoup plus grande que celle utilisée pour représenter les REAL si bien que les petites erreurs disparaissent au moment des conversions. On pourrait essayer d'éviter de tels effets en séparant les différents calculs correspondants à une même valeur de A, par exemple en stockant les valeurs successives de A et C dans des tableaux que l'on remplira successivement par deux boucles, tandis qu'une troisième réalisera les calculs de discriminant.

1.9.2. Influence de l'ordre des opérations

1.9.3. Série en 1/n²

1.9.4. Recherche d'un zéro d'une équation par la méthode de dichotomie

On considère les fonctions y(x) = tan(x * π/4) - 1 et z(x) = y(x) * 10-20. En utilisant la méthode de dichotomie, on recherche les racines de y(x) = 0 et z(x) = 0 comprises entre 0 et π/2. On examinera l'influence de la façon d'exprimer que f(x1) et f(x2) sont de mêmes signes :
f(x1) * f(x2) > 0, ou une autre méthode.

1.9.5. Calcul de π par l'algorithme d'Archimède

1.9.6. Calcul de sin(α) par un développement en série entière

version imprimable

retour vers le haut chapitre suivant