Mathématiques

Sommaire

Étude d’un algorithme

Production académique pour les travaux académiques mutualisés 2009-2010, réalisée par V. Maille.

 Objectif

n étant un entier donné, que fait cet algorithme ?

Vous pouvez changer les valeurs de n
et appuyer sur = ou "CRTL + Entrée" pour l’exécuter et conjecturer.

 Niveau

Classe de terminale S

 Modalités

  • Ce scénario a déjà été réalisé d’autres années : une fois en classe, une fois par mail.
    Cette année, l’énoncé est déposé sur le forum de l’ENT Environnement numérique de travail et les élèves ont 15 jours pour faire leurs propositions.
  • Les élèves de l’établissement n’utilisent que depuis cette année cet outil et il faut avouer que les 2 premières semaines se sont écoulées sans qu’aucun message ne vienne lancer le débat.
  • À la séance suivante, j’ai donc emmené les élèves en salle informatique et la consigne était :
    • 1. De se connecter à l’ENT (et oui...)
    • 2. De participer au forum en apportant une contribution.
  • Le faisant ainsi en classe, l’enseignant peut répondre directement et les élèves peuvent échanger entre-eux. Cela a l’avantage de lancer le débat.
    Mais la consigne reste « au fur et à mesure de vos questions, postez les sur le forum, pour garder une trace. On vous demandera une rédaction à la fin de l’activité ».
    L’enseignant répond aux élèves via le forum aussi même si la réponse a été donnée oralement.
  • Cette fois-ci le débat est lancé et les échanges continuent durant la semaine.
  • A la séance suivante, on revient en classe sur 2 ou 3 points, pendant 20 minutes, les questions/réponses sont encore une fois déposées sur le forum.
  • Les élèves doivent rédiger sur copie leur réponse au problème pour la fois suivante, de ce fait quelques questions sont encore posées la semaine suivante.

 Fil de la discussion

Par Vincent MAILLE : Que fait ce programme ?
Pièces jointes : Document algo.html
Voir le fichier joint. Tout est dans le titre !
Modifiez le nombre n avec des valeurs entières et répondez à la question. J’attends vos idées
VM

Par Marie-Astrid : Que fait ce programme ?
J’en sais rien !

Par Stanislas : Premières idées
Bon... apparemment j’inaugure, alors :

Dans un premier temps on initialise les variables (n, p et compagnie...) à leurs valeurs de départ.
Ensuite, on insère une boucle qui ordonne au programme de répéter la partie.

si reste (n,a) . reste (n,b) = 0 alors
 p=1
sinon
 a=6k-1 ; b=6k+1 ;k=k+1
fin

tant que a+p*l est inférieur ou égal à l (=racine de n)...

Cette boucle, parlons-en, il s’agit en fait d’une condition qui en fonction de la valeur du reste de la division de n par a et par b va modifier la valeur de nos variables et par le biais de ces modifications nous permettre de sortir de la boucle et également autre chose que nous allons voir ensuite...

Donc, si le reste de la division de n par a est nul (donc si a|n) ET si b|n aussi, p=1

Dans le cas contraire, on modifie les valeurs de a, b et k conformément à ce qui est écrit dans l’algorithme

Enfin on vérifie si a+p*n est toujours supérieur à l ou non pour savoir si la boucle doit se répéter une nouvelle fois...


Par Vincent MAILLE : Premières idées
Je cite : « Donc, si le reste de la division de n par a est nul (donc si a|n) ET si b|n aussi, p=1 »

Pas si sûr ...... un produit est nul ........

VM


Par Vincent : Premières idées
Exemple pour le premier tour de boucle :

1-On vérifie que a+p*n <= l

 a+p*n
=2+0*324
=0 > l

Cette condition est vraie, on fait donc un tour de boucle

2-On vérifie que a|n et que b|n

324/2 = 162, reste 0
324/3 = 108, reste 0

Cette condition est donc vraie, donc p = 1.

3-A la fin de la boucle on revérifie si a+p*n <= 0 pour savoir si on repart pour un tour de boucle

 a+p*n
=2+1*324
=972 > l (comme l = 18)

Cette condition est fausse, par conséquent on sort de la boucle.

Là, on tombe sur une nouvelle condition qui vérifie si p=1, or dans la boucle justement on avait mis la valeur de p à 1. Par conséquent le programme indique non et se termine.


