Document ressource Algorithmique

Pour une pratique active de l’élève

Citons à nouveau le projet de programme pour la classe de Seconde :
L’algorithmique a une place naturelle dans tous les champs des mathématiques et les problèmes posés doivent être en relation avec les autres parties du programme (fonctions, géométrie, statistiques et probabilité, logique) mais aussi avec les autres disciplines ou la vie courante.
La découverte de l’algorithmique peut avantageusement avoir lieu tout au long de l’année et gagne à être mise en œuvre par des situations variées, notamment en diversifiant les supports d’activités des élèves. On pourrait très bien commencer par exécuter les algorithmes1 sans ordinateur à la main sur papier, avec les mains, avec les pieds, ou avec des objets etc. Par ailleurs, même si cela diffère entre la calculatrice et l’ordinateur, il convient de lier la gestion de mémoire à des actes liés aux manipulations concrètes d’écriture, d’affectation et d’affichage de données.

Organisation des enseignements

L’enseignement de l’algorithmique ne relève pas, à ce niveau, de cours spécifiques ; au contraire, l’introduction de chaque nouvel élément (variable, boucle, itération, etc.) devrait apparaître lors de la résolution de problèmes pour lesquels les dé-marches habituelles sont malcommodes ou peu performantes : par exemple dans le cas de répétition d’une tâche, ou dans le cas d’un traitement trop long pour être envisagé « à la main ». Ces situations peuvent être rencontrées lors de l’extension à des cas plus généraux de situations déjà rencontrées : recherche du pgcd de nombres très grands, tri d’un très grand nombre de valeurs numériques, simulations sur des échantillons de grande taille…
Une piste envisageable pourrait être la réécriture d’un algorithme simple, dont la complexification – dans une mesure raison-nable – fait écho à de nouvelles notions rencontrées pendant l’année ou à de nouveaux questionnements sur la nature de l’objet étudié. Par exemple : écrire un algorithme permettant de créer un tableau de valeurs d’une fonction, puis se poser les questions : comment modifier cet algorithme pour trouver les extremums de cette fonction ? puis, l’adapter pour trouver les variations de cette fonction ? enfin, dans quelle mesure cet algorithme est-il fiable ?…
Il serait souhaitable d’intégrer l’écriture d’algorithmes dans tous les domaines du programme :
– fonctions : étude numérique et asymptotique;
– géométrie : les questions d’affichage, de positionnement et de déplacement d’objets géométriques simples (points, seg-ments, cercles) peuvent être un champ d’investigation très riche
– statistique : questions de tris, détermination de certains indicateurs (médiane, quartiles) ;
– probabilités : la modélisation de certains phénomènes à partir de fréquences observées : méthode dite de Monte-Carlo, etc. ;
– numérique : le traitement des nombres permet d’aborder des problèmes de comparaisons et de taille des nombres, d’exactitude dans les calculs, etc.
Ne pouvant être exhaustif, ce document n’apportera que quelques éclairages sur ces thèmes.
La variété des supports et les moyens de les mettre en œuvre dans la classe sont des éléments indispensables à la mise en place de cet enseignement.
Il est important de noter que l’algorithmique modifiera profondément le rapport entre l’élève et les outils ou instruments auxquels il sera confronté dans son environnement scolaire et particulièrement ceux habituellement identifiés comme issus du monde des TIC dans l’enseignement (calculatrices, ordinateurs, logiciels mais aussi divers objets comme les appareils photos numériques, etc.).
Enfin, il faut avant tout éviter de confronter les élèves à des difficultés trop importantes ; en effet, la classe de seconde est une classe de détermination et il ne s’agit pas d’y former des programmeurs mais de faire en sorte que les mathématiques et l’algorithmique soient au service d’activités de résolution de problèmes pour les sciences.

Pratiques de l’élève

