L’algorithmique revisitée avec Snap! et Python

Des algorithmes aux fonctions
lundi 14 janvier 2019
par  Nathalie CARRIÉ

L’article Initiation à l’algorithmique avec Scratch et Algobox a été revisité afin de mettre l’accent sur la notion universelle de fonction en mathématiques, grâce à l’utilisation du langage de programmation visuelle Snap! qui permet de créer ses propres blocs. Les notions d’entrées-sorties ne sont pas abordées car elles ne relèvent pas de la pensée algorithmique.
Autant se consacrer à l’essentiel : la compréhension des algorithmes.
Tous les algorithmes sont illustrés à l’aide d’un programme Python.

En revisitant cet article Initiation à l’algorithmique avec Scratch et Algobox, Exemples de base, écrit en septembre 2009, je souhaite montrer aux élèves comment mettre l’accent sur la notion universelle de fonction en mathématiques. J’ai donc distribué un devoir d’algorithmique à mes élèves de première S et première STMG. Ce devoir présente des algorithmes de base illustrant les notions essentielles d’algorithmique que les élèves rencontreront en mathématiques au cours de leurs années lycée.
 [1]
Depuis cette rentrée scolaire 2018-2019, j’essaye de montrer aux élèves dans la mesure du possible à quel point la compréhension des algorithmes peut les aider dans leur compréhension des mathématiques. J’aborde toute chose sous l’angle des fonctions (voir cet article : « Tout est algorithme, tout est fonction » [2]). En expliquant simplement qu’une fonction, c’est une boîte dans laquelle on entre des objets (nombres, listes d’objets...), et de laquelle ne ressort qu’un unique résultat.

Le devoir d’algorithmique consistait à réécrire les algorithmes d’un devoir d’algorithmique préparé avec le logiciel AlgoBox dans Snap! [3], devoir originel que vous trouverez dans le Port-Folio au bas de cet article.
Il s’agissait ensuite de transformer chaque algorithme en fonction, cela en créant le bloc correspondant dans le logiciel Snap!. Les élèves devaient également écrire un petit commentaire expliquant l’objet de chaque algorithme.
19 algorithmes au total étaient à réécrire sous forme de fonction. [4]

L’utilisation de Snap! permet bien sûr d’assurer la transition entre Scratch que les élèves ont étudié au collège et le langage Python qui est demandé au lycée depuis la rentrée dernière. Mais l’utilisation de Snap! permet bien plus que cela. Il permet d’asseoir la notion de fonction (tant en mathématiques, qu’en informatique) dans l’esprit des élèves.
L’écriture des fonctions en langage Python en devient plus immédiat, plus limpide. Et les élèves, avec leur calculatrice NumWorks [5] écriront à la rentrée [6] les fonctions du devoir en Python.

Ce passage des algorithmes aux fonctions, que ce soit avec Snap! ou avec Python, permet d’épurer chaque algorithme, d’orienter les élèves vers l’essentiel, de ne pas les perdre notamment dans des gestions d’entrées-sorties...


Algorithmique : Les instructions élémentaires

- Déclaration des variables
La plupart des langages de programmation nécessite une phase de déclaration des variables, donc il serait bien d’énumérer avec les élèves la liste des variables dont ils peuvent avoir besoin dans un algorithme.
Voici quelques types de données que les élèves pourront rencontrer :

    1. la variable est du type Nombre
    2. la variable est du type Chaîne de caractères
    3. la variable est du type liste de (nombres/chaînes de caractères)
    4. la variable est du type booléen (un booléen ne prend que 2 valeurs : vrai ou faux)

- Affectation
Il s’agit de faire comprendre aux élèves qu’une variable, c’est comme le tiroir d’une commode. Ce tiroir comporte une étiquette (le nom de la variable) ; on y range des objets : le contenu de la variable (par exemple un nombre, une liste de nombres).
Afin de donner aux élèves de bonnes habitudes, ce serait bien de leur faire initialiser leurs variables systématiquement.
Ce petit algorithme permet d’échanger le contenu des variables a et b.

Échange avec utilisation d’une variable temporaire

a ← 2
b ← 3
c ← a
a ← b
b ← c

- Calcul
Des calculs sont effectués à partir des variables d’entrée, comme par exemple :

Échange sans utilisation d’une variable temporaire

a ← 2
b ← 3
a ← a + b
b ← a - b
a ← a - b

- Entrées / Sorties
Si les variables n’ont pas été initialisées dans l’algorithme, on pourra les lire au clavier par exemple. Une variable doit être affichée pour en connaître le contenu.

