samedi, 18 février 2012
http://maths.ac-amiens.fr/097-etude-d-un-algorithme.html
Production académique pour les travaux académiques mutualisés 2009-2010, réalisée par V. Maille.
n étant un entier donné, que fait cet algorithme ?
Classe de terminale S
| 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. si reste (n,a) . reste (n,b) = 0 alors 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 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 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 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 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... Si ce n’est pas le cas, alors la boucle continue. On recommence, en changeant les variables a, b, et k : Or, on a vérifié dans la première boucle que n n’était pas divisible par 2 et 3. 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 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... |
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 :
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.
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.
Quelques exemples de copies d’élèves :
|
|
|
|