Kha-tastrophe.net

Le site kha-tastrophique de Kha

> Cours > Informatique> Algorithmique et Analyse > Introduction

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.

1. L'expérience montre aussi que ces apprentissages trop brefs de langages de programmation confinent le débutant dans ces pratiques de programmation "atomique" sans lui permettre de découvrir et de pratiquer toutes les possibilités d'abstraction (structure de données et de contrôle) qu'offre un langage. Quant aux cours d'approfondissement, ils ont trop souvent tendance, sous prétexte "d'efficacité", à se contenter de l'étude des particularismes d'une implémentation du langage...

fermer cette précision

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.

2. Il nous semble qu'il faille préférer la traduction littérale de la maxime anglo-saxonne "divide to conquer" à son homologue française "diviser pour rèner" où le mot "règner" a une connotation plus statique que "conquérir".

fermer cette précision

3. La démarche est la même que lorsqu'on code a * x + b : on ne se préocupe pas de la façon dont le processeur va réaliser la multiplication et l'addition.

fermer cette précision

4. En effet, il faut toujours se rappeler que l'exactitude d'un programme n'est pratiquement jamais prouvable par des tests : les "jeux d'essais" ne doivent être conçus que pour tenter de révéler les insuffisances du programme (comment, par exemple, essayer de prouver, par des test l'exactitude des 264 multiplications possibles sur un processeur 32 bits?). L'exactitude d'un programme ne peut donc être prouvée que par "raison démonstrative"; c'est pourquoi le programme doit être décomposé en sous-ensembles, aux rôles bien définis, de tailles suffisamment faibles et de structures suffisamment simples pour qu'on puisse aisément raisonner sur chacun.

fermer cette précision

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.

5. En particulier, l'étude d'algorithmes d'analyse numérique n'est pas notre propos, pas plus que l'étude d'algorithmes liés à la programmation de machines parallèles. Nous ne parlerons pas non plus des techniques de "programmation par objets", encore que beaucoup des concepts liés à celles-ci sous-entendent notre exposé.

fermer cette précision

6. Rappelons que la première qualité d'un programme (quasiment inaccessible pour un projet d'envergure) est de ne pas être faux. Il ne faut pas, non plus, perdre de vue le fait que si les erreurs commises par les machines sont devenues extrêmement rares, les machines calculent faux : en particulier les reel ne sont pas des réels et les integer ne jouissent pas de toutes les propriétés des entiers.

fermer cette précision

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

7. Le fait que nous parlions d'algorithmes implique que nous ne nous intéressons ici qu'aux "langages impératifs" dont les représentants les plus connus dans notre domaine sont : Ada, Algol, Basic, C, C++, Forth, Fortran, Java, Pascal, PL/I.

fermer cette précision

8. Le mot "données" est utilisé en informatique avec une signification plus large que son sesn originel : tout ce qui est manipulé, transformé par le programme, et non pas seulement les valeurs et paramètres initiaux donnés au programme. Par exemple lors de la résolution de l'équation ax² + bx + c = 0 les valeurs a=2, b=-10, c=12 sont les données au sens habituel, mais en informatique le discriminant Δ, les racines x1, x2 ... sont aussi des "données" manipulées par le programme.

fermer cette précision

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

9. En particulier, dans les langages modernes (Pascal, Ada, Fortran 90) l'accent est mis sur la détection précoce (par le compilateur) du plus possible des erreurs d'écriture ; ce qui entraîne le rejet de la souplesse d'écriture, qui serait favorable à la créativité.

fermer cette précision

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

    • 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") ;
  • 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) :

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

16. Ici réapparaît le problème du "nuisible" GOTO, nous dirons que son emploi n'est licite que pour réaliser une structure de contrôle "naturelle" mais absente du langage utilisé.

fermer cette précision

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,

    Exécution séquentielle

    Schéma illustrant l'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

    Schéma illustrant l'exécution alternative

    Exécution conditionnelle

    Schéma illustrant l'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

    Schéma illustrant la structure switch de C

    structure "case" de Pascal

    Schéma illustrant la 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 répétitive

    Schéma illustrant les exécutions répétitives

  • 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

    Exécutions de sous-programmes

    Schéma illustrant les exécutions de sous-programmes

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.

