TPs d’algorithmique sur les fonctions avec CaRMetal

jeudi 2 décembre 2010
par  Alain BUSSER

Les boucles sont indigestes pour les élèves lorsqu’on y utilise l’indice. Sinon, grâce aux nombres pseudo-aléatoires, on peut faire des choses intéressantes sans que les élèves aient à savoir comment on fait pour répéter l’action n fois, mais juste combien de fois on répète l’action.

Premier TP : Représentation graphique

Pour représenter graphiquement une fonction, on l’approxime en général par un polygone ayant un grand nombre de points et dont les côtés sont donc petits et nombreux. Ce qu’il est impossible de faire sans une boucle parcourant les abscisses successives des points de la courbe.

Ceci dit, si on renonce à joindre les points, tout en les maintenant nombreux, on a un nuage de points qui évoque assez bien la représentation de la fonction.

L’idée vient, une fois de plus, du livre de Guillaume Connan.

Ceci dit, lorsqu’on dessine un nuage de points, l’algorithmique n’est plus nécessaire, on peut aussi dessiner un seul point, activer sa trace, puis utiliser le Monkey...

Le sujet du TP est téléchargeable ici, d’un clic droit :

PDF - 179 ko
représentation graphique
Sujet du TP au format pdf

En Seconde, même en début d’année, ce TP est une réussite, si on tient compte de l’enthousiasme des élèves (« c’est génial, cet algorithme ! »). Par contre il a été impossible de l’évaluer, les questions notées de la deuxième page ayant été presque complètement ratées.

Certains élèves, victimes de leur zèle, ont constaté qu’en lâchant le Monkey au bout d’un temps trop long, celui-ci reste actif, ce qui a au moins l’avantage de déclencher l’hilarité...

La question II/2 a été très difficile aux yeux des élèves, ce qui en Seconde, est nouveau : Pour la plupart des élèves, les techniques algébriques de résolution d’inéquations sont inédites ou mal conceptualisées.

La question III a toujours été mal faite, les élèves ayant trouvé l’algorithme si « génial » qu’ils ont cru le voir partout (y compris sur un tableur, où pourtant on n’utilise pas de nombres aléatoires). Avec 2000 points, l’algorithme donne ceci :

alors qu’avec 101 points (pas de 0,1) l’approximation polygonale donne ceci :

Par contre, la représentation par points aléatoires est utilisée pour les surfaces implicites par le logiciel 3D-XplorMath

Deuxième TP : Recherche d’extrema

La méthode du thermomètre a déjà été utilisée pour optimiser une fonction de deux variables. Elle peut aussi servir à chercher le maximum d’une fonction non monotone sur un intervalle. Là encore, le point est déplacé aléatoirement pour éviter de provoquer des réflexions métaphysiques sur ce qui se passe dans la boucle. Et là encore, JavaScript n’est pas nécessaire et on peut là encore, utiliser le Monkey.

Voici le sujet :

PDF - 128.7 ko
optimisation : sujet du TP
sujet du TP sur l’optimisation en pdf

Il est intéressant de voir comment des élèves pour qui la notion de boucle est encore en cours d’acquisition, se trompent lorsqu’ils essayent de taper au clavier au lieu de cliquer sur une boucle toute faite comme CaRMetal le permet. L’erreur la plus répandue est celle consistant à écrire

for(i=0; i=200; i+=1)

On sent là un besoin de décrire la boucle comme un intervalle (de i=0 jusqu’à i=200) et non comme JavaScript le fait, par une initialisation suivie d’un test pour rester dans la boucle (on reste dans la boucle tant que i reste inférieur ou égal à 200). Dans cette optique, il est intéressant de voir l’historique du logiciel Xcas, dont le langage de programmation ressemble à JavaScript, mais auquel il y a quelque temps, a été ajouté une version française « pour i de 0 jusque 200 faire ».

De façon générale, la première cause de blocage reste la lecture trop superficielle du sujet. Ainsi beaucoup d’élèves ne regardent même pas les deux premières lignes, et le texte

le point M ailleurs que sur les axes et la courbe

a souvent été compris comme son contraire

le point M sur les axes ou la courbe

Ce qui éclaire sur certaines difficultés rencontrées en probabilités...


Seuls deux élèves ont fini le TP avant la fin de l’heure, et encore ils n’ont pas fait le II/3. Le TP est donc trop long, et il eût peut-être été mieux de ne pas faire le I qui a été long. Cependant, la réponse obtenue au I/8 est plus précise que celle du II, ce que certains élèves ont d’ailleurs remarqué spontanément.