La pratique de l’algorithmique ne se résume pas à l’écriture de programmes ; il serait même judicieux de ne pas commencer par là. Il convient donc de proposer aux élèves des situations, activités et organisations pédagogiques variées.
Les travaux proposés pourront être conçus dans une perspective d’action de l’élève et devront être présentés le plus souvent possible dans un cadre plus large que celui de la simple réalisation isolée d’un programme. Ils pourront par exemple s’ins-crire dans la durée et dans une organisation individuelle et/ou collective.
Voici quelques exemples de supports d’activités : relectures d’algorithmes, complexifications progressives, transpositions d’algorithmes utilisant différents types de langages, progressivité dans le choix et l’utilisation des outils de programmation…
Par ailleurs, il conviendrait de ne pas négliger la richesse de l’apprentissage à partir d’algorithmes erronés. Le travail de cor-rection, de recherche de dysfonctionnements de certains algorithmes, l’étude des cas particuliers sont des pistes qu’il conviendrait d’explorer.
Enfin, l’écriture d’algorithmes pourrait par ailleurs être l’occasion de développer le travail en équipe dans le cadre de la réali-sation de petits projets.
1 De tels exemples seront proposés dans la suite du document ressource.

Supports de programmation

Comme aucun logiciel ou langage n’est imposé par le programme, on montrera ci-après différents types d’environnements de programmation. Les calculatrices graphiques programmables peuvent être exploitées grâce à leur commodité d’usage en classe entière. Cependant, leurs limites dues à leur petite taille et leur capacité mémoire incitent à proposer aux élèves des ac – tivités s’appuyant sur des logiciels utilisables sur ordinateur. Une large part des exemples proposés ci-après est parfaitement traitable avec des calculatrices comme support.
Une piste intéressante pourrait être d’organiser l’enseignement autour d’une progressivité dans les outils utilisés au cours de l’année (sans pour autant les multiplier) en traitant des exemples sur plusieurs environnements.
Il peut être également intéressant de mettre en avant le fait que la complexification de l’algorithme détermine de manière plus ou moins ouverte le choix de l’instrument comme par exemple pour les problèmes liés :
– au temps de calcul ;
– à la nature, la taille ou la précision des nombres utilisés ;
– à la lisibilité de l’algorithme ;
– à la nature de la sortie.
Nombreux sont les logiciels qui peuvent être utilisés2 : des logiciels dédiés (comme SCRATCH, EXECALGO ou LI-NOTTE…), aux logiciels de programmation (PYTHON…) ou liés au calcul scientifique (SCILAB…) en passant par les logi-ciels de calcul formel (XCAS, MAXIMA, WIRIS…) qui proposent un module de programmation. Ces derniers permettront de travailler sur des types de données plus spécifiques (très grands nombres, expressions algébriques…). On pourra à l’occa-sion utiliser le tableur qui, s’il traduit parfaitement les instructions conditionnelles, tend cependant à cacher les itérations sous les opérations de recopie de formules.
On se reportera à la présentation détaillée de quelques logiciels qui figure à la fin de ce document.
Les exemples proposés dans ce document sont donc déclinés dans différents environnements.

Évaluation des pratiques

L’évaluation des pratiques en Algorithmique peut s’organiser autour d’une évaluation par compétences qui ne conduira pas nécessairement à une note spécifique chiffrée.
Les activités menées dans le cadre de la pratique de l’algorithmique peuvent servir de support d’évaluation des compétences liées, d’une part, aux trois modalités fondamentales de l’activité en algorithmique qui sont :
a) analyser le fonctionnement ou le but d’un algorithme existant ;
b) modifier un algorithme existant pour obtenir un résultat précis ;
c) créer un algorithme en réponse à une problème donné.
et, d’autre part, à la résolution de problèmes telles que :
d) modéliser et s’engager dans une activité de recherche ;
e) faire une analyse critique ;
f) pratiquer une lecture active de l’information (critique, traitement), en privilégiant les changements de registre (graphique, numérique, algébrique, géométrique) ;
g) communiquer à l’écrit et à l’oral.

Une initiation à l’algorithmique

De quoi va-t-on parler ?