Lire a
Lire b
a ← a + b
b ← a - b
a ← a - b
Afficher a, b

Blocs de contrôle : Boucle et itérateur, instruction conditionnelle

- Calcul itératif Pour ... De ... A ...

Lorsque le nombre de boucles est connu, il s’agit d’effecteur un calcul itératif.

n ← 100
Pour i allant de 1 à n
   action1
   action2
    ...
Fin Pour

Les actions sont effectuées ici 100 fois, le compteur i étant incrémenté (i ← i + 1) à chaque exécution de la boucle.



- Instruction conditionnelle Si ... Alors ... ( Sinon ... )

Si une condition a une valeur logique vraie, on effectue une ou plusieurs actions.

Si condition vraie Alors
   action1
   action2
   ...
FinSi
Si condition vraie Alors
   action1
   action2
   ...
Sinon
   action1b
   action2b
   ...
FinSi



- Calcul itératif avec fin de boucle conditionnelle Tant Que ... Faire ... ou Faire ... Jusqu’à ...

Le calcul itératif va être exécuté tant qu’une condition a une valeur logique vraie ou le calcul itératif va être arrêté lorsque la condition a une valeur logique vraie.

Boucle Tant que Boucle Répéter... Jusqu’à
Tant Que condition vraie Faire
   action1
   action2
   ...
Fin Tant Que
Répéter
   action1
   action2
   ...
Jusqu'à condition vraie
Fin Répéter

Devoir d’algorithmique

En classe, depuis cette année, j’écris tous mes algorithmes avec Snap!.
En effet, j’ai pu créer mes propres blocs Snap! [7] spécifiques à l’écriture des algorithmes (ils sont donnés au bas de cet article), de sorte à obtenir mon propre IDE [8] idéal à l’enseignement de l’algorithmique en classe. Une bibliothèque spécifique à l’écriture des algorithmes en français sera prochainement intégrée aux librairies additionnelles de Snap!.

Voici le devoir entièrement réécrit avec Snap! :

Devoir d’algorithmique, page 1 Devoir d’algorithmique, page 2
PNG

- Variables

9 algorithmes sont proposés dans le devoir pour illustrer la notion de variables.

Algorithme 1

L’algorithme proposé fonction correspondante
algorithme 1 fonction 1
appel à la fonction
Code Python appel à la fonction
  1.  def algo1(x,y):
  2.     return x+y
  1.  algo1(2,3)

Déplier tous les blocs
Replier tous les blocs

Algorithme 2

L’algorithme proposé fonction correspondante
algorithme 2 fonction 2
appel à la fonction
Code Python appel à la fonction
  1.  def algo2(x):
  2.     return x+1
  1.  algo2(2)

Algorithme 3

L’algorithme proposé fonction correspondante
algorithme 3 fonction 3
appel à la fonction
Code Python appel à la fonction
  1.  def algo3(x):
  2.     return 4*(x+1)
  1.  algo3(2)

Algorithme 4

L’algorithme proposé fonction correspondante
algorithme 4 fonction 4
appel à la fonction
Code Python appel à la fonction
  1.  def algo4(x):
  2.     return -3*(x-2)-4
  1. from random import randint
  2.  
  3. algo4(randint(1,10))

Algorithme 5

L’algorithme proposé fonction correspondante
algorithme 5 fonction 5
appel à la fonction
Code Python appel à la fonction
  1.  def algo5(x):
  2.     return -3*x+2
  1. from random import randint
  2.  
  3. algo5(randint(1,10))


ce qui donne dans un terminal :

Quel a été le nombre tiré au hasard ?

Algorithme 6

L’algorithme proposé fonction correspondante
algorithme 6 fonction 6

variante efficace
appel à la fonction
Code Python appel à la fonction définition d’une fonction
Python épurée...
  1.  def algo6(A,B):
  2.     return [A+B,B+A]
  1.  algo6(5,3)
  1.  def algo6(A,B):
  2.     return [A+B,A+B]

Remarque importante : Cet algorithme est l’occasion d’insister sur l’ordre des instructions dans un algorithme. [9]

Algorithme 7

L’algorithme proposé fonction correspondante
algorithme 7 fonction 7
appel à la fonction
Code Python appel à la fonction
  1.  def algo7(prixenfrancs):
  2.     return prixenfrancs/6.55957
  1.  algo7(100)

Algorithme 8

L’algorithme proposé fonction correspondante
algorithme 8 fonction 8
appel à la fonction
Code Python appel à la fonction
  1.  def algo8(largeur,longueur):
  2.     return largeur*longueur
  1.  algo8(20,30)

