Arithmétique, algorithmique et nombres complexes avec CaRMetal

vendredi 27 mai 2011
par  Alain BUSSER

CaRMetal est un logiciel de géométrie dynamique. Pas un logiciel de calcul. Pourtant, sans faire exprès, il a été doté de capacité à écrire des algorithmes sur

  1. des grands nombres entiers ;
  2. des nombres décimaux à beaucoup de décimales ;
  3. des nombres complexes.

Comme ce n’était pas prévu dans CaRMetal, ces fonctionnalités ne sont pas documentées. Cet article a donc pour but de montrer comment faire tout ça.

L’idée directrice de cet article est que depuis la console JavaScript de CaRMetal, on peut accéder à toute la puissance du langage Java. Comme on n’a rien sans rien, il est nécessaire de charger dans JavaScript les bibiothèques Java dont on a besoin, ce qui se fait avec

importPackage(NomDuPaquet);

Mais c’est le seul effort supplémentaire à fournir ! Après cela on peut jouer du synthé, accéder à toutes les méthodes cachées de CaRMetal, faire communiquer celui-ci avec d’autres logiciels, etc.

Bref, pour en savoir plus que ce qui est montré dans cet article, il faut aller consulter la référence du langage Java...

Précision sur le vocabulaire : Dans cet article, le mot CaRScript désigne un programme en JavaScript destiné à être exécuté sous CaRMetal, alors que le mot CaRAScript désigne la variante où le CaRSCript est lancé automatiquement lors du mouvement d’un point sur la figure.

Bézout

Mais avant d’aller charger des bibiothèques spécialisées de Java, CaRMetal possède 4 fonctions arithmétiques, qu’on peut utiliser dans des expressions de la figure (coordonnées de points, couleurs des objets, ...) :

- La fonction div accepte deux nombres (non nécessairement entiers) et retourne le quotient euclidien du premier par le deuxième. Malgré la présentation dans le menu, il faut séparer le dividende du diviseur par un point-virgule et non par une virgule.
- La fonction mod accepte deux nombres (non nécessairement entiers) et retourne le reste euclidien du premier par le deuxième. En utilisant 2 \pi comme deuxième nombre, on a la valeur principale d’un angle en radians. La fonction n’est donc pas purement arithmétique.
- La fonction lcm accepte deux nombres et renvoie leur ppcm.
- La fonction gcd accepte deux nombres et renvoie leur pgcd. Par exemple, en créant une courbe implicite et en y entrant l’équation

gcd(x;y)-2

on a la ligne de niveau 2 du pgcd :

qui renseigne sur l’algorithme utilisé...


Cela permet de faire des CaRAScripts consacrés à l’arithmétique.

Premier exemple : Point à mouvement limité

On peut aussi utiliser la récursivité permise par CaRMetal pour limiter le mouvement d’un point P à l’intérieur d’un carré de côté 6, tout simplement en assujettissant ses coordonnées à être réduites modulo 3 (le cadenas évite même d’avoir à taper la formule deux fois) :

Le point P ne peut suivre la souris que si celle-ci reste elle-même dans le carré, sinon il effectue un saut très visible : On a là une manière graphique et dynamique d’introduire le reste euclidien. On peut ensuite représenter graphiquement la fonction mod(x ;3) et commenter l’effet produit sur les réels négatifs...

Deuxième Exemple : Affichage du pgcd des coordonnées

Un moyen simple d’entrer à la souris deux entiers (pour calculer leur pgcd) c’est de prendre les coordonnées (entières) d’un point [1]. Sous CaRMetal, on peut

  1. commencer par créer un point A ;
  2. mettre son incrément à 1 (ainsi ses coordonnées seront entières)
  3. lui donner comme alias Le pgcd de %x(A)% et %y(A)% est %gcd(x(A);y(A))%

Pour aller plus loin,

on peut aussi rajouter un texte appelé « Aff » [2], et le modifier en live par un CaRAScript lui-même piloté par le mouvement de A, et dont le contenu pourraît être

Ceci dit, la fonction gcd utilisée ici n’est pas celle de CaRMetal mais celle de l’objet BigInteger de Java qui sera décrite dans le prochain onglet.

