Algorithmique et programmation au Lycée

Renée De Graeve   Bernard Parisse

Table des matières

Index

Chapitre 1  Introduction

1.1  Apprendre en programmant.

Ce document est principalement destiné aux enseignants qui souhaitent utiliser Xcas pour enseigner l’algorithmique au lycée. Nous espérons qu’il sera aussi consulté par des élèves. Dans sa version HTML consultable depuis un navigateur, certains champs de saisies peuvent être modifiés et testés directement, y compris sur une tablette ou un smartphone, ce qui devrait être un plus par rapport à un cours de programmation papier ou PDF (les fonctions “utilitaires” qui sont appelées plusieurs fois par d’autres fonctions n’ont pas besoin d’être validées par l’utilisateur, elles sont interprétées au chargement).

Xcas possède deux interfaces. L’interface classique (Xcas natif) fonctionne sur PC et nécessite une installation, cf. la section A.3. On peut aussi utiliser Xcas pour Firefox sans installation depuis tout appareil disposant d’un navigateur (Firefox recommandé), par exemple depuis un smartphone ou une tablette sans installation, depuis le lien :
http://www-fourier.ujf-grenoble.fr/~parisse/xcasfr.html
(L’accès réseau est nécessaire uniquement lors du chargement de la page).
Il n’est donc pas indispensable d’aller en salle informatique pour faire un exercice d’algorithmique pendant un cours de mathématiques, on peut utiliser les smartphones (en mode avion) ou les tablettes des élèves comme des super-calculatrices (formelles, graphiques, 3d, ... il ne manque que le mode examen...). C’est une raison supplémentaire pour écrire ce document, car faire programmer les algorithmes par les élèves nous parait indispensable pour les motiver par la satisfaction de faire tourner son programme puis de le modifier et de l’améliorer.

Faire programmer nous semble bien plus formateur que de demander à un élève de comprendre ce que fait un algorithme non commenté, surtout s’il n’a pas de machine pour le tester (par exemple le jour du bac). En effet l’élève n’a aucun rôle créateur (il ne conçoit pas l’algorithme), il a un rôle analogue à celui d’un professeur corrigeant des copies ce qui n’est pas du tout motivant et a devant les yeux un modèle désastreux d’algorithme puisque non commenté ! De plus, comprendre ce que fait un algorithme non commenté est parfois plus difficile que d’en concevoir un, car les notations de variables, par exemple, ne prennent souvent sens qu’une fois l’algorithme compris. Imagine-t-on donner les étapes de calcul d’une démonstration, sans explications, et demander quel est le théorème qui a été démontré ? Bien sur, la programmation s’apprend de manière progressive, en regardant des exemples de code commentés, puis en complétant des maquettes d’algorithmes avant de se lancer dans l’écriture complète de nouveaux algorithmes.

1.2  Le choix du langage de programmation

La plupart des langages interprétés permettent d’apprendre à programmer les concepts algorithmiques au programme du lycée (test, boucle, variable, affectation, fonction). Pour les élèves, la difficulté principale ce sont les concepts algorithmiques, rarement la syntaxe du langage lui-même, à condition de pouvoir se faire aider par l’enseignant s’ils sont bloqués. C’est donc l’enseignant qui devrait choisir un langage avec lequel il se sent à l’aise, non seulement pour écrire lui-même un programme, mais aussi pour trouver rapidement une erreur de syntaxe ou d’exécution dans le programme d’un de ses élèves.

Pour la grande majorité des élèves, nous pensons qu’il serait souhaitable qu’ils soient confrontés lors des changements de professeur à plusieurs langages au cours de leur scolarité (par exemple Xcas, calculatrices, Python, Javascript ...), ce qui leur permettrait de mieux comprendre les concepts universels partagés (l’algorithmique) et les biais et particularités propres à un langage donné (voir en appendice), et faciliterait aussi leur adaptation à d’autres langages plus tard. Pour ceux qui se destinent à des études scientifiques, il nous parait important qu’ils soient aussi confrontés à d’autres types de langages (compilés, fonctionnels ...) au cours de leurs études supérieures, dont au moins un langage de plus bas niveau : les langages interprétés permettent d’utiliser facilement des types ou instructions puissantes, se confronter avec un langage de plus bas niveau permet de mieux comprendre ce qui est basique ou ne l’est pas et ce qui est intrinsèquement rapide ou/et couteux en ressource mémoire ou ne l’est pas (on peut voir ça comme l’analogue entre faire une démonstration ou admettre un théorème).