Algorithme 9

L’algorithme proposé fonction correspondante
algorithme 9 fonction 9

Le script de la fonction algo9
appel à la fonction
On peut alors appliquer l’algorithme 9 - qui n’est autre que la fonction racine carré - aux nombres d’une liste
Code Python appel à la fonction
  1.  
  2. from math import sqrt
  3.  
  4. def algo9(x):
  5.     return sqrt(x)
  1. algo9(2)
  2. liste = [1,2,3,4]
  3. map(algo9, liste)


ce qui donne dans le terminal :



- Boucles de niveau I

3 algorithmes sont donnés dans le devoir pour illustrer la notion de boucles dont le nombre d’itérations est connu à l’avance.

Algorithme 10

L’algorithme proposé fonction correspondante
algorithme 10 fonction 10
variante efficace
appel à la fonction
Code Python appel à la fonction
  1. from math import sqrt
  2. def algo10(n_min,n_max):
  3.     a = []
  4.     for n in range(n_min,n_max):
  5.         a.append(sqrt(n))
  6.     return a  
  1. algo10(1,50)

Algorithme 11

L’algorithme proposé fonction correspondante
algorithme 11 fonction 11
variante efficace
appel à la fonction
Code Python appel à la fonction
  1. def algo11(n_min,n_max):
  2.     a = []
  3.     for n in range(n_min,n_max):
  4.         a.append(8*n)
  5.     return a  
  1.  algo11(1,10)

Algorithme 12

L’algorithme proposé fonction correspondante
algorithme 12 fonction 12
appel à la fonction
Cette somme des inverses des entiers naturels de 1 à 10
peut se calculer très simplement avec la combinaison des 2 fonctions Appliquer/Combiner (map/reduce)
et une variante efficace pour la fonction 12 se trouve donc être
Code Python appel à la fonction
  1.  def algo12(n_min,n_max):
  2.     somme = 0
  3.     for n in range(n_min,n_max):
  4.         somme = somme +1./n
  5.     return somme
  1.  algo12(1,10)

- Conditions

4 algorithmes illustrent la notion d’instructions conditionnelles.

Algorithme 13

L’algorithme proposé fonction correspondante
algorithme 13 fonction 13
Ce qui donne l’occasion de programmer un booléen
appel à la fonction
Code Python appel à la fonction
  1. from math import sqrt
  2. def algo13(x):
  3.     if (x > 0 or x == 0):
  4.         return sqrt(x)
  1.  algo13(3)

 [10]

Algorithme 14

L’algorithme proposé fonction correspondante
algorithme 14 fonction 14
appel à la fonction
Code Python appel à la fonction
  1. def algo14(x,y):
  2.     if x > y:
  3.         return x
  4.     else:
  5.         return y
  1. from random import randint
  2. algo14(randint(1,10),3)

Algorithme 15

L’algorithme proposé fonction correspondante
algorithme 15 fonction 15
appel à la fonction
Code Python appel à la fonction
  1. def algo15(A,B):
  2.     if A > 0:
  3.         A = A + 1
  4.     if B > 4:
  5.         B = B - 1
  6.     return [A,B]
  1.  algo15(1,3)

Algorithme 16

L’algorithme proposé fonction correspondante
algorithme 16 fonction 16
appel à la fonction
Code Python appel à la fonction
  1. def algo16(x):
  2.     if !(x==1):
  3.         return 1/(x-1)
  1. from random import randint
  2. algo16(randint(1,10))

 [11]


- Boucles de niveau II

3 algorithmes sont donnés dans le devoir pour illustrer la notion de boucles qui seront exécutées à l’aide de la réalisation d’une certaine condition.

Algorithme 17

L’algorithme proposé fonction correspondante
algorithme 17 fonction 17
La condition peut évidemment s’écrire : ou
appel à la fonction
> 2500-22*110 = 80
Code Python appel à la fonction
  1.  
  2. def algo17(montant):
  3.     while montant >= 110:
  4.         montant = montant-110
  5.     return montant
  1. # le montant doit être supérieur ou égal à 110
  2. # afin que la boucle soit exécutée au moins une fois.
  3.  algo17(2500)

Algorithme 18

L’algorithme proposé fonction correspondante
algorithme 18 fonction 18
appel à la fonction
Cette fonction renvoie le premier entier naturel N à partir duquel 2^N ≥ 10 000
Vérification
Code Python appel à la fonction
  1.  
  2. def algo18():
  3.     N = 1
  4.     while 2**N < 10000:
  5.         N = N + 1
  6.     return N
  1. #
  2.  algo18()