Troisième exemple : Bézout dynamique

Toujours avec un point A de coordonnées entières, on peut mettre l’algorithme d’Euclide étendu dans un CaRAScript acceptant les coordonnées (entières donc) de A, pour afficher dynamiquement dans un objet texte (ci-dessous appelé prems), les nombres u et v réalisant l’égalité de Bézout. Les lignes de code suivantes sont du pur JavaScript, seules les lignes 1 et 2 communiquent avec CaRMetal (en récupérant les coordonnées du point appelant), ainsi que la ligne 19, qui crée un affichage LaTeX donnant la solution de l’équation diophantienne donnée par l’algorithme d’Euclide étendu :

Une fois le CaRAScript recopié, il faut bien entendu l’associer au point A pour que les mouvements de celui-ci mettent à jour, presque instantanément, l’affichage en LaTeX.

Cet exemple a un prolongement géométrique :

On peut afficher les (autres) points de la droite dont l’équation cartésienne est donnée dans prems. Une méthode lente mais simple consiste à créer préalablement des points de coordonnées entières, codées dans leur nom (par exemple PX3Y2 pour le point de coordonnées 3 et 2) puis les cacher tous. Ensuite, on applique SetHide(false) à chacun des points P tels que ux(P)+vy(P)=d...

Mersenne

Sur un ordinateur 32 bits, chaque entier est codé sur 32 bits signés, donc son écriture décimale comporte au maximum 10 chiffres. Le langage Java possède un objet entier long dont la taille est double du précédent, donc inapte par exemple à gérer les plus grands nombres de Mersenne premiers connus... Pour y remédier, Java possède un objet BigInteger dans la classe math [3], et CaRMetal peut accéder à ses méthodes pour peu qu’on y charge la classe math (c’est l’équivalent du célèbre from math import * de Python). Tous les CaRScripts de cet onglet et du suivant commenceront donc par

importPackage(java.math)

Ceci permettra alors de manipuler ces fameux « gros entiers ». Mais avant tout, qu’est-ce que c’est qu’un gros entier ? C’est un entier dont le nombre de chiffres n’est pas limité. Ainsi, même 1 et 2 sont des gros entiers, pour peu qu’on les considère comme tels.

Pour entrer un gros entier, il faut l’introduire comme une chaîne de caractères et le convertir. Par exemple, pour que 1 soit un gros entier, on utilise

BigInteger("1")

Si l’entier à convertir en gros entier est caché dans une variable x, on peut convertir celle-ci en chaîne de caractères avec x.toString(), mais cette conversion est faite automatiquement par JavaScript. Comme on doit souvent utiliser 1 comme un gros entier, on peut aussi faire

BigInteger.ONE

Les quatre opérations sont infixées mais leur nom, écrit en toutes lettres, doit être précédé d’un point. Par exemple, pour vérifier que 2+1=3, on peut entrer

importPackage(java.math);
a=BigInteger(2);
b=BigInteger.ONE;
Println(a.add(b));

De même,

- la différence entre a et b s’écrit a.subtract(b),
- le produit de a par b s’écrit a.mulltiply(b) ;
- le quotient euclidien de a par b s’écrit a.divide(b) ;
- le reste dans le même division s’écrit a.mod(b) ;
- la puissance b-ième de a s’écrit a.pow(b) ;
- la même, mais modulo n, s’écrit a.modPow(b,n) ;
- s’il existe, l’inverse de a modulo n est donné par a.modInverse(n) ;

Par exemple, on voudrait savoir combien font 127^{1023} modulo 2^{32} :

Presque instantanément, on apprend que

127^{1023} \equiv 828489599 \: [4294967296]

Les nombres ci-dessus (127 et 1023) ont été choisis premiers de Mersenne. Il résulte du petit théorème de Fermat que pour qu’un nombre de Mersenne soit premier, l’exposant doit lui-même être premier. Mais la réciproque n’est pas vraie. Le test de Lucas-Lehmer permet assez vite de vérifier si un petit nombre de Mersenne est premier, mais avec un grand nombre c’est une autre histoire ! Ceci dit, avec des tests analogues, Java sait tester la primalité d’un nombre arbitrairement grand, avec isProbablePrime (suivi d’un entier qui représente le nombre d’essais ; théoriquement cet entier devrait être supérieur à l’entier à tester pour être certain que l’entier à tester est premier ; concrètement la probabilité qu’il soit composé est négligeable en fournissant environ 10 comme nombre de tests à isProbablePrime).

