Algorithmique Progressivité des usages, compétences et ...maths.ac-reunion.fr/IMG/pdf/Synthese_stage_ALGO_2012-2013.pdf · Groupe Académique Tice La Réunion – 20 octobre 2012

Algorithmique :

Progressivité des usages, compétences et évaluation

Table des matières

Préface .................................................................................................................................................. 3 Le mot des auteurs .............................................................................................................................. 4 Algorithmique et programmes officiels ............................................................................................. 5 Différentes manières d'introduire l'algorithmique au lycée ........................................................... 8

a) Programme de calcul .............................................................................................................. 8

b) Recette de cuisine ................................................................................................................. 10 c) Cas concret lié à la géométrie ............................................................................................... 14 d) Recherche parmi une liste de nombres ................................................................................. 19

Outils au service de la préparation de l'esprit ................................................................................ 20 a) Boite mémoire ....................................................................................................................... 20

b) Procédure échange ................................................................................................................ 29

c) Présentation de Larp ............................................................................................................. 30

d) Prolongements possibles ....................................................................................................... 35

Algorithmique sous forme de schéma : une bonne représentation mentale des instructions plus

complexes. .......................................................................................................................................... 38 a) SI...ALORS...SINON visualisé avec un organigramme ....................................................... 38 b) SI...ALORS...SINON et suite de Syracuse ........................................................................... 42

c) TANT QUE vu par la somme d'entiers de 1 à 100................................................................ 47

Pseudo - langage et logiciel associé .................................................................................................. 55 a) Vers l’écriture d’un algorithme ............................................................................................. 55 b) Du pseudo - langage à Algobox ............................................................................................ 58

c) D’Algobox au pseudo - langage ........................................................................................... 62 d) Traduire l’algorithme de calcul de distance en Algobox ...................................................... 64

Approfondissements .......................................................................................................................... 73 a) Dictionnaire d'algorithmique ................................................................................................ 74

b) Etude d’algorithmes erronés ................................................................................................. 76 c) Algorithme de tris ................................................................................................................. 77

d) Complexité ............................................................................................................................ 80

Compétences et évaluations .............................................................................................................. 82 a) Eléments théoriques et extraits des documents ressources ................................................... 82

b) Evaluation sur des productions écrites – Exemples de mise en œuvre ................................. 85 c) Evaluation orale .................................................................................................................... 89 d) Exemple de fiche de suivi pour l’évaluation par compétences ............................................ 89 e) Evaluation basée sur l’épreuve expérimentale de terminale S.............................................. 91

Groupe Académique Tice La Réunion – 20 octobre 2012 3/93

Préface

Le Groupe Académique Tice La Réunion a mis en place un stage Algorithmique : Progressivité

des usages, compétences et évaluation, fruit d’un travail conjoint entre les inspecteurs et les

professeurs formateurs.

Les apports des formateurs se sont faits sous le contrôle de l’inspection de mathématiques, sauf

mention contraire où ils ont exprimé un avis tout à fait personnel, ce à quoi nous les avons

encouragés d’ailleurs vivement : de ces idées personnelles surgiront les pistes des bonnes

pratiques futures.

Nous vous invitons à vous approprier les idées présentées mais aussi à vous en détacher pour

faire ainsi jouer pleinement votre liberté pédagogique.

En souhaitant que cette synthèse de stage vous soit fructueuse et vous éclaire sur quelques-unes

de vos interrogations.

Les IA-IPR de mathématiques

Jean-Philippe Brébant ; Philippe Janvier.

Le Groupe Académique Tice La Réunion est composé de cinq collègues de mathématiques répartis

sur le collège, le lycée général et professionnel. Trois d’entre eux ont participé à l'élaboration de ce

stage :

Mme FUR-DESOUTTER Sophie, professeur agrégé de mathématiques au lycée polyvalent

Jean Hinglo (seul lycée de l'île nommé Ambition Réussite) au Port.

M. MICHEL David, professeur agrégé de mathématiques au lycée Bellepierre.

M. VELLARD Terrence, professeur certifié de mathématiques au lycée polyvalent Jean

Hinglo au Port et IANTE de mathématiques.

Cette équipe académique est aussi membre de l'équipe de travaux académiques mutualisés (TraAM)

pour l'année 2011-2012 et pour l’année 2012-2013.


Le mot des auteurs

L'objectif de cette synthèse n'est pas de former des experts en algorithmique mais de proposer une

progressivité annuelle et sur les trois ans du lycée. Nous aborderons les quatre champs du

programme (numérique, géométrie, probabilités et statistiques, fonctions) et proposerons différents

registres, puis des scénarios pour diversifier l’apprentissage et approfondir le savoir-faire des

élèves.

Nous nous efforcerons de tenir une présentation telle que les différents documents de ce papier

soient bien séparés afin que le lecteur intéressé puisse imprimer aisément un extrait pour son

cours : ainsi nous retournerons à une nouvelle page pour un énoncé ou document à compléter, pour

un document d'accompagnement du professeur, pour une correction etc.

S'il est difficile pour des élèves de comprendre l'algorithmique et de l'apprécier en tant qu'outil très

performant suivant les besoins (combien de fois avons-nous entendu les élèves dire : “ Ah ! j'aime

pas ça” , lorsque nous utilisons l'algorithmique dans un chapitre), imaginons combien il est difficile

pour des collègues de l'enseigner sans formation soutenue au préalable et sans recul. Nous avons

alors décidé d'écrire ces quelques pages pour “dédramatiser la chose” : en effet, si un collègue,

très autonome, se fie à ses manuels pour apprendre la notion et orienter son cours ; 2 fois sur 3, il

sera déstabilisé par ce mélange algorithmique/programmation voire meme l'effacement quasi

complet de l'algorithmique au profit de la programmation et ne voudra pas se lancer.

Nous allons donc essayer de proposer un aspect plus théorique et plus naturel : on peut faire

beaucoup de choses avec, seulement, un stylo et du papier, sans pseudo-langage : avec des phrases

en français. L'algorithmique n'est juste qu'une structuration d'idées, peu importe le langage

d'implémentation, on dit meme que “l'algorithmique est à la programmation ce que le brouillon est

à la copie finale.”

De ce fait, nous proposerons des activités progressives dans lesquelles la structuration d'idées est

mise en avant par un travail préparatoire de l'esprit (lecture – compréhension – organigramme...)

basé sur les 3 trimestres.

Après une brève introduction, nous vous proposerons différentes manières d'introduire

l'algorithmique : programme de calculs, recette de cuisine, langage français sur des notions de

collège (Théorèmes de Pythagore, Thalès, notions simples de statistiques).

Dans un second temps, nous présenterons différents outils essentiels pour bien débuter en

algorithmique (cas de l'affectation, intéret de dérouler à la main des algorithmes : lecture et

compréhension d'algorithmes simples, et présentation du logiciel LARP pour aider la

compréhension d'un mécanisme algorithmique).

Ensuite, nous passerons aux instructions plus complexes tels que le SI...ALORS...SINON ou le TANT

QUE... via une bonne représentation mentale par LARP. Enfin, il sera temps de parler de pseudo-

langage et de logiciel associé de programmation, pour ensuite approfondir vers des séances plus

complexes (type abstrait tableau, hors programme mais justifié par un champ du programme : la

statistique) ou d'autres aspects de l'algorithmique tels que la complexité.

Et pour finir, nous vous présenterons une évaluation par compétences, appuyée par un témoignage

de classe.

En espérant que ce document vous apporte l’aide nécessaire, nous vous en souhaitons une bonne

lecture !

Sophie Fur - Desoutter, David Michel, Terrence Vellard.


Algorithmique et programmes officiels La classe de seconde est, pour le moment, le niveau qui a été retenu pour introduire de manière

officielle la définition du mot algorithme. Plusieurs formulations sont envisageables pour définir ce

qu'est un algorithme, mais elles rejoignent toutes le même sens :

“Un algorithme est une suite finie d’instructions, données dans un certain ordre, qui, une fois

exécutée, permet d’obtenir un résultat.

Le programme sert ensuite à automatiser cette suite d'instructions.”

Il est possible de présenter un algorithme sous différentes formes, nous en avons choisi quatre,

appelées registres, qui sont:

Des phrases en français sur papier ou langage naturel

Un organigramme

Un pseudo - langage : : 1i i ou 1i i ou encore 1i i au lieu des phrases en français

du type : mettre 1i dans i ou i prend la valeur 1i .

Un langage de programmation lié à un logiciel : passage sur l’ordinateur ou calculatrice.

La démarche algorithmique est, depuis les origines, une composante essentielle de l’activité

mathématique.

Au collège, les élèves ont rencontré des algorithmes:

Algorithmes opératoires,

Algorithme des différences pour calculer le PGCD de deux nombres,

Algorithme d’Euclide,

Algorithmes de constructions en géométrie.

Ce qui est proposé dans le programme du lycée est une formalisation en langage naturel propre à

donner lieu à une traduction sur une calculatrice ou à l’aide d’un logiciel.

Il s’agit de familiariser les élèves avec les trois grands principes de l’organisation d’un algorithme :

Gestion des entrées – sorties.

Affectation d’une valeur.

Mise en forme d’un calcul.


Dans le cadre d’une activité algorithmique, les élèves sont entraînés :

A décrire certains algorithmes en langage naturel ou dans un langage symbolique ;

A en réaliser quelques-uns à l’aide d’un tableur ou d’un petit programme réalisé sur une

calculatrice ou avec un logiciel adapté ;

A interpréter des algorithmes plus complexes.

Extrait du BO n°30 du 23 juillet 2009

Il est à noter que aucun langage ni logiciel n’est imposé, bien que certains soient préconisés :

Larp (en 2nd

)

Algobox (en 2nd

, 1ère

ES-L ou terminale ES-L, et séries technologiques)

Scilab en terminale S voire en 1ère S.

Bien entendu, la calculatrice.

Le document ressource nous invite donc à orienter notre enseignement en gardant ces points

particuliers à l'esprit :

Les instructions algorithmiques doivent être introduites tout au long du lycée afin de

travailler les compétences algorithmiques suivantes :

◦ comprendre et analyser un algorithme préexistant

◦ modifier un algorithme pour obtenir un résultat particulier

◦ analyser la situation : identifier les données d’entrée, de sortie, de traitement…

◦ mettre au point une solution algorithmique : comment écrire un algorithme en « langage

courant » en respectant un code…

◦ valider la solution algorithmique par des traces d’exécution et des jeux d’essais simples

◦ adapter l’algorithme aux contraintes du langage de programmation

◦ valider un programme simple

Les instructions doivent être introduites régulièrement au service du raisonnement et des

mathématiques : raisonnement et logique sont travaillés au travers de l’algorithmique.

Pas de cours d’algorithmique mais introduire de manière progressive les notions par

différentes activités, par des résolutions de problèmes montrant son intérêt

Idée de progression spiralée autour de l’algorithmique.

Les attendus donnés dans le programme de 2nd

sont des attendus du lycée, de même que le

document d’accompagnement « algorithmique » est pour le lycée sur les 3 années.

Les pages 1 à 13 concernent tout le lycée.


Nous proposons donc, de manière générale, des propositions d'organisation pour les classes de

seconde :

Ecueil à éviter

«Programme: La pratique de l’algorithmique ne se résume pas à l’écriture de programmes; il

serait meme judicieux de ne pas commencer par là. Il convient de proposer aux élèves des

situations, activités et organisations pédagogiques variées.».

Travailler les compétences algorithmiques, de manière progressive, dans les 4 champs du

programme:

◦ Fonctions

◦ Numériques

◦ Géométrie

◦ Probabilités et statistiques

Y compris dans la vie de tous les jours, en faisant varier les supports (papier, ordinateur),

les différents registres, les différents types d’activités.


Différentes manières d'introduire l'algorithmique au lycée

Le Groupe Académique Tice est composé de collègues qui ont fait leurs expériences en matière

d'introduction de l'algorithmique séparément. En voici 4 :

a) Programme de calcul

On donne le programme de calcul suivant : • choisir un nombre • lui ajouter 4 • multiplier la somme obtenue par le nombre choisi • ajouter 4 à ce produit • écrire le résultat 1. Quel est le résultat si le nombre choisi est -2 ? 2. Quel est le résultat si le nombre choisi est 5 ? 3. Quel type de nombre retourne ce programme ? On justifiera la réponse. 4. Quel nombre doit-on choisir pour obtenir 1 ?

Il s'agit d'un programme de calcul du DNB 2007, afin de faire le lien avec le collège.


Fiche professeur

Objectif : introduire la notion d’algorithme (en tant que suite d’instructions)

× Classe : 2nd

× Durée : 15 min

× Champ du programme : fonction ou numérique

× Le registre : en langage naturel

× Compétences :

- comprendre et analyser un algorithme préexistant

- analyser la situation : identifier les données d’entrée, de sortie, le traitement…

On donne le programme de calcul suivant : • choisir un nombre • lui ajouter 4 • multiplier la somme obtenue par le nombre choisi • ajouter 4 à ce produit • écrire le résultat 1. Quel est le résultat si le nombre choisi est -2 ? résultat : 0 2. Quel est le résultat si le nombre choisi est 5 ? résultat : 49

3. Quel type de nombre retourne ce programme ? On justifiera la réponse. Un carré : 2

2x .

4. Quel nombre doit-on choisir pour obtenir 1 ? il faut choisir -1 ou -3.

Commentaires :

En partant d’un exemple connu, vu en 3ième

, il s’agit d’introduire la notion d’algorithme comme

une suite d’instructions qui termine.

Cet exemple est un exemple biaisé d’algorithme puisqu’il n’intervient pas dans le cadre de la

résolution d’un problème mais il a été choisi car il est relativement simple et n’introduit pas de

difficultés mathématiques importantes qui pourraient bloquer la compréhension et donc la

résolution du problème.

Ce programme de calcul engendre une répétition de tâches1 qui induit l’utilisation de l’outil

informatique (tableur, calculatrice…) en particulier de l’algorithmique.

Prolongement possible: Utilisation d’un tableur (ou d’une calculatrice programmable) pour

automatiser les calculs et aller ainsi vers l’algorithmique.

1 Document ressource « Algorithmique »: 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


b) Recette de cuisine

Recette de la pâte à crêpes

Ingrédients

250g de farine

4 œufs

un demi-litre de lait

1 pincée de sel

50 grammes de beurre

1 sachet de sucre vanillé

Dans un saladier, verser la farine et les œufs. Puis progressivement ajoutez le lait tout en

mélangeant avec votre fouet.

Ajoutez le sucre vanillé, la pincée de sel.

Laissez reposer la pâte à crêpe si possible une heure.

Partie A 1. Que vous faut-il pour faire une pâte à crêpes ?

2. L’ordre d’écriture des ingrédients est-elle importante ?

3. L’ordre de mélange des ingrédients est-il important ? Pour quels ingrédients ?

4. Listez dans l’ordre approprié, les actions à faire (ou instructions) pour réaliser une pâte

à crêpes. Partie B

1. Proposez une autre action de la vie courante qui peut être décomposée comme une

suite d’instructions à réaliser dans un ordre précis. Une suite finie et non-ambiguë d’instructions permettant de donner la réponse à un problème est appelé un algorithme (Quel est le plus grand diviseur de deux entiers ?, Trouver le nombre mystère). Un algorithme peut être décomposé en trois parties :

1. On entre des données (ou variables) C’est la phase d’ENTREE

On entre un nombre

2. Ces données sont traitées par une suite

d’instructions C’est la phase de TRAITEMENT

(1) lui ajouter 4 (2) multiplier la somme obtenue par le nombre choisi (3) ajouter 4 à ce produit

3. Un résultat est obtenu C’est la phase de SORTIE

Le résultat obtenu est le nombre cherché


2. Compléter le tableau ci-dessous pour décrire l’algorithme utilisé pour faire une pâte à

crêpes.


2. Ces données sont traitées par une suite d’instructions C’est la phase de TRAITEMENT



Fiche professeur

Objectif : introduire la construction en trois phases (entrée, traitement, sortie) d’un algorithme.

× Classe : tout niveau

× Durée : 1 h


× Le registre : en langage naturel, familiarisation au pseudo - langage

× Compétences : comprendre et analyser un algorithme préexistant

Recette de la pâte à crêpes Ingrédients

250g de farine

4 œufs

un demi-litre de lait

1 pincée de sel

50 grammes de beurre

1 sachet de sucre vanillé

Dans un saladier, verser la farine et les œufs. Puis progressivement ajoutez le lait tout en

mélangeant avec votre fouet.

Ajoutez le sucre vanillé, la pincée de sel.

Laissez reposer la pâte à crêpe si possible une heure.

Partie A 1. Que vous faut-il pour faire une pâte à crêpes ?

2. L’ordre d’écriture des ingrédients est-elle importante ?

3. L’ordre de mélange des ingrédients est-il important ? Pour quels ingrédients ?

4. Listez dans l’ordre approprié, les actions à faire (ou instructions) pour réaliser une pâte à

crêpes. Partie B

1. Proposez une autre action de la vie courante qui peut être décomposée comme une suite

d’instructions à réaliser dans un ordre précis. Une suite finie et non - ambiguë d’instructions permettant de donner la réponse à un problème est appelé un algorithme (Quel est le plus grand diviseur de deux entiers ?, Trouver le nombre mystère).


Un algorithme peut être décomposé en trois parties :


On entre un nombre

2. Ces données sont traitées par une suite

d’instructions C’est la phase de TRAITEMENT

(1) lui ajouter 4 (2) multiplier la somme obtenue par le nombre choisi (3) ajouter 4 à ce produit


Le résultat obtenu est le nombre cherché

2. Compléter le tableau ci-dessous pour décrire l’algorithme utilisé pour faire une pâte à

crêpes.


250g de farine 4 œufs un demi-litre de lait 1 pincée de sel 50 grammes de beurre 1 sachet de sucre vanillé

2. Ces données sont traitées par une suite d’instructions C’est la phase de TRAITEMENT

(1) Verser la farine (2) Ajouter les œufs (3) Ajouter progressivement le lait en remuant (4) Ajouter le sucre vanillé (5) Ajouter le sel (6) Laisser reposer


Le résultat obtenu est la pâte à crêpes.

Commentaires :

Cette activité est traitée en début d’année de 2nd

, comme introduction à l’algorithmique. Elle permet

de formaliser l’algorithmique, le vocabulaire (notion d’instructions, d’ordre) et la structure d’un

algorithme (en 3 phases : entrée, traitement, sortie) en créant des liens avec la vie courante, en

établissant une liaison mentale.

Il s’agit de montrer aux élèves que l’algorithmique n’est pas nouveau puisqu'ils en font sans le

savoir, dans la vie de tous les jours.

Afin de simplifier l’apprentissage, seul le langage en français (ou langage naturel) est présent ici et

aucune difficulté mathématique n’est introduite avec cet exemple de la vie courante.

Contrairement à l’exercice du DNB 2007, cet algorithme correspond à la définition d’algorithme,

énoncée plus haut, car ici nous avons un problème : faire des crêpes.


c) Cas concret lié à la géométrie

