Embed Size (px)
Citation preview
Algorithmes en 2nde
Claude Poulin pour le groupe de réflexion-production - Nouméa 2009
Algorithmique: L’algorithmique est une branche complexe des
mathématiques
- comparaison de performances- convergence des algorithmes- preuves de programmes…
En 2nde, on abordera seulement
- l’initiation à la pensée algorithmique- l’analyse d’algorithmes existants- des modifications d’algorithmes - la réalisation d’algorithmes- quelques bases de programmation
Des algorithmes, quand?
En relation avec toutes les parties du programme: fonctions, statistiques, géométrie, logique et langue (si .. alors, et...).
Il ne s’agit pas seulement d’utiliser des algorithmes existants.
Des algorithmes, pourquoi?
La résolution de certains problèmes montre la
nécessité d’organiser une suite de traitements, de calculs; de mettre au point des solutions algorithmiques.
Officiellement…
Des algorithmes partout …. La notion d’algorithme reste proche de « recette »,
« méthode systématique», « procédure »…
Des algorithmes plus ou moins complexes sont utilisés dans la vie courante (recherche d’informations -comment marche Google? -, traitement et compression des données, tris, codage, simulation, imagerie médicale, automate de banque…. ). pour un ambulancier..
Des algorithmes déjà rencontrés en mathématiques:
- division à la main- résolution d’une
équation du premier degré
- Euclide- Eratosthène- constructions en
géométrieUne solution de
x²+ax=b
L’expression des algorithmes:
En langage ordinaire.
En pseudo langage, pas aussi formalisé que dans un programme.
Parfois sous forme de schéma: organigramme …
Un exemple…
"Faites prendre la moitié du nombre pair pensé, puis ajouter 1 et multiplier le résultat par 6; demandez le quotient par 3 du résultat obtenu. Ce quotient diminué de 2 est le nombre pensé."
(Emile Fourrey, Récréations mathématiques, 1905)
Algorithme en plusieurs étapes, où l’on retrouve une entrée, un traitement de données et une sortie d’un résultat.
choisir un nombre pair x prendre sa moitié ajouter 1 au résultat précédent multiplier le résultat par 6 puis diviser par 3 retrancher 2 annoncer le nombre pensé.
Et la programmation ?
C’est la réalisation de l’algorithme (la phase « intelligente ») qui a un réel intérêt.
Programmer, c’est finalement traduire un algorithme afin qu’il soit exécuté (ordinateur, machine outil, ..).
Cela reste un travail « subalterne », un simple codage dans un langage particulier.
Apprendre à programmer?
En 2nde ce n’est pas vraiment prévu.
Il s’agit simplement quand la nécessité se fait (ou l’envie, car il est assez stimulant de « voir tourner » un algorithme en espérant obtenir le résultat attendu) de traduire l’algorithme dans un langage adéquat
(mais le langage n’est pas l’essentiel – vaut mieux avoir …. quelque chose à dire !).
Les supports de programmation.
Principalement les outils déjà communément utilisés (tableurs, calculatrices).
Il est possible de compléter avec des logiciels de programmation: Scratch, Python, Algobox, Visual Basic, Html&Javaou des logiciels de calculs scientifiques (Scilab, Derive…)
Et même des logiciels de calcul formel (Xcas, Mupad…).
Attention !
Faire tourner un programme permet de montrer qu’il contient des erreurs, pas qu’il est juste.
Utiliser l’outil informatique pour émettre des conjectures, oui ; mais gare aux preuves « sommaires » apportées par l’exécution d’un programme.
Traitements de l’exemple.
A la main ou en effectuant les calculs sur une simple calculatrice.
Par exemple, si le partenaire a choisi 10
10/2= +1= X6= /3= -2= et on annonce le résultat affiché.
S’il faut recommencer avec un autre nombre, cela devient vite fastidieux.
Il vaut mieux automatiser ce calcul à l’aide d’un tableur.
On retrouve l’affectation en B1, les formules et la sortie en B6.
A B
Choisir un nombre 10
=B1/2
=B2+1
=B3*6
=B4/3
Résultat =B5-2
A B
Choisir un nombre 10
5
6
36
12
Résultat =10
Ou utiliser la calculatrice programmable …
TI, on passe en mode programmation avec la touche « PRGM » , nouveau, Nom= DEVINE
Input N « demande à l'utilisateur de saisir un nombre : la valeur est stockée dans une mémoire nommée N »
N/2→ R « La flèche →, qui obtenue par appui sur la touche STO, demande à la calculatrice de stocker un résultat dans une mémoire nommée R.
Stocker une valeur s'appelle faire une affectation »
R+1 → R
R*6 → R
R/3 → R
R-2 → R
Disp R « La dernière ligne affiche la valeur contenue dans la mémoire R. »
------------------------------------------------------------------------
Il faut parler un peu « patois »
Input veut dire entrée
STO vient de to store qui veut dire stocker
Disp vient de to display qui veut dire afficher
CASIO, on passe en mode programmation avec la touche « PRGM »
La ligne ("Nombre="? → N) demande à l'utilisateur de saisir un nombre: un texte est affiché (Nombre=) et le ? invite l'utilisateur à faire la saisie, laquelle est stockée
(→)dans une mémoire nommée N.
La flèche → demande à la calculatrice de stocker un résultat dans une mémoire : à partir de la 2ème ligne, les résultats de calculs sont stockés dans la mémoire R.
La dernière ligne (R ) affiche la valeur contenue dans la mémoire R.
avec Scratch*
* Scratch, logiciel libre et ludique, possède une tortue comme LOGO; il a le gros avantage de bien visualiser les structures; on peut exécuter plusieurs algorithmes en parallèle.
avec Scilab
x=10 x = 10. r=((x/2)+1)*6/3-2 r = 10.
Avec un logiciel de calcul formel (Xcas)
Là il y a une différence de taille: on aura la preuve formelle, par simplification.
Comment aborder le sujet en seconde.
Une recette de cuisine. Faire exécuter l’algorithme de
construction de l’œuf . Le rangement d’un cartable. Jouer au robot (un élève écrit des
consignes – calculs, figure – et un autre exécute).
Donner des petits algorithmes et deviner ce qu’ils doivent donner ; les modifier …
Et …
Essayer de faire le lien avec les collègues de français et la logique (si .. alors, ou, et, non …).
La notion de variable est une notion majeure utilisée avec un tableur (une cellule est avant tout une variable)
La notion de variable est très utilisée aussi sur la calculatrice (pour stocker temporairement une valeur).
« Rédiger » un problème de construction en géométrie consiste déjà à proposer un algorithme de construction. Les ordres dans ce cas sont usuellement des droites à tracer avec la règle ou des cercles avec le compas.
Y a-t-il des difficultés?
Un algorithme apporte une solution à un problème. Il doit être juste par construction, jamais par essai. Il doit être rédigé clairement, lisiblement dans un
souci de communication (et de maintenance!) Les étapes que l’on retrouve quasi systématiquement
(préparation du traitement, traitement, édition des résultats) doivent être clairement identifiées.
Les éléments de base restent néanmoins limités…
L’affectation:
Dans A range 3 A := 3 A ← 3
Déconseillé A = 3 ou A → 3
Exercice « échanger A et B » …Exercice « permuter circulairement A, B et C »
Une bonne habitude, la déclaration quand c’est possible ou l’initialisation systématique des variables…
Le calcul de la surface d’un rectangle quand on entrera les deux dimensions (Python*):
Un exercice d’initiation, un exemple à commenter ou un exemple à modifier …
* Python, logiciel libre possède un interpréteur et un compilateur, une tortue; mais peut présenter des inconvénients pour des débutants (pas de déclaration de variable;blocs par indentation; = pour affectation…)
Le test (structure alternative):ALGORITHME Equation
VAR A, B, C, DELTA : REEL DEBUT LIRE ( A, B, C) Delta := B*B - 4*A*C SI Delta > 0 : Ecrire ( 'Première racine : ', (-B + Racine(Delta)) / (2* A) Ecrire ( 'Deuxième racine : ', (-B - Racine(Delta)) / (2 *A) SINON SI Delta = 0 Ecrire('Une racine double :', -B / ( 2*A) SINON Ecrire('Pas de racine réelle') FSI FSIFIN
Le test (structure alternative ; Algobox*):VARIABLES a EST_DU_TYPE NOMBRE b EST_DU_TYPE NOMBRE c EST_DU_TYPE NOMBRE d EST_DU_TYPE NOMBRE x1 EST_DU_TYPE NOMBRE x2 EST_DU_TYPE NOMBRE
DEBUT_ALGORITHME LIRE a LIRE b LIRE c d PREND_LA_VALEUR b*b-4*a*c
SI (d<0) ALORS DEBUT_SI AFFICHER "Pas de racine réelle" FIN_SI SINON DEBUT_SINON x1 PREND_LA_VALEUR (-b-sqrt(d))/(2*a) AFFICHER "x1=" AFFICHER x1 x2 PREND_LA_VALEUR (-b+sqrt(d))/(2*a) AFFICHER "x2=" AFFICHER x2 FIN_SINONFIN_ALGORITHME
*Algobox, logiciel libre est un excellent outil de rédaction d’algorithme, avec des commandes prêtes à l’emploi et possibilité d’exécution immédiate.
Le test (structure alternative): Ranger deux nombres (Scratch)
Et les boucles ?
Affectation, entrée, sortie ne doivent pas présenter de grandes difficultés.
La structure conditionnelle demandera plus de temps.
Élaborer une boucle reste la véritable difficulté en algorithmique.
La répétition:
Pour œuf n° 1 jusqu’à œuf n° 6
Faire Casser l’œufVerser le contenu dans le bolFinFaire
Dans cet exemple le nombre d’itérations est connu.
VARIABLES n EST_DU_TYPE NOMBRE somme EST_DU_TYPE NOMBRE
DEBUT_ALGORITHME somme PREND_LA_VALEUR 0
POUR n ALLANT_DE 1 A 100 DEBUT_POUR somme PREND_LA_VALEUR somme+1/n
FIN_POUR AFFICHER sommeFIN_ALGORITHME
La construction d’une étoile (avec la tortue de Scratch) :
La répétition, version 2:N ← 0S ← 0Tant que S <1000 Faire S ← S + N N ← N+1 FinFaireEcris S
Ici le nombre d’itérations est inconnu.
Exemple: pourquoi cet algorithme est faux?
I ← 0
Tant que I < 100 Faire
Ecris I Fin Faire
En seconde – fonctions.
Calculer l’indice de masse corporelle I= masse/taille² Si I>25 afficher « en surpoids »…
Tableau de valeurs avec un tableur. Maximiser le volume d’une boîte.
En seconde – expressions.
Résolution d’une équation du 1er degré. Transformations formelles avec Xcas. Méthode de Hörner. Encadrement de solutions de f(x)=0
(dichotomie). existence d’un triangle pour trois nombres
donnés sortir le plus grand de trois nombres
Algorithme permettant d'obtenir la valeur approchée de la solution positive de l'équation (ALGOBOX).
1 VARIABLES
2 a EST_DU_TYPE NOMBRE
3 b EST_DU_TYPE NOMBRE
4 ecart EST_DU_TYPE NOMBRE
5 milieu EST_DU_TYPE NOMBRE
6 image EST_DU_TYPE NOMBRE
7 DEBUT_ALGORITHME
8 a PREND_LA_VALEUR 1
9 b PREND_LA_VALEUR 3
10 ecart PREND_LA_VALEUR b-a
11 TANT_QUE (ecart>0.001) FAIRE
12 DEBUT_TANT_QUE
13 milieu PREND_LA_VALEUR (a+b)/2
14 image PREND_LA_VALEUR milieu*milieu -2
15 AFFICHER "("
16 AFFICHER a
17 AFFICHER ";"
18 AFFICHER b
19 AFFICHER ")"
20 AFFICHER "milieu="
21 AFFICHER milieu
22 AFFICHER ";"
23 AFFICHER "image par la fontion="
24 AFFICHER image
25 SI (image<0) ALORS
26 DEBUT_SI
27 a PREND_LA_VALEUR milieu
28 FIN_SI
29 SINON
30 DEBUT_SINON
31 b PREND_LA_VALEUR milieu
32 FIN_SINON
33 ecart PREND_LA_VALEUR b-a
34 FIN_TANT_QUE
35 AFFICHER "la valeur qui annule la fonction est proche de :"
36 AFFICHER milieu
37 FIN_ALGORITHME
² 2 0x
En seconde – statistiques, probas.
Fluctuation d’échantillonnage: simulations d’un lancer de deux dés.
Intervalles de confiance. Déterminations de Q1, Me, Q3 (les
valeurs obtenues à la machine ne sont pas satisfaisantes).
En seconde – géométrie.
Calcul des coordonnées d’un milieu. Programme de construction dans le plan. Vérifier la colinéarité de deux vecteurs. Construction d’un cube avec Géospace.
Et après ?
Il est évident que cette initiation aux algorithmes sera poursuivie par la suite…
Des documents sont déjà à consulter sur:http://www.ac-noumea.nc/maths/ (prise en main des calculatrices programmables,
de Xcas, de Maple, de Mupad…)
Des stages de différents niveaux seront proposés.
L’algorithmique au service de problèmes. Procédures de tris et comparaison de leurs
performances. recherche d’un maximum d’une fonction par
trisection. Approximation de Approximation de Pi Algorithme récursif d’Euclide Algorithmes sur les graphes Algorithmes sur le méthodes de calculs
d’intégrales
2
Des algorithmes qui gagnent à être connus….
Équations différentielles : méthode d’Euler, accélération de Runge …
Équations non linéaires : point fixe, méthode de la sécante, Newton, Delta d’Aitken, Steffesen et Romberg…
Systèmes linéaires : Gauss, Souriau.. Algorithme CORDIC.
Et quelques bases en analyse numérique et en calcul formel.