Le script ci-dessous commence par vérifier que 2^{127}-1 est premier (avec l’affichage de true), puis que 1023^{31} ne l’est pas, puis calcule et affiche l’inverse de 1023^{31} modulo 2^{127}-1 (un nombre de 39 chiffres tout de même) :

L’inverse est 144241301817751220596031080948389737388.

Pour en savoir plus, voir la référence sur les gros entiers.

Fermat

Les nombres de Fermat ont des propriétés intéressantes et relativement peu connues. En particulier, on n’en connaît que 5 qui soient premiers (les 5 plus petits d’entre eux). Et deux nombres de Fermat sont toujours premiers entre eux, les gros entiers de Java permettent de le verifier sur des exemples, tout simplement en calculant leur pgcd. Par exemple, F_7=2^{128}+1 et F_8=2^{256}+1 sont premiers entre eux :

Et puisqu’ils sont premiers entre eux, il existe deux entiers u et v tels que u \times F_7 + v \times F_8=1. Pour les trouver, on peut réécrire l’algorithme d’Euclide étendu pour les gros entiers :

On a instantanément

u=-170141183460469231731687303715884105728

v=57896044618658097711785492504343953926464851149359812787997104700240680714241

Ne sont-ce pas là des gros entiers ?


Puisque les 5 premiers nombres de Fermat sont premiers, Pierre de Fermat a conjecturé que tous les nombres de Fermat le sont. Un siècle plus tard, Leonhard Euler prouvait (avec l’algorithme exposé ci-dessous) que le 6e nombre de Fermat est divisible par 641, donc composé. Aujourd’hui on n’a pas trouvé de nombre de Fermat premier au-delà des 5 plus petits d’entre eux, et les tests de primalité sont difficiles à appliquer parce que les nombres de Fermat sont grands et il faut beaucoup de place en mémoire pour les stocker.

Mais le test de primalité isProbablePrime des gros entiers répond très vite pour des nombres de Fermat comme les précédents, qui sont gros sans être trop gros :

La réponse (false) vient très vite, ce qui veut dire que le 7e nombre de Fermat possède des diviseurs premiers. Comment les trouver en un temps raisonnable ? La théorie d’Euler fournit un algorithme assez rapide :

Si le nombre de Fermat F_n=2^{2^n}+1 possède un diviseur, celui-ci est nécessairement congru à 1 modulo 2^{n+2}.

Par exemple, le célèbre diviseur 641 de F_5 est bien congru à 1 modulo 128.

Il suffit alors de chercher exclusivement des diviseurs du nombre de Fermat qui vérifient la condition ci-dessus ; ces diviseurs potentiels sont en progression arithmétique de raison assez grande, et en effectuant les divisions, l’algorithme suivant converge relativement vite :

La fenêtre de sortie, affichée par-dessus le script, donne la décomposition en facteurs premiers du 7e nombre de Fermat.

Évidemment un logiciel de calcul formel donne lui aussi, et assez rapidement, la réponse (ici giac-Xcas, sous TeXMacs) :

L’approche algorithmique est différente, ne serait-ce que du point de vue didactique (la joie de la création...).

Multiprécision

L’import de la bibliothèque math de Java ne donne pas seulement accès aux gros entiers, mais également aux gros décimaux (BigDecimal). Le mode de fonctionnement est le même que dans les onglets précédents :

Pour créer un nombre en multiprécision, l’écrire comme une chaîne de caractères, et fournir celle-ci à BigDecimal : Par exemple, pour convertir 1,2 en gros décimal, on peut simplement faire ceci :

importPackage(java.math);
a=BigDecimal(1.2);
Println(a);

Problème : On a ceci :

1.1999999999999999555910790149937383830547332763671875

Ce qui explique certains problèmes avec les fractions...

Pour éviter cela, il faut surtout éviter de passer par la valeur binaire de 1,2 et donc mettre 1,2 entre guillemets :