Les objectifs d'un tel exemple sont :

Montrer que la vie courante et la géométrie peuvent être très liées

Organiser une stratégie pour répondre à un questionnement

Utiliser des résultats mathématiques de collège pour résoudre le problème

Réinvestir le savoir-faire du collège.

Les compétences développées deviennent alors :

Projeter son imagination afin de mieux comprendre l’enjeu d’une problématique

Organisation d’idées via une rédaction simple mais claire et précise

Transposer les techniques de construction à la règle et au compas à une échelle

humaine (voir scénario Théorème de Pythagore)

Décontextualiser les connaissances mathématiques (on peut utiliser les

mathématiques en dehors de l’école, si si on peut…)


Scénario 1 :

Je désire construire une maison rectangulaire qui, vue de dessus, possède les mesures (en mètres)

suivantes :

Vous devez donner les instructions aux ouvriers afin que la construction se fasse bien. On suppose

que si on donne la longueur d'un mur à construire, les ouvriers savent le construire droit. On ne gère

pas les étapes de construction, on donne juste des directives. Comment agencer les étapes de

construction afin d'obtenir un angle parfaitement droit puisqu'il n'existe pas d'équerre géante (on

veut une construction semblable à une construction à la règle et au compas) ?

Les ouvriers disposent d'un mètre mesureur de 30 mètres, d'autant de corde, et de quoi monter des

murs. Et vous, vous disposez de quoi réfléchir au calme : papier, crayon, calculatrice...

Vous devez agencer les instructions comme une recette de cuisine (une ligne = une étape, chaque

ligne commence par un verbe).

Scénario 2 :

En vacances, je me baladais en voiture le long d'une rivière, et de l'autre côté de la rive je me

demandais quelle distance séparait deux arbres alignés parallèlement à la rivière conformément au

schéma :

Dans le coffre de la voiture, je dispose d'un télémètre, papier, crayon, calculatrice... l'aide d'une

tierce personne, et éventuellement d'un gros caillou ou bâton que l'on peut trouver dans le champ

entre ma voiture et la rivière. Je peux me disposer n'importe où dans le champ.

Comment mesurer la distance entre les 2 arbres ?

15

20

Ma voiture


Document d'accompagnement de l'enseignant

Titre : Première approche de l'algorithmique via le Théorème de Pythagore et celui de Thalès.

Cadre : Chapitre en cours : Première semaine de Rentrée.

Nous commençons dès la rentrée le programme, en revenant de temps à autre et en cas de besoin

sur des connaissances antérieures. Dans le cas présent, l’approche de la notion d’algorithmique

permet de revenir sur deux théorèmes centraux vus au collège.Il n'est pas nécessaire d'introduire le

nom « algorithme » à ce stade afin de ne pas créer de blocage chez les élèves.

Nous allons utiliser, comme support, deux situations de la vie réelle et privilégier le travail de

groupe (constat établi : de plus en plus délaissé au collège).

Objectifs : Se familiariser avec le concept d'agencement des idées par étape notamment l'aspect linéaire

(séquentiel) du temps dans l'exécution des instructions.

Investir les notions théoriques de construction ou d'utilisation de théorème dans un cas dit

réel.

Pré – requis : Construction d'un triangle à la règle et au compas

Utilisation du théorème de Pythagore

Maîtrise des hypothèses du théorème de Thalès (il sera alors l'occasion de revenir sur cette

importance).

Bien expliciter les outils mis à disposition par le scénario et le degré de recul que doit avoir

l'élève : en effet, celui qui construit un algorithme est associé à un manager ou chef de

projet, il donne les instructions, anticipe tous les cas possibles afin de pouvoir déléguer.

Les limites : Aucun pseudo-langage n'a été introduit : le but, dans un premier temps, est d'aider les élèves

à structurer les idées et non à « coder » un programme.

Pas de chronométrage précis de la séance afin de ne pas desservir l'intérêt des élèves avec

cette nouvelle notion.

Prolongement : Pas de prolongement.

Déroulement : Présentation du premier scénario et des outils autorisés.

Conception de groupe de 3 ou 4 personnes.

1ère phase de recherche sans indication supplémentaire : ce sera l'occasion de passer dans

les groupes, de préciser l'état d'esprit dans lequel l'élève doit être, de faire ressortir les acquis

du collège si le groupe reste bloqué.

Mise en commun des idées de chaque groupe.

2ème phase de recherche pour l'écriture des étapes attendues.

Correction.

Présentation du second scénario et des outils autorisés et même déroulement.


Une possible correction :

Scénario 1 :

On se retrouve dans un cas de construction d'un triangle rectangle ABC à la règle et au compas. La

maison s'assimile à un rectangle ABCD comme suit :

L'assurance de l'angle droit permet d'utiliser le théorème de Pythagore pour calculer la longueur du

segment [AC].

La corde jouera le rôle du compas.

Une solution possible de séquence d'instructions:

1. Construire le mur de 20 mètres.

2. Mesurer 15 mètres sur la corde.

3. (À partir de B), reporter la longueur de 15 mètres en traçant un arc de cercle sur le sol.

4. (Grâce au théorème de Pythagore), calculer la longueur du segment [AC]. (AC = 25

mètres).

5. Mesurer 25 mètres sur la corde.

6. (À partir de A), reporter la longueur de 25 mètres en traçant un arc de cercle sur le sol en

intersection du premier.

7. Construire le mur de 15 mètres.

8. Recommencer les étapes 2) à 7) pour construire les autres murs.

Scénario 2 :

On se retrouve dans un cas de calcul de longueur dans une figure type de Thalès.

On laissera éventuellement l'élève s'interroger sur l'importance de l'endroit où placer le point A, et

surtout les points E et F pour obtenir le parfait parallélisme.

N.B. : L'absence de nombre a gené certains élèves. Il a fallu revoir les consignes, le but étant de