Le mot « algorithme » vient du nom de l’auteur persan Al-Khuwarizmi (né vers 780 – mort vers 850) qui a écrit en langue arabe le plus ancien traité d’algèbre « abrégé de calcul par la complétion et la simplification »3 dans lequel il décrivait des pro-cédés de calcul à suivre étape par étape pour résoudre des problèmes ramenés à des équations4.
Dans un premier temps rédiger un algorithme consiste à décrire les différentes étapes de calcul pour résoudre un problème algébrique, numérique ou décisionnel.
Des exemples souvent repris pour illustrer ces différents aspects, comme le rendu de monnaie pour le volet numérique, ou encore les recettes de cuisine. On trouve encore des algorithmes dans des situations de la vie courante (s’habiller) ou profes-sionnelle (ainsi, la conduite d’un train, la consultation d’un catalogue de bibliothèque, etc.).
Plus généralement le mot « algorithme » désigne tout procédé de calcul systématique voire automatique. S’ajoute à cela la notion de « finitude ».
On définit parfois les algorithmes de la manière suivante : « un algorithme est une suite finie de règles à appliquer dans un ordre déter-miné à un nombre fini de données pour arriver, en un nombre fini d’étapes, à un certain résultat et cela indépendamment des données. »5 Le ré-sultat doit donc s’obtenir en un temps fini.
À propos des « règles à appliquer », il faut entendre un traitement fait sur des données imposé par une suite « d’instructions » visant à transformer ces données pour arriver au résultat visé.
Ces « instructions » sont de natures diverses selon le type de données au départ. C’est ce que nous allons préciser.

Les éléments de base d’un algorithme simple

Les trois étapes

D’après ce qui précède, trois étapes structurent un algorithme simple6 :
La préparation du traitement
Il s’agit de repérer les données nécessaires voire indispensables à la résolution. Ces données peuvent être numériques, ou sous forme de textes (on dit souvent chaînes de caractères), ou de type logique (à deux valeurs possibles, vrai ou faux), ou enfin de type graphique (des points).
Souvent les données pertinentes doivent être agencées sous une forme plus vaste, comme par exemple des tableaux ou listes où on peut par exemple ranger commodément les valeurs prises par une fonction sur un grand nombre de points.
Dans cette phase peut aussi figurer ce qu’on appelle l’entrée des données, qui peut se manifester par la saisie de caractères ou de nombres sur le clavier, ou la lecture de la position du pointeur de la souris, ou encore par la lecture d’un fichier contenant ces nombres ou caractères.
Il s’agit aussi de repérer les résultats intermédiaires qu’il est bon de mémoriser pour la suite car indispensables au traitement.
Il est parfois utile d’utiliser des variables auxiliaires pour ne pas perturber les données initiales.
Le traitement
Il s’agit de déterminer toutes les étapes des traitements à faire et donc des « instructions » à donner pour une exécution auto-matique. Si ces instructions s’exécutent en séquence, on parle d’algorithme séquentiel. Si les opérations s’exécutent sur plu-sieurs processeurs en parallèle, on parle d’algorithme parallèle. Si les tâches s’exécutent sur un réseau de processeurs on parle d’algorithme réparti ou distribué. Nous ne traiterons ici que des algorithmes séquentiels7.
La sortie des résultats
Les résultats obtenus peuvent être affichés sur l’écran, ou imprimés sur papier, ou bien encore conservés dans un fichier. Si on n’en fait rien, ils « restent » en mémoire jusqu’à la prochaine exécution ou sont perdus. À l’occasion, la sortie pourrait être graphique (afficher ou déplacer le pointeur de la souris ou des objets sur l’écran) ou sonore … voire sur Internet.

Les instructions