importPackage(java.math);
a=BigDecimal("1.2");
Println(a);

Une alternative est de calculer le quotient comme un quotient de gros décimaux :

importPackage(java.math);
a=BigDecimal(BigDecimal(6).divide(BigDecimal(5)));
Println(a);

Le nombre décimal écrit en chaîne de caractères peut aussi être donné sous forme d’écriture scientifique, comme 12E-1. On peut aussi fournir à BigDecimal un nombre entier, voire un gros entier. Et BigDecimal.ONE est le nombre 1 vu comme un gros décimal.

- Pour avoir l’opposé d’un gros décimal a, on fait a.negate() ;
- Pour additionner deux gros décimaux a et b , on fait a.add(b) ;
- Pour soustraire deux gros décimaux a et b , on fait a.subtract(b) ;
- Pour multiplier deux gros décimaux a et b , on fait a.multiply(b) ;
- La puissance de a s’obtient par a.pow(n) ;

Pour la division, c’est plus compliqué parce qu’il faut indiquer le nombre de chiffres à garder dans le quotient, ainsi que la manière d’arrondir le dernier chiffre (un entier parmi BigDecimal.ROUND_DOWN, BigDecimal.ROUND_UP, et 5 variantes visibles dans la référence ).

Par exemple, pour afficher 100 décimales du quotient de 22 par 7, arrondies par excès, on peut faire

Le reste euclidien d’un gros décimal a par un gros décimal b s’obtient par a.remainder(b).


Racines carrées

C’est maintenant que ça commence à devenir franchement algorithmique : Les gros décimaux n’ont pas de fonctions trigonométriques, exponentielles, racine carrée... Donc si on a besoin de connaître la racine carrée de 2 à 1000 décimales, on doit d’abord trouver un moyen de calculer la racine carrée ! Pour sa célébrité et sa rapidité de convergence, on va prendre la méthode de Héron. Et là déjà, se pose un problème inattendu : Jusqu’où doit-on aller pour être sûr d’avoir 1000 décimales correctes ? En tablant sur un doublement du nombre de décimales à chaque itération, on peut obtenir une borne supérieure au nombre nécessaire d’itérations, mais on peut aussi essayer expérimentalement, en affichant la différence entre les deux bornes données par l’algorithme de Heron, et en adaptant le nombre de boucles jusqu’à ce que la différence affichée soit inférieure à la millième décimale ; on trouve alors 11 pas :

Ci-dessus on a encadré \sqrt{2} entre deux suites a_n et b_n telles que a_0=1, b_n=\frac{2}{a_n} et a_{n+1}=\frac{a_n+b_n}{2}. On s’est arrêté lorsque a_n-b_n est suffisamment petit, en relançant l’algorithme jusqu’à ce que l’affichage final soit assez petit : 11 itérations ont donc été nécessaires.

Maintenant, on a un moyen de calculer la racine carrée de 2 à 1000 décimales par défaut, simplement en affichant la valeur finale de a [4] :

Maintenant qu’on a 1000 chiffres, il peut être intéressant de faire une étude statistique dessus. Pour cela un moyen rapide avec JavaScript est l’utilisation d’une expression régulière, fabriquée avec la recette suivante :

  1. on convertit le chiffre dont on veut compter les occurences en caractère (on le met entre guillemets) ;
  2. on « compile » le caractère « g » qui va rendre la recherche globale (on ne cherche pas le premier « 7 », on cherche tous les « 7 ») ;
  3. on lance la RegExp, telle un chien de chasse, à la recherche des occurences du chiffre ;
  4. On obtient alors une longue liste de chiffres tous identiques (que des « 7 » par exemple) ; on calcule alors la longueur de cette liste pour avoir l’effectif correspondant.

Le script obtenu est le suivant :

Et le tableau des effectifs obtenu :

chiffres 0 1 2 3 4 5 6 7 8 9
effectifs 108 99 109 82 100 104 90 104 113 92

La répartition est suffisamment uniforme pour donner l’impression que la racine carrée de 2 est un nombre normal en base 10.

Exponentielle de l’unité

