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 3−2,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 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−2y^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+3 où x 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:;

onload

On tape en syntaxe Python : 

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

onload

2.2.3  Définition d’une fonction algébrique d’une variable

Exemple :
On veut définir la fonction f 1f_1 définie pour x∈ℝx \in \mathbb{R}, par f 1(x)=x 2+1f_1(x)=x^2+1.
ff est le nom de la fonction et xx est le nom de l’argument de f 1f_1 (ici xx est un réel), la valeur de la fonction f 1f_1 est x 2+1x^2+1.
Remarque : En mathématique on dit que xx est une variable.
En syntaxe Xcas, on tape simplement :


On pourrait aussi définir f1 par un programme avec fonction...ffonction et retourne :


En syntaxe Python

def f1(x):
    return x^2+1



2.2.4  Définition d’une fonction algébrique de 2 variables

Exemple :
On veut définir la fonction f 2f_2 définie pour (x,y)∈ℝ 2(x,y) \in \mathbb{R}^2, par f 2(x,y)=x 2+y 2f_2(x,y)=x^2+y^2.
f 2f_2 est le nom de la fonction et f 2f_2 a 2 arguments réels : x,yx,y (en mathématique on dit que x,yx,y sont les variables de f 2f_2). La valeur de la fonction f 2f_2 est x 2+y 2x^2+y^2.
On tape simplement :


Ou on tape :


Valeur par défaut d’une variable
On peut définir la valeur par défaut de la variable y et ainsi donner le même nom ff aux 2 fonctions f 1f_1 et f 2f_2 définies précédement.
Ainsi la fonction ff sera définie par :
si elle a une variable xx alors f(x)=x 2+1f(x)=x^2+1 et
si elle a 2 variables x,yx,y alors f(x,y)=x 2+y 2f(x,y)=x^2+y^2.
En syntaxe Xcas, on tape alors simplement :


Ou on tape :






En syntaxe Python:

def f(x,y=1) : 
    return x^2+y^2;






Autre exemple :
On veut définir la fonction gg définie pour (a,b)∈ℕ 2(a,b) \in \mathbb{N}^2 par g(a,b)=q,rg(a,b)=q,r où q,rq,r désigne le quotient et le reste de la division euclidienne de aa par bb.
On tape simplement :


ou bien avec fonction...ffonction et retourne :


gg est le nom de la fonction, a,ba,b sont les noms des arguments de gg (aa et bb sont des entiers) et iquorem renvoie le quotient et le reste de la division euclidienne de aa par bb sous la forme d’une liste.
On a aussi les instructions :
iquo(a,b) qui renvoie le quotient de la division euclidienne de aa par bb.
irem(a,b) qui renvoie le reste de la division euclidienne de aa par bb.
et on a donc iquorem(a,b) est identique à [iquo(a,b),irem(a,b)].


2.2.5  Définition d’une fonction algébrique sans lui donner un nom

On peut définir une fonction sans la nommer, cela permet de la passer en argument d’une autre commande (par exemple une commande de recherche de racines par dichotomie).
En syntaxe Xcas
Par exemple pour définir la fonction x−>x 2+1x-&gt;x^2+1, on écrit simplement :
x->x^2+1.


On tape pour avoir la valeur de cette fonction en x=5x=5 :


(x->x^2+1)(5)
Si on veut donner un nom à la fonction, on tape :
f(x):=x^2+1
puis, on tape :

En syntaxe à la Python
Par exemple pour définir la fonction x−>x 2+1x-&gt;x^2+1, on écrit :
lambda x : x*x+1.
Le logiciel Xcas le traduit en x−>x 2+1x-&gt;x^2+1.
On tape :


Si on veut donner un nom à la fonction, on tape :

def f(x):
    return x*x+1


puis, on tape :

Remarque : il n’y a pas de risques de confusion !
Si vous avez une variable lambda qui est affectée, l’écriture :
(lambda x : x*x+1)(5), ne modifie pas cette variable.
On tape pour définir la fonction lambda :

On tape pour avoir la valeur de la fonction lambda en x=5x=5 :


On tape pour définir une fonction sans nom :


On tape pour avoir sa valeur en x=5x=5 :

2.2.6  Définition d’une fonction algébrique par morceaux avec quand

quand a 3 arguments : une condition (même symbolique) et 2 expressions :
quand(Cond,Expr1,Expr2)
Si la condition Cond est vraie alors quand renvoie Expr1, si la condition Cond est fausse alors quand renvoie Expr2.

Exemple : écriture alternative pour la fonction Abs1 définie par Abs1(x)=|x−1|−1(x)=|x-1|-1, on a :

On tape :


ou bien avec fonction...ffonction et retourne :





Remarque différence entre ifte et quand






Pourquoi une erreur ?
Ici x n’a pas de valeur : avec ifte ou if then else end_if il faut que la variable x soit affectée pour pouvoir tester la condition (quand on définit une fonction ce qui suit le := n’est pas évalué donc la définition de f(x) ne pose pas de problème).
Pour la définition de gg avec when...., la variable x n’a pas besoin dêtre affectée. Il n’y a donc pas d’erreur.





1
En toute rigueur ce sont des nombres écrits en base 2 et non en base 10 mais on peut l’ignorer au niveau du lycée
2
On peut utiliser la syntaxe à la Python au sein de Xcas, mais il faut déclarer les variables locales avec # local (bien mettre un espace entre # et local) et n’utiliser que " (et non ’) comme délimiteur de chaînes de caractères.

Chapitre 3  Les instructions de programmation sur des exemples

On donne ici les instructions en syntaxe Xcas, et en syntaxe Python.

3.1  Commentaires et documentation.

3.1.1  Les commentaires dans un programme.

Pour faire un commentaire, on écrit // (ou # si on a choisi la syntaxe Python), tout ce qui suit est le commentaire.

3.1.2  Documenter une fonction avec la commande help

help(nom_prog) renvoie la 1ère ligne d’un programme (hors commentaire). On peut donc indiquer à la personne utilisant un programme ce que fait ce programme en écrivant comme première ligne du programme une chaîne de caractères commentant la fonction.
Exemple avec la fonction disciminant Delta(a,b,c) qui calcule b 2−4acb^2-4ac.
On tape en syntaxe Xcas : 

fonction Delta(a,b,c) 
  // discriminant
  "calcule b^2-4ac"; 
  return b^2-4a*c;
ffonction:;

onload

On tape en syntaxe Python : 

def Delta(a,b,c) :
    # discriminant
    "calcule b^2-4ac" 
    return b^2-4a*c



3.2  Stocker une valeur dans une variable avec :=

L’opérateur infixé := stocke le deuxième argument dans la variable donnée comme premier argument.
On peut aussi stocker plusieurs valeurs dans plusieurs variables, par exemple : En syntaxe Xcas :
a,b,c:=1,2,3 ou (a,b,c):=(1,2,3) ou [a,b,c]:=[1,2,3]
En syntaxe Python :
(a,b,c)=(1,2,3) ou [a,b,c]=[1,2,3]

Exemple :
En syntaxe Xcas :







En syntaxe Python :







3.3  Enlever une valeur stockée dans une variable avec purge

En syntaxe Xcas : l’instruction purge(a) permet d’enlever une valeur stockée dans la variable a. La variable a redevient une variable libre i.e. une variable non affectée.
En syntaxe Python : l’instruction del a permet d’enlever une valeur stockée dans la variable a.
Exemple :
En syntaxe Xcas :








En syntaxe Python :







3.4  Suite d’instructions avec ; ou :;

En syntaxe Xcas, pour effectuer une suite d’instructions, il suffit d’écrire ces instructions les unes à la suite des autres, en terminant chaque instruction par ;
En syntaxe Xcas, on tape :


En syntaxe Python, on tape :


Notez le signe # qui force l’interpréteur à passer en mode compatible Python.

Remarque :
Lorsque la réponse est trop longue, on peut aussi utiliser :; et on obtient Done comme réponse.


Notez qu’à l’intérieur d’un programme écrit en syntaxe Python le ; n’est pas nécessaire, il suffit de séparer les instructions par un passage à la ligne, en respectant la même indentation que la première instruction.

3.5  L’instruction retourne ou return

L’instruction retourne arrête immédiatement l’exécution du programme et renvoie la valeur de l’instruction située après retourne.

Exemple :
En syntaxe Xcas :







En syntaxe Python :

def Delta(a,b,c) :
    return b^2-4*a*c



def Abs(x) :
    if x>0 :
        return x
    return -x





3.6  L’instruction local

Notion de variables locales:
Supposons qu’on souhaite définir une fonction hh de deux variables a,ba,b (aa et bb sont des entiers) qui renvoie le numérateur et le dénominateur de la fraction ab\frac{a}{b} simplifiée.
Pour cela il faut diviser aa et bb par leur pgcd qui est gcd(a,b).

En syntaxe Xcas, on peut écrire sans utiliser de variables locales :

fonction h0(a,b) 
  retourne (a/gcd(a,b),b/gcd(a,b)); 
ffonction:;

onload
En syntaxe Python 

def h0(a,b) :
     return (a/gcd(a,b),b/gcd(a,b))


Mais on observe que cela nécessite de faire deux fois le calcul de gcd(a,b).

Pour éviter de faire faire à l’ordinateur deux fois le même calcul, on va utiliser une variable locale cc qui servira à stocker le calcul intermédiaire gcd(a,b) avec l’instruction : c:=gcd(a,b) (:= est le symbole de l’affectation et gcd(a,b) renvoie le pgcd de aa et bb).
Cette variable n’est pas visible à l’extérieur du programme, les modifications faites sur c dans le programme n’ont aucun effet sur la variable c de la session.
On écrit en syntaxe Xcas local c; (ne pas oublier le ;). Le langage Python déclare implicitement les variables d’une fonction comme variables locales, aussi en syntaxe Python dans Xcas la déclaration de variables locales se fait par un commentaire Python # local c;.

D’où la définition de la fonction h en utilisant des variables locales
En syntaxe Xcas :

fonction h(a,b) 
  local c;
  c:=gcd(a,b);
  retourne (a/c,b/c); 
ffonction:;

onload








On voit ainsi que les valeurs de a,b,c n’ont pas été changées par l’exécution des fonctions h0 ou h. En syntaxe Python :

def h(a,b) :
    # local c
    c:=gcd(a,b);
    return (a/c),b/c)










Autre exemple :
En syntaxe Xcas :

fonction Racine(a,b,c) 
  //racine x1,x2 de ax^2+bx+c=0
  "calcule b^2-4ac,x1,x2"; 
  local d,x1;x2;
  d=b^2-4a*c;
  x1=(-b+sqrt(d))/(2a);
  x2=(-b-sqrt(d))/(2a);
  retourne b^2-4a*c,x1,x2;
ffonction:;

onload




En syntaxe Python :

def Racine(a,b,c) :
    # racine x1,x2 de ax^2+bx+c=0
    # local d,x1,x2  
    "calcule b^2-4ac,x1,x2"; 
    d=b^2-4a*c
    x1=(-b+sqrt(d))/(2a)
    x2=(-b-sqrt(d))/(2a)
    retourne b^2-4a*c,x1,x2





3.7  L’instruction pour

Exemple de pour : la somme des nombres impairs
On veut, dans cet exemple, définir une fonction Simpair(n) d’une variable n (n est un entier) qui calcule la somme des n premiers entiers impairs i.e. 1+3+...+2n-1.
Pour cela, on utilise une variable locale SS que l’on initialise à 0 :
S:=0;
puis on va faire nn étapes en utilisant cette variable locale SS.
SS va contenir successivement :
étape 1 S:=S+(2*1−1);S:=S+(2*1-1); donc SS contient 1 (0+1)
étape 2 S:=S+(2*2−1);S:=S+(2*2-1); donc SS contient 4 (1+3)
...
étape kk S:=S+(2*k−1);S:=S+(2*k-1); donc SS contient 1+3+..2k−11+3+..2k-1
...
étape nn S:=S+2*n−1;S:=S+2*n-1; donc SS contient 1+3+..2n−11+3+..2n-1
En syntaxe Xcas, on utilise une boucle pour :
pour k de 1 jusque n faire S:=S+2*k-1; fpour;
En syntaxe Python, on utilise une boucle for : 

for k in range(1,n+1): 
    S:=S+2*k-1

Dans cette boucle k sera successivement égal à 1, 2, 3,...n.
On dit que l’instruction S:=S+2*k-1 figurant dans le corps la boucle sera exécuté n fois.
Comment fonctionne cette boucle pour ?

En syntaxe Xcas : 

fonction Simpair(n) 
  local S,k;
  S:=0; 
  pour k de 1 jusque n faire 
    S:=S+2*k-1; 
  fpour;
  retourne S; 
ffonction:;

onload

En syntaxe Python : 

def Simpair(n):
    # local S,k
    S=0
    for k in range(1,n+1):
        S=S+2*k-1 
    return(S)



On pourra vérifier le résultat, en utilisant la commande sum de Xcas :

Intermède mathématique
1,3,5,7,9,11, Au vue des résultats obtenus pouvez-vous deviner la valeur de s(100) ?
Pouvez-vous deviner et montrer la formule qui donne s(n) ?
On devine : s(n)=1+3+...2n−1=n 2s(n)=1+3+...2n-1=n^2
On sait que pour tout k∈ℕk \in \mathbb{N} on a :
k 2−(k−1) 2=((k−1)+1) 2−(k−1) 2=2k−1k^2-(k-1)^2=((k-1)+1)^2-(k-1)^2=2k-1 et
(k+1) 2−k 2=2k+1(k+1)^2-k^2=2k+1
Donc :
1=1 2−0 21=1^2-0^2 (k=1k=1),
3=2 2−1 23=2^2-1^2 (k=2k=2),
5=3 2−2 25=3^2-2^2 (k=3k=3),
...
2k−1=k 2−(k−1) 22k-1=k^2-(k-1)^2
2k+1=(k+1) 2−(k) 22k+1=(k+1)^2-(k)^2
...
2n−1=n 2−(n−1) 22n-1=n^2-(n-1)^2
Donc :
s(n)=1+3+...2n−1=1+(n) 2=1+(4−1)+(9−4)...+(n 2−(n−1) 2)=n 2s(n)=1+3+...2n-1=1+(n)^2=1+(4-1)+(9-4)...+(n^2-(n-1)^2)=n^2
En classe de terminales, on peut montrer cette formule par récurrence :
s(1)=1s(1)=1 si s(n)=(n) 2s(n)=(n)^2 alors on a :
s(n+1)=s(n)+2(n+1)−1=(n) 2+2n+1=(n+1) 2s(n+1)=s(n)+2(n+1)-1=(n)^2+2n+1=(n+1)^2
La formule est donc montrée par récurrence.

3.8  L’instruction pour avec un pas

Exemple de pour avec un pas : la somme des nombres impairs
Revenons à l’exemple précédent :
définir une fonction Simpair(n) d’une variable n (n est un entier) qui calcule la somme : 1+3+...+2n-1.
Avec la syntaxe Xcas, on peut faire varier la variable k avec un pas de 2, en commencant par 1 jusque 2n-1, on écrit :
pour k de 1 jusque 2*n-1n pas 2 faire fpour;
Dans ce cas la valeur de S doit être augmentée à chaque pas de la valeur k.
On tape en syntaxe Xcas : 

fonction Simpair1(n) 
 local S,k;
 S:=0; 
 pour k de 1 jusque 2*n-1 pas 2 faire 
   S:=S+k; 
 fpour;
 retourne S; 
ffonction:;

onload

On tape en syntaxe Python : 

def Simpair1(n):
    # local S,k
    S=0
    for k in range(1,2*n,2):
       S=S+k 
    return(S)



Autre exemple de pour avec un pas : le ticket de caisse
On veut faire le programme d’un ticket de caisse lors d’achats dans un magasin qui ne pratique pas de réduction pour les achats en gros.
Le programme du ticketcaisse a comme paramètre une liste L donnant le nombre d’un même article suivi du prix de cet article, par exemple :
si L:=[2,24,1,15,5,10] cela signifie qu’il y 2 articles à 24 euros, 1 article à 15 euros et 5 articles à 10 euros.
Soit n:=dim(L), dans cet esxemple n:=6.
On va parcourir la liste avec une variable k : L[k] sera le nombre d’articles ayant comme prix L[ k+1] : il faut donc, dans cet exemple, que k prenne successivement pour valeur 0, 2, 4=n-2.
Pour cela on initialise la somme à payer avec 0 : S:=0 puis
on utilise une boucle pour avec un pas de 2 :
pour k de 0 jusque n-2 pas 2 faire S:=S+L[k]*L[k+1]; fpour;
Dans cette boucle pour, la variable k est initialisée à 0, puis les instructions du corps de la boucle sont effectuées, puis k est incrémenté automatiquement de 2 (k:=k+2),
puis on fait le test k<=n-2 si oui les instructions du corps de la boucle sont à nouveau effectuées etc ... sinon on effectue les instructions qui suivent fpour.
En syntaxe Xcas : 

fonction Ticketcaisse(L) 
 local S,n,k;
 n:=dim(L);
 S:=0;
 pour k de 0 jusque n-2 pas 2 faire S:=S+L[k]*L[k+1]; fpour;
 retourne S; 
ffonction:;

onload




En syntaxe Python : 

def Ticketcaisse(L) :
    # local S,n,k
    n=size(L)
    S=0
    for k in range(0,n-1,2) :
        S=S+L[k]*L[k+1]
    retourne S





3.9  L’instruction si

Lorsque l’on veut faire des instructions seulement si une condition est réalisée on utilise l’instruction si.
Cette instruction a 2 formes :
En syntaxe Xcas :
si <condition> alors <instruction>; fsi;
et
si <condition> alors <instruction1>; sinon <instruction2> fsi;
Comment fonctionne le test si ... alors ... fsi ?

Comment fonctionne le test si ... alors ...sinon ... fsi ?

En syntaxe Python : 

if <condition> : 
   <instruction>

et 

if <condition> : 
   <instruction1>
else :
    <instruction2>

Exemple de si alors fsi : somme des nombres premiers <= n
Rappel Un nombre premier est un entier nn qui admet 2 diviseurs qui sont 1 et nn, par exemple : 17 est un nombre premier et 1 4 ne sont pas des nombres premiers.
On veut définir une fonction Spremier(n) d’une variable n (n est un entier) qui calcule la somme des nombres premiers inférieurs ou égaux à n : 2+3+5+7+11...+p pour p premier et p<=n. Pour cela on utilisera la fonction booléenne est_premier de Xcas qui teste si un nombre entier est premier.
Si est_premier(k)==vrai et si k<=n alors la valeur de S doit être augmentée de la valeur k.
Pour cela, on utilise une variable locale S (la somme) et le test.
En syntaxe Xcas :
si est_premier(k) alors S:=S+k fsi;
En syntaxe Python :

if est_premier(k): 
    S:=S+k

À part le nombre 2 les nombres premiers sont impairs, donc on initialise S à 2 puis, on fait varier k de 3 jusque n avec un pas de 2.
En syntaxe Xcas : 

fonction Spremier(n) 
 local S,k;
 S:=2; 
 pour k de 3 jusque n pas 2 faire 
   si est_premier(k) alors S:=S+k fsi; 
 fpour;
 retourne S; 
ffonction:;

onload


En syntaxe Python : 

def Spremier(n):
    # local S,k
    S=2
    for k in range(3,n+1,2):
        if est_premier(k) :
            S=S+k 
    return(S)




Exercice : combien y-a-t-il de nombres premiers <= n ?
Modifier l’algorithme précédent pour définir la fonction Nbpremiers(n) d’une variable n (n est un entier) qui calcule le nombre de nombres premiers qui sont inférieurs ou égaux à n.
En syntaxe Xcas : 

fonction Nbpremiers(n) 
 local S,k,N;
 si n<2 alors retourne 0 fsi;
 N:=1; 
 pour k de 3 jusque n pas 2 faire 
   si est_premier(k) alors N:=N+1 fsi; 
 fpour;
 retourne N; 
ffonction:;

onload


En syntaxe Python : 

def Nbpremiers(n):
    # local S,k,N
    if n<2 :
        retourne 0
    N=1
    for k in range(3,n+1,2) :
        if est_premier(k) :
            N=N+1 
    return(N)



On pourra vérifier le résultat, en utilisant la commande nprimes de Xcas :

Autre exemple du test si alors sinon fsi : le ticket de caisse
Dans un magasin on favorise les achats en gros :
si un article a a comme prix affiché P euros, pour l’achat d’au moins 3 articles a, vous avez une réduction de 10%.
On veut, dans cet exemple, définir une fonction Prix de 2 variables n (n est un entier) et P un réel qui calcule le prix de n article(s).
Pour cela, on utilise :
En syntaxe Xcas, une variable locale S qui sera la somme à débourser et le test :si alors sinon fsi;
En syntaxe Python, on utilise le test :

if <condition> :
    <instruction1> 
else : 
    <instruction2>

En syntaxe Xcas : 

fonction Prix(n,P) 
 local S;
 si n>=3 alors S:=n*P*0.9; 
 sinon S:=n*P; fsi;
 retourne S;
ffonction:;

onload




En syntaxe Python : 

def Prix(n,P) :
    # local S
    if n>=3 :
        S:=n*P*0.9
    else :
        S:=n*P
    return S






3.10  Utiliser une fonction utilisateur dans un programme

Exemple : combien de nombres premiers dans [1,b],[b+1,2b]..[(p-1)b+pb] ? On veut définir une fonction Lnbpremiers(b,p) de paramètres 2 entiers qui renvoie une liste de p entiers qui sont le nombre de nombres premiers compris entre 1 et b,b+1 et 2b ... (p-1)*b+1 et p*b de nombres premiers entre 0 et p*b=n.
Par exemple si b=10 et p=3 Lnbpremiers(b,p) doit renvoyer: [4,4,2] puisque :
entre 1 et 10 il y a 4 nombres premiers (2,3,5,7),
entre 11 et 20 il y a 4 nombres premiers (11,13,17,19),
entre 21 et 30 il y a 2 nombres premiers (23,29).
Pour cela on utilisera la fonction utilisateur Nbpremiers écrite précédemment en exercice.
En syntaxe Xcas : 

fonction Lnbpremiers(b,p)
  local L,k,n1,n2,n;
  L:=NULL;
  n:=p*b;
  n1:=Nbpremiers(1);
  pour k de b jusque n pas b faire 
     n2:=Nbpremiers(k);
     L:=L,n2-n1;
     n1:=n2;
  fpour;
  retourne [L];
  ffonction:;

onload




En syntaxe Python : 

def Lnbpremiers(b,p) :
    # local L,k,n1,n2,n
    L=[]
    n=p*b
    n1=Nbpremiers(1)
    for k in range(b,n+1,b) : 
        n2=Nbpremiers(k)
        L.append(n2-n1)
        n1=n2
    return L;






Autre exemple : le ticket de caisse
On veut faire le programme du ticket de caisse lorsque le magasin pratique l’achat en gros (la liste L doit spécifier le nombre nn d’un même article de prix PP).
En utilisant la fonction Prix(n,P) écrite précédemment (cf 3.9), modifier le programme précédent lorsque le magasin pratique l’achat en gros.
En syntaxe Xcas : 

fonction Ticketengros(L) 
 local S,n,k; 
 n:=dim(L);
 S:=0;
 pour k de 0 jusque n-2 pas 2 faire 
   S:=S+Prix(L[k],L[k+1]); 
 fpour;
 retourne S; 
ffonction:;

onload




En syntaxe Python : 

def Ticketengros(L) :
    # local S,n,k 
    n=dim(L)
    S=0
    for k in range(0,n-1,2) : 
        S=S+Prix(L[k],L[k+1]) 
    return S