19. Mais ce n'est pas facile, par exemple Fortran 90 utilise le mot "type" et Ada le mot "agrégat" avec des significations différentes de celles utilisées ici.

fermer cette précision

1.6.1. 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. "

1.6.2. 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" :

type : fiche_étud = agrégat_de
        nom, prénom : textuel ; (on indique les types des composantes)
        âge : numérique ;
    fin_agrégat fiche_étud (aspect "complètement parenthésé" : mot-clé fermant une structure)
variable p : pointeur_sur fiche_étud ;
variables lauréat, candidat : fiche_étud ;

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

20. Nous avons fait ce choix parce que ce comportement correspond à l'expérience de la majorité des programmateurs.

fermer cette précision

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

21. Nous utilisons, à dessein, une notation peu usitée ; ainsi nous serons moins tentés par les reminiscences d'un langage particulier.

fermer cette précision

On pourra aussi définir des types énumérés, par énumération des valeurs possibles :
type etat_de_file = (vide, pleine, normale)

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"

22. Afin de faciliter la reconnaissance, nous systématiserons la dénomination en faisant précéder les noms de type par le préfixe "ty_".

fermer cette précision

23. La seule exigence pour ce dernier type étant qu'il existe une relation d'ordre entre valeurs appartenant à ce type.

fermer cette précision

1.6.3. Les instructions exécutables et de contrôle


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

  • 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).
    fonction max (x, y, "ty_valeur_à_comparer": Entrées)
                    : résultat : "ty_valeur_à_comparer"
        si x < y alors
            max Symbole : affectation x
        sinon
            max Symbole : affectation 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).

Exemple d'exécution séquentielle

Exemple d'exécution séquentielle

les instructions sont exécutées dans l'ordre où elles apparaissent dans ce programme (ordre des N°), les colonnes indiquent la valeur de chaque variable après exécution de l'instruction correspondante. (on suppose que x, y, z, t sont des variables entières). Que deviendraient ces valeurs si les instructions étaient exécutées dans l'ordre 1, 2, 4, 5, 3, 6 ?

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

Erreur courante lors des exécutions séquentielles

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

représentation statique en FORTRAN 77

FORTRAN 77 (standard) n'a ni pointeur, ni allocation dynamique, ni type agrégat, la seule implémentation possible est de gérer, en parrallèle, plusieurs tableaux : les éléments de même indice, pris dans chacun de ces tableaux, constituent l'élément de liste, l'un contenant la valeur de clé, l'autre l'indice de l'élément suivant dans la liste ; on écrira :

Déclarations :

INTEGER         Lx_nom                                  longueur maximale des noms
INTEGER         Nx_Enf                                  nombre maximal d'enfants
PARAMETER       ( Lx_nom = 15, Nx_Enf = 12 )
CHARACTER       *(Lx_nom) t_Nom (1:Nx_enf)              tableau des "noms"
INTEGER         t_p_suiv (1:Nx_enf)                     tableau des "pointeurs vers élément suivant"
INTEGER         NIL
PARAMETER       ( NIL = 0 )
INTEGER         Hd_ptr
INTEGER         p, pp

Partie exécutable :

Hd_ptr = 1              allocation et liaison de 2 éléments de liste
p = 2
t_p_suiv(Hd_ptr) = p
t_p_suiv(p) = NIL
...
pp = p
p = t_p_suiv(p)         considérer l'élément suivant de celui pointé par p

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 Symbole : affectation 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

26. Il y eut débat entre tenants des langages "avec pointeurs" et ceux des langages "sans pointeur". Aujourd'hui, la plupart des langages dispose de la notion de pointeur, même si, par souci de sécurité, les plus modernes en restreignent énergiquement l'usage.

fermer cette précision

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

27. Un pointeur désigne une cible (target en anglais)

fermer cette précision

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.

28. Le rôle du pointeur est à mettre en parallèle avec celui des indices utilisées dans la gestion des tableaux.

fermer cette précision

L'ambiguïté sémantique est exemplaire dans l'affectation pA Symbole : affectation 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 Symbole : affectation 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 Symbole : affectation 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).

Exemple de pointeurs et d'objets pointés en mémoire