Actuellement aucun langage n’est imposé dans les textes pour le lycée, nous espérons que cette situation va perdurer et que certains enseignants résisteront aux pressions de vouloir imposer Python comme le seul et unique langage de programmation au lycée (comme pour les enseignements obligatoires d’informatique en classe préparatoires). Pour les aider dans cette démarche, nous avons ajouté la possibilité de programmer dans Xcas avec une syntaxe compatible avec Python (les personnes connaissant Python peuvent consulter l’appendice B.1 qui décrit plus en détails les différences entre Python et Xcas).

Pourquoi choisir Xcas ?
Xcas est fortement orienté mathématique et de ce fait peut facilement interagir avec les thèmes du programme de maths, tous les types mathématiques au programme du lycée sont directement accessibles (par exemple : les nombres entiers, rationnels, réels, complexes, les nombres approchés, les vecteurs, les polynômes et les matrices).

Le langage de programmation natif de Xcas est proche du langage algorithmique ce qui facilite ensuite sa traduction dans d’autre langage, y compris en syntaxe Python (menu Fichier, Exporter, texte python). Nous avons adapté le langage en français pour en faciliter l’apprentissage d’après notre expérience d’enseignement avec des publics divers :

Xcas accepte également l’écriture de programmes en syntaxe compatible Python, mais en évitant certains pièges du langage par rapport aux mathématiques :

On s’efforcera de donner dans ce document des programmes écrits avec les mots-clefs en français et leur traduction en syntaxe Python, les deux syntaxes sont valides dans Xcas. Lorsque la traduction Python n’est pas fournie, on peut l’obtenir de manière automatique depuis Xcas : on saisit le programme écrit en français, puis on l’exporte en texte Python.

Une partie des programmes de ce document écrits en syntaxe Python, peuvent être utilisés dans un interpréteur Python à condition d’y avoir chargé le module giacpy par la commande from giacpy import * et d’avoir affecté quelques variables symboliques (par exemple pour x par x=giac('x'), car il n’y a pas de variables symboliques en Python)

1.3  Structure du document

Les deux premiers chapitres 2 et 3 sont destinés aux débutants, ils présentent les notions de variables, types fondementaux, les structures de programmation et les fonctions avec de nombreux exemples, en partie non mathématiques. Les chapitres suivants donnent de nombreux exemples d’algorithmes dans des thèmes mathématiques allant de la résolution d’équation, à la géométrie et aux statistiques. En annexe on trouvera une aide à l’installation et aux premiers pas avec Xcas, ainsi qu’une discussion plus avancée sur les divers langages de programmation interprétés.

Chapitre 2  Types, fonctions

2.1  Types

2.1.1  Entiers, rationnels, réels, complexes et les nombres approchés.

Dans Xcas :

Pour avoir une valeur approchée d’un nombre réel on utilise la commande evalf, par exemple evalf(sqrt(2)) ou evalf(sqrt(2),20) pour avoir une valeur approchée de 2\sqrt 2 avec 20 chiffres significatifs.



Pour avoir l’écriture d’un nombre complexe sous la forme a+iba+ib avec aa et bb réels on utilise la commande evalc, par exemple evalc((1+i*sqrt(2))^2+2).



2.1.2  Les listes, les séquences et les chaînes de caractères

Définition d’une liste

Qu’est-ce qu’une liste ?
C’est une énumération d’objets, dont l’ordre est important. Cela peut servir à représenter les coordonnées d’un point ou d’un vecteur, à contenir une liste de valeurs (observations) en statistiques, ...
Une liste est délimitée par des crochets [] et les éléments de la liste sont séparés par une virgule ,

Création d’une liste

Définition d’une séquence