3.11  L’instruction tantque

Notion de boucle tantque
On utilise une boucle tantque lorsque l’on ne connaît pas à l’avance le nombre d’itérations à effectuer et que l’on arrête les itérations quand une condition devient fausse.
En syntaxe Xcas :
tantque <condition> faire <instructions> ftantque;
En syntaxe Python :

while  <condition> :
    <instructions>

Comment fonctionne une boucle tantque ?

ou bien on peut dire en langage courant que :
<condition> est une condition de continuation de la boucle. tant que la condition est vérifiée, on fait les instructions de la boucle.
Traduction d’une boucle pour en une boucle tantque
Exemple : somme des éléments d’une liste Soit une liste L de nombres réels.
On veut faire la somme des réels de L.
En syntaxe Xcas :
On tape en utilisant une boucle pour : 

fonction Somme(L) 
 local n,j,S;
 n:=dim(L);
 S:=0;
 pour j de 0 jusque n-1 faire
   S:=S+L[j];
 fpour;
 retourne S;
ffonction:;

onload
On tape en utilisant une boucle tantque : 

fonction Somme1(L) 
 local n,j,S;
 n:=dim(L);
 S:=0;
 j:=0;
 tantque j <= n-1 faire
   S:=S+L[j];
   j:=j+1;
 ftantque;
 retourne S;
ffonction:;

onload
On peut aussi écrire Somme2, mais Attention à l’ordre des instructions de la boucle tantque et au test d’arrêt : 

fonction Somme2(L) 
 local n,j,S;
 n:=dim(L);
 j:=0;
 S:=L[0];
 tantque j < n-1 faire
   j:=j+1;
   S:=S+L[j];
 ftantque;
 retourne S;
ffonction:;

onload








En syntaxe Python :
On tape en utilisant une boucle pour : 

def Somme(L) :
    # local n,j,S
    n=dim(L)
    S=0
    for j in range(n) :
        S:=S+L[j]
    return S


On tape en utilisant une boucle tantque : 

def Somme1(L) :
    # local n,j,S
    n=dim(L)
    S=0
    j=0
    while j <= n-1 :
        S=S+L[j]
        j=j+1
    return S


On peut aussi écrire Somme2, mais Attention à l’ordre des instructions de la boucle tantque et au test d’arrêt : 

def Somme2(L) :
    # local n,j,S
    n=dim(L)
    j=0
    S=L[0]
    while j < n-1 :
        j=j+1
        S=S+L[j]
    return S;










On peut vérifier ces résultats avec la fonction sum de Xcas :


Autre exemple : trouver le n-ième nombre premier On veut définir une fonction Niemeprem(n) qui renvoie le nième nombre premier.
On utilise, pour cela la fonction booléenne est_premier (ou is_prime) de Xcas qui teste si un nombre entier est premier.
A part le nombre 2, les nombres premiers sont impairs, donc on traite le cas de 2, puis on initialise k à 3 et on fait varier k avec un pas de 2. En syntaxe Xcas : 

fonction Niemeprem(n)
  local k,p;
  si n==1 alors retourne 2; fsi;
  k:=3;p:=1;
  tantque p<n faire
    si est_premier(k) alors p:=p+1; fsi;
    k:=k+2;
  ftantque;
  retourne k-2;
ffonction:;

onload


En syntaxe Xcas avec un pour : 

fonction Niemeprem1(n)
  local k,p;
  si n==1 alors retourne 2; fsi;
  p:=1;
  pour k de 3 jusque 100*n pas 2 faire
    si est_premier(k) alors p:=p+1; fsi;
    si p==n alors break; fsi;
  fpour;
  retourne k;
ffonction:;

onload


En syntaxe Python : 

def Niemeprem(n) :
    # local k,p
    if n==1 :
        return 2
    k=3
    p=1
    while p<n :
        if isprime(k) : 
            p=p+1
        k:=k+2
    return k-2




On pourra vérifier le résultat du programme car cette fonction existe dans Xcas c’est ithprime(n)


En syntaxe Python avec un for: 

def Niemeprem1(n) :
    # local k,p
    if n==1 :
        return 2
    p=1
    for k in range(3,100*n,2) :
        if isprime(k) :
           p:=p+1
        if p==n :
           break;
    return k;




3.12  Un exercice et un problème

3.12.1  Exercice

On veut définir une fonction Snpremiers(n) d’une variable n (n est un entier positif) qui calcule la somme des n premiers nombres premiers. On utilise, pour cela la fonction booléenne est_premier (ou is_prime) de Xcas qui teste si un nombre entier est premier.
A part le nombre 2, les nombres premiers sont impairs, donc on initialise S à 2 et k à 3 avec un pas de 2.
En syntaxe Xcas, (l’indice j compte les nombres premiers, l’indice k sert à chercher les nombres qui sont premiers) : 

fonction Snpremiers(n)
  local S,k,p,j;
  j:=1;
  S:=2;
  k:=3;
  tantque j< n faire
     si est_premier(k) alors 
       S:=S+k;
       j:=j+1;
     fsi;
     k:=k+2;
  ftantque;
  retourne S;
ffonction:;




En syntaxe Xcas, avec un pour : 

fonction Snpremiers1(n)
  local S,k,p,j;
  j:=1;
  S:=2;
  pour k de 3 jusque 100*n pas 2 faire
     si est_premier(k) alors 
       S:=S+k;
       j:=j+1;
     fsi;
     si j==n alors break; fsi
  fpour;
  retourne S;
ffonction:;




En syntaxe Python, (l’indice j compte les nombres premiers, l’indice k sert à chercher les nombres premiers) : 

def Snpremiers(n) :
    # local S,k,p,j
    j=1
    S=2
    k=3
    while j< n :
        if is_prime(k) : 
            S=S+k
            j=j+1
        k=k+2
    return S




En syntaxe Python avec un for : 

def Snpremiers1(n) :
    # local S,k,p,j
    j=1
    S=2
    for k in range(3,100*n,2) :
        if is_prime(k) : 
            S=S+k
            j=j+1
        if j==n :
            break
    return S


3.12.2  Problème : le crible d’Eratosthène

3.12.3  Description

Pour trouver les nombres premiers inférieurs ou égaux à NN :

  1. On écrit les nombres de 2 à NN dans une liste TABTAB.
  2. On met 2 dans la case PP .
  3. Si P×P≤NP \times P \leq N il faut traiter les éléments de PP à NN : on barre tous les multiples de PP à partir de P×PP \times P.
  4. On augmente PP de 1.
    Si P×PP\times P est strictement supérieur à NN, on arrête
  5. On met le plus petit élément non barré de la liste dans la case PP. On reprend à l’étape 3.
  6. on met les éléments non nuls de TABTAB dans une liste PREMPREM.

3.12.4  Écriture de l’algorithme

Fonction crible(N)
 local TAB PREM I P
 // TAB et PREM sont des listes
 //=> est le STO des calculatrices
 [] =>TAB
 [] =>PREM
 //on suppose que les indices d'une liste debutent par 0
 pour I de 0 a N faire 
  TAB:=concat(TAB, I)
 fpour
 //On met 0 dans TAB[1] car 1 n'est pas premier
 //barrer 1 a ete realise en le remplacant par 0
 TAB[1]:=0
 //TAB est la liste 0 0 2 3 4 ...N 
 P:=2
 // On a fait les points 1 et 2
 tantque P*P <= N faire
  pour I de P jusque E(N/P) faire
    //E(N/P) designe la partie entiere de N/P
    TAB[I*P]:=0
  fpour
  // On a donc barre tous les multiples de P a partir de P*P
  P:=P+1
  //On cherche le plus petit nombre <= N non barre (i.e. non nul)
  // entre P et N
  tantque (P*P <= N) et (TAB[P]=0) faire
    P=P+1
  ftantque
 ftantque
 //on ecrit le resultat dans une liste PREM
 pour I de 2 a N faire
  si TAB[I]!= 0 alors 
     PREM:=concat(PREM, I)
  fsi
 fpour
 retourne PREM

3.12.5  En syntaxe Xcas

Première version

//renvoie la liste des nombres premiers<=n selon Eratosthene
crible0(n):={
  local tab,prem,p,j;
  tab:=[0,0];
  prem:=[];
  pour j de 2 jusque n faire
    tab:=append(tab,j);
  fpour;
  p:=2;
  tantque (p*p<=n) faire
    pour j de p jusque floor(n/p) faire
      tab[j*p]:=0;
    fpour
    p:=p+1;
    tantque ((p*p<=n) et (tab[p]==0)) faire
      p:=p+1;
    ftantque;
  ftantque;
  pour j de 2 jusque n faire
    si (tab[j]!=0) alors 
      prem:=append(prem,j);
    fsi
  fpour
  retourne(prem);
}:;

onload




L’instruction time affiche le temps d’exécution de la commande.

Une version plus efficace

  1. On utilise seq pour définir tab et on remplace les affectations := par des affectations par référence =<. 
    tab:=[0,0];
pour j de 2 jusque n faire
 tab:=append(tab,j);
fpour;
    par 
    tab:=seq(j,j,0,n);
tab[0]=<0; tab[1]=<0;
  2. On remplace tout d’abord les affectations := d’éléments d’une liste par une affectation par référence =< c’est à dire sans recopier la liste à chaque fois qu’on en modifie un élément, ce qui est plus efficace.
  3. Puis, lorsque qu’on barre les multiples de p premier on remplace les multiplications de tab[eval(j*p)]:=0; par des additions on faisant varier j avec un pas : On remplace donc 
    pour j de p jusque floor(n/p) faire
   tab[j*p]:=0;
fpour;
    par 
    pour j de p*p jusque n pas p faire
    tab[j]=<0;
fpour;

On obtient : 

//renvoie la liste des nombres premiers<=n selon Eratosthene
crible(n):={
  local tab,prem,p,j;
  tab:=seq(j,j,0,n);
  tab[0]=<0; tab[1]=<0; 
  prem:=[];
  p:=2;
  tantque (p*p<=n) faire
    pour j de p*p jusque n pas p faire
      tab[j]=<0;
    fpour
    p:=p+1;
    tantque ((p*p<=n) et (tab[p]==0)) faire
      p=<p+1;
    ftantque;
  ftantque;
  pour j de 2 jusque n faire
    si (tab[j]!=0) alors 
      prem:=append(prem,j);
    fsi
  fpour
  retourne(prem);
}:;

onload



3.12.6  En syntaxe Python

Première version

# renvoie la liste des nombres premiers<=n selon Eratosthene
def crible0(n) :
    # local tab,prem,p,j
    tab =[0,0]
    prem =[]
    for j in range(2,n+1) :
        tab.append(j)
    p=2
    while p*p<=n :
        for j in range(p,floor(n/p)+1) :
            tab[j*p]=0 
        p=p+1
        while p*p<=n and tab[p]==0 :
            p=p+1
    for j in range(2,n+1) :
        if tab[j]!=0 : 
            prem.append(j)
    return prem





Une version plus efficace

# renvoie la liste des nombres premiers<=n selon Eratosthene
def crible(n) :
    # local tab,prem,p,j
    tab=range(0,n+1)
    tab[0]=<0; tab[1]=<0 
    prem=[]
    p=2
    while p*p<=n :
        for j in range(p*p,n+1,p) :
            tab[j]=<0
        p=p+1
        while p*p<=n and tab[p]==0 :
            p=p+1
    for j in range(2,n+1) :
        if tab[j]!=0 :
            prem.append(j)
    return prem;





3.13  Autre exemple de boucle tantque : le ticket de caisse

En fin de mois, Paul n’a plus qu’une somme a dans son porte-monnaie. Paul fait sa liste de courses Lc en mettant au début ce qu’il veut vraiement acheter et à la fin de sa liste, il met les achats qu’il doit faire à plus long terme. Dans le magasin (qui ne fait pas de réduction), sa liste de courses Lc devient une liste de prix L.
Dans ce cas, on ne peut pas utiliser une boucle avec pour car on ne sait pas au départ combien de fois on doit effectuer la boucle.
On note S la variable qui stockera successivement la somme des prix des premiers éléments de L : pour cela on utilise la fonction Somme(L) écrite précedemment (cf 3.11).
Il veut faire un programme qui arrête sa liste dès que S>a en coupant L en 2 listes : La liste des objets de ce qu’il achète réellement pour un montant S<=a et Lfin liste des objets qu’il n’achète pas (Lfin est une liste vide lorsque Somme(L)<=a).
Ticketfindemois(L,a) doit renvoyer La,Lfin,P où P est la somme à payer.
"arrêt" se traduit ici par Lfin ==[] ou S>a donc
"continuation" se traduit ici par Lfin!=[] et S<=a.
On teste tout d’abord si Paul a assez d’argent pour payer toute sa liste : pour cela, on utilise le programme Somme précédent (cf 3.11).
Paul a assez d’argent pour payer toute sa liste lorsque Somme(L)<=a et alors on a La :=L, Lfin :=[] et P:=Somme(L).
Si Somme(L)>a, Paul n’a pas assez d’argent donc Lfin!=[] est vrai et la condition d’arrêt est : S<=a. On écrit Ticketfindemois(L,a) pour que k soit le nombre d’articles achetés lorsqu’ on sort du tantque.
En syntaxe Xcas : 

fonction Ticketfindemois(L,a) 
 local S,n,k,Lfin,La;
 S:=Somme(L);
 si S <=a alors retourne L,[],S fsi;
 n:=dim(L);
 k:=0;
 S:=L[0];
 tantque S <=a faire 
   k:=k+1;
   S:=S+L[k];
  ftantque;
 La:=gauche(L,k);
 Lfin:=droit(L,n-k);
 retourne La,Lfin,S-L[k];
ffonction:;

onload








En syntaxe Python : 

def Ticketfindemois(L,a) : 
    # local S,n,k,Lfin,La
    S=Somme(L)
    if S <=a :
        return L,[],S
    n=dim(L)
    k=0
    S=L[0]
    while S <=a : 
        k=k+1
        S=S+L[k]
    La:=gauche(L,k)
    Lfin:=droit(L,n-k)
    return La,Lfin,S-L[k]










On peut aussi écrire mais Attention à l’ordre des instructions dans le tantque. En syntaxe Xcas : 

fonction Ticketfindemois1(L,a) 
 local S,n,k,Lfin,La;
 S:=Somme(L);
 si S <=a alors retourne L,[],S fsi;
 n:=dim(L);
 S:=0;
 k:=0;
 tantque S <=a faire 
   S:=S+L[k];
   k:=k+1;
 ftantque;
 La:=gauche(L,k-1);
 Lfin:=droit(L,n-k+1);
 retourne La,Lfin,S-L[k-1];
ffonction:;

onload








Dans Ticketfindemois1, c’est k-1 et non k, qui est pas la valeur du nombre d’articles achetés lorsqu’on sort du tantque.
En effet, lorsqu’on s’arrête SS devient supérieur à aa : il ne faut donc pas acheter l’article L[k].
Donc La:=gauche(L,k-1); et Lfin:=droit(L,n-k+1).
Remarque
On aurait pu aussi écrire sans utiliser Somme mais c’est plus compliqué car la condition du tantque porte sur k et sur S !!! En syntaxe Xcas : 

fonction Ticketfindemois2(L,a) 
  local S,n,k,La,Lfin,P;
  n:=dim(L);
  k:=0;
  S:=L[0];
  tantque S<=a et k<n-1 faire
    k:=k+1;
    S:=S+L[k];
  ftantque;
  si S<=a alors retourne L,[],S fsi;
  La:=gauche(L,k);
  Lfin:=droit(L,n-k);
  P:=S-L[k];
 retourne La,Lfin,P;
ffonction:;