Exemple de pointeurs et d'objets pointés en mémoire

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

29. Oublions l'usage "bricolé" des pointeurs imposés par certains compilateurs pour gérer des objets de grande taille, procédé inventé afin de pallier aux déficiences du système d'adressage du processeur ou de l'environnement (MS/DOS par exemple).

fermer cette précision

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.

30. La communication implicite de données à l'aide de variables globales est source de trop d'erreurs pour qu'il en soit question ici ...

fermer cette précision

Les arguments d'un sous-programme peuvent servir à :

  • passer des informations du programme appelant vers le sous-programme (argument d'Entrée)
  • renvoyer des informations du sous-programme vers le programme appelant (argument de Sortie)
  • passer des informations du programme appelant vers le sous-programme, informations que celui-ci modifie et retourne modifiées au programme appelant (argument d'Entrée/Sortie)
1.8.6.1. 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 Symbole : affectation y; max Symbole : affectation x
    sinon
        min Symbole : affectation x; max Symbole : affectation 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é.
1.8.6.2. Exemple 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...

1.8.6.3. Exemple 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);
1.8.6.4. Exemple 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);
1.8.6.5. Exemple 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.

1.8.6.6. Exemple 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é

On considère l'équation Ax² - 2x + C = 0. On donne à C la valeur de 1/A (ce qui correspond au cas de la racine double x = 1/A).
Pour A variant de 1 à 30 imprimer le signe du discriminant Δ.
Faire une statistique sur un échantillon plus important en imprimant le nombre de cas : Δ positif, Δ nul et Δ négatif.

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

3 variables "réelles" x, y, z ; on leur affecte les valeurs :« x = 1», «y = 1020», «z = -1020».
Imprimer les résultats de «x + y + z», «y + x + Z», «y + z + x», «x + (y + z)», «(x + y) + z»

1.9.3. Série en 1/n²

Ecrire et mettre au point un programme qui lit un nombre n dans le fichier standard d'entrée puis calcule la somme des carrés des inverses n premiers entiers. On choisira n assez grand ≈ 100 000.
On programmera la somme directe : 1 + 1/4 + 1/9 + 1/16 + ... + 1/100 000²
ainsi que la somme rétrograde 1/100 000² + 1/99 999² + 1/99 998² + ... + 1
Comparer ces résultats entre eux ainsi qu'à la valeur théorique de la somme infinie : π²/6

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

On recherche π comme limite des périmètres de polygones réguliers convexes inscrits dans un cercle de rayon 1/2 quand on fait tendre le nombre de côtés vers l'infini. Il est aisé de montrer que quand on passe du polygone à n côtés au polygone à 2n côtés, la relation de récurrence entre la longueur an des côtés est :
a2n = √(1/2 (1 - √(1 - an²))). On peut initialiser la récurrence avec a6 = 1/2.
Imprimer la suite des valeurs Pn des périmètres. Comparer avec la suite des valeurs calculées à partir de la relation de récurrence théoriquement équivalente : a2n = an/√(2 (1 + √(1 - an²)))

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

On est heureux d'apprendre dans le cours d'Analyse que sin(α) peut être calculé à l'aide du développement :
sin(α) = α - α3/3! + α5/5! - ... + (-1)nα2n+1/(2n+1)! + ... (série dont le rayon de convergence est infini)
et que, d'autre part, l'erreur commise en tronquant une série alternée absolumment décroissante est inférieure à la valeur absolue du premier terme négligé.
Calculer la valeur de sin(31.415926535) par cette méthode. On recherchera une précision de 10-4. Il pourra être instructif d'imprimer les valeurs succesives des termes de la somme. N.B. 31.415926535 ≈ 10 π

Les Shadoks essaient leur fusée :

"leur fusée n'était pas très au point, mais ils avaient calculé qu'elle avait quand même UNE CHANCE SUR UN MILLION DE MARCHER. Et ils se dépêchaient de bien rater les 999 999 premiers essais pour être sûr que le millionième marche. "

Les devises Shadoks : plus ça rate, plus on a de chances que ça marche

"Car tel est le principe de base de la logique Shadok :
Ce n'est qu'en essayant continuellement que l'on finit par réussir."

mais quelqu'un a-t'il jamais programmé ainsi ???