Qu’est-ce qu’une séquence ?
On peut le voir comme une liste sans crochets, ce qui signifie que si on sépare 2 séquences par une virgule, elles sont concaténées, on ne peut donc pas créer une séquence de séquences alors qu’on peut créer une liste de listes. Par exemple les arguments d’une fonction sont regroupés en une séquence.
Une séquence n’est pas délimitée (ou est délimitée par des parenthèses ()) et les éléments de la séquence sont séparés par une virgule ,

Attention,
cette syntaxe renvoie un n-uplet en Python, il s’agit d’une liste constante (non modifiable après création).

Création d’une séquence

Transformation d’une séquence en liste et vice-versa

Si S est une séquence alors [S] est une liste.
Si L est une liste alors op(L)] est une séquence.







Définition d’une chaine de caractères

Qu’est-ce qu’une chaine de caractères ?
C’est la concaténation de 0, 1 ou plusieurs caractères.
Une chaine de caractères est délimitée par ""
On concaténe de 2 chaînes avec +


2.1.3  Les instructions sur les listes les séquences et les chaînes de caractères

2.1.4  Les booléens

Définition

L’ensemble des booléens est un ensemble à 2 éléments :
vrai ou 1 et faux ou 0.
Pour faire des tests, on utilise des opérateurs booléens.

Opérateur booléen infixé qui teste l’égalité ==

Pour tester l’égalité entre deux objets (réels, entiers, expressions, listes..) on utilise l’opérateur ==. Le test renvoie vrai si les deux objets sont égaux, au sens où leur représentation informatique est identique. Pour tester que deux expressions littérales contenues dans les variables a et b sont mathématiquement équivalentes, il est parfois nécessaire de faire une commande explicite de simplification, au lieu d’écrire a==b on écrit simplify(a-b)==0.

Exemple :







Les différentes significations des signes :=, =,==, #=

Attention

Opérateur booléen infixé qui teste la non égalité !=

Le signe != sert à tester la non égalité.
C’est un opérateur booléen infixé. Il renvoie vrai ou faux.
Exemple :





Opérateur booléen infixé qui teste l’inégalité <, >, <=, >=

Les signes <, >, <=, >= servent à tester les inégalités.
Ce sont des opérateurs booléens infixés. Ils renvoient vrai ou faux.
Exemple :







2.1.5  Expressions, polynômes

Simplification d’une expression avec normal

Xcas renvoie le résultat d’un calcul littéral sans le simplifier (sauf pour les calculs dans les rationnels).
Il faut utiliser la fonction normal ou simplify pour obtenir un résulat simplifié.





Les polynômes

Un polynôme à une indéterminée à coefficients dans \mathbb{R} est déterminé par une séquence a n,...,a 1,a 0a_n,...,a_1,a_0 d’éléments de \mathbb{R}, c’est l’expression :
a nx n+...+a 1x+a 0a_nx^n+...+a_1x+a_0 (ou a 0+a 1x+a 2x 2+..+a nx na_0+a_1x+a_2x^2+..+a_nx^n).
nn est le degré du polynôme.
On dit que l’on a écrit le polynôme selon les puissances décroissantes (ou croissantes).
a n,..a 1,a 0a_n,..a_1,a_0 sont les coefficients du polynôme et xx est la variable ou l’indéterminée du polynôme.
On notera l’ensemble des polynômes à une indéterminée xx : [x]\mathbb{R}[x].

Un polynôme à 2 indéterminées xx et yy à coefficients dans \mathbb{R} est déterminé par une séquence A n(y),...,A 1(y),A 0(y)A_n(y),...,A_1(y),A_0(y) d’éléments de [y]\mathbb{R}[y] et a pour expression :
A n(y)x n+...+A 1(y)x+A 0(y)A_n(y)x^n+...+A_1(y)x+A_0(y) (ou A 0(y)+A 1(y)x+A 2(y)x 2+..+A n(y)x nA_0(y)+A_1(y)x+A_2(y)x^2+..+A_n(y)x^n)
Par exemple :
si A 0(y)=y 32,A 1(y)=2y,A 2(y)=y 3+2*y+3A_0(y)=y^3-2,A_1(y)=-2y,A_2(y)=y^3+2*y+3
Le polynôme s’écrit :
y 322y*x+(y 3+2*y+3)*x 2=x 2*y 3+2*x 2*y+3*x 22*x*y+y 32y^3-2-2y*x+(y^3+2*y+3)*x^2=x^2*y^3+2*x^2*y+3*x^2-2*x*y+y^3-2
Le degré par rapport à xx du polynôme de cet exemple et égal à 2.
Le degré par rapport à yy du polynôme de cet exemple et égal à 3.