Le nombre e ne fait pas un bon titre avec sa seule lettre (Georges Perec n’apprécierait guère), alors autant le décrire comme l’image de 1 (qui est ici un gros décimal) par la fonction exponentielle. Pour calculer rapidement e à 1000 décimales, on peut utiliser sa série entière, tronquée au rang ... Tiens mais au fait, au rang combien ? Jusqu’où doit-on aller pour que l’inverse d’une factorielle soit plus petite que la millième décimale ? Jusqu’où doit-on aller pour que la factorielle d’un nombre soit supérieure à 10^{1000} ?

On peut répondre à la question avec la formule de Stirling, ou tout simplement par tâtonnements :

Bingo ! Il faut donc boucler 450 fois (ou additionner 450 termes) ; bien que ce ne soit pas très prudent, on va tronquer systématiquement chaque terme, ce qui risque de fausser les 3 dernières décimales affichées.

Pour calculer les factorielles, on va les stocker dans une variable p (comme « produit ») qui sera initialisée à 1, mais vu comme un gros décimal. et on va additionner à la variable s (comme « somme ») les inverses des valeurs successives de p, obtenues en divisant le gros décimal 1 par p :


Pour en savoir plus sur les gros décimaux, voir la référence ; la comparaison avec la version Python est également intéressante.

Complexes

Cependant, les concepteurs de Java ont oublié les nombres complexes. La raison profonde de ce fait est la propriété archimédienne de l’ensemble des réels, ou plus exactement le fait que celui-ci soit ordonné. En effet en Java les nombres (qu’ils soient entiers, réels, gros entiers ou gros décimaux) sont des cas particuliers de tous les objets qu’on peut ordonner, comme les dates et les chaînes de caractères :

Et bien entendu les nombres complexes ne sont pas comparables entre eux : Pour un langage objet comme Java, les complexes ne sont pas des nombres ! Et donc ils ne sont pas implémentés.

Mais pour gérer les intersections de coniques, le concepteur de CaRMetal avait besoin des complexes. Alors, très logiquement, il les a créés ! Donc, pour pouvoir effectuer des calculs sur des complexes (ou leur appliquer des algorithmes), on ne va pas importer un paquet du langage Java, mais directement un paquet du code source de CaRMetal, avec

importPackage(Packages.rene.zirkel.structures)

Une fois que c’est fait, il suffit d’entrer z=Complex(3,2) pour avoir le nombre complexe 3+2i dans le CaRScript. Cependant cet objet est encore un peu abstrait, et ne s’affiche pas comme on le voudrait :

En gros, on apprend que z est un complexe et on voit l’adresse mémoire de z (elle change à chaque exécution). Pour afficher le contenu de z, on peut demander séparément ses parties réelle et imaginaire en faisant suivre le nom z d’un point puis de real() pour la partie réelle ou img() pour la partie imaginaire [5] :

Comme on aura souvent à afficher des nombres complexes dans la suite, il est plus commode de créer un algorithme d’affichage plutôt que recommencer ce qui est fait ci-dessus ; ce qui en JavaScript se fait avec une « fonction » appelée cartesian (ce choix sera expliqué ci-dessous) :

Pourquoi cartesian ? Parce qu’un nombre complexe peut aussi être déterminé par sa forme trigonométrique, ci-dessous nommée polar [6] :

On voit ci-dessus (avec l’affichage produit) que la forme cartésienne de 4+3i est plus facile à lire que sa forme trigonométrique, et que les angles sont donnés en radians à 16 décimales.

De toute manière, les noms cartesian et polar sont des choix personnels réalisés en JavaScript, qu’on peut donc facilement changer. De même, si on n’aime pas la syntaxe z.img(), on peut la changer en écrivant quelque chose comme

function imaginaire(z){
   return z.img();
}

Opérations

L’objet complexe de CaRMetal ne possède pas d’opérations unaires comme l’opposé, l’inverse ou le conjugué. Les créer comme des fonctions JavaScript est laissé en (excellent) exercice. On écrit

  1. a.plus(b) pour additionner deux complexes a et b ;
  2. a.minus(b) pour les soustraire ;
  3. a.mult(b) pour les multiplier ;
  4. a.divide(b) pour les diviser ;
  5. a.sqrt() pour avoir l’une des trois racines carrées de a
  6. et a.sqrt3() pour avoir l’une de ses trois racines cubiques.