donner une méthode et non de résoudre un cas particulier.

A

B C

D

A

B C

E F


Une solution possible de séquence d'instructions:

1. Se positionner où l'on veut dans le champ en A.

2. Prendre le télémètre et viser un arbre le B par exemple.

3. Relever la distance inscrite sur le télémètre.

4. Demander à une tierce personne de longer la rive jusqu'à intercepter le faisceau du

télémètre entre A et B. Planter un bâton dans le sol, on appellera ce point E.

5. Relever la distance entre A et E.

6. Faire de même avec le 2ème arbre.

7. Se mettre en F et la tierce personne en E et mesurer la distance EF grâce au télémètre.

8. (Grâce au théorème de Thalès) Calculer BC.


d) Recherche parmi une liste de nombres

Problématique :

Voici une liste de notes sur 20 :

{18 ; 0 ; 13 ; 4 ; 8 ; 9 ; 12 ; 7 ; 2 ; 16}.

1. Combien de notes sont au dessus de la moyenne, et combien sont en dessous ?

2. Comment avez - vous fait pour les déterminer ? Écrire les étapes de votre réflexion comme

si vous deviez l'expliquer à un enfant de classe élémentaire.

Réactions observées, et réflexion :

De manière générale, les élèves n'éprouvent pas de difficulté à donner la réponse : 4 notes

supérieures à 10 et 6 en dessous. Pour l'expliquer, ils se justifient par : “j'ai regardé” ou “ça se voit”

mais ne comprennent pas la question ou du moins ne la réalisent pas.

La première étape sera donc de les faire réaliser ce qu'ils font machinalement : je regarde la

première note, puis la seconde et ainsi de suite jusqu'à la fin.

Ensuite, il faut compter, sans mélanger, les notes au dessus de 10 et en dessous de 10. Un bon

exemple est de prendre un élève désigné pour tel type de note et un autre pour l'autre type ou la

main gauche pour un type, et la main droite pour l'autre.

Ceci légitimera la création de 2 compteurs.

Après on se pose quelques questions de routine, comme par exemple, quelle doit être la première

valeur des compteurs ? Au départ, “c'est zéro !”.

On arrive alors à structurer les idées de cette manière :

début

Créer cpteur≥10 et initialiser à 0.

Créer cpteur<10 et initialiser à 0.

Regarder la première note,

est-elle plus grande ou égale à 10 ?

si oui, ajouter 1 à cpteur≥10

si non, ajouter 1 à cpteur<10.

Passer à la note suivante.

Recommencer la question tant qu'il y a des notes.

Afficher : “le nombre de note supérieures à 10 est :” cpteur≥10.

Afficher : “le nombre de note inférieures à 10 est :” cpteur<10.

fin

N.B. : Il sera intéressant de dérouler l'algorithme entièrement au tableau sur la série de

nombre


Outils au service de la préparation de l'esprit

Dans cette première partie seront abordées des activités permettant d'introduire l'affectation et la

notion de variable, des outils afin de bien préparer les esprits à l'algorithmique et des réflexes de

base à rapidement obtenir pour comprendre l'état d'esprit avec lequel on fait de l'algorithmique.

a) Boite mémoire

On considère la fonction f définie sur par 2 5 4 5 4f x x x x x . On souhaite

remplir la table de valeurs suivantes :

x -1 0 1 2 3

f x

Voici une liste d’instructions pour calculer une image :

(1) Choisir un nombre (2) Mémoriser ce nombre (3) Soustraire 5 au nombre mémorisé (4) Multiplier le résultat précédent par le nombre mémorisé (5) Ajouter 4 à ce produit (6) Donner le résultat

Pour mémoriser le nombre choisi, on imagine qu’il est stocké dans une « boîte - mémoire ». De même pour les résultats des instructions (3), (4) et (5). Ainsi pour cet algorithme, on peut considérer que quatre boîtes vont être utilisées :

La boîte a : pour le nombre choisi

Les boîtes ,b c et d : pour chacun des résultats des calculs des instructions (3), (4) et (5).

1. Dans cette question, on suppose que le nombre choisi est 2.

Ainsi la boîte mémoire a contient la valeur 2. Compléter les autres boîtes mémoires par leur contenu.

2


2. Recommencer la question précédente en supposant que le nombre choisi est 3 :

3. Compléter les pointillés en utilisant à chaque fois le nom de la boîte précédente (et une autre

si nécessaire).

4. L’utilisation de ces boîtes va permettre de réécrire les instructions sous une autre forme, plus

proche des instructions spécifiques aux outils (ordinateur ou calculatrice) que nous

utiliserons. Ainsi l’instruction (3) : « Soustraire 5 au nombre mémorisé » devient : « mettre 5a dans b ». Ce qu'il faut comprendre de la façon suivante : on soustrait 5 à la valeur qui est dans a et on met le résultat de cette soustraction dans b. On peut formuler autrement et dire par exemple : « b prend la valeur 5a » ou « remplacer b par 5a ». Compléter les .... ci - dessous pour dire ce que deviennent les instructions (4) et (5) avec cette façon d’écrire. (4) Multiplier le résultat précédent par le nombre mémorisé devient : « mettre ..................... dans .... »

(5) Ajouter 4 au résultat précédent devient : « ..................................................».

5. Les instructions (1) et (2) peuvent être résumées en une seule comme le montre le tableau ci-

dessous. Compléter les ….. des instructions (3), (4) et (5).


Instructions écrites en langage courant

Ecriture proche de celles des ordinateurs et

calculatrices

Commentaires

Cette écriture n’est pas «figée», elle peut varier

selon les manuels utilisés. C’est une écriture

intermédiaire entre le langage courant et les

différents langages de programmation sur

ordinateur ou calculatrice.

(1) Choisir un nombre

Entrer a

L’instruction Entrer a signifie trois choses :

1) elle permet de demander à l’utilisateur

d’entrer une valeur

2) elle définit le nom de la boîte dans laquelle

va être rangée la réponse de l’utilisateur

3) elle stocke la valeur entrée par l’utilisateur

dans la boîte a .

Dans certains manuels, on utilise plutôt

l’instruction « Saisir a » On rencontrera aussi l’expression «Lire a», qui aura le meme sens.

(2) Mémoriser ce nombre

(3) Soustraire 5 au nombre mémorisé

Mettre 5a dans b

Chacun de ces calculs s’effectue en utilisant un

nombre déjà rangé dans une boîte.

Chaque résultat est rangé dans une autre boîte.

« Mettre a – 5 dans b » signifie deux choses :

(4) Multiplier le résultat précédent par le nombre mémorisé

Mettre ……… dans c

(5) Ajouter 4 à ce produit

Mettre ……… dans d

(6) Donner le résultat

………………. d

La valeur contenue dans la boîte d est

annoncée.

(attention, ce n’est pas la lettre d qui est

annoncée) On rencontrera aussi l’expression « Afficher d » qui aura le meme sens.

6. Fini de compléter la table de valeurs de f .


Application

On considère la fonction f définie sur par 2

3 7f x x . On souhaite remplir la table de

valeurs précédente. Voici la liste d’instructions pour calculer une image :

1. Ecrire les instructions comme on vient de le faire dans le tableau de la question 6.

2. En fait on aurait pu n'utiliser que deux boîtes - mémoire : une pour la valeur entrée par

l'utilisateur et l'autre pour la réponse à annoncer. Ecrire ci-dessous l'instruction 2 pour que

l'algorithme sorte la réponse recherchée.

(1) Choisir un nombre (2) Mémoriser ce nombre (3) Ajouter 3 au nombre mémorisé (4) Calculer le carré du résultat précédent (5) Soustraire 7 au résultat précédent (6) Donner le résultat

1) Entrer a

2)

3) Sortir b


Fiche professeur

Objectif : Introduire la notion de variable et d’affectation

× Classe : tout niveau

× Durée : 1 h


× Le registre : en langage naturel, familiarisation au pseudo - langage

× Compétences : comprendre et analyser un algorithme préexistant

On considère la fonction f définie sur par 2 5 4 5 4f x x x x x . On souhaite

remplir la table de valeurs suivantes :

x -1 0 1 2 3

f x 10 4 0 -2 -2

Voici une liste d’instructions pour calculer une image :

(1) Choisir un nombre (2) Mémoriser ce nombre (3) Soustraire 5 au nombre mémorisé (4) Multiplier le résultat précédent par le nombre mémorisé (5) Ajouter 4 à ce produit (6) Donner le résultat

Pour mémoriser le nombre choisi, on imagine qu’il est stocké dans une « boîte - mémoire ». De même pour les résultats des instructions (3), (4) et (5). Ainsi pour cet algorithme, on peut considérer que quatre boîtes vont être utilisées :

La boîte a : pour le nombre choisi

Les boîtes ,b c et d : pour chacun des résultats des calculs des instructions (3), (4) et (5).

1. Dans cette question, on suppose que le nombre choisi est 2.

Ainsi la boîte mémoire a contient la valeur 2. Compléter les autres boîtes mémoires par leur contenu.

2

-3 -6 -2


2. Recommencer la question précédente en supposant que le nombre choisi est 3 :

3. Compléter les pointillés en utilisant à chaque fois le nom de la boîte précédente (et une autre

si nécessaire).

4. L’utilisation de ces boîtes va permettre de réécrire les instructions sous une autre forme, plus

proche des instructions spécifiques aux outils (ordinateur ou calculatrice) que nous

utiliserons. Ainsi l’instruction (3) : « Soustraire 5 au nombre mémorisé » devient : « mettre 5a dans b ». Ce qu'il faut comprendre de la façon suivante : on soustrait 5 à la valeur qui est dans a et on met le résultat de cette soustraction dans b. On peut formuler autrement et dire par exemple : « b prend la valeur 5a » ou « remplacer b par 5a ». Compléter les .... ci - dessous pour dire ce que deviennent les instructions (4) et (5) avec cette façon d’écrire. (4) Multiplier le résultat précédent par le nombre mémorisé devient : « mettre a b dans c »

(5) Ajouter 4 au résultat précédent devient : « mettre 4c dans d ».

5. Les instructions (1) et (2) peuvent être résumées en une seule comme le montre le tableau ci-

dessous. Compléter les ….. des instructions (3), (4) et (5).

-6 3

-2 -2



Ecriture proche de celles des ordinateurs et calculatrices

Commentaires

Cette écriture n’est pas «figée», elle peut varier

selon les manuels utilisés. C’est une écriture

intermédiaire entre le langage courant et les

différents langages de programmation sur

ordinateur ou calculatrice.

(1) Choisir un nombre

Entrer a

L’instruction Entrer a signifie trois choses :

1) elle permet de demander à l’utilisateur

d’entrer une valeur

2) elle définit le nom de la boîte dans laquelle

va être rangée la réponse de l’utilisateur

3) elle stocke la valeur entrée par l’utilisateur

dans la boîte a .

Dans certains manuels, on utilise plutôt

l’instruction « Saisir a » On rencontrera aussi l’expression «Lire a», qui aura le meme sens.

(2) Mémoriser ce nombre

(3) Soustraire 5 au nombre mémorisé

Mettre 5a dans b

Chacun de ces calculs s’effectue en utilisant un

nombre déjà rangé dans une boîte.

Chaque résultat est rangé dans une autre boîte.

« Mettre a – 5 dans b » signifie deux choses :


Mettre a b dans c


Mettre 4c dans d

(6) Donner le résultat

Sortir d

La valeur contenue dans la boîte d est

annoncée.

(attention, ce n’est pas la lettre d qui est

annoncée) On rencontrera aussi l’expression « Afficher d » qui aura le meme sens.

6. Fini de compléter la table de valeurs de f .


Application

On considère la fonction f définie sur par 2

3 7f x x . On souhaite remplir la table de

valeurs précédente. Voici la liste d’instructions pour calculer une image :

1. Ecrire les instructions comme on vient de le faire dans le tableau de la question 6.

2. En fait on aurait pu n'utiliser que deux boîtes - mémoire : une pour la valeur entrée par

l'utilisateur et l'autre pour la réponse à annoncer. Ecrire ci-dessous l'instruction 2 pour que

l'algorithme sorte la réponse recherchée.

1) Entrer a

2) Mettre 2( 3) 7a dans b

3) Sortir b

(1) Choisir un nombre (2) Mémoriser ce nombre (3) Ajouter 3 au nombre mémorisé (4) Calculer le carré du résultat précédent (5) Soustraire 7 au résultat précédent (6) Donner le résultat