Coefficients et degré d’un polynôme

Xcas représente les polynômes soit sous la forme d’une expression symbolique, soit comme la séquence des coefficients selon les puissances décroissantes (poly1[1,2,3] i.e. [a2,a1,a0]:=[1,2,3]).
Par exemple, le polynôme x 2+2x+3x^2+2x+3 s’écrit:
soit x^2+2x+3x est l’indéterminée mais Attention x doit être une variable symbolique donc x doit être purgée,
soit poly1[1,2,3]
Les commandes symb2poly(x^2+2x+3) et poly2symb([1,2,3],x) passent d’une représentation à l’autre.

2.1.6  Connaître les types et les sous-types

Les types
Xcas sait reconnaître le type d’un objet.
Pour avoir le type de l’objet a ou le contenu d’une variable a, on utilise type(a).
Les types utilisés ici sont :
real ou 1 ce qui signifie que a contient un nombre flottant.






integer ou 2 ce qui signifie que a contient un nombre entier,






rational ou 10 ce qui signifie que a contient un nombre rationnel,






func ou 13 ce qui signifie que a est le nom d’une fonction,








vecteur ou 7 ce qui signifie que a contient une liste,






string ou 12 ce qui signifie que a contient une chaîne de caractères,






expression ou 8 ce qui signifie que a contient une expression,










identifier ou 6 ce qui signifie que a contient le nom d’une variable non affectée.





Les sous-types
Certains types de variables peuvent servir à plusieurs usages : par exemple une liste peut représenter les coordonnées d’un point dans l’espace ou les coefficients d’un polynôme ou un ensemble. Xcas possède une commande subtype permettant de préciser le type d’une variable. Pour avoir le sous-type de la variable a, on utilise subtype(a).
Par exemple si a contient une liste, subtype(a) renvoie 1 pour une séquence, 2 pour un ensemble, 10 pour un polynôme et 0 sinon.







2.2  Les fonctions

On distingue les fonctions ou commandes de Xcas et les fonctions définies par l’utilisateur. Pour éviter le risque d’utiliser un nom de fonction de Xcas, il est conseillé de nommer les fonctions utilisateurs en utilisant une majuscule comme première lettre. Pour définir des fonctions (utilisateurs), on distinguera :

2.2.1  Quelques fonctions algébriques de Xcas

abs est la fonction valeur absolue.


ceil est le plus grand entier >=&gt;= à l’argument.
cos est la fonction cosinus.


floor est la partie entière i.e.le plus grand entier <=&lt;= à l’argument.




frac est la partie fractionnaire d’un réel.




max est la fonction maximum pour une séquence de nombres réels.


min est la fonction minimum pour une séquence de nombres réels.


^ est la fonction puissance.


round est la fonction qui arrondit un réel en l’entier (resp le décimal) le plus proche.






sign est la fonction signe de l’argument et renvoie -1, 0 ou +1.






sin est la fonction sinus.


sqrt est la racine carrée.






tan est la fonction tangente.

2.2.2  Quelques fonctions aléatoires de Xcas

Nous donnons ci-après les fonctions aléatoires les plus fréquentes : pour des raisons de compatibilité avec le langage Python chacune des fonctions ci-dessous peuvent être préfixée par random. (par exemple on peut écrire random.randint() ou randint())

srand randseed RandSeed
srand ou randseed initialise la suite des nombres aléatoires : srand ou randseedrenvoie un entier qui a servi à cette initialisation.
On tape :

RandSeed
RandSeed(n) initialise les nombres aléatoires selon la valeur de l’entier n.
On tape :

