Pourquoi l’algorithmique ?

L’algorithmique est-elle pertinente ?
samedi 22 mai 2010
par  Alain BUSSER

Qu’est-ce que la démarche algorithmique ? Question importante puisque l’expression est citée dans le programme de Seconde. Un algorithme est défini comme

Une suite d’instructions dont l’exécution en séquence mène à la résolution d’un problème.

Des mots importants pour décrire un algorithme sont donc les suivants :

  • ensuite
  • après ça
  • pour cela, on va devoir
  • finalement
  • on recommence
  • en boucle
  • tant que
  • jusqu’à

etc. : Des mots faisant référence au temps qui passe. Un algorithme fait référence à une chronologie parce qu’un chercheur seul (comme un élève devant sa copie) ne peut pas tout faire en même temps. Mais pour une équipe de chercheurs (ou des élèves participant au Rallye mathématiques) la méthode algorithmique n’est absolument pas nécessaire : Elle n’est pas adaptée au calcul parallèle...

Dans la suite de cet article, on va choisir un problème relativement simple pour comparer les différentes méthodes de résolution de ce même problème :


Calculer la moyenne de 100 nombres pseudo-aléatoires compris entre 0 et 1.

Historique

Sans avoir lu les écrits d’Euclide ni ceux d’Ératosthène, il paraît évident que ces deux-là connaissaient et pratiquaient la méthode algorithmique, au sens d’une séquence d’instructions (donc énoncées à l’impératif) :

  • Lorsque Euclide calculait un pgcd, c’était par une suite de soustractions successives ;
  • Le crible d’Ératosthène se construit étape après étape.

Chez Al-Khawarizmi, les méthodes exposées pour résoudre des équations utilisent des étapes qui doivent être parcourues dans l’ordre si on veut aboutir à la solution.

Chez Descartes, dans le discours de la méthode, on trouve cette description de l’algorithmique (sans le dire) :


diviser chacune des difficultés que j’examinerais, en autant de parcelles qu’il se pourrait, et qu’il serait requis pour les mieux résoudre.

La première informaticienne, Ada Lovelace, proposait un algorithme de calcul des nombres de Bernoulli. Il est vraisemblable que cet algorithme fonctionnait en séquence tout simplement parce qu’il était destiné à la machine analytique de Charles Babbage, laquelle utilisait des cycles comme la mise en mémoire de résultats intermédiaires et la récupération ultérieure de ces résultats.

Le tout premier ordinateur, ENIAC, était financé par un projet parallèle au projet Manhattan, auquel participait John von Neumann. L’architecture proposée par celui-ci est de très loin la plus répandue dans les ordinateurs, or elle impose la démarche algorithmique. D’où l’idée selon laquelle programmer un ordinateur, ça commence par l’algorithmique.

Mais ce n’est pas toujours vrai : Le calcul parallèle est à peu près incompatible avec l’algorithmique, ainsi que l’informatique quantique, et les processseurs vectoriels (utilisés dans les superordinateurs) rend celle-ci désuète. Or le succès grandissant des ordinateurs bi-cœurs et du calcul par réseau mettent le calcul parallèle de plus en plus à la mode.

Algorithmique

Dans l’exemple du calcul de la moyenne de 100 nombres aléatoires, la démarche algorithmique (pour la somme des 100 nombres) consiste à effectuer dans l’ordre les opérations suivantes :

  1. Créer une variable numérique qui contiendra la somme ;
  2. Initialiser cette variable à 0 ;
  3. Répéter 100 fois le point suivant :
  4. Ajouter à la variable en question, un nombre pseudo-aléatoire entre 0 et 1 ;
  5. Une fois qu’on a fini, diviser la somme des 100 nombres par 100.

En JavaScript (sous CaRMetal) cela donne ceci :

C’est la syntaxe de la boucle qui est complexe en JavaScript...

Et en Python (sous eric4) :

On remarque qu’il a fallu initialiser la variable somme à « 0. » au lieu de « 0 » pour que Python la considère comme réelle et non entière. On remarque également la simplicité de la boucle sous Python, « range(1,100) » désignant une liste d’entiers, comme dans l’onglet « calcul vectoriel ».

Or pour beaucoup d’élèves de Seconde,

  • penser à créer une variable,
  • penser que pour additionner 100 nombres, il faut additionner les deux premiers d’entre eux, puis additionner le troisième à la somme partielle, etc.
  • Passer de cette constatation à la réalisation sur machine,

ce n’est pas facile du tout !

