Échange de variables

vendredi 10 septembre 2010
par  Alain BUSSER

L’énoncé est inspiré du livre de Guillaume Connan : Échanger les contenus de deux variables. L’algorithme de Guillaume Connan implémente cet échange sans faire intervenir une troisième variable. Cette contrainte n’était ici pas imposée.

L’énoncé du TP est téléchargeable ici :

PDF - 104.1 ko
le sujet du TP en pdf

En fait aucun élève n’a réussi la première partie du TP (aussi celle-ci n’était-elle pas notée).

L’effet attendu était la création spontanée de l’algorithme suivant :

Mettre 3 dans x
Mettre 8 dans y
Mettre x dans y
Mettre y dans x

C’est bien ce qui s’est passé. Mais les élèves n’ont pas pensé à créer une autre variable que x et y, pour y stocker temporairement les anciennes valeurs afin que celles-ci ne soient pas écrasées par les nouvelles. En effet, si on examine le script en mode pas-à-pas, on constate que le problème vient de la ligne 7, où y écrase x :

Surprenamment, ce phénomène semble très difficile à imaginer par les élèves : Alors que

x prend 3
x prend 8

leur semble simple à comprendre (ils savent qu’à la fin, x=8), dans le cas présent, l’idée qu’on prenne le nombre dans y pour le mettre dans x leur paraît un mouvement (remplacement) et non une copie. L’image des nombres dans les tiroirs n’est donc pas idéale pour décrire un algorithme (quand on transfère le contenu d’un tiroir à un autre tiroir, le premier tiroir est vide !). Dans le cas présent, il s’agit plus d’une copie que d’un transfert. La description des tiroirs a alors été abandonnée pour parler de téléchargement :

Lorsque vous téléchargez un logiciel sur 01net, l’original qui se trouve sur le site 01net est-il modifié ? Disparaît-il ?

Réponse de certains élèves : « Je ne télécharge rien, de peur que ce ne soit pas libre » (humour de lycéen...)

La description de la situation par le remplissage progressif d’un tableau permet de mieux préciser ce qui se passe :

  • Après la ligne 2, on a
x
  • Après la ligne 3, on a
x
y
  • Après la ligne 5, on a
x 3
y
  • Après la ligne 6, on a
x 3
y 8

Mais après la ligne 7, on a

x 8
y 8

Le 3 ayant disparu dans les limbes, on ne peut plus le récupérer !

Le même tableau a facilité le corrigé : Pour peu que l’on pense à créer une troisième variable z, on a

x 3
y 8
z

puis, après avoir mis x dans z :

x 3
y 8
z 3

ce qui permet d’écraser une des occurences du 3 sans perdre ce nombre à tout jamais. La suite de l’algorithme donne successivement

x 8
y 8
z 3

puis par « transfert » (en fait, copie) de z vers y :

x 8
y 3
z 3

ce qui répond à la question.

Aucun élève n’a réussi à trouver cet algorithme, sauf un, qui avait utilisé deux variables (en JavaScript, un problème technique ayant fait renoncer à AlgoBox) :

var x=3;
var y=8;
var a=y;
var b=x;
x=a;
y=b;
Println(x);
Println(y);

Seulement, à force de tâtonner dans tous les sens, cet élève a oublié le script ci-dessus, et a recréé de mémoire la version incomplète ci-dessous :

Les autres élèves ont opté pour des tentatives plus compliquées, parce que reposant sur des opérations et non des simples copies. Exemple typique :


La deuxième partie du TP, la seule qui était notée, était de la programmation : Traduire en JavaScript (pour la raison technique évoquée ci-dessus) l’algorithme de l’énoncé, puis le tester. L’erreur la plus fréquente a été l’oubli du signe de multiplication :

On remarquera à cet effet la richesse de l’affichage des erreurs de syntaxe par Rhino (moteur JavaScript), qui, s’il n’indique pas exactement la cause de l’erreur [1], met en exergue la ligne où est apparue l’erreur. Par contraste, qui se sentirait capable en moins de 10 minutes, de dire où est l’erreur dans le script AlgoBox ci-dessous ?