Pour aller plus loin, (pour les élèves qui iraient vraiment plus vite que les autres), on peut penser à faire chercher les valeurs exactes des extrema et leurs antécédents, en demandant de calculer une valeur approchée de \frac{5\sqrt{3}}{3}, puis la valeur exacte et la valeur approchée de l’image de ce nombre.

Nombres triangulaires

Pour calculer les nombres triangulaires (sujet à la mode) par une boucle, il est visiblement souhaitable d’utiliser le mode pas-à-pas, pour que les élèves aient le temps de voir ce qui se passe, à leur rythme. Comme CaRMetal n’a pas de mode pas-à-pas, et bien qu’on puisse simuler celui-ci, le premier TP sur les boucles a été fait sous Open Office Calc, ce tableur étant doté du langage JavaScript via l’interpréteur rhino, le même que CaRMetal.

La syntaxe des boucles en JavaScript semble complexe, mais elle est très conforme au vocabulaire de la Terminale L : Une phase d’initialisation, typiquement i=0, puis une condition, non de sortie, mais pour rester dans la boucle, et enfin le corps de la boucle, où l’indice i est incrémenté.

Voici le sujet d’un TP sur les nombres triangulaires en mode pas-à-pas :

PDF - 199.6 ko
boucle en mode pas-à-pas

Additionner une colonne de nombres avec un tableur n’est visiblement pas une compétence largement acquise à l’entrée en Seconde (le bouton \Sigma n’est pas connu des élèves), ni bien entendu le « dollar ». Les élèves semblent par contre autant à l’aise avec le tableur de GeoGebra qu’avec celui d’Open Office.


Somme toute (c’est le cas de le dire !), la question la plus intéressante de ce TP a été la question non notée.

Tableur : Un seul élève a vu que la colonne contenant les doubles des nombres triangulaires était formée par des produits de valeurs de l’indice.

Pour entrer les nombres triangulaires dans la colonne B du tableur, les élèves, qui ignorent totalement le symbole « dollar » et son utilisation, ont entré les nombres à la main (recopiés de la feuille de TP). Pourtant l’algorithme suggérait d’entrer la formule

=B1+A2

dans la cellule B2, et de copier cette formule vers le bas. Il semble que l’usage du tableur en collège ne va pas jusqu’à là...

GeoGebra

Les élèves ont découvert, émerveillés, que GeoGebra a aussi un tableur, mais là aussi, ils ont entré les nombres à la main. L’étape suivante a été de sélectionner les colonnes A et B du tableur, puis choisir (après clic droit) de « créer un nuage de points ». Puis après un zoom pour voir tous ces points, la seule instruction qui leur a été donnée a été « c’est une régression qu’il faut faire ; cherchez parmi les outils de régression de GeoGebra ». Cette instruction a suffi à guider les élèves vers la régression polynomiale, spontanément ! Voici la version avec curseur (objet que les élèves ne connaissent pas) :

Désolé, l'activité GeoGebra ne peut pas démarrer. Assurez-vous que Java 1.4.2 (ou version supérieure) est installée et activeée sur votre navigateur (Cliquez ici pour installer Java maintenant !)
Créé avec GeoGebra

En manipulant le curseur, on trouve pour quelles valeurs du degré la courbe passe par les points ; les élèves ont changé le degré par essais et ont trouvé la formule.

Xcas

Certains élèves avaient Xcas sur leur ordinateur, d’autres pas. Ceux-là sont allés sur Xcas en ligne et y ont tapé l’instruction. Aucun n’a pensé à factoriser l’expression affichée...


La dernière question tombe un peu comme un cheveu sur la soupe : Son but est de montrer que pour additionner les entiers consécutifs, il y a un autre algorithme que celui avec la boucle ci-dessus. Par exemple, il semble a priori plus facile de calculer \frac{10 \times 11}{2} que de calculer 1+2+3+4+5+6+7+8+9+10.

Un problème se pose : Les élèves doivent pour comparer les deux algorithmes, admettre que ces deux nombres sont égaux pour toute valeur de n, la démonstration par récurrence n’étant pas franchement au programme de Seconde ! Il reste l’explication offerte par le fameux dessin du rectangle coupé en deux :

Désolé, l'activité GeoGebra ne peut pas démarrer. Assurez-vous que Java 1.4.2 (ou version supérieure) est installée et activeée sur votre navigateur (Cliquez ici pour installer Java maintenant !)
Créé avec GeoGebra

En attendant, les élèves ont eu à faire confiance à Xcas, ce qui évidemment ne leur a posé aucun problème.

Fonctions affines

Pour voir s’il est plus rapide de calculer la somme terme à terme ou d’effectuer le produit de n par n+1 et diviser par 2, on a besoin d’outils permettant de mesurer le temps.