Tiens ! Une fonction sans entrée(s). On peut alors décider de paramétrer le nombre 10000 à l’aide d’un passage par argument de cette valeur et de placer le nombre 10000 dans un tiroir qui s’appellera nombre par exemple.

Code Python appel à la fonction
  1.  
  2. def algo18(nombre):
  3.     N = 1
  4.     while 2**N < nombre:
  5.         N = N + 1
  6.     return N
  1. # on passe alors le nombre 10000 en argument à la fonction.
  2. algo18(10000)
  3. # La fonction renvoie 14
  4. # (le premier entier naturel N à partir duquel 2^N ≥ 10 000)
  5. # ce qui permet de relancer l'appel à la fonction
  6. # avec une nouvelle valeur si besoin :
  7. algo18(500000)
  8. # La fonction renvoie maintenant 19
  9. # (le premier entier naturel N à partir duquel 2^N ≥ 500 000)

Algorithme 19

L’algorithme proposé fonction correspondante
algorithme 19 fonction 19
on peut aussi envisager
un retour plus détaillé de la fonction
appel à la fonction
Cette fonction renvoie le nombre de rebonds nécessaires à la balle pour passer en dessous de la hauteur 100.
Code Python appel à la fonction
  1. def algo19(hauteur):
  2.     nombre_rebonds = 0
  3.     while hauteur > 100:
  4.         nombre_rebonds = nombre_rebonds + 1
  5.         hauteur = 0.9 * hauteur
  6.     return nombre_rebonds
  1.  algo19(300)
  2. # la fonction algo19 renvoie
  3. # le nombre de rebonds nécessaires
  4. # à la balle
  5. # pour passer de la hauteur initiale
  6. # de 300
  7. # en dessous de la hauteur 100.

Blocs spécifiques Snap! pour écrire les algorithmes demandés

- Script pour la flèche d’affectation

La boucle Pour i allant (...)

La boucle Pour i allant de 1 à n
On la trouve dans la librairie Tools à précharger avant Snap! 5, et est intégrée par défaut à Snap! 5.

un programme Snap! pour la boucle Tant que

On utilise la boucle Répéter ... Jusqu’à ... déjà présente par défaut dans les blocs de contrôle pour créer ce bloc.

Les fonctions : corrigé du devoir d’algorithmique

Vous trouverez la totalité des blocs présentés dans cet article sur le cloud de Snap! Berkeley.
https://snap.berkeley.edu/snapsource/snap.html#present:Username=nathalierun&ProjectName=2018-12-27-Algorithmique.Solution

5 lutins y sont présents, ils correspondent aux différentes parties du devoir :
- le lutin Variables
- le lutin Boucles1
- le lutin Conditions
- le lutin Boucles2
- le lutin algorithmique

Quelques indications sur le barême que j’ai appliqué à ce devoir numérique :
- 0.5 par script transcris correctement
- 0.5 par fonction correcte
- 0.25 pour toute explication correcte du but de l’algorithme, écrite sous forme de commentaire.
1 point pour la présentation générale des résultats (4 lutins).
Avec 19 algorithmes, cela fait bien un barême sur 20 (le total étant tronqué à 20).
Ce barême garantit quasiment la moyenne pour chaque élève qui a rendu son devoir. Je pratique en général une évaluation positive et essaye toujours d’encourager les élèves qui ont rendu quelque chose, pour avoir au moins essayé. Le devoir était globalement assez difficile, mais il m’a permis de voir si les élèves avaient bien compris les algorithmes écrits et les notions de boîte pour les fonctions. Ils ont dû nécessairement distinguer quelles étaient les entrées données à la boîte, et quel était le résultat qui devait en sortir.

Le devoir était obligatoire en première S ( à rendre avant les vacances de l’été austral ) ; et facultatif en première STMG ( à rendre à la rentrée).
Pour la classe de première S, le coefficient appliqué à ce devoir est 4. Je donne aussi régulièrement des devoirs [Wims] à faire en ligne (coefficient 1), des interrogations surprises coefficient 2, et des devoirs sur table (prévenus) coefficient 4, mais encore des projets à faire à la maison qui demandent un lourd investissement personnel comme un devoir sur la fractale de Von Koch (qui comporte de l’algorithmique, des calculs et des dessins papier). Ce dernier est compté coefficient 4.

