Map/Keep/Combine en langage Snap!, Map/Filter/Reduce en Python, Javascript, C++, Java, et autres langages, j’opterais pour Appliquer/Extraire/Combiner pour nos élèves français.
Ce trio Appliquer/Extraire/Combiner est un outil puissant pour enseigner les Mathématiques.
Des scripts Snap! et Python sont donnés pour illustrer le concept.
Appliquer/Extraire/Combiner, c’est Map/Filter/Reduce en langage Python, Map/Keep/Combine en langage Snap!.
Ce trio permet de coder les algorithmes au coeur même de la notion de fonction.
- Premier tour d’horizon avec Map/Keep/Combine ou (...)
- Pourquoi Snap ! pour coder les Mathématiques ? : Le ` no (...)
- La notion de Fonction au centre de l’apprentissage des (...)
- Exemples progressifs niveau lycée
- Un peu d’arithmétique
- Calculs sur les suites
- Et en géométrie ?
- De l’intérêt du Map/Keep/Combine
- Comment le présenter aux élèves en cours de mathématiques (...)
- Map/Keep/Combine expliqué aux élèves de NSI
- Conclusion
- Annexe
- Table des matières
Le trio Map/Filter/Reduce se nomme en langage Snap! Map/Keep/Combine.
Pour nos élèves français, j’opterai pour Appliquer/Extraire/Combiner. Ce trio permet de manipuler des fonctions et les appliquer à une liste de données.
Le trio Map/Filter/Reduce existe dans les langages Python, Javascript, Java, et de nombreux autres langages.
Nous illustrerons dans cet exposé les exemples principalement en langage Snap!. Mais aussi en Python, langage d’excellence adopté officiellement pour coder au lycée [1].
J’attire votre attention sur le fait que les algorithmes de cet article sont évidemment perfectibles. Mon but ici n’est pas de les optimiser mais de montrer l’intérêt de Map/Filter/Reduce (ou Map/Keep/Combine) pour les coder avec les élèves.
En première lecture, je vous propose de survoler l’article du regard et d’attacher de l’importance aux images des scripts Snap! car vous risquez d’être très surpris, surtout si vous ne connaissez pas ce langage de programmation visuelle.
Vous pouvez aussi lire la table des matières détaillée avant de commencer. Vous aurez un aperçu plus complet des thèmes et exemples abordés dans cet article.
Premier tour d’horizon avec Map/Keep/Combine ou Map/Filter/Reduce
Avant d’entrer dans des détails plus techniques, je vous propose de vous laisser porter par les images des scripts fournis pour Map, Combine et Keep ci-dessous (Map/Reduce/Filter). Vous allez ainsi découvrir par vous-même à quoi servent ces trois fonctions.
Si un onglet vous paraît trop obscur au premier abord, je vous suggère de changer d’onglet, vous y reviendrez par la suite. En effet, le concept étant peut-être totalement nouveau pour vous, vous devez vous en imprégner petit à petit (à la Réunion, nous disons Ti lamp, ti lamp...).
Premiers exemples d’application de fonctions à une liste d’objets avec Map
Vous trouverez dans cette section :
- des exemples de Map pour obtenir divers tableaux de valeurs de fonctions vues au lycée,
- comment générer des listes de booléens aléatoires simplement avec Map, avec application aux tirages de cartes et aux jets de dés,
- comment calculer la puissance n-ième d’une matrice sans récursivité,
- de très belles images d’un léopard pour lesquelles, grâce à Map, des modifications des codes RGB des pixels de ces images en ont délicatement changé les couleurs.
Tableau de valeurs d’une fonction
– Carrés des 7 premiers entiers
– Cubes des 7 premiers entiers
– Puissances de 10 des 7 premiers entiers
– Puissances de 2 des 7 premiers entiers
– Racine carré des 1000 premiers entiers
Le résultat obtenu donne immédiatement envie d’en extraire les nombres dont la racine est entière...
Lutin Tableaux_0 du projet Snap! lié à cet article.
— Scripts Python. [2]
- def entiers_1_a_n(n): return list(range(1,n+1))
- entiers_1_a_n(10)
- # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
- def carre(x): return x**2
- def carres_des_nombres(x_list):
- return map(carre, x_list)
- carres_des_nombres(entiers_1_a_n(10))
- # renvoie [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
- def cube(x): return x**3
- def cubes_des_nombres(x_list):
- return map(cube, x_list)
- cubes_des_nombres(entiers_1_a_n(10))
- # renvoie [1, 8, 27, 64, 125, 216, 343, 512, 729, 1000]
- def puissance_de_10(x): return 10**x
- def puissances_de_10_des_nombres(x_list):
- return map(puissance_de_10, x_list)
- puissances_de_10_des_nombres(entiers_1_a_n(9))
- # renvoie [10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000]
- def puissance_de_2(x): return 2**x
- def puissances_de_2_des_nombres(x_list):
- return map(puissance_de_2, x_list)
- puissances_de_2_des_nombres(entiers_1_a_n(10))
- # renvoie [2, 4, 8, 16, 32, 64, 128, 256, 512, 1024]
Dans tous les scripts précédents, on aurait pu définir la fonction à mapper avec le mot-clé lambda comme dans le script suivant qui calcule les racines carrés des entiers de 1 à 1000.
- map(lambda a:a**(1/2), entiers_1_a_n(1000))
Retour aux onglets Premiers exemples d’application de fonctions à une liste d’objets avec Map
Obtenir une liste aléatoire de booléens
[3]
– Comment tirer au hasard un booléen Vrai ou Faux ?
– Comment créer une liste aléatoire de booléens ?
Il suffit d’appliquer le prédicat précédent à la liste des entiers de 1 à n si n est le nombre de booléens que nous souhaitons.
On pourra bien sûr en faire un bloc qui renvoie le nombre voulu de booléens :
Applications
Cela sera très utile dans
- tous les problèmes de simulations en général,
- Promenades aléatoires
- Jeu de Pile ou Face
- Tirages de cartes
- Jets de dés
- simulations en probabilité
- simulation d’une loi binomiale
- en théorie des graphes
- génération de matrices d’adjacence de graphes aléatoires
- en simulations numériques
- génération d’octets aléatoires
- génération de nombres binaires
On pourra faire découvrir aux élèves les tables de vérité en leur demandant d’appliquer les différents prédicats de l’algèbre de Boole à des booléens aléatoires.
On trouvera quelques exemples (tirages de cartes, jets de dés, matrice d’adjacence) dans la partie Exemples progressifs niveau lycée de cet article.
Retour aux onglets Premiers exemples d’application de fonctions à une liste d’objets avec Map
Calcul de la puissance n-ième d’une matrice (sans récursivité)
Je suis partie de l’idée suivante.
Pour calculer $2^n$ sans utiliser d’algorithme récursif, on utilise la définition de l’élévation d’un nombre à une puissance.
J’effectue donc le produit de 2 par 2 n fois.
On va donc appliquer la fonction constante x ↦ 2 aux n premiers entiers naturels (par exemple).
Ensuite, on combine ces valeurs avec l’opérateur × .
Il en est de même pour les matrices, à condition d’utiliser pour le Combine la multiplication dans l’espace des matrices.
On se réfèrera au projet :
https://snap.berkeley.edu/snap/snap.html#present:Username=nathalierun&ProjectName=Matrix_project_all_categories_IREM
Voir le lutin appelé A**n .
En seconde lecture, on pourra lire pour plus de détails l’article Calcul matriciel avec Snap ! et sa librairie APL.
— Scripts Python.
- map(lambda a:2, entiers_1_a_n(10))
- # renvoie la liste constante [2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
- # on peut aussi définir fonction_constante
- def fonction_constante(a_list): return map(lambda a:2, entiers_1_a_n(10))
- fonction_constante(entiers_1_a_n(10))
- # renvoie bien [2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
L’utilisation Reduce en Python nécessite d’importer la fonction reduce du module functools. [4]
- from functools import reduce
- reduce(lambda x,y: x * y, fonction_constante(entiers_1_a_n(10)))
- # renvoie 1024
Retour aux onglets Premiers exemples d’application de fonctions à une liste d’objets avec Map
Appliquer le négatif à un rectangle de pixels colorés
Qu’est-ce qu’une image affichée sur un écran ? C’est simplement un rectangle de pixels colorés. Une image de résolution 480×360 est donc constituée de 172800 pixels, chacun ayant des attributs RGBA (Red, Green, Blue, Alpha). Si les pixels de cette image sont dans un tableau appelé screen, on peut voir les composantes des pixels choisis au hasard :
(pixel beige) | (pixel marron clair) |
(pixel marron clair orangé) |
Ce léopard est une image de taille 480×258.
screen est donc un tableau de 123840 pixels.
Ici, on a décidé de mettre toutes les composantes rouges de chaque pixel du léopard à 150.
On réalise cette magie à l’aide de cette fonction récursive :
Si l’on décide de passer cette image en négatif, cela nous donne un très joli effet sur le léopard (ici, il y a une erreur, c’est donc un faux négatif...).
Et voici le script pour réaliser ce faux négatif :
Et voici notre léopard en négatif.
Et voici le script pour réaliser ce négatif :
Retour aux onglets Premiers exemples d’application de fonctions à une liste d’objets avec Map
Exemples de réduction avec Combine
Pour un ensemble fini de réels, on peut lui associer son plus grand élément, sa somme, son produit, sa moyenne arithmétique, sa médiane, son nombre d’éléments… autant de fonctions qui à un ensemble de réels associent un réel unique.
Si on considère un vecteur comme un n-uplet de réels, on peut lui associer sa longueur, son produit scalaire avec un vecteur fixe, sa première coordonnée, sa norme pour une norme quelconque, l’angle qu’il fait avec un vecteur donné… [5]
Somme
– Somme des 10 premiers entiers naturels.
- reduce(lambda x,y: x + y, entiers_1_a_n(10))
- # renvoie la somme des 10 premiers entiers naturels, soit 55.
Produit
– Produit des 10 premiers entiers naturels. [6]
- reduce(lambda x,y: x * y, entiers_1_a_n(10))
- # renvoie le produit des 10 premiers entiers naturels, soit 3628800.
- # remarque...
- from math import factorial
- factorial(10) # renvoie 3628800
Moyenne arithmétique
La moyenne arithmétique de n nombres est la somme de ces nombres divisés par le nombre de nombres en jeu. |
La moyenne arithmétique des 10 premiers entiers naturels est 5,5.
– Script Moyenne arithmétique.
- def moyenne_arithmetique(x_):
- return reduce(lambda x,y: x + y, x_) / len(x_)
- moyenne_arithmetique(entiers_1_a_n(10)) # renvoie 5.5
Moyenne géométrique
La moyenne géométrique de n nombres positifs est la racine n-ième du produit de ces nombres. |
La moyenne géométrique des 10 premiers entiers naturels non nuls est 4,5287 à 0,0001 près.
– Script Moyenne géométrique de nombres positifs.
- def moyenne_geometrique(x_):
- return reduce(lambda x,y: x * y, x_) ** (1/len(x_))
- moyenne_geometrique(entiers_1_a_n(10)) # renvoie 4.528728688116765
Moyenne harmonique
La moyenne harmonique de n nombres est l’inverse de la moyenne arithmétique des inverses de ces n nombres. |
Moyenne harmonique des 10 premiers entiers naturels :
– Script Moyenne harmonique.
– On remarquera que la division dans Snap! peut être effectuée avec un opérateur d’ordre supérieur.
– Ce qui permet de coder encore pus simplement le script Moyenne harmonique.
- def moyenne_harmonique(x_):
- return len(x_) / reduce(lambda x, y: x + y, map(lambda x: 1/x, x_))
- moyenne_harmonique(entiers_1_a_n(10)) # renvoie 3.414171521474055
Exercice : coder la moyenne quadratique.
La moyenne quadratique de n nombres est la racine carrée de la moyenne arithmétique des carrés de ces nombres. |
Cette moyenne est très utile en statistiques (calcul de l’écart-type) et en Théorie de la mesure.
En effet,
L’écart type dans une population est la moyenne quadratique des distances à la moyenne. |
Produit scalaire
– Script Vecteur produit des coordonnées.
– Vecteur produit des coordonnées de 2 vecteurs de l’espace [-1, 2, 1] et [1, -2, 3].
– Script produit scalaire sans opérateur d’ordre supérieur. [7]
– Produit Scalaire de 2 vecteurs de l’espace.
– Le Combine du produit scalaire utilisant la multiplication comme opérateur d’ordre supérieur.
– Script produit scalaire avec opérateur d’ordre supérieur.
Voir le lutin Produit scalaire du projet Snap! lié à cet article.
Le script Python peut être le suivant, en utilisant la multiplication définie comme opérateur d’ordre supérieur. [8]
- def produit_scalaire(x_, y_):
- return reduce(lambda x,y: x + y, multiplier(x_, y_))
- produit_scalaire([-1, 2, 1], [1, -2, 3]) # renvoie -2
- produit_scalaire(entiers_1_a_n(10), entiers_1_a_n(10)) # renvoie 385
Exemples d’extractions avec Keep
– Qu’est-ce qu’un prédicat ?
La fonction P : X ↦ {True, False}
est appelée prédicat sur X. Lorsque P est un prédicat sur X, on dit parfois que P est une propriété de X.
Utiliser Keep (ou Filter) revient à appliquer un prédicat P à une liste de données. Ce qui permet d’obtenir une sous-liste en compréhension de la liste de données initiale. [9]
On appelle booléen l’un des éléments de l’ensemble True, False.
Voici quelques exemples de prédicats :
Ce nombre est-il positif ?
– -1 n’est évidemment pas un nombre positif...
- def est_positif(x): return x >= 0
Ce nombre est-il pair ?
- def est_pair(a): return a % 2 == 0
Ce nombre est-il premier ?
- 1997 est-il premier ?
- Prédicat est-ce un nombre premier :
Comme nous avons en Python avec Filter : [10]
- filter(lambda x: 197 % x == 0, entiers_1_a_n(197)) # renvoie [1, 197]
nous pouvons coder ainsi un prédicat nombre_premier en Python :
- def nombre_premier(n):
- return len(filter(lambda x: n % x == 0, entiers_1_a_n(n))) == 2
[11]
- nombre_premier(97) # renvoie True
- filter(lambda x: 197 % x == 0, entiers_1_a_n(197)) # renvoie [1, 197]
Ce nombre est-il un carré ?
- 122 * 122 est un carré alors que 122 * 123 ne l’est pas :
- Prédicat est-ce un carré ?
- Voici comment obtenir la liste des carrés inférieurs à 100.
Ce code Python
- 49 in map(lambda x: x * x, entiers_1_a_n(round(100 ** (1/2)))) # renvoie True
permet d’écrire le script suivant :
- def est_un_carre(n): # script pour des entiers
- if n < 0: return False
- return n in map(lambda x: x * x, entiers_1_a_n(round(n ** (1/2))))
- est_un_carre(122 * 122) # renvoie True
- est_un_carre(122 * 123) # renvoie False
- est_un_carre(-49) # renvoie False
- filter(est_un_carre, entiers_1_a_n(100)). # renvoie [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
Ce nombre est-il un cube ?
- 456533 est-il un cube ?
- 122 * 122 * 122 est un carré alors que 122 * 122 * 123 ne l’est pas :
- Prédicat est-ce un cube ?
- Voici comment obtenir la liste des cubes inférieurs à 1000.
- def est_un_cube(n): # script pour des entiers
- return n in map(lambda x: x * x, entiers_1_a_n(round(n ** (1/3))))
- est_un_cube(122 * 122 * 122) # renvoie True
- est_un_cube(122 * 122 * 123) # renvoie False
- filter(est_un_cube, entiers_1_a_n(100)). # renvoie [1, 8, 27, 64]
– Ce nombre est-il la somme de 3 cubes ?
- 684 est-il la somme de 3 cubes ?
684 est bien la somme de 3 cubes :
- Prédicat somme de 3 cubes
- Somme de 3 cubes inférieurs à 100 :
– Exemples concrets d’extractions avec Keep :
Créons d’abord une liste de 10 nombres entiers aléatoires avec Map. On la nomme tyty.
Extraire les nombres positifs d’une liste de nombres
On peut extraire facilement avec Keep les items positifs de la liste tyty.
- tyty = [-23,10,52,73,57,56,16,22,47,-96]
- filter(est_positif, tyty) # renvoie [10, 52, 73, 57, 56, 16, 22, 47]
Extraire les nombres pairs d’une liste de nombres
On peut alors extraire les nombres pairs de la liste tyty ainsi :
- filter(est_pair, tyty) # renvoie [10, 52, 56, 16, 22, -96]
Extraire un ensemble de carrés
On peut extraire les carrés de la liste tyty ainsi :
- filter(est_un_carre, tyty). # renvoie [16]
Extraire les entiers d’un ensemble de nombres
Ce test permet de savoir si un nombre est un réel ou un entier.
– Les racines entières des 50 premiers entiers s’obtiennent donc avec ce Keep en ne gardant que les nombres qui - considérés comme des chaînes de caractères - ne contiennent pas le point.
– Mais cela n’est pas très intéressant.
[12]
Nous voulons aussi garder leur antécédent... [13]
La colonne 1 du résultat comprend les nombres inférieurs à 50 dont les racines sont entières.
Lutin Tableaux_0 du projet Snap! lié à cet article.
- str(5632.78)[1:3] == '.0' # renvoie False mais pour 1.0, 2.0, 3.0, etc... on obtiendrait True
- c_ = map(lambda x: x ** (1/2), entiers_1_a_n(50))
- filter(lambda x: len(str(x)) == 3 and str(x)[1:3] == '.0', c_)
Obtenir les classes d’équivalence modulo n
Voici une note historique donnée par Alain Busser lors d’un échange autour de son jeu Union-Find :
« L’idée de modéliser les classes d’équivalences comme images réciproques par une fonction (qui caractérise la classe d’équivalence) remonte au moins à Dedekind dans sa construction des nombres. Dans son livre il définit pour la première fois le »mapping« ou image d’un ensemble par une fonction. Et ceci, avant que Cantor publie sur les ensembles ! La classe d’équivalence ne s’obtient pas par un mapping mais par un filter. »
Toute application f : E → F induit sur E la relation d’équivalence avoir même image par f.
Prenons par exemple pour un entier non nul n l’application Rₙ, Reste modulo n : m → m % n , m appartenant à ℕ.
L’ensemble des nombres qui ont même image par Rₙ sont les entiers dont la division par n fournit le même reste.
Prenons par exemple la liste Y = [2,3,1,1,9,1,1,48] qui est la liste des restes modulo 49 des nombres de cette liste :
c = [492,346,344,50,156,246,1961,587].
Le Map de la fonction f : x → Reste modulo 49(x) à la liste c = [492,346,344,50,156,246,1961,587] fournit la liste Y. [14]
On a donc : f([492,346,344,50,156,246,1961,587]) = [2,3,1,1,9,1,1,48] c’est à dire f(c) = Y.
Nous allons maintenant extraire de la liste c les items dont le reste modulo 49 est 1 avec ce Keep : [15]
L’image réciproque de 1 par f dans la liste c est donc :
Nous pouvons aussi l’écrire ainsi : [16]
Où le script de f⁻¹(valeur) dans la liste a se code de la manière suivante :
Ainsi, (Reste modulo 49)⁻¹(1) = {344,50,246,1961}, ensemble qui représente une partie de la classe d’équivalence de 1 pour la relation d’équivalence induite par l’application R₄₉.
Nous pourrons appliquer ce script à d’autres relations d’équivalence pour déterminer des parties de classes d’équivalence.
Voir le lutin index_of_item du projet Snap! lié à cet article.
Pourquoi Snap! pour coder les Mathématiques ? : Le ` no code - no limit ` langage
La diversité des articles qui ont déjà été rédigés sur le site de l’IREM de la Réunion depuis 2016 autour du langage Snap! [17] [18] et des codes qu’ils contiennent vous permettront de percevoir - si vous ne le savez pas déjà - à quel point Snap! est un langage `no code - no limit `...
Imaginez Scratch auquel on ajoute la puissance du lambda-calcul (λ-calcul).
L’idée de base du lambda-calcul étant que tout est fonction, vous obtenez un langage de programmation visuel (VPL) [19] qui code du code. [20]
Dans Snap!, les données sont dites de première classe.
Une donnée de type première classe peut être :
– la valeur d’une variable
– un argument d’une fonction
– la valeur de retour d’une fonction
– un membre d’une liste
– anonyme
Dans Snap!, les fonctions sont de première classe car elles peuvent constituer les entrées de n’importe quel bloc.
Une fonction qui peut prendre des fonctions comme argument ou qui renvoie une fonction est dite fonction d’ordre supérieur. Ce n’est qu’un aspect du type première classe.
Les listes y sont de première classe bien sûr. Ainsi, elles peuvent être elles-même des listes de listes.
Ce qui donne une puissance sans limite de programmation au logiciel.
C’est pour cela que Jens Mönig, principal développeur de Snap!, appelle ce langage le ´ no code - no limit language ´.
Extrait du résumé de ` Programming as a Medium `, keynote présenté le 16 juin 2022 par Jens Mönig au APSCE CTE-STEM (International Conference on Computational Thinking Education and STEM Education) :
Snap! permet d’approcher la programmation non seulement comme un outil qui nous aide à accomplir certaines tâches comme le calcul, l’apprentissage mais aussi comme un support privilégié d’exploration.
Snap! est un langage de programmation visuel emprunt de la philosophie de Scratch [23]. Contrairement à Scratch, Snap! traite les blocs de code comme des citoyens de première classe au lieu de les confiner à un mode d’édition pur.
Snap! est donc exactement ce qu’il nous faut pour coder et explorer le monde des Mathématiques.
Vous pourrez bien évidemment faire avec Snap! tout ce que vous faisiez avec Scratch [24].
Comme vous pouvez l’imaginez [25], il n’y a pas à connaître le lambda-calcul pour coder les fonctions du lycée avec Snap!, le Scratch qui code du code... [26]
Et à propos du mot clé lambda, remarquons que Alonzo, la petite mascotte de Snap! [27] s’appelle ainsi à la mémoire d’Alonzo Church (père du lambda-calcul) et possède une houpe sur la tête en forme de λ tourné.
Nous nous attachons ici à donner des exemples simples, qui illustrent les algorithmes clés des programmes de lycée.
La notion de Fonction au centre de l’apprentissage des Mathématiques
Dans l’article Tout est algorithme, tout est fonction, j’avais fait une première approche d’une pensée fonctionnelle du programme de première S en vigueur en 2019. J’y abordais la question fondamentale :
Qu’est-ce que la pensée algorithmique ?
C’est le fait d’analyser un problème afin de le décomposer en nombreuses petites fonctions ayant des tâches très précises, très réduites.
Dans cet article, je souhaite aller plus loin avec cette pensée fonctionnelle grâce au trio Map/Filter/Reduce, c’est à dire Map/Keep/Combine en langage Snap!.
En Mathématiques, il est courant d’appliquer une fonction à un ensemble ou à une partie d’un ensemble, et pas seulement à un élément isolé. C’est là que le trio Map/Filter/Reduce trouve tout son sens, en travaillant avec des listes d’objets qui peuvent être des nombres, mais aussi des images, des listes, des fonctions, des lutins ou un mélange de tout cela...
- La fonction Map, d’ordre supérieur, applique à chaque élément de E une fonction f:E → F.
Elle permet d’obtenir f(E), image de E par f, qui est une partie de F. [28] - La fonction Keep (Filter) envoie un ensemble E vers un sous-ensemble de E (en appliquant un test logique à chaque élément de E (un prédicat)). [29]
- Enfin, la fonction Combine (Reduce) applique un opérateur [30] à un ensemble d’objets E [31], et renvoie un objet unique. [32]
Voici comment Brian Harvey [33] décrit graphiquement de manière très explicite ce trio dans le manuel de référence du langage page 50.
La puissance des listes conjuguée à une pensée fonctionnelle
Aborder un algorithme à l’aide de listes et l’application exclusive du trio Map/Keep/Combine va donner une dimension supérieure à l’application de cet algorithme. Voici comment Mathematica décrit l’utilisation qu’il fait des listes :
« Lists are central constructs in the Wolfram Language, used to represent collections, arrays, sets, and sequences of all kinds. Lists can have any structure and size and can routinely involve even millions of elements. Well over a thousand built-in functions throughout the Wolfram Language operate directly on lists, making lists a powerful vehicle for interoperability. »
C’est cette vision des listes qui donne à Mathematica une telle puissance pour la résolution des algorithmes. Le langage Snap! a également été écrit dans cette optique : celle de permettre une programmation fonctionnelle en travaillant délibérément sur des objets de première classe, en particulier, des fonctions d’ordre supérieur et des listes de listes...
Nous voulons ici montrer à l’aide de nombreux exemples que nous pouvons nous aussi coder les algorithmes grâce à une pensée fonctionnelle exclusive, et que cela est abordable par nos élèves.
De la décomposition canonique d’une application à une décomposition de type Map/Filter/Reduce
La décomposition canonique d’une fonction se fait naturellement comme étant la composée : s o b o i .
(s = surjection, b = bijection, i = injection) [34]
Ce principe n’est pas utilisable mais donne sujet à réflexion. Au vu de tous les exemples que nous avons pu étudier, il semblerait que toute fonction calculable [35] puisse s’obtenir à l’aide de la composée de fonctions choisies parmi { Map , Filter, Reduce }, dans n’importe quel ordre, à condition d’autoriser des appels récursifs à ces fonctions. [36]
D’après la thèse de Alonzo Church concernant la définition de la notion de calculabilité,
Toutes les applications calculables peuvent être calculées en utilisant des fonctions récursives.
Par ailleurs, nous avons remarqué, au fil des exemples rencontrés depuis plusieurs mois, qu’un grand échantillon des applications calculables peut être implémenté à l’aide de fonctions d’ordre supérieur (bien sûr en autorisant des appels récursifs), notamment du type Map/Filter/Reduce.
Nous aimerions bien que cela nous conduise à cette affirmation...
Un grand nombre de fonctions calculables peut s’évaluer par un algorithme du type Map/Filter/Reduce.
Au lieu de fonder les mathématiques sur la notion d’ensemble, on peut fonder les mathématiques autour de la notion de fonction. On pourra commencer à ce sujet par lire cet article de Pierre Lescanne : Et si on commençait par les fonctions !.
De nombreux sites proposent des explications plus ou moins simples de ce qu’est le lambda-calcul et la programmation fonctionnelle, mais ne cherchez pas trop simple ; de toute façon, c’est compliqué ;-) ! Personnellement, je me cantonne au codage de fonctions mathématiques avec l’usage exclusif de fonctions, et vous verrez, au fur et à mesure, on entre petit à petit dans l’esprit de la programmation fonctionnelle.
Par exemple, pour rester en mode fonctionnel, on évitera d’utiliser for each item
pour parcourir une liste. Brian Harvey explique cela très bien dans le paragraphe ` Functional and Imperative List Programming ` page 48 du manuel de référence de Snap! 7.0. [37]
Écrire un algorithme, c’est décomposer le problème en une suite de fonctions aussi simples que possible.
Écrire un algorithme, ce sera donc écrire une série de fonctions permettant de résoudre cet algorithme, sachant qu’une fonction est obtenue grâce à un enchainement des opérateurs de référence : + , × .
Exemples progressifs niveau lycée
Vous trouverez dans cette section
– comment coder avec map des tableaux de valeurs pour une fonction du second degré avec des pas différents,
– le codage des coefficients binomiaux k parmi n avec deux combine,
– celui de la somme des k parmi n,
– un onglet de statistiques dans lequel nous adoptons le point de vue de John Tukey selon lequel une série statistique est résumée par les cinq valeurs caractéristiques : minimum, 1er quartile, médiane, 3ème quartile, maximum,
– des utilisations des booléens en simulation : tirages de cartes, jets de dés,
– des générations de graphes aléatoires.
La recherche du minimum ou du maximum d’une liste représentant un tableau de valeurs se fera en utilisant Combine et l’opérateur a min b ou a max b .
Second degré
On peut coder une fonction du second degré x ↦ a x² + b x + c ainsi :
[38] L’image de 100 par la fonction du second degré x ↦ 2 x² - 3 x + 1 est 19701.
On peut mapper cette fonction
– sur les entiers de l’intervalle [-3, 4] afin d’obtenir, par exemple, un tableau de valeurs de cette fonction pour les entiers de cet intervalle :
– sur la subdivision réelle par pas de 0.1 des nombres entiers de l’intervalle [0, 6].
Mais si dans le script précédent, on entre une liste comme argument [39], on obtient le script suivant :
Ce qui nous permet d’obtenir un tableau de valeurs simplement en appelant le script précédent :
On peut même obtenir un pas sur l’intervalle de départ :
Voir le lutin Second degré du projet Snap! lié à cet article.
Combinaisons de k éléments d’un ensemble à n éléments
Somme des (k parmi n) = 2ⁿ
– Somme des k parmi 5, k allant de 0 à 5. [40]
– Somme des k parmi 10, k allant de 0 à 10. [41]
Voir le lutin Combine du projet Snap! lié à cet article.
Maximum, minimum, quartiles, médiane
Le maximum, le minimum, les premier et troisième quartiles q1 et q3, la médiane sont les 5 valeurs caractéristiques d’une série statistique au sens de John Tukey. Il appelle ces cinq valeurs Résumé à 5 valeurs d’une série statistisque. Ce résumé à 5 valeurs est une façon de transmettre l’information essentielle dans une distribution. [42]
Script maximum de deux nombres |
Script minimum de deux nombres |
Soit alpha_0 = [5, 9, 7, 10, 4, 3, 6, 10, 1, 2] une série de 10 données que nous prenons pour illustrer nos calculs.
Nous devons d’abord l’ordonner : alpha = [1, 2, 3, 4, 5, 6, 7, 9, 10, 10]
Ainsi, le maximum de la série de données alpha s’obtient avec ce Combine : [43]
Et son minimum :
La médiane d’une série statistique partage l’ensemble ordonné de ses observations en deux parties égales. |
Par exemple, la médiane de la liste des 33 premiers nombres de Carmichael [44] est 101101, elle s’obtient avec ce Keep :
Nous devons distinguer les séries ayant un nombre de données impair de celles ayant un nombre de données pair.
D’où le script médiane d’une série de données alpha : [45]
– Script rang de la médiane d’une série de données alpha [46]
La médiane de alpha est 5,5. Son rang est 5,5.
Les quartiles q1, q2 (la médiane), et q3 d’une série statistique partagent un ensemble ordonné d’observations en quatre parties égales. |
– Script premier quartile q1 d’une série de données alpha : q1 est la médiane de la 1ère sous-série extraite lorsque l’on scinde la série de départ en deux séries de longueurs égales.
– Script rang de q1 d’une série de données alpha
– Script troisième quartile q3 d’une série de données alpha : q3 est la médiane de la 2nde sous-série extraite lorsque l’on scinde la série de départ en deux séries de longueurs égales.
– Script rang de q3 d’une série de données alpha
Enfin, nous pouvons obtenir le résumé de la série statistique alpha au sens de John Tukey.
– Script 5 valeurs caractéristiques de la série statistique alpha au sens de John Tukey
Les 5 valeurs caractéristiques de la série statistique alpha au sens de John Tukey sont :
[min, q1, med, q3, max] = [1, 3, 5.5, 9, 10]
– Script informations statistiques sur alpha
D’où les premières informations statistiques de la série alpha :
et celle des 33 premiers nombres de Carmichael :
Exercices
En vous inspirant des exemples précédents, on pourra :
– Coder les premier et neuvième déciles d1 et d9 [47].
– Extraire les nombres de la série dans l’intervalle interquartile [q1, q3] et les nombres de la série dans l’intervalle interdéciles [d1, d9].
– Écrire un script qui ayant entré une liste de données, renvoie une liste qui représente en mode texte le diagramme stem-and-leaf d’une distribution. Ce diagramme est une forme de graphique de fréquences. Ce diagramme est très intéressant à coder, car, contrairement aux histogrammes, il garde les informations concernant les données, et peut même s’appliquer à des données non numériques.
La série de données [20, 30, 32, 35, 41, 41, 43, 47, 48, 51, 53, 53, 54, 56, 57, 58, 58, 59, 60, 62, 64, 65, 65, 69, 71, 74, 77, 88 and 102] sera repésentée ainsi avec un diagramme stem-and-leaf :
2 | 0
3 | 025
4 | 11378
5 | 133467889
6 | 024559
7 | 147
8 | 8
9 |
10 | 2
On classe d’abord les données par ordre de grandeur [48]. On choisit ensuite le stem, ici on prend les dizaines. Les leaves sont les unités.
Voir le lutin John_Tukey du projet Snap! lié à cet article.
Tirages de cartes, Jets de dés
- Tirages de cartes
Cela revient à se poser la question suivante : comment tirer au hasard exactement p True parmi un ensemble de n booléens ?
Il suffit pour cela de créer une liste de n True, à laquelle on append une liste de $ n-p $ False. Puis on mélange le tout. Les indices des True donneront les cartes tirées avec un codage choisi de manière naturelle au préalable. Ce qui permettra d’afficher la main tirée au hasard.- Tirage de 3 cartes parmi 7
[49] - Tirage d’une main dans un jeu de 13 cartes
- Tirage de 3 cartes parmi 7
- Simulation de jets de dés
- Lancer d’un dé tétraédrique dont les faces sont numérotées de 1 à 4.
- Jet d’un dé tétraédrique dont les faces sont nommées A, B, C, D 13 fois
- Script Jet d’un dé à p faces n fois
- Jet d’un dé à 6 faces 3 fois
- Lancer d’un dé tétraédrique dont les faces sont numérotées de 1 à 4.
On pourra bien sûr utiliser ces idées pour coder la simulation d’un jeu de Pile ou Face, de lancers de pièce [50], de promenades aléatoires de fourmis sur une droite.
Voir le lutin Booléens du projet Snap! lié à cet article.
Graphes aléatoires
On pourra générer la matrice d’adjacence d’un graphe avec deux map imbriqués.
Dans le cas particulier d’un graphe simple et fini, la matrice d’adjacence est une matrice binaire avec des zéros sur la diagonale.
Script pour générer une telle matrice
Et un exemple de matrice d’adjacence d’un graphe simple :
Matrice qui représente de manière unique le graphe de sommets {A, B, C, D} suivant :
A → D
B → A, B → C, B → D
C → B, C → D
D → B
ToDo list
En statistiques, on pourra s’amuser à coder l’espérance, la variance, et l’écart-type d’une série de données.
Un peu d’arithmétique
L’arithmétique est un domaine des Mathématiques qui se prête particulièrement au codage avec des listes. Il est même presque intuitif de coder les problèmes d’arithmétique avec le trio Map/Keep/Combine (Map/Filter/Reduce).
Le lutin Nb_Premiers du projet Snap! lié à cet article est consacré à l’arithmétique. On y trouvera tous les scripts proposés ci-dessous.
Vous trouverez dans cette section comment coder :
– le nombre de diviseurs de n avec la longueur d’un Keep.
– un prédicat qui teste si un nombre est premier ou non.
– le crible d’Ératosthène
– les (nombres premiers avec n) inférieurs à n
– la fonction Phi d’Euler
– le test de primalité de Fermat qui s’appuie sur le Petit théorème de Fermat.
Diviseurs de n
– Liste des diviseurs de n
Prenons par exemple le nombre 323. 323 est le produit 17 × 19 ainsi 323 possède 4 diviseurs : 1, 17, 19 et 323.
Le prédicat Reste nul pour 323 mod n, n ≤ 323 renvoie donc 4 True sur 323 booléens.
On garde alors les items True du prédicat Reste nul pour 323 mod n
Ceci nous donne le script Liste des diviseurs de n. [51]
Liste des diviseurs de 100. [52] | Liste des diviseurs de 101. |
Liste des diviseurs de 323. | Liste des diviseurs de 997. |
Liste des diviseurs de 998. | Liste des diviseurs de 1001. [53] |
– Nombre de diviseurs de n
323 possède 4 diviseurs 1, 17, 19 et 323. Donc 323 n’est pas premier.
– Somme des diviseurs de n
La somme des diviseurs de 100 est 217.
En effet, $1 + 2 + 4 + 5 + 10 + 20 + 25 + 50 + 100 = 217$
Nombres premiers
Le nombre de diviseurs de 323 s’obtient en demandant la longueur de ce Keep :
Et n est premier si son nombre de diviseurs est égal à 2.
D’où le script is n a prime number ?.
101107 est premier. 101107 sur le site NumberEmpire.
– Crible d’Ératosthène
Script Help Crible d’Ératosthène
Help Crible d’Ératosthène
Script Crible d’Ératosthène | Crible d’Ératosthène appliqué a 100. |
On retrouvera grâce au crible d’Ératosthène qu’il y a 25 nombres premiers inférieurs à 100 : [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
Et 168 nombres premiers inférieurs à 1000 :
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997]
– Décomposition en facteurs premiers
Décomposition en facteurs premiers de 561.
Script Décomposition en facteurs premiers
Fonction Phi d’Euler
Définition de la fonction phi d’Euler :
Pour tour entier n ≥ 1, φ(n) est le nombre d’entiers compris entre 1 et n (inclus) qui sont premiers avec n. |
– Script Nombres premiers avec n inférieurs à n.
On vérifiera grâce à ce script qu’il y a 40 nombres premiers avec 100 inférieurs à 100. Ainsi, φ (100) = 40. [1,3,7,9,11,13,17,19,21,23,27,29,31,33,37,39,41,43,47,49,51,53,57,59,61,63,67,69,71,73,77,79,81,83,87,89,91,93,97,99]
Et 400 nombres premiers inférieurs à 1000. Ainsi, φ (1000) = 400.
– Script Fonction Phi d’Euler.
Fonction Phi d’Euler appliquée à 100.
Fonction Phi d’Euler appliquée à 81.
Test de primalité de Fermat
Le petit théorème de Fermat s’énonce comme suit :
si p est un nombre premier et si a est un entier quelconque, alors $a^p – a$ est un multiple de p |
Le Map de la fonction x → x^113 modulo 113 renvoie les index de chaque item, car 113 est premier (d’après le petit théorème de Fermat).
Nous avons besoin pour ce test d’activer
Use BigNumbers de la librairie Bignums, rational, complex
Script Petit théorème de Fermat.
Petit théorème de Fermat appliqué à 113.
Script Test de primalité de Fermat.
Le test de primalité de Fermat appliqué à 113 répond naturellement True,
tandis que le test de primalité de Fermat appliqué à 112 répond naturellement False.
Le test de primalité de Fermat appliqué à 561 donne comme réponse True pourtant,
la liste des diviseurs de 561 est :
Donc 561 = 3 x 11 x 17.
561 est un nombre de Carmichael pour lesquels le test de primalité de Fermat donne True.
On pourra consulter THE ON-LINE ENCYCLOPEDIA OF INTEGERS SEQUENCES.
Ainsi, les 33 premiers nombres de Carmichael sont listés sur cette page.
ToDo list
– Recherche de nombres premiers particuliers (Mersenne, Fermat)
33 premiers nombres de Mersenne notés Mₙ :
[0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, 131071, 262143, 524287, 1048575, 2097151, 4194303, 8388607, 16777215, 33554431, 67108863, 134217727, 268435455, 536870911, 1073741823, 2147483647, 4294967295, 8589934591]
On se demande quels sont les nombres de Mersenne premiers.
« Il existe un test de primalité efficace pour les nombres de Mersenne, le test de primalité de Lucas-Lehmer ; de ce fait, les plus grands nombres premiers connus sont des nombres de Mersenne. Les nombres de Mersenne premiers sont pourtant rares : seulement 51 sont connus début 2022. On ne sait même pas s’il en existe une infinité. » [54]
Test de primalité de Lucas-Lehmer
Édouard Lucas a développé ce test le premier dans sa Théorie des fonctions numériques simplement périodiques en 1878.
Test de primalité de Lucas-Lehmer pour les nombres de Mersenne
Je vous propose d’appliquer le théorème énoncé dans ce test de primalité pour écrire un script qui détermine si un nombre de Mersenne Mₙ est premier. [55]
– Détermination de triplets pythagoriciens
Ce sont les triplets de la forme $ x² + y² = z² $. [56]
– Somme de 2 carrés, somme de 3 carrés, somme de 4 carrés
Lagrange a démontré en 1770 que tout nombre entier est somme de 4 carrés.
Écrire un script qui pour un entier n renvoie une liste [p, q, r, s] telle que $n = p² + q² + r² + s²$ .
– Somme de 2 cubes
J’adore cette anecdote à propos de Srinivasa Ramanujan rapportée par le mathématicien Godfrey Harold Hardy. Hardy parlant du numéro d’immatriculation sans intérêt du taxi qu’il venait de prendre, Ramanujan lui rétorque que ce numéro est au contraire très intéressant :
« 1729 est le plus petit nombre décomposable en somme de deux cubes de deux manières différentes. » [57]
Écrire un script qui renvoie pour un entier n les sommes de 2 cubes non dupliquées inférieures à n sous la forme $x³ + y³$ [58].
– Algorithme d’Euclide-Bézout
Écrire un script pour l’algorithme Bézout-Blankinship récursif.
Calculs sur les suites
L’utilisation du trio Map/Filter/Reduce (Map/Keep/Combine) est particulièrement intéressant pour les calculs sur les suites.
Vous trouverez dans cette section comment coder sans boucle :
– la somme des termes d’une suite avec un simple combine
– le produit des termes d’une suite avec un simple combine
– quelques calculs autour des nombres de Fibonacci
– une exploration autour la suite de Syracuse : Temps de vol , Temps de vol en altitude, altitude maximale qui s’obtient avec un simple Combine utilisé avec l’opérateur maximum( , ).
– une petite investigation sur la suite (1 + 1/n)ⁿ.
Somme des termes d’une suite
J’ai expérimenté en classe le codage des suites numériques avec Map/Combine en première S pendant l’année scolaire 2018-2019 [59].
– Voir ce premier exemple
– Somme des termes d’une suite arithmétique
– En Terminale S (année scolaire 2017-2018)
[60]
Voir le lutin Suites SA et SG du projet Snap! lié à cet article.
Produit des termes d’une suite
– Le produit des premiers entiers naturels inférieurs à n nous donne n!.
Ainsi 10! = 1 x 2 x 3 x ... x 10 = 3628800
On aura donc le choix pour coder la fonction factorielle entre ces deux scripts :
Voir le lutin Combine du projet Snap! lié à cet article.
Suite de Fibonacci
La suite des nombres de Fibonacci commence ainsi [1,1,2,3,5,8,13,..], dans laquelle, hormis les deux premiers termes 1 et 1 qui servent à initialiser la suite, les termes sont obtenus comme somme des deux précédents.
Ainsi, le 12-ième nombre de Fibonacci est 144.
On peut coder le calcul du n-ième nombre de Fibonacci à l’aide de ce script récursif :
Ce qui nous permet d’écrire ce script qui renvoie du 1er au n-ième nombre de Fibonacci :
Map du 1er au 5-ième nombre de Fibonacci :
On peut aussi construire autrement la liste des premiers nombres de Fibonacci :
– Script Help nombres de Fibonacci jusqu’au n-ième
– d’où le Script Nombres de Fibonacci jusqu’au n-ième
Avec lequel nous obtenons :
Voir le lutin Fibonacci du projet Snap! lié à cet article.
Suite de Syracuse
Voici la définition de la suite de Syracuse donnée dans Wikipedia :
On appelle suite de Syracuse une suite d’entiers naturels définie de la manière suivante : on part d’un nombre entier strictement positif ; s’il est pair, on le divise par 2 ; s’il est impair, on le multiplie par 3 et l’on ajoute 1. |
Script suite de Syracuse pour u₀ appliquée à n :
suite de Syracuse pour u₀ = 12 appliquée à 100 |
suite de Syracuse pour u₀ = 15 appliquée à 20 |
Script suite de Syracuse du nombre a₀ jusqu’au rang n
Exemple avec u₀ = 15 jusqu’au rang 18 :
Map de la suite de Syracuse pour u₀ = 10 sur les entiers de 0 à 7 :
Suite de Syracuse de 77 671 jusqu’au rang 260 nous fournit la résultat suivant :
On pourra le vérifier à l’aide de ce lien.
La conjecture de Syracuse [61], ou conjecture de Collatz, affirme que pour tout entier N > 0, il existe un indice n tel que uₙ = 1. |
Il existe tout un vocabulaire autour de cette suite :
– Temps de vol : c’est le plus petit indice n tel que uₙ = 1.
L’index du 1er item de la liste des termes de la suite de Syracuse pour u₀ = 77671 est 232.
Ce qui nous fournit le script Temps de vol suite de Syracuse suivant :
Ainsi, le temps de vol de la suite de Syracuse pour u₀ = 77671 est 231.
Le Map de la fonction liste(index, value) sur la suite de Syracuse du nombre 15 jusqu’au rang 18 fournit :
Le 1er item égal à 1 dans la liste des termes de la suite de Syracuse du nombre 15 jusqu’au rang 18 s’obtient avec ce bloc :
L’index du 1er item égal à 1 dans la liste des termes de la suite de Syracuse du nombre 15 jusqu’au rang 18 s’obtient donc ainsi :
Ce qui nous fournit le script Temps de vol suite de Syracuse plus efficace que le précédent [62] :
dans lequel le script Help est :
Le temps de vol de la suite de Syracuse pour u₀ = 15 est 17.
– Temps de vol en altitude : c’est le plus petit indice n tel que uₙ₊₁ < u₀.
Script Temps de vol en altitude suite de Syracuse [63]
dans lequel le script Help est :
Le temps de vol en altitude de la suite de Syracuse pour u₀ = 15 est 11.
– Altitude maximale : c’est la valeur maximale de la suite.
Le maximum de la suite de Syracuse du nombre 77 671 s’obtient grâce à un Combine.
Ainsi, l’altitude de la suite de Syracuse du nombre 77 671 est de 1 570 824 736 (et son temps de vol est 231).
On sait qu’une fois 1 atteint, le maximum a déjà été atteint.
D’où le script Altitude maximale de vol de la suite de Syracuse pour u0 donné :
- Altitude maximale de la suite de Syracuse du nombre 127 :
- Altitude maximale de la suite de Syracuse du nombre 15 :
- Altitude maximale de la suite de Syracuse du nombre 14 :
- Altitude maximale de la suite de Syracuse du nombre 121 :
Voir le lutin Syracuse du projet Snap! lié à cet article.
Suite ((1 + 1/n )ⁿ)
Voici les 5 premiers termes de la suite (1 + 1/n)ⁿ :
Cette suite tend vers le nombre d’Euler lorsque n croît, mais elle est à convergence très lente.
On voit en effet qu’il faut attendre n = 1 000 000 pour avoir les 5 premiers chiffres exacts de e.
e = 2.71828182845904523536028747135266249775724709369995...
[64]
Voir le lutin e = lim((1+1/n)ⁿ) du projet Snap! lié à cet article.
On pourra aussi consulter le lutin e qui fournit une comparaison de 3 méthodes d’approximation de e. Voir l’onglet Encadrement de e dans les recherches de valeurs approchées de nombres réels.
Applications : Recherche de valeurs approchées
On pourra effectuer des recherches de valeurs approchées de π, e, √2 , φ = (1 + √5)/2 , ln(2), etc... grâce à des algorithmes bien choisis.
Cette section Applications permet d’aborder la constante d’Apéry, de voir diverses approches pour obtenir une approximation de e, puis un algorithme pour approcher π avec une très belle formule de Ramanujan.
Encadrement de e
1. Encadrement de e par programmation fonctionnelle en Terminale S (année scolaire 2017-2018).
2. On pourra comparer trois méthodes pour approcher le nombre d’Euler et tester leur efficacité dans le lutin e qui fournit une comparaison de ces 3 méthodes d’approximation de e.
- Méthode 1
Définition de e par Euler comme somme de la série Σ(1/n !) (de n = 0 à +∞) |
- Méthode 2
La suite numérique de terme général ((1 + 1/n)ⁿ) tend vers e lorsque n tend vers +∞ |
- Méthode 3
Cet élégant algorithme nous vient d’un tweet dans lequel le théorème suivant est cité :
La racine n-ième de la moyenne géométrique des coefficients binomiaux de la n-ième ligne du triangle de Pascal tend vers √e lorsque n tend vers +∞. |
Malheureusement, il se révèle être inefficace pour l’approximation de e.
Ce Map permettra d’embrasser les 3 méthodes d’un seul clic :
Approximation de π par Ramanujan
L’une des formules fournissant une approximation de π à convergence rapide a été trouvée par le mathématicien indien Srinivasa Ramanujan en 1910.
Valeurs approchées de π par Ramanujan : la fonction à sommer
Script Valeurs approchées de π
Il faut bien sûr activer la librairie BigNumbers.
On pourra mapper Valeurs approchées de Pi de 0 à 50. [65]
ToDo List
– Suites adjacentes tendant vers le nombre d’Or φ = (1 + √5)/2
– Suites tendant vers √2
– Suites tendant vers ln(2)
Et en géométrie ?
Les applications du trio Map/Keep/Combine en géométrie dans l’environnement de Snap! ouvrent un vaste champ de possibilités de codage des problèmes que l’on se pose. Avec l’avènement des big data, la Statistique est devenue un domaine majeur dans l’enseignement des Mathématiques alors que la Géométrie avait perdu un peu de son faste.
Mais grâce à l’environnement graphique que Snap! nous offre et le trio Map/Keep/Combine, la géométrie analytique revient à l’honneur.
Effectuons une petite incursion au pays où les problèmes de géométrie se résolvent par le recours systématique au calcul algébrique.
On se place dans le plan affine muni d’un système de coordonnées cartésiennes.
Le problème de Fermat
Dans l’article Les routes de Monsieur Fermat avec CarMetal et Scratch publié sur L’IREM de la Réunion, nous avions déjà abordé le sujet sous l’angle des fonctions.
Nous avons besoin ici de munir l’espace affine cartésien d’une métrique afin de parler de distances.
Enoncé du problème posé par FERMAT :
Résolution où le triangle $ABC$ des trois villes présente des angles inférieurs à 120°.
Étant donné un point $M$ du plan, le problème est de minimiser la distance $MA+MB+MC$.
D’où l’idée de travailler sur la fonction :
$f$ : $M \mapsto MA+MB+MC$.
Toricelli a démontré en 1659 qu’il existe un point intérieur au triangle $ABC$ qui rend $f(M)$ minimum.
Écrire un script qui étant donné trois points $A$, $B$, $C$ entrés sous la forme de listes de leurs coordonnées renvoie la liste des coordonnées du point qui réalise le minimum de $f(M)$.
Pour traiter l’exercice, on pourra :
- mapper la somme des trois distances $MA$, $MB$, $MC$ aux points de la fenêtre Snap! de l’écran [-240,240] x [-180,180]. [66]
- appliquer à la liste obtenue Combine avec l’opérateur min( , ).
Je propose dans cette annexe une première approche pour résoudre ce problème.
Mais voici la démarche détaillée d’une seconde approche que j’ai eue.
L’algorithme qui en résulte est plus simple, du fait d’une meilleure organisation de la structure des données de départ. [67]
– Créer une liste Points_du_Plan qui contient les coordonnées des points de la fenêtre graphique de Snap! dans sa résolution d’origine 480 x 360.
Points_du_Plan = [ [-240,-180],[-239,-180], ... , [239,-180],[240,-180], [-240,-179],[-239,-179], ... , [239,-179],[240,-179], ... ,[-240,180],[-239,180], ... , [239,180],[240,180] ] [68]
Grâce à ce script :
– On crée alors une liste des distances $MA+MB+MC$ pour M décrivant Points_du_Plan. On obtient un tableau de même taille que le précédent.
Avec ce script pour la fonction somme des distances :
où la distance est codée à l’aide d’un Combine avec l’opérateur + .
On effectue alors ce Combine avec l’opérateur min( , ). Il nous renvoie la distance minimale d réalisée.
Pour finir, un Keep permet d’extraire les coordonnées du point de Toricelli qui réalise la distance minimale.
Voici quelques points de Fermat_Toricelli obtenus par cet algorithme pour des points $A, B, C$ différents.
- Le point de Fermat_Toricelli de A = [-80, 160], B = [45, -150], C = [180, -60] est T = [82, -69].
Il réalise le minimum de $MA+MB+MC$ et ce minimum vaut 468. [69] - Le point de Fermat_Toricelli de A = [-127, -59], B = [-98, 24], C = [171, -3] est T = [-88, 5], il réalise la distance minimale de 356.
- Le point de Fermat_Toricelli de A = [-200, 10], B = [210, 140], C = [-120, -60] est T = [-119, -39], il réalise la distance minimale de 490.
- Le point de Fermat_Toricelli de A = [200, 10], B = [-100, 50], C = [10, -120] est T = [22, -54], il réalise la distance minimale de 417.
Barycentre d’une liste de points
On considère la fonction $f$ du plan dans l’ensemble des vecteurs définie par :
Étant donné 3 points $A$, $B$, $C$,
$f$ : $ M \mapsto \alpha \overrightarrow{MA} + \beta \overrightarrow{MB} + \gamma \overrightarrow{MC} $
L’antécédent du vecteur $\vec{0}$ par cette fonction est le barycentre de $ A_{(\alpha)}, B_{(\beta)}, C_{(\gamma)} $.
On a donc $ f^{-1}(\vec{0}) = G $ . [70]
Nous allons donc représenter un point par la liste de ses coordonnées dans le plan.
Le vecteur $ \alpha \overrightarrow{MA} + \beta \overrightarrow{MB} + \gamma \overrightarrow{MC} $ sera obtenu pour $M$ décrivant le plan en appliquant le Map suivant :
Map( $ \alpha {\Box}A + \beta {\Box}B + \gamma {\Box}C $ ) à la liste des points de la fenêtre Snap! de l’écran ; où $A$, $B$, $C$ sont fournis par les listes de leurs coordonnées.
On effectue ensuite Keep(= $\vec{0}$) sur la liste obtenue afin d’extraire de cette liste les coordonnées du point $G$.
Le principe que je viens d’exposer fonctionne mais constitue l’artillerie lourde puisque l’on sait exprimer le barycentre de plusieurs points de manière explicite.
Pour 3 points, on pourra en effet déterminer le point G avec cette relation $ G = 1/(\alpha + \beta + \gamma) ( \alpha A + \beta B + \gamma C ) $ [71]
Comme application intéressante du barycentre en géométrie analytique, il y a la notion de morphing.
Je cherche à réaliser avec Snap! un morphing d’un cercle qui se transforme en carré [72] comme dans ce travail Morphing et barycentre avec CaRMetal (1) et dans celui-ci Morphing et barycentre avec CaRMetal (2) où les élèves avaient créé des animations de morphose.
On peut généraliser ces méthodes à un barycentre de n points avec l’apparition des macros depuis la version 8.0 de Snap! sortie le 15 août 2022. Brian Harvey appelle cela la métaprogrammation. Elle permet d’écrire des programmes de programmes. Ce concept a été présenté au colloque international Snap!Con 2022 par :
– Jens Mönig dans sa présentation : What’s cooking in Snap !
– Brian Harvey dans sa présentation : A History of Metaprogramming
Transformations géométriques
On peut trouver l’expression cartésienne des coordonnées des points du plan obtenus par les transformations suivantes :
– translation $t_{\vec{u}} : M \mapsto M’ $ tel que $ \overrightarrow{MM’} = \vec{u} $
On a sur les coordonnées : ${x’ = x + x_u,y’ = y + y_u}$
Mais avec un opérateur d’addition adéquat, on pourra écrire $M’ = M + u$ [73]
– symétrie centrale de centre A : A est le milieu de [MM’] donc $M’ = 2 A - M$ [74]
– symétrie axiale par rapport à $\delta$ : on devra exprimer que $\delta$ est la médiatrice de [MM’].
– homothétie $h_{(Ω,k)} : M \mapsto M’ $ tel que $ \overrightarrow{ΩM’} = k \overrightarrow{ΩM}$. On aura donc : $ M’ = k M + (1-k) Ω $ [75]
– rotation d’angle $\theta$ : ${x’ = x \cos\theta + y \sin\theta,y’ = -x \sin\theta + y \cos\theta }$
On pourra alors mapper la transformation voulue aux points de l’ensemble dont on veut obtenir le transformé.
On a obtenu par cet algorithme la transformée d’une lemniscate de Bernouilli par une rotation de 120° [76]. [77]
Et cette rosace de lemniscates de Bernouilli.
Courbes algébriques
On pourra s’amuser à représenter des courbes définies par leur équation dans la fenêtre de Snap! en utilisant (Map/Keep). [78]
On pourra travailler dans la fenêtre d’origine dont la résolution par défaut est 480 x 360 pixels². Mais on peut bien sûr modifier cette résolution de base afin d’obtenir des courbes plus fines.
Comme ce bouquet de fleurs fractales obtenu par un algorithme très simple. Ce bouquet a une taille de 1900 x 1202 pixels². [79]
Ainsi, F et F’ étant deux points du plan, la lemniscate de Bernouilli [80] est le lieu des points M tels que $ MF . MF’ = {OF}^2 $.
En posant $OA = a = OF \sqrt 2 $ , l’équation cartésienne de la lemniscate s’écrit :
$ (x^2 + y^2)^2 = a^2 (x^2 - y^2) $
En travaillant sur les coordonnées polaires, nous obtenons un tracé efficace (moins de perte de points aux endroits où la courbe est quasi verticale ; moins d’accumulation au voisinage du point double). Les images sont de bien meilleure qualité.
Si l’on travaille sur l’équation cartésienne de la lemniscate sous la forme $R(x,y) = 0$, il faut mapper la relation $R(x,y)$ aux coordonnées des points du plan de Snap! pour calculer l’expression puis utiliser Keep sur la liste calculée pour extraire les points qui vérifient l’égalité $R(x,y) = 0$.
Avec les coordonnées polaires, un simple map appliqué à la liste des angles de l’intervalle [1°, 360°] suffit, car nous avons des expressions explicites.
Ensuite, on effectue un map des commandes de tracé de la courbe appliqué à l’ensemble des coordonnées extraites.
Et maintenant, nous pouvons nous permettre tous les délires possibles.
Comme par exemple ces lemniscates de Bernouilli qui nous envoient des messages cryptés...
La première image renvoie les 179 premières décimales de π sur une lemniscate de Bernouilli.
Une idée centrale de la philosophie de Gödel est qu’il n’y a pas de hasard dans l’univers.
La seconde image nous envoie ce message crypté en Hexadécimal sur une lemniscate.
La troisième nous envoie ce message crypté en morse.
Variations autour de la lemniscate de Bernouilli
– Vol de colombes [81]
– Lemniscate de Bernouilli effet ruban de Möbius
On peut jouer sur la programmation visuelle vue par Snap! pour allier l’usage de Map/Keep/Combine et le clonage des lutins. Ces magnifiques lemniscates à effet ruban de Möbius sont obtenues en estampillant chaque lutin sur la lemniscate. [82]
– Une lemniscate de Bernouilli et une cardioïde pour dire je t’aime à l’infini ;-)
[83] |
ToDo list
- Étant donné 3 points A, B, C, écrire un script qui renvoie sur une fenêtre graphique quelques éléments remarquables du triangle ABC :
– le point de Fermat-Toricelli si tous les angles du triangle ABC sont inférieurs à 120°,
– le centre de gravité du triangle ABC,
– l’orthocentre du triangle ABC,
– les centres respectifs des cercles inscrit et circonscrit. [84]
– la droite d’Euler du triangle ABC,
– si on a le courage... le Point d’Apollonius du triangle ABC. (Euh, je plaisante !) - S’amuser à tracer les courbes algébriques exposées dans le livre Courbes mathématiques du Palais de la Découverte.
Nous sommes bien sûr très loin de la géométrie dynamique.
En alliant les perspectives offertes par le codage dans un environnement graphique très performant (lutins, clônage, envoi de messages avec transmission optionnelle de données [85] depuis la version 8.0), et l’outil Map/Keep/Combine sur des listes de données, je suis persuadée que l’on pourra créer un environnement de géométrie dynamique avec Snap!.
De l’intérêt du Map/Keep/Combine
Travail sur les listes
Cette section développe la pertinence de travailler sur des listes de nombres.
– Comment obtenir tous les index d’un item dans une liste,
– Comment renverser une liste,
– Comment insérer un élément dans une liste,
– Un algorithme pour shuffle (secouer les éléments d’une liste).
Voir le lutin Listes du projet Snap! lié à cet article.
Tous les index d’un item dans une liste
Reprenons notre liste Y = [2,3,1,1,9,1,1,48] qui est la liste des restes modulo 49 des nombres de la liste c dans l’onglet Obtenir les classes d’équivalence modulo n des exemples d’extraction avec Keep.
Cherchons les index de 1 dans la liste Y. Ce seront aussi les index des antécédents de 1 dans la liste c par la fonction f.
Les index d’un item dans une liste sont ni plus ni moins les antécédents de cet item par la fonction Liste.
Nous allons copier Escher et voir le problème depuis une dimension supérieure, comme ces reptiles qui sortent de la dimension 2 pour prendre de la hauteur et observer ce qui leur arrive dans le plan, avant d’y retourner. [86] C’est exactement ce que nous allons faire : nous élever pour obtenir des informations que nous n’avons pas (les index), afin de revenir à une simple liste, connaissant les informations cherchées. Nous retrouverons ce raisonnement un grand nombre de fois au cours de cet article. Il est à chaque fois notifié par une icône de gecko, comme vous avez déjà pu l’observer au cours de cet article. C’est pourquoi nous l’appellerons le le principe du gecko. |
On mappe la fonction Liste(valeur, index) pour obtenir la liste de listes suivante :
De cette liste, on extrait alors les listes dont le premier item est égal à 1.
Finalement, en mappant à la liste résultat la fonction item(last), on obtient la liste des antécédents de 1 dans la liste Y.
Nous devons maintenant appliquer un Keep pour obtenir tous les antécédents de 1 par la fonction Liste. [87]
Le script qui découle de ce raisonnement est donc celui-ci :
Et nous avons bien : Liste⁻¹(1) = {3, 4, 6, 7} [88]
– Traitons maintenant un autre exemple cette fois en Python.
Nous avons d’abord besoin d’une fonction qui construit une liste de nombres compris entre a et b [89] :
- def numbers(a,b):
- if (a > b):
- return []
- return [a] + numbers(a+1,b)
ou
- def numbers_(a,b):
- if (a > b):
- return []
- return list(range(a,b+1))
Dans la liste alpha = [3, 1, 2, 3, 4, 5, 3, 7, 3, 3], les index de la valeur 3 sont 0, 3, 6, 8 et 9 :
- alpha = [3, 1, 2, 3, 4, 5, 3, 7, 3, 3]
- numbers(0, len(alpha)-1) # renvoie la liste [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] qui contient les index de la liste alpha
- c = map(lambda a,b: [a, b], alpha, numbers(0, len(alpha)-1))
- # renvoie [[3, 0], [1, 1], [2, 2], [3, 3], [4, 4], [5, 5], [3, 6], [7, 7], [3, 8], [3, 9]]
- d = filter(lambda x: x[0] == 3, list(c))
- # renvoie [[3, 0], [3, 3], [3, 6], [3, 8], [3, 9]]
Renverser une liste
Le script last at the top place le dernier élément d’une liste au début de la liste :
On renverse la liste avec un appel récursif à reverse(last_at_the_top) :
- def last_at_the_top():
- # à écrire ;-)
- return()
- def reverse(a):
- if a == []:
- return a
- return [a[-1] + reverse(last_at_the_top(a)[1:])]
Insérer un élément
- def insert_(n,id,lst):
- return lst[:id]+[n]+lst[id:]
- lst = [1, 2, 3, 4]
- insert_(99,3,lst)
- [1, 2, 3, 99, 4]
Secouer les éléments d’une liste (shuffle)
Script Shuffle
Où le script Shuffle helper est :
Si je secoue la liste [1,5,3,4,5], j’obtiens
Quelques exemples d’utilisation
– Mélange des entiers de 1 à 7
– Mélange de lutins
Concaténation
Il s’agit de réécrire la fonction append(a, b)
de Snap! qui concatène deux listes.
En Python, on pourra s’amuser à réécrire a + b
pour deux listes a et b.
ToDo list
– échanger deux éléments
– tester si une sous-liste appartient à une liste
– ordonner une liste
Efficacité du trio Map/Filter/Reduce en programmation
Le trio Map/Filter/Reduce permet une parallélisation des processus pour des données massives.
– Utilisation par les développeurs professionnels
Julien Aymé est développeur Java travaillant dans la grande distribution à la Réunion. Je lui ai demandé de m’expliquer le rôle de Map-Reduce et son utilisation dans son développement.
Voici l’interview de Julien, développeur Java. [90]
En gros, il y dit qu’on effectue le découpage des paquets de données (streams) en plus petits paquets sur lesquels les algorithmes seront appliqués en parallèle, puis on regroupe les résultats. On y gagne en efficacité pour des gros paquets de données (streams). Voir une explication détaillée du fonctionnement de Map-Reduce sur Wikipedia. Par exemple, pour son utilité dans le cloud computing, il y est dit ceci :
Le MapReduce a émergé en 2004 comme un important modèle de programmation pour les applications utilisant d’énormes quantités de données grâce à sa répartition efficace du travail sur différents nœuds de calcul. Il commence notamment à être utilisé dans le Cloud Computing car son nombre de données stockées et manipulées ne cesse de croître. Il est donc nécessaire d’avoir un moyen d’améliorer le traitement des données au sein du Cloud.
Vous trouverez de nombreux sites expliquant l’utilisation de Map/Filter/Reduce en programmation. [91]
Notez qu’une librairie Streams (Lazy lists) est fournie avec Snap!.
Comment le présenter aux élèves en cours de mathématiques ?
Avec Snap!, on peut évidemment reformuler les titres des blocs Map, Keep, Combine afin qu’ils soient facilement utilisables par les élèves. J’ai donc reformulé le trio Map/Keep/Combine à des fins pédagogiques, afin que ces blocs soient plus accessibles aux élèves, comme ceci : Appliquer/Extraire/Combiner.
À propos de fins pédagogiques, remarquons tout d’abord que la team de Snap! a choisi de manière délibérée d’appeler ce trio Map/Keep/Combine au lieu de Map/Filter/Reduce afin que ces termes soient clairement compréhensibles par les jeunes codeurs, même si la plupart des langages utilisent Map/Filter/Reduce. En particulier, le mot filter ne distingue pas les filtres entrants [92] des filtres sortants [93]. Keep est totalement non ambigü, il désigne bien un filtre entrant. [94]
Le lutin Squelette du projet Snap! lié à cet article est consacré à cette présentation.
– Faire un Map, c’est simplement Appliquer une fonction à une liste de données. On obtient une liste transformée contenant le même nombre d’objets que la liste de départ.
– Faire un Keep (ou Filter), c’est Extraire des éléments d’une liste en appliquant un prédicat à cette liste de données (une condition est-elle vérifiée ou pas ?). On obtient alors une liste extraite de la liste de départ ; cette liste contient les éléments vérifiant la condition demandée.
Ainsi, le script suivant permet d’extraire les multiples de 7 des entiers non-nuls inférieurs à 50.
– Effectuer un Combine (ou un Reduce), c’est Combiner, appliquer à la liste de départ une fonction dont l’image est un objet unique, résultat d’une combinaison des éléments de la liste de départ. On pourra illustrer un exemple de Combine avec des nombres réels par le produit scalaire de deux vecteurs [95].
La somme des 10 premiers entiers est égale à 55. Tous les lycéens connaissent(aient...) ce résultat !
Effectuer un Combine (ou un Reduce), c’est donc appliquer un opérateur de E × E dans E aux éléments de E comme indiqué dans la note [13]. L’exemple le plus simple à mon sens est la somme des éléments d’une liste de nombre réels.
On pourra demander aux élèves de chercher des exemples avec des nombres (autre que le produit scalaire) mais aussi avec des objets d’autres types.
Dans cet exemple : Combine (liste[1:10] avec l’opérateur join( , ) ), nous allons obtenir 12345678910.
Cela permettra de réfléchir avec les élèves sur le sens d’un opérateur, essence de tous calculs...
– Appliquer/Extraire/Combiner (Map/Keep/Combine) avec quelques exemples concrets.
Vous trouverez dans cette section des exemples où les trois items Appliquer, Extraire, Combiner sont combinés d’abord deux à deux, puis les trois ensemble. Vous trouverez même des Combine opérant sur des lutins polygonaux.
Appliquer/Extraire (Map/Filterbleu marine] ou Map/Keepviolet])
On obtient la liste des cubes pairs inférieurs à 1000.
Appliquer/Combiner (Map/Reducebleu marine] ou Map/Combineviolet])
La somme des dix premiers cubes est égale à 3025.
La longueur d’une liste pourra s’obtenir en mappant la fonction constante x ↦ 1 à la liste : [96]
puis en combinant les valeurs 1 obtenues à l’aide de l’opérateur + .
En fait, la simple action de compter, c’est Combiner (Reduce).
— Dans un genre plus fun, on pourra travailler avec les élèves sur des lutins polygonaux.
[97]
Pour obtenir une série de 2 triangles, un carré, un pentagone,
un hexagone et un heptagone, on pourra faire :
Et pour obtenir une liste de 3 triangles, 2 carrés, 3 pentagones, 3 hexagones et 2 heptagones :
On pourra ensuite combiner les lutins polygones obtenus avec l’opérateur créé à cet effet qui combine et tamponne deux lutins sur l’image :
D’où le résultat (avec parfois plusieurs tampons appliqués) :
Les élèves pourront ainsi s’amuser à créer des polygones étoilés.
Vous trouverez les scripts ci-dessus dans le lutin Polygones du projet Snap! lié à cet article.
Extraire/Combiner (Filter/Reducebleu marine] ou Keep/Combineviolet])
La somme des carrés d’entiers inférieurs à 100 est 385.
Le plus grand nombre premier inférieur à 100 est 97.
Appliquer/Extraire/Combiner (Map/Filter/Reducebleu marine] ou Map/Keep/Combineviolet])
La somme des cubes pairs des 10 premiers entiers est 1800.
En appliquant le trio Appliquer/Extraire/Combiner (Map/Filter/Reduce ou Map/Keep/Combine) en classe, nous allons pouvoir mettre l’accent sur la notion de fonction, demander aux élèves quel est l’ensemble de départ, l’ensemble d’arrivée, réfléchir sur des notions profondes liées aux fonctions. Travailler sur le sens.
En classe, nous allons principalement travailler avec des nombres. Appliquer une fonction (donc utiliser le bloc Map) à une liste de nombres, c’est utiliser une suite de fonctions de référence. Par exemple, calculer $(1 + 1/x)^x$ , c’est appliquer la fonction inverse, ajouter 1, puis élever le résultat obtenu à la puissance $x$ (opérateur d’exponentiation ^).
Combiner une liste de nombres ne pourra se faire qu’avec des opérateurs associatifs. Les opérateurs les plus utilisés seront + , ×.
On pourra demander aux élèves de coder l’opérateur d’exponentiation ^ sans utiliser un algorithme récursif, ce qui peut être très instructif. Il suffit de se référer à la définition.
a ^ b = (a × a × ... × a) b fois.
Il suffit donc d’appliquer la fonction constante x ↦ a à une liste quelconque de b nombres entiers ;-), puis appliquer Combine avec l’opérateur × à la liste qui résulte du Map précédent.
On pourra revenir à la définition d’un opérateur avec les élèves et leur demander de coder les opérateurs min, et max.
Puis rechercher le minimum ou le maximum d’une liste en utilisant Combine et l’opérateur a min b ou a max b.
On travaille sur le fond des mathématiques.
Lorsque l’on commence à raisonner en termes de Appliquer/Extraire/Combiner (Map/Keep/Combine), on ne pense plus que comme cela. On ne revient plus jamais aux algorithmes de type séquentiels et on découvre des manières vraiment très élégantes de coder les algorithmes, ces manières étant du pur raisonnement fonctionnel, toujours !
Cela est parfois bien sûr très difficile mais cela en vaut le détour ! Plus nos élèves apprendront tôt à raisonner en ces termes, plus ce sera ancré dans leur mode de pensée : raisonner en fonctionnel ! Je suis intimement persuadée qu’en leur montrant ce raisonnement très tôt au collège, ils auront moins de mal que nous [98] par la suite à coder des algorithmes plus délicats.
Map/Keep/Combine expliqué aux élèves de NSI [99]
La récursivité est au coeur de la programmation fonctionnelle.
Map, Keep, Combine sont des fonctions d’ordre supérieur récursives. [100]
La multiplication dans Snap! comme opérateur d’ordre supérieur
Demandons donc aux élèves pour commencer de coder les opérateurs de base comme étant des opérateurs d’ordre supérieur, comme dans Snap!.
Si nous voulons coder cet opérateur en Python, passons par Snap! au préalable pour écrire ce script opérateur d’ordre supérieur multiplier x_ par y_ dans lequel x_ et y_ sont des listes :
Ainsi, la liste des entiers de 1 à 10 multipliée par la liste des entiers de 2 à 3 donne :
D’où le code Python : [101].
- def multiplier(x_, y_):
- if x_ == [] or y_ == []:
- return []
- return [x_[0]*y_[0]] + multiplier(x_[1:],y_[1:])
- multiplier([1,2,3,4],[2,4]) # renvoie [2, 8]
Proposition de codage des blocs Map, Keep, Combine
On pourrait donc ensuite demander aux élèves de NSI de coder les blocs Map, Keep, Combine avec des fonctions récursives, à condition qu’ils soient déjà aguerris aux manipulations de listes. [102]
– La fonction Map
En Python, cela donne : [103]
- def map_(func, data):
- if data == []:
- return data
- return [func(data[0])] + map_(func,data[1:])
- map_(lambda x: x*x, [1,2,3,4,5]) # renvoie [1, 4, 9, 16, 25]
– La fonction Keep
Code Python proposé pour redéfinir la fonction filter : [104].
- def filter_(pred, data):
- if data == []:
- return data
- if pred(data[0]):
- return [data[0]] + filter_(pred,data[1:])
- else:
- return filter_(pred,data[1:])
- filter_(lambda x: x % 2 == 0, [1,2,3,4,5]) # renvoie [2, 4]
- filter_(lambda x: x % 2 == 0, entiers_1_a_n(100)) # renvoie les entiers pairs compris entre 1 et 100.
– La fonction Combine
Code Python proposé pour Reduce :
- def reduce_(operateur,data):
- if data [1:] == []:
- return data[0]
- return operateur(data[0], reduce_(operateur,data[1:]))
- reduce_(lambda x,y: x+y, [1,2,3,4,5]) # renvoie 15
Algorithmes de tri au programme de NSI : tri par insertion, tri par sélection
Les algorithmes de tri sont des exemples d’algorithmes qui font appel à deux notions profondes : ils font appel à la fois à la récursivité et aux fonctions d’ordre supérieur.
Je conseille à vos élèves l’excellente application Algorithms Explained and Animated sur téléphone du chercheur japonais Moriteru Ishida.
Ils y trouveront des animations très claires des algorithmes de tri suivants : Bubble sort, Selection Sort, Insertion Sort, Heap Sort, Merge Sort, Quicksort. D’autres nombreux algorithmes de Computer Science y sont aussi expliqués.
Les tris par sélection et par insertion ont été proposés dans les programmes de NSI de Première. Je vous propose ci-dessous des versions récursives de ces deux algorithmes de tri.
– Script Tri par sélection
– Script Tri par insertion
Où le script Insère valeur dans liste déjà triée est :
Si alpha est la liste [5,9,7,10,4,3,6,10,1,2], la liste triée donne :
Le tri fusion a été proposé dans les programmes de NSI de Terminale comme exemple d’algorithme de tris pour illustrer la méthode « diviser pour régner ». Ce tri fusion est un algorithme récursif qui se prête particulièrement aux listes chaînées.
Vous trouverez le tri fusion (merge) dans les algorithmes de tri proposés par Brian Harvey dans ce projet Snap!.
Le lutin Listes du projet Snap! lié à cet article est consacré aux algorithmes de Tri.
Conclusion
Pour terminer, je pense qu’il est très important de mettre les élèves dès le début du collège devant une programmation fonctionnelle visuelle grâce à Snap! utilisant le trio Map/Keep/Combine. En effet, persister à ne faire que de la programmation séquentielle avec les élèves risque de les enfermer dans un schéma de pensée dont ils auront un mal fou à se débarrasser.
Les façons de penser finissent par devenir des automatismes. Si vous avez l’habitude de programmer avec des boucles, il devient plus difficile de développer l’aptitude d’écrire des algorithmes en utilisant des fonctions d’ordre supérieur. Mais vos élèves n’ont pas encore cet automatisme d’utiliser des boucles, donc si vous leur enseignez les fonctions d’ordre supérieur très tôt, ils trouveront leur utilisation naturelle. [105]
Par ailleurs, si vous avez quelques élèves qui programment en Python depuis qu’ils ont 11 ans, ils risquent d’être surpris par vos méthodes et vous demander pourquoi vous ne codez pas des boucles comme tout le monde (itératif vs fonctionnel...). Dites-leur simplement que c’est à eux de décider s’ils sont prêts à apprendre quelque chose de nouveau dans votre classe ou s’ils veulent programmer à 30 ans de la même façon qu’à 11 ans. [106]
Je pense qu’il est important de comprendre que ce mode de programmation permis grâce à Map/Keep/Combine (Map/Filter/Reduce) est abordable avec des exemples simples très tôt dans un cursus d’apprentissage des algorithmes mathématiques.
Nous allons ainsi aider nos élèves à placer au centre des résolutions de problèmes l’essentiel en mathématique : la notion de fonction. Nous allons ainsi les aider à mieux comprendre l’essence des mathématiques, et à être moins bloqués par cet apprentissage.
Le mot de la fin.
Avez-vous remarqué qu’il n’y a pas une seule boucle dans les scripts de cet article ? ...
PostScriptum
* Le lecteur vigilant aura certainement pris note du mélange de l’anglais et du français dans l’écriture des scripts. Lorsque je code, je raisonne en fait dans les deux langues et vous livre ici le résultat de mes réflexions. L’uniformisation de tous les scripts serait un travail à finaliser même s’il n’est pas essentiel.
De nombreuses langues sont supportées dans Snap!. Si la vôtre n’y est pas, ou si les traductions de certains scripts viennent à manquer, il est possible de contribuer au projet Snap! sur Github et d’y proposer une traduction.
* Pour information aux lecteurs, tout ce qui est contenu dans cet article est délivré sous licence Creative Commons BY-NC-SA [107]. Cette licence s’applique également aux projets Snap! vers lesquels cet article pointe.
* Mon identifiant sur https://snap.berkeley.edu/ est nathalierun. Vous trouverez sur ma page publique les quelques projets que j’ai déjà partagés.
Remerciements
Je remercie chaleureusement :
* Brian Harvey passionné - comme Seymour Papert - de l’Éducation Mathématique des enfants par les ordinateurs, enseignant en Computer Science [108], pour ses critiques sans complaisance sur le fond du sujet.
* Mon ami Yves Martin pour ses conseils avisés tant sur le fond que sur la forme de cet article. Avec Yves, nous faisions partie de l’association AbraCAdaBRI comprenant 5 félés du logiciel Cabri et Géomètre, un des premiers logiciels de géométrie dynamique. Cette association avait été créée par Éric Hakhenholz dans le but de publier la revue AbraCAdaBRI papier diffusée à environ 200 exemplaires pendant 2 ans. Cette revue papier fut une aventure extraordinaire. Éric a eu la bonne idée de la remettre en ligne sur dgpad.net. [109]
Spéciale dédicace
Je dédie ce travail à mes enfants et à mes petits-enfants. Mais bien évidemment aussi à Mes Élèves et à tous les élèves que je n’aurai pas.
Annexe
Annexe de Géométrie
Dans l’onglet suivant, j’expose une première piste - qui fonctionne - que j’avais explorée pour coder en langage Snap! le problème de Fermat.
Juste pour montrer à quel point adopter une structure de données appropriée pour la mise en oeuvre d’un algorithme est aussi important que l’algorithme lui-même.
Le problème de Fermat
Voici la première démarche détaillée que j’ai suivie :
– Créer une liste Points_du_Plan qui contient les coordonnées des points de la fenêtre graphique de Snap! dans sa résolution d’origine 480 x 360.
Points_du_Plan = [ [ [-240,-180],[-239,-180], ..., [239,-180],[240,-180] ] , [ [-240,-179],[-239,-179], ..., [239,-179],[240,-179] ] , ... , [ [-240,180],[-239,180], ..., [239,180],[240,180] ] ] [110] [111]
Grâce à ce script :
– On crée alors une liste des distances $MA+MB+MC$ pour M décrivant Points_du_Plan. On obtient un tableau de même taille que le précédent.
Grâce à ce script :
– Un Combine sur chaque ligne avec l’opérateur min( , ) permet d’écrire un premier script Help distance_de_Fermat qui renvoie la liste des distances minimum pour chaque y.
– La distance de Fermat s’obtient alors en effectuant un Combine sur cette dernière liste avec l’opérateur min( , ) avec ce script :
Que l’on appelle comme ceci :
Mais nous n’avons pas encore les coordonnées du point de Fermat-Toricelli.
Nous devons donc appliquer le principe du gecko deux fois de suite afin de récupérer les deux index correspondant à la distance de Fermat dans le tableau des distances. [112]
- une première fois avec un Keep sur le tableau des distances pour récupérer l’index id_yT de l’ordonnée $y_T$ du point qui réalise cette distance minimum.
- un second Keep permet de récupérer l’index id_xT de l’abscisse $x_T$.
On a alors T(id_xT - 241, id_yT - 181)).
J’ai aussi décidé de montrer cette première approche [113] car au niveau du temps de calcul, elle ne me semble pas si mauvaise que cela. En effet, cette approche agit récursivement sur de plus petites listes que la structure de données exposée dans le corps du problème de Fermat.
J’ai même l’impression qu’elle est plus rapide [114]. Les deux approches fonctionnent.
Table des matières
- Premier tour d’horizon avec Map/Keep/Combine ou Map/Filter/Reduce
- Premiers exemples d’application de fonctions à une liste d’objets avec Map
- Tableau de valeurs d’une fonction
- Obtenir une liste aléatoire de booléens
- Calcul de la puissance n-ième d’une matrice (sans récursivité)
- Appliquer le négatif à un rectangle de pixels colorés
- Exemples de réduction avec Combine
- Somme
- Produit
- Moyenne arithmétique
- Moyenne géométrique
- Moyenne harmonique
- Produit scalaire
- Exemples d’extractions avec Keep
- Qu’est-ce qu’un prédicat ?
- Ce nombre est-il positif ?
- Ce nombre est-il pair ?
- Ce nombre est-il premier ?
- Ce nombre est-il un carré ?
- Ce nombre est-il un cube ?
- Exemples concrets d’extractions avec Keep
- Extraire les nombres positifs d’une liste de nombres
- Extraire les nombres pairs d’une liste de nombres
- Extraire un ensemble de carrés
- Extraire les entiers d’un ensemble de nombres
- Obtenir les classes d’équivalence modulo n
- La notion de Fonction au centre de l’apprentissage des Mathématiques
- La puissance des listes conjuguée à une pensée fonctionnelle
- De la décomposition canonique d’une application à une décomposition de type Map/Filter/Reduce
- Exemples progressifs niveau lycée
- Second degré
- Combinaisons de k éléments d’un ensemble à n éléments
- Somme des (k parmi n) = 2ⁿ
- Maximum, minimum, quartiles, médiane
- Tirages de cartes, Jets de dés
- Graphes aléatoires
- ToDo list
- Un peu d’arithmétique
- Diviseurs de n
- Nombres premiers, Crible d’Ératosthène
- Fonction Phi d’Euler
- Test de primalité de Fermat
- ToDo list
- Calculs sur les suites
- Somme, produit, suite de Fibonacci, suite de Syracuse
- Somme des termes d’une suite
- Produit des termes d’une suite
- Suite de Fibonacci
- Suite de Syracuse
- Suite ((1 + 1/n )ⁿ)
- Applications : Recherche de valeurs approchées
- Constante d’Apéry
- Encadrement de e
- Approximation de π par Ramanujan
- ToDo List
- Et en géométrie ?
- Le problème de Fermat
- Barycentre d’une liste de points
- Transformations géométriques
- Courbes algébriques
- Variations autour de la lemniscate de Bernouilli
- ToDo List
- De l’intérêt du Map/Keep/Combine
- Travail sur les listes
- Tous les index d’un item dans une liste
- Renverser une liste
- Insérer un élément
- Secouer les éléments d’une liste (shuffle)
- Concaténation
- ToDo list
- Efficacité du trio Map/Filter/Reduce en programmation
- Comment le présenter aux élèves en cours de mathématiques ?
- Appliquer/Extraire/Combiner
- Appliquer/Extraire (Map/Filter ou Map/Keep)
- Appliquer/Combiner (Map/Reduce ou Map/Combine)
- Extraire/Combiner (Filter/Reduce ou Keep/Combine)
- Mixer Appliquer/Extraire/Combiner (Map/Filter/Reduce ou Map/Keep/Combine)
- Map/Keep/Combine expliqué aux élèves de NSI
- La multiplication dans Snap! comme opérateur d’ordre supérieur
- Proposition de codage des blocs Map, Keep, Combine
- Algorithmes de tri au programme de NSI : tri par insertion, tri par sélection, mais d’autres encore
- Annexe
- Annexe de géométrie
- Le problème de Fermat
- PostScriptum
- Remerciements
Cet article a été coédité avec le site de l’IREM de La Réunion, sur lequel il a été publié sous le titre Le trio Map/Keep/Combine au coeur de la notion de fonction. [115]