Version CaRMetal

Mais tout d’abord, on va remplacer le 10 du TP précédent par un n ce qui va permettre de faire varier n par la suite :

Pour mesurer le temps mis à exécuter un CaRScript, on peut créer une variable début de type Date juste avant le script, et une autre variable de type Date juste après ; ainsi la différence entre les deux mesure la durée de l’exécution du script, en millisecondes :

Le problème est que la durée pour additionner 10 nombres est

  • trop petite pour être affichée avec précision (inférieure à une milliseconde) ;
  • trop fluctuante (le processeur est aussi occupé à d’autres tâches).

Une solution est de faire le tout 100 fois et de diviser la durée totale par 100 à la fin. Ainsi, on calcule une durée moyenne qui fluctue moins :

Enfin, on transforme cette mesure du temps mis à faire 10 additions, en une suite de mesures pour différentes valeurs de n, en remplaçant var n=10 par une boucle sur n (de 1 à 100) :

Bien entendu, tout a été fait pour que l’exécution de ce script soit un peu longue ! Et on remarque que les résultats, quoique globalement croissants, sont encore assez irréguliers. Avec 1000 répétitions au lieu de 100, le nuage de points représentant la suite de mesures ressemble à ceci :

De temps en temps, une tâche externe à CaRMetal ralentit le processeur et le point est anormalement élevé. Dans la plupart des cas, l’alignement est assez bon, ce qui amène à la conjecture suivante :

Le temps mis à additionner n nombres est fonction affine de n.

Pour comparaison, on peut représenter en rouge les temps de calcul des \frac{n(n+1)}{2} sur le même graphique :

Le temps mis à calculer les \frac{n(n+1)}{2} est globalement constant et toujours inférieur au temps mis à faire des additions : L’algorithme consistant à trouver d’abord une expression simplifiée pour 1+2+3+4+...+n puis à l’utiliser au lieu des additions, est donc plus rapide que l’algorithme consistant à effectuer des boucles : Une multiplication pour éviter des milliers d’additions !

Version Python

Comme Python possède un objet time possédant notamment une méthode clock(), on peut faire la même chose avec Python. Par exemple, si on crée un fichier nommé somme.py et qu’on y écrit ce script

import time
begin=time.clock()
for p in range(1000000):
        s=0
        for k in range(100):
                s+=k
end=time.clock()
print(end-begin)

en entrant python somme.py dans la console, on a au bout de moins d’une minute, un affichage comme 43.34 qui veut dire que les 99 additions ont été faites en 43,34 microsecondes. D’ailleurs la version compilée prend presque autant de temps.

On peut bien entendu aussi mettre ces mesures de temps dans une boucle (avec moins de répétitions tout de même) en construisant au fur et à mesure un tableau :

mais dans ce cas, pour représenter graphiquement le tableau, on a besoin d’un outil plus lourd comme TkInter, Gimp, OpenOffice.org Calc etc. Voici ce que donne la version Kig :

On constate que l’affichage des points consomme du temps de calcul (bien qu’il soit fait avant l’ouverture de Kig), puisque le temps des 99 additions est devenu supérieur à 140 microsecondes.

Version Xcas

Xcas permet de faire directement la mesure de temps grâce à l’outil time. Et pas besoin d’écrire un programme pour additionner les nombres entiers, puisque Xcas a une instruction sum. En combinant les deux, on a le temps mis par Xcas pour additionner 100 nombres, sous forme d’un intervalle :

On lit que pour additionner 100 nombres, Xcas met ... un certain temps, compris entre 65 microsecondes et 75 microsecondes, à comparer avec le temps mis par CaRMetal (environ 110 microsecondes d’après le graphique ci-dessus), et les 43 microsecondes de Python.

Comme Xcas ne calcule pas le temps moyen, on va chercher le temps minimal, qui est la première entrée du tableau ci-dessus, et qu’on obtient en donnant à l’indice de lecture dans le tableau, la valeur 0 :

Enfin, comme avec CaRMetal, on remplace 100 par n qui va varier de 1 à 100, et, en utilisant l’outil seq (comme sur les calculatrices et GeoGebra), on obtient la suite de temps de sommes de suites suivante :

Pour vérifier que le temps minimum est globalement croissant, on peut représenter le nuage de points, avec plotlist :

Et là encore, la fonction semble non seulement croissante, mais aussi affine.

Version Euler Math Toolbox

Avec Euler Math Toolbox, on peut travailler directement dans une liste, comme avec Xcas :

temps=zeros(1,100);

crée la liste, puis on écrit la fonction somme :