Entrer a Mettre 3a dans b Mettre 2b dans c Mettre 7c dans d Sortir d


Commentaires :

Cette activité n’a pas pour objectif principal de remplir la table de valeurs (car la calculatrice le fait

aussi !) mais plutôt de comprendre ce que fait la machine.

Les boîtes – mémoire sont comparées à la touche ANS de la calculatrice : « derrière » la touche

ANS il y a une boîte mémoire qui retient le résultat précédent. Seul le dernier résultat est

réutilisable avec la touche ANS, chaque résultat est écrasé automatiquement par le suivant comme

lors d’une nouvelle affectation.

Cette activité a été traitée en 2nd

(1 heure de cours environ) après « la recette de la pâte à crêpes » et

en terminale S pour « remettre en place » les notions d’algorithmique.

Cette activité est en langage naturel et permet l’introduction d’un pseudo - langage tout en allant

vers l’écriture d’un algorithme.

Les élèves doivent transcrire les boîtes - mémoire en pseudo - langage, tout en respectant la

structure d’un algorithme. C’est l’occasion de présenter les différentes notations, 1i i ou

: 1i i ou 1i i , que les élèves seront amenés à rencontrer et à en choisir une commune à la

classe.

La question 4. (diminuer le nombre d’instructions utilisées), permet d’aborder la modification d’un

algorithme et la notion de complexité.


b) Procédure échange

L'intérêt de la procédure échange réside dans le fait que cela peut être une application directe de la

partie théorique sur la notion de variable et de l'affectation et va permettre de démontrer la nécessité

de “dérouler un algorithme à la main” afin de comprendre ce que ce dernier fait.

Cette activité ne s'inscrit dans aucun champ du programme spécifiquement, le registre est le

pseudo-langage ou le langage français suivant votre niveau d'exigence. Les compétences mises en

avant sont : Exécuter un algorithme sur du papier.

La problématique : écrire un algorithme qui demande la saisie de 2 nombres “a et b” et qui échange

ensuite ces deux valeurs.

Ce qu'il faudrait que les élèves écrivent (de manière générale, ils le font naturellement) :

Saisir une valeur dans a

Saisir une valeur dans b

Mettre la valeur de a dans b

Mettre la valeur de b dans a

L'intérêt désormais est de les accompagner dans le déroulement de l'algorithme en choisissant des

valeurs à a et à b et de procéder à chaque étape.

Il faudrait ensuite trouver un moyen de corriger cet algorithme erroné.

Plusieurs images sont possibles pour aider ceux qui ne comprennent pas :

imaginons 1 verre de soda et 1 verre de jus, nous désirons permuter le contenu de ces 2

verres.

Il est aussi possible d'introduire une nouvelle représentation, l'organigramme, afin de mettre en

avant les différentes étapes d'un algorithme, d'utiliser l'exécution pas à pas et de gagner, par la

même occasion, du temps par rapport au déroulement à la main. Le logiciel préconisé par

l'inspection, pour l’utilisation des organigrammes, est LARP, que nous développons dans la

prochaine partie.


c) Présentation de Larp

Larp est un logiciel qui existe en 2 versions : gratuite et payante. Il permet de faire de

l'algorithmique sous forme d'organigramme, et de parcourir chaque étape d'exécution pas à pas.

Après avoir lancé le logiciel, créer un nouveau projet en cliquant sur “fichier/nouveau”. Vous avez

le choix entre pseudo - code ou organigramme. Choisir organigramme.

Une nouvelle page apparaît avec une bulle “début” et une bulle “fin”.


Dans la colonne de gauche, vous trouverez les différents modules que l'on peut “faire glisser” dans

les nœuds gris.

Voici l'organigramme correspondant à la procédure échange :


Vous noterez que chaque étape correspond, dans la forme du quadrilatère, à un module de la

colonne de gauche :

Pour lancer l'exécution, cliquer sur l'un des deux symboles en vert, suivant que vous désirez une

exécution simple ou pas à pas:


Nous choisissons le pas à pas pour la pédagogie :


Deux fenêtres sont apparues :

la console (à fond noir) qui va permettre le dialogue avec l'utilisateur

la trace (à fond gris) qui va afficher l'évolution des variables au fur et à mesure que

l'organigramme est parcouru (le module concerné passe au vert).


d) Prolongements possibles

Les lectures d’algorithmes permettent un entraînement régulier des notions abordées précédemment

et permettent de travailler les compétences : savoir exécuter un algorithme et savoir analyser un

algorithme.

Sous forme de QCM, ils sont traités très rapidement par les élèves et présentent peu de difficulté.

Ils montrent toujours l’importance de « faire tourner un algorithme à la main ».

Ils sont été faits en 2nd

, suite au travail d’introduction présenté précédemment et en révisions dans

les autres classes.

Savoir exécuter un algorithme



Savoir analyser un algorithme


Algorithmique sous forme de schéma : une bonne représentation mentale des instructions plus complexes.

Nous allons vous proposer des fiches d'activité afin d'introduire le SI...ALORS...SINON et le TANT

QUE. L'intérêt est, bien entendu, de réinvestir le temps passé sur le logiciel LARP car l'utilisation

de l'organigramme se prête assez bien à l'image mentale dans la compréhension de ces 2

instructions dites complexes. En effet, les modules liés au SI...ALORS...SINON offrent 2 sorties

possibles : une VRAI et une FAUX bien distinctes. Les modules liés au TANT QUE voient une

sortie revenir au début affichant bien l'effet de retour.

a) SI...ALORS...SINON visualisé avec un organigramme

On considère le programme de calcul suivant.

1. Donner la condition sur x pour pouvoir appliquer ce programme

2. Appliquer ce programme à :

a) 0

b) 1

c) 4

d) 81

3. Montrer que si 4x , 1 3x .

On prend le double

On prend le carré de l’inverse

vrai

faux


4. Compléter les phrases suivantes :

Si 0;4x , alors ...f x

Si 4;x , alors ...f x .

5. Voici la transcription de ce programme de calcul avec le logiciel LARP.

Construire l’organigramme ci-dessus avec le logiciel LARP.

Puis vérifier vos résultats de la question 2.


Fiche professeur

Objectifs : Introduire un nouveau registre (organigramme)

Introduire progressivement le test SI-SINON en partant d’un langage naturel

× Classe : 2nd

× Durée : 1 h

× Champ du programme : fonction

× Les registres : en langage naturel, organigramme

× Les compétences :


- analyser la situation : identifier les données d’entrée, de sortie, de traitement…

- valider la solution algorithmique par des traces d’exécution et des jeux d’essais

simples.

On considère le programme de calcul suivant.

1. Donner la condition sur x pour pouvoir appliquer ce programme : 0x

2. Appliquer ce programme à :

a) 0 1

On prend le double

On prend le carré de l’inverse

vrai

faux


b) 1 1

4

c) 4 6

d) 81 20

3. Montrer que si 4x , 1 3x .

4. Compléter les phrases suivantes :

Si 0;4x , alors 2 1f x x

Si 4;x , alors 2

1

1f x

x

.

5. Voici la transcription de ce programme de calcul avec le logiciel LARP.

Construire l’organigramme ci-dessus avec le logiciel LARP.

Puis vérifier vos résultats de la question 2.


b) SI...ALORS...SINON et suite de Syracuse

A tout entier naturel 1n , on applique l’algorithme suivant :

Si 1n , le processus s’arrête, sinon :

-si n est pair, on le transforme en 2

n,

-si n est impair, on le transforme en 3 1n .

On note à nouveau n le résultat obtenu et on ré - applique l’algorithme à ce n .

Lorsque, pour l’entier n , l’algorithme abouti à 1 on appelle « suite de Syracuse associée à n », la

suite (finie) des entiers rencontrés pour passer de 1 à n .

On note ( )L n le nombre d’entiers de cette suite finie.

( )L n est la longueur de la suite de Syracuse associée à n .

Exemple : Pour 5n , on obtient successivement les nombres 5 16 8 4 2 1 donc 5 6L .

1. Quelques tests

a. Quelle est la longueur de la suite obtenue pour 4n ? On écrira tous les entiers de la

suite.

b. Quelle est la longueur de la suite obtenue pour 12n ? On écrira tous les entiers de la

suite.

2. Problème simplifié

On souhaite obtenir des résultats particuliers relatifs aux longueurs des suites L n pour n entier

naturel.

Pour cela, on étudiera dans un premier temps le problème simplifié :



n,


a. Quel est le résultat obtenu si 6n ?

b. Quel est le résultat obtenu si 5n ?

c. En vous aidant de l’exercice précédent « Organigramme », construire, sur le papier,

l’organigramme associé à cet algorithme.

d. Après validation par le correcteur, construire l’organigramme avec LARP.


Aide : Pour tester si n est pair, le logiciel teste si l’entier est divisible par 2 (si le reste de la division euclidienne de n par 2 est nul).

e. Exécuter l’algorithme pour vérifier vos résultats des questions a. et b.


Fiche professeur

Objectifs : Induire l’utilisation d’algorithme

Introduire un nouveau registre (organigramme)

Introduire progressivement le test SI-SINON en partant d’un langage naturel

× Classe : 2nd

× Durée : 1 h avec la manipulation sur LARP

× Champ du programme : numérique, histoire des mathématiques

× Les registres : en langage naturel, organigramme





simples


Si 1n , le processus s’arrête, sinon :


n,


On note à nouveau n le résultat obtenu et on ré - applique l’algorithme à ce n .

Lorsque, pour l’entier n , l’algorithme abouti à 1 on appelle « suite de Syracuse associée à n », la

suite (finie) des entiers rencontrés pour passer de 1 à n .

On note ( )L n le nombre d’entiers de cette suite finie.

( )L n est la longueur de la suite de Syracuse associée à n .

Exemple : Pour 5n , on obtient successivement les nombres 5 16 8 4 2 1 donc 5 6L .

1. Quelques tests

a. Quelle est la longueur de la suite obtenue pour 4n ? On écrira tous les entiers de la

suite. L=3

b. Quelle est la longueur de la suite obtenue pour 12n ? On écrira tous les entiers de la

suite. L=10

2. Problème simplifié

On souhaite obtenir des résultats particuliers relatifs aux longueurs des suites L n pour n entier

naturel.

Pour cela, on étudiera dans un premier temps le problème simplifié :


- si n est pair, on le transforme en 2

n,

- si n est impair, on le transforme en 3 1n .

a. Quel est le résultat obtenu si 6n ? On obtient 3


b. Quel est le résultat obtenu si 5n ? On obtient 16

c. En vous aidant de l’exercice précédent « Organigramme » construire, sur le papier,

l’organigramme associé à cet algorithme.

a. Après validation par le correcteur, construire l’organigramme avec LARP.

b. Exécuter l’algorithme pour vérifier vos résultats des questions a. et b.

Aide : Pour tester si est pair, le logiciel teste si l’entier est divisible par 2 (si le reste de la division euclidienne de par 2 est nul).

On prend On prend

vrai

faux est pair


Commentaires :

- Ce style d’activité, où les calculs sont répétitifs, permet d’induire l’utilisation

d’algorithme comme le préconise le document ressources sur l’algorithmique2 : « par

exemple dans le cas de répétition, ou, dans le cas d’un traitement trop long pour être

envisagé à la main ».

- L’organigramme papier ou LARP, ne prend pas en compte le test, 1n pour simplifier

l’apprentissage. De même, nous ne justifions pas que l’algorithme s’arrête toujours, cela n’a

d’ailleurs toujours pas été démontré !

Ce peut être l’occasion de présenter le problème de boucle infinie et l’importance d’un test

d’arrêt.

Ces « oublis » ne sont pas un manque de rigueur mais une volonté de simplification pour un

apprentissage réussi.

Il ne s’agit pas en 2nd

d’en faire des informaticiens (dans le sens, programmeurs) mais de

leur faire entendre les notions et l’intérêt de l’algorithmique en favorisant une représentation

mentale (ici, à l’aide d’un organigramme).

- Plusieurs prolongements peuvent être envisagés :

Introduction de la boucle TANT QUE : il est possible, en rajoutant le test 1n de

complexifier l’algorithme et d’introduire la notion de TANT QUE, « tant que 1n faire les opérations demandées ».

Manipulation : le logiciel LARP est introduit pour vérifier les résultats, le mode

Pas à Pas permet de contrôler étape par étape le déroulement de l’algorithme et de

bien en comprendre le fonctionnement. Cette activité permet de présenter le logiciel

LARP, en proposant une petite manipulation sans ajouter, pour l’instant, de difficulté