Exploration numérique des complexes

On constate qu’il n’a pas de puissances entières des nombres complexes dans CaRMetal. Pour élever un complexe au carré, il faut donc le multiplier par lui-même. Ainsi, pour vérifier que si j=-\frac{1}{2}+i \frac{\sqrt{3}}{2}, on a j^2=\bar{j}, on multiplie j par j :

On reconnaît le classique problème d’approximation binaire de certains nombres décimaux. Il faut donc comprendre que 1E-17 c’est peut-être zéro, et qu’un nombre comme 2+1E-17i est peut-être réel... Voir ci-dessous le problème de la conversion en réel.

Mais on peut persister et signer, en regardant la valeur de 1+j+j^2 :

On voit que la somme est réelle, on voit moins qu’elle est nulle, c’est un peu une question d’habitude [7].

Ensuite, il peut être intéressant de voir comment CaRMetal réagit à la division d’un complexe par 0. Pour cela, on définit 0 comme égal à 0+0i pour être sûr que c’est un complexe (en fait la partie imaginaire est inutile, CaRMetal convertit automatiquement x réel en x+0i). La division du complexe 1 par le complexe 0 donne ceci :

Ce n’est pas que le quotient n’existe pas, c’est qu’il est complexe mais avec des parties réelle et imaginaire inexistantes.

Une variante de l’exemple précédent consiste à calculer le carré de i, après avoir défini celui-ci :

Résultat parfait, à part que le résultat n’est pas reconnu comme réel (on verra ci-dessous comment gérer la conversion d’un complexe en réel).

Didactiquement, il peut être intéressant de comparer sur des exemples les nombres

Complex(a,b);
Complex.plus(Complex.mult(un,a),Complex.mult(i,b));

On peut aussi multiplier un complexe par un réel, par exemple calculer son double :

Certains complexes sont réels

Pour l’instant, CaRMetal ne sait pas qu’un complexe de partie imaginaire nulle est réel. Pour explorer numériquement le fait que la somme et le produit d’un complexe par son conjugué sont réels, on a donc besoin d’un test de réalité, et d’une conversion en réel. Comme on l’a vu précédemment, un complexe est réel si sa partie imaginaire est suffisamment petite, réclamer qu’elle soit sctrictement nulle est trop demander à JavaScript qui n’aime pas trop les nombres décimaux. Par ailleurs, si un nombre complexe est réel, il est facile de le convertir en nombre réel (il suffit de le transformer en sa partie réelle) mais que faire si l’utilisateur essaye de convertir en réel un nombre qui ne l’est pas ? Ici on choisit de renvoyer un discret message d’erreur plutôt que de tout bloquer, en disant que la conversion a abouti mais que son résultat n’est pas un nombre réel :

Exploration d’une transformation

Pour finir, un CaRAScript permet de construire un nombre complexe dynamique, en choisissant comme parties réelle et imaginaire de celui-ci, les coordonnées du point qui appelle le CaRAScript, ci-dessous notées X(« $name$ ») et Y(« $name$ »). On va s’en servir pour explorer dynamiquement la transformation z \mapsto \frac{1}{\bar{z}}. Cette activité peut être motivée purement algébriquement par la constatation que l’inverse et le conjugué d’un complexe non nul ont tous les deux le même argument, et donc que Arg\left(\frac{1}{\bar{z}}\right)=Arg(z).

Dans le script ci-dessous, on note z le nombre complexe, et Z son image par la transformation. Un point également nommé Z doit être présent dans la figure avant de lancer le script, et il est assujetti par le script à rester l’image du point initial :

Pour que ce script fonctionne, il faut, par le gestionnaire de scripts, l’associer aux mouvements d’un point autre que Z (voir le TP 51 de l’onglet suivant pour voir comment on fait ça). Alors lors des mouvements de ce point, on voit

  • que les deux points restent alignés avec l’origine (remarque sur les arguments ci-dessus) ;
  • que la transformation a une infinité de points fixes ;
  • que ceux-ci sont disposés sur une courbe remarquable ;
  • que la transfomation est involutive...