On peut dire que la démarche algorithmique n’est pas naturelle pour un élève entrant en Seconde. D’où l’intérêt de se poser la question de la pertinence de ladite démarche, et de la nécessité de la pratiquer ou la faire pratiquer.

Pour finir cet onglet, je cite Guillaume Connan (article pour Repères) :


Il faut donc être extrêmement attentif à la chronologie des instructions données. C’est un exercice intéressant en soi mais pas
sans danger (c’est d’ailleurs la source de la plupart des « bugs » en informatique).

Langages fonctionnels

Le même algorithme en Xlogo est plus simple à écrire, et à lire, parce que la boucle est effectuée sans faire référence à son indice, donc de façon statique : On répète 100 fois l’addition, sans avoir à imaginer la valeur que prend l’indice à chacune des répétitions :

LOGO, comme LISP, OCamL, Haskell etc. est un langage fonctionnel, où la notion d’affectation est superflue, et la « programmation » entièrement basée sur la récursivité. Disons qu’en programmation fonctionnelle [1], au lieu de dire ce que doit faire la machine, on lui décrit la situation, et on la laisse se débrouiller pour trouver la réponse à partir de cette description. Cette façon de programmer permet donc de se passer de la démarche algorithmique. La version programmation déclarative de l’algorithme d’Euclide donne quelque chose comme ceci :


Le pgcd de a et b est égal au pgcd de a et a-b.

On n’y voit aucune affectation, aucune chronologie, et pourtant traduit en JavaScript on a bien un programme (extrait de cet article) :

Voici comment OcamL Light calcule la moyenne de 100 nombres aléatoires :

Alors, vaut-il la peine de contourner la difficulté que présente pour certains élèves la démarche algorithmique, et contourner la démarche elle-même en utilisant un langage fonctionnel ? Là encore je cite Guillaume Connan :


Cependant, utiliser des algorithmes récursifs nécessite de maîtriser un tant soit peu... l’axiome de récurrence. Or cette étude a été réservée jusqu’à maintenant aux seuls élèves de Terminale S. L’étude des suites débute depuis de nombreuses années en Première et chaque professeur a fait l’expérience des difficultés des élèves à maîtriser cette notion.

Rajoutons qu’en évoquant la récursivité, et en n’évoquant pas l’affectation de variables, on se met totalement en porte-à-faux par rapport aux impératifs du programme...

Ceci dit, même si la quasi-totalité des logiciels connus sont conçus avec des langages impératifs, donc grâce à l’algorithmique, quelques grandes créations logicielles ont été faites avec des langages fonctionnels :

  • Les éditeurs de texte emacs et TeXmacs sont écrits en Scheme qui est une variante de LISP, donc fonctionnelle dans son principe.
  • Il en est de même de plusieurs logiciels de calcul formel, notamment Yacas, Derive et Maxima.
  • Le logiciel de démonstrations automatiques Coq et son interface CoqIde sont écrits en OCamL.

Calcul vectoriel

Sans aller jusqu’à la récursivité, on peut rendre les boucles statiques en utilisant des listes ordonnées (appelées vecteurs) ce qui contourne aussi la difficulté. Par exemple en SciLab, la boucle se rédige

for i=1:100

La notation « 1:100 » désigne la liste des 100 premiers entiers dans un logiciel de calcul matriciel tel que MatLab, Octave, SciLab ou Euler Math Toolbox (le double-point se lit « jusque »). On a donc un indice dans un tableau de nombres : Les 100 valeurs n’apparaissent pas à des moments successifs, mais sont stockées une fois pour toutes à différents emplacements d’un même tableau.

Mais avec SciLab il n’est même plus nécessaire d’écrire la boucle, on peut directement travailler sur le tableau ! Ci-dessous, le tableau des 100 nombres aléatoires est stocké dans la variable a, et la somme des éléments de a s’obtient par sum(a) :

Comme le montre la dernière ligne SciLab ci-dessus, on n’a même pas besoin de calculer la somme et la diviser par 100, puisque SciLab permet également de calculer directement la moyenne par mean.

Le calcul par un processeur vectoriel comme on en trouve dans les superordinateurs fonctionne de cette manière : Au lieu d’opérer sur des nombres, ils opèrent sur des vecteurs c’est-à-dire des tableaux de nombres.

Mais SciLab n’est pas le seul outil qui permet de calculer d’un coup une moyenne de 100 nombres : Les tableurs ont plus ou moins spécialement été conçus pour ça :

  1. On entre dans la cellule A1 la formule « =ALEA() » ;
  2. On la copie vers le bas, jusqu’à A100 ;
  3. On sélectionne une cellule vide, dans laquelle on entre la fonction « =MOYENNE(A1:A100) »