par rapport à la construction de l’organigramme (il est donné aux élèves qui n’ont

qu’à le recopier).

Lectures d’algorithmes : des lectures d’algorithmes plus complexes servent

d’entraînement (toujours travailler la notion de « faire tourner un algorithme à la

main ») et permettent d’introduire de nouvelles notions, par exemple, la boucle FOR.

Les compétences travaillées sont : comprendre et analyser un algorithme préexistant.

L’exemple suivant permet d’introduire le fonctionnement de la boucle FOR en liant

langage naturel et pseudo - langage.

2 L’algorithmique au lycée, DGESCO, Juin 2009


c) TANT QUE vu par la somme d'entiers de 1 à 100

Il existe bien des manières pour sensibiliser les élèves à comprendre le mécanisme pour faire la

somme d'entiers. Certaines seront trop théoriques et d'autres plus pratiques. Ce qui serait intéressant

est d'allier les deux. C'est la raison pour laquelle nous proposons d'utiliser LARP afin d'aider à la

compréhension théorique et de l'allier à une attribution de rôle : un élève compte de 1 à 100 et un

autre mémorise les sommes intermédiaires (il est nécessaire de mémoriser que la dernière après

ajout du compteur).

Les Objectifs d'une telle séance : Consolider la notion de variable informatique grâce une distribution de rôles aux élèves

Consolider la passerelle du langage naturel vers le pseudo - langage

Consolider l’utilisation du « tant que » en partant d’un langage naturel

Mettre en évidence le lien entre la démarche papier et l’automatisation

Les compétences développées :

Vérification de (la condition d’arrêt) l’arrêt de l’algorithme et donc de sa véracité

Analyser la situation :

◦ Transposer la gestuelle papier à l’écriture algorithmique

◦ Gestion de plusieurs variables dont le rôle est bien attribué

Voici un organigramme possible :

Nous vous proposons aussi la fiche d'activité de mise en œuvre en classe pour l'introduction de la

boucle TANT QUE par le tracé de courbe et consolidation par la somme des entiers de 1 à 100 :


Algorithme de tracé de courbe (document élève)

Exercice:

Soit la fonction 2f x x définie sur 3;3 . Écrire l'algorithme qui permet de créer la courbe

représentative de la fonction.

Réflexion:

Le but de cet algorithme est de ..............................................................................................................

................................................................................................................................................................

Algorithme:

Début

Fin


Exercice:

Comment calculer la somme de 1 à 100 (1+2+3+...+98+99+100) avec la boucle tant que.

Réflexion:

Le but de cet algorithme est de ..............................................................................................................

................................................................................................................................................................

Algorithme:

Début

Fin

Un peu de mathématiques :

Il existe une formule mathématique simple. Saurez-vous trouver le résultat sans calculatrice ?

................................................................................................................................................................

................................................................................................................................................................

................................................................................................................................................................

................................................................................................................................................................

................................................................................................................................................................

................................................................................................................................................................

................................................................................................................................................................

................................................................................................................................................................

................................................................................................................................................................

................................................................................................................................................................


Document d'accompagnement de l'enseignant

Titre : Un algorithme simplifié du tracé de fonction

Cadre : Chapitre en cours : Généralité sur les fonctions numériques (partie I)

Ayant choisi de scinder ce chapitre en 2 parties espacées dans l'année, il m'est paru indispensable

d'inclure dans cette première partie la représentation graphique d'une fonction numérique ce qui

laisse une ouverture à l'initiation à l'algorithmique.

Il me paraît évident que l'on ne peut traiter l'algorithmique comme un chapitre indépendant ; ce

chapitre est l'occasion d'introduire des fondements de l'algorithmique, pour notre 2ième

séance, et

ce de manière assez intuitive.

Objectifs : Se familiariser avec le concept d'agencement des idées par étape notamment l'aspect linéaire

(séquentiel) du temps dans l'exécution des instructions par celle de l'affectation à une

variable par incrémentation: le fameux 1i i .

Compréhension de la boucle « tant que ».

Pré-requis : Ensemble de définition

Notions d'image et antécédent

Tracé de la courbe représentative d'une fonction: La courbe est vue comme un ensemble de

points dont les coordonnées ont été calculées dans un « tableau de valeurs » de la fonction.

En algorithmique, notions abordées mais non acquises :

test si … alors … sinon

écriture des idées en français, structurées par étape.

Les Limites : Les outils abstraits utilisés sont choisis par mes soins par une consigne très précise qui, sans

que l'élève ne le sache, retranscrit les limites du langage informatique.

Aucun pseudo-langage n'a été introduit : Le but, dans un premier temps, est d'aider les

élèves à structurer les idées et non à « coder » un programme.

L'optimisation d'algorithme concernant la complexité en temps et en espace n'est pas une

priorité et ne sera pas abordée directement.

Pas de chronométrage précis de la séance afin de ne pas desservir l'intérêt des élèves avec

cette nouvelle notion.

Prolongement : Application des algorithmes en salle informatique sur Algobox.

Répondre à la question : « Existe-t-il un nombre n tel que la somme de 1 à n soit égale à

25765 ? ». Ceci implique une amélioration de l’algorithme, et un travail de test…


Déroulement : Présentation d'une calculatrice graphique et son module de traçage de courbes.

Observation en temps réel du tracé d'une courbe : nous allons essayer de comprendre ce que

fait implicitement la calculatrice :

Occasion de faire un rappel sur le 3ème point des pré - requis

Réflexion sur les grandes étapes de l'algorithme et, par conséquent, explicitation de

son but.

Énonciation précise de l'exercice.

Travail de recherche par les élèves en autonomie en groupe de 4 maximum.

Correction si nécessaire avec introduction de la boucle « tant que » et de l'incrémentation en

pseudo-langage.

Si le temps (timing) le permet : Évaluation de la compréhension des objectifs par un 2ième

algorithme : Calcul de ∑i= 1

100

i avec éventuellement découverte de la formule par un retour

mathématique.


Algorithme de tracé de courbe (document de l'enseignant)

En introduction, je prévois 5 min pour vidéo projeter une calculatrice graphique (exemple Virtual

TI) traçant la fonction 2x sur un intervalle convenable [-10 ; 10] par exemple.

L'idée est de leur demander comment la courbe est apparue : d'un coup? Point par point? Dans

quel sens ? (de gauche à droite) Des points espacés ? Rapprochés ? Et donc à la fin, ils doivent etre

capables de dire que les coordonnées d'un premier point sont calculées puis le point est affiché

ensuite on passe au prochain point etc. Mais on s'arrete quand ? Et on démarre d'où ?...

Ne pas hésiter à demander comment on trace une droite grâce à son équation.

Exercice:

Soit la fonction 2f x x définie sur 3;3 . Écrire l'algorithme qui permet de créer la courbe

représentative de la fonction.

Réflexion:

La réflexion est un moment privilégié pendant lequel on doit énumérer chaque étape dont on aura

besoin ou l'outil que l'on va utiliser:

- Il va falloir construire le tableau de valeur

- Combien de points ? Si beaucoup, quel va être l'espace (le pas) entre chaque point ? C'est le

moment de faire un schéma avec un espace d'une unité entre chaque point et de discuter.

Affiche-t-on les points une fois le tableau de valeur créé ? Ou au fur et à mesure du calcul de

chaque point ? C'est l'occasion de sensibiliser les élèves sur la complexité en temps.

Le but de cet algorithme est de remplir le tableau de valeurs pour plusieurs x et demander à

afficher chaque point ;M x f x au fur et à mesure du calcul.

Algorithme: La colonne de gauche est l'algorithme attendu en français sans pseudo-langage. Les

élèves peuvent y réfléchir en groupe. La colonne de droite est l'algorithme écrit en pseudo-langage

que le professeur pourra donner par la suite.

Début

1) x prend la valeur -3

2) Calculer f(x)

3) Afficher le point ;M x f x

4) Ajouter 0.1 à x

5) Recommencer les étapes 2) 3) et 4)

jusqu'à ce que x soit égal à 3.

Fin

Début

-3 -> x

tant que x<3

afficher ;M x f x

x+ 0.1 -> x

Fin

Dans la colonne de droite, c'est l'occasion d'introduire la notion de "tant que". On notera le décalage

par rapport à la "marge" sous le "tant que", c'est une convention, cela signifie que tout ce qui est

décalé s'exécute dans le "tant que".


Exercice : Comment calculer la somme de 1 à 100 (1+2+3+...98+99+100) avec la boucle tant que.

Réflexion:

Passer en revue la liste de 1 à 100 et additionner au fur et à mesure en sauvegardant les résultats

temporaires.

Si on essaie de calculer cette somme de tete (en mettant les élèves à contribution), on se rend

compte que l'on a besoin de quelqu'un qui compte et de quelqu'un qui calcule et mémorise chaque

résultat. Naturellement, on va pouvoir faire comprendre que pour l'algorithme c'est pareil, on

prendra un "compteur" et une variable "résultat".

Il faudra bien faire comprendre que l'action principale est portée par le compteur qui doit

absolument passer en revue tous les nombres de 1 à 100 sans pour autant que les élèves écrivent

explicitement tous les nombres dans leur algorithme ce qui rendra l'outil algorithme inintéressant.

(cf l'algorithme précédent, on est parti de -3, on a trouvé le mécanisme pour passer aux nombres

suivants, sans les écrire!!!)

Le but de cet algorithme est de donner le résultat final au calcul demandé.

Algorithme :

Début

Prendre un compteur de 1 à 100

Prendre une variable "résultat" initialisée à 0

Ajouter le premier chiffre du compteur au

résultat et mémoriser ce résultat, le

compteur passe au chiffre suivant.

Tant que le compteur n'a pas terminé,

ajouter le nombre du compteur au

"résultat" précédent.

Afficher le résultat.

Fin

Début

1 -> compteur

1 -> résultat

Tant que compteur<100

compteur +1 -> compteur

résultat + compteur -> résultat

afficher résultat

Fin

De manière générale, les élèves mettront compteur 100, ce qui peut etre intéressant lorsque vous

déroulerez l'algorithme : on se rendra compte que la somme calculée sera

1+2+3+...+99+100+101. D'où l'intéret du < et le besoin de vérifier.

Voici une version TI de l'algorithme que l'on peut proposer:


N.B. : La notion de POUR....ALLANT DE....A....... est moins naturelle à communiquer que le

TANT QUE qui se rapproche du français. Il peut être intéressant d'introduire le “POUR” à partir

d'une transformation du TANT QUE car dès que l'on connaît à l'avance le nombre d'étapes du

TANT QUE alors il est possible de le transformer en “POUR” comme le montre l'exemple suivant :


Pseudo - langage et logiciel associé

a) Vers l’écriture d’un algorithme

Exercice 1

On considère l'algorithme ci-dessous Dans la première ligne, on a écrit la liste de toutes les variables

utilisées par la suite.

1. Que renvoie cet algorithme si on entre les nombres 3 ; 2 ;

1 ; 5 ?

2. Que représente la sortie par rapport aux valeurs entrées ?

3. Cet algorithme sert donc à …………………………….

Exercice 2

On souhaite calculer la distance AB entre deux points donnés A et B dont on connaît les

coordonnées dans un repère orthonormal.

1. Soient 1;2A et 4;8B dans un repère orthonormal. Calculer la distance AB .

2. Ecrire un algorithme ci-dessous qui :

- demande à l’utilisateur d’entrer 4 nombres, correspondant aux coordonnées des

points A et B . (On entre d’abord les coordonnées de A puis celles de B ).

- affiche la distance AB .

Variables :

Ax ,Ay ,

Bx ,By ,

Ix , Iy

Début

Entrer Ax

Entrer Ay

Entrer Bx

Entrer By

Ix prend la valeur 2

A Bx x

Iy prend la valeur 2

A By y

Sortir ;IIx y

Fin

Variables :

Début

Fin


Fiche professeur

Objectif : Ecrire des algorithmes en pseudo-langage

× Classe : 2nd

× Durée : 30 min

× Champ du programme : géométrie

× Les registres : en langage naturel, en pseudo-langage




- mettre au point une solution algorithmique : comment écrire un algorithme en

respectant un code, des opérations d’affichage…


simples.

Exercice 1 On considère l'algorithme ci-dessous Dans la première ligne, on a écrit la liste de toutes les variables utilisées par la suite.

1. Que sort cet algorithme si on entre les nombres 3 ; 2 ; 1 ; 5 ? (2 ; 3/2)