function somme(n)
$s=0;
$for i=1 to n;
$s=s+i;
$end;
$return s;
$endfunction

La boucle peut être faite en une seule ligne :

for n=1 to 100; start=time; loop 1 to 1000; somme(n); end; temps[n]=time-start; end;

Après, un simple

plot2d(temps);

donne l’affichage suivant :

Version SciLab

Comme pour Euler Math Toolbox, on commence par créer un tableau vide :

t=zeros(1,100);

La boucle tient en une ligne (avec une boucle sur 1000 valeurs pour ralentir un peu l’algorithme) :

for n=1:100, timer(); for p=1:1000, s=0; for i=1:n, s=s+i; end; end; t(n)=timer(); end

On obtient le graphique suivant :

Ainsi, à partir de mesures de temps d’exécution de programmes, on peut aborder par une problématique (estimer le temps de calcul de nombres triangulaires) les fonctions affines. Pour ne pas multiplier à l’excès les TP d’algorithmique, un devoir maison a été donné aux élèves, dont voici l’énoncé :

PDF - 121.8 ko
sujet du DM sur les fonctions affines

Avec une moyenne de 13,86, ce devoir est plutôt réussi. Le fait de travailler sur des fonctions affines « issues du monde réel » a plutôt motivé les élèves, qui voient apparemment mieux ce qui se passe parce que les fonctions affines sont moins abstraites que celles du cours. On peut donc parler d’enseignement basé sur une problématique dans ce cas. Par contre, il s’agit bel et bien d’une régression linéaire et non d’une vraie fonction affine, ce qui rend l’exercice un peu prématuré en Seconde.


Cette activité est intéressante en Seconde parce que

  1. Elle est expérimentale ; qu’on aime ou qu’on n’aime pas, l’expérimentation est au programme de Seconde ;
  2. Elle utilise des boucles imbriquées ;
  3. Elle utilise de la statistique (lissage par moyenne mobile, recherche de minimum, calcul de moyenne) ;
  4. Elle utilise l’algorithmique comme objet d’étude pour un problème de maths (d’habitude, c’est plutôt le contraire) ;
  5. Elle introduit les fonctions affines dans un enseignement basé sur la problématique, comme le demande le programme de Seconde ;
  6. Elle permet même, avec les unités en jeu, de faire un peu de révision sur les écritures scientifiques...

Pour voir d’autres exemples de mesure de temps de calcul, on peut essayer avec l’algorithme d’Euclide ou le calcul de nombres de Fibonacci.


Documents joints

GeoGebra - 4.3 ko
GeoGebra - 4.3 ko
GeoGebra - 3.5 ko
GeoGebra - 3.5 ko

Commentaires

Annonces

Prochains rendez-vous de l’IREM

Séminaire EDIM-IREM

- Mercredi 22 novembre 2017, 14h-18h, campus du Tampon, amphi 120 D
- Mercredi 7 février 2018, PTU, Saint-Denis, salle S23.6
- Mercredi 7 mars 2018, 14h-18h, campus du Tampon
- Mercredi 4 avril 2018, PTU, Saint-Denis, salle S23.6
- Mercredi 2 mai, 14h-18h, campus du Tampon
- Mardi 5 juin 2018, PTU, Saint-Denis, salle S23.6
- Mercredi 6 juin, 14h-18h, campus du Tampon

Fête de la science

Campus du Moufia, 16 et 17 novembre 2017.
Thème : « La recherche à l’heure du numérique »

Semaine des mathématiques

Du 26 au 31 mars 2018.
Thème : « Mathématiques et mouvement »


Brèves

Décès de Roger Mohr

mardi 27 juin

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

À travers les labyrinthes : algorithmes et fourmis

dimanche 1er septembre 2013

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

Rencontres Mondiales du Logiciel Libre à St-Joseph

mardi 20 août 2013

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

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

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

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

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

dimanche 19 août 2012

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

Ouverture du SILO

mardi 1er novembre 2011

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

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

Sur le Web : Site du SILO

Introduction à la science informatique

lundi 12 septembre 2011

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

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

Sur le Web : CRDP de Paris

Deux publications sur l’algorithmique

samedi 17 octobre 2009

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

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

Une carte mentale pour l’algorithmique

jeudi 10 septembre 2009

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

Un catalogue libre d’algorithmes pour le lycée

dimanche 30 août 2009

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

L’algorithmique à l’IREM de Lille

vendredi 26 juin 2009

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

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

Statistiques

Dernière mise à jour

dimanche 12 novembre 2017

Publication

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

Visites

44 aujourd'hui
911 hier
2164279 depuis le début
5 visiteurs actuellement connectés