Cerise sur le gâteau : CaRMetal possède un outil « inversion » avec lequel il est bon de comparer la transformation explorée...

TP Complexes

Résolution des équations du second degré

Au programme de Terminale S, ne figurent que les équations à coefficients réels, mais il sera plus simple de les convertir automatiquement en complexes, et de tout faire dans le champ complexe.

Tout d’abord, on peut vérifier que vu comme un complexe, -1 possède une racine carrée :

En estimant que la partie réelle est nulle aux erreurs d’approximation près, on réalise que la racine carrée en question est i.

Il possède aussi une racine cubique

En fait, 1 aussi possède trois racines cubiques, mais CaRMetal choisit la racine réelle (1 lui-même) et non j qu’on a vu dans l’onglet précédent.

L’algorithme de résolution des équations du second degré est plus simple dans sa version complexe que dans sa version réelle parce qu’il n’y a plus besoin de test. Ci-dessous, d1 est l’une des racines du discriminant et d2 l’autre racine. Comme CaRMetal n’a pas d’opposé des nombres complexes, on multiplie d1 par -1 pour avoir d2. x1 et x2 sont alors les deux solutions de l’équation, et la fonction trinome retourne un tableau contenant leurs écritures cartésiennes :

On voit que les solutions de l’équation z^2+2z+5=0 sont -1+2i et -1-2i, mais comme précédemment il faut un peu d’entraînement pour reconnaître la partie réelle des deux solutions !


On aborde maintenant des sujets de l’épreuve expérimentale du bac S 2009 :

Sujet 051

Celui-là est un très bon prétexte à un CaRAScript : Sur une figure CaRMetal comprenant le point O(0,0), le cercle de centre O et de rayon 1, un point M sur le cercle, et deux points N et Q libres dans le plan, on peut utiliser l’algorithme suivant :

  1. récupérer l’affixe z de M ;
  2. calculer son carré z2 et son cube z3 ;
  3. les additionner (on remarque que la somme de plus que deux termes est parfaitement gérée par CaRMetal) ;
  4. déplacer les points d’affixes respectifs z2 et q (la somme).

En JavaScript ça donne ceci :

Pour finir, il reste à ouvrir le gestionnaire de scripts pour associer à ce script, le point M :

Après cela, tout mouvement de M va faire bouger N et Q, permettant ainsi de conjecturer l’alignement considéré.

Sujet 111

Puisqu’on itère une fonction f, un bon début est d’implémenter celle-ci en JavaScript :

Voici le résultat

n a
1 1.5+(3.5)i
2 -0.5+(3)i
3 -1.25+(1.75)i
4 -1+(0.75)i
5 -0.375+(0.375)i
6 0.125+(0.5)i
7 0.3125+(0.8125)i
8 0.25+(1.0625)i
9 0.09375+(1.15625)i
10 -0.03125+(1.125)i
11 -0.078125+(1.046875)i
12 -0.0625+(0.984375)i
13 -0.0234375+(0.9609375)i
14 0.0078125+(0.96875)i
15 0.01953125+(0.98828125)i
16 0.015625+(1.00390625)i
17 0.005859375+(1.009765625)i
18 -0.001953125+(1.0078125)i
19 -0.0048828125+(1.0029296875)i
20 -0.00390625+(0.9990234375)i
21 -0.00146484375+(0.99755859375)i
22 0.00048828125+(0.998046875)i
23 0.001220703125+(0.999267578125)i
24 0.0009765625+(1.000244140625)i
25 0.0003662109375+(1.0006103515625)i
26 -0.0001220703125+(1.00048828125)i
27 -0.00030517578125+(1.00018310546875)i
28 -0.000244140625+(0.99993896484375)i
29 -0.000091552734375+(0.999847412109375)i
30 0.000030517578125+(0.9998779296875)i

Pour connaître les distances

Au lieu de regarder les complexes a, on va plutôt regarder la différence entre a et j, ou plutôt on va regarder le module de celle-ci. Avec la notation des langages objet, le « ou plutôt » se note par un point, ce qui donne la nouvelle ligne 17 ci-dessous :

Le résultat affiché montre une suite convergente :