2. Que représente la sortie par rapport aux valeurs entrées ?

3. Cet algorithme sert donc à calculer les coordonnées du

milieu d’un segment.

Variables :

Ax , Ay , Bx , By , Ix ,

Iy

Début

Entrer Ax

Entrer Ay

Entrer Bx

Entrer By

Ix prend la valeur 2

A Bx x

Iy prend la valeur 2

A By y

Sortir ;IIx y

Fin


Exercice 2

On souhaite calculer la distance AB entre deux points donnés A et B dont on connaît les

coordonnées dans un repère orthonormal.

3. Soient 1;2A et 4;8B dans un repère orthonormal. Calculer la distance AB .

4. Ecrire un algorithme ci-dessous qui :

- demande à l’utilisateur d’entrer 4 nombres, correspondant aux coordonnées des

points A et B . (On entre d’abord les coordonnées de A puis celle de B ).

- affiche la distance AB .

Variables : xA, yA, xB, yB, d

Début

Entrer xA

Entrer xB

Entrer yA

Entrer yB

Mettre 2 2

xB xA yB yA

dans d

Sortir d

Fin


b) Du pseudo - langage à Algobox

Exercice 1 : On a déjà rencontré l’algorithme ci-dessous écrit sous deux formes. On introduit une nouvelle écriture qui correspond à celle du logiciel que l’on va utiliser :

Instructions écrites en langage courant Ecriture proche de celles des ordinateurs et

calculatrices

Ecriture sous le logiciel Algobox

(1) Demander à l’utilisateur de donner un nombre

Entrer a

(2) Soustraire 5 au nombre mémorisé Mettre 5a dans b


Mettre a b dans c


Mettre 4c dans d

(5) Donner le résultat Sortir d

1. Comparer la 2

ième et la 3

ième colonne.

2. Ouvrir le logiciel Algobox et écrire cet algorithme.

3. Choisir un nombre et faire exécuter l’algorithme. Vérifier la cohérence du résultat. Exercice 2 : Voici un algorithme écrit partiellement dans les trois formes rencontrées.



calculatrices


(1) Demander à l’utilisateur de donner les coordonnées de deux points dans un repère.

Entrer ; ; ;A A B Bx y x y

(2) Soustraire Ax à Bx

(4)

Mettre B Ay y dans Y

(4) Donner ;X Y


1. Remplir les cases vides des deux premières colonnes et les lignes vides de l’algorithme en

langage Algobox dans la troisième colonne.


3. Choisir deux couples de nombres et faire exécuter l’algorithme. Quel est le résultat obtenu ?


Fiche professeur

Objectifs : Passer du pseudo-langage à un langage programmation.

Introduction du langage Algobox.

× Classe : 2nd

× Durée : 45 min

× Champ du programme : fonction, géométrie

× Les registres : en langage naturel, en pseudo - langage, en langage de programmation



- analyser la situation : identifier les données d’entrée, de sortie, de traitement…pour

bien les traduire en programmation

- adapter l’algorithme aux contraintes du langage de programmation : identifier les

variables (la nature), les instructions, les sorties…

- valider un programme simple

Exercice 1 : On a déjà rencontré l’algorithme ci-dessous écrit sous deux formes. On introduit une nouvelle écriture qui correspond à celle du logiciel que l’on va utiliser :

Instructions écrites en langage courant Ecriture proche de celles des ordinateurs et

calculatrices


(1) Demander à l’utilisateur de donner un nombre

Entrer a

(2) Soustraire 5 au nombre mémorisé Mettre 5a dans b


Mettre a b dans c


Mettre 4c dans d

(5) Donner le résultat Sortir d

1. Comparer la 2

ième et la 3

ième colonne.


3. Choisir un nombre et faire exécuter l’algorithme. Vérifier la cohérence du résultat.


Exercice 2 : Voici un algorithme écrit partiellement dans les trois formes rencontrées.



calculatrices


(1) Demander à l’utilisateur de donner les coordonnées de deux points dans un repère.

Entrer ; ; ;A A B Bx y x y

(2) Soustraire Ax à

Bx Mettre B Ax x dans X

(4) Soustraire Ay à

By

Mettre B Ay y dans Y

(4) Donner ;X Y

Sortir ;X Y

1. Remplir les cases vides des deux premières colonnes et les lignes vides de l’algorithme en

langage Algobox dans la troisième colonne.


3. Choisir deux couples de nombres et faire exécuter l’algorithme. Quel est le résultat obtenu ?

Commentaires :

- Cette activité permet de travailler la structure en trois phases d’un algorithme : entrée,

traitement, sortie.

- Manipulation : le logiciel Algobox est présenté aux élèves au début du deuxième trimestre

(utilisation en classe entière à l’aide d’un TBI, puis manipulation en recopiant un algorithme

donné). Il s’agit ici, uniquement, de recopier l’algorithme complété pour se familiariser avec

l’utilisation du logiciel. On n’attend ni que les élèves sachent manipuler parfaitement le

logiciel ni qu’ils écrivent directement un algorithme sous Algobox.

x_B est du_type_nombre type_nombre y_B est du_type_nombre type_nombre X est du_type_nombre type_nombre

Lire y_A type_nombre Lire x_B

X PREND_LA_VALEUR x_B - x_A

AFFICHER X


c) D’Algobox au pseudo - langage

Exercice 3 On a écrit ci-dessous un algorithme en Algobox. Le traduire en pseudo - langage.


Fiche professeur

Objectif : Maîtriser le changement de langage.

× Classe : 2nd

× Durée : 15 min

× Champ du programme : numérique

× Les registres : en pseudo - langage, en langage de programmation




- valider un programme simple

Exercice 3 On a écrit ci-dessous un algorithme en Algobox. Le traduire en pseudo - langage.

Variables : , , ,a b c d Début Entrer a Mettre 3a dans b Mettre 2b dans c Mettre 7c dans d Sortir d Fin


d) Traduire l’algorithme de calcul de distance en Algobox

Exercice 4

1. Reprendre l’algorithme écrit pour le calcul de la distance AB et le transcrire sous Algobox.

2. Compléter le tableau suivant :

;

;

A A

B B

A x y

B x y

1;4A ; 2;5B 1; 5A ; 4;3B 5;6A ; 7; 8B

Distance AB


Fiche professeur

Objectif : Ecrire en langage de programmation : du pseudo - langage au langage de programmation

× Classe : 2nd

× Durée : 20 min en salle informatique ou en salle de classe équipée d’un TBI.

× Champ du programme : géométrie




- mettre au point une solution algorithmique : comment écrire un algorithme en

respectant un code, des opérations d’écriture, d’affichage…

- valider la solution algorithmique par des traces d’exécution et de jeux d’essais

simples

- adapter l’algorithme aux contraintes du langage de programmation : identifier les

variables (la nature), les instructions, les sorties…

- valider un programme simple.

Exercice 4

1. Reprendre l’algorithme écrit pour le calcul de la distance AB et le transcrire sous Algobox.

L’algorithme à traduire est :

Variables : xA, yA, xB, yB, d

Début

Entrer xA

Entrer xB

Entrer yA

Entrer yB

Mettre 2 2

xB xA yB yA dans d

Sortir d

Fin


Avec Algobox

Phase d’entrée

En ouvrant le logiciel, la page d’accueil est la suivante :

On déclare les 4 variables qui sont des variables de type « nombre ».


En réitérant, on obtient ce qui suit :


Phase de traitement

En cliquant sur « Nouvelle Ligne », une ligne apparaît sous « DEBUT_ALGORITHME » pour

affecter les variables et entrer les instructions.

Pour entrer


Cliquer sur « Nouvelle Ligne » puis renouveler l’instruction « LIRE variable » pour entrer

Ay ,

,B Bx y en utilisant le menu déroulant.

Cliquer sur « Nouvelle Ligne » puis sur « AFFECTER valeur à variable ». Pour affecter la valeur à d .

pow(y_A-y_B,2) signifie .


Il reste à afficher d .

Phase de sortie Cliquer sur « Nouvelle Ligne » puis sur « AFFICHER Variable », enfin choisir d dans le menu déroulant.

L’algorithme traduit sous Algobox est :

2. Compléter le tableau suivant, en donnant des valeurs approchées à 210 près.


;

;

A A

B B

A x y

B x y

1;4A ; 2;7B 1; 5A ; 4;3B 5;6A ; 7; 8B

Distance AB 3,16

8,54 14,14

Pour compléter le tableau, appuyer sur « Tester Algorithme ». Puis entrer les cordonnées des points.


Méthodologie

En créant ces activités, nous avons cherché à instaurer une progressivité dans les apprentissages afin

de travailler régulièrement et tout au long de l’année les différents registres (langage naturel,

pseudo - langage, langage de programmation) et évaluer toutes les compétences algorithmiques.

Voici un schéma récapitulatif :


Approfondissements Rappelons que l'algorithmique est, en générale, difficilement accepté par les élèves. Il est donc

primordial de créer un contexte (cadre) le plus approprié possible. Il est donc important de faire un

point sur la mise en œuvre, dans la mesure du possible, des activités d'approfondissement :

Il faut favoriser :

La recherche individuelle : les élèves « s’imprègnent du sujet »

Le travail de groupe :

◦ Favorise les échanges et l’autonomie des groupes

◦ Permet souvent la participation des élèves en difficultés (différenciation et

gestion de l’hétérogénéité sur un même projet global) sur un problème ouvert

leur permettant d’apporter leurs démarches personnelles.

La production d’affiches : production d’une solution exprimée en langage naturel

L’affichage des productions et créer un débat :

Partir des représentations des élèves, exprimées en langage naturel pour

établir un langage commun qui devient alors nécessaire (amener

progressivement vers le pseudo - langage…).

Document ressource « Algorithmique »: […] mise en place d’activités de groupe permettant des

premières réflexions autour de la notion d’algorithme dans le cadre de situations axées sur la

communication. […] après un temps d’investigation les élèves seront charges de produire un

≪texte≫ (écrit ou oral) compréhensible et directement utilisable par leurs camarades par

exemple.

[…]Dans la progression pédagogique on aura intéret à passer par des phases de tâtonnement,

d’expression orale, d’échanges sans chercher à aborder trop rapidement la formalisation écrite qui

peut s’avérer bloquante pour certains.

Pour cela, voici un vade-mecum de la mise en œuvre :

Anticiper les blocages des élèves

Proposer des aides sous formes de questions permettant à l’élève de poursuivre sa réflexion

◦ Quelles sont tes connaissances en algorithmique?

◦ As-tu bien compris l’énoncé? Peux-tu reformuler le problème?

◦ Quelle est la structure d’un algorithme?

◦ Que pourrais-tu faire pour comprendre l’algorithme?

◦ Etc.

Faire tourner un algorithme (méthode pas à pas) doit devenir un automatisme chez l’élève

◦ Tout au long de l’année, le professeur habituera les élèves à faire « tourner un

algorithme » afin que cela devienne une méthode pour analyser et

comprendre un algorithme.

◦ Le professeur pourra éventuellement aider les élèves en difficulté en faisant

« tourner » avec eux l’algorithme pour quelques valeurs. Le principal étant

que les élèves démarrent l’exercice afin de pouvoir essayer, tâtonner,

expérimenter, conjecturer…avoir une démarche scientifique.


Voici quelques exemples d'approfondissement :

a) Dictionnaire d'algorithmique

Si on désire que les élèves conçoivent des algorithmes ou les comprennent et les modifient, ils

seront demandeurs de limites.

En effet, qu'est-ce-que j'ai le droit de faire et de ne pas faire en algorithmique ?

L'expérience accumulée lors des séances précédentes facilitera l'acquisition de ce savoir-faire. Il

est important que cette limitation de vocabulaire algorithmique, que cet accouchement

d'instructions que l'on connaît et que l'on s'autorise viennent de l'élève. Cela « cassera des

barrières » pour la compréhension et augmentera considérablement le capital confiance de l'élève.

N'hésitons pas (prenons meme jusqu'à 15 min) alors à demander aux élèves ce qu'ils connaissent

comme instructions en algorithmique, ce qu'ils ont déjà lu... “tout ce que peut faire un ordinateur”

L'occasion sera alors bonne pour revoir les fondamentaux des théorèmes : l'importance des

hypothèses lorsque l'on a un “si”...

Voici ce qui en est ressorti.


Dictionnaire en algorithmique

Il est important dans tout algorithme de déclarer (annoncer en premier lieu) les variables que l'on