Certes il y a bien eu une itération là-dedans, mais c’est le tableur qui s’en est chargé. L’élève qui manipule le tableur ne voit pas l’itération, et ne suit pas une démarche algorithmique...

Il en est de même pour la calculatrice graphique : Pour une Ti, on peut entrer

Seq(random(),i,1,100) \rightarrow L1

Ensuite, bien qu’on puisse écrire un programme pour calculer la moyenne des nombres stockés dans L1, il suffit d’aller dans le menu statistiques, et de choisir « calc » puis « 1-Var stat » pour avoir l’affichage de la moyenne (avec en bonus les quartiles) : Là encore, c’est la calculatrice qui se charge du travail...

Certes, les élèves les plus curieux (et passionnés) adoreront qu’on leur explique comment leur calculatrice calcule une moyenne, mais les autres (et ils risquent d’être nombreux) vont dire « à quoi bon se fouler alors que de toute façon la calculatrice le fait ? »

Dans ce cadre, la pertinence de la démarche algorithmique peut se comparer à l’opinion d’une large proportion de conducteurs qui ne jugent pas utile d’être des experts de la mécanique pour piloter leur voiture !

Calcul parallèle

Depuis que la vitesse des processeurs plafonne à 2 GHz, pour construire des ordinateurs plus rapides, on met plusieurs « cœurs » dans les processeurs (on n’a d’ailleurs pas attendu de dépasser le GHz pour cela). Ce qui mine de rien remet au goût du jour le calcul parallèle, rival de l’architecture de Von Neumann qui incarne aujourd’hui la démarche algorithmique. Et même avec un processeur unique, la programmation événementielle sort du contexte temporel qui préside à la démarche algorithmique puisqu’on attend un évènement pour lancer le processus auquel il doit répondre.

Or dès lors qu’il y a deux processeurs à travailler en même temps sur des variables communes, il y a des risques de conflit, comme le montre l’exemple suivant en Scratch (langage spécialisé dans le calcul parallèle) :

La scène comprend deux lutins, des robots, appelé Rôôô et Beau (évidemment). Le programme de Rôôô est celui-ci :

et celui de Beau celui-ci :

Bien malin qui saura deviner la valeur de x après le clic sur le drapeau vert ! En effet tandis que Rôôô essaye de forcer la valeur de x à être égale à 2, Beau essaye en même temps de forcer la même valeur à être égale à 3. Le pauvre x en est tout écartelé !

Exercice

Avec deux variables x et y, et le programme de Rôôô suivant :

et le programme de Beau que voici :

Deviner les valeurs que prennent x et y après le clic sur le drapeau !

Ce genre de conflit (presque complètement en dehors du champ de l’algorithmique) n’a rien de théorique, puisque l’article sur Descartes cité précédemment fait l’objet en ce moment d’un blocage dû à une écriture en commun par des auteurs qui ne sont pas d’accord entre eux sur le contenu de ce qu’ils écrivent :

À noter que pour résoudre ce conflit, le site wikipedia utilise bel et bien le langage de l’algorithmique :

La synergie

L’intérêt du calcul parallèle s’explique en logique épistémique par la notion de synergie. En logique épistémique, la vérité d’une proposition p n’est pas le seul sujet d’intérêt, mais également les connaissances que des agents a, b etc. ont de la vérité de p. On note K_a p (la letrre K est l’initiale du verbe anglais to know, « savoir ») le fait que l’agent a sait que p est vrai (ce qui bien entendu présuppose que p soit vrai !) et de même K_b p signifie que b est au courant que p est vrai.

Par exemple, si p est la proposition x=2 (x étant une variable), et a et b des processeurs, K_a(x=2) exprime le fait que la variable x est effectivement égale à 2, mais aussi que celle-ci est située dans une zone de mémoire à laquelle le processeur a a accès (dans Scratch, cela signifie que soit x est une variable propre à l’agent a, soit x est une variable commune aux deux agents). En informatique théorique, la logique épistémique gère donc la notion d’accessibilité d’un fait.

Voici quelques théorèmes de la logique épistémique à deux agents :

K_a p \Rightarrow K_{\left\{a,b\right\}}p

(tout ce que sait a est une connaissance de l’équipe \left\{a,b\right\})

K_b p \Rightarrow K_{\left\{a,b\right\}}p

(idem pour b)

K_a p \cup K_b p \Rightarrow K_{\left\{a,b\right\}}p

(tout ce que connaît un agent est une connaissance de l’équipe)

Mais la réciproque n’est pas vraie ! On parle de connaissance distribuée pour ce qui peut être inféré par le travail en équipe des deux agents mais qu’aucun agent ne saurait inférer seul, par manque de connaissance.