random rand
random() ou rand() renvoie un nombre réel (pseudo)-aléatoire de l’intervalle semi-ouvert [0,1[[0,1[.
On tape :

choice
choice(L) ou random(L) ou rand(L) renvoie un élément tiré au hasard parmi les éléments de la liste L.
On tape :

randint
randint(a,b) renvoie un nombre entier (pseudo)-aléatoire compris entre a et b (bornes incluses).
On tape :

shuffle
shuffle(L) applique une permutation aléatoire à la liste L.
On tape :

sample ou rand
sample(L,n) ou rand(n,L) renvoie, si n<=size(L), n éléments tirés, au hasard, sans remise parmi les éléments de la liste L et sinon renvoie une erreur.
On tape :


Remarque sample(L,len(L)) ou rand(dim(L),L) est identique à shuffle(L).

On tape en syntaxe Xcas :

fonction testrand()
  local L1,L2,L3,n1,n2,a1,a2;
  n1:=random();
  n2:=random();
  a1:=randint(1,10);
  a2:=randint(1,10)
  L1:=sample([1,2,3,4,5,6],3);
  L2:=sample([1,2,3,4,5,6],3);
  L3:=shuffle([1,2,3,4,5,6]);
  return n1,n2,a1,a2,L1,L2,L3;
ffonction:;


abs(sqrt abs(sqrt

Nous donnons c65ent être préfixée par floor(-2.42) sign est la fonction signe de l’argument et renvoie -1, 0 ou +1.
ksign est la fonction signe de l’argument et renvoie -1, 0 ou +1.
sign est la fonction signe de l’argument et renvoie -1, 0 ou +1.

1, x-2,-xe;tght:bold">Remarque sample(L,len(L)) ou rand(dim(L),L) est identique à pace">XcasEC END -BEGIN NOTES chapp;Ult59">revea_deffootvalerul>iabdlevea_defthmfootvalesiabdtevea_defdt-thmfootvalesia tions vale1" href="#t:bo1"oncl>Re/dtabddevea_defdd-thmfootvalesiabdivevea_deffootvalet:bo">En toutI.rigur tmce:sotre stynombL=' onmquignoree=au niveau du lycéee/divRe/ddabdtevea_defdt-thmfootvalesiations vale2" href="#t:bo2"o2cl>Re/dtabddevea_defdd-thmfootvalesiabdivevea_deffootvalet:bo">2:=pn> outilisee=nex1,2,3,4,var tm ou randint()=au seies. srandnlt59">1/a>Chapionc 3="heLote(teviuspan stUI.protaill';var s tmp=se">srandn< tions chap:protent ê-2:=>ly:s iciolote(teviuspan ste([1,2,3,4,); ,/spae([1,2,3,4,ce">ra.-SEC END -->

id="hevea_deec37" Cizme2,3iL=' e);eoc(tmp)';var.lt59">2vea_deec37" vea_defa60">3.1="heCizme2,3iL=' e);eoc(tmp)';var.

Nous donnons c76s fonctions ci-dessous pe7oires l;Pyle=f3iL= asecizme2,3iL=span> .

3.1.2="heDoc(tmp)e< tions ci-dessous pe78iable o>lynsindcy='r,var tmpersly:s utilisrmqln vétaillrce:lue=f3itrce:vétaillren> sranda"previoi>c"previlay='inherit';var tmp=UI.caseval(previousSiblinb^2-4acing.value);tmp=UI.rmquote(tmp); (tmp); nextSibe([1,2,3,4,5,6],3); L3:=shuffle([1,2,3,4,5,6]); return :xtS2,a1,a2,L1,L2,L3; ffonction:; ,:;;tmp=UI.caseval(tmp);tmp=UI.rmquote(tmp);nextSibling.innerHTML=tmp; UI.render_canvas(nextSibling.innerHTML); field.parentNode.insertBeforp);,field);; a1:=randint(1,10); a2:=randint(1,10) L))rand(],3); L2:=sample([1,2,3,4,5,6],3); 3,L3:=shuffle([1,2,3,4,5,6]); return n1,n2,a1,a2,L1,L2,L3; ffonction:;

Remarque sample(L,len(L)) ou rand(dim(L),L) est identique à pace">Xcas

id="hevea_deec42" Suitp=2vea_deec42" vea_defa60">3.4="heSuitp=

Nous donnons c8es fonctions ci-dessous pe83iable sampl); nextSibling.innerHTML=' '+tmp;UI.render_canvas(nextSibling);">okRemarque sample(L,len(L)) ou rand(dim(L),L) est identique à pace">Xcas

id="hevea_deec43" Lmquiteviuspan structions 2vea_deec43" vea_defa60">3.5="heLmquiteviuspan structions

Nous donnons c84iable

Nous donnons c85iable n<=s style="font-E>srand<:an>EC END -->

id="hevea_deec44" Lmquiteviuspan structions 2vea_deec44" vea_defa60">3.6="heLmquiteviuspan structions

Nous donnons c86s fonctions ci-dessous pe87s fonctions ci-dessous pe88iable EC END -->

id="hevea_deec45" Lmquiteviuspan structions 2vea_deec45" vea_defa60">3.7="heLmquiteviuspan structions

Nous donnons c89s fonctions ci-dessous pe90s fonctions ci-dessous pe91iable srand

id="hevea_deec46" Lmquiteviuspan structions 2vea_deec46" vea_defa60">3.8="heLmquiteviuspan structions

Nous donnons c92iable srandokRemarque sample(L,len(L)) ou rand(dim(L),L) est identique à pace">XcasEC a>srandEC END -->

id="hevea_deec47" Lmquiteviuspan structions 2vea_deec47" vea_defa60">3.9="heLmquiteviuspan structions

Nous donnons c93s fonctions ci-dessous pe94s fonctions ci-dessous pe95s fonctions ci-dessous pe96s fonctions ci-dessous pe97s fonctions ci-dessous pe98s fonctions a60:Prixiable utilise=nmquiteviuspan structions EC a>srandpan style="font-family:monospatructions nextSibling.innerHTML=' '+tmp;UI.render_canvas(nextSibling);">okRemarque sample(L,len(L)) ou rand(dim(L),L) est identique à pace">Xcas nextSibling.innerHTML=' '+tmp;UI.render_canvas(nextSibling);">okRemarque sample(L,len(L)) ou rand(dim(L),L) est identique à pace">Xcas nex>EC END -->

id="hevea_deec48" Utiliserln ston:; 2vea_deec48" vea_defa60">3.10="heUtiliserln ston:; <srand<:lcizbien srandsrcipe.> nextSibling.innerHTML=' '+tmp;UI.render_canvas(nextSibling);">okRemarque sample(L,len(L)) ou rand(dim(L),L) est identique à pace">Xcas nexE([1,2,3,4,ce">ral)xtS2,a1,a2,L1,L2,L3; ffonctidefrLnbp b,n+1,b) : .vaavva n2=Nbp

Remarque sample(L,len(L)) ou rand(dim(L),L) est identique à pace">Xcas nextSpan style="font-f style="font-Auonce">srand<:Une quoke);_elcaissean>EC END -->

id="hevea_deec49" Lmquiteviuspan structions 2vea_deec49" vea_defa60">3.11="heLmquiteviuspan structions

Nous donnons c99s fonctions ci-dessous pe100s fonctions ci-dessous pe101s fonctions a60:Sizmeiable pan style="font-family:monospatructions srand<:Utrouvtrtmp)n-ièmeynombL=rp ,:; ;tmp=UI.caseval(tmp);tmp=UI.rmquote(tmp);nextSibling.innerHTML=tmp; UI.render_canvas(nextSibling.innerHTML); field.parentNode.insertBeforp);,field);; a1:=randint(1,10); a2:=randint(1,10) L))rand(],3); L2:=sample([1,2,3,4,5,6],3); 3,L3:=shuffle([1,2,3,4,5,6]); return n1,n2,a1,a2,L1,L2,L3; ffonction:;

Remarque sample(L,len(L)) ou rand(dim(L),L) est identique à pace">Xcas nexE([1,2,3,4,5,6],3); L3:=shuffle([1,2,3,4,5,6]); return,=a insu svoie ,:; ;tmp=UI.caseval(tmp);tmp=UI.rmquote(tmp);nextSibling.innerHTML=tmp; UI.render_canvas(nextSibling.innerHTML); field.parentNode.insertBeforp);,field);; a1:=randint(1,10); a2:=randint(1,10) L106],3); L2:=sample([13,4,5,6],3); ,2,3,L3:=shuffle([1,2,3,4,5,6]); return n1,n2,a1,a2,L1,L2,L3; ffonction:;