va utiliser et aussi le type d'objet que l'on va y attribuer. Est-ce un nombre, un entier, du texte... ??

Ceci nous amène à utiliser l'instruction de déclaration en listant toutes les variables avant le début

de l'algorithme.

On passe ensuite au corps de l'algorithme :

Opérations de bases : + ,× ,−,÷ ,√, an...

Saisir ou Lire : L'ordinateur attend que quelqu'un “tape” au clavier une valeur.

Afficher : L'ordinateur envoie à l'écran la valeur d'une variable ou du texte.

Prend la valeur : Une variable prend une certaine valeur.

Tracer un point : L'ordinateur affiche le point dont les coordonnées seront écrites entre parenthèses

à la suite de l'instruction.

Tracer un segment : L'ordinateur affiche le segment d'extrémité les points dont les coordonnées

seront placées à la suite de l'instruction séparées par une flèche (ex : tracer un segment (x,y)->(a,b) )

Si .....1..... Alors .....2..... Sinon .....3..... : C'est une instruction conditionnelle, cela signifie qu'il y a

une condition à remplir pour accéder au “alors”, exemple : “Si je n'ai pas 18 ans, alors je ne sors

pas en boîte de nuit”.

Tant que .....1..... Alors .....2..... : C'est aussi une instruction conditionnelle, qui a une nuance face au

“si ... alors ... sinon...”. En effet, le “si ... alors ... sinon...” est ponctuel, alors que le “tant que...”

connote un effet de répétition jusqu'à ce que je valide la condition. On teste la condition, si on ne la

remplit pas, on la teste encore une fois, puis encore... jusqu'à ce qu'on la valide, exemple : “tant que

je ne m'assume pas, alors je dois écouter mes parents”.

Par quoi peut-on alors remplacer les chiffres .....1..... , .....2..... , .....3..... dans les 2 instructions vues

ci-dessus ?

.....1..... est une condition :

a = b

a ≠ b

a < b

a > b

a ≤ b

a ≥ b

.....2....., .....3..... on met une instruction vue dans le corps de l'algorithme.


b) Etude d’algorithmes erronés

Un exercice exigible et fort intéressant pour augmenter le capital confiance des élèves est l'étude

d'algorithmes erronés.

Elle permet de:

Privilégier une pédagogie par l’erreur (on cherche, on essaye, on se trompe, on vérifie…)

par le biais de débats, d’échanges oraux sur les productions des élèves (cf. doc ressource

« raisonnement au collège »)

Document ressource « Algorithmique » : Par ailleurs, il conviendrait de ne pas

négliger la richesse de l’apprentissage à partir d’algorithmes erronés. Le travail de

correction, de recherche de dysfonctionnements de certains algorithmes, l’étude des

cas particuliers sont des pistes qu’il conviendrait d’explorer.

Faire tourner un programme (notamment avec le « pas à pas ») permet de montrer qu’il

contient des erreurs

Faire des observations:

◦ Erreurs classiques liées à l’affectation, déclaration variables, = = du test et =

de l’affectation…

◦ Erreurs classiques liées à l’affichage : les élèves confondent souvent afficher

n et afficher « n » .

◦ Dans les boucles (essentiellement pour le « tant que »), les erreurs souvent

constatées sont :

◦ L’initialisation de la variable que l’on va incrémenter

◦ La condition d’arrêt de la boucle

◦ L’ordre des instructions car elle peut provoquer des erreurs.

Voici deux exemples d'algorithme erroné :

Le premier exemple favorise l'attention sur la condition d' arret : en effet le résultat obtenu ici est la

somme de 1 à 101.

Le second exemple favorise l'attention sur l'initialisation : en effet le résultat obtenu ici est la

somme de 1 à 100 + 1.


c) Algorithme de tris

Cette notion est bien entendu à un niveau très élevé par rapport aux attendus de la seconde. De ce

fait, il ne faut pas hésiter à baisser les exigences pour rendre la séance pédagogique.

Pourtant, plusieurs intérêts sont mis en avant pour une telle séance :

Travail de groupe en langage naturel: (favorise le dialogue)

Introduction nécessaire au type abstrait « tableau » (légitimer par un réinvestissement pour

la recherche de la médiane d’une série statistique)

Vérification au « pas à pas »

Lecture/compréhension et complétion d’algorithme

Réinvestissement de la procédure « échange »

Introduction intuitive à la complexité en temps (cf wikipédia : des animations sur le tri sont

proposées)

Amélioration de la compréhension des entrées/sorties

De part sa complexité, la fiche d'activité proposée s'est déroulée de manière particulière :

La première page de la fiche s'est déroulée sur une séance de 1h sans aucun support. Le

scénario a été écrit au tableau, les élèves ont réfléchi à un algorithme sur leur brouillon en

groupe de 4 en français. Le passage au pseudo - langage s'est fait par une distribution de

rôle : un élève jouait le rôle d'une variable, nous avons donc eu besoin de 3 élèves. Le

professeur a ensuite donné l'algorithme en pseudo - langage et a distribué la correction en

début de séance prochaine.

La seconde page s'est déroulée sur deux séances de 1h : une première séance pour la

compréhension du second algorithme, et une autre séance pour la partie statistique.

Il est évident que lors de la toute première séance, les élèves ont une multitude de choix pour trier le

tableau. L'idée est alors de les orienter vers le tri par minimum sans créer de nouveau tableau

vide ! (par soucis de complexité en espace).


Scénarios de tris et application à la statistique

Voici un tableau de 10 nombres :

8 2 4 1 6 0 3 5 9 7

Comment trier ce tableau dans l'ordre croissant sans utiliser un deuxième tableau mais en échangeant les

nombres de place ?

Réflexion de la classe :

recherche du plus petit élément

parcourir le tableau nombre par nombre

échanger un nombre au fur et à mesure du parcours avec le plus petit élément restant

Écrire l'algorithme en français :

Solution de la classe :

rechercher le plus petit élément du tableau, et l'échanger avec l'élément d'indice 1 ;

rechercher le second plus petit élément du tableau, et l'échanger avec l'élément d'indice 2 ;

continuer de cette façon jusqu'à ce que le tableau soit entièrement trié.

Écrire l'algorithme en pseudo - langage (langage informatique) :

Aide du professeur :

Si le tableau s'appelle T,

T[i] représente le ième nombre du tableau. Par exemple, dans le tableau au dessus,

T[3] est le 3ème nombre, c'est à dire 4.

T[1]>T[6] car T[1] est 8 et T[6] est 0.

Il va donc falloir parcourir le tableau en entier afin de mettre dans chaque case le nombre

correspondant. Il y aura donc une répétition pour chaque case, ce qui implique une boucle. Nous

connaissons la taille du tableau, et donc le nombre de répétitions, on peut utiliser une boucle “pour”.

À chaque case d'indice i que l'on parcourt, il va falloir comparer son nombre avec tous les autres

nombres restant du tableau pour déterminer le plus petit que l'on placera dans cette case d'indice i.

Cette comparaison implique une recherche par répétition après la case d'indice i et donc elle

commencera à la case d'indice i+1.

Il faudra sauvegarder l'indice de la case dans laquelle se situe le plus petit élément. Appelons cette

variable “min”.

Solution des élèves :

début

| afficher : “Rentrer la taille n du tableau :”

| lire n

| pour i de 1 à n – 1 //on va parcourir le tableau case par case pour mettre la bonne valeur dans la case correspondante

| | min ← i //au départ, elle est initialisée à la première case de la partie du tableau restant à trier.

| | pour j de i + 1 à n //on parcourt le reste du tableau pour chercher le plus petit élément

| | | si t[j] < t[min], alors min ← j //si le plus petit élément n'est pas à l'indice min, on sauvegarde e nouvel indice

| | si min ≠ i, alors échanger t[i] et t[min] //on échange éventuellement les éléments d'indices i et min

fin

http://fr.wikipedia.org/wiki/Plus_petit_élément


Essayez cet algorithme à la main, sur du papier et répondez aux 2 questions suivantes :

Pourquoi, à la troisième ligne, “i” va jusqu'à “n-1” ? ............................................................

.........................................................................................................................................................................

Pourquoi, à la dernière ligne, le test “si min ≠ i” est effectué ? ..............................................................................

........................................................................................................................................................................................

Un autre algorithme de tri:

T est un tableau de N nombres

i est du type entier

permut est du type booléen

début

| REPETER

| | permut = FAUX

| | POUR i VARIANT DE 1 à N-1 FAIRE

| | | SI T[i] > T[i+1] ALORS

| | | | echanger T[i] et T[i+1]

| | | | permut = VRAI

| | | FIN SI

| | FIN POUR

| TANT QUE permut = VRAI

fin

En reprenant le tableau du précédent exemple,

décrivez en français ce que fait l'algorithme :

...................................................................................

...................................................................................

...................................................................................

...................................................................................

...................................................................................

...................................................................................

...................................................................................

...................................................................................

...................................................................................

...................................................................................

Conclusion :

Nous avons donc vu 2 algorithmes pour trier une série de nombres. Le premier cherche à ..........................

...................................................................................................................................................................... .

Le 2nd

fait ...................................................................................................................................................... .

Un peu de statistique :

Rappelez les étapes pour trouver la médiane

d'une série statistique :

.............................................................................

.............................................................................

.............................................................................

Pour une série statistique ordonnée d'effectif

total 15, où se trouve la médiane ?: .................

.............................................................................

Pour une série statistique ordonnée d'effectif

total 14, comment trouver la médiane ?..........

.............................................................................

Généralisons, si N est impaire, où se trouve

la médiane ? ......................................................

Et si N est paire, où se trouve la médiane ?

.............................................................................

.............................................................................

Complétez l'algorithme, en pseudo - langage, qui

détermine la médiane d'une série statistique.

tab est un tableau de N nombres

médiane est du type nombre

début

| ........ tab.

| SI mod(N,2)=....

| débutSI

| | .......prend la valeur

| finSI

| SINON

| débutSINON

| | .......prend la valeur

| finSINON

| AFFICHER mediane

fin

tab [....]+ tab[ ....]

2

tab [.......

2]

* mod(a,b) représente le reste de la

division de a par b. Ici on cherche à avoir

le reste de la division de N par 2.


d) Complexité

Le chapitre Équation est idéal pour insister sur l'état d'esprit dans lequel on doit être pour faire de

l'algorithmique sans que les élèves ne s'en aperçoivent.

En effet, grâce aux cartes mentales (ou représentation schématique), on peut schématiser la leçon

comme suit :

On se rend compte que ce schéma utilise bien des notions présentes en algorithmique et habituent

les élèves. Mais surtout, il donne naissance à un second schéma qui devient directement intéressant

pour notre exercice. En effet, si l'on désire savoir le nombre éventuel de solution à un système

d'équation,

{ a x+ b y=ca ' x+ b' y=c '

On peut schématiser comme suit :

Droites verticales

x = c

Droites non verticales

y = ax+b

y=b y = ax

Droites horizontales Droites qui passent par l'origine

Si a=0 Si b=0

Si (a,b) et (a',b') sont proportionnels de

coefficient k Sinon

Les droites sont confondues

Les droites sont parallèles

Les droites sont sécantes

Si c et c' sont proportionnels de coefficient k

Sinon


L'exercice est alors de leur demander d'écrire un algorithme qui demande les coefficients des 2

équations et qui conclut si les 2 droites sont soit confondues, parallèles, sécantes.

La difficulté désormais est de savoir comment on traduit la proportionnalité en mathématiques, car

il est évident que l'ordinateur ne comprendra pas l'instruction “est proportionnel”. En revanche,

grâce au tableau de proportionnalité, les élèves savent trouver le coefficient. C'est ce qu'il va falloir

mettre en évidence pour la progression.

Voici la version que les élèves ont fournie :

1 VARIABLES 2 a EST_DU_TYPE NOMBRE 3 b EST_DU_TYPE NOMBRE 4 c EST_DU_TYPE NOMBRE 5 a1 EST_DU_TYPE NOMBRE 6 b1 EST_DU_TYPE NOMBRE 7 c1 EST_DU_TYPE NOMBRE 8 DEBUT_ALGORITHME 9 SI (a/a1=b/b1 et a/a1=c/c1) ALORS 10 DEBUT_SI 11 AFFICHER "les droites sont confondues" 12 FIN_SI 13 SI (a/a1=b/b1 et a/a1!=c/c1) ALORS 14 DEBUT_SI 15 AFFICHER "les droites sont parallèles" 16 FIN_SI 17 SI (a/a1 != b/b1) ALORS 18 DEBUT_SI 19 AFFICHER "les droites sont sécantes" 20 FIN_SI 21 FIN_ALGORITHME

Cet algorithme fonctionne bien, mais il n'est pas optimal. En effet, aux deux premières conditions,

on opère 8 opérations : 4 divisions, 2 tests d'égalité, 1 opération relation “et”, et 1 affichage de

message.

Pour la troisième condition, on compte 4 opérations, soit, au total, 20 opérations.

Dans la version suivante, très proche du schéma ci-dessus, on compte 9 opérations. J'ai retiré des

lignes inutiles pour la lisibilité : des “début_SI” et “fin_SI”

1 VARIABLES 2 a EST_DU_TYPE NOMBRE 3 b EST_DU_TYPE NOMBRE 4 c EST_DU_TYPE NOMBRE 5 a1 EST_DU_TYPE NOMBRE 6 b1 EST_DU_TYPE NOMBRE 7 c1 EST_DU_TYPE NOMBRE 8 DEBUT_ALGORITHME 9 SI (a/a1=b/b1) ALORS 10 DEBUT_SI 11 SI (a/a1=c/c1) ALORS 13 AFFICHER "Les droites sont confondues" 15 SINON 17 AFFICHER "Les droites sont parallèles" 19 FIN_SI 20 SINON 21 DEBUT_SINON 22 AFFICHER "Les droites sont sécantes" 23 FIN_SINON 24 FIN_ALGORITHME


Compétences et évaluations

a) Eléments théoriques et extraits des documents ressources