Par Vincent MAILLE : Premières idées
En effet, justement on peut se demander parmi les variables a, b, k, n, p, l, quelles sont celles qui varient et quelles sont celles qui sont fixes tout au long du programme .... mais ça ne dit toujours pas à quoi sert ce programme......La seule variable à modifier est n pour commencer. Entrez différentes valeurs, et regardez la réponse affichée pour faire une conjecture.

VM


Par Marie-Astrid :
Bon si j’ai bien compris que n et l varient.

et p=0, a=2, k=1 sont 3 constantes.

pourtant, si a|n OU si b|n

or reste(n, a)*reste(n, b)=0

alors p=1 <---- alors qu’au début j’ai dit que p constante (p=0) du coup I’m lost :s

bon avec le temps je comprendrais bien un petit truc au moins un petit.


Par Vincent MAILLE : A propos du nombre p
p vaut 0 au début en effet, et dès que reste(n, a)*reste(n, b) c’est à dire comme tu l’expliques dès que a|n ou b|n alors p vaut 1.... Que dire alors de la condition a+p.n≤l si p vaut 1 ?...On avance mine de rien. Donc, dès que l’on trouve un diviseur parmi les valeurs possibles de a et b, p vaut 1, mais a et b peuvent-ils prendre toutes les valeurs jusqu’à racine(n) ?

Autre remarque : En fait n peut être modifié au moment du lancement, mais une fois le programme lancé, n et l ne changent plus, seuls a, b, k et p sont modifiés au cours du programme.


Par Morgan : Conjecture
Cela a un rapport avec les nombres premiers
Si n est un nombre premier alors "Oui" sinon "Non"

Par Vincent MAILLE : Conjecture
Ah......enfin une conjecture......qui ne semble pas fausse a priori.....Il n’y a plus qu’à démontrer !

Par Stanislas : Avancement pour nos ami(e)s allemands
Donc si p=0 l’inégalité est vraie, donc la boucle continue.
En revanche si on change la valeur de p (p=1) car p ne peut valloir que 0 et 1, alors la boucle est "rompue".
Si n est premier le programme affiche OUI, en revanche si n n’est pas premier le programme affiche NON.

Par Vincent MAILLE : Premières idées
Oui, si p=0, la boucle continue...jusqu’à un certain point quand même, car il faut voir que les valeurs de a et b vont augmenter à chaque tour.
Si p vaut 1, en effet la quantité a+p*n>=n et donc on sort de la boucle et on affiche "non".
Reste donc à prouver que n premier <=> p=0

Par Vincent : La boucle
On voit que la boucle continue tant que a+p*n <= l et on voit également que cette boucle donne pour ordre d’incrémenter k de 1 et de faire comme autres opérations a=6k-1 et b = 6k+1...
En faisant un tableau, on dirait que celui ci regroupe tous les nombres premiers, ce qui laisse a supposer que tous les nombres premiers s’écrivent sous la forme 6n+1 ou 6n-1... Cela reste a prouver.

Par Vincent MAILLE : La boucle
N’y a-t-il que des nombres premiers ?

Par Stanislas : La boucle
On constate donc qu’il n’y a pas que les nombres premiers. Il semblerait que tout les nombres que l’on a besoin sont présents avec k=k+1 ; a=6k-1 ; b=6k+1
Il vaut mieux en avoir plus que pas assez !!!

