Algorithmique 1 et évaluation des compétences (Daprès un travail présenté par lacadémie de Nancy-Metz. Mars 2010 )

Algorithmique

1

et évaluation des compétences

(D’après un travail présenté par l’académie de Nancy-Metz. Mars 2010 )

Quelles compétences en algorithmique ? La question du référentiel.

2

d’analyser le fonctionnement ou le but d’un algorithme existant ;de modifier un algorithme existant pour obtenir un résultat précis ;de créer un algorithme en réponse à un problème donné.

Envisager une évaluation par compétences qui ne conduira pas nécessairement à une note spécifique chiffrée.

( document ressource : ) L’élève sera capable …

Les compétences visées (document ressource)

3

comprendre et analyser un algorithme préexistant ; modifier un algorithme pour obtenir un résultat

particulier ; analyser la situation : identifier les données

d’entrée, de sortie, le traitement...; mettre au point une solution algorithmique :

comment écrire un algorithme en « langage courant » en respectant un code, identifier les boucles, les tests, des opérations d’écriture, d’affichage... ;

valider la solution algorithmique par des traces d’exécution et des jeux d’essais simples ;

adapter l’algorithme aux contraintes du langage de programmation : identifier si nécessaire la nature des variables... ;

valider un programme simple.

3


4

Être capable de … comprendre et analyser un

algorithme préexistant ; modifier un algorithme pour

obtenir un résultat particulier ; analyser la situation : identifier

les données d’entrée, de sortie, le traitement...;

mettre au point une solution algorithmique : comment écrire un algorithme en « langage courant » en respectant un code, identifier les boucles, les tests, des opérations d’écriture, d’affichage... ;




4

Pouvons-nous proposer des exercices pour chacune de ces compétences ?


5









5

Expliquer en une phrase ce que fait cet algorithme

Entrée : Saisir trois nombres a, b et cTraitement :Affecter a+b+c à MAffecter M/3 à M Sortie : Afficher M


6







adapter l’algorithme aux contraintes du langage de programmation : identifier si nécessaire la nature des variables...


6

Modifier cet algorithme afin qu’il permette de calculer la moyenne de trois notes a, b et c affectées des coefficients 1,2 et 3 et qu’il signale si le résultat est ou non supérieur à 10

Entrée : Saisir trois nombres a, b et cTraitement :Affecter a+b+c à MAffecter M/3 à M Sortie : Afficher M


7



obtenir un résultat particulier ; analyser la situation : identifier les

données d’entrée, de sortie, le traitement...;





7

On veut écrire un algorithme qui permette de calculer la moyenne de trois notes a, b et c affectées des coefficients 1,2 et 3 et qui signale si le résultat est ou non supérieur à 10.Compléter :

Entrée :

Traitement :

Sortie :


8









8

Un examen comporte trois épreuves de coefficients respectifs 1, 2 et 3.

Un étudiant est reçu à l’examen si sa moyenne est supérieure ou égale à 10.

Écrire un algorithme qui renvoie l’information « l’étudiant est reçu » ou l’information « l’étudiant n’est pas reçu » à la saisie des trois notes.


9









9

Un examen comporte trois épreuves de coefficients respectifs 1, 2 et 3. Un étudiant est reçu s’il obtient une moyenne supérieure ou égale à 10, il est recalé s’il obtient strictement moins de 8 et il doit passer un oral si sa moyenne est comprise entre 8 et 10. On veut écrire un algorithme qui renvoie le résultat de l’examen à la saisie des trois notes.Un programmeur distrait a écrit l’algorithme ci-dessous. Quelles sont les erreurs qu’il a commises ? Entrée : saisir a,b,c Traitement :

affecter a+2*b+3*c/6 à M si M>=8 et M<=10 afficher « oral » sinon si M>=10 afficher « reçu » sinon afficher « recalé »


10









10

Un examen comporte trois épreuves de coefficients respectifs 1, 2 et 3. Un étudiant est reçu s’il obtient une moyenne supérieure ou égale à 10, il est recalé s’il obtient moins de 8 et il doit passer un oral si sa moyenne est comprise entre 8 et 10. On veut écrire un algorithme qui renvoie le résultat de l’examen à la saisie des trois notes.Exécuter l’algorithme suivant en utilisant Algobox. Entrée : saisir a,b,c Traitement :