Or, 10 minutes quand on est dans une salle exigüe pleine d’ordinateurs surchauffés et d’élèves encore plus surchauffés (et trop nombreux) c’est énorme, surtout quand d’autres élèves appellent au secours au même moment...

Pour l’algorithme de la fin du TP, il reste à démontrer qu’il réalise bien l’échange entre x et y.

La démonstration la plus élégante consiste à décrire chacune des affectations par une matrice, et à calculer le produit des matrices pour montrer que ce produit est une symétrie par rapport à y=x (échange de x et y) :

\left(\begin{array}{rr}\frac{1}{4}&-\frac{1}{8} \\ 0&1 \end{array}\right)\left(\begin{array}{rr}1&0 \\ \frac{1}{2}&4 \end{array}\right)\left(\begin{array}{rr}2&-8 \\ 0&1 \end{array}\right)=\left(\begin{array}{rr}0&1 \\ 1&0 \end{array}\right)

Il va de soi que cette démonstration ne peut être donnée en Seconde ! La méthode de Hoare pas vraiment non plus... Par contre on peut raisonner avec un calcul littéral :

  • Si initialement, x contient a et y contient b,
  • après la ligne 3, x contient 2a-8b et y contient toujours b ;
  • après la ligne 4, x contient 2a-8b et y contient \frac{2a-8b}{2}+4b=a-4b+4b=a ;
  • enfin après la ligne 5, y contient toujours a et x contient \frac{a}{4}-\frac{2a-8b}{8}=\frac{a}{4}-\left(\frac{a}{4}-b \right)=b cqfd

La morale de ce TP, c’est que le choix de l’outil n’est nullement anodin : Avec leur affectation « simultanée » de plusieurs variables [2], les langages lua et Python rendent tout le TP inutile, comme le montre la séance IDLE ci-dessous :


[1il s’agit alors de comprendre que, après « x=2 », JavaScript attend un point-virgule, et que cette affectation n’est pas celle voulue à cause de l’absence du signe « * » ; pas simple mais on s’y fait assez vite, ne serait-ce qu’en regardant l’expression.

[2due à des conversions spontanées en listes de nombres


Commentaires

Logo de Axel
mardi 8 mai 2012 à 23h42 - par  Axel

Echange de 2 variables -> une petite astuce :

x=x+y
y=x-y
x=x-y

Annonces

Prochains rendez-vous de l’IREM

Séminaire EDIM-IREM

- Mercredi 14 juin 2017, 14h-18h, PTU, Saint-Denis, salle S23.6
- Mercredi 21 juin 2017, 14h-18h, 146 route de Grand-Coude, Saint-Joseph


Brèves

À travers les labyrinthes : algorithmes et fourmis

dimanche 1er septembre 2013

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

Rencontres Mondiales du Logiciel Libre à St-Joseph

mardi 20 août 2013

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

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

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

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

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

dimanche 19 août 2012

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

Ouverture du SILO

mardi 1er novembre 2011

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

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

Sur le Web : Site du SILO

Introduction à la science informatique

lundi 12 septembre 2011

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

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

Sur le Web : CRDP de Paris

Deux publications sur l’algorithmique

samedi 17 octobre 2009

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

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

Une carte mentale pour l’algorithmique

jeudi 10 septembre 2009

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

Un catalogue libre d’algorithmes pour le lycée

dimanche 30 août 2009

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

L’algorithmique à l’IREM de Lille

vendredi 26 juin 2009

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

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

Statistiques

Dernière mise à jour

samedi 24 juin 2017

Publication

757 Articles
Aucun album photo
132 Brèves
11 Sites Web
131 Auteurs

Visites

285 aujourd'hui
695 hier
2048019 depuis le début
15 visiteurs actuellement connectés