Ce phénomène de synergie peut se résumer à ceci :


Une équipe vaut plus que la somme de ses constituants.

L’un des buts du Rallye mathématiques est justement de montrer par la pratique qu’ensemble, les élèves de Troisième-Seconde sont meilleurs en maths que séparément...

En fait, l’étude des processeurs concurrents se fait par des outils très différents de l’algorithmique, surtout lorsqu’il y a beaucoup de processeurs, comme dans les réseaux de neurones. Dans ce cas l’outil mathématique le plus approprié semble être les automates cellulaires. On peut considérer que dans un de ces superordinateurs à multiprocesseurs, au lieu de partager le travail dans le temps comme le fait l’algorithmique, on le partage dans l’espace, entre les processeurs. Or l’espace a plus de dimensions que le temps (typiquement, 4 dans les cablages optimaux entre processeurs).

Deux exemples de ces superordinateurs distribués :

Le projet SETI, au but un peu original...

Plus mathématique (arithmétique pour être précis), le GIMPS...

Et, avec moins de postes en réseau local, le rendu du film Shrek 3 aurait pris des décennies s’il n’avait pas été fait en calcul massivement parallèle...

La démarche algorithmique n’est donc pas indispensable dans la formation des futurs programmeurs de génie que sont en puissance, les élèves qui entrent en Seconde. La question se pose alors de savoir ce qu’on veut, et pourquoi on le veut. Hypothèse personnelle : La raison de cette introduction de l’algorithmique en Seconde pourrait bien être le souci de préparer les élèves (essentiellement scientifiques) qui auront des TP de programmation dans le supérieur (université, prépa...), TP au cours desquels ils montrent en général une méconnaissance quasi-totale de la démarche algorithmique. Pour ces étudiants allergiques aux TP d’algorithmique, on devrait peut-être envisager une modification profonde de l’enseignement de l’algorithmique dans le supérieur... À défaut, autant reporter la difficulté en « préparant les élèves à la prépa » dans le domaine de la programmation, en insufflant des notions d’algorithmique à doses homéopathiques dès la Seconde (pour avoir le temps d’approfondir ces notions d’ici le Bac).

Le bilan d’une année de Seconde passée à faire (beaucoup) de l’« algorithmique » commence seulement en fin d’année à être positif : Ayant constaté l’énormité de la difficulté pour certains élèves de Seconde, des boucles, je leur ai dit que je me sentais stoppé net dans mon élan par un gros mur, au pied duquel ils m’avaient placé. "Dans ce cas, il y a deux posibilités :

  1. Ou bien on fait demi-tour et on cherche un autre chemin (abandonner la démarche algorithmique et se remettre au tableur)
  2. Ou bien on cogne dans le mur jusqu’à ce qu’on réussisse à faire un trou dedans et passer par cette brêche (faire encore plus, et surtout encore plus souvent, de l’algorithmique)"

Malgré de gros doutes, il semble que le choix de la seconde méthode ait été le bon, comme en témoigne l’amélioration des résultats à une interrogation donnée deux fois dans l’année scolaire, avec presque le même sujet, et jugée par les élèves, bien plus facile la seconde fois que la première ; comme en témoigne aussi la réussite des deux derniers TPs de l’année scolaire (ici et ici)