Les « instructions » sont les « briques de base » des algorithmes, dont l’assemblage dans un ordre précis conduit au résultat attendu. Nous les présenterons dans un pseudo-langage « en français », accompagnées de traductions concrètes à l’aide de quelques outils logiciels.8
Pour plus de facilité, nous suivrons pas à pas le développement de la formalisation concernant l’algorithme suivant :
Un joueur lance deux dés et fait la somme des points obtenus. S’il obtient 8, il gagne 10€, sinon il perd 1€.
Variante : le joueur rejoue 10 fois (et cumule ses gains et pertes).
Autre variante : le joueur rejoue jusqu’à avoir un gain cumulé de 5€ .
Instructions pour traiter les données
Pour réaliser ces trois étapes évoquées précédemment, on a besoin d’« instructions de base » comme la lecture de données, l’affectation de variables et l’écriture de données.
L’affectation de données dans des variables
La formalisation de notre algorithme commence par le tirage d’un dé et la mémorisation des points obtenus. Cette action nécessite de créer une « mémoire » ou variable destinée à cet usage, zone de mémoire à laquelle il est commode de donner un nom ou identificateur. Avec le logiciel SCRATCH cela prend l’allure suivante :9
Le « bloc » vert matérialise une instruction fournissant une valeur numérique, tandis que le « bloc » orange s’occupe du ran-gement de cette valeur dans une variable nommée a (qui aura été préalablement créée).
Les identificateurs sont des suites de lettres et chiffres (sans espaces) qui doivent être choisies judicieusement pour que l’al-gorithme soit immédiatement lisible et interprétable ; dans l’exemple nous avons choisi a mais il eût mieux valu nommer cette variable dé ou tirage1 puisqu’elle est destinée à contenir le résultat du tirage.
En bref, l’ « affectation » permet d’attribuer une valeur à une variable désignée par son identificateur.10
On peut comparer l’affectation de valeur à une va riable comme le rangement d’un objet dans un petit tiroir (ne pouvant contenir qu’un objet à la fois) ; sur la façade du tiroir figure un nom, c’est l’identificateur qui permet de parler du tiroir lui-même. Cette notion est très proche de celle de variable au sens mathématique.
Dans notre pseudo-langage en français, nous traduirons l’affectation par l’instruction : identificateur prend la valeur valeur. L’affectation remplace la valeur précédente de la variable par la nouvelle. Ainsi l’instruction « A prend la valeur 2 » affecte la valeur 2 à la variable dont A est l’identificateur et ceci quelle que soit la valeur contenue au préalable dans la variable A (la-quelle sera perdue).
On rencontrera ici ou là des variables indicées, nommées listes ou tableaux ; si mathématiquement ces variables ressemblent à des vecteurs, on peut aussi bien les assimiler à des « commodes » pourvues de multiples tiroirs !
La lecture (ou entrée) des données
La « lecture de données » pourra se faire par interrogation de l’utilisateur ou par extraction à partir d’un fichier rangé sur un disque voire de données accessibles par Internet. On a choisi de la traduire par l’instruction : Saisir identificateur .
Par exemple, dans XCAS l’instruction
input(A);
va affecter dans la variable nommée A un nombre ou une expression tapée au clavier. De même, l’instruction
entrée := ramene(« fichier.txt »);
va « ramener » (affecter) dans la variable nommée entrée la première ligne du fichier désigné (ou la prochaine ligne si des lectures ont déjà eu lieu).
L’écriture (ou sortie) des données
L’ « écriture des données » permet d’afficher pour l’utilisateur les valeurs des variables après traitement (ou en cours de trai-tement dans le cas où l’on veut contrôler l’exécution). On a choisi de la traduire par l’instruction : Afficher identificateur. On pourra peaufiner la présentation des résultats pour avoir un affichage lisible et compréhensible. Une variante consiste à « sortir » directement des informations non contenues dans une variable, nous le traduirons par : Afficher « message ».
Dans SCRATCH ces « sorties » peuvent être de la forme ou Les séquences d’instructions
Le « traitement des données » se fait par une suite d’instructions parmi lesquelles figurent des affectations d’opérations ou de calculs. Ces opérations ou ces calculs sont spécifiques selon le type des données utilisées (nombres entiers, nombres déci-maux, ou chaînes de caractères) ou selon les structures données utilisées (listes, tableaux, etc.).
Les instructions, simples ou complexes, sont en principe traitées les unes après les autres dans leur ordre d’apparition dans le programme. Dans la plupart des langages de programmation, les instructions d’une même séquence sont séparées par un ca-ractère deux-points ou point-virgule ou simplement par un passage à la ligne. Ainsi, dans la recette de la pâte à crêpes, on trouve la séquence d’instructions (mettre la farine dans le bol ; faire un puits ; mettre les œufs dans le puits).
On voit très bien ce principe à l’œuvre dans le logiciel SCRATCH, la séquence d’instructions se matérialisant par l’em-boîtement des « pièces de puzzle ». Ci -contre, à titre d’exemple, la simulation du lancer de deux dés et de l’obtention de leur
somme (deux variables ayant pour noms a et b ont été préalable-ment créées).
L’affectation est en couleur orange, le calcul en couleur verte et l’écriture des données en couleur violette ; et cette séquence
comporte trois instructions.
La même démarche, réalisée avec le logiciel XCAS, amènerait à écrire : a := 1+hasard(6) :; b := 1+hasard(6) :; print(a+b) ;
Instructions (ou structures) de contrôle
Le traitement de données se fait parfois sous conditions ou de manière spécifique. On parle alors de « structures de contrôle ». Elles sont de plusieurs natures différentes :
La « structure alternative »
Selon qu’une certaine condition est vérifiée ou non, on fera un certain traitement ou un autre (par « traitement » on entend, comme expliqué ci-dessus, une ou plusieurs instruc-tions en séquence). Pour revenir à notre joueur, l’alternative la plus simple est d’afficher un message favorable si la somme des deux dés (soit a+b) vaut 8 et défavorable sinon :
On a choisi de traduire la structure alternative par l’instruction :
Si condition alors
│ Traitement 1
Sinon
└ Traitement 2
On peut d’ailleurs imaginer que, selon le cas, il se peut que, si la condition n’est pas vérifiée, il n’y ait pas de Traitement 2 à ef-fectuer alors la série d’instruction du Traitement 2 est vide. On écrira alors l’instruction :
Si condition alors
└ Traitement 1
Pour ce qui concerne la « condition », c’est une expression logique prenant l’une des deux valeurs VRAI ou FAUX, qui peut être simple ou complexe.
Par exemple une « condition simple » peut correspondre à un test d’égalité « A est égal à B » noté A=B, ou un test d’inégalité noté « A est strictement inférieur à B » noté A<B, « A est strictement supérieur à B » noté A>B, « A est supérieur ou égal à B » noté A>=B, « A est inférieur ou égal à B » noté A<=B.
Une « condition complexe » est une combinaison logique de conditions simples. Par exemple le test « A est égal à B » et « B est égal à C », se note (A=B) ET (B=C) et le test « A est strictement inférieur à B » ou « B est strictement supérieur à C » se note (A<B) OU (B>C).

Présentation générale
1 / Quelques généralités sur l’algorithmique
2 / Pour une pratique active de l’élève
3 / Supports de programmation
4 / Évaluation des pratiques
Une initiation à l’algorithmique
1 / De quoi va-t-on parler ?
2 / Les éléments de base d’un algorithme simple
Exemples de dispositifs de classe
1 / Quelques jeux
2 / Quelques automates
3 / Lecture d’algorithmes
4 / Évaluation de projets d’élèves
Algorithmes et géométrie
1 / Quelques problèmes
2 / Points, segments et distances
3 / Algorithmes divers
Algorithmes et fonctions
1 / Recherche des extremums sur un segment : fenêtrage vertical
2 / Tester la monotonie
3 / La question du fenêtrage horizontal : comportement asymptotique
4 / Recherche de solution d’équation et d’extremum
Algorithmes et probabilités
1 / Le jeu du lièvre et de la tortue
2 / Coïncidence de date d’anniversaire dans une classe
Bibliographie
Présentation rapide des logiciels
1 / SCRATCH
2 / XCAS
3 / LINOTTE
4 / MAXIMA
5 / PYTHON
6 / SCILAB
7 / EXECALGO
8 / Tableau de correspondance entre les langages