À chaque étape on a :
Au début, on a :
k:=0;S:=L[0]; donc S est le prix de 1 article.
lorsqu’on fait kk fois la boucle on a :
S:=L[0]+..L[k]; donc S est la somme de k+1 articles.
Quand on sort du tantque on a :
soit S<=a est vrai, donc k==n-1 est vrai (puisque (S<=a et k<n-1)==faux).
S est donc la somme de toute la liste L i.e. S est la somme à payer pour l’achat de n articles i.e. Paul peut acheter toute sa liste de courses.
soit S>a et k<=n-1 alors S représente la somme des prix des k+1 premiers articles (k+1 car on a commencé à l’article k=0. Mais Paul ne peut pas acheter le dernier article puisque S>a. Le prix P représente la somme des prix des k premiers articles i.e.des articles L[0],..L[k-1] ou encore des artices de la liste gauche(L,k) donc P:=S-L[k].







3.14  Interruption d’une boucle

Si on utilise retourne à l’intérieur d’une boucle dans une fonction, celle-ci est interrompue. Ceci permet de transformer des boucles "tantque" en boucle "pour" souvent plus lisibles.

Reprenons l’exemple ci-dessus, on remarque que la boucle tantque utilise un compteur k qu’on incrémente à chaque itération comme dans une boucle pour. Il est donc naturel d’essayer de réécrire cette fonction avec une boucle pour. Il suffira de tester dans le corps de la boucle si la somme (avec le nouvel article) dépasse le contenu du porte-monnaie, dans ce cas il faut s’arrêter sans acheter le nouvel article, on interrompt la boucle et on renvoie les résultats (on calcule la somme au fur et à mesure et donc on n’utilise pas la fonction Somme). Dans Ticketfindemois3, c’est k, qui est pas la valeur du nombre d’articles achetés lorsqu’on sort du pour.
En effet, lorsqu’on s’arrête SS devient supérieur à aa : il ne faut donc pas acheter l’article L[k].
Donc La:=gauche(L,k); et Lfin:=droit(L,n-k).
En syntaxe Xcas : 

fonction Ticketfindemois3(L,a)
  local k,n,S,La,Lfin;
  n:=dim(L);
  S:=0;
  pour k de 0 jusque n-1 faire
    si S+L[k]>a alors 
      La:=gauche(L,k);
      Lfin:=droit(L,n-k);
      retourne La,Lfin,S;
    fsi;
    S:=S+L[k];
  fpour;
  retourne L,[],S;
ffonction:;

onload








En syntaxe Python: 

def Ticketfindemois3(L,a):
    # local k,n,S,La,Lfin
    n=dim(L)
    S=0
    k=0
    for k in range(n) :        
        if (S+L[k])>a :
            La=gauche(L,k)
            Lfin=droit(L,n-k)
            return La,Lfin,S
        S=S+L[k]
    return(L,[],S)










Cette méthode s’applique pour toute boucle tantque dont on peut prévoir à priori un majorant du nombre d’itérations. On peut d’ailleurs aussi l’utiliser si on se fixe un nombre maximal d’itérations qui tient compte du temps d’exécutions, typiquement en Xcas de l’ordre du million d’itérations si on veut un résultat en moins de quelques secondes.

Remarque : si on ne veut pas quitter la fonction, il est quand même possible d’interrompre la boucle prématurément en utilisant l’instruction break.

3.15  Autre exemple de boucle tantque : le ticket de caisse

Pour avoir des clients le dimanche matin, le magasin de Paul offre selon les dimanches une réduction immédiate rr qui varie selon le montant aa des achats par exemple une réduction de 10 euros dès 60 euros d’achats, ou une réduction de 5 euros dès 50 euros d’achats etc...
Ce magasin ne pratique pas de réduction pour des achats en gros.
Pour être sûr de bénéficier de la réduction, Paul fait sa liste de courses LcLc en mettant au début ce qu’il veut vraiement acheter et à la fin de sa liste, il met les achats qu’il doit faire à plus long terme (contrairement au programme précédent, on suppose ici que Paul a suffisamment d’argent).
Attention
On suppose ici que la liste de courses est constituée par une suite des nombres nn,PP où nn est le nombre d’achats du même article de prix PP.
Il veut faire un programme qui arrête sa liste dès que S>=aS&gt;=a en coupant LcLc en 2 listes LaLa liste des objets de ce qu’il achète réellement pour un montant SS avant réduction et LfinLfin liste des objets qu’il n’achète pas (LfinLfin est éventuellement une liste vide).
Paul veut que son programme ait paramètres Lc,a,rLc,a,r et qu’il renvoie :
LaLa, LfinLfin, SS, S−rS-r.
Dans ce cas, on ne sait pas au départ combien de fois on doit effectuer la boucle.
Mais on sait quand on doit s’arrêter :
on arrête la boucle lorsque le prix SS de la liste complète LcLc n’atteint pas le montant aa ou dés que le prix SS du début de LcLc vérifie S>=a.
On utilise pour cela une boucle tantque :
tantque <condition> faire <instructions> ftantque;
Cela veut dire :
tant que "non arrêt", on fait les instructions de la boucle.
"arrêt" se traduit ici par Lfin ==[] ou S>=a donc,
"non arrêt" se traduit ici par Lfin!=[] et S<a.
Attention la variable kk qui va parcourir la liste L devra être initialisée (ici k:=0;) et modifiée dans le corps de la boucle (ici k:=k+2;).
La fonction Ticketdimanche a 3 paramètres L,a,r et renvoie la liste LaLa des courses qui ont été prises en compte,
la liste LfinLfin des courses qui n’ont pas été prises en compte (cette liste peut être vide si S<=a)
la somme S des achats sans la remise et
la somme S-r à payer.
En syntaxe Xcas : 

fonction Ticketdimanche(L,a,r) 
 local S,n,k,Lfin,La; 
 n:=dim(L);
 S:=0;
 k:=0;
 tantque k<n et S<a faire 
   S:=S+L[k]*L[k+1];
   k:=k+2;
 ftantque;
 La:=gauche(L,k);
 Lfin:=droit(L,n-k);
 si S<a alors r:=0; fsi;
 retourne La,Lfin,S,S-r;
ffonction:;

onload







En syntaxe Python : 

def Ticketdimanche(L,a,r) :
    # local S,n,k,Lfin,La 
    n=dim(L)
    S=0
    k=0
    while k<n and S<a : 
        S=S+L[k]*L[k+1]
        k=k+2
    La=gauche(L,k)
    Lfin=droit(L,n-k)
    if S<a :
        r=0
    return La,Lfin,S,S-r









Traduction du “tantque” en “pour”
On remarque que la boucle “tantque” a un compteur k, on peut donc la transformer en boucle “pour” avec sortie prématurée de la boucle lorsque S>aS&gt;a.
Attention gauche(L,k) représente les k premiers éléments de L i.e c’est L[0]..L[k-1].
Ici, on sort de la boucle pour lorsque S>=a donc pour avoir la réduction il faut acheter L[k] fois l’article L[k+1], c’est à dire prendre en compte la liste L[0].. L[k+1] qui est une liste de k+2 éléments c’est donc gauche(L,k+2). En syntaxe Xcas : 

fonction Ticketdimanche1(L,a,r) 
 local S,n,k,Lfin,La; 
 n:=dim(L);
 S:=0;
 pour k de 0 jusque n-1 pas 2 faire
   S:=S+L[k]*L[k+1];
   si S>=a alors 
     La:=gauche(L,k+2); 
     Lfin:=droit(L,n-k-2); 
     retourne La,Lfin,S,S-r;
   fsi;
 fpour;
 retourne L,[],S,S;
ffonction:;









En syntaxe Python : 

def Ticketdimanche1(L,a,r):
    # local S,n,k,Lfin,La
    n=dim(L)
    S=0
    for k in range(0,n,2):
        S=S+L[k]*L[k+1]
        if S>=a :
            La=gauche(L,k+2)
            Lfin=droit(L,n-k-2)
            return La,Lfin,S,S-r
    return L,[],S,S









3.16  Encore un exemple de boucle tantque : le ticket de caisse

Maintenant le magasin de Paul favorise aussi les achats en gros : 10% de réduction lorsque on achète 3 fois le même produit. En plus il offre selon les dimanches une réduction immédiate rr qui varie selon le montant aa des achats, par exemple une réduction de 10 euros dès 60 euros d’achats.
Modifier les programmes précédents pour tenir compte des achats en gros. On utilise ici la fonction Prix écrite précédemment (cf 3.9).
Attention comme précédemment on suppose ici que la liste de courses est constituée par une suite des nombres nn,PP où nn est le nombre d’achats du même article de prix PP.
En syntaxe Xcas : 

fonction Ticketdimgros(L,a,r) 
 local S,n,k,Lfin,La; 
 n:=dim(L);
 S:=0;
 k:=0;
 tantque k < n et S<a faire 
   S:=S+Prix(L[k],L[k+1]);
   k:=k+2;
 ftantque;
 La:=gauche(L,k);
 Lfin:=droit(L,n-k);
 si S < a alors r:=0 ;fsi;
 retourne La,Lfin,S,S-r;
ffonction:;

onload






En syntaxe Python : 

def Ticketdimgros(L,a,r) :
    # local S,n,k,Lfin,La 
    n=dim(L)
    S=0
    k=0
    while k < n and S<a :
        S=S+Prix(L[k],L[k+1])
        k=k+2
    La=gauche(L,k)
    Lfin=droit(L,n-k)
    if S < a :
        r=0 
    return La,Lfin,S,S-r








Transformation en boucle pour En syntaxe Xcas : 

fonction Ticketdimgros1(L,a,r) 
 local S,n,k,Lfin,La; 
 n:=dim(L);
 S:=0;
 pour k de 0 jusque n-1 pas 2 faire
   S:=S+Prix(L[k],L[k+1]);
   si S>=a alors 
     La:=gauche(L,k+2);
     Lfin:=droit(L,n-k-2);
     retourne La,Lfin,S,S-r;
   fsi;
 fpour;
 retourne La,[],S,S;
ffonction:;

onload





En syntaxe Python : 

def Ticketdimgros1(L,a,r):
    # local S,n,k,Lfin,La
    n=dim(L)
    S=0
    for k in range(0,n,2):
        S=S+Prix(L[k],L[k+1])
        if S>=a :
            La=gauche(L,k+2)
            Lfin=droit(L,n-k-2)
            return La,Lfin,S,S-r
    return La,[],S,S







3.17  Exercice : Algorithme de tracé de courbe

Soit la fonction f définie sur [a,b].
On veut tracer le graphe de cette fonction sur l’intervalle [a,b].
En partageant [a,b] en n parties égales on obtient :
a=a0,a1=a+h,a2=a+2h, ...b=a+n*h avec h=(b-a)/n. Le graphe sera obtenu en reliant les points de coordonnées [a f(a)] [a1 f(a1)] etc ... par des segments.
En syntaxe Xcas : 

fonction Graphe(f,a,b,n)
 local L,h,k;
 L:=NULL;
 h:=(b-a)/n;
 pour k de 0 jusque n-1 faire
   L:=L,segment(point(a,f(a)),point(a+h,f(a+h)));
   a:=a+h;
 fpour;
 retourne L;
ffonction:;

onload







En syntaxe Python : 

def Graphe(f,a,b,n):
    # local L,h,k
    L=NULL
    h=(b-a)/n
    for k in range(n):
        L=L,segment(point(a,f(a)),point(a+h,f(a+h)))
        a=a+h
    return L









3.18  Mettre au point un programme

Lorsqu’on écrit un programme, il y a deux étapes à franchir :

Chapitre 4  Résolution d’équations

4.1  Encadrer une racine d’une équation par dichotomie

Algorithme de dichotomie
On suppose que la fonction ff est continue sur l’intervalle [a,b][a,b] et que f(a)<0f(a)&lt;0 et f(b)>0f(b)&gt;0 (si f(a)>0f(a)&gt;0 et f(b)<0f(b)&lt;0 on peut se ramener au cas précédent en échangeant aa et bb). On en déduit que ff s’annule pour x=x 0x=x_0 avec a<x 0<ba&lt;x_0&lt;b, on cherche une valeur approchée de x 0x_0.

Pour avoir une meilleur approximation de x 0x_0, on cherche le signe de f(c)f(c) où c=a+b2c=\frac{a+b}{2} est le milieu de [a,b][a,b]. Si f(c)=0f(c)=0 alors x 0=cx_0=c et on est content ! Si f(c)<0f(c)&lt; 0, il est de même signe que f(a)f(a), on peut donc remplacer aa par cc, sinon f(c)>0f(c)&gt;0 est de même signe que f(b)f(b), on peut remplacer bb par cc. On recommence le processus jusquà ce que f(c)=0f(c)=0 ou |b−a|<10 −n|b-a|&lt;10^{-n} (avec par exemple n=3n=3). 

fonction Dichotomie0(f,a,b,n)
 local c;
 si f(a)*f(b)>0 alors retourne [] fsi; 
 si f(a)==0 alors retourne [a] fsi;
 si f(b)==0 alors retourne [b] fsi;
 si f(a)>0 alors a,b:=b,a; fsi; // echange a et b pour avoir f(a)<=0
 tantque abs(b-a)>10^(-n) faire
   c:=evalf(a+b)/2;
   si f(c)=0 alors retourne [c] fsi;
   si f(c)<0 alors a:=c; sinon b:=c; fsi; // on a f(a)<=0
 ftantque
 retourne [c];
ffonction:;


Notez le test d’arrêt qui utilise |b−a||b-a| car aa et bb ont peut-être été échangés. Exemple :







On peut rajouter en début de programme un test sur n pour que le nombre d’itérations ne soit pas trop grand, par exemple
si n>12 alors n:=12; fsi;
On peut aussi utiliser une variable locale pour ne faire qu’une seule fois le calcul de 10 −n10^{-n} et de f(c)f(c). Ce qui donne le programme suivant : 

fonction Dichotomie1(f,a,b,n)
 local c,fc,eps;
 si f(a)*f(b)>0 alors retourne [] fsi; 
 si f(a)==0 alors retourne [a] fsi;
 si f(b)==0 alors retourne [b] fsi;
 si f(a)>0 alors a,b:=b,a; fsi; // echange a et b pour avoir f(a)<=0
 si n>12 alors n:=12; fsi;
 eps:=10^(-n);
 tantque abs(b-a)>eps faire
   c:=evalf(a+b)/2;
   fc:=f(c);
   si fc=0 alors retourne [c] fsi;
   si fc<0 alors a:=c; sinon b:=c; fsi; // on a f(a)<0
 ftantque
 retourne [c];
ffonction:;





Il n’est pas indispensable de tester que f(a)=0f(a)=0, f(b)=0f(b)=0 et f(c)=0f(c)=0 (comme cela n’arrive pratiquement jamais, c’est donc inefficace de le faire), on peut supprimer ces lignes. Il faut alors utiliser f(c)≤0f(c)\leq 0 comme test (au lieu de f(c)<0f(c)&lt;0) pour conserver comme invariant de boucle f(a)≤0f(a)\leq 0 et f(b)>0f(b)&gt;0. 

fonction Dichotomie(f,a,b,n)
 local c,eps;
 si f(a)*f(b)>0 alors retourne [] fsi; 
 si f(a)>0 alors a,b:=b,a; fsi; // echange a et b pour avoir f(a)<=0
 si n>12 alors n:=12; fsi;
 eps:=10^(-n);
 tantque abs(b-a)>eps faire
   c:=evalf(a+b)/2; // invariant f(a)<=0 et f(b)>0
   si f(c)<=0 alors a:=c; sinon b:=c; fsi; 
 ftantque
 retourne [c];
ffonction:;




Traduction du “tantque” en “pour”
On observe qu’à chaque itération de la boucle on divise la longueur de l’intervalle par 2, le nombre d’itérations ne peut pas être très grand. On peut donc transformer la boucle “tantque” en boucle “pour” en se fixant à priori un nombre maximal d’itérations ce qui évitera d’ailleurs d’avoir une boucle qui ne se termine jamais. On montrera plus bas que 2100 itérations suffisent en calcul approché. 

fonction Dichotomie2(f,a,b,n)
 local c,k,eps;
 eps:=10^-n;
 si f(a)*f(b)>0 alors retourne []; fsi; 
 pour k de 1 jusque 2100 faire
   c:=(a+b)/2.0; // invariant f(a)*f(b)<=0
   si b-a<eps alors retourne [c]; fsi;
   si f(a)*f(c)<=0 alors b:=c; sinon a:=c; fsi;
 fpour;
 retourne [c];
ffonction:;






Exercice : modifier le programme pour ne pas faire le calcul de f(a)f(a) dans la boucle.

Remarque avancée : si on connaît les logarithmes, on peut calculer le nombre d’itérations NN pour que |b−a|/2 N<10 −n|b-a|/2^N&lt;10^{-n} en résolvant cette équation. On peut aussi observer que les calculs se font en approché, dans Xcas le plus grand nombre représentable par défaut est evalf(2^(1024-1), donc la taille du plus grand intervalle est (légèrement inférieure à) 2 10252^{1025}. Le plus petit réel strictement positif représentable est evalf(2^(-1069)). Comme on divise par 2 la taille de l’intervalle à chaque itération, le nombre maximal d’itérations est au plus 1025+1069=20941. Au-delà, soit aa et bb sont représentés par le même nombre flottant (et le test |b−a|<10 −n|b-a|&lt;10^{-n} sera donc vrai) soit ils ne différeront que par leur dernier bit de mantisse, et dans ce cas c=(a+b)/2c=(a+b)/2 sera arrondi vers aa ou vers bb et la boucle tanque continuera indéfiniment.
La majoration est le plus souvent très pessimiste, par exemple si a=1a=1 et b=2b=2 ils sont déjà représentés avec le même exposant et le nombre d’itérations sera limité par 48. 

fonction Dichotomie3(f,a,b,n)
 local c,k,N;
 si f(a)*f(b)>0 alors retourne []; fsi; 
 N:=ceil(log((b-a)/10^(-n))/log(2)); 
 si N>2100 alors N:=2100 fsi;
 pour k de 1 jusque N faire
   c:=(a+b)/2.0; // f(a)*f(b)<=0
   si f(a)*f(c)<=0 alors b:=c; sinon a:=c; fsi;
 fpour;
 retourne [c];
ffonction:;





Exercice : Modifier la fonction ci-dessus pour calculer ff une seule fois par itération, c’est-à-dire qu’on calcule cc et f(c)f(c) mais qu’on ne recalcule pas f(a)f(a).
Première méthode :
On introduit 3 variables locales fa, fb, fc contenant les valeurs de f(a)f(a), f(b)f(b), f(c)f(c). On en profite pour tester au passage si f(c)=0f(c)=0. 

fonction Dichotomie4(f,a,b,n)
 local c,k,N,fa,fb,fc;
 fa:=f(a);
 fb:=f(b);
 si fa*fb>0 alors retourne []; fsi; 
 si fa==0 alors retourne [a] fsi;
 si fb==0 alors retourne [b] fsi;
 N:=ceil(log((b-a)/10^(-n))/log(2)); 
 si N>2100 alors N:=2100 fsi;
 pour k de 1 jusque N faire
   c:=(a+b)/2.0;
   fc:=f(c);
   si fc==0 alors retourne [c] fsi;
   si fa*fc<0 alors b:=c; sinon a:=c; fa:=fc; fsi;
 fpour;
 retourne [c];
ffonction:;






Deuxième méthode :
On échange le rôle de aa et bb si f(a)>0f(a)&gt;0. 

fonction Dichotomie5(f,a,b,n)
 local c,k,N;
 si f(a)*f(b)>0 alors retourne []; fsi; 
 N:=ceil(log(abs(b-a)/10^(-n))/log(2)); 
 si N>2100 alors N:=2100 fsi;
 si f(a)>0 alors a,b:=b,a; fsi;
 pour k de 1 jusque N faire
   c:=(a+b)/2.0; // invariant f(a)<=0 et f(b)>0
   si f(c)<=0 alors a:=c; sinon b:=c; fsi;
 fpour;
 retourne [c];
ffonction:;






Ce programme est optimal.

On peut vérifier ces résultats en utilisant la commande fsolve de Xcas qui effectue la résolution numérique d’une équation :

4.2  Résoudre dans ℝ\mathbb{R} une équation se ramenant au premier degré ou au degré 2

On considère une équation qui se ramène au premier ou au deuxième degré.
Si cette équation se ramène au premier degré, elle est de la forme :

a*x+b=0 avec a!=0

donc cette équation a une solution qui est:
x0:=-b/a.
Si cette équation se ramène au deuxième degré, elle est de la forme :

a*x^2+b*x+c=0 avec a!=0

donc :

On tape : 

fonction Solution12(Eq,Var)
 local a,b,c,d;
 Eq:=normal(gauche(Eq)-droit(Eq));
 si degree(Eq,Var)==0 alors 
   si (Eq==0) alors retourne "infinite de solution" ;
   sinon retourne "pas de solution" ;
   fsi;
 fsi; 
 si degree(Eq,Var)==1 alors 
   //a:=coeff(Eq,Var,1);b:=coeff(Eq,Var,0);
   b:=subst(Eq,Var=0);
   a:=subst(Eq,Var=1)-b;
   retourne normal([-b/a]);
 fsi;
 si degree(Eq,Var)==2 alors 
   //a:=coeff(Eq,Var,2);b:=coeff(Eq,Var,1);c:=coeff(Eq,Var,0);
   c:=subst(Eq,Var=0);
   d:=subst(Eq,Var=1);
   b:=(d-subst(Eq,Var=-1))/2;
   a:=d-b-c;
   d:=b^2-4*a*c;
   si d>0 alors retourne simplify([(-b+sqrt(d))/(2*a),(-b-sqrt(d))/(2*a)]);fsi;
   si d==0 alors retourne simplify([-b/(2*a)]); fsi;
   retourne [];
 fsi;
 retourne "degree >2";
ffonction:;

onload









4.3  Résoudre un système de deux équations du premier degré à deux inconnues.

On veut résoudre le système de deux équations du premier degré
a 1x+b 1y+c 1=0,a 2x+b 2y+c 2=0a_1 x+b_1 y+c_1=0, \quad a_2x+b_2y+c_2=0 à deux inconnues x,yx,y. On notera a1, b1, c1, a2, b2, c2 les coefficients des équations dans les programmes.
Pour éviter d’étudier des cas particuliers inintéressants, on va supposer que (a 1,b 1)≠(0,0)(a_1,b_1)\neq (0,0) et (a 2,b 2)≠(0,0)(a_2,b_2) \neq (0,0). Dans ce cas a 1x+b 1y+c 1=0a_1 x+b_1 y+c_1=0 et a 2x+b 2y+c 2=0 a_2x+b_2y+c_2=0 sont les équations de 2 droites D 1D_1 et D 2D_2.

Solution géométrique

On commence par écrire un programme dans le cas où les droites D 1D_1 et D 2D_2 sont concourrantes. 

fonction Intersection1(Eq1,Eq2,Var1,Var2)
 local a1,b1,c1,a2,b2,c2;
 Eq1:=normal(gauche(Eq1)-droit(Eq1));
 Eq2:=normal(gauche(Eq2)-droit(Eq2));
 a1:=coeff(Eq1,Var1,1);
 a2:=coeff(Eq2,Var1,1);
 b1:=coeff(Eq1,Var2,1);
 b2:=coeff(Eq2,Var2,1);
 si normal(a1*b2-a2*b1)==0 alors
   retourne "Cas non traite : Eq1 ou Eq2 n'est pas une  "+
          "equation de droite ou droites paralleles"; 
 fsi;
 c1:=subst(Eq1,[Var1,Var2],[0,0]);
 c2:=subst(Eq2,[Var1,Var2],[0,0]);
 print("droites concourantes");
 retourne [normal((-b2*c1+b1*c2)/(a1*b2-a2*b1)),
           normal((a2*c1-a1*c2)/(a1*b2-a2*b1))];
ffonction:;









Exercice : modifiez le programme ci-dessus pour éviter de calculer plusieurs fois a 1b 2−a 2b 1a_1b_2-a_2b_1, en stockant sa valeur dans une variable locale.
Correction de l’exercice : 

fonction Intersection2(Eq1,Eq2,Var1,Var2)
 local a1,b1,c1,a2,b2,c2,d;
 Eq1:=normal(gauche(Eq1)-droit(Eq1));
 Eq2:=normal(gauche(Eq2)-droit(Eq2));
 a1:=coeff(Eq1,Var1,1);
 a2:=coeff(Eq2,Var1,1);
 b1:=coeff(Eq1,Var2,1);
 b2:=coeff(Eq2,Var2,1);
 d:=normal(a1*b2-a2*b1);
 si d==0 alors
   retourne "Cas non traite : Eq1 ou Eq2 n'est pas une"+
    " equation de droite ou droites paralleles ou confondues"; 
 fsi;
 c1:=subst(Eq1,[Var1,Var2],[0,0]);
 c2:=subst(Eq2,[Var1,Var2],[0,0]);
 print("droites concourantes");
 retourne [normal((-b2*c1+b1*c2)/d),
           normal((a2*c1-a1*c2)/d)];
ffonction:;







Voici maintenant un programme qui teste que les équations entrées sont bien des équations de droite et traite aussi le cas des droites parallèles ou confondues : 

fonction Intersection(Eq1,Eq2,Var1,Var2)
 local a1,b1,c1,a2,b2,c2,d;
 Eq1:=normal(gauche(Eq1)-droit(Eq1));
 si degree(Eq1,Var1)>1 et degree(Eq1,Var2)>1  alors 
   retourne "pas de degre 1"; 
 fsi;
 Eq2:=normal(gauche(Eq2)-droit(Eq2));
 si degree(Eq2,Var1)>1 et degree(Eq2,Var2)>1 alors 
   retourne "pas de degre 1"; 
 fsi;
 a1:=coeff(Eq1,Var1,1);
 a2:=coeff(Eq2,Var1,1);
 b1:=coeff(Eq1,Var2,1);
 b2:=coeff(Eq2,Var2,1);
 si [a1,b1]==[0,0] ou [a2,b2]==[0,0] alors 
   retourne "Eq1 ou Eq2 est nulle"; 
 fsi;
 c1:=subst(Eq1,[Var1,Var2],[0,0]);
 c2:=subst(Eq2,[Var1,Var2],[0,0]);
 d:=normal(a1*b2-a2*b1);
 si d!=0 alors 
   print("droites concourantes");
   retourne [normal((-b2*c1+b1*c2)/d),
             normal((a2*c1-a1*c2)/d)];
 fsi;
 si a1!=0 et a2!=0 alors 
   si c1*a2-c2*a1==0 alors 
     print("droites confondues");
     retourne [normal(-c1/a1),Var2]; 
   sinon 
     print("droites paralleles");
     retourne [] ;
   fsi;
 fsi;    
 si b1!=0 et b2!=0 alors 
   si c1*b2==c2*b1 alors 
     print("droites confondues");
     retourne [Var1,normal(-c1/b1)]; 
   sinon 
     print("droites paralleles");
     retourne [];
   fsi;
 fsi;
ffonction:;






On vérifie avec Xcas :




Justification de la solution lorsque D 1D_1 et D 2D_2 sont concourantes
On a vu que c’était le cas si et seulement si b 1a 2−b 2a 1≠0 b_1a_2-b_2a_1\neq0.

1
Il faut ajouter 5 pour un langage traditionnel où la mantisse a 53 chiffres significatifs. Attention, ceci n’est plus valable dans Xcas si on modifie la valeur de Digits

Chapitre 5  Les figures en géométrie plane avec Xcas

5.1  Le point : point et le segment : segment

point a comme arguments l’abscisse et l’ordonnée du point.
point trace le point à l’aide d’une croix sur l’écran de géométrie 2d2d.
Si on a donné un nom au point (par ex A:=point(1,1); ou A:=point([1,1]);) ce nom sera affiché à côté de la croix.

segment a comme argument 2 points.
segment trace le segment reliant ces 2 points sur l’écran de géométrie 2d2d.

5.2  Les coordonnées d’un point : coordonnees

coordonnees a comme argument 1 point.
coordonnees renvoie la liste constitué de l’abscisse et de l’ordonnée du point.



5.3  La droite et son équation : droite et equation

droite a comme argument 2 points.
droite trace la droite passant par ces 2 points sur l’écran de géométrie 2d2d.

equation a comme argument une droite.
equation renvoie l’équation de cette droite

5.4  Ligne brisée : polygone_ouvert

polygone_ouvert a comme argument une liste L de points.
polygone_ouvert trace la ligne brisée joignant les points L[k] et L[k+1] pour k=0..dim(L)-2.

5.5  Les polygones : triangle, carre, polygone

triangle a comme argument 3 points.
triangle trace le triangle défini par ces 3 points sur l’écran de géométrie 2d2d.

carre a comme argument 2 points.
carre trace le carré direct défini par ces 2 points sur l’écran de géométrie 2d2d.


polygone a comme argument une liste de points.
polygone trace le polygone fermé défini par cette liste de points sur l’écran de géométrie 2d2d.

Exercice
Faire un programme qui trace les polygones réguliers connaissant son centre CC, un de ses sommets AA et le nombre nn de côtés.

fonction Isopolygonec(C,A,n)
 local L,k;
 L:=NULL;
 L:=A;
 pour k de 0 jusque n-1 faire
   L:=L,C+(A-C)*exp(2*i*k*pi/n);
 fpour;
 retourne polygone(L);
ffonction:;

onload
Xcas, la fonction isopolygone a 3 arguments : 2 sommets et nn le nombre de côtés ou bien le centre du polygone, un sommet et un nombre négatif −n-n qui a comme valeur absolue le nombre nn de côtés.
Avec Xcas, on tape :

qui est identique à :

5.6  Le cercle et son équation : cercle et equation

Si le cercle est défini par son centre et son rayon alors cercle a pour argument un point et un réel r.
cercle trace le cercle de centre ce point et de rayon abs(r) sur l’écran de géométrie 2d2d.


Si le cercle est défini par son diamètre alors cercle a pour argument 2 points.
cercle trace le cercle de diamètre ces 2 points.


5.7  Les tangentes à un cercle passant par un point et leurs équations

Si C est un cercle et B un point situé à l’extérieur de (resp sur) C alors tangent(C,B) trace les (resp la) tangente(s) à C passant par B.





5.8  Exercice : les lunules d’Hippocrate

Ce théorème, très ancien, a été démontré par Hippocrate de Chios (-500) (Ne pas le confondre avec Hippocrate de Cos, le médecin), qui étudia aussi la duplication du cube, c’est-à-dire le calcul de la racine cubique de 2.
Hippocrate recherchait alors la quadrature du cercle et pensait que la quadrature de ses lunules allait le rapprocher du but.
Une lunule est une portion de surface délimitée par deux arcs de cercles non concentriques de rayons différents. Ces arcs ont mêmes extrémités et forment un croissant de lune en forme de ménisque : convexe d’un côté et concave de l’autre.

5.8.1  Exercice 1

Soit le triangle ABCABC rectangle en AA et 𝒞\mathcal{C} le cercle circonscrit à ABCABC (de diamètre BCBC).
La lunule L ACL_{AC} est la figure formée par le demi-disque de diamètre ACAC extérieur au triangle ABCABC, auquel on enlève son intersection avec le disque délimité par 𝒞\mathcal{C}.
La lunule L ABL_{AB} est la figure formée par le demi-disque de diamètre ABAB extérieur au triangle ABCABC, auquel on enlève son intersection avec le disque délimité par 𝒞\mathcal{C}.
Ces deux lunules (en jaune sur la figure ci-dessous) sont appelées lunules d’Hippocrate.
Montrer que la somme des aires de ces deux lunules L BCL_{BC} et de L BAL_{BA} (en jaune) est égale à l’aire du triangle ABCABC (en rouge).
On tape pour faire la figure : 

fonction Lunule1()
local A,B,C,L;
L:=NULL;
A:=point(0);
B:=point(2,affichage=quadrant1);
C:=point(3*i,affichage=quadrant1);
L:=L,cercle((A+C)/2,3/2,pi/2,3*pi/2,affichage=3+rempli);
L:=L,cercle(A,B,-pi,0,affichage=3+rempli);
L:=L,cercle(B,C,0,pi,affichage=4+rempli);
L:=L,triangle(A,B,C,affichage=1+rempli);
retourne L;
ffonction:;

onload

Solution
On calcule S1S1 l’aire du triangle ABCABC :
S1=AB*AC/2S1=AB*AC/2 On calcule S2S2 la somme des aires de L BCL_{BC} et de L BAL_{BA} :
S2S2 est obtenue par différence : S2S2 est égale à la somme des aires des demi-cercles de diamètres ABAB et ACAC à laquelle on enlève l’aire en bleu.
L’aire en bleu est égale à l’aire du demi-cercle de diamètre BCBC à laquelle on enlève l’aire S1S1 du triangle ABCABC :
S2=π*AB 2/2+π*AC 2/2−(π*BC 2/2−S1)S2=\pi*AB^2/2+\pi*AC^2/2-(\pi*BC^2/2-S1)
D’après le théorème de Pythagore on a : AB 2+AC 2=BC 2AB^2+AC^2=BC^2 donc :
S2=S1S2=S1.

5.8.2  Exercice 2

Soient un carré de côtés ll et les cercles ayant comme diamètre les côtés du carré.
À l’extérieur du carré, ces cercles déterminent avec le cercle circonscrit au carré 4 lunules.
Trouver l’aire des 4 lunules ainsi déterminées.
À l’intérieur du carré, ces cercles en se coupant déterminent 4 "pétales".
Trouver l’aire des 4 "pétales" ainsi déterminées.
On tape pour faire la figure : 

fonction Lunule2()
local A,B,C,L;
L:=NULL;
L:=L,cercle(point(2),2,-pi/2,pi/2,affichage=1+rempli);
L:=L,cercle(point(2*i),2,0,pi,affichage=2+rempli);
L:=L,cercle(point(-2),2,pi/2,3*pi/2,affichage=3+rempli);
L:=L,cercle(point(0,-2),2,pi,2*pi,affichage=4+rempli);
L:=L,cercle(0,2*sqrt(2),affichage=5+rempli);
L:=L,cercle(point(0,-2),2);
L:=L,cercle(point(0,2),2);
L:=L,cercle(point(2,0),2);
L:=L,cercle(point(-2,0),2);
L:=L,carre(-2-2*i,2-2*i);
retourne L;
ffonction:;

onload

Solution Un carré est formé de 2 triangles rectangles donc l’aire des 4 lunules est égale à l’aire du carré (cl le résultat précédent).
La somme de l’aire du carré et de l’aire des "pétales" est égale à l’aire des 4 demi-cercles de rayon l/2l/2 (car les 4 demi-cercles qui sont à l’intérieur du carré remplissent le carré et se superposent selon les "pétales") donc l’aire des "pétales"=π*l 2/2−l 2\pi*l^2/2-l^2.

5.8.3  Exercice 3

Si la tentative de la quadrature du cercle est un échec, Hippocrate a trouvé la quadrature de plusieurs lunules en partant de la remarque suivante :
deux secteurs circulaires OABOAB et O 1A 1B 1O_1A_1B_1 de rayon rr et r 1r_1 semblables i.e. dont les angles au centre aa ont la même valeur ont des aires proportionnelles aux carrés des longueurs de leurs cordes.
On tape pour faire la figure : 

fonction Secteurcirc(O,r,t,a)
local A,B,L,xO,yO;
L:=NULL;
[xO,yO]:=coordonnees(O);
A:=point(xO+r*cos(t),yO+r*sin(t));
B:=point(xO+r*cos(t+a),yO+r*sin(t+a));
L:=L,cercle(O,r,t,t+a,affichage=4+rempli);
L:=L,triangle(O,A,B,affichage=1+rempli);
retourne L;
ffonction:;

onload
Voici 2 secteurs circulaires identiques :

Voici 2 secteurs circulaires semblables :

Chaque secteur circulaire est composé ici d’un triangle (en rouge) et d’une calotte circulaire (en bleu). Les aires des triangles ainsi que les aires des calottes circulaires,sont aussi proportionnelles aux carrés des longueurs des cordes.
Montrer ces résultats.
Solution
Si deux secteurs circulaires OABOAB et O 1A 1B 1O_1A_1B_1 de rayon rr et r 1r_1 ont pour angle au centre aa on a :
La longueur ABAB vaut 2Rsin(a/22R\sin(a/2 donc r=AB/(2sin(a/2)r=AB/(2\sin(a/2)
L’aire du secteur circulaire vaut aR 2/2=AB 2(a/(8sin(a/2) 2)aR^2/2=AB^2(a/(8\sin(a/2)^2)
L’aire du secteur circulaire est donc proportionnelle à AB 2AB^2.
L’aire du triangle OABOAB vaut R 2cos(a/2)sin(a/2)=AB 2(1/(4tan(a/2))R^2\cos(a/2)\sin(a/2)=AB^2(1/(4\tan(a/2))
L’aire du triangle est donc proportionnelle à AB 2AB^2.
L’aire de la calotte circulaire vaut AB 2((a/(8sin(a/2) 2)−(1/(4tan(a/2))AB^2((a/(8\sin(a/2)^2)-(1/(4\tan(a/2)).
L’aire du calotte circulaire est donc proportionnelle à AB 2AB^2.
Application
Soit un triangle ABCABC isocèle et rectangle en CC.
Soit DD le symétrique de CC par rapport à ABAB.
Le demi-cercle ABCABC de diamètre ABAB et le quart de cercle AMBAMB de centre DD définissent la lunule AMBCAMBC en rouge sur la figure.
On tape pour faire la figure : 

fonction Lunule3()
local A,B,C,D,L,xO,yO;
L:=NULL;
A:=point(-2);
B:=point(2,affichage=quadrant1);
C:=point([0,2],affichage=quadrant1);
D:=point(0,-2);
L:=L,affichage(cercle(0,2,0,pi),1+rempli);
L:=L,triangle(A,B,C,affichage=4+rempli);
L:=L,affichage(cercle(D,2*sqrt(2),pi/4,3*pi/4),6+rempli);
L:=L,triangle(A,B,D,affichage=3+rempli);
retourne L;
ffonction:;

onload

Solution L’aire des 2 calottes circulaires rouges est égale à l’aire de la calotte circulaire cyan puisque AB 2=AC 2+BC 2=2AC 2AB^2=AC^2+BC^2=2AC^2 (car le triangle ABCABC est rectangle isocèle de sommet CC.
L’aire du triangle ABCABC (aire bleue+aire de la calotte circulaire cyan) est donc égale à l’aire de la lunule AMBCAMBC (aires des calottes circulaires rouges +aire bleue)

5.8.4  Exercice 4

Soit un trapèze isocèle ABCDABCD vérifiant BC=CD=ADBC=CD=AD et AB 2=3DC 2AB^2=3DC^2.
Soit l’arc de cercle BCMDABCMDA de centre II intersection des médiatrices de ACAC et de DCDC (où MM est un point de l’arc CDCD).
Soit l’arc de cercle BNABNA tangent à ACAC de centre JJ intersection de la médiatrice de DCDC et de la perpendiculaire en AA à ACAC.
On tape pour faire la figure : 

fonction Lunule4()
local A,B,C,D,I,J,L;
L:=NULL;
A:=point(-sqrt(3.));
B:=point(sqrt(3.));
C:=point(1,sqrt(2*sqrt(3.)));
D:=point(-1,sqrt(2*sqrt(3.)));
//I:=inter_unique(droite(x=0),mediatrice(A,D));
I:=point(0,sqrt(-3+2*sqrt(3.))*sqrt(3.))/3);
//J:=inter_unique(droite(x=0),perpendiculaire(A,droite(A,C)));
J:=point(0,-sqrt(3+2*sqrt(3.)));
L:=L,affichage(cercle(I,evalf(longueur(A,I)),angle(I,I+2,B),2*pi+angle(I,I+2,A)),1+rempli);
L:=L,triangle(A,B,C,affichage=2+rempli);
L:=L,triangle(A,C,D,affichage=2+rempli);
L:=L,affichage(cercle(J,sqrt(6+2*sqrt(3.)),angle(J,J+2,B),angle(J,J+2,A)),4+rempli);
L:=L,affichage(triangle(J,A,B),3+rempli);
L:=L,segment(D,I),segment(C,I),segment(A,C),segment(A,J),segment(J,B),segment(I,J);
retourne L;
ffonction:;

onload


Solution L’aire de la lunule (rouge + vert) ABCDABCD est égale à l’aire du trapèze ABCDABCD (vert+bleu).
En effet, l’aire de la calotte bleue est égale à 3 fois l’aire d’une calotte rouge car les secteurs circulaires JBAJBA et ICDICD sont homothétiques et que AB 2=3DC 2AB^2=3DC^2.
On a donc puisque AD=DC=CBAD=DC=CB, l’aire des calottes rouges sont égales.
Donc l’aire des 3 calottes rouges est égale à l’aire bleue et :
aire lunule(ABCDABCD)=aire trapeze(ABCDABCD)-aire calotte bleue+3*aire lunule(CDCD)
Donc
aire lunule(ABCDABCD)=aire trapeze(ABCDABCD).

Chapitre 6  La géométrie analytique

Dans ce chapitre, les programmes que l’on va faire ne feront pas de tracés mais renverront des valeurs (coordonnées, coefficients, équations).
On pourra alors faire les figures avec Xcas et vérifier les résultats obtenus par ces programmes.

6.1  Les segments

6.1.1  Calculer la distance de deux points connaissant leurs coordonnées

Si les points A et B ont pour coordonnées cA:=[xA,yA] et cB:=[xB,yB] le segment AB a pour longueur :
sqrt((xA-xB)^2+(yA-yB)^2)
On tape : 

fonction Longueur(cA,cB)
 local xA,xB,yA,yB;
 xA:=cA[0];
 yA:=cA[1];
 xB:=cB[0];
 yB:=cB[1];
 retourne simplify(sqrt((xA-xB)^2+(yA-yB)^2));
ffonction:;

onload






Vérifions avec Xcas :

6.1.2  Calculer les coordonnées du milieu d’un segment

Si les points A et B ont pour coordonnées cA:=[xA,yA] et cB:=[xB,yB], le milieu de AB a pour coordonnées [(xA+xB)/2,(yA+yB)/2] :
On tape : 

fonction Milieu(cA,cB)
 local xA,xB,yA,yB;
 xA:=cA[0];
 yA:=cA[1];
 xB:=cB[0];
 yB:=cB[1];
 retourne [(xA+xB)/2,(yA+yB)/2];
ffonction:;

onload






Vérifions avec Xcas :

6.2  Les droites

6.2.1  Équation d’une droite définie par 2 points ou par sa pente et un point

Équation d’une droite définie par 2 points
Si les points A et B ont pour coordonnées cA:=[xA,yA] et cB:=[xB,yB], la droite d passant par A et B a pour équation :
(xA-xB)*y-(yA-yB)*x-yB*xA+yA*xB=0 ou encore
si (xA==xB) alors l’équation de d est x=xA
si (xA!=xB) alors l’équation de d est y=(yA-yB)*(x-xB)/(xA-xB)+yB
Équation d’une droite définie par sa pente et un point
La droite passant par le point A de coordonnées cA:=[xA,yA] et de pente m a pour équation :
y=m*(x-xA)+yA.
On tape : 

fonction Droite1(cA,cB)
 local xA,xB,yA,yB;
 xA:=cA[0];
 yA:=cA[1];
 xB:=cB[0];
 yB:=cB[1];
 retourne normal((xA-xB)*y-(yA-yB)*x-yB*xA+yA*xB)=0;
ffonction:;

fonction Droite2(cA,m)
 local xA,yA;
 xA:=cA[0];
 yA:=cA[1];
 retourne y-m*(x-xA)-yA=0;
ffonction:;


On peut réunir les 2 programmes en un seul en testant la dimension du deuxième paramètre de Droite qui est soit une liste de dimension 2, soit un réél.
On peut aussi faire en sorte que Droite accepte 1 seul argument qui soit son équation : pour cela, on donne au deuxième argument une valeur par défaut (ici cette valeur sera arbitraire par exemple 0) (cf 2.2.4).
On tape : 

fonction Droite(cA,L=0)
 local xA,xB,yA,yB,m;
 si type(cA)==expression alors retourne cA;fsi;
 xA:=cA[0];
 yA:=cA[1];
 si type(L)==vecteur alors 
   xB:=L[0];
   yB:=L[1];
   retourne normal((xA-xB)*y-(yA-yB)*x-yB*xA+yA*xB)=0;
 sinon
   m:=L;
   retourne y-m*(x-xA)-yA=0;
 fsi;
ffonction:;

onload
Observez qu’on a donné une valeur par défaut 0 au deuxième paramètre L, si Droite est appelée avec deux arguments tout se passe comme si on avait écrit L et non L=0, par contre si Droite est appelée avec un seul argument, alors L prend la valeur 0 au début de la fonction.














Vérifions avec Xcas :



6.2.2  Coefficients (a,b,c) de la droite d’équation ax+by+c=0

Étant donnée l’équation d’une droite a*x+b*y+c=0, on va écrire une fonction qui renvoie les coefficients a, b et c.
On utilise tout d’abord gauche et droit qui renvoie le côté gauche et le côté droit d’une équation.
Par exemple si Eq:=eq1=eq2 alors gauche(Eq) renvoie eq1 et droit(Eq) renvoie eq2 donc
gauche(Eq)-droit(Eq) renvoie eq qui est égal à eq1-eq2.
On peut alors trouver a, b et c en donnant des valeurs à x et y.
Posons :
c:=subst(eq,[x,y],[0,0])
d1:=subst(eq,[x,y],[1,0])
d2:=subst(eq,[x,y],[0,1])
Alors on a a:=d1-c et b:=d2-c
On tape : 

fonction Coeffsdroite(Eq)
 local a,b,c,d1,d2,eq;
 eq:=gauche(Eq)-droit(Eq);
 c:=subst(eq,[x,y],[0,0]);
 d1:=subst(eq,[x,y],[1,0]);
 d2:=subst(eq,[x,y],[0,1]);
 retourne normal(d1-c,d2-c,c);
ffonction:;

onload




Remarque
On peut aussi utiliser :
coeff(P(x,y),x) (resp coeff(P(x,y),y)) qui renvoie la liste des coefficients selon les puissances décroissantes du polynôme P par rapport à la variable x (resp y) et
coeff(P(x,y),x,n) (resp coeff(P(x,y),y,n)) qui renvoie le coefficient de x^n (resp de y^n) du polynôme P.
On tape : 

fonction Coeffdroite(Eq)
 local a,b,c;
 Eq:=gauche(Eq)-droit(Eq);
 a:=coeff(Eq,x,1);
 b:=coeff(Eq,y,1);
 c:=subst(Eq,[x,y]=[0,0]);
 retourne normal(a,b,c);
ffonction:;






Vérifions avec Xcas :

6.2.3  Point d’intersection de 2 droites sécantes

Cette section reprend la section sur la résolution de système de 2 équations à 2 inconnues. Soient deux droites d1 et d2 d’équation :
a 1x+b 1y+c 1=0a_1x+b_1y+c_1=0 et a 2x+b 2y+c 2=0a_2x+b_2y+c_2=0
Ces 2 droites sont parallèles si a 1b 2=a 2b 1a_1b_2=a_2b_1.
Si a 1b 2≠a 2b 1a_1b_2\neq a_2b_1 d1 et d2 sont sécantes.
Les coordonnées de leur point d’intersection sont
(−c 2*b 1+b 2*c 1)/(−b 2*a 1+a 2*b 1),(c 2*a 1−a 2*c 1)/(−b 2*a 1+a 2*b 1)(-c_2*b_1+b_2*c_1)/(-b_2*a_1+a_2*b_1),(c_2*a_1-a_2*c_1)/(-b_2*a_1+a_2*b_1) Interdroite(d1,d2) renvoie [] si d1 et d2 sont paralléles et sinon renvoie les coordonées de leur point d’intersection.
On utilise les programmes Droite et Coeffsdroite précédents (cf 6.2.2 pour avoir les coefficients des équations Eq1 et Eq2 de d1 et de d2 On tape : 

fonction Interdroite(d1,d2)
 local a1,a2,b1,b2,c1,c2,gd1,gd2,d;
 (a1,b1,c1):=Coeffsdroite(d1);
 (a2,b2,c2):=Coeffsdroite(d2);
 d:=normal(a2*b1-b2*a1);
 si d==0 alors retourne [];fsi;
 retourne [(b2*c1-b1*c2)/d,(c2*a1-a2*c1)/d];
ffonction:;

















On fait la figure avec Xcas:

Vérifions avec Xcas :



6.3  Triangles et quadrilatères définis par les coordonnées des sommets

On définit des versions de la commande polygone de Xcas donc ces 2 programmes vont faire des figures. 

fonction Triangle(cA,cB,cC)
 retourne polygone(cA,cB,cC);
ffonction:;
fonction Quadrilatere(cA,cB,cC,cD)
 retourne polygone(cA,cB,cC,cD);
ffonction:;












6.4  Les vecteurs

6.4.1  Les coordonnées d’un vecteur défini par 2 points

Si les coordonnées du point A (resp B) sont cA:=[xA,yA] (resp cB:=[xB,yB]), les coordonnées du vecteur AB sont [xB-xA,yB-yA].
On tape : 

fonction Vecteur(cA,cB)
 local xA,xB,yA,yB;
 xA:=cA[0];
 yA:=cA[1];
 xB:=cB[0];
 yB:=cB[1];
 retourne normal([xB-xA,yB-yA]);
ffonction:;


ou plus simplement :








On fait la figure avec Xcas :

Vérifions avec Xcas :

6.4.2  Calculer les coordonnées de la somme de deux vecteurs dans un repère

Si les vecteurs V1 et V2 ont pour coordonnées cV1:=[x1,y1] et cV2:=[x2,y2], les coordonnées du vecteur V1+V2 sont [x1+x2,y1+y2].
On tape : 

fonction SumVect(cV1,cV2)
 local x1,x2,y1,y2;
 x1:=cV1[0];
 y1:=cV1[1];
 x2:=cV2[0];
 y2:=cV2[1];
 retourne normal([x1+x2,y1+y2]);
ffonction:;


ou plus simplement :








On fait la figure avec Xcas :

Vérifions avec Xcas :

6.4.3  Coordonnées de DD extrémité du vecteur d’origine CC équipollent au vecteur ABAB

On a D:=C+(B−A)D:=C+(B-A).
On tape :










On fait la figure avec Xcas :

Vérifions avec Xcas :

6.4.4  Norme d’un vecteur

Soit le vecteur V:=[xV,yV], on pose cV:=[xV,yV] la liste des coordonnées de V.
La norme de V est égale à sqrt(xV^2+yV^2).
On tape : 

fonction Norme(cV)
 local xV,yV;
 xV:=cV[0];
 yV:=cV[1];
 retourne sqrt(xV^2+yV^2);
ffonction:;








Vérifions avec Xcas :

6.5  Changement de repères

6.5.1  Le problème

Soient 2 repères orthonormés O,Ox,Oy O,Ox,Oy et I,IX,IY I,IX,IY.
Notations :

Avec ces notations, on a :

6.5.2  Le programme Changexy2XY(cM,cI,cU)

On connaît les coordonnées cM:=[x M,y M] cM:=[x_M,y_M] d’un point M M dans le repère (O,Ox,Oy) (O,Ox,Oy) ainsi que les coordonnées c I:=[x I,y I] c_I:=[x_I,y_I] et c U:=[x U,y U] c_U:=[x_U,y_U] de I I et de U U dans le repère (O,Ox,Oy) (O,Ox,Oy).
On cherche les coordonnées C M:=[X M,Y M] C_M:=[X_M,Y_M] de M M dans le repère (I,IX,IY) (I,IX,IY).
On a donc : OM=x Mu+y Mv = OI+IM = (x Iu+y Iv)+(X MU+Y MV) = x Iu+y Iv+X M(x Uu+y Uv)+Y M(x Vu+y Vv) = (x I+X Mx U+Y Mx V)u+(y I+X My U+Y My V)v \begin{matrix} OM=x_Mu+y_Mv&=&OI+IM\\ &=&(x_Iu+y_Iv)+(X_MU+Y_MV) \\ &=&x_Iu+y_Iv+X_M(x_Uu+y_Uv)+Y_M(x_Vu+y_Vv)\\ &=&(x_I+X_Mx_U+Y_Mx_V)u+(y_I+X_My_U+Y_My_V)v \end{matrix} Donc : x M=x I+X Mx U+Y Mx V,y M=y I+X My U+Y My Vx_M=x_I+X_Mx_U+Y_Mx_V, \quad y_M=y_I+X_My_U+Y_My_V on en déduit X M,Y MX_M, Y_M X M=(x M−x I)y V−(y M−y I)x Vx Uy V−y Ux V,Y M=(x M−x I)y U−(y M−y I)x Ux Vy U−y Vx UX_M= \frac{(x_M-x_I)y_V-(y_M-y_I)x_V}{x_Uy_V-y_Ux_V}, \quad Y_M= \frac{(x_M-x_I)y_U-(y_M-y_I)x_U}{x_Vy_U-y_Vx_U} Or x V=−y U x_V=-y_U et y V=x U y_V=x_U donc x Uy V−y Ux V=x U 2+y U 2=1x_Uy_V-y_Ux_V=x_U^2+y_U^2=1 Finalement : X M=(x M−x I)x U+(y M−y I)y U,Y M=(x M−x I)y U−(y M−y I)x UX_M= (x_M-x_I)x_U+(y_M-y_I)y_U, \quad Y_M= (x_M-x_I)y_U-(y_M-y_I)x_U On tape : 

fonction Changexy2XY(cM,cI,cU)
local xM,xI,xU,xV,yM,yI,yU,yV,l;
xM:=cM[0];
yM:=cM[1];
xI:=cI[0];
yI:=cI[1];
xU:=cU[0];
yU:=cU[1];
l:=xU^2+yU^2;
si l!=1 alors l:=sqrt(l);xU:=xU/l;yU:=yU/l;fsi;
xV:=-yU;
yV:=xU;
retourne normal([((xM-xI)*xU+(yM-yI)*yU),(-(xM-xI)*yU+(yM-yI)*xU)]);
ffonction:;


Remarque
Dans le programme ci-dessus, on teste si le vecteur U est unitaire, si ce n’est pas le cas, on le rend unitaire avec :
l:=xU^2+yU^2;si l!=1 alors l:=sqrt(l);xU:=xU/l;yU:=yU/l;fsi;
On tape :










La figure avec Xcas :

6.5.3  Le programme ChangeXY2xy(CM,cI,cU)

Il s’agit du programme inverse du précédent : on connaît les coordonnées C M:=[X M,Y M]C_M:=[X_M,Y_M] d’un point MM dans le repère (I,IX,IY)(I,IX,IY) ainsi que les coordonnées c I:=[x I,y I]c_I:=[x_I,y_I] et c U:=[x U,y U]c_U:=[x_U,y_U] de II et de UU dans le repère (O,Ox,Oy)(O,Ox,Oy). On cherche les coordonnées c M:=[x M,y M]c_M:=[x_M,y_M] de MM dans le repère (O,Ox,Oy)(O,Ox,Oy).

On a vu précédemment que : x M=x I+X Mx U+Y Mx V,y M=y I+X My U+Y My Vx_M=x_I+X_Mx_U+Y_Mx_V, \quad y_M=y_I+X_My_U+Y_My_V On tape : 

fonction ChangeXY2xy(CM,cI,cU)
 local XM,xI,xU,xV,YM,yI,yU,yV,l;
 XM:=CM[0];
 YM:=CM[1];
 xI:=cI[0];
 yI:=cI[1];
 xU:=cU[0];
 yU:=cU[1];
 l:=xU^2+yU^2;
 si l!=1 alors l:=sqrt(l);xU:=xU/l;yU:=yU/l;fsi;
 xV:=-yU;
 yV:=xU;
 retourne normal([xI+XM*xU+YM*xV,yI+XM*yU+YM*yV]);
ffonction:;

onload
Remarque
Dans le programme ci-dessus, si le vecteur U n’est pas unitaire, on le rend unitaire :
l:=xU^2+yU^2;si l!=1 alors l:=sqrt(l);xU:=xU/l;yU:=yU/l;fsi;
On tape :










La figure avec Xcas :

6.5.4  Exercices

En se servant des programmes précédents, faire les programmes :

  1. calculant les coordonnées c Cc_C du sommet CC d’un triangle équilatéral direct ABCABC connaissant les coordonnées c Ac_A de AA et c Bc_B de BB,
  2. calculant les coordonnées c Cc_C et c Dc_D des sommets CC et DD d’un carré direct ABCDABCD connaissant les coordonnées c Ac_A de AA et c Bc_B de BB.

Solution
1/ Soit un triangle équilatéral direct ABCABC. Dans le repère orthonormé OxyOxy, AA a pour coordonnées c A:=[x A,y A] c_A:=[x_A,y_A] et BB a pour coordonnées c B:=[x B,y B] c_B:=[x_B,y_B].
Cherchons les coordonnées C C=[X C,Y C] C_C=[X_C,Y_C] du point CC dans le repère d’origine AA et d’axe des XX dirigé selon le vecteur ABAB. On pose : l:=(x B−x A) 2+(y B−y A) 2l:=\sqrt{(x_B-x_A)^2+(y_B-y_A)^2} On a : c U:=[x B−x Al,y B−y Al],C C:=[l2,l32]c_U:=[\frac{x_B-x_A}{l},\frac{y_B-y_A}{l}], \quad C_C:=[\frac{l}{2},\frac{l\sqrt{3}}{2}] Et les coordonnées de CC dans le repère orthonormé OxyOxy sont :
ChangeXY2xy(CC,cA,cU) (fonction écrite précédemment cf 6.5.3).
On tape : 

fonction Coordequi(cA,cB)
 local xA,yA,xB,yB,cU,l,CC;
 xA:=cA[0];
 yA:=cA[1];
 xB:=cB[0];
 yB:=cB[1];
 l:=sqrt((xB-xA)^2+(yB-yA)^2);
 cU:=[(xB-xA)/l,(yB-yA)/l];
 CC:=[l/2,l*sqrt(3)/2];
 retourne ChangeXY2xy(CC,cA,cU);
ffonction:;








On fait la figure avec Xcas :

Vérifions avec Xcas :


2/ Soit un carré direct ABCDABCD, avec AA de coordonnées c A:=[x A,y A]c_A:=[x_A,y_A] et BB de coordonnées c B:=[x B,y B]c_B:=[x_B,y_B] dans le repère orthonormé OxyOxy.
Cherchons les coordonnées C C:=[X C,Y C]C_C:=[X_C,Y_C] du point CC et C D:=[X D,Y D]C_D:=[X_D,Y_D] des points CC et DD dans le repère d’origine AA et d’axe des XX dirigé selon le vecteur ABAB. On pose : l:=(x B−x A) 2+(y B−y A) 2l:=\sqrt{(x_B-x_A)^2+(y_B-y_A)^2} On a : c U:=[x B−x Al,y B−y Al],c C=[l,l],c D=[0,l]c_U:=[\frac{x_B-x_A}{l},\frac{y_B-y_A}{l}], \quad c_C=[l,l], \quad c_D=[0,l] Donc les coordonnées de CC dans le repère orthonormé OxyOxy sont :
ChangeXY2xy(CC,cA,cU)
les coordonnées de DD dans le repère orthonormé OxyOxy sont :
ChangeXY2xy(CD,cA,cU) (fonction écrite précédemment cf 6.5.3). 

fonction Coordcarre(cA,cB)
 local xA,yA,xB,yB,CC,CD,cU,l;
 xA:=cA[0];
 yA:=cA[1];
 xB:=cB[0];
 yB:=cB[1];
 l:=sqrt((xB-xA)^2+(yB-yA)^2);
 cU:=[(xB-xA)/l,(yB-yA)/l];
 CC:=[l,l];
 CD:=[0,l];
 retourne ChangeXY2xy(CC,cA,cU),ChangeXY2xy(CD,cA,cU);
ffonction:;










On fait la figure avec Xcas :

On vérifie avec Xcas :

6.6  Cercles, Tangentes à un cercle

6.6.1  Équation d’un cercle défini par son centre et son rayon

Le cercle CC défini par son centre AA de coordonnées [x A,y A][x_A,y_A] et de rayon rr a pour équation : (x−x A) 2+(y−y A) 2=r 2(x-x_A)^2+(y-y_A)^2=r^2 ou encore x 2+y 2−2x Ax−2y Ay+x A 2+y A 2−r 2=0x^2+y^2-2x_Ax-2y_Ay+x_A^2+y_A^2-r^2=0 On va écrire une procédure Cercle qui renvoie une liste constituée des coordonnées de son centre, de son rayon et de son équation.
On tape : 

fonction Cercle1(cA,r)
 //cercle defini par son centre et son rayon
 local xA,yA;
 xA:=cA[0];
 yA:=cA[1];
 retourne [cA,r,x^2+y^2-2*xA*x-2*yA*y+xA^2+yA^2-r^2=0];
ffonction:;


6.6.2  Équation d’un cercle défini par son diamètre

Si les points AA et BB ont pour coordonnées [x A,y A][x_A,y_A] et [xB,yB][xB,yB], le cercle CC de diamètre ABAB a pour équation :
si M:= Milieu(A,B), si xM:=M[0], si yM:=M[1] et si r:=Longueur(A,B)/2 :
(x-xM)^2+(y-yM)^2=r^2 ou encore
x^2+y^2-2*xM*x-2*yM*y+xM^2+yM^2-r^2=0
On va écrire une procédure Cercle qui renvoie une liste constituée des coordonnées de son centre, de son rayon et de son équation.
On tape : 

fonction Cercle2(cA,cB)
 //cercle d\'efini par son diam\`etre
 local xA,xB,xM,yA,yB,yM,M,r;
 xA:=cA[0];
 yA:=cA[1];
 xB:=cB[0];
 yB:=cB[1];
 cM:=Milieu(cA,cB):
 xM:=cM[0];
 yM:=cM[1];
 r:=Longueur(cA,cB):
 retourne [cM,r,x^2+y^2-2*xM*x-2*yM*y+xM^2+yM^2-r^2=0];
ffonction:;


6.6.3  Équation d’un cercle défini par son centre et son rayon ou par son diamètre

On peut reunir les 2 programmes en un seul en testant la dimension du deuxième paramètre de Cercle qui est soit une liste de dimension 2 (cercle défini par son diamètre), soit un réel (cercle défini par centre et rayon).
On tape : 

fonction Cercle(cA,L)
 local cB,xA,xB,xM,yA,yB,yM,cM,r;
 xA:=cA[0];
 yA:=cA[1];
 si type(L)==vecteur alors 
   xB:=L[0];
   yB:=L[1];
   cB:=[xB,yB]
   cM:=Milieu(cA,cB);
   xM:=cM[0];
   yM:=cM[1];
   r:=Longueur(cA,cB)/2;
   retourne  [cM,r,x^2+y^2-2*xM*x-2*yM*y+xM^2+yM^2-r^2=0];
 sinon
   r:=L;
   retourne [cA,r,x^2+y^2-2*xA*x-2*yA*y+xA^2+yA^2-r^2=0];
 fsi;
ffonction:;

onload










On fait la figure avec Xcas :

On vérifie avec Xcas :

6.6.4  Centre et rayon d’un cercle donné par son équation

On utilise ici les commandes Xcas gauche, droit ,coeff, subst
On tape : 

fonction Centrerayon(Eq)
 local k,a,b,c;
 Eq:=gauche(Eq)-droit(Eq);
 k:=coeff(Eq,x,2);
 si k!=coeff(Eq,y,2) alors retourne "ce n'est pas un cercle";fsi;
 Eq:=Eq/k;
 a:=-coeff(Eq,x,1)/2;
 b:=-coeff(Eq,y,1)/2;
 c:=subst(Eq,[x,y],[0,0]);
 retourne [a,b], normal(sqrt(a^2+b^2-c));
ffonction:;




On vérifie avec Xcas :

6.6.5  Construire la tangente à un cercle en l’un de ses points

Soit C C un cercle de centre I I de coordonnées c I=[x I,y I] c_I=[x_I,y_I] et de rayon r r.
Soit A A un point de C C de coordonnées c A=[x A,y A]c_A=[x_A,y_A]. la tangente au cercle C C en A A est perpendiculaire à IA IA, donc a pour pente m=−(x A−x I)/(y A−y I) m=-(x_A-x_I)/(y_A-y_I)
L’équation de cette tangente est donc : Droite(cA,m) (fonction Droite a été écrite précédemment cf 6.2.1).
On utilise aussi, ici, les fonctions Longueur (cf 6.1.1) et Cercle (cf 6.6.3).
On tape : 

fonction Tangent1(C,cA)
 local I,r,m,xI,yI,xA,yA,cI;
 cI:=C[0];
 r:=C[1];
 si Longueur(cA,cI)!=r alors retourne "A n'est pas sur C"; fsi;
 xI:=cI[0];
 yI:=cI[1];
 xA:=cA[0];
 yA:=cA[1];
 si yA!=yI alors 
   m:=-(xA-xI)/(yA-yI);
   retourne Droite(cA,m);
 fsi
 retourne x=xA; 
ffonction:;












On fait la figure avec Xcas :

On vérifie avec Xcas :

6.6.6  Construire les tangentes à un cercle passant par un point

Soit C C un cercle de centre I I de coordonnées c I:=[x I,y I] c_I:=[x_I,y_I] et de rayon r r.
Soit A A un point du plan de coordonnées c A:=[x A,y A] c_A:=[x_A,y_A].
Si A A est à l’intérieur de C C il n’y a pas de tangente à C C passant par A A.

Le cas simple

On suppose qu’on a choisi comme repère, le repère IXYIXY d’origine le centre I I du cercle CC et tel que AA est sur l’axe des XX (i.e. de coordonnées [X A,0][X_A,0]) et à l’extérieur de CC.
On peut mener par AA, 2 tangentes T 1 T_1 et T 2 T_2 à C C.
Soient M 1 M_1 et M 2 M_2 les 2 points de tangeance de T 1 T_1 et T 2 T_2.
Les triangles IAM 1 IAM_1 (resp IAM 2 IAM_2) sont rectangles en M 1 M_1 (resp M 2 M_2) et M 1M 2 M_1M_2 est perpendiculaire à AI AI.
Soit H H l’intersection de M 1M 2 M_1M_2 avec AI AI.
On fait la figure avec Xcas :

On a : r 2=IM 1 2=IM 2 2=IA×IHr^2=IM_1^2=IM_2^2=IA \times IH Donc dans le repère IXYIXY, AA a pour abscisse X A=Longueur(cI,cA)X_A=\mbox{Longueur(cI,cA)} et pour ordonnée 0.
HH a pour abscisse r 2X A\frac{r^2}{X_A} et pour ordonnée 0.
M 1 M_1 et M 2 M_2 ont la même abscisse : X M 1=X M 2=r 2X AX_{M_1}=X_{M_2}=\frac{r^2}{X_A} M 1 M_1 et M 2 M_2 ont des ordonnées opposées :
Y M 1>0,Y M 1 2=r 2−r 4X A 2=r 2(1−r 2X A 2),Y M 2=−Y M 1Y_{M_1}&gt;0,\quad Y_{M_1}^2=r^2-\frac{r^4}{X_A^2}=r^2(1-\frac{r^2}{X_A^2}), \quad Y_{M_2}=-Y_{M_1} Y M 1=rX A 2−r 2X A,Y M 2=−Y M 1Y_{M_1}=r\frac{\sqrt{X_A^2-r^2}}{X_A}, \quad Y_{M_2}=-Y_{M_1} Les tangentes sont donc :

Droite([X A,0],[X M 1,Y M 1]) \mbox{Droite}([X_A,0], [X_{M_1},Y_{M_1}]) et Droite([X A,0],[X M 2,Y M 2]) \mbox{Droite}([X_A,0], [X_{M_2},Y_{M_2}])

Si A A est sur C C (i.e. X A==r X_A==r) alors on peut mener par A A , une tangente T 1 T_1 à C C qui est Droite(x=X A) \mbox{Droite}(x=X_A).

Le cas général

On se ramène au cas précédent par changement de repère.
Soit OxyOxy le repère. Dans le repère OxyOxy, II (resp AA) a pour coordonnées c Ic_I (resp c Ac_A).
On fait un changement de repère en prenant le centre II du cercle comme origine et IA IA comme axe des X X.
On note X M X_M et Y M Y_M les coordonnées d’un point M M ou d’un vecteur M M dans le nouveau repère IXYIXY et x M x_M et y M y_M les coordonnées de MM dans le repère OxyOxy.
Dans le repère IXYIXY, AA a pour abscisse X A=Longueur(c A,c I)X_A=\mbox{Longueur}(c_A,c_I) et pour ordonnée 0.
HH a pour abscisse r 2X A\frac{r^2}{X_A} et pour ordonnée 0.
Si U U est le vecteur unitaire de IX IX on a :
x U:=(x A−x I)/X A x_U:=(x_A-x_I)/X_A et y U:=(y A−y I)/X A y_U:=(y_A-y_I)/X_A avec X A:=Longueur(c A,c I) X_A:=\mbox{Longueur}(c_A,c_I).
On a vu que (cf 6.5.2) : x M=x I+X Mx U+Y Mx V,y M=y I+X My U+Y My Vx_M=x_I+X_Mx_U+Y_Mx_V, \quad y_M=y_I+X_My_U+Y_My_V x V:=−y U,y V:=x Ux_V:=-y_U, \quad y_V:= x_U Donc :
x M=x I+X Mx U−Y My U,y M=y I+X My U+Y Mx Ux_M=x_I+X_Mx_U-Y_My_U, \quad y_M=y_I+X_My_U+Y_Mx_U En remplaçant x U x_U et y U y_U par leur valeur, on a :
x M=x I+X M(x A−x I)−Y M(y A−y I)Longueur(c A,c I)y M=y I+X M(y A−y I)+Y M(x A−x I)Longueur(c A,c I)x_M=x_I+\frac{X_M(x_A-x_I)-Y_M(y_A-y_I)}{\mbox{Longueur}(c_A,c_I)} \quad y_M=y_I+\frac{X_M(y_A-y_I)+Y_M(x_A-x_I)}{\mbox{Longueur}(c_A,c_I)} Dans le repère IXYIXY les coordonnées de M 1 M_1 et M 2 M_2 sont :
X M 1=X M 2=r 2/x AX_{M_1}=X_{M_2}=r^2/x_A Y M 1=rX A 2−r 2X A,Y M 2=−Y M 1Y_{M_1}=r\frac{\sqrt{X_A^2-r^2}}{X_A}, \quad Y_{M_2}=-Y_{M_1} Donc : x M 1 = x I+r 2/x A(x A−x I)−r1−r 2/x A(y A−y I)Longueur(c A,c I) y M 1 = y I+r 2/x A(y A−y I)+r1−r 2/x A(x A−x I)Longueur(c A,c I), x M 2 = x I+r 2/x A(x A−x I)+r1−r 2/x A(y A−y I)Longueur(c A,c I), y M 2 = y I+r 2/x A(y A−y I)−r1−r 2/x A(x A−x I)Longueur(c A,c I) \begin{matrix} x_{M_1}&=&x_I+\frac{r^2/x_A(x_A-x_I)-r\sqrt{1-r^2/x_A}(y_A-y_I)}{\mbox{Longueur}(c_A,c_I)} \\ y_{M_1}&=&y_I+\frac{r^2/x_A(y_A-y_I)+r\sqrt{1-r^2/x_A}(x_A-x_I)}{\mbox{Longueur}(c_A,c_I)}, \\ x_{M_2}&=&x_I+\frac{r^2/x_A(x_A-x_I)+r\sqrt{1-r^2/x_A}(y_A-y_I)}{\mbox{Longueur}(c_A,c_I)},\\ y_{M_2}&=&y_I+\frac{r^2/x_A(y_A-y_I)-r\sqrt{1-r^2/x_A}(x_A-x_I)}{\mbox{Longueur}(c_A,c_I)} \end{matrix} On écrit la fonction Tangent(C,cA) qui renvoie une liste (éventuellement vide) contenant la ou les équations des tangentes au cercle C passant par le point AA de coordonnées cA, en utilisant Milieu (cf 6.1.2), Longueur (cf 6.1.1), Droite(cf 6.2.1) et Cercle (cf 6.6.3).
On tape : 

fonction Tangent(C,cA)
 local cI,r,xI,yI,xA,yA,XM1,YM1,xM1,yM1,XM2,YM2,xM2,yM2,l;
 cI:=C[0];
 xI:=cI[0];
 yI:=cI[1];
 r:=C[1];
 l:=Longueur(cA,cI);
 xA:=cA[0];
 yA:=cA[1];
 si l < r alors 
   print("A n'est pas a l'exterieur de C");
   retourne [];
 fsi;
 si l==r et yA==yI alors 
   retourne [x-xA=0]; 
 fsi;
 si l==r et (yA-yI)!=0 alors 
   retourne [normal(Droite([xA,yA],-(xA-xI)/(yA-yI)))];
 fsi;
 XM1:=r^2/l;
 YM1:=r*sqrt(1-r^2/l^2);
 xM1:=normal(xI+(XM1*(xA-xI)-YM1*(yA-yI))/l);
 yM1:=normal(yI+(XM1*(yA-yI)+YM1*(xA-xI))/l);
 XM2:=r^2/l;
 YM2:=-r*sqrt(1-r^2/l^2);
 xM2:=normal(xI+(XM2*(xA-xI)-YM2*(yA-yI))/l);
 yM2:=normal(yI+(XM2*(yA-yI)+YM2*(xA-xI))/l);
 retourne [Droite([xM1,yM1],[xA,yA]),Droite([xM2,yM2],[xA,yA])];
ffonction:;












On fait la figure avec Xcas :



On fait la figure avec Xcas :

On vérifie avec Xcas :




On peut utiliser non seulement Milieu (cf 6.1.2), Longueur (cf 6.1.1), Droite(cf 6.2.1) et Cercle (cf 6.6.3), mais aussi le programme de changement de repère écrit précedemment ChangeXY2xy (cf 6.5.3 : 

fonction Tangentes(C,cA)
 local cI,r,xI,yI,xA,yA,XA,CM1,CM2,cM1,cM2,cU;
 cI,r:=C; 
 xI,yI:=cI;
 xA,yA:=cA;
 XA:=Longueur(cA,cI);
 cU:=[xA-xI,yA-yI]/XA;
 si XA >r alors
   CM1:=[r^2/XA,r*sqrt(1-r^2/XA^2)];
   CM2:=[r^2/XA,-r*sqrt(1-r^2/XA^2)];
   cM1:=ChangeXY2xy(CM1,cI,cU);
   cM2:=ChangeXY2xy(CM2,cI,cU);
   retourne [Droite(cM1,[xA,yA]),Droite(cM2,[xA,yA])];
 fsi;
 si XA==r alors 
   CM1:=[r,1];
   cM1:=ChangeXY2xy(CM1,cI,cU);
   retourne [Droite(cM1,[xA,yA])];
 fsi
 retourne [];
ffonction:;














On vérfie avec Xcas :



6.6.7  Solution analytique des tangentes à un cercle

On peut aussi faire une résolution analytique pour construire la (ou les) tangente(s) à un cercle CC passant par un point AA.
On pourra se servir des programmes écrits précédement : Longueur (cf 6.1.1), Droite(cf 6.2.1), Cercle (cf 6.6.3) et Solution12 (cf 4.2).

On considère un repère orthonormé dans lequel le centre II du cercle CC de rayon rr a pour coordonnées [x I,y I][x_I,y_I].
C C a pour équation (x−x I) 2+(y−y I) 2=r 2(x-x_I)^2+(y-y_I)^2=r^2 soit x 2+y 2−2x Ix−2y Iy+x I 2+y I 2−r 2=0x^2+y^2-2x_Ix-2y_Iy+x_I^2+y_I^2-r^2=0 Soit A A un point de coordonnées [x A,y A] [x_A,y_A].
Si A A se trouve à l’extérieur du cercle C C, on peut mener par A A, deux tangentes. Les points de contact M 1 M_1 et M 2 M_2 de ces tangentes avec C C sont aussi les points d’intersection de C C et du cercle de diamètre IA IA.
Le cercle de diamètre IA IA a pour centre K K et rayon RR où KK est le milieu de IA IA de coordonnées [x K,y K]=c K [x_K,y_K]=c_K=Milieu(cI,cA)(cI,cA) et R= R=Longueur(cI,cA)/2(cI,cA)/2. Ce cercle a donc comme équation (x−x K) +(y−y K) 2=R 2(x-x_K)^+(y-y_K)^2=R^2 i.e.
x 2+y 2−2x Kx−2y Ky+x K 2+y K 2−R 2=0x^2+y^2-2x_Kx-2y_Ky+x_K^2+y_K^2-R^2=0 Il faut donc résoudre le système d’inconnues x,yx,y x 2+y 2−2xIx−2yIy+xI 2+yI 2−r 2 = 0 x 2+y 2−2x Kx−2y Ky+x K 2+y K 2−R 2 = 0 \begin{matrix} x^2+y^2-2xIx-2yIy+xI^2+yI^2-r^2&=&0\\ x^2+y^2-2x_Kx-2y_Ky+x_K^2+y_K^2-R^2&=&0 \end{matrix} qui est équivalent à : x 2+y 2−2xIx−2yIy+xI 2+yI 2−r 2 = 0 2(xI−x K)x+2(yI−y K)y+x K 2+y K 2+r 2−xI 2−yI 2−R 2 = 0 \begin{matrix} x^2+y^2-2xIx-2yIy+xI^2+yI^2-r^2&=&0 \\ 2(xI-x_K)x+2(yI-y_K)y+x_K^2+y_K^2+r^2-xI^2-yI^2-R^2&=&0 \end{matrix} On a 2(xI−x K)=(xI−x A)2(xI-x_K)=(xI-x_A) et 2(yI−y K)=(yI−y A)2(yI-y_K)=(yI-y_A)
Or A≠I A\neq I donc x A≠x I≠x Kx_A\neq x_I \neq x_K ou y A≠y I≠y Ky_A \neq y_I \neq y_K. Si (yI−y K)≠0(yI-y_K) \neq 0 (resp (xI−x A)≠(xI-x_A) \neq ) alors on connaît yy (resp xx) en fonction de xx (resp yy) et il faut résoudre une équation de degré 2 en xx (res yy).
Si A A est sur le cercle C C, on peut mener par A A, une tangente (c’est une droite passant par A A et qui est perpendiculaire à IA IA.
Si A A est à l’intérieur du cercle C C, il n’y a pas de tangente passant par A A.
On utilise encore Longueur (cf 6.1.1), Droite (cf 6.2.1) et Cercle (cf 6.6.3), mais aussi le programme Solution12 écrit précedemment (cf 4.2 : On tape : 

fonction Tangenteq(C,cA)
 local cI,r,l,xI,yI,xA,yA,xK,yK,Eq,xM,yM,xM1,yM1,xM2,yM2,R,m;
 cI:=C[0];
 xI:=cI[0];
 yI:=cI[1];
 r:=C[1];
 l:=Longueur(cA,cI);
 xA:=cA[0];
 yA:=cA[1];
 R:=l/2;
 si l >r alors
  xK:=(xI+xA)/2;
  yK:=(yI+yA)/2;
  si (yI-yA)!=0 alors 
    yM:=(xK^2+yK^2+r^2-xI^2-yI^2-R^2+2*(xI-xK)*x)/(yA-yI);
    Eq:=x^2+yM^2-2xI*x-2yI*yM+xI^2+yI^2-r^2=0;
    [xM1,xM2]:=Solution12(Eq,x);
    yM1:=subst(yM,x=xM1);
    yM2:=subst(yM,x=xM2);
  sinon
    xM:=(xK^2+yK^2+r^2-xI^2-yI^2-R^2+2*(yI-yK)*y)/(xA-xI);
    Eq:=xM^2+y^2-2xI*xM-2yI*y+xI^2+yI^2-r^2=0;
    [yM1,yM2]:=Solution12(Eq,y)
    xM1:=subst(xM,y=yM1);
    xM2:=subst(xM,y=yM2);
  fsi;
 retourne [Droite(cA,[xM1,yM1]),Droite(cA,[xM2,yM2])];
 fsi;
 si l==r alors
   si (yI-yA)!=0 alors
     m:=normal(-(xA-xI)/(yA-yI));
     retourne [Droite([xA,yA],m)];
   sinon
     retourne [Droite([xA,yA],[xA,yA+1])];
   fsi;
 fsi;
 retourne [];
ffonction:;














On vérifie avec Xcas :



Chapitre 7  Quelques tests géométriques

7.1  Test d’alignement de 3 points

Établir que trois points sont alignés ou non alignés.
Si les 3 points sont confondus Estaligne(A,B,C) renvoie 2
Si les 3 points sont alignés Estaligne(A,B,C) renvoie 1
Si les 3 points ne sont pas alignés Estaligne(A,B,C) renvoie 0
On tape : 

fonction Estaligne(cA,cB,cC)
 local xA,yA,xB,yB,xC,yC;
 si cA==cB et cA==cC alors retourne 2; fsi;
 si cA==cB ou cA==cC alors retourne 1; fsi;
 xA:=cA[0];
 yA:=cA[1];
 xB:=cB[0];
 yB:=cB[1];
 xC:=cC[0];
 yC:=cC[1];
 si normal((xB-xA)*(yC-yA)-(xC-xA)*(yB-yA))==0 alors 
   retourne 1;
 fsi; 
 retourne 0;

ffonction:;










On fait la figure avec Xcas :

On vérifie avec Xcas :



7.2  Test de parallélisme de 2 droites

Soient deux droites D 1D_1 et D 2D_2 d’équation :
a 1x+b 1y+c 1=0a_1x+b_1y+c_1=0 et a 2x+b 2y+c 2=0a_2x+b_2y+c_2=0
Ces 2 droites sont parallèles si a 1b 2=a 2b 1a_1b_2=a_2b_1.
On utilise la fonction Coeffsdroite (cf 6.2.2 qui calcule les coefficients a, b et c de l’équation d’une droite ax+by+c=0 : On tape : 

fonction Estparallele(d1,d2)
 local a1,a2,b1,b2,d,c1,c2;
 a1,b1,c1:=Coeffsdroite(d1);
 a2,b2,c2:=Coeffsdroite(d2);
 d:=normal(a2*b1-b2*a1);
 si d==0 alors retourne 1; fsi;
 retourne 0;
ffonction:;












On fait la figure avec Xcas :

On vérifie avec Xcas :



7.3  Caractériser alignement et parallélisme par la colinéarité

Trois points AA, B B et C C sont alignés si les vecteurs AB AB et AC AC sont colinéaires.
Deux droites AB AB et CD CD sont parallèles si les vecteurs AB AB et CD CD sont colinéaires.

Chapitre 8  Statistiques

8.1  Calcul de moyenne et écart-type

Exercice : Écrire une fonction prenant en argument la liste des données et renvoyant sa moyenne et son écart-type, au moyen d’une boucle pour (sans utiliser mean ou stddev qui sont les commandes Xcas pour moyenne et écart-type). 

fonction Stats(L)
  local j,Lj,n,s,s2;
  n:=dim(L);
  s:=0; s2:=0;
  pour j de 0 jusque n-1 faire
    Lj := L[j];
    s := s+Lj 
    s2 := s2+Lj^2;
  fpour
  retourne s/n,sqrt(s2/n-(s/n)^2);
ffonction:;






On vérifie avec Xcas :


Exercice : Écrire une fonction prenant en argument la liste des données et renvoyant sa médiane.
Indication : Pour déterminer une médiane, il faut au préalable trier les données, ce qui est la partie difficile de l’algorithme, le reste de l’algorithme est simple. Au niveau du lycée on peut utiliser la commande Xcas sort qui trie une liste par ordre croissant, puis on renvoie l’élément d’indice la taille de la liste/2. 

fonction Median(L)
  local n;
  n:=dim(L);
  L:=sort(L);
  si irem(n,2)==1 alors 
    retourne L[(n-1)/2];
  sinon
    retourne (L[n/2-1]+ L[n/2])/2.;
  fsi;
ffonction:;










On vérifie avec Xcas :


Exercice : Écrire une fonction qui calcule la moyenne et l’écart-type et qui a comme argument soit la liste alternant valeur et effectif soit 2 listes. 

fonction Statexo1(L)
  local j,lj,n,n1,s,s2,vj,ej;
  n:=dim(L);
  si type(n)!=vecteur alors retourne "erreur"; fsi;
  s:=0; 
  s2:=0;
  n1:=n[0];
  n:=sum(col(L,1));
  pour j de 0 jusque n1-1 faire
    lj := L[j];
    vj := lj[0];
    ej := lj[1];
    s := s+vj*ej 
    s2 := s2+vj^2*ej;
  fpour;
  retourne s/n,sqrt(s2/n-(s/n)^2);
ffonction:;
fonction Statexo2(L1,L2)
  local j,vj,ej,n,n1,n2,s,s2;
  n1:=dim(L1);
  n2:=dim(L2);
  si n1!=n2 alors retourne "erreur"; fsi;
  n:=sum(L2);
  s:=0; 
  s2:=0;
  pour j de 0 jusque n1-1 faire
    vj := L1[j];
    ej := L2[j];
    s := s+vj*ej 
    s2 := s2+vj^2*ej;
  fpour;
  retourne s/n,sqrt(s2/n-(s/n)^2);
ffonction:;


On a mesuré la taille en cm (arrondie à l’entier le plus proche) de 200 fossiles de la même espèce. On a obtenu pour k=0..12 une taille L1[k] d’effectif de L2[k].
Calculer la moyenne et l’écart-type de cette distribution.








On a mesuré la taille en cm (arrondie à l’entier le plus proche) d’une autre espèce de fossiles. On a obtenu pour k=0..12 une taille L1[k] d’effectif de L3[k].
Calculer la moyenne et l’écart-type de cette distribution.






On vérifie avec Xcas :



8.2  Simulation d’un échantillon

Exercice : Générer aléatoirement nn valeurs 0 ou 1, la probabilité d’avoir 1 étant fixée à pp (pour faire cela, on comparera avec pp le résultat de la commande Xcas alea(0,1) qui renvoie un réel entre 0 et 1). Calculer la fréquence de 1 observée. 

fonction Simu(n,p)
  local j,a,n1;
  n1:=0;
  pour j de 1 jusque n faire
    a:=alea(0,1);
    si a<=p alors n1:=n1+1; fsi;
  fpour
  retourne n1/n;
ffonction:;

onload

On peut visualiser les fréquences obtenues avec la commande plotlist([y0,...,yn]) de Xcas qui trace la ligne polygonale reliant les points d’abscisse k et d’ordonnée yk pour k=0..n.

Commandes Xcas permettant de faire le calcul directement :


La commande randvector génère ici nn valeurs aléatoires selon la loi binomiale de paramètres 1 et pp, on en fait ensuite la moyenne. On peut bien sur utiliser d’autres lois que la loi binomiale, par exemple la loi uniforme (uniform), la loi normale (normald), la loi exponentielle (exponential), ...

8.3  Intervalle de fluctuation

Écrire un algorithme effectuant NN simulations d’échantillons, en utilisant la fonction précédente, renvoyer la liste des fréquences ainsi que la proportion de fréquences situées en-dehors de l’intervalle [p−1/n,p+1/n][p-1/\sqrt{n},p+1/\sqrt{n}].

Rappelons qu’on s’intéresse à cet intervalle, parce qu’une simulation suit une loi binomiale de moyenne npnp et d’écart-type σ=np(1−p)\sigma=\sqrt{n p (1-p)} donc les fréquences suivent une loi binomiale de moyenne pp et d’écart-type σ˜=σ/n=p(1−p)/n\tilde{\sigma}=\sigma/n=\sqrt{p (1-p)/n}. Or 4p(1−p)=1−(2*p−1) 2⇒4p(1−p)≤14p(1-p)=1-(2*p-1)^2 \Rightarrow 4p(1-p)\leq 1 donc 2σ˜=2σn=4p(1−p)n≤1n2\tilde{\sigma}=2\frac{\sigma}{n}= \sqrt{\frac{4p(1-p)}{n}} \leq \frac{1}{\sqrt{n}} Pour nn grand, la loi binomiale s’approche d’une loi normale ayant cet écart type.

On utilise la fonction Simu écrite précédemment (cf 8.2). 

fonction Fluctuat(N,n,p)
  local j,L,out;
  L:=[];
  out:=0;
  pour j de 0 jusque N-1 faire
    L[j]:=Simu(n,p);
    si abs(L[j]-p)>1/sqrt(n) alors out:=out+1; fsi;
  fpour;
  retourne out/N,L;
ffonction:;


On lance 20 fois une pièce de de monnaie mal équilibrée, la probabilité d’obtenir face étant égale à 0.4.
Simu(20,0.4) renvoie donc la fréquence du nombre de faces observées. On effectue plusieurs fois 100 simulations :





On peut visualiser la répartition de ces fréquences :

Avec les commandes de Xcas
On génère une séquence de NN moyennes de vecteurs de nn valeurs aléatoires selon la loi binomiale de paramètres 1 et pp :


On compte les moyennes dont l’écart à pp est plus grand que 1/n1/\sqrt{n} :


On peut accélérer le calcul en utilisant le générateur aléatoire selon la loi binomiale de paramètres nn et pp


On peut enfin tracer le graphe de l’évolution de la proportion de fréquences en-dehors de l’intervalle [p−1/n,p+1/n][p-1/\sqrt{n},p+1/\sqrt{n}] lorsque NN augmente. On génère une liste de fréquences :
puis on compte les fréquences en-dehors de l’intervalle et on stocke les fréquences dans une liste 

L:=[]; compteur:=0; a:=p-1/sqrt(n); b:=p+1/sqrt(n);
pour j de 0 jusque N-1 faire 
  si l[j]<a ou l[j]>b alors compteur++; fsi;
  L[j]:=compteur/(j+1);
fpour;
gl_y=0..0.1;plotlist(L)


On a utilisé ici la fonction d’incrémentation, compteur++ est équivalent à compteur=compteur+1.

La probabilité théorique d’être dans l’intervalle [p−1/n,p+1/n][p-1/\sqrt{n},p+1/\sqrt{n}] est donnée par la commande Xcas :

Il y a donc une probabilité faible (de l’ordre de 4%) de ne pas être dans l’intervalle de fluctuation.
La probabilité d’être dans l’intervalle plus précis [np−σ/n,np+σ/n][np-\sigma/\sqrt{n},np+\sigma/\sqrt{n}] est donnée par :

Elle est ici identique parce que les bornes de l’intervalle ont la même partie entière.

8.4  Évolution d’une fréquence.

On illustre l’évolution d’une fréquence vers sa moyenne théorique (espérance).

Expérience : on tire un dé à 6 faces, si le résultat est 1 on renvoie 1, si c’est 2 à 4 on renvoie 2, si c’est 5 ou 6 on renvoie 4. Simulation, en utilisant la fonction piecewise : 

fonction experience()
  local a;
  a:=alea(6)+1; // simule un de 6
  return piecewise(a<2,1,a<5,2,4);
ffonction:;

onload

On effectue NN expériences et on regarde l’évolution de la moyenne des résultats. 

fonction evolutionmoyenne1(N)
  local l,s,j,a;
  l:=[];
  s:=0;
  pour j de 1 jusque N faire
    s:=s+experience();
    l:=append(l,s/j);
  fpour;
  return l;
ffonction:;

onload

Dans la version HTML interactive, cliquez plusieurs fois sur le bouton ok pour voir différents comportements.

On peut écrire une fonction plus générale en passant la fonction experience en argument 

fonction evolutionmoyenne(experience,N)
  local l,s,j,a;
  l:=[];
  s:=0;
  pour j de 1 jusque N faire
    s:=s+experience();
    l:=append(l,s/j);
  fpour;
  return l;
ffonction:;

onload

8.5  Triangles de spaghettis

On prend un spaghetti qu’on casse en 3 morceaux, peut-on construire un triangle avec ces 3 morceaux ? On fixe l’unité de longueur au spaghetti entier. On a donc 3 longueurs aa, bb et c=1−a−bc=1-a-b et il faut vérifier les inégalités triangulaires a<b+c,b<a+c,c<a+ba&lt;b+c, b&lt;a+c, c&lt;a+b (voir la section 9.4).

Première méthode de coupe : on tire au hasard xx et yy entre 0 et 1. Si x<yx&lt;y, on pose a=x,b=y−xa=x, b=y-x (et donc c=1−yc=1-y) sinon on échange xx et yy (a=ya=y, b=x−yb=x-y et c=1−xc=1-x). Simulation, correct vérifie l’inégalité triangulaire, spag1 renvoie 1 si on peut faire un triangle et 0 sinon : 

correct(a,b,c):=a<b+c et b<a+c et c<a+b:;

fonction spag1()
  local x,y,c;
  x:=alea(0,1);
  y:=alea(0,1);
  si y>x alors 
    return correct(x,y-x,1-y); 
  sinon 
    return correct(y,x-y,1-x); 
  fsi;
ffonction:;

fonction spagn(n)
  local L,s;
  L:=[]; // liste des frequences de succes
  s:=0; // nombre de succes
  pour j de 1 jusque n faire
    si spag1() alors s++ fsi; 
    L:=append(L,s/j); 
  fpour;
  return L;
ffonction:;

onload

Exercice : modifier spag1 pour couper le spaghetti en prenant au hasard, puis en coupant le morceau le plus long au hasard. 

fonction spag1()
  local x,y,c;
  x:=alea(0,1);
  si x>1/2 alors
    y:=x; // on casse x
    x:=x*alea(0,1); 
  sinon // on casse 1-x
    y:=x+(1-x)*alea(0,1);
  fsi;
  return correct(x,y-x,1-y); 
ffonction:;


Voir l’étude à la fin du manuel Algorithmes et simulation de Xcas.

8.6  Les aiguilles de Buffon

Le naturaliste Buffon, en 1777 a posé le problème de l’aiguille en ces termes : "Je suppose que dans une chambre, dont le parquet est simplement divisé par des joints parallèles, on jette en l’air une baguette et que l’un des joueurs parie que la baguette ne croisera aucune des parallèles du parquet..."

On peut modéliser le problème en supposant que la distance entre les paralléles est de 1, et que les parallèles sont horizontales, d’équations y=k,k∈ℤy=k, k \in \mathbb{Z}. On suppose que la longueur de l’aiguille est ll. Lorsqu’elle tombe sur le parquet, on suppose qu’une de ses extrémités est en (x,y)(x,y) et qu’elle fait un angle θ\theta avec l’horizontale, son autre extrémité est donc en (x+lcos(θ),y+lsin(θ))(x+l\cos(\theta),y+l\sin(\theta)). Elle coupe une des parallèle si l’intervalle [y,y+lsin(θ)][y,y+l\sin(\theta)] contient un entier c’est-à-dire si la partie entière de yy diffère de celle de y+lsin(θ)y+l\sin(\theta). On observe que la valeur de xx n’a pas d’importance, et que la valeur de yy modulo 1 non plus. Pour effectuer la simulation, on suppose donc que yy est un réel aléatoire selon la loi uniforme entre 0 et 1, et θ\theta un réel aléatoire selon la loi uniforme entre −π2-\frac{\pi}{2} et π2\frac{\pi}{2} 

fonction buffonpi(l)
  local y,theta;
  y:=alea(0,1);
  theta:=alea(-.5,.5)*pi;
  si floor(y+l*sin(theta))!=0 alors return 1; sinon return 0; fsi;
ffonction:;

onload
Tests pour quelques valeurs de ll


On peut aussi générer la direction aléatoire sans utiliser le nombre π\pi en tirant au hasard deux réels entre 0 et 1 et si le point obtenu est dans le disque unité, on prend la direction obtenue. 

fonction buffonsanspi(l)
  local y,X,Y;
  y:=alea(0,1); 
  repeter X:=alea(0,1); Y:=alea(0,1) jusqua X*X+Y*Y<=1;
  si floor(y+l*Y/sqrt(X^2+Y^2))!=0 alors return 1; sinon return 0; fsi;
ffonction:;

onload

On peut enfin définir algébriquement

Pour conjecturer le comportement de la probabilité en fonction de ll on va l’estimer par la fréquence observée au bout de NN d’expériences, par exemple on prendra N=1000N=1000 (pour éviter un temps d’exécution trop long) 

fonction probabuffon(l,N)
  local s,j;
  s:=0;
  pour j de 1 jusque N faire
    s := s+buffonpi(l);
  fpour;
  return s/N;
ffonction:;

onload

Pour ll petit, le comportement est linéaire, pour ll grand on observe une asymptote horizontale (qui est y=1y=1 car lorsque la taille ll de l’aiguille est de plus en plus grande, la probabilité de ne pas couper une horizontale tend vers 0 puisque la direction θ\theta doit être de plus en plus proche). On peut démontrer que le coefficient de proportionnalité pour ll petit vaut 2π\frac{2}{\pi}, (cf. le manuel Exercices de Xcas pour l=1l=1).

Pour obtenir un tracé plus précis sans attendre trop longtemps, il faut trouver une astuce pour accélérer le calcul dans probabuffon. Pour cela on part de la version algébrique de buffon qui se prête au calcul appliqué en parallèle à une liste (sin appliqué à une liste renvoie la liste des sinus des éléments de la liste, + effectue la somme composante par composante, etc.). On doit renvoyer 0 si le nombre de parallèles traversées est nul et 1 sinon, donc si on fait NN expériences, la proportion est donnée par :

On peut maintenant tracer le graphe de manière plus précise, par exemple avec N=5000N=5000 et un pas de 0.03 sur [0,3][0,3], sans patienter trop longtemps :

Ce type d’optimisation est fréquent dans les langages interprétés, on essaie d’utiliser les commandes natives du logiciel pour effectuer les boucles les plus internes au lieu de les faire exécuter par l’interpréteur, forcément plus lent que les commandes natives qui sont compilées.

8.7  Marche aléatoire à 1 dimension.

Un marcheur ivre se déplace sur un trottoir, en faisant un pas aléatoirement vers la droite ou vers la gauche. On simule sa position après nn pas (on suppose qu’il part de l’origine). 

fonction marche(n)
  local j,x;
  x:=0;
  pour j de 1 jusque n faire
    si alea(2)==1 alors x++; sinon x--; fsi;
  fpour;
  return x;
ffonction:;

onload
On effectue NN marches aléatoires et on trace l’histogramme des positions, par exemple pour n=100n=100 et N=3000N=3000

On peut aussi s’intéresser au nombre de passage par l’origine. 

fonction retour(n)
  local j,x,r;
  x:=0; r:=0;
  pour j de 1 jusque n faire
    si alea(2)==1 alors x++; sinon x--; fsi;
    si x==0 alors r++; fsi;
  fpour;
  return r;
ffonction:;

onload
et conjecturer son espérance par observation d’un nombre important de marches

On peut aussi observer l’espérance en fonction du nombre de pas. Pour cela, on approche l’espérance par exemple par la moyenne de 1000 nombre de retours. 

fonction moyenneretour1(n)
  local s,j;
  s:=0;
  pour j de 1 jusque 1000 faire
    s := s+retour(n);
  fpour;
  return s/1000;
ffonction:;

onload

Comme pour les aiguilles de Buffon, le temps de calcul est long (c’est pour cela que l’on a mis un pas de 20 dans la commande précédente), mais il est possible d’accélérer en faisant plusieurs optimisations : 

fonction moyenneretour(N,n) // N experiences, marche de n
  local k,pos,r;
  pos:=seq(0,N); // N marcheurs a l'origine
  r:=0;
  n:=iquo(n,2);
  pour k de 1 jusque n faire
    pos:=pos+randvector(N,2)+randvector(N,2); 
    r:=r+count_eq(k,pos); // nombre de passage origine translatee
  fpour;
  retourne r/N;
ffonction:;

onload
On peut maintenant faire le tracé avec une bonne précision en quelques secondes :

8.8  Les urnes de Polya

On place dans une urne rr boules rouges et bb boules bleues, indiscernables au toucher. On tire une boule, on note sa couleur, et on remet dans l’urne cette boule ainsi qu’une boule de même couleur (le nombre total de boules augmente donc de 1). On recommence, on effectue en tout nn tirages.

On fait une simulation, on va renvoyer la liste des proportions de boules rouges dans l’urne au cours de l’expérience. Il y a rr boules rouges parmi r+br+b, on convient donc que la boule tirée est rouge si un tirage d’entier dans [0,r+b[[0,r+b[ est strictement inférieur à rr. 

fonction polya(r,b,n)
  local L,j;
  L:=[r/(r+b)];
  pour j de 1 jusque n faire
    si alea(r+b)<r alors r++; sinon b++; fsi;
    L[j]:=r/(r+b);
  fpour;
  return L;
ffonction:;

onload
Exemple :
Simulation avec 1000 tirages et 1 boule rouge et 1 boule bleue au début :
Dans la version HTML, si on clique plusieurs fois, on observe que la valeur limite est très variable. On peut s’intéresser à la répartition de cette proportion limite de boules rouges (obtenue ici au bout de 1000 étapes). On modifie la fonction précédente pour ne renvoyer que la dernière proportion. 

fonction polya1(r,b,n)
  local j;
  pour j de 1 jusque n faire
    si alea(r+b)<r alors r++; sinon b++; fsi;
  fpour;
  return r/(r+b);
ffonction:;

onload
Puis on fait l’histogramme des fréquences pour NN expériences
Le temps de calcul commence à s’allonger, on peut essayer d’optimiser un peu. On observe que le nombre total de boules augmenté de 1 à chaque tirage, il suffit donc de suivre la valeur de rr 

fonction polya2(r,b,n)
  local j,total,totalalafin;
  totalalafin:=r+b+n-1;
  pour total de r+b jusque totalalafin faire
    si alea(total)<r alors r++; fsi;
  fpour;
  return r/(total-1);
ffonction:;

onload

Une autre façon d’optimiser consiste à observer que j ne sert pas dans la boucle pour de polya1. 

fonction polya3(r,b,n)
  seq(when(alea(r+b)<r,r++, b++),n);
  return r/(r+b);
ffonction:;

onload

Pour N=1000N=1000, on s’aperçoit que la distribution semble uniforme. Ceci n’est plus le cas pour d’autres valeurs de rr et bb, dans la version HTML, vous pouvez tester diverses valeurs initiales, par exemple 5,5 ou 1,5.

Chapitre 9  Les algorithmes du document ressource Python d’eduscol

On propose dans ce chapitre des versions Xcas de programmes Python donnés dans ce document

Pour les statistiques, voir le chapitre 8.

Pour la dichotomie, voir 4.1.

9.1  Arithmétique

On renvoie au manuel de programmation de Xcas (menu Aide, Manuels), on donne ici rapidement les équivalents Xcas du document eduscol.

9.1.1  Euclide

On calcule le PGCD de aa et bb en observant que si bb est nul c’est aa, sinon c’est le PGCD de bb et du reste de la division euclidienne de aa par bb (irem(a,b)) 

fonction pgcd(a,b)
  tantque b!=0 faire 
    a,b:=b,irem(a,b);
  ftantque;
  return a;
ffonction:;

onload

9.1.2  Écriture en base 2

L’écriture de nn en base 2 est l’écriture de n/2n/2 à laquelle on ajoute le reste de la division nn par 2. 

fonction base2(n)
  local l;
  l:=[];
  tantque n>0 faire
    l:=append(l,irem(n,2));
    n:=iquo(n,2);
  ftantque;
  return revlist(l);
ffonction:;

onload
Il faut inverser l’ordre des éléments dans la liste avant de la renvoyer, parce qu’on calcule en premier le dernier bit de l’écriture de nn en base 2.

L’opération inverse se fait en utilisant le même principe : lorsqu’on ajoute un bit à la fin de l’écriture de nn en base 2, cela revient à multiplier nn par 2 et lui ajouter la valeur de ce bit. 

fonction base10(l)
  local n,x;
  n:=0;
  pour x in l faire
    n=2*n+x;
  fpour;
  return n;
ffonction:;

onload

La taille de l’écriture en base 2 s’obtient par dim(l) ou directement par le programme suivant 

fonction taille2(n)
  local l;
  l:=0;
  tantque n>0 faire
    n:=iquo(n,2);
    l++;
  ftantque;
  return l;
ffonction:;

onload

9.1.3  Test de primalité

On teste si nn est divisible par un entier d≤nd\leq \sqrt{n}. 

fonction estpremier(n)
  local d;
  si n<2 alors return false; fsi;
  d:=2;
  tantque d*d<=n faire
    si irem(n,d)=0 alors return false; fsi;
    d++;
  ftantque;
  return true;
ffonction:;

onload

Remarque : cet algorithme est qualifié de naïf car il ne permet pas de tester la primalité de grands entiers.

9.1.4  Factorisation d’entiers

Au lieu de s’arrêter et d’indiquer que le nombre n’est pas premier lorsqu’on a une division exacte par dd, on ajoute dd à la liste des facteurs et on divise nn par dd. Lorsqu’on sort de la boucle extérieure, nn vaut 1 ou est premier, il ne faut pas oublier de l’ajouter à la liste des facteurs. 

fonction facto(n)
  local l,d;
  l:=[]; d:=2;
  tantque d*d<=n faire
    tantque irem(n,d)=0 faire
      l:=append(l,d);
      n:=n/d;
    ftantque;
    d++;
  ftantque;
  si n>1 alors l:=append(l,n); fsi;
  return l;
ffonction:;

onload




Exercice :
Comparer l’efficacité de l’algorithme précédent avec l’algorithme du document eduscol et compter le nombre d’itérations lorsque nn est premier dans chacun de ces 2 programmes.

fonction facto1(n)
  local l,d;
  l:=[]; d:=2;
  tantque n>1 faire
    si irem(n,d)=0 alors
      tantque irem(n,d)=0 faire
        l:=append(l,d);
        n:=n/d;
      ftantque;
    fsi;
    d++;
  ftantque;
  return l;
ffonction:;

onload


Remarque : ce type d’algorithme est qualifié de naïf, car il ne permet pas de factoriser des nombres ayant de grands facteurs premiers.

9.2  Longueur d’un arc de courbe

On cherche la longueur approchée d’un arc de courbe d’équation y=f(x)y=f(x) entre les points d’abscisses aa et bb. Pour cela on approche l’arc de courbe par une ligne polygonale composée de nn petits segments reliant les points de la courbe d’abscisses a+kha+kh et a+(k+1)ha+(k+1)h pour k∈[0,n−1]k \in [0,n-1] et h=b−anh=\frac{b-a}{n}. 

fonction longueurcourbe(f,a,b,n)
  local l,k,h;
  h:=evalf((b-a)/n);
  l:=0;
  pour k de 0 jusque n-1 faire
    l:=l+distance(point(a+k*h,f(a+k*h)),point(a+(k+1)*h,f(a+(k+1)*h)));
  fpour;
  return l;
ffonction:;

onload

Exercice :
Cette fonction longueurcourbe est relativement inefficace, car on calcule plusieurs fois les mêmes quantités. Utilisez des variables locales pour la rendre plus efficace.

Solution : 

fonction longueurcourbe(f,a,b,n)
  local l,k,h,x,M,N;
  h:=evalf((b-a)/n);
  l:=0;
  x:=a;
  M:=point(x,f(x));
  pour k de 0 jusque n-1 faire
    x:=x+h;
    N:=point(x,f(x));
    l:=l+distance(M,N);
    M:=N;
  fpour;
  return l;
ffonction:;


Remarque : hh est approché, donc en effectuant la boucle on va accumuler des erreurs d’arrondis. Si l’erreur est faite par excès, la dernière valeur de xx risque d’être un peu supérieure à 1, et f(x)f(x) devient alors complexe, avec une partie imaginaire très petite. Ceci n’a pas d’importance dans Xcas, car l’instruction point(x,y) renvoie le point d’affixe x+iyx+iy. Dans d’autres langages, par exemple Python, cela peut provoquer une erreur.

Exercice :
Faire afficher la ligne polygonale dont on calcule la longueur.

Solution : 

fonction approxcourbe(f,a,b,n)
  local L,k,h,x,M,N;
  h:=evalf((b-a)/n);
  x:=a;
  M:=point(x,f(x));
  L:=[M];
  pour k de 0 jusque n-1 faire
    x:=x+h;
    N:=point(x,f(x));
    L:=append(L,N);
    M:=N;
  fpour;
  return polygone_ouvert(L);
ffonction:;



9.3  Réfraction et recherche de minimas

On se donne une courbe d’équation y=f(x)y=f(x) séparant deux milieux d’indices n 1n_1 et n 2n_2 et on cherche le chemin lumineux reliant deux points A(x A,y A)A(x_A,y_A) et B(x B,y B)B(x_B,y_B) situés de part et d’autre de la courbe, il s’agit de deux segments de droite AMAM et BMBM où MM est le point de la courbe tel que la somme n 1AM+n 2BMn_1AM+n_2BM est minimal. Comme MM a pour coordonnées (x,f(x))(x,f(x)), on peut calculer cette somme en fonction de xx g(x)=n 1(x−x A) 2+(f(x)−y A) 2+n 2(x−x B) 2+(f(x)−y B) 2g(x)=n_1\sqrt{(x-x_A)^2+(f(x)-y_A)^2}+n_2\sqrt{(x-x_B)^2+(f(x)-y_B)^2} Il s’agit donc de déterminer le minimum de la fonction gg (en supposant connue la fonction ff).

9.3.1  Minimum d’une fonction

On commence par la recherche approchée du minimum d’une fonction gg. On se donne un point de départ xx et un pas hh, on regarde si on diminue la valeur de gg en se déplaçant vers la gauche. Si c’est le cas, on continue à se déplacer vers la gauche jusqu’à ce que gg ne diminue plus, on a alors atteint un minimum local relativement à la discrétisation choisie. Si ce n’est pas le cas, on essaie de se déplacer vers la droite.1 

fonction minih(g,x,h) 
  // recherche d'un minimum local de g a partir de x en se deplacant
  // par pas de h vers la gauche ou vers la droite
  si g(x-h)<g(x) alors
    tantque g(x-h)<g(x) faire x:=x-h; ftantque;
  sinon
    tantque g(x+h)<g(x) faire x:=x+h; ftantque;
  fsi;
  retourne x;
ffonction:;

onload
Exemple :
Recherche du minimum de la fonction (x 2−2) 2(x^2-2)^2 en partant de 2.0 (prendre le carré d’une expression, ici x 2−2x^2-2, et en chercher le minimum est une méthode de recherche d’une solution approchée)
Attention ! ce programme peut tourner en boucle indéfiniment si gg décroit indéfiniment. Un programme plus robuste fixera un nombre maximal d’itérations, par exemple ici 1000 par défaut. 

fonction minih(g,x,h,N=1000) 
  local j;
  si g(x-h)<g(x) alors
    pour j de 1 jusque N faire 
      si g(x-h)>g(x) alors return x; fsi;
      x:=x-h;
    fpour;
  sinon
    pour j de 1 jusque N faire 
      si g(x+h)>g(x) alors return x; fsi;
      x:=x+h;
    fpour;
  fsi;
  retourne "non trouve";
ffonction:;


Exercice :
Améliorer ce programme pour calculer gg une seule fois par itération.

Solution :
Pour avoir une valeur de xx avec une précision fixée à l’avance, on commence avec un pas de hh (par défaut 0.1) et on divise le pas par 10. 

fonction mini(g,x,h=0.1,eps=1e-10) 
  // recherche d'un minimum local avec une precision de eps
  tantque h>eps faire
    x:=minih(g,x,h);
    h:=h/10;
  ftantque;
  retourne minih(g,x,h);
ffonction:;

onload
On effectue un dernier appel à minih pour assurer que la précision est meilleure que 1e-10.
Exercice :
expliquer pourquoi il est plus rapide d’appeler mini(g,1.0,0.1,1e-10) que minih(g,1.0,1e-10).

9.3.2  Application à la réfraction

Appliquons maintenant au problème de la réfraction. La fonction refraction prend en arguments la fonction ff définissant la courbe séparatrice, les points AA et BB et les indices de réfraction, elle renvoie le point MM. 

fonction refraction(f,A,B,n1,n2)
  local g,x,tst;
  si f(abscisse(A))<ordonnee(A) ou f(abscisse(B))>ordonnee(B) alors 
    return "A et B sont du meme cote du graphe!"; 
  fsi;
  g(x):=n1*distance(A,point(x,f(x)))+n2*distance(B,point(x,f(x))); 
  x:=mini(g,abscisse(milieu(A,B)));
  return point(x,f(x));
ffonction:;

onload
Illustration avec une fonction linéaire 1−2x1-2x, la séparatrice est la droite DD d’équation y=1−2xy=1-2x
Pour tester avec une courbe non linéaire, par exemple avec la fonction f(x)=cos(5x)f(x)=\cos(5x), il suffit de modifier la définition de ff :

9.3.3  Discussion

L’application à la réfraction est certainement trop difficile pour des élèves débutants, on définit en effet ici une fonctionnelle (fonction dont un argument est une fonction), et on définit une fonction dans une autre fonction (la fonction gg). De plus la définition de gg ci-dessus n’est pas recommandée, car elle dépend de la valeur de paramètres n 1,n 2,An_1,n_2, A et BB qui ne sont pas passés en argument (gg n’est pas une fonction pure, i.e. indépendante du contexte). Pour rendre gg indépendante du contexte, il faut remplacer dans son expression n1*distance(A,M)+n2*distance(B,M)
n 1,n 2,A,Bn_1,n_2,A,B par leurs valeurs. Dans Xcas, on peut le faire en utilisant le moteur de calcul formel. On utilise une variable symbolique x pour calculer l’expression de gg, c’est le rôle de la commande purge(x) ci-dessous, et on utilise la commande unapply qui permet de définir une fonction à partir d’une expression. 

fonction refraction(f,A,B,n1,n2)
  local g,M,x,tst,xM;
  tst:=(f(abscisse(A))-ordonnee(A))*(f(abscisse(B))-ordonnee(B));
  si tst>=0 alors return "A et B sont du meme cote du graphe!"; fsi;
  purge(x);
  M:=point(x,f(x));
  g:=unapply(n1*distance(A,M)+n2*distance(B,M),x);
  xM:=mini(g,abscisse(milieu(A,B)));
  return point(xM,f(xM));
ffonction:;


On a aussi amélioré le test que les deux points AA et BB sont bien de part et d’autre de la courbe en introduisant une variable locale tst qui doit être négative.

Dans des langages non formels, pour faire les choses proprement, il faut passer explicitement les paramètres A,B,n1,n2 à la fonction g, en les regroupant (dans une liste dans un langage de script, par un pointeur vers une structure en C). Le prototype de la fonction g est alors g(x,params), celui des fonctions mini est mini(g,param,x,h,eps). Mais ceci complique bien sur la présentation au niveau du lycée.

9.3.4  Autre méthode de recherche de minimum

On suppose ici qu’on cherche le minimum d’une fonction gg sur un intervalle [a,b][a,b] avec gg d’abord décroissante puis croissante. On suppose donc qu’on a un triplet a,c,ba,c,b tel que g(c)g(c) est plus petit que g(a)g(a) et g(b)g(b) a<c<b,g(c)<g(a),g(c)<g(b)a&lt;c&lt;b, \quad g(c)&lt;g(a), g(c)&lt;g(b) On effectue ensuite une sorte de dichotomie. On se fixe une précision ε\epsilon

  1. On effectue une boucle tant que b−a>εb-a&gt;\epsilon
  2. On calcule la valeur de gg au milieu uu de [a,c][a,c]. Si g(u)g(u) est plus petit que g(a)g(a) et g(c)g(c) on peut utiliser le nouveau triplet a,u,ca,u,c, on passe à l’itération suivante.
  3. Sinon, on calcule la valeur de gg au milieu vv de [c,b][c,b]. Si g(v)g(v) est plus petit que g(c)g(c) et g(b)g(b) on peut utiliser le nouveau triplet c,v,bc,v,b, on passe à l’itération suivante.
  4. Sinon, g(u)g(u) est plus grand que g(c)g(c) ou que g(a)g(a) donc est plus grand que g(c)g(c) puisque g(c)<g(a)g(c)&lt;g(a), et de même g(v)g(v) est plus grand que g(c)g(c), donc on utilise le nouveau triplet u,c,vu,c,v et on passe à l’itération suivante.

Le programme se termine (En effet, si on applique la troisième règle, b−ab-a est divisé par 2. Si on applique uniquement la 1ère et la 2ème règle, si on applique deux fois de suite la première règle bb est remplacé par cc puis par le uu précédent donc on gagne un facteur 2, de même pour la deuxième règle, si on applique la première puis la deuxième bb est remplacé par cc et aa par uu donc on gagne aussi un facteur 2). 

fonction mini2(g,a,b,c,eps=1e-10)
  local u,v;
  si c<=a ou c>=b alors return "erreur"; fsi;
  si g(c)>=g(a) ou g(c)>=g(b) alors return "erreur"; fsi;
  tantque b-a>eps faire
    u:=(a+c)/2;
    si g(u)<g(a) et g(u)<g(c) alors a,c,b:=a,u,c; continue; fsi;
    v:=(b+c)/2;
    si g(v)<g(c) et g(v)<g(b) alors a,c,b:=c,v,b; continue; fsi;
    a,c,b:=u,c,v;
  ftantque;
  return a,b,c;
ffonction:;

onload

Exercice :
Rendre ce programme plus efficace en calculant le moins de fois possible les images par gg de a,b,c,u,va,b,c,u,v.

9.4  Solveur de triangle

On cherche à construire un triangle ABCABC dont les cotés sont donnés par a=BC,b=AC,c=ABa=BC,b=AC,c=AB où a,b,ca,b,c vérifient les inégalités triangulaires a<b+c,b<a+c,c<a+ba&lt;b+c, \quad b&lt;a+c, \quad c&lt;a+b On peut par translation se ramener au cas où AA est l’origine, puis par rotation à B(c,0)B(c,0), il s’agit donc de déterminer les coordonnées (x,y)(x,y) de CC. 

c:=3; x:=1; y:=2;
A:=point(0,0,legende="A(0,0)"); 
B:=point(c,0,legende="B(c,0)"); 
C:=point(x,y,legende="C(x,y)");
triangle(A,B,C);

onload
On a deux équations a 2=BC 2=(x−c) 2+y 2,b 2=AC 2=x 2+y 2a^2=BC^2=(x-c)^2+y^2, \quad b^2=AC^2=x^2+y^2 En en faisant la différence, on obtient a 2−b 2=(x−c) 2−x 2=−2cx+c 2a^2-b^2=(x-c)^2-x^2=-2cx+c^2 d’où l’on tire la valeur de xx x=c 2−(a 2−b 2)2cx=\frac{c^2-(a^2-b^2)}{2c} puis la deuxième équation nous donne deux valeurs pour yy (correspondant à deux triangles symétriques) y=±b 2−x 2y=\pm \sqrt{b^2-x^2} Remarque :
Puisque a,b,ca,b,c vérifient les inégalités triangulaires a<b+c,b<a+c,c<a+b a&lt;b+c, \quad b&lt;a+c, \quad c&lt;a+b si x=c 2−(a 2−b 2)2cx=\frac{c^2-(a^2-b^2)}{2c} alors b 2−x 2≥0b^2-x^2\geq 0, en effet :
4c 2x 2=(b 2+c 2−a 2) 24c^2x^2=(b^2+c^2-a^2)^2 donc
4c 2(b 2−x 2)=(2cb) 2−(b 2+c 2−a 2) 2=(2cb+b 2+c 2−a 2)(2cb−b 2−c 2+a 2)4c^2(b^2-x^2)=(2cb)^2-(b^2+c^2-a^2)^2=(2cb+b^2+c^2-a^2)(2cb-b^2-c^2+a^2).
Donc b 2−x 2b^2-x^2 a le même signe que ((b+c) 2−a 2)(a 2−(b−c) 2)((b+c)^2-a^2)(a^2-(b-c)^2). Ce signe est positif puisque d’après les inégalités triangulaires on a :
0<a<b+c0&lt;a&lt;b+c donc a 2<(b+c) 2a^2&lt;(b+c)^2 et
b−c<a b-c&lt;a et c−b<ac-b&lt;a donc |b−c|<a|b-c|&lt;a donc (b−c) 2<a 2(b-c)^2&lt;a^2. 

fonction trisolve(a,b,c)
  local x,y;
  x:=(c^2+b^2-a^2)/(2*c);
  y:=sqrt(b^2-x^2);
  return point(0,0),point(c,0),point(x,y);
ffonction:;

onload

Remarque :
Le document ressource Python eduscol utilise une méthode de résolution approchée pour déterminer le triangle. Cela nous semble peu adapté, car la résolution exacte est accessible au niveau lycée et est beaucoup plus simple.

1
Cette méthode se généralise en dimension plus grande, on cherche la direction de plus grande pente et on se déplace dans cette direction d’un pas constant

Chapitre 10  Aide

10.1  Les fonctions usuelles avec Xcas

abs : valeur absolue ou le module de l’argument.
ceil : renvoie le plus petit entier >= à l’argument.
cos : renvoie le cosinus de l’argument.
Digits : pseudo-variable pour modifier le nombre n de chiffres significatifs (par ex Digits:=n).
evalf : évaluation numérique du premier argument (le nombre de digits peut être donné comme second argument).
floor : renvoie la partie entière de l’argument (le plus grand entier <= à l’argument.
frac : partie fractionnaire de l’argument.
max : renvoie le maximum des éléments d’une séquence ou d’une liste de réels.
min : renvoie le minimum des éléments d’une séquence ou d’une liste de réels.
+ : renvoie la concaténation de 2 chaînes ou addition terme à terme de 2 expressions ou 2 listes (opérateur infixé).
round : renvoie l’argument réel arrondi à l’entier (ou le décimal) le plus proche.
sin : renvoie le sinus de l’argument.
sign : renvoie le signe (-1,0,+1) de l’argument.
sqrt : renvoie la racine carrée de l’argument.
tan : renvoie la tangente de l’argument.

10.2  Les fonctions Xcas de calcul formel utilisées

coeff(P,var,[n] : renvoie la liste des coefficients d’un polynôme P par rapport à la variable Var ou le coefficient de degré n.
count(f,L) : applique la fonction f aux éléments de la liste L et en renvoie la somme.
degree(P,var : renvoie le degré du polynôme P par rapport à la variable var.
dim : renvoie la longueur d’une liste, d’une séquence ou d’une chaîne de caractères.
droit : renvoie le côté droit d’une équation, d’un intervalle, d’une liste ou d’une chaîne .
fsolve ou resoudre_numerique : renvoie la solution numérique d’une équation.
gauche : renvoie le côté gauche d’une équation, d’un intervalle, d’une liste ou d’une chaîne.
iquo : renvoie le quotient euclidien de 2 entiers.
iquorem : renvoie la liste du quotient et du reste euclidien de 2 entiers.
irem : renvoie le reste euclidien de 2 entiers.
normal : renvoie une simplification de l’argument.
purge(a) : enlève la valeur stockée dans la variable a.
simplify ou simplifier : renvoie une simplification de l’argument.
solve ou resoudre : renvoie la solution d’une équation.
sommets : renvoie la liste des sommets d’un polygone.
subst ou substituer : remplace dans une expression, une variable non affectée par une valeur.
sum ou somme : somme des éléments d’une liste (ou séquence).
subtype : renvoie 1 pour une séquence, 2 pour un ensemble, 10 pour un polynôme et 0 sinon ce qui définit le sous-type de l’argument.
type : renvoie nn dans [1..12] définissant le type de l’argument.

10.3  Les fonctions Xcas de géométrie utilisées

affichage : employé comme option de commandes graphiques permet de faire des dessins en couleur (par ex A:=point([1,1],affichage=rouge)).
carre : renvoie et dessine le carré direct donné par 2 points.
centre : renvoie et dessine le centre du cercle donné en argument.
cercle : renvoie et dessine le cercle donné par 1 point et 1 réel (son centre et son rayon) ou par 2 points (son diamètre) ou par son équation.
demi_droite : renvoie et dessine la demi-droite donnée par son origine et 1 point ou par son origine et son vecteur directeur [1,m].
droite : renvoie et dessine la droite donnée par 2 points ou par 1 point et son vecteur directeur [1,m].
est_aligne : renvoie 1 si les points sont alignés, 2 si les points sont confondus et 0 sinon.
est_parallele : renvoie 1 si 2 droites sont parallèles et 0 sinon.
equation : renvoie l’équation de l’argument.
inter dessine et renvoie la liste des points d’intersection de 2 objets géométriques.
inter_unique renvoie et dessine un des points d’intersection de 2 objets géométriques.
longueur : renvoie la longueur du segment défini par 2 points ou par les coordonnées de ces points. norm : renvoie la norme l2 d’un vecteur :
norm([x 1,..x n])([x_1,..x_n]) : renvoie (x 1 2+...x n 2)\sqrt(x_1^2+...x_n^2)
point : renvoie et dessine le point de coordonnées l’argument.
polygone : renvoie et dessine le polygone donné par une liste de points.
polygone_ouvert : renvoie et dessine la ligne polygonale donnée par une liste de points.
rayon :renvoie le rayon du cercle donné en argument.
segment : renvoie et dessine soit le segment donné par 2 points ou le vecteur donné par un point et son vecteur directeur. Bien voir la différence entre segment(point(cA),point(cB)) (c’est le segment (A,B)) et segment(cA,cB) qui est aussi segment(point(cA),point(cA+cB)).
sommets : renvoie la liste des sommets du polygone donné en argument et les dessine.
translation(B-A,C) : renvoie et dessine le translaté de C dans la translation de vecteur AB.
triangle : renvoie et dessine le triangle donné par 3 points.
vecteur : renvoie et dessine le vecteur donné par 2 points ou par un point et son vecteur directeur. Bien voir la différence entre vecteur(point(cA),point(cB))(c’est le vecteur (A,B)) et vecteur(cA,cB) qui est aussi vecteur(point(cA),point(cA+cB)).

10.4  Les fonctions Xcas de programmation utilisées

break : pour interrompre une boucle (tantque <cond> faire inst1; si <cond> alors inst2;break;fsi;ftantque;).
fpour
fsi
ftantque
jusque
local
pas
pour <k> de <k1> jusque <k2> faire <instructions> pas <p> fpour
quand
retourne
si <condition> alors <instructions1> sinon <instructions2> fsi
tantque <condition> faire <instructions> ftantque

10.5  Les fonctions Xcas utilisées en statistiques

alea(n1,n2) : renvoie un réel aléatoire de [n1,n2[.
alea(n) : renvoie un entier aléatoire entre 0 et n-1.
binomial : peut être employé comme option de la commande randvector.
binomial_cdf(n,p,x1,x2) : renvoie Proba(x1<=X<=x2) quand X suit la loi binomiale B(n,p).
mean : renvoie la moyenne d’une liste ou d’une liste pondérée par le deuxième argument.
median : renvoie la médiane d’une liste ou d’une liste pondérée par le deuxième argument.
plotlist : lorsque l’argument est L=[y 0,...,y n]L=[y_0,...,y_n], trace la ligne polygonale reliant les points d’abscisse kk et d’ordonnée y ky_k pour k=0..nk=0..n.
randvector : renvoie une liste de nombres aléatoires de taille nn constituée d’entiers aléatoires distribués selon la loi indiquée.
stddev : renvoie l’écart-type d’une liste ou d’une liste pondérée par le deuxième argument.

Annexe A  Premiers pas avec les interfaces de Xcas

A.1  Les différentes intefaces

Vous pouvez utiliser Giac/Xcas avec plusieurs interfaces différentes :

A vous de choisir!

A.2  Avec Xcas pour Firefox

Depuis votre navigateur (il est conseillé d’utiliser Firefox pour des performances optimales) ouvrez le lien
http://www-fourier.ujf-grenoble.fr/~parisse/xcasfr.html
Lors de la première utilisation, vous êtes invités à choisir entre la compatibilité de syntaxe Python ou la syntaxe Xcas native. Ceci peut être modifié ultérieurement en cliquant sur le bouton Config en haut à gauche.

La ligne de commande se trouve en bas de page, au-dessus se trouve une ligne de boutons assistants

Vous pouvez sauvegarder une session, vous pouvez aussi l’envoyer par mail. Le lien Clone permet de

Pour plus de détails, vous pouvez cliquer sur le bouton Tutoriel en haut à gauche en-dessous du bouton Config.

A.3  Xcas natif sur PC Windows et Linux et sur Mac.

Pour installer Xcas suivez les instructions depuis:
http://www-fourier.ujf-grenoble.fr/~parisse/install_fr.html
Vous pouvez ensuite taper des commandes dans les lignes de commande en utilisant les menus, en particulier le menu Outils qui contient les commandes mathématiques de calcul les plus utilisées, à défaut le menu Cmd qui les contient classées par thèmes, le menu Graph pour les commandes de type graphes de fonction, le menu Geo pour la géométrie, pour plus de détails voir le menu Aide, Débuter en calcul formel, Tutoriel.

Pour programmer, il est plus confortable d’ouvrir un niveau de programmes depuis le menu Prg, nouveau programme. Un assistant de création de fonction s’ouvre immédiatement (vous pouvez l’ignorer en tapant sur la touche Echap). Un niveau de programme apparait avec son propre menu et des boutons assistants Test, Boucle et Fonction pour vous aider à saisir les structures de base de l’algorithmique. Une fois votre programme saisi, vous l’interprétez en tapant sur le bouton OK (raccourci clavier F9). S’il est correct, vous pouvez tester votre fonction depuis une ligne de commande.

Vous pouvez cloner une session simple vers Xcas pour Firefox à partir du menu Fich, Clone, Online.

A.4  Conseils pour adapter des scripts Python.

De nombreuses ressources Python d’algorithmique lycée n’utilisent pas de sortie graphique et fonctionneront sans changement avec Xcas. Si ce n’est pas le cas :

Pour les scripts utilisant des commandes graphiques du module matplotlib, il faudra utiliser à la place des commandes graphiques de Xcas que vous trouverez depuis le menu Graphe ou Geo, par exemple :

A.5  Python et giacpy

Une partie des programmes en syntaxe Python de ce document peuvent s’exécuter dans un interpréteur Python, après avoir chargé le module giacpy. Il faut d’abord installer ce module sur votre PC, en suivant les instructions ici:
https://www-fourier.ujf-grenoble.fr/~parisse/giac_fr.html#python
Ensuite le chargement se fait par la ligne de commande
from giacpy import *
Les commandes de Xcas en anglais sont en général accessibles depuis l’interpréteur Python, mais il faut parfois faire des ajustements :

Annexe B  Xcas, Python et Javascript.

B.1  Le mode de compatibilité Python de Xcas

Xcas accepte une syntaxe compatible avec le langage Python. La principale différence entre la programmation en français et Python, c’est qu’il n’y a pas de fin de bloc explicite en Python, c’est l’indentation qui joue ce rôle. L’indentation consiste à ajouter au début de chaque ligne d’un même bloc le même nombre d’espaces. Il est recommandé d’indenter les programmes en mode Xcas, en mode Python c’est obligatoire. Il faut donc faire attention :

Attention, le mode de compatibilité Python de Xcas n’est pas identique à Python. Seules les constructions de base sont acceptées (pas de programmation orientée objet)  :

Certaines commandes Xcas sont compatibles avec Python, par exemple range, assert, random, etc. Notez que :

Exemple : On veut faire un programme qui teste si un nombre est parfait : un entier naturel nn est parfait si il est égal à la somme de ses diviseurs (1 compris, nn non compris).

On écrit la fonction Parfait qui a comme argument un entier n.
On définit les variables locales à la fonction :

Pour tous les entiers j entre 1 et n-1 on teste si j divise n et pour cela on cherche le reste de la division de n par j, c’est irem(n,j) ou n%j qui renvoie ce reste. Si le reste est nul, c’est que j divise n donc on ajoute j à s. Quand j a parcouru tous les entiers jusque n-1 (i.e. quand la boucle pour est terminée), on teste si s est égal à n. Si il y a égalité alors n est parfait, sinon n n’est pas parfait.

Une implémentation en syntaxe Xcas en français : 

fonction Parfait(n)
  local j,s;
  "Parfait(n) renvoie vrai si n est la somme de ses diviseurs";
  s:=0;
  pour j de 1 jusque n-1 faire
    si irem(n,j)==0 alors
      s:=s+j; // j divise n, on l'ajoute a la somme
    fsi;
  fpour;
  si s==n alors // on pourrait aussi recrire return s==n
    retourne vrai;
  sinon
    retourne faux;
  fsi;
ffonction:;



L’indentation permet de visualiser facilement la forme du programme, ici on a 3 instructions : 1 affectation, 1 boucle pour qui contient une instruction (1 test si) et 1 test si/sinon. L’indentation sert aussi à contrôler qu’on n’a pas fait de faute de syntaxe (non-fermeture d’une parenthèse par exemple). En syntaxe compatible Python, le programme Parfait précédent s’écrit : 

def Parfait(n):
    # local j,s
    '''Parfait(n) determine si l'entier n est la somme de ses diviseurs'''
    s=0
    for j in range(1,n):
        if n%j==0: 
            s=s+j # j divise n, on l'ajoute
    if s==n:
        return True
    else:
        return False



B.2  Xcas et Javascript

Javascript est le langage des navigateurs, il est donc extrêmement répandu et peut être utilisé sans installation sur PC/Mac. De ce fait, un programme écrit en javascript pourra facilement être intégré dans une petite interface utilisateur en HTML (voir l’exemple ci-dessous), et exécuté depuis n’importe quel autre navigateur, ce qui peut être assez motivant.
Du point de vue des types de variables utilisables, on dispose entre autres de nombres approchés, de chaines de caractères et de listes, il n’y a pas de type particulier pour les entiers. Les structures de controle ont une syntaxe proche du langage C, point-virgule en fin d’instruction, délimiteurs de blocs explicites {}, test en if () { ... } else { ... } et boucle en for(init;condition;incrementation){...} ou while(condition){...}, déclaration de variable par var et retour de fonction par return.
Si vous connaissez javascript, vous pouvez utiliser une syntaxe très proche dans Xcas. Exemple, syntaxe utilisable dans les deux langages pour le calcul du nn-ième nombre de Fibonacci : 

function fibo(n){
  var u,v,w,j;
  u=1; v=1;
  if (n<2) return 1;
  for (j=2;j<=n;j++){
    w=u+v; u=v; v=w; // ou en Xcas (u,v)=(v,u+v);
  }
  return v;
}


Pour avoir une interface HTML minimaliste pour cette fonction, on crée un fichier nommé disons fibo.html (que l’on consultera depuis un navigateur) contenant : 

<script>
function fibo(n){
  var u,v,w,j;
  u=1; v=1;
  if (n<2) return 1;
  for (j=2;j<=n;j++){
    w=u+v; u=v; v=w; 
  }
  return v;
}
</script>
Le 
<textarea cols="5" rows="1" id="input" 
onkeypress="if (event.keyCode!=13) return true; 
document.getElementById('output').value=fibo(eval(value)); 
return false;">5</textarea>
i&egrave;me nombre de Fibonacci est
<textarea rows="1" id="output"></textarea>

On peut utiliser les commandes de Xcas depuis Javascript, c’est exactement ce que fait l’interface Xcas pour Firefox.

B.3  Xcas et Python

Python est un langage assez populaire dans les milieux scientifiques et est facile à installer. Il possède un type spécifique pour les entiers. Sa principale différence par rapport aux autres langages est que les structures de controle n’ont pas de délimiteur explicite de fin de bloc, c’est l’indentation qui joue ce role. L’obligation d’indenter correctement a certaines vertus pédagogiques, mais pas l’absence de délimiteur explicite de fin de bloc. Ceci rend aussi l’échange de code source Python avec des applications orientées texte (copier/coller, mail, forums, traitement de texte) plus fragile1, ou même la lecture difficile si le code est affiché sur plus qu’une page. Si on modifie du code existant, par exemple pour placer une boucle dans une autre ou dans un test, devoir réindenter le code est une source d’erreur potentielle (d’où l’intérêt d’avoir quelques espaces en réserve, ce qui explique sans doute la recommandation d’utiliser 4 espaces pour indenter). De plus, la déclaration de variables locales dans une fonction est implicite, ce qui n’est pas très pédagogique. D’autre part, la syntaxe de la boucle for en Python utilise des objets plus abstraits (itérateurs) ou qui peuvent être inutiles (liste d’entiers en Python 2), elle s’éloigne de celle de la grande majorité des autres langages, y compris la traduction en langage machine. Ainsi l’exemple de Fibonacci donne 

def fibo(n):
    u=1 
    v=1
    if n<2:
        return 1
    for j in range(2,n+1):
        w=u+v  # ou directement u,v=v,u+v
        u=v 
        v=w 
    return v

B.4  Comparaison rapide

La principale différence entre les 3 langages, c’est que Xcas est un logiciel de calcul formel et permet de travailler avec des variables symboliques et des expressions. Dans Xcas, une variable globale peut ne pas avoir de valeur (son évaluation la renvoie), ce n’est pas le cas en Javascript ou en Python (l’évaluation d’une variable non initialisée renvoie une erreur). De ce fait, il ne faut pas oublier de déclarer les variables locales d’une fonction pour éviter des erreurs. En contrepartie pour réaliser des fonctions comme la dichotomie ou la recherche d’une valeur approchée d’intégrale par la méthode des rectangles, on peut passer une expression symbolique en paramètre et l’évaluer en un point, ce qui est conceptuellement plus simple que de passer une fonction en argument à une autre fonction. Avec Xcas, on peut aussi faire du calcul symbolique à l’intérieur d’une fonction, par exemple dériver une expression, calculer des valeurs exactes ou approchée, et dans ce dernier cas travailler avec un nombre arbitraire de décimales.

Des trois langages, Javascript est le plus rapide, puis Python puis Xcas.

1
Ainsi, l’exercice de spécialité du sujet de bac S 2017 centres etrangers demande aux candidats d’interpréter un algorithme écrit en syntaxe Python sans délimiteurs de blocs explicites ... et l’un des blocs est mal indenté, très probablement au cours d’un passage par un logiciel de traitement de texte

Annexe C  Les biais des langages interprétés

Les ordinateurs n’exécutent pas directement les instructions données dans un langage comme Xcas, Javascript, Python, C, Pascal, etc., ils exécutent uniquement du code machine spécifique au micro-processeur de l’ordinateur. Il y a deux façons de traduire le langage en code machine : soit une fois pour toutes lors d’une étape appelée compilation, soit au moment de l’exécution de l’instruction du langage par l’interpréteur (qui est lui-même un programme écrit dans un langage compilé), on parle alors de langage interprété (en toute rigueur, il existe une troisième possibilité un peu intermédiaire qui consiste à compiler au moment où on exécute l’instruction du langage).

Les langages interprétés sont par nature plus faciles à mettre en oeuvre (pas de compilation) et de ce fait rendent l’apprentissage plus simple. Mais la traduction au moment de l’exécution a bien entendu un impact sur le temps d’exécution, parce que les boucles sont traduites autant de fois qu’elles sont exécutées (des optimisations peuvent y remédier plus ou moins, il est d’ailleurs fort possible que la syntaxe de la boucle for en Python soit liée à des considérations d’optimisation). De plus, les langages interprétés utilisent des variables dont le type est déterminé au moment de l’exécution du code, ce qui a un impact aussi bien pour la taille occupée par la variable que pour l’exécution d’une opération qui doit commencer par déterminer le type des arguments pour agir en conséquence. Enfin, lorsqu’on utilise un langage compilé, on a accès aux types de données directement manipulables par le microprocesseur, dont la place occupée en mémoire est optimale et le temps d’exécution très rapide, par exemple on peut multiplier deux entiers dont le produit est inférieur à 2 632^{63} en moins d’un milliardième de seconde.

Bien entendu, on peut améliorer le temps d’exécution avec un langage interprété si certaines taches répétitives sont codées dans une instruction du langage, par exemple l’instruction effectuant le produit de deux matrices n’est pas programmé dans le langage interprété lui-même mais est compilé une fois pour toutes dans le code exécutable de l’interpréteur. Le programmeur qui souhaite avoir un code suffisamment rapide va donc adopter un style de programmation qui favorisera l’utilisation de commandes du langage effectuant en une seule instruction ce qui nécessiterait une ou plusieurs boucles imbriquées si on le programmait uniquement avec les instructions de base d’un langage compilé. C’est pour cette raison que les programmeurs expérimentés travaillant avec un langage interprété écrivent souvent dans un style “algébrique” avec le moins possible de structures de controle explicites et des types de données souvent assez complexes. Par exemple pour écrire un produit scalaire de deux listes en Xcas, on utilisera la commande dot, si elle n’existait pas, on pourrait écrire sum(x[j]*y[j],j,0,size(x)-1) pour éviter de faire une boucle pour, le chapitre statistiques 8 contient quelques exemples d’optimisation de ce type. Pour des commandes plus compliquées, on utilisera sans doute des commandes seq imbriquées au lieu de boucles. Mais ce style présente un risque, celui de calculer plusieurs fois la même quantité : une expression algébrique n’a pas de variables locales pour stocker de résultats intermédiaires. Il faut donc prendre garde au biais de ne pas calculer des quantités intermédiaires. Ce n’est pas le seul biais, il faut également faire attention à l’utilisation d’instructions faisant des boucles implicitement et à l’utilisation de types de données puissants qui risquent de masquer la complexité des opérations nécessaires et pourraient être remplacés par des types plus simples, par exemple utiliser un dictionnaire (ou annuaire) alors qu’un tableau ferait l’affaire. Un exemple avec la recherche de nombres premiers plus petits que nn par crible, écrit de deux manières 

def premiers1(n):
    prem=list(range(2,n+1))
    k=2
    nRacine=n**0.5
    while k<nRacine :
        prem=[p for p in prem if p<=k or p%k!=0]
        k=prem[prem.index(k)+1]   # nouveau nombre premier
    return prem

def premiers2(n):
    prem=list(range(0,n))
    k=2
    while k*k<n :
        for j in range(2*k,n,k): # on barre les multiples de k
            prem[j]=0
        k += 1
        while prem[k]==0: k += 1 # cherche le premier non barre
    res=[]  
    for k in prem:
        if k!=0: res.append(k) # on garde les 0 uniquement
    return res

premiers2 est un crible, il n’effectue aucune division et travaille sur une seule liste (plus une deuxième à la fin pour garder uniquement les nombres premiers). premiers1 a un code plus compact, mais il effectue des divisions pour tester la primalité et recrée une liste à chaque itération, et est donc significativement plus lent, par exemple pour n=n=10**6, il prend presque 10 fois plus de temps.

D’ailleurs d’un point de vue pédagogique il est toujours bon de savoir ce qu’il y a derrière une boite noire lorsque c’est accessible au niveau de l’élève ou de l’étudiant. De plus le style algébrique est certes compact, mais il est souvent plus difficile à maintenir (aussi bien à relire qu’à corriger), et il peut aussi générer une occupation mémoire inutile : par exemple en simulation, générer une grosse matrice de nombre aléatoires alors qu’une boucle agissant sur des lignes de cette matrice générées une par une et effacées après usage est incomparablement moins gourmand en mémoire.

Enfin, l’optimisation d’un code destiné à être vraiment utilisé nécessite souvent la compilation des parties critiques, et l’optimisation de ces parties critiques se fait souvent de manière différente et parfois opposée aux habitudes acquises en optimisant du code interprété. Illustrons cela plus en détails sur un exemple très utile en mathématique: le produit scalaire de deux vecteurs et le produit d’une matrice par un vecteur. Il s’agit d’une boucle pour que l’on code par 

fonction ps(u,v)
 local r,j,n
 r:=0;
 pour j de 0 jusque n-1 faire
  r:=r+u[j]*v[j];
 fpour;
 return r;
ffonction

On peut optimiser en utilisant l’instruction d’incrémentation r += u[j]*v[j]; au lieu de r:=r+u[j]*v[j];.

Traduit dans un langage compilé, ce code n’est pas loin d’être optimal, par exemple en C++ : 

double ps(const vector<double> & u,const vector<double> & v){
  size_t j,n=u.size();
  double r=0;
  for (j=0;j<n;j++){
    r += u[j]*v[j];
  }
  return r;
}

Les variables r,j,n sont stockées dans des régistres du microprocesseur. Par itération, il y a 2 additions d’entiers 64 bits (adresse de base des vecteurs et valeur de l’indice), 2 lectures en mémoire de 8 octets (u[j] et v[j]), puis une multiplication de flottants, une addition de flottant, une incrémentation d’entier 64 bits (l’indice), une comparaison entre 2 entiers 64 bits, un branchement. Ce qui prend le plus de temps c’est la lecture en mémoire des double des vecteurs u et v et le branchement/test de fin de boucle.

En langage interprété, ce code sera beaucoup plus lent, car à chaque itération, pour déterminer la valeur de u[j] et v[j], il faut évaluer la variable d’indice j (lue dans l’annuaire des variables affectées), de même pour les variables u et v, s’apercevoir que ce sont bien des tableaux, comparer j à la taille de u et de v (erreur si l’indice est trop grand), extraire la jj-ième case du tableau. Ensuite on fait le produit, ce qui nécessite de tester le type des variables, on ajoute le résultat à r ce qui nécessite à nouveau de tester le type des arguments de +=. Puis on incrémente j de 1 et on compare à n (qu’il faut évaluer). Pour diminuer les opérations de gestion de la boucle, certains langages interprétés ont une instruction de boucle spécifique pour itérer sur les éléments d’une liste, par exemple si on veut afficher les éléments d’une liste au lieu de faire 

fonction aff(u)
 local j,n
 pour j de 0 jusque n-1 faire
  afficher(u[j]);
 fpour;
ffonction;

on écrira 

fonction aff(u)
 local j;
 pour j in u faire
  afficher(j);
 fpour;
ffonction;

Cette boucle est implémentée en interne par une variable de longueur de la liste n, une autre d’indice, disons k, et j est évalué par calcul de u[k], mais les opérations de gestion de la boucle sont pré-compilées et donc plus rapides. Dans ce type de boucle, le code est plus compact et ne pose aucun problème de maintenance. Par contre, pour le produit scalaire, faire la même chose nécessite d’introduire des objets plus complexes : on peut imaginer générer la liste des paires u[j],v[j] puis itérer sur cette liste. Mais si on ne veut pas créer inutilement en mémoire une liste de paires, cette liste doit être générée de manière virtuelle (par exemple au moyen d’une paire de pointeurs sur les tableaux u et v) et il faut disposer d’une commande capable de prendre en argument une liste virtuelle. Par exemple en Python on pourrait écrire sum(i*j for i,j in zip(u,v)). Un mécanisme de création de liste virtuelle peut bien entendu avoir un intérêt intrinsèque, mais il faut avoir conscience que les objets que l’on manipule sont plus complexes que les listes (qui sont déjà des objets non triviaux), et que l’utilisation de cet objet dans l’exemple du produit scalaire pour optimiser une boucle est un artéfact de langage interprété, et qu’il sera difficile d’optimiser plus avec ce style de programmation. Il sera d’ailleurs plus facile d’optimiser en langage compilé sans utiliser ce type d’objets.

Ainsi, il est possible d’optimiser la boucle du produit scalaire, on peut pour nn grand regrouper plusieurs itérations, et gagner du temps sur les parties test/branchement, par exemple 2 par 2 

double ps(const vector<double> & u,const vector<double> & v){
  size_t j,n=u.size();
  double r=0;
  n--;
  for (j=0;j<n;j+=2){
    r += u[j]*v[j]+u[j+1]*v[j+1];
  }
  n++;
  for (;j<n;j++){
    r += u[j]*v[j];
  }
  return r;
}

Et si on effectue le produit d’une matrice MM par un vecteur vv, on peut optimiser le temps d’exécution en mutualisant la lecture des coefficients de vv, on fait plusieurs produits scalaires avec vv simultanément. 

double ps(const vector<double> & u1,
  const vector<double> & u2,const vector<double> & v){
  size_t j,n=u1.size();
  double r1=0,r2=0;
  n--;
  for (j=0;j<n;j+=2){
    double vj=v[j],vj1=v[j+1];
    r1 += u1[j]*vj+u1[j+1]*vj1;
    r2 += u2[j]*vj+u2[j+1]*vj1;
  }
  n++;
  for (;j<n;j++){
    r1 += u1[j]*v[j];
    r2 += u1[j]*v[j];
  }
  return r;
}

Ici en faisant 2 produits scalaires simultanément, on fait 6 lectures en mémoire au lieu de 8 pour 2 itérations.

Il nous parait donc essentiel pour un scientifique d’apprendre aussi un langage pas trop éloigné de la machine, ou au moins d’être capable de coder avec des objets de base.

  
""