Une compétence est un ensemble cohérent et indissociable de connaissances, de capacités et

d’attitudes

Exemples

Connaissances : Théorème de Pythagore

Capacité : Calculer une longueur à partir du théorème de Pythagore

Attitude : Sens de l’observation, rigueur, goût du raisonnement, attitude critique face aux

résultats…

Une compétence s’acquiert en continu et progressivement.

Elle renvoie à un modèle d’apprentissage spiralaire (non-linéaire) :

- Qualité d’une production

- Répétition de cette qualité

On peut distinguer trois degrés dans l’acquisition et l’évaluation d’une compétence :

Compétence de premier degré : Débutant

Savoir exécuter une opération en réponse à un signal (une question, une consigne, une situation

connue et identifiable sans ambiguïté ni difficulté).

Exemple : Calculer la longueur d’un côté d’un triangle rectangle connaissant les deux autres.

Compétence de deuxième degré : Confirmé

Posséder toute une gamme de compétences élémentaires et savoir dans une situation inédite choisir

celle qui convient.

Exemple : Calculer la longueur de la diagonale d’un carré

Compétence de troisième degré : Expert (c’est le niveau visé – « maîtrise de la compétence »)

Savoir choisir et combiner correctement plusieurs compétences élémentaires pour traiter une

situation nouvelle et complexe.


Exemple :

Pour résoudre ce problème, l’élève doit mobiliser des connaissances (Théorème de Pythagore,

racine carrée…), des capacités liées à ces connaissances (calculs de longueur…) et des attitudes

(choix des bons savoir - faire, goût du raisonnement…).

On évalue ainsi des compétences par ce genre de problème appelé tâche complexe (qui ne veut pas

dire forcément compliqué !).

Evaluer ne veut pas dire forcément noté

L’évaluation est un élément majeur du processus de formation.

Elle cherche à situer l’état des acquis des élèves par rapport aux objectifs d’apprentissages

visés.

Elle permet de mesurer les progrès et de mettre en place des remédiations personnalisées.

Elle doit permettre aux élèves de cibler les points faibles et les impliquer ainsi dans le processus

d’apprentissage (auto-évaluation).

Pour cela, la note ne s’avère pas indispensable pour donner l’information : croix, pastille verte,

appréciation…

BO – Programme de MPS

« L’évaluation peut prendre des formes variées afin de valoriser l’acquisition de compétences et

de qualités telles que l’autonomie, l’initiative, l’engagement dans une démarche scientifique, le

travail d’équipe, le raisonnement et la communication écrite et orale »


Document ressource « raisonnement » au lycée:

• Les compétences évaluées « raisonner, démontrer, élaborer une démarche » ou « développer

une démarche connue, mettre en forme un raisonnement » sont des compétences évaluées au

baccalauréat dans toutes les séries.

• Il convient donc d’évaluer progressivement dès la classe de seconde les apprentissages sur

la logique et le raisonnement.

• L’évaluation peut être faite à l’oral. Etre capable de reformuler de manière mathématique

un énoncé est une compétence qu’il convient de faire acquérir dans le dialogue et le débat.

A l’écrit, de la meme manière qu’au collège, deux principes essentiels doivent etre retenus :

distinguer le fond de la forme

valoriser des écrits intermédiaires […], les efforts de clarté, d’explication (éventuellement

sous forme de bonus)

• Evaluation possible par l’élève lui-même (auto-évaluation), par un autre élève ou groupe

d’élèves (cf. Doc ressource « raisonnement au collège »)

Document ressource « Algorithmique » au lycée:

L’évaluation des pratiques en algorithmique peut s’organiser autour d’une évaluation par

compétences qui ne conduira pas nécessairement a 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 à un problème donné.

et, d’autre part, à la résolution de problèmes telles que :

a) modéliser et s’engager dans une activité de recherche ;

b) faire une analyse critique ;

c) pratiquer une lecture active de l’information (critique, traitement), en privilégiant les

changements de registre (graphique, numérique, algébrique, géométrique) ;

d) communiquer à l’écrit et à l’oral.


b) Evaluation sur des productions écrites – Exemples de mise en œuvre

Enoncé :

Un travail de groupe a été effectué où les élèves ont travaillé en autonomie.

Le professeur est présent pour aider les élèves, il est présent en tant que « personne ressource ».

Voici quelques productions d’élèves commentées avec exemples d’évaluations :

Production 1 :

Travail sur le langage naturel:

• Introduction progressive de l’usage des

boucles

• Mise en place d’une syntaxe commune à

partir des productions d’élèves

Compétences évaluées positivement

Créer:

Communiquer:


Production 2 :

Sur l’importance des mots utilisés – Lien avec l’affectation

1ère

production: Créer: En cours d’acquisition

2ème

production: Créer: Modéliser:


Autre exemple :

Enoncé :


Production d’élève :

Phase de « tâtonnement, essais »

par la méthode « pas à pas »

• Faire « tourner l’algorithme »

pour établir des conjectures

• Principe d’une démarche scientifique

Les conjectures permettent aux élèves d’arriver à une conclusion:

Analyser:

Compétences liées à la résolution de problème:


c) Evaluation orale

L’évaluation peut se faire à l’oral (en cours d’apprentissage mais aussi en évaluation

sommative). Elle permet notamment de :

• Différencier : Suivi uniquement de quelques élèves

• Pointer des compétences non observables à l’écrit

• Valoriser des élèves sur d’autres compétences, liées à la démarche scientifique

(communiquer, argumenter…)

Le professeur pourra lister les compétences algorithmiques sur une fiche de suivi ainsi que les

compétences liées à la résolution de problèmes (voir fiche de suivi ci-dessous).

Pendant chaque séance, il pourra évaluer positivement des compétences par l’oral observées

chez quelques élèves.

L’objectif n’est pas d’évaluer tous les élèves sur toutes les compétences (difficilement gérable)

mais de relever des manifestations positives d’une compétence.

Puis après chaque séance, il pourra évaluer d’autres compétences grâce aux productions écrites

des élèves.

d) Exemple de fiche de suivi pour l’évaluation par compétences


Evaluation par compétences – Fiche élève

Le professeur à tout moment (oral, écrit, devoir surveillé…) peut relever des

manifestations positives d’une compétence.

Il peut également former les élèves à l’auto-évaluation sur ces compétences.

(« dans notre activité, à quoi correspondait la compétence « Analyser un algorithme ?

Pensez-vous l’avoir réussi ? »)

Ainsi c’est l’élève lui-même qui se mettra « les verts » (facilité de gestion).

La partie droite est applicable dans d’autres domaines comme pour MPS.

La valeur clé ici pour valider une compétence est la constance (d’où l’importance de

l’évaluer de manière répétée, de manière spiralée).

Ce diagramme permet en outre à l’élève de s’auto-évaluer, de cibler ses points faibles.

Il permet au professeur d’observer rapidement les difficultés et de mettre en place des

remédiations.


e) Evaluation basée sur l’épreuve expérimentale de terminale S

On considère l’algorithme suivant :

1. Quelle sera la sortie de cet algorithme avec l’entrée 5 puis avec l’entrée -7 ?

2. Donner l’expression algébrique de la fonction définie sur par cet algorithme.

Appeler le correcteur pour valider vos résultats

3. Traduire votre algorithme en langage algobox.


4. A l’aide de l’algorithme, remplir le tableau ci-dessous :


5. Modifier l’algorithme pour pouvoir remplir le tableau de valeurs en une seule fois.

6. Faire afficher les points correspondants.


7. Modifier l’algorithme pour remplir le tableau suivant :

x -5 -4 -3,5 -2 -1 0 1,25 2 3 4 5

f x


Début

Saisir x 23A x

4B x

6C A B

Afficher C .

Fin

x -5 -4 -3 -2 -1 0 1 2 3 4 5

f x


Fiche professeur

× Classe : 2nd

× Durée : 1h en salle informatique

× Champ du programme : fonction, numérique


× Les compétences à évaluer en algorithmique :

- analyser le fonctionnement ou le but d’un algorithme existant

- modifier un algorithme existant pour obtenir un résultat précis

- créer un algorithme en réponse a un problème donné.

× Les compétences à évaluer en résolution de problèmes : - modéliser et s’engager dans une activité de recherche

- faire une analyse critique ;

- pratiquer une lecture active de l’information (critique, traitement), en privilégiant les

changements de registre

- communiquer à l’écrit et à l’oral.

Grille d’évaluation associée

Compétences évaluées Eléments permettant de situer l’élève

Com

pét

ences

alg

ori

thm

iqu

es

An

aly

ser l

e fo

nct

ionnem

ent

d’u

n a

lgori

thm

e L’élève est capable

d’exécuter quelques étapes

de l’algorithme.

L’élève est capable de tirer

profit des indications

éventuellement données à

l’orale pour déterminer les

deux images demandées.

L’élève est capable

d’expérimenter, de faire des

essais pour comprendre le

but de l’algorithme.

créer

un a

lgori

thm

e en

ré

ponse

à u

n p

roblè

me

donné

L’élève sait identifier les

variables, la nature des

variables, les déclarer, et

leur affecter une valeur ;

identifier les données

d’entrée, de sortie et la

phase de traitement.

L’élève sait faire afficher un

résultat.


Mo

dif

ier u

n

alg

ori

thm

e ex

ista

nt

L’élève comprend quelle est

la nature de la modification

à apporter et sait la traduire

avec Algobox.

C

om

pét

ences

ré

solu

tio

n d

e p

rob

lèm

es fa

ire

un

e a

naly

se

crit

iqu

e :

vér

ifie

r,

réag

ir

L’élève a vérifié ses

résultats avec la table de la

calculatrice ou a validé la

solution algorithmique par

des traces d’exécution et des

jeux d’essais simples.

Com

mu

ni

qu

er à

l’

ora

l

L’élève sait expliquer ses

résultats, la traduction de

l’algorithme et ses

éventuelles vérifications.

Au

ton

om

ie, p

rise

d’i

nit

iati

ve

L’élève est autonome. Les

appels à l’aide sont modérés

et utilisés de façon

constructive.

L’élève sait faire appel à des

notions antérieures : la

courbe représentative de la

fonction f est l’ensemble

des points de coordonnées

; )x f x .

Commentaires :

Plusieurs annonces « Appeler le correcteur pour valider vos résultats » favorisent l’autonomie

des élèves. Ces derniers ne peuvent demander de l’aide ou appeler l’enseignant qu’à ces moments

précis.

Cette formule les a incités à chercher davantage (au lieu d’appeler le professeur sans réfléchir, à la

première difficulté).

La grille d’évaluation n’est pas exhaustive, elle peut aussi être simplifiée.

Elle permet d’évaluer les compétences algorithmiques mais aussi les compétences en raisonnement

et en résolution de problèmes qui sont liées.

Documents

Algorithmique Progressivité des usages, compétences et ...maths.ac-reunion.fr/IMG/pdf/Synthese_stage_ALGO_2012-2013.pdf · Groupe Académique Tice La Réunion – 20 octobre 2012