Par Morgan : La boucle
J’en ai marre je comprends pas =’(

Par Vincent MAILLE : La boucle
La propriété à montrer est donc :
Si p est un nombre premier plus grand ou égal à 5, alors p=1 [6] ou p=-1[6] Et que dirait la forme contraposée ?

Par Marie-Astrid : La boucle
Si p<>1 [6] ou p<>-1[6] alors p n’est pas un nombre premier ou p est plus petit strictement que 5.

Par Nelson : Proposition
Donc, la conjecture précédente est bonne. Le programme affiche "Oui" si le nombre est premier, "Non" s’il ne l’est pas.

Je vais essayer d’expliquer pourquoi, je ne garantis pas le résultat :

Au départ, on demande au programme de vérifier si a + p * n < l
Or, dans la première boucle, p = 0.
Si a < l, alors a + p * n < l, quel que soit n...

Donc, le programme continue :

On lui demande de vérifier si le produit des restes des divisions de n par a et b est nul, ce qui signifierait qu’au moins l’un des deux l’est, et donc que n est divisible soit par a, soit par b.

Si c’est le cas, alors on change la valeur de p en 1, et le programme affiche "Non", car le nombre n n’est pas premier...
On sort également de la boucle, puisque désormais a + p * n > l.

Si ce n’est pas le cas, alors la boucle continue. On recommence, en changeant les variables a, b, et k :
k se voit ajouter une unité, a vaut alors 6k-1, b 6k+1.

Or, on a vérifié dans la première boucle que n n’était pas divisible par 2 et 3.
n ne peut donc s’écrire ni 6m, ni 6m+2 (= 2(3m+1)) , ni 6m+3 (= 3(2m+1)), ni 6m+4 (= 2(3m+2))
Il ne reste que deux possibilités : n s’écrit 6m+1, ou 6m+5 (ce qui, modulo 6, revient à 6m-1).

Ces deux dernières possibilités, nous les testons justement toutes en donnant à a la valeur de 6k-1 et b la valeur de 6k+1, et en augmentant la valeur de k de 1 à chaque boucle.

Si n s’écrit 6m+1 ou 6m-1, nous le saurons donc forcément en calculant à chaque fois le produit des restes des divisions de n par a et b. Si ce produit est nul, alors un des restes est nul, impliquant que n est divisible par a ou b.

Le programme va boucler en cherchant tous les diviseurs possibles de n, de la forme 6m+1 ou 6m-1.
S’il en trouve un, il sortira de la boucle de la même façon que dans la première boucle, et affichera "Non".

S’il n’en trouve pas, il va continuer de tester tous les suivants. Mais il finira par sortir de la boucle, car il arrivera un moment, en augmentant continuellement la valeur de a, que ce dernier devienne supérieur à l, impliquant ainsi que a + p * n > l (car p=0). Et le nombre n n’ayant aucun diviseur autre que 1 et lui-même, il sera premier, et le programme affichera "Oui".

J’ai peut-être oublié des étapes, mais je pense que ça se tient, malgré tout ;p


Par Vincent MAILLE : Proposition
ça semble fonctionner....enfin presque toujours......

Par Stanislas : Cas particulier
Dans ce programme on a pu constater que 2 exceptions étaient présentes : 0 et 1. Le programme affiche "OUI" alors qu’il devrait afficher "NON"

Par Vincent MAILLE : Proposition
Il ne reste plus qu’à rédiger votre démonstration à présent...

 Plus-value ou non de l’ENT

Aspect positif :

Ce problème aux multiples pistes et “rebondissements” trouve tout son intérêt à être traité via un outil tel que le forum :

  • On garde des traces du cheminement des idées.
  • On peut apporter une réponse à chacun lisible par tous.
  • Ceux qui ont moins d’idées peuvent lire l’avancée des autres et l’utiliser pour faire leur propre synthèse.
  • Le professeur peut orienter les questions selon l’avancée de chacun.

Aspect négatif :

On retrouve le problème de saisie de mathématiques sur le forum, bien que pour cet exercice, ce ne soit pas trop handicapant.

 Questions / Réponses

L’utilisation du forum en classe n’a-t-elle pas paru artificielle aux élèves ?

En fait, comme leur première excuse était « j’y suis allé chez moi et ça ne fonctionnait pas ». On l’a commencé en classe, et comme il y avait une suite à faire à la maison, puis à rendre, ils ont été d’accord pour jouer le jeu de poster les messages.

Est-ce que tu as mis l’ensemble de la production ? Beaucoup d’élèves sont-ils venus ?

Oui, Ils sont tous venus, c’est un groupe très réduit d’élèves de terminale S spécialité mathématique du fait qu’il n’y a qu’une terminale S dans mon lycée.

Tu l’as testé les autres années, sous quelle forme l’activité a-t-elle le mieux fonctionné ? Avantages/inconvénients de chaque dispositif.

Par mail c’était bien aussi, même si c’est plus individualiste, de toutes manières les pistes de résolutions circulent rapidement.

Ici avec le forum, on a des réponses que l’on ne donne qu’une fois, quitte à renvoyer sur le bon message si une question revient.
Les élèves doivent alors faire l’effort de relire s’ils veulent faire une synthèse complète.

Au niveau des copies, cela donne quoi ? Plutôt intéressant ou alors simple copie de message.

Les productions ont été vraiment intéressantes (voir copies jointes). Le contenu a vraiment été personnel pour les élèves qui ont joué le jeu.

 Copies d’élèves

Quelques exemples de copies d’élèves :

format PDF - 3 Mio
format PDF - 10 Mio
format PDF - 5 Mio
format PDF - 7.6 Mio
Mise à jour : 18 février 2012