[1ainsi qu’en programmation logique comme avec Prolog


Commentaires

Logo de seb
samedi 12 octobre 2013 à 13h54 - par  seb

Sauf que Algorithmique ne signifie absolument pas séquentialité ! Dans le vaste monde de l’Algorithmique il y a tout un pan sur l’algorithmique distribuée et l’algorithmique parallèle. D’autre part, dire qu’on n’a plus besoin d’algorithmique séquentielle n’est pas raisonnable.

Annonces

Prochains rendez-vous de l’IREM

Séminaire EDIM-IREM

- Mercredi 14 juin 2017, 14h-18h, PTU, Saint-Denis, salle S23.6
- Mercredi 21 juin 2017, 14h-18h, 146 route de Grand-Coude, Saint-Joseph


Brèves

Décès de Roger Mohr

mardi 27 juin

On sait bien que Nicolas Bourbaki n’était pas le nom d’une personne mais le pseudonyme d’un groupe. L’équivalent en informatique théorique est Claude Livercy, auteur de la théorie des programmes. Roger Mohr était un des membres de Claude Livercy.

À travers les labyrinthes : algorithmes et fourmis

dimanche 1er septembre 2013

Quand les chercheurs mettent au point des modèles d’optimisation et de recherche de plus court chemin qui s’inspirent du comportement de masse de colonies de fourmis...
À écouter : Sur les Épaules de Darwin, émission diffusée sur France Inter samedi 31 août 2013.

Rencontres Mondiales du Logiciel Libre à St-Joseph

mardi 20 août 2013

Les RMLLd se dérouleront pour la 2e fois à Saint-Joseph du 22 au 25 août.
C’est une opportunité pour les élèves qui suivent la spécialité ISN et les passionnés d’informatique.

Voici pour le samedi et le dimanche quelques interventions choisies :
- http://2013.d.rmll.info/Raspberry-votre-ordinateur-au-format-carte-de-credit?lang=fr
- http://2013.d.rmll.info/Materiel-libre-et-DIY?lang=fr
- http://2013.d.rmll.info/Arduino-de-l-electronique-libre?lang=fr

Noter aussi les conférences Art et Culture du dimanche, ainsi qu’une conférence plus engagée.

Le programme complet se trouve ici. Une radio sera ouverte pour l’occasion.
Des plaquettes à distribuer se trouvent ici.

Hyper-vidéos pour l’algorithmique au lycée

dimanche 19 août 2012

Olivier Roizès, à la demande de l’ADIREM, a réalisé une collection d’hyper-vidéos de présentation de logiciels et environnements de programmation. Ces hyper-vidéos, c’est-à-dire des vidéos contenant des éléments clicables, devraient être utiles aux enseignants désireux de se familiariser avec Python, CaRMetal, R, Rurple, Scilab ou Xcas.

Ouverture du SILO

mardi 1er novembre 2011

Le SILO (Science Informatique au Lycée : Oui !) est un espace collaboratif documentaire de partage et de formation collégiale, à destination des professeurs appelés à enseigner l’informatique au lycée.

Une initiative du CNDP, de l’INRIA et de Pasc@line, à laquelle se sont associés SPECIF, fuscia, EPI et ePrep.

Sur le Web : Site du SILO

Introduction à la science informatique

lundi 12 septembre 2011

Le CRDP de Paris publie le premier ouvrage destiné aux professeurs chargés d’enseigner la nouvelle spécialité « Informatique et sciences du numérique » en Terminale S à la rentrée 2012. Cet ouvrage a été coordonné par Gilles Dowek, directeur de recherche à l’INRIA.

Sur la création de la spécialité ISN, on pourra également consulter l’interview donnée au Café pédagogique par l’inspecteur général Robert Cabanne.

Sur le Web : CRDP de Paris

Deux publications sur l’algorithmique

samedi 17 octobre 2009

L’IREM d’Aix-Marseille publie une brochure de 73 pages, téléchargeable librement, intitulée Algorithmes et logique au lycée. Ces notions sont illustrées et déclinées sur des exercices du programme de spécialité mathématique en série L, mais sont adaptables aux programmes à venir.

Le hors série thématique n° 37 du magazine Tangente, disponible actuellement en kiosque, s’intitule « Les algorithmes. Au cœur du raisonnement structuré ». Extrait de l’éditorial : « La rédaction de Tangente a conçu la quasi-totalité de ce hors série thématique pour qu’il puisse être lu par des élèves de Seconde ».

Une carte mentale pour l’algorithmique

jeudi 10 septembre 2009

Sur son site, Jean-Jacques Dhénin a publié une carte mentale géante qui renvoie vers plus de 30 documents en ligne sur l’algorithmique. Tout ce qu’il faut — et même davantage — pour faire face au nouveau programme de Seconde !

Un catalogue libre d’algorithmes pour le lycée

dimanche 30 août 2009

Guillaume Connan, de l’IREM de Nantes, publie un catalogue libre de 119 pages d’algorithmes pour le lycée. Sur son site très riche, on trouvera d’autres documents en rapport avec l’algorithmique, notamment sur l’utilisation des langages fonctionnels au lycée et sur la comparaison programmation fonctionnelle/programmation impérative.

L’algorithmique à l’IREM de Lille

vendredi 26 juin 2009

Le groupe AMECMI de l’IREM de Lille vient de mettre en ligne des ressources importantes au service des professeurs de Seconde :

- Algorithmique et programmation (Emmanuel Ostenne)
- Bibliographie amoureuse de l’algorithmique (Alain Juhel)

Statistiques

Dernière mise à jour

lundi 24 juillet 2017

Publication

759 Articles
Aucun album photo
133 Brèves
11 Sites Web
132 Auteurs

Visites

306 aujourd'hui
292 hier
2063396 depuis le début
12 visiteurs actuellement connectés