n d
1 2.9154759474226504
2 2.0615528128088303
3 1.4577379737113252
4 1.0307764064044151
5 0.7288689868556626
6 0.5153882032022076
7 0.3644344934278313
8 0.2576941016011038
9 0.18221724671391565
10 0.1288470508005519
11 0.09110862335695782
12 0.06442352540027595
13 0.04555431167847891
14 0.03221176270013797
15 0.022777155839239456
16 0.016105881350068987
17 0.011388577919619728
18 0.008052940675034493
19 0.005694288959809864
20 0.004026470337517247
21 0.002847144479904932
22 0.0020132351687586233
23 0.001423572239952466
24 0.0010066175843793117
25 0.000711786119976233
26 0.0005033087921896558
27 0.0003558930599881165
28 0.0002516543960948279
29 0.00017794652999405825
30 0.00012582719804741396

Pour connaître la nature de la suite, on peut, au lieu d’afficher le terme courant de la suite, le diviser par le précédent, ce qui se fait en affectant une variable ad hoc avec le terme précédent :

On voit alors très bien sur les 15 premières décimales que le rapport est tout le temps le même... Mais pas sur la 16e décimale, qui est alternativement un 5 ou un 6.

Sujet 112

Bien que prévu pour un logiciel de calcul formel, ce TP se prête bien à un traitement algorithmique avec CaRMetal, à condition d’utiliser un tableau de complexes :

La suite du TP est laissée en (intéressant) exercice, vu qu’il est presque aussi aisé d’additionner les termes d’un tableau lorsque ceux-ci sont complexes que lorsqu’ils sont réels (par contre, trier les éléments du tableau est beaucoup plus difficile dans ce cas !).


[1On a alors une sorte de curseur bidimensionnel discret.

[2« Aff » pour « affichage », parce que GeoPlan bien...

[3en minuscule parce que ce n’est pas l’objet Math de JavaScript mais l’objet math de Java

[4Ceci dit il est plus prudent de calculer à 1010 décimales et ne garder que les 1000 premières décimales.

[5Les parenthèses vides sont révélatrices du fait que dans CaRMetal, la partie imaginaire est une méthode, contrairement à ce qui avait été fait en JavaScript dès 2010, où c’était une propriété de l’objet. En fait les nombres complexes de CaRMetal n’ont que des méthodes et aucune propriété. C’est un choix cohérent avec leur présence dans les structures du logiciel.

[6Un bon polar doit avoir un bon argument pour ménager le suspense !

[7le même entraînement peut s’avérer utile en calcul matriciel numérique, où une matrice diagonale peut avoir des coefficients très petits en-dehors de la diagonale.


Commentaires

Annonces

Prochains rendez-vous de l’IREM

Séminaire EDIM-IREM

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


Brèves

Décès de Roger Mohr

mardi 27 juin

On sait bien que Nicolas Bourbaki n’était pas le nom d’une personne mais le pseudonyme d’un groupe. L’équivalent en informatique théorique est Claude Livercy, auteur de la théorie des programmes. Roger Mohr était un des membres de Claude Livercy.

À travers les labyrinthes : algorithmes et fourmis

dimanche 1er septembre 2013

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

Rencontres Mondiales du Logiciel Libre à St-Joseph

mardi 20 août 2013

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

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

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

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

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

dimanche 19 août 2012

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

Ouverture du SILO

mardi 1er novembre 2011

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

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

Sur le Web : Site du SILO

Introduction à la science informatique

lundi 12 septembre 2011

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

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

Sur le Web : CRDP de Paris

Deux publications sur l’algorithmique

samedi 17 octobre 2009

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

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

Une carte mentale pour l’algorithmique

jeudi 10 septembre 2009

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

Un catalogue libre d’algorithmes pour le lycée

dimanche 30 août 2009

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

L’algorithmique à l’IREM de Lille

vendredi 26 juin 2009

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

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

Statistiques

Dernière mise à jour

lundi 24 juillet 2017

Publication

759 Articles
Aucun album photo
133 Brèves
11 Sites Web
132 Auteurs

Visites

50 aujourd'hui
427 hier
2064430 depuis le début
7 visiteurs actuellement connectés