Quelques remarques de correction :
Dans les erreurs trouvées dans les copies numériques, les plus intéressantes sont :
- Beaucoup de confusion entre les arguments d’entrée et ceux de sortie. Ainsi, les arguments d’entrée sont x, y, z pour l’algorithme 4, alors que seul x est un argument à entrer dans la fonction, y et z sont issus de calcul et seul z est à retourner.
- une élève a codé « rapporter » au lieu de « afficher » dans le script Snap!
- ceci n’est pas une erreur, bien au contraire. Depuis que les élèves connaissent la fonction Snap! « Appliquer » (« Mapper »), ils ne font plus de boucle... car ils ont bien compris que c’est tellement plus direct, tellement plus efficace !


Se former à Snap!

- On pourra suivre ce MOOC de formation à Snap! sur openSAP.

- S’abonner au compte Twitter de Jens Möenig, le développeur principal de Snap!, vous permettra d’être au courant des principales modifications apportées à Snap!.

- La chaîne Youtube de Jens Möenig présente quelques tutoriaux essentiels pour utiliser Snap!.

 [12]


D’autres articles sont consacrés à Snap! sur ce site, faisant l’apologie des algorithmes et des fonctions :

- Programmer des algorithmes avec Snap! ou la programmation visuelle au lycée
- L’héritage des Micromondes LOGO : programmation fonctionnelle au collège avec Snap!, article qui explique pourquoi passer de Scratch à Snap! pour préparer le brevet en physique chimie au collège.
- Pourquoi faire des fractales en classe ? qui permet de visiter l’algorithmique au travers de la géométrie avec Snap!.
- Rouge, Vert, Bleu, de 0 à 255 pour comprendre le codage des couleurs avec Snap!.
Et enfin cet article de fond [13] :
- Tout est algorithme, tout est fonction qui constitue une première approche d’une pensée fonctionnelle du programme de première scientifique.


[1Cet article, les documents, les images et tous les contenus nathalierun.net et Snap! vers lesquels il mène sont sous license CC BY-NC-SA 3.0 FR.

[2Cet article est le fruit d’une présentation du séminaire 2018-2019 de l’IREM qui devait initialement se dérouler le 28 novembre 2018, reportée au 13 février 2019. L’article sera publié après cette présentation.

[3Je présente Snap! dans cet article Programmer des algorithmes avec Snap! ou la programmation visuelle au lycée écrit en avril 2017.

[4La numérotation des algorithmes est détaillée sur ces 2 images :
- https://nathalierun.net/lycee/piwig...
- https://nathalierun.net/lycee/piwig...

[5une bonne partie de la classe en est équipée, les autres élèves utilisent un terminal Linux ou l’émulateur NumWorks au choix

[6Je rappelle que nous sommes à la Réunion aux vacances de l’été austral ;-)

[7Comme je l’ai déjà expliqué dans des articles précédents, Snap! est un logiciel de programmation visuelle dérivé de Scratch ; son nom initial était BYOB Build Your Own Blocks.

[8IDE : integrated development environment : environnement de développement « intégré ».

[9Ainsi, j’ai relevé dans les copies numériques des élèves les 2 blocs suivants qui conduisent à des résultats erronés.

[10Remarque : je tiens à préciser que l’opérateur de comparaison >= existe en Python par défaut. Le but ici est de faire écrire le bloc qui renvoie ce booléen et surtout qui attirera l’attention des élèves sur la signification mathématique (et la valeur logique d’une phrase comme x>=0) de cet opérateur.

[11Remarque : Bien sûr, on peut remplacer la condition !(x==1) par x !=1 en Python... c’est encore voulu, et à but pédagogique.

[12Ma signature en couleur...D’après ce programme de Jens Mönig :
https://snap.berkeley.edu/snapsourc...
l’explication en vidéo étant ici.

[13Il serait également intéressant, au moins d’un point de vue culturel, de jeter un coup d’oeil sur l’état des lieux de la programmation visuelle avec cet article :
De retour de Scratch2017Bdx, un colloque international sur la programmation visuelle donné à l’occasion des 50 ans de LOGO et des 10 ans de Scratch à Bordeaux en juillet 2017.


Documents joints

Devoir d'algorithmique, page 1
Devoir d'algorithmique, page 2
Première : Travail d'algorithmique, Consignes
Programme de Mathématiques, classe de Première (...)

Portfolio

Travail d'algorithmique originel 1 Travail d'algorithmique originel 2 Travail d'algorithmique, Consignes 1 Travail d'algorithmique, Consignes 2 Travail d'algorithmique, Commentaires faits (...)

Commentaires

Navigation

Articles de la rubrique