affecter (a+2*b+3*c)/6 à M si M<8 afficher « recalé » sinon si M>=10 afficher « reçu » sinon afficher « oral »


11



obtenir un résultat particulier ; analyser la situation : identifier les

données d’entrée, de sortie, le traitement...;





11

Certaines compétences s’appliquent :

- à un algorithme, - à une situation

Exemples d’énoncés – exemple 1

12

Dans un repère orthonormal on considère les points A(-1;0) et B(3;0).Ecrire un algorithme qui effectuera la tâche suivante :

Si l’utilisateur lui fournit les coordonnées (x;y) d’un point C, le programme retournera l’une des deux informations « ABC est un triangle rectangle en C »

ou « ABC n’est pas un triangle rectangle en C ».

Solution 1

13

Critère choisi : la relation de PythagoreLe triangle est rectangle si AC²+BC²=16

Traitement algorithmique :saisir x, yAffecter (x+1)²+y² à PAffecter (x-3)²+y² à QAffecter P+Q à R

si R=16 alors…sinon …

Solution 2

14

Critère choisi :Utilisation du cercle circonscritLe triangle est rectangle si CI=2.

Traitement algorithmique :saisir x, y Affecter rac((x-1)²+y²) à R


Solution 2bis

15

Critère choisi :Utilisation du cercle circonscritLe triangle est rectangle si CI²=4

Traitement algorithmique :saisir x, y Affecter (x-1)²+y² à R


Solution 3

16

Critère choisi : utilisation du projeté orthogonal H de C, puis du critère CH²=BHxAH ou de la trigonométrie

Traitement algorithmique :saisir x, ysi y²=(x+1)(3-x) alors…sinon …

Remarques

17

Suivant le critère choisi, le traitement est plus ou moins complexe, et requiert ou non des variables supplémentaires.

Le critère mathématique le plus naturel (Pythagore) ne fournit pas le test le plus simple.

La solution utilisant la distance du point au milieu de l’hypoténuse présente une difficulté supplémentaire liée à la précision de la machine : le recours au carré de la distance.

Compétences en jeu

18

Géométrie : choix d’un critère pertinent, mobilisation de connaissances…

Calcul algébrique :Calcul d’une expression mobilisant deux variables

Raisonnement : utilisation d’une caractérisation « si … alors le triangle est rectangle en C »

Compétences en jeu - algorithmique

19

A partir d’une situation donnéeanalyser la situation

identifier les données d’entrée, élémentaire Identifier les données de sortie, élémentaire Identifier le traitement requis, la difficulté

principale n’est pas algorithmiquemettre au point une solution algorithmique

Les principales difficultés de l’algorithme sont masquées car elles touchent à la programmation.

La liste de compétences s’enrichit …

20

A partir d’un algorithme donné exécuter un algorithme ; comprendre et analyser un algorithme préexistant ; modifier un algorithme pour obtenir un résultat

particulier ; traduire un algorithme donné dans un langage de

programmation.

A partir d’une situation donnée analyser la situation (identifier les données d’entrée,

de sortie, le traitement...) mettre au point une solution algorithmique

(identifier les boucles, les tests, des opérations d’écriture, d’affichage prendre en compte les limites du langage de programmation, les questions de précision.. )

20

Exemple 2

2121

Déterminer tous les nombres entiers naturels égaux à la somme des cubes de leurs chiffres.

Version 1 – problème ouvert

Exemple 2

22

1 ) Ecrire un algorithme permettant de trouver tous les nombres inférieurs à 9999 qui sont égaux à la somme des cubes de leurs chiffres.

2) Calculer 5 x 93 .En déduire qu’il n’existe pas de nombre N à 5 chiffres qui soit égal à la somme des cubes de ses chiffres.

Existe-t-il des nombres de plus de 5 chiffres solutions du problème ?

3) A l’aide d’une calculatrice ou d’un logiciel déterminer tous les nombres solutions du problème.

