Embed Size (px)
Citation preview
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
L’enseignement de l’algorithmique
Stéphane Clément
Lycée Jean Cocteau -
26 novembre 2009
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
Introduction
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
Présence universelle des algorithmes
Dans le rapport de la commission Kahane sur l’informatique :
« ... Mais cette présence qui se renforce, est souvent occultée auxyeux du public qui ne voit que le produit fini ».
Cette observation s’applique parfaitement aux algorithmes dont onvoit plus souvent les résultats que les principes fondamentaux.
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
Quelques recommandations
L’algorithmique a une place naturelle dans tous les champs desmathématiques et les problèmes posés doivent être en relation avecles autres parties du programme
La pratique de l’algorithmique ne se résume pas à l’écriture deprogrammes ; il serait même judicieux de ne pas commencer par là
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
Quelques recommandations
Les travaux proposés pourront être conçus dans une perspectived’action de l’élève...
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
De quoi s’agit-il ?
de mettre en évidence et d’expliciter des algorithmessous-jacents à certaines pratiquesd’étudier, de simuler et de formaliser des algorithmesde concevoir et de construire des algorithmes pour résoudre unproblème donné
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
La surprise de lanouveauté ?
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
Est-ce une nouveauté pour nos élèves ?
Algorithme de la multiplicationAlgorithme de la divisionSimulation d’un lancé de dé avec un tableurProgramme de constructionRecherche de la médiane d’une série statistique
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
Des algorithmes partout et depuis toujours
résolution d’une équation du second degréalgorithme d’Euclide de calcul du PGCD de deux entiers naturelscalcul d’une valeur approchée de
√N par la méthode de Héron
« macros », « prototypes », « nouveaux outils » des logiciels degéométrie dynamiquesouvent, dès que l’on décrit une technique, on n’est pas loind’écrire un algorithme
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
Des algorithmes partout et depuis toujours
Circulaire du 6 avril 1971 : l’enseignement du calcul dans lesétablissements du second degré.
[...] Les élèves apprendront à organiser un calcul et à en dresserl’organigramme ; ils établiront par exemple la feuille de calcul desvaleurs d’une fonction numérique f donnée, en blanc, avant tout choixde valeurs de la variable x ; c’est déjà l’élaboration d’un programme,une voie ouverte vers l’informatique [...]
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
La pensée algorithmique :une pensée « constructive »
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
Un algorithme, qu’est-ce que c’est ?
une façon systématique de procéder pour faire quelque chose :calculer, trier, rechercher,...
ou plus précisément :
une suite finie de règles à appliquer, dans un ordre déterminé, àun nombre fini de données pour obtenir, en un nombre finid’étapes, un certain résultat et cela indépendamment desdonnées
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
Les ingrédients des algorithmes
Pour bâtir des algorithmes, on utilise trois grands principes :Combiner des fonctions : faire ci puis ça. Par exemple, pouradditionner A, B et C : additionner A et B, puis additionner lerésultat à C.Introduire des branchements : si ceci alors cela sinon ...Utiliser des boucles et des récursions.
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
L’apport de la pensée algorithmique
Un petit problème récréatif :
deux promeneurs arrivent successivement dans un jardin public,désert, où sont disposés trois bancs assez larges pour accueillir deuxpersonnes. Ces deux promeneurs s’asseoient au hasard sur l’un desbancs.Quelle est la probabilité que les deux promeneurs s’asseoient sur lemême banc ?
On peut envisager de répéter un grand nombre de fois une simulationde l’expérience et construire un algorithme réalisant ce travail...
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
Mise en œuvreL’algorithmique s’utilise dans les trois domaines du programmes.
Je vais vous proposer quelques exemples (en construction) àdébattre.
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
Dans le domaine "géométrie"
Déterminer si des points sont alignés.Première technique :
On calcule les coordonnées de−→AB et de
−→AC.
Si−→AB et
−→AC sont colinéaires alors les points A, B et C sont
alignés.
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
Déterminer si des points sont alignés.
Première technique avec Scratch :
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
Déterminer si des points sont alignés.Première technique avec Algobox :
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
Déterminer si des points sont alignés.
Première technique avec python :
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
Déterminer si des points sont alignés.
Deuxième technique :
On détermine l’équation réduite de la droite (AB).on vérifie que les coordonnées du point C vérifie l’équation de(AB).
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
Déterminer si des points sont alignés.
Troisième technique :
On calcule les longueurs AB, AC et BC.Si AB = BC + AB ou BC = AB + BC ou AC = AB + BC, alorsles points A, B, et C sont alignés sinon ils ne sont pas alignés.
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
Déterminer si des points sont alignés.
Sans boucle ni récursion est-ce vraiment un algorithme ?
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
Dans "statistique probabilité" (1)
D’après les élèves "Miramas est un trou".Est-ce que cette affirmation est vraie ?Comment produire une réponse objectivée ?
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
Dans "statistique probabilité" (1)
On récupère l’ensemble des populations des villes françaises dansun tableur.La fonction NB.SI permet de compter par exemple le nombre decommunes qui ont une population supérieure à Miramas.
NB.SI(plage,critère) détermine le nombre de cellules non videsrépondant à un critère à l’intérieur d’une plage.
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
Dans "statistique probabilité" (2)
Certaines calculatrices n’utilisent pas les mêmes définitions quecelles des programmes pour par exemple la médiane. On peutdécider de reprogrammer des fonctionnalités.
1 Ranger la série dans l’ordre croissant2 Déterminer N la taille de la série3 Si N = 2n alors ... sinon ...
Bien sûr ce n’est pas un algorithme transposable directement enprogrammation. Il faudrait maintenant voir comment ranger dansl’ordre croissant la série. Il nous faut fabriquer un algorithme de tri.
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
Dans "statistique probabilité" (3)
Tirages sans remise.Deux algorithmes possibles :
On tire le premier dans la liste des valeurs possibles ;on tire le second dans la même liste ;si le tirage est le même que le premier tirage, on retourne àl’étape précédente, sinon on continue ;on effectue le troisième tirage ;...
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
Dans "statistique probabilité" (3)
Deuxième algorithme possible :
On tire le premier dans la liste des valeurs possibles ;on enlève de la liste le tirage déjà effectué ;on tire le second dans cette nouvelle liste ;on enlève de la liste ce second tirage ;on effectue le troisième tirage ;...
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
Dans "statistique probabilité" (4)
Combien de fois faut-il lancer un dé cubique pour obtenir un 6 ?
1 À l’aide de la calculatrice, on réalise quelques simulations del’expérience. On note à chaque fois le nombre de lancersnécessaires.
2 On écrit un algorithme qui affiche à la sortie le nombre delancers nécessaires à l’obtention du premier 6. On programmecet algorithme. on le fait tourner et on observe le nombre delancers nécessaire pour différentes simulations.
3 On modifie l’algorithme précédent afin de réaliser non plus une,mais plusieurs expériences. On fait calculer le nombre moyen delancers pour atteindre le premier 6 ?
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
Dans le domaine "fonctions" (1)
Une introduction possible à la dichotomie : un jeu2 personnes : 1 joueur et 1 maître du jeu.Le maître du jeu affiche deux nombres entiers a et b et choisit unnombre entier N secret entre a et b.Le joueur doit essayer de deviner le nombre secret en se conformantaux règles suivantes :
Le joueur propose un nombre.Le maître du jeu compare la proposition au nombre secret etrépond "Gagné", "Plus" ou "Moins".Le joueur, s’il n’a pas encore gagné, propose un autre nombre etce jusqu’à ce qu’il gagne.
L’objectif est de trouver une stratégie plus efficace pour amenerrapidement à la victoire.
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
Dans le domaine "fonctions" (2)
Une situation concrète :
pour fabriquer une boite on utilise une feuille de carton de 50 cm sur30 cm. On enlève quatre carrés isométriques dans chaque angle dela feuille. On relève ensuite les bords de façon à obtenir une boitesans couvercle.
On note x la longueur, en cm, des côtés des carrés que l’on enlèvedans chaque angle.
En utilisant une calculatrice graphique, déterminer une valeurapprochée de x , à 10−2 près, pour laquelle le volume V de la boiteest maximal.
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
Dans le domaine "fonctions" (2)
Le volume de la boite peut s’exprimer en fonction de x par :
V (x) = (50− 2x)(30− 2x)× x
Pour obtenir une valeur approchée, on choisit une première fenêtreassez large pour avoir une vue globale de la courbe, puis parcadrages successifs, on va déterminer un encadrement d’amplitude10−3.
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
Une premiere fenêtre
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
Une deuxième fenêtre
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
Quel est l’algorithme sous-jacent au tracé d’unecourbe ?
Une autre situation :
Les différents tracés présentés ci-après, ont été obtenus à partird’une même fonction élémentaire et pour des fenêtres relativementproches les unes des autres...
C’est l’occasion de s’interroger sur l’algorithme éxécuté par lacalculatrice pour afficher une courbe à l’écran.
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
Un premier tracé...
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
Un autre...
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
Un troisième... plus piquant !
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
Un quatrième assez esthétique
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
La fonction...
f (x) = sin(50πx)
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
... et un dernier tracé presque rassurant...
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
La période de ta fonction est de 0.04, et l’écran d’une TI 83 comporte94 pixels de large. Donc, si on choisit comme fenêtre xmin = 0 etxmax = 0.04× 94 = 3.76, chaque pixel représente (environ ?) unepériode. Donc lorsque la machine essaye de tracer la fonction, achaque fois qu’elle avance d’un pixel, elle tombe sur la même valeur,d’où la droite horizontale...
Pour les autres, il doit falloir faire un peu de congruence pourexpliquer les décalages !
La dernière fenêtre est intéressante car on obtient une bellesinusoïde, ce qui, si l’on n’y prend garde, est trompeur : en effet, en0, sin(50 ∗ pi ∗ x) vaut 0, ce qui est loin d’être le cas sur le tracé fournipar la calculatrice.
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
Lire, écrire, simulerun algorithme
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
Comment écrire et présenter un algorithme ?
Un langage et une notation pour l’écriture des algorithmes sontprésentés dans la brochure Algorithmes et logique de l’IREMd’Aix-Marseille (qui peut être téléchargée sur le site de l’IREM).
Cette brochure aborde aussi la notion de preuve d’un algorithme(finitude et efficience de l’algorithme).
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
Un exemple célèbre : l’algorithme d’Euclide
Cet algorithme prend deux entiers naturels a et b en entrée etretourne leur pgcd.
x ← ay ← btant que y 6= 0 faire
r ← x mod yx ← yy ← r
résultat x
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
Un exemple de simulation "à la main"
x ← ay ← btant que y 6= 0 faire
r ← x mod yx ← yy ← r
résultat x
a=168 ; b=180
x y r168 180
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
Un exemple de simulation "à la main"
x ← ay ← btant que y 6= 0 faire
r ← x mod yx ← yy ← r
résultat x
a=168 ; b=180
x y r168 180180 168 168
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
Un exemple de simulation "à la main"
x ← ay ← btant que y 6= 0 faire
r ← x mod yx ← yy ← r
résultat x
a=168 ; b=180
x y r168 180180 168 168168 12 12
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
Un exemple de simulation "à la main"
x ← ay ← btant que y 6= 0 faire
r ← x mod yx ← yy ← r
résultat x
a=168 ; b=180
x y r168 180180 168 168168 12 1212 0 0
Résultat : 12
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
Comment évaluer le travailet la progression des
élèves ?
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
L’écrit ?
L’évaluation écrite en temps limité est assez inadaptée pour apprécierles compétences que les élèves développent dans cette partie del’enseignement. Elle peine à rendre compte des initiatives prises. Laquestion de la présence ou de l’interdiction d’outil pendant cet écritconduit à des postures difficilement tenables pour l’institution :interdire toute calculatrice dans une épreuve appelée à tester del’algorithmique paraît choquant, gérer la diversité des fonctionnalitésoffertes est un vrai casse-tête qui finit par poser des problèmesd’équité.
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
Ce qui s’est fait... et peut se faire
l’expérience de l’épreuve pratique en série S : évaluation ensituationl’épreuve de spécialité au baccalauréat de la série L : évaluationécrite en temps limité (simulation d’un algorithme, identificationdu résultat fourni par un algorithme)la réalisation d’un projet et son aboutissement, l’efficience del’algorithme construit sont des formes d’auto-évaluation...
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
Introduction Nouveauté ? La pensée algorithmique Mise en œuvre Lire, simuler, écrire Evaluation
Stéphane Clément Lycée Jean Cocteau -
L’enseignement de l’algorithmique