Version 2 – problème guidé

Exemple 2

23


2) Ecrire un algorithme permettant de trouver tous les nombres inférieurs à 999 qui sont égaux à la somme des cubes de leurs chiffres.




Version 3 – problème guidé mathématiques et algorithmique

Algorithme en langage conventionnel

24

Variables

m, c, d, u, N, S nombres entiers naturels

Début pour m allant de 0 à 9

pour c allant de 0 à 9 pour d allant de 0 à 9 pour u allant de 0 à 9

affecter la valeur 1000m+100n+10d+u à N affecter la valeur m3+c3+d3+u3 à S Si N=S alors Afficher N

Fin

25

Version scilab

26

******************************************1 VARIABLES2 u EST_DU_TYPE NOMBRE3 d EST_DU_TYPE NOMBRE4 c EST_DU_TYPE NOMBRE5 m EST_DU_TYPE NOMBRE6 S EST_DU_TYPE NOMBRE7 N EST_DU_TYPE NOMBRE8 DEBUT_ALGORITHME9 POUR m ALLANT_DE 0 A 910 DEBUT_POUR11 POUR c ALLANT_DE 0 A 912 DEBUT_POUR13 POUR d ALLANT_DE 0 A 914 DEBUT_POUR15 POUR u ALLANT_DE 0 A 916 DEBUT_POUR17 N PREND_LA_VALEUR u+10*d+100*c+1000*m18 S PREND_LA_VALEUR pow(u,3)+pow(d,3)+pow(c,3) +pow(m,3)19 SI (S==N) ALORS20 DEBUT_SI21 AFFICHER N22 FIN_SI23 FIN_POUR24 FIN_POUR25 FIN_POUR26 FIN_POUR27 FIN_ALGORITHME

Version algobox

***Algorithme lancé***01153370371407***Algorithme terminé***

Compétences en jeu - version 3

27






Arithmétique :• Numération décimaleCalcul algébrique :• Manipulation

d’expressions à plusieurs variables

Raisonnement :• Raisonnement par

disjonction des cas.(Analyse :• Comparaison de suites)


28






AlgorithmiqueA partir d’une situation

donnée analyser la situation

identifier les données d’entrée,

de sortie, le traitement

mettre au point une solution algorithmique

identifier les boucles, les tests, des opérations d’écriture,

d’affichage écrire un programme en

réponse à une question posée.A partir d’un algorithme

donné modifier un algorithme pour

obtenir un résultat particulier ;


29

Déterminer tous les nombres entiers naturels égaux à la somme des cubes de leurs chiffres.

A partir d’un algorithme donné exécuter un algorithme ; comprendre et analyser un


obtenir un résultat particulier ; écrire un programme en réponse à

une question posée.

A partir d’une situation donnée analyser la situation (identifier les

données d’entrée, de sortie, le traitement...)

mettre au point une solution algorithmique (identifier les boucles, les tests, des opérations d’écriture, d’affichage...)

Prendre l’initiative pertinente de construire une solution algorithmique.

Les difficultés des élèves

30

Les erreurs repérées : Confusion affectation et égalité ; Notion de variable non comprise ; Confusion de lecture du programme

; Difficulté de validation de

l’algorithme ; Difficulté pour comprendre le rôle

de l’algorithme.

30

Les facteurs de complexité

31

la nécessité d’un test d’arrêt ; le nombre de boucles à imbriquer ;le nombre d’issues des tests ;les variables qui subissent de nouvelles affectations dans le traitement ;Les variables « masquées » ;La complexité des concepts mathématiques mobilisés ;La complexité du traitement mathématique requis pour le traitement algorithmique ;La présence d’astuces ou de contraintes liées au traitement algorithmique ou au langage à utiliser.

LES ENJEUX

32

Concevoir des situations qui soient intéressantes, d’un point de vue mathématique et accessibles d’un point de vue algorithmique

Repérer les compétences

Peut-on / doit-on évaluer isolément les compétences relatives à l’algorithmique ?

Documents

Algorithmique 1 et évaluation des compétences (Daprès un travail présenté par lacadémie de Nancy-Metz. Mars 2010 )