[FAQ] fr.sci.maths - partie 3/3

medtib@alussinan.org (Mehdi Tibouchi)


Archive-Name: fr/maths/maths-faq-3

Last modified: 2006-11-11
Version 2.12


          #####################################################
          #                                                   #
          #           FAQ fr.sci.maths (partie 3/3)           #
          #                                                   #
          #####################################################

fr.sci.maths est un groupe de discussion destiné à recueillir les
discussions en français concernant les mathématiques.

Ce document rassemble les questions qui ont été fréquemment posées dans
ce forum.

Remarque sur la notation : le signe de multiplication utilisé ici est
l'astérisque *, comme souvent en informatique.

La version texte de ce document a été divisée en trois parties, afin de
faciliter sa difusion sur les forums francophones.

On trouvera, dans cette partie, les chapitres V à VII inclus.

Pour les chapitres I et II, se referer au document intitulé :
             "[FAQ] fr.sci.maths - partie 1/3".
Pour les chapitre III et IV, se referer au document intitulé :
             "[FAQ] fr.sci.maths - partie 2/3".


Table des matières :

I   Contradictions.
     1. Est-ce que 0,9999... = 1 ?
     2. J'ai réussi à montrer que 2=1.
     3. Zéro puissance zéro égal un (0^0 = 1).

II  Démonstrations.
     1. Le petit théorème de Fermat.
     2. ab et a+b premiers entre eux.
     3. Irrationalité de la racine carrée de 2.
     4. Irrationalité de la racine d'un nombre premier.
     5. Irrationalité de e.
     6. Transcendance de e.
     7. Somme des puissances des premiers entiers.
     8. Les nombres et les polynômes de Bernoulli.
     9. Par combien de zéros le nombre 1998! se termine-t-il ?
    10. Expression par radicaux des racines d'un polynôme de degré n.

-+- Début de la deuxième partie -+-

III Géométrie.
     1. Problème de la chèvre.
     2. Problème (dit) de Napoléon.

IV  Énigmes.
     1. Pièces et balance, traduit par Vincent Lefèvre. 
     2. Les âges du capitaine.
     3. Quel est le nombre qui continue cette suite : 2, 12, 1112,...
     4. Probabilité que 2 personnes soient nées le même jour.
     5. Somme et produit de deux entiers.
     6. Les deux échelles.
     7. La cuve de vin.

-+- Début de la troisième partie -+-

V   Questions fondamentales.
     1. Les nombres premiers.
     2. Pi.
     3. Le grand théorème de Fermat.
     4. La conjecture de Syracuse.
     5. Les cardinaux des ensembles infinis - Partie I.
     6. Les cardinaux des ensembles infinis - Partie II. 
     7. Qu'est-ce que le nombre e ?

VI  Mathématiques et Ordinateur.
     1. Logiciels de mathématiques.
     2. L'algorithme de CORDIC sur les calculatrices.

VII Conclusion.
     1. Références.
     2. Remerciements.
     
========================================================================

Changements intervenus depuis la version précédente :
  - Mises à jour ou suppression des liens morts.
  - Rééquilibrage des trois parties pour tenir dans la limite de 64ko.
  - Révision du paragraphe I.3.
  - Suppression du paragraphe VI.1 de Frédéric Bastok (double-emploi
    avec le document posté chaque quinzaine).
  - Réécriture du paragraphe VI.2 (maintenant VI.1), qui était dépassé
    et étrangement structuré.
  - Autres détails cosmétiques.

Les changements sont précédés du caractère : |

========================================================================


V Questions fondamentales.
  ========================

1. Les nombres premiers.
   ---------------------

  Définition :
   - Un nombre premier est un entier possédant exactement  2  diviseurs.
     (ces deux diviseurs sont donc 1 et lui-même).

  A noter que la définition de nombre premier exclut 1. Admettre 1 comme
  nombre premier rendrait  faux  l'important  "Théorème  fondamental  de
  l'arithmétique" qui dit qu'il existe une unique  manière  d'écrire  un
  nombre entier supérieur à 1 comme produit de  nombres  premiers  (sans
  prendre en compte l'ordre de la multiplication).

 a) En existe-t-il une infinité ?

    Oui.  En voici une démonstration par l'absurde.  Noter  qu'après  le
    Théorème de Pythagore, c'est sûrement le résultat mathématique  pour
    lequel on connaît le plus de démonstrations différentes.

    Supposons qu'il n'en  existe  qu'un  nombre  fini  n,  qui  seraient
    p_1, p_2,..., p_n. Le produit p_1*...*p_n est divisible  par  chacun
    de ces premiers p_1,..., p_n. Cela signifie que p_1*...*p_n+1  n'est
    divisible par  aucun  d'entre  eux.  Donc  le  plus  petit  diviseur
    (excepté 1) de ce nombre, qui est forcément un nombre premier, n'est
    ni p_1, ni p_2,..., ni p_n.  Notre  liste  ne  peut  donc  pas  être
    complète, il doit donc exister une  infinité  de  nombres  premiers.

 b) Quel est le plus grand que l'on connaisse ?

|    Actuellement (attention, les records tombent vite!),  le plus grand
|    nombre premier connu est 2^32582657 - 1 qui a été découvert en 2006
|    dans le cadre du projet GIMPS.  Il a 9808358 chiffres décimaux.  Ce
|    nombre est le quarante-quatrième nombre de Mersenne connu.
|    (Source : http://www.utm.edu/research/primes/largest.html)


 c) Polynôme donnant l'ensemble des nombre premiers.

    Il existe un  polynôme à coefficients entiers à 26 variables tel que
    l'ensemble des nombres premiers coïncide avec l'ensemble des valeurs
    **positives** prises par P(a,b,c,...x,y,z) lorsque les 26  variables
    a,b,c,...,x,y,z parcourent N.

    Ce polynôme s'écrit:
P(a,b,...,y,z) = (k+2) * {1 - [wz+h+j-q]^2 - [(gk+2g+k+1)(h+j)+h-z]^2
              - [2n+p+q+z-e]^2 - [16((k+1)^3)(k+2)((n+1)^2) + 1 - f^2]^2
              - [(e^3)(e+2)((a+1)^2) +1 -o^2]^2 - [(a^2-1)(y^2)+1-x^2]^2
              - [16(r^2)(y^4)(a^2-1) +1 -u^2]^2 - [((a+(u^2)
                 (u^2-a))^2-1)(n+4dy)^2+1-(x+cu)^2]^2 - [n+l+v-y]^2
              - [(a^2-1)l^2+1-m^2]^2 - [ai+k+1-l-i]^2
              - [p+l(a-n-1)+b(2an+2a-n^2-2n-2)-m]^2 -[q+y(a-p-1)
              + s(2ap+2a-p^2- 2p-2)-x]^2-[z+pl(a-p)+t(2ap-p^2-1)-pm]^2}

    Rendre P(a,...,z) positif revient à annuler simultanément chacun des
    crochets dans le   " long "  facteur  {1 - [...]^2 - ... - [...]^2}.
    Ce facteur se réduit alors à 1,  tandis  que  les  conditions  ainsi
    imposées à  k  font  que  le  facteur  " court ",  à  savoir  (k+2),
    est premier.

    On  peut  lire  dans  "  l'Abrégé  d'Histoire  des  Mathématiques  "
    de Jean Dieudonné (pages 232 et suivantes) l'existence d'un polynôme
    à 21 variables ayant  la même forme  et  les mêmes propriétés que le
    polynôme déjà cité.

    Pour ceux qui voudraient s'initier  à  ce  genre  de  mathématiques,
    On peut lire:
  --  l'article "Diophantine Decision Problems",
      de la regrettée Julia Robinson, pages 76 à 116
      du livre "Studies in Number Theory", volume 6 des MAA Studies
      in Mathematics, édité (au sens scientifique du terme)
      par W.J. LeVeque.
  --  "Little book of big primes" de Paulo Ribenboim.
  --  "book of prime numbers records"

  Annexe:  Dans  le  même  ordre  d'idée  il  existe  un  polynôme  dont
     les  valeurs  positives  donnent   les   nombres   de   Fibonacci :
     f(x,y) = 2 x(y^4) + (x^2)(y^3) - 2(x^3)(y^2) - (y^5) - y(x^4) + 2 y


 d) Nombres de Mersenne et nombres premiers.

    Au sujet du projet GIMPS (Great Internet Mersenne Prime Search),  ce
    projet consiste à chercher le plus  grand  nombre  premier  sous  la
    forme d'un nombre de Mersenne (Les  nombres  de  Mersenne  sont  les
    nombres premiers du type  2^p - 1  où p est lui-même premier).

    Le  38ième nombre de Mersenne a  été  trouvé  le 1er  juin  1999 par
    l'équipe de Nayan Hajratwala,  George Woltman et Scott Kurowski.  il
    s'agit  de  2^6972593 - 1.  Ce nombre  compte  2,098,960  décimales.
    Trouverez vous le 39ième nombre de Mersenne ?
    Vous pouvez vous aussi participer  à  ce  grand  projet  en  faisant
    tourner  sur  votre  machine  (quelle que  soit  la  plateforme)  le
    programme qui a été développé pour ce projet. C'est un programme que
    vous pouvez faire tourner en tâche de fond et qui utilise les cycles
    CPU non utilisés (donc cela ne ralentira pas votre ordinateur).
    C'est un projet de recherche à plusieurs qui utilise  les  résultats
    fournis par les 4200  participants  pour  déterminer  quels  nombres
    restent à tester,... C'est un projet qui se fait  en  collaboration,
    celui qui a la chance de  trouver  un  nombre  de  Mersenne  inscrit
    définitivement son nom  dans l'histoire des maths... (et gagne aussi
    10 000 $ je crois, mais j'espère que  vous  ne  ferez  pas  ça  pour
    l'argent).

    Plus de renseignements sur: http://www.mersenne.org/prime.htm
    ou en français (miroir officiel) sur:
    http://www.mersenne.org/french_prime.htm



2. Pi.
   ---

 a) Algorithmes de calculs de décimales.
    C'est Archimede (en 225 avant JC) qui calcula le premier algorithme
    sur les décimales de Pi.
|   On trouve sur Internet de nombreux recueils de formules et méthodes
|   permettant de calculer des décimales. Par exemple :
|   http://www.peripheria.net/calcul/
|   ou encore le site très complet de Boris Gourévitch :
|   http://www.pi314.net/
    
 b) l'algorithme de Bailey, Borwein et Plouffe ?
    C'est pour calculer pi en base 16 (il y a une version en base 10,
    mais beaucoup plus lente). L'intérêt, c'est qu'on peut calculer un
    chiffre sans devoir déterminer tous les précédents.
|   Voir par exemple les pages web précédentes, ou encore :
|   http://fr.wikipedia.org/wiki/Formule_BBP
|   http://www.joyofpi.com

    J.P. Delahaye a écrit un très  beau  livre  sur  le sujet:
    "Le Fascinant nombre Pi" aux éditions Belin - Pour la science.



3. Le grand théorème de Fermat.
   ----------------------------

 a) Enoncé.
    Le  " grand "  ou  " dernier "  théorème   de   Fermat   dit   ceci:
    alors qu'il  existe  des  carrés  qui  sont  somme  de  deux  carrés
    (par exemple 5² = 3² + 4², 13² = 12² + 5²), il n'existe  aucun  cube
    (non   nul)   qui   soit   somme   de   deux   cubes   (non   nuls).
    De même, il n'existe aucune puissance quatrième qui  soit  somme  de
    deux puissances quatrièmes (non nulles), etc.
    En général, pour n > 2, il n'existe aucun triplet (x, y, z)
    d'entiers non nuls, tels que x^n + y^n = z^n.

    C'est à dire, traduit en langage mathématique :
    pour n > 2 l'équation  x^n + y^n = z^n  n'a pas de  solution entière
    non triviale.

 b) Histoire liée au théorème.

    Contrairement au petit théorème, il s'agit d'un résultat extrêmement
    difficile, dont Fermat n'a pas publié de démonstration, et qu'il n'a
    probablement  pas  démontré.  Fermat   n'a   même   jamais   affirmé
    publiquement l'avoir démontré. Il écrivit dans une marge du livre II
    des Oeuvres de Diophante:

    " j'ai découvert une démonstration merveilleuse, mais je  n'ai  pas
      la place de la mettre dans la marge ".

    Le livre et cette annotation ont été publiés après sa mort, par  son
    fils.

    En dépit de la simplicité de son énoncé, ce théorème  est  tellement
    difficile à prouver que les  plus  grands  mathématiciens  s'y  sont
    cassé les dents pendant 358 ans  exactement,  d'après  le  livre  de
    Simon Singh. On notera cependant, que :

 -> Euler (1707-1783) le démontre pour n = 3 et ses multiples
 -> Legendre (1752-1833) pour n = 5
 -> Kummer (1810-1893) pour tout n tel que 2<n<100

|   En 1995, une démonstration est enfin publiée:
    celle d'Andew Wiles (1953-).

 c) Références.
    Voici une page bien documentée sur le sujet (Warning in english!)
    http://www.best.com/~cgd/home/flt/flt01.htm

    Simon Singh a écrit un très beau livre :
    _Le dernier Théorème de Fermat_ aux éditions JC Lattès,
    à partir d'un documentaire qu'il devait réaliser sur le sujet
    pour la BBC. C'est principalement un roman.

    Dans un genre plus mathématiques, on pourra consulter avec profit le 
    livre de Yves Hellegouarch :
    _Invitation aux mathématiques de Fermat-Wiles_ aux éditions  Masson,
    très bien fait, mais demandant un niveau  licence  ou  maîtrise   de
    mathématiques, pour en comprendre toutes les finesses.



4. La conjecture de Syracuse.
   --------------------------

a) Présentation de la conjecture.
   Le problème de la conjecture de Syracuse,   également connue sous les
   noms de problème   de Collatz,   Kakutani,  ou Ulam,   se présente de
   manière très simple.
   On  se  donne  une entier naturel n plus grand que 1.  S'il est pair,
   on le divise par deux, s'il est impair, on le multiplie par 3  et  on
   lui ajoute 1 (ce qui revient à lui appliquer la fonction x |-> 3x+1).
   On   >conjecture<  que l'on finit toujours par trouver la valeur 1 au
   fil des calculs,   valeur à partir de laquelle on restera bloqué dans
   le cycle 1-4-2-1-...

   Cependant,  le fait que l'on retrouve toujours 1 n'a pas été démontré
   et  même  si on est  presque  sûr que cela est vrai,  quel  que  soit
   l'entier n choisi au départ,  il  n'est  pas exclu  qu'il  existe  un
   entier n ne vérifiant pas cette propriété, d'où le nom de :
   >conjecture< de Syracuse.

   Depuis  plusieurs  dizaines  d'années,  ce  problème  est  activement
   étudié par les mathématiciens, mais n'a pas encore été résolu.
   Les recherches ont  cependant bien avancé,  comme nous allons le voir
   plus loin.

b) Une métaphore éclairante.
   Comment souvent, les mathématiciens,  en travaillant sur ce problème,
   ont senti que certaines idées  étaient récurrentes etont introduit un
   vocabulaire adapté pour décrire les phénomènes étudiées.
   Imaginons que l'on vérifie la propriété pour n=15. On obtient :
   46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1.

   On appelle cette suite finie d'entiers le VOL, ou la  TRAJECTOIRE  de
   15.  Il  faut  imaginer  une  représentation  de  cette  suite sur un
   graphique,  l'axe  des  abscisses  figurant l'indice de chaque entier
   dans la suite,  l'axe des ordonnées indiquant l'entier correspondant.

   On appelle ETAPE, un nombre de cette suite finie.  Ici,  par exemple,
   80 est une étape du vol de 15.
   Si la conjecture est vraie,  on  remarque  que  la  suite atteint une
   étape maximale,  appelé  ALTITUDE  MAXIMALE du vol.  Ici,  l'altitude
   maximale était 160.

   On définit également la  DUREE de chaque vol comme le nombre d'étapes
   à franchir avant d'arriver pour la première fois au chiffre 1,  et la
   durée de  VOL  EN  ALTITUDE   comme la durée entre le moment où le
   vol commence, et celui où il repasse sous sa valeur initiale.

c) Des avancées intéressantes.
   A partir de là, il est plus facile de comprendre les dernières
   avancées dans la résolution du problème. Il a été ainsi démontré que
   chacune des propositions suivantes était équivalente à l'énoncé de
   la conjecture de Syracuse elle-même :

   (1) Tout vol a une durée finie
   C'est en gros l'énoncé de la conjecture en elle-même.

   (2) Tout vol est de durée en altitude finie
   En effet, si ceci est vrai, alors on conclut sur notre problème par
   récurrence. Pour n=2 on finit par retomber sous 2, c'est à dire à 1.
   Supposons que n et tous les entiers plus petits quelui vérifient la
   conjecture. Démontrons que c'est alors le cas de n+1 :
   Le vol n+1 a une durée en altitude finie, donc, au cours des
   calculs, on arrive à n, ou à un entier inférieur, que l'on note i.
   Mais i vérifie la conjecture, donc il aboutit au cycle 4-2-1. Ainsi
   n+1 aboutit-il aussi à ce cycle. Réciproquement, si la conjecture
   est vraie, la propriété (2) est bien entendue vraie.

   (3) Tout vol a un nombre fini d'étapes paires (resp. impaires)
   On considère le vol n. Après un certain nombre d'étapes, on atteint
   un dernier nombre pair. On le divise par deux, et on obtient un
   impair. Mais, si on applique x -> 3x+1 à cet impair, on obtiendra un
   pair, ce qui contredit le fait qu'on ait dépassé les dernier pair, 
   sauf si le nombre impair que l'on vient de trouver est 1.
   Alors on s'arrête dans les calculs, et n vérifie la conjecture, qui
   de ce fait est vraie.

   (4) Tout vol a un nombre fini d'étapes paires (resp. impaires) en
       altitude
   Démonstration analogue.

   Les mathématiciens désespèrent quant au fait de démontrer 
   directement la conjecture elle-même, et pensent qu'il est moins
   difficile de montrer que l'une de ces propriétés, équivalentes au
   problème, est vraie.

   On sait par ailleurs montrer que la propriété est vraie pour un très
   grand nombre d'entiers. On considère par exemple n = 4*k + 1.
   En effectuant les calculs, on trouve qu'il devient 12*k+4, 6*k+2,
   3*k+1, ce dernier entier étant plus petit que n.
   Pour n = 4*k, on descend sous n dès la première étape du calcul. De
   même que pour 4k + 2.
   Il suffirait donc de pouvoir montrer que 4k+3 a lui aussi une durée
   de vol en altitude finie pour conclure que la conjecture est vraie !
   On peut affiner ce type de démonstration. En travaillant avec les
   entiers du type 65536*k + i (avec i compris entre 0 et 65535), tous
   les cas aboutissent sauf 1729 cas, donc il ne reste que 2,6% des
   nombres à étudier.

   Des développements plus récents ont montré que pour n assez grand,
   il existait une constante alpha telle que au moins n^alpha des
   entiers inférieurs à n possèdent la propriété de Syracuse.
   En 1995, J. Lagarias et D. Applegate démontrèrent ce résultat pour
   la constante alpha=0,81. Mais leurs calculs furent menés avec des
   ordinateurs et sont invérifiables à la main.

d) Les records établis
   Les records enregistrés au fur et à mesure des recherches ont été
   soigneusement consignés.

   C'est à  T. Oliveira e Silva que l'on doit les records les plus
   récents et les plus significatifs. Les records suivants proviennent
   de sa page web :

   Le plus grand nombre testé est : 77 * 2^50 = 86694292826882048.
   La conjecture a été vérifiée par deux fois avec des ordinateurs
   jusqu'à n = 2^51 = 2251799813685248.
   Le record de l'altitude maximale est tenu par le vol 
   82450591202377887, qui atteint l'entier :
   875612750096198197075499421245450.

   D'autres records, datant de 1998 et sans doute améliorés depuis :
   Celui de vol de durée record en vol est celui du vol
   100759293214567, de durée 1820 (c'est assez faible, on aurait pu
   croire que des entiers résisteraient plus).
   Enfin celui de durée en altitude record est le vol 70665924117439,
   dont la durée en altitude est de 1177 étapes.

e) Données heuristiques et indécidabilité du problème
   Si l'on étudie la façon dont les entiers évoluent en terme de parité
   au cours d'un calcul de Syracuse, on peut avoir une idée de son 
   temps de vol.. Ainsi, si l'on obtient souvent des nombres pairs,
   ils vont être divisés par deux, et on arrivera plus rapidement à 1
   (en admettant qu'on arrive toujours à 1).
   En tenant compte du fait qu'un nombre impair donne un nombre pair et
   que ce dernier va être divisé par deux ensuite, et qu'il y a dans
   l'ensemble des entiers naturels autant de pairs que d'impairs, on
   estime, au moyen d'un calcul probabiliste, qu'un entier donné est en
   moyenne multiplié par 3/4 lorsqu'on effectue une étape du calcul.
   Ceci tend à confirmer la conjecture. Expérimentalement, ce résultat
   de 3/4 est très bien confirmé, et le modèle statistique semble
   performant.

   Cependant, certains mathématiciens sont arrivés à se poser la
   question de l'indécidabilité du problème. Ils ont proposé quelques
   extensions du problème : autoriser les entiers négatifs, ou
   remplacer 3x+1 quand x est impair par qx+1 avec q un entier impair
   donné. Pour certaines valeurs de q>3, la conjecture n'est pas vraie.

   Mais c'est J. Conway qui a semé le doute. Plutôt que de ce demander
   si un entier donné, au cours du calcul, était pair ou impair, c'est
   à dire avait 0 ou 1 pour reste par la division euclidienne par 2,
   il s'intéresse au reste par la division euclidienne par un entier p
   et propose alors p formules à employer pour effectuer les calculs
   selon ce que ce reste soit 0, 1, 2, .., ou p-1. Il a montré que si
   alors on étendait la conjecture de Syracuse, on arrivait à un
   problème indécidable.


   Finalement, on a vu que beaucoup de résultats tendent à nous faire
   penser qu'il est >presque< impossible que la conjecture soit fausse.
   Cependant, il est arrivé dans l'histoire que les mathématiciens
   aient une telle intuition très forte en faveur d'une conjecture et
   qu'elle soit en fait fausse. Les résultats de J. Conway montrant que
   des problèmes très similaires sont indécidables incitent donc à la
   prudence !

f) Bibliographie
   "La conjecture de Syracuse", par Jean-Paul Delahaye 
      in: _Pour La Science_ N°247 de mai 1998.

   Et sur le web :
|  "The 3x+1 problem and its generalizations" par Jeff Lagarias :
|     http://www.cecm.sfu.ca/organics/papers/lagarias/



5. Les cardinaux des ensembles infinis - Partie I.
   -----------------------------------------------

 a) Avertissement

Le sujet est vaste  et  peut  intéresser  des  gens  de  niveaux  divers
(à partir du lycée et bien au-delà).  C'est  pourquoi  cet  article  est
découpé en 2 parties.  La  première  s'adresse  au  niveau  pré-bac,  la
seconde est accessible à partir du DEUG, environ.
Dans la première  partie,  l'accent  est  mis  sur  la  "vulgarisation",
parfois au détriment de  la  rigueur :  pour  éviter  des  complications
techniques, certaines démonstrations sont  "un  peu  fausses",  tout  en
donnant l'idée principale de  la  méthode.  Chaque  fois  que  c'est  le
cas, c'est signalé, et on peut se reporter  à  la  seconde  partie  pour
trouver une démonstration (à priori) rigoureuse.
La seconde partie complète la première, avec des outils  plus  abstraits
et  plus  puissants.  Elle  s'efforce  à  la  rigueur,  mais  elle  peut
comporter des erreurs ou imprécisions.


Merci  enfin  à  David  Madore  (David.Madore@ens.fr),  spécialiste   du
sujet, d'avoir corrigé et complété une première mouture de cet  article.
Merci également à tous les lecteurs de fr.sci.maths  qui  m'ont  indiqué
des corrections diverses.


Rappel : N : ensemble des entiers naturels          = {0,1,2,3,...}
         Z : ensemble des entiers relatifs (signés) = {...,-1,0,1,...}
         Q : ensemble des nombres rationnels (fractions)
         R : ensemble des nombres réels
         C : ensemble des nombres complexes
L'étoile signifie que l'ensemble est privé de 0 (N*={1,2,3,...}).

Voici d'abord les résultats essentiels, qui seront suivis  par  quelques
explications :
_ N, Z, Q  ont autant d'éléments
_ R, C     ont autant d'éléments
_ Les 3 premiers ont moins d'éléments que les 2 derniers.

La notion de cardinal étend  la  notion  de  nombre  aux  infinités,  de
façon  à  ce  que  l'on   puisse   comparer   les   ensembles   infinis.
Voici comment.

 b) Cardinal d'un ensemble fini

Pour un ensemble fini, le  cardinal  est  une  notion  intuitive,  c'est
simplement le nombre  d'éléments  de  l'ensemble.  Il  appartient  à  N.
Ex : Card {1,2,3} = 3 = Card {6,15,28}

(*) Opérations sur les cardinaux (finis) :
    --------------------------------------
(1) Si A et B sont deux ensembles finis *disjoints* alors
    Card (A Û B) = Card A + Card B
    où Û désigne l'union disjointe.

Ex : A = {1,2,3}     Card A = 3
     B = {8,9}       Card B = 2
     A Û B = {1,2,3,8,9}  Card(A Û B) = 5 = 3+2.

(2) Si A et B sont deux ensembles finis, alors
    Card (A × B) = (Card A) . (Card B)
    où A × B désigne le produit cartésien des ensembles A et B.

Ex : A = {1,2,3}  Card A = 3
     B = {a,b}    Card B = 2
     A × B = { (1,a), (1,b), (2,a), (2,b), (3,a), (3,b) }
     Card (A × B) = 6 = 3x2.

(3) Si A est un ensemble fini on note P(A) l'ensemble des parties de  A,
    c'est a dire l'ensemble des sous-ensembles de A.
    alors Card P(A) = 2^(Card A)
En effet : pour constituer une partie B de A, il y a un choix à
           faire pour chaque élément de A : soit on le met dans B,
           soit on ne l'y met pas (2 possibilités).
           S'il y a n éléments dans A, cela donne 2^n possibilités
           pour B, soit 2^n parties différentes.

Ex : A = {1,2,3}  Card A = 3
     P(A) = { Ø, {1}, {2}, {3}, {1,2}, {2,3}, {1,3}, {1,2,3} }
     Card P(A) = 8 = 2^3

Ce sont ces propriétés (1), (2), (3) qu'on va  vouloir  généraliser  aux
ensembles infinis.

                               -----

Pour un ensemble infini,  l'intuition  ne  s'applique  plus  :  il  faut
recourir à des définitions formelles.  C'est  Cantor  qui,  le  premier,
a fourni  un  système  cohérent  permettant  de  traiter  les  ensembles
infinis.

 c) Définition rigoureuse d'un ensemble infini :

Une bijection f entre 2 ensembles E et F est une  application  qui  fait
correspondre  à  chaque   élément  de  E  un   unique   élément   de   F
et inversement.

S'il existe une bijection entre  E  et  F,  on  dit  que  E  et  F  sont
équipotents et on note : E ~ F.

Un ensemble est  dit  fini  s'il  est  en  bijection  avec  un  ensemble
A_n = {1, 2, 3, ..., n} avec n un entier naturel (et A_0 = Ø).
Alors Card(E) = n, et on retrouve la notion intuitive.

Un ensemble E qui ne peut pas être mis en bijection avec un tel ensemble
A_n est dit infini.
Ex : N est un ensemble infini.

 d) Cardinal d'un ensemble infini :

On étend la notion  de  cardinal  aux  ensembles  infinis  de  la  façon
suivante (schématiquement ; pour  plus  de  rigueur  voir  partie  II) :

1. Si 2 ensembles sont équipotents (en bijection),  on  dit  qu'ils  ont
le même cardinal.

2. On dit que Card E <= Card F si E a même cardinal qu'une partie de  F.
En particulier, si un ensemble infini E  est  inclus  dans  un  ensemble
(infini) F alors Card E <= Card F (inégalité large).

Ex. (règle 1) :
Card Z = Card N car il existe (au moins) une bijection de N
dans Z, qu'on peut expliciter :
g : n --> n/2      si n est pair
    n --> -(n+1)/2 si n est impair
ce qui donne 0 -->  0
             1 --> -1
             2 -->  1
             3 --> -2
               ...
Ex. (règle 2) :  Card N <= Card Z <= Card Q <= Card R <= Card C.

 e) Quelques résultats sur les ensembles dénombrables

On a vu Card N = Card Z. Établissons quelques autres résultats :

(*) Card N = Card (N^2)
On peut en effet compter les éléments de N^2 = { (a,b) | a,b dans N }.
Une bijection possible de N^2 dans N est le "comptage en diagonale" :
(0,0) --> 0
(1,0) --> 1
(0,1) --> 2
(2,0) --> 3
(1,1) --> 4
(0,2) --> 5
 ...
(on compte les points de N^2 selon les diagonales bas-droite -> 
haut gauche, en s'éloignant de l'origine).
On peut même expliciter la bijection :
 (p,q) --> (p+q).(p+q+1)/2 + q

De même, on a Card (Z^2) = Card Z.

(*) Card (Z) = Card Q

Essentiellement, une fraction  p/q  est  un  couple  d'entiers  relatifs
(p,q).  Cette  égalité  n'est  donc  pas  particulièrement   surprenante
quand on a admis Card (Z^2) = Card Z.

Formellement,  la  démonstration  est  un  peu  technique  :  elle   est
donc donnée dans la deuxième partie.

On a donc : Card N = Card Z = Card Q.

Ce cardinal est noté aleph_0.
(aleph est la première lettre de l'alphabet hébreu).

Tous les ensembles infinis qui ont le même  cardinal  que  N  sont  dits

dénombrables.

Au sens large,  "dénombrable"  signifie  aussi  "fini  ou  dénombrable".
Enfin,  un  ensemble  qui  n'est  ni  fini  ni  dénombrable  est  dit...
indénombrable.

 f) Quelques résultats sur les ensembles indénombrables

Plaçons nous maintenant dans les réels.

(*) Card [0,1] = Card [0,2] = Card [a,b] = ...
Il est facile de trouver une bijection de [0,1] dans [0,2] :
k : x --> 2x par exemple.
De même, on peut toujours trouver  une  bijection  entre  2  intervalles
de R, ouverts ou fermés.
Tous les intervalles de R ont donc le même cardinal.

(*) Card (a,b) = Card R
(a,b) désigne l'intervalle, sans se préoccuper  de  l'inclusion  ou  non
des bornes.
La fonction tangente, par exemple, fournit une bijection
de ]-pi/2,pi/2[ dans R.
En appliquant ce qui précède, tout intervalle de R a le même
cardinal que R.

(*) Card ([0,1[^2) = Card [0,1[
En effet on peut  expliciter  une  bijection  de  [0,1[^2  dans  [0,1[ :
Soit  (a,b)  dans  [0,1[^2.  Écrivons  leur   développement   décimal  :
a = 0, a1 a2 a3 a4 ...
b = 0, b1 b2 b3 b4 ...
formons alors c = 0, a1 b1 a2 b2 a3 b3 a4 b4 ...
N'est-il pas alors clair que la fonction   l : (a,b) --> c
est une bijection de [0,1[^2 dans [0,1[ ?

[en fait, pas tout a fait :  il  y  a  une  lacune,  expliquée  dans  la
seconde partie, mais ça ne change pas le résultat]

Grâce à ce qui précède on déduit que :
Card R = Card [0,1[ = Card ([0,1]^2) = Card R^2.
On peut démontrer la même  chose  avec  n'importe  quel  exposant  à  la
place de 2.

(*) Card C = Card R

En  effet,  les  fonctions  partie  réelle  et  partie  imaginaire  d'un
complexe  fournissent  une   bijection   évidente   de   C   dans   R^2.
Avec ce qui précède on a donc Card C = Card R^2 = Card R.

 g) Rapport dénombrable/indénombrable

On va maintenant voir que R n'est pas dénombrable.

Pour simplifier,  on  va  montrer  que  [0,1[  n'est  pas  dénombrable ;
ce qui implique, bien sûr, que R ne l'est pas.
Supposons le contraire : on  peut  alors  énumérer  [0,1[,  c'est-à-dire
qu'il existe une suite (u_n), n dans N,  qui  contient  tous  les  réels
de [0,1[.

Écrivons le développement décimal  (par  exemple)  des  premiers  termes
de (u_n) en notant u_n,i le i-ème chiffre  après  la  virgule  de  u_n :
u_1 = 0, u_1,1 u_1,2 u_1,3 u_1,4 ...
u_2 = 0, u_2,1 u_2,2 u_2,3 u_2,4 ...
...
u_n = 0, u_n,1 u_n,2 u_n,3 u_n,4 ...
...

On forme maintenant le nombre v s'écrivant :
v = 0, u_1,1 u_2,2 u_3,3 u_4,4 ... u_i,i ...
(on  prend  les  chiffres  de   la   diagonale   principale   ci-dessus)

On forme enfin le nombre  w  en  remplaçant  chaque  chiffre  de  v  par
son prédécesseur (et 0 par 8) :
w = 0, w_1 w_2 w_3 w_4 ...
avec :
w_i = 8         si u_i,i = 0
w_i = u_i,i - 1 sinon

Alors le nombre w, qui est bien défini, n'est  pas  dans  la  liste  des
valeurs parcourues par (u_n). En effet :
w_1 (le premier  chiffre  de  w  après  la  virgule)  est  différent  de
u_1,1 (le premier chiffre de u_1  après  la  virgule)  donc  w  <>  u_1.
w_2 <> u_2,2  donc  w <> u_2
...
w_n <> u_n,n  donc  w <> u_n pour tout n.

On a donc construit  un  réel  de  [0,1[  qui  n'est  pas  dans  (u_n) :
contradiction avec l'hypothèse.
Une  telle  suite  u_n  parcourant  tous  les  réels  de  [0,1[ n'existe
donc pas, donc [0,1[ est indénombrable.
La technique qui nous a permis de le montrer est  classique,  et  connue
sous le nom de "Procédé diagonal de Cantor".

 h) Conclusion :

Tout ceci nous permet d'écrire :
Card N = Card Z = Card Q  <  Card R = Card C.

Pour d'autres développements, et des  justifications  plus  rigoureuses,
voir la partie II.



6. Les cardinaux des ensembles infinis - Partie II.
   ------------------------------------------------

 a) Autre définition rigoureuse d'un ensemble infini :

Une  définition  équivalente  (moyennant  l'axiome  du  choix)  à  celle
de la première partie  est :
Un ensemble E est dit infini si on  peut  trouver  une  bijection  entre
lui-même et une de ses parties (strictes) F, ie :
F inclus dans E, F <> E, F ~ E.

Ex : N est en bijection avec N*, par la fonction f : n --> n+1
     ainsi, N est infini

 b) Cardinal d'un ensemble infini :

La  façon  parfaitement  rigoureuse  de  définir  le  cardinal  pour  un
ensemble  infini  s'appuie  sur  le   théorème   de   Cantor-Bernstein :

Thm : Soient A et B deux ensembles (finis ou infinis).
      Si A s'injecte dans B et B s'injecte dans A, alors
      A et B sont équipotents.
(la démonstration est facile dans le cas fini,  un  peu  moins  dans  le
cas général).

Ce théorème justifie les écritures :
Card(A) = Card(B) si A et B sont équipotents
Card(A) <= Card(B) si A s'injecte dans B
En  effet,  on  peut   alors   appliquer   la   règle   d'antisymétrie :
si n <= m et m <= n alors n = m.
Écrire  cette  règle  avec  les  cardinaux  infinis   est   une   simple
ré-écriture du théorème de Cantor-Bernstein.

D'autre  part,  on  a  l'équivalence  (moyennant  l'axiome  du  choix) :

- A s'injecte dans B
- B se surjecte sur A
et en notant Card(B) >= Card(A) si B se surjecte sur A,
on reste cohérent en manipulant les cardinaux.

Pour la culture (merci à David Madore) :
Si A et B sont  deux  ensembles  quelconques,  alors  soit  A  s'injecte
dans  B  (ie  Card(A)   <=   Card(B)),   soit   B   s'injecte   dans   A
                     (ie Card(B) <= Card(A)).
En d'autres termes  :  les  cardinaux  forment  une  classe  "totalement
ordonnée".

 c) Quelques précisions sur les ensembles dénombrables

(*) Card (Z^2) = Card Q
On a une injection évidente f : Q --> Z^2 :
                            f(p/q) = (p,q)

avec p,q premiers entre eux et q>0
[on  peut  rajouter  f(0)=(0,1)  pour   être   parfaitement   rigoureux]
Évidemment, ce n'est pas une bijection  :  (4,6)  par  exemple  n'a  pas
d'antécédent, puisque f(4/6) = (2,3).
On a donc Card Q <= Card(Z^2).

D'autre part, on a vu dans la première partie :  Card  (Z^2)  =  Card Z.
Or    Z    s'injecte   trivialement   dans   Q   :   Card Z  <=  Card Q.
De ces  deux  inégalités  on  déduit  Card (Z^2) = Card Q,  alors  qu'il
serait fastidieux d'exhiber une bijection  explicite  entre  Q  et  Z^2.

 d) Quelques précisions sur les ensembles indénombrables

(*) Card ([0,1[^2) = Card [0,1[
En fait, l'application l donnée dans la  partie  I  n'est  pas  vraiment
une bijection, mais seulement une injection. Cela est dû  à  l'existence
de deux  écritures  décimales  distinctes  pour  les  décimaux  :  l'une
avec un nombre fini de chiffre (ex  :  1,23),  l'autre  avec  un  nombre
infini  de  chiffres  (ex  :  1,2299999...)  [Voir  la  FAQ 0,999...=1].
En  conséquence,  le  nombre   0,50595959...   par   exemple   n'a   pas
d'antécédent puisque:
l(0,555... , 0,099...) = l(0,555.. , 0,1) = 0,51505050...
Cependant, ça suffit : l nous fournit  une  injection  de  [0,1[^2  dans
[0,1[,  et  l'injection  réciproque  est  triviale.  En  appliquant   le
théorème de Cantor-Bernstein on peut  donc  conclure  en  toute  rigueur
que Card([0,1[) = Card([0,1[^2).

La  généralisation  à  Card R  =  Card (R^2),  se  fait  toujours  comme
indiqué dans la première partie.

 e) Rapport dénombrable/indénombrable

Voici une démonstration plus indirecte du fait que R est  indénombrable,
mais  qui  a  l'avantage  de  préciser   le   rapport   entre   les   2,
à savoir R ~ P(N), l'ensemble des parties de N.

(*) Soit E un ensemble. P(E) n'est jamais équipotent à E.
En voici une (jolie) démonstration par l'absurde.

Supposons qu'il existe une bijection h : E --> P(E)
Pour tout x dans E, h(x) est un sous-ensemble de E.
Notons  F = { x dans E | x n'est pas dans h(x) }.
Par construction, F est une partie de E, donc F est dans P(E).
Comme h est une bijection, F a un antécédent dans E, ie :
il existe y dans E tel que h(y) = F = {x dans E | x n'est pas dans h(x)}

Alors :
- si y est dans F, par définition de F, y n'est pas dans h(y)=F.
Absurde.
- si y n'est pas dans F, par définition de F, y est dans h(y)=F.
  Absurde aussi.
C'est donc l'hypothèse d'existence de la bijection h qui est fausse.
Cqfd.

(*) Card P(N) = Card R
On constitue donc l'application p : P(N) --> R  de  la  façon  suivante.
Soit E dans P(N). E est donc un sous-ensemble (fini  ou  infini)  de  N.

On forme un nombre d écrit en base 2 de la façon suivante :
d = 0, d0 d1 d2 d3 d4 d5...
où  dn = 1 si n est dans E, 0 sinon
On a alors d dans [0,1], de façon claire (d=0 si E=@, d=1 si E=N).

[On peut définir p de façon plus concise :
 p(E) = \somme_{n dans E} 2^-(n+1)]

La fonction p : E --> p(E)=d est alors une surjection de  P(N)  dans  R.
[Tout réel r de [0,1] est atteint, et  pour  connaître  son  antécédent,
 il suffit d'écrire le développement binaire de r.
 En revanche, p n'est pas une bijection, en raison  de  l'existence  de
 2 développements binaires, comme pour  les  développements  décimaux.]

D'autre  part,  si  on  fabrique  l'application  q  comme  p,  mais   en
considérant que cette fois d est écrit  en  base  3  (ou  10,  ou  n>2),
alors l'application q est une injection de P(N) dans R.
[Tous les réels ne sont pas atteints, mais  chaque  réel  atteint  a  un
 antécédent unique.]

P(N) se surjecte et s'injecte à la fois dans R, donc P(N) ~ R :
                    Card P(N) = Card R

Par généralisation du cas fini, on écrit :
Card R = Card P(N) = 2^(Card N) = 2^(aleph_0)

(*) Card N < Card R
En effet, puisque N est inclus (donc s'injecte) dans R,Card N <= Card R.
De plus, on  vient  de  montrer  que  Card R = Card P(N),  et  que  P(N)
n'est pas équipotent à N. Donc Card N < Card R.

 f) Hypothèse du Continu...

On définit aleph_1  comme  étant  le  plus  petit  cardinal  strictement
supérieur à aleph_0 (pour une définition  plus  rigoureuse  de  aleph_1,
voir l'article de David Madore :
http://www.eleves.ens.fr:8080/home/madore/w/ordinals/ordinals.html)

Le fait de savoir  si  Card R  =  aleph_1  est  indécidable  d'après  la
construction  de  R  seule,  c'est  à  dire  qu'on  peut  arbitrairement
décider que oui ou non.
Habituellement, on fait l'hypothèse que c'est bien le cas
(hypothèse du Continu) : aleph_1 = Card R.

En   termes   plus   simples,   l'hypothèse   du   Continu   dit   que :
toute partie de R est soit au plus dénombrable, soit  équipotente  à  R.

En termes intuitifs  (!)  :  il  n'existe  pas  d'ensemble  "strictement
plus gros" que N mais "strictement plus petit" que R.

 g) Opérations sur les cardinaux

Toutes  les  opérations  valables  avec  les   cardinaux   finis,   sont
extensibles  aux  cardinaux  infinis,  mais  l'intérêt   est   moindre :
Si A ou B est infini :
Card (A Û B) = Card A + Card B = Max (Card A , Card B)
Card (A × B) = Card A . Card B = Max (Card A , Card B)
Card (P(A))  = 2^Card(A)

L'hypothèse du Continu "dit" ainsi que aleph_1 = 2^aleph_0.

 h) Références

 -- Initiation à la théorie des ensembles, J. Breuer
    Dunod, 1961
 -- Théorie axiomatique des ensembles, Jean-Louis Krivine,
    Presses Universitaires de France, 1972 (niveau maîtrise)
    voir aussi :
 -- Théorie des ensembles, Jean-Louis Krivine, Vuibert, 1998


7. Qu'est-ce que le nombre e ?
   ---------------------------

a. le point de vue Néperien.

On pose ln(e) = 1.

Il suffit d'expliquer comment on définit naturellement la fonction
logarithme, et tu comprendras pourquoi e est e.

La fonction ln se définit (à une constante près) par la propriété :
		ln(xy)=ln(x)+ln(y).
En dérivant cette relation, on vérifie que :
y ln'(xy))= ln'(x). Donc : ln'(y) = ln'(1)/y.

On définit donc la fonction ln comme étant LA SEULE FONCTION dérivable
telle que :
  1 ln(xy)=ln(x)+ln(y)
  2. ln'(1) = 1.

Puis on définit e par : ln(e)=1.

L'intérêt de cette définition de la fonction ln : on a de jolis
développements en série entière, la fonction exp, inverse de la fonction
ln vérifie : y'=y et y(0)=1 (c'est un théorème).

Tiens, d'ailleurs, on peut aussi décider de définir d'abord la fonction
exp. Les théorèmes deviennent des définitions et les définitions
deviennent des théorèmes :


b. Le point de vue de Cauchy:

exp est la solution de l'équation différentielle y'=y,
vérifiant : exp(0) = 1.

Suivant ce point de vue, on définit e=exp(1) et on définit ln comme
étant la fonction inverse de la fonction exp (de sorte que ln(e)=1).

On a alors le théorème :
  1. ln(xy)=ln(x)+ln(y)
  2. ln'(1) = 1.


c. Le point de vue Théologique e^(i\pi) + 1 = 0.

Il suffit de définir la fonction puissance.

Si a est un réel positif, on définit a^n pour tout entier naturel n,
puis a^(1/p) pour tout entier naturel p (c'est le nombre b tel que
b^p=a.  Ce nombre existe car l'application b->b^p est un bijection)

donc a^q pour tout nombre rationnel positif q, puis a^x pour tout réel
positif x (par passage à la limite).

On s'aperçoit que la fonction que l'on définit ainsi admet un
prolongement analytique : z dans C -> a^z dans C, on démontre qu'il
existe une infinité de réels positifs tel que e^(i\pi) + 1 = 0

et on définit e comme le plus petit réel positif tel que :
                            e^(i\pi) + 1 = 0

Ensuite, on peut définir la fonction exponentielle par exp(x)=e^x, et
les définitions du second point de vue deviennent des théorèmes (alors
qu'en utilisant la définition du second point de vue (convenablement
étendue aux nombres complexes), l'équation e^(i\pi) + 1 = 0 est un
théorème).

========================================================================


VI Mathématiques et Ordinateurs.
   =============================

1. Logiciels de Mathématiques.
   ---------------------------

| Il existe une multitude de programmes informatiques pouvant être 
| utiles aux mathématiques de multiples façons. On peut distinguer
| plusieurs types d'applications.
|
| a) Les logiciels de calcul formel.
|
|    Ces programmes permettent de manipuler des expressions symboliques
|    et de calculer avec (par exemple dériver des fonctions, factoriser
|    des polynômes, calculer des développement en série entière, etc.).
|
|    Les plus connus sont sans doute les logiciels commerciaux Maple,
|    de Maplesoft, et Mathematica, de Wolfram Research. Il existe
|    également des systèmes libres de calcul formel généralistes, tels
|    que Yacas (léger et facile), Maxima (puissant et complet) ou encore
|    Axiom (efficace pour manipuler des structures algébriques
|    abstraites).
|
|    Certains programmes de calcul symbolique sont plus spécialisés dans
|    certains domaines, comme PARI/GP pour la théorie des nombres, GAP
|    pour la théorie des groupes ou Macaulay pour l'algèbre commutative.
|
|    Une liste assez complète de ce qui existe est disponible ici :
|    http://en.wikipedia.org/wiki/List_of_computer_algebra_systems
|
| b) Les logiciels d'analyse numérique.
|
|    À l'opposée, on trouve des logiciels permettant d'effectuer des
|    calculs approchés sur des quantités importantes de données
|    numériques (résoudre de grands systèmes linéaires, effectuer des
|    transformées de Fourier rapides, résoudre numériquement des
|    équations aux dérivées partielles, etc.).
|
|    On peut citer notamment le logiciel commercial MATLAB, référence du 
|    domaine, et ses concurrents libres GNU Octave et Scilab, à la
|    syntaxe et aux fonctionnalités très similaires. Tous les trois
|    manipulent en premier lieu des matrices.
|
|    L'écriture de simulations numériques s'effectue par ailleurs souvent 
|    dans des langages de programmation classiques (C, FORTRAN, Python...) 
|    assistés de bibliothèques spécialisées, telles que LAPACK en FORTRAN
|    ou SciPy en Python. Un répertoire de nombreux ensembles de routines
|    est disponible à l'adresse :
|    http://gams.nist.gov/
|
| c) Les logiciels de statistiques.
|
|    On s'éloigne un peu des mathématiques à proprement parler, mais on
|    peut mentionner notamment GNU R, un langage de programmation et un
|    environnement logiciel très puissant et libre dans le domaine de 
|    l'analyse statistique.
|    
| d) Les logiciels de tracé de graphes.
|
|    Certains programmes sont spécialisés dans la représentation
|    graphique (courbes, surfaces, nuages de points, etc.) de fonctions
|    ou de données numériques. Citons par exemple gnuplot, descartes ou
|    encore ploticus.
|
| e) Les logiciels de géométrie plane.
|
|    Il existe des programmes permettant de réaliser et raisonner sur
|    des figures de géométrie euclidienne plane : on peut placer des
|    points et construire des droites les reliant, des parallèles et des
|    perpendiculaires, des coniques, des lieux de points, et ainsi de
|    suite.
|
|    Le plus connu du public francophone est sans doute Cabri Géomètre,
|    mais il existe de nombreux concurrents, notamment libres, tels que
|    Dr. Geo, Kig, GeoGebra ou encore GeoProof (ce dernier étant doté de
|    fonctionnalités de démonstration automatique).
|
| f) Les assistants de preuve.
|
|    Certains programmes permettent, dans un système formel donné, de
|    vérifier la correction d'une démonstation, et dans une certaine
|    mesure de produire automatiquement la preuve de certains énoncés.
|    Les techniques ainsi mises en oeuvre sont parfois appliquées à la
|    démonstrations de certains algorithmes, ou à la certification de
|    preuves de résultats mathématiques non-triviaux (récemment, on a
|    ainsi pu voir certifiée en Coq une démonstration du théorème des
|    quatre couleurs, grâce aux travaux de B. Werner et G. Gonthier).
|
|    On peut citer dans le domaine des programmes tels que Coq, PhoX
|    ou encore Isabelle.
|
| g) La mise en page mathématique.
|
|    La réalisation de documents imprimés comportant un nombre important
|    de formules mathématiques et autres diagrammes est à peu de choses
|    près l'apanage d'un seul logiciel : LaTeX, éventuellement complété
|    de divers paquets d'extension (comme amsmath pour des
|    fonctionnalités mathématiques supplémentaires ou xy pour les
|    diagrammes) et de programmes externes pour des tâches particulières
|    (comme BibTeX pour la gestion des bibliographies ou METAPOST pour
|    la réalisation de figures).
|
|    LaTeX n'est pas un éditeur « WYSIWYG », au sens où l'utilisateurs
|    ne manipule pas directement une prévisualisation du document
|    imprimé, mais un fichier texte dans lequel il indique des
|    instructions de mise en forme, ce qui rend particulièrement commode
|    l'insértion des expressions mathématiques. Il existe cependant des
|    surcouches graphiques telles que LyX permettant aux utilisateurs
|    rebutés par le texte pur de profiter de la puissance de LaTeX via
|    un éditeur plus visuel. Dans la même veine, on peut mentionner le
|    traitement de texte scientifique GNU TeXmacs, qui s'inspire des
|    principes de séparation de la structure et du contenu qui prévalent
|    en TeX/LaTeX.
|
|    En ce qui concerne la mise à disposition de textes mathématiques en
|    ligne sur le web, elle se fait encore très fréquemment via LaTeX, en
|    proposant aux visiteurs de télécharger des documents imprimables PS
|    ou PDF, ou bien en insérant les formules mathématiques composées par
|    LaTeX sous forme d'images dans la page HTML (statiquement grâce à
|    des programmes comme LaTeX2HTML, ou de manière dynamique comme le
|    fait WikiTeX). La norme MathML, publiée depuis 1999 et dont le
|    support commence à apparaître dans les navigateurs web, doit
|    permettre de remédier à cette situation. MathML n'est toutefois
|    pas du tout un langage conçu pour qu'un être humain écrive avec,
|    et donc la réalisation de documents XHTML contenant du MathML passe
|    par des traitements de texte comme TeXmacs, OpenOffice.org ou
|    l'éditeur intégré au navigateur Amaya. Il existe aussi des outils, 
|    comme itex2mml, pour convertir des expressions mathématiques LaTeX
|    en MathML.


2. L'agorithme de CORDIC sur les calculatrices.
   --------------------------------------------

  Un des algorithmes les plus courants sur calculatrice scientifique
  est l'algorithme CORDIC (pour "COordinate Rotation DIgital Computer")
  dont la référence classique est : Jack E. Volder, 
  "The CORDIC Trigonometric Computing Technique," IRE Transactions
  on Electronic Computers, Vol. EC-8, pp.330-334, 1959. J. Volder y
  décrit des algorithmes pour l'évaluation rapide des fonctions sinus 
  et cosinus au moyen d'une série de rotations du système de coordonnées
  (méthodes qu'on retrouvera lors de l'évaluation de la tangente)

  Dans une calculatrice typique un nombre 'flottant' occupe 8 octets 
  de mémoire et se décompose en :
  - une mantisse constituée de 13 chiffres codés indépendamment sur
    4 chiffres binaires (on parle de Binaire Code Decimal ou BCD) 
  - un exposant (puissance de 10) éventuellement signé
  - le signe du nombre (et de l'exposant s'il n'est pas signé)

  Les algorithmes mathématiques sont généralement implémentés à un 
  plus bas niveau utilisant une représentation fixe en BCD (sur 16
  chiffres soit 8 octets dans notre exemple).
  Une multiplication (division) par 10^n peut donc être remplacée par
  un décalage de 4*n chiffres binaires. Sur calculatrice on tente 
  d'éviter les opérations 'lourdes' que sont la multiplication et la
  division.
  
  Toutes les fonctions 'standard' peuvent se ramener (entre autres) 
  aux quatre fonctions suivantes :  ln, exp, tan, arctan 
 
  Soit à évaluer une de ces fonctions f au point x, le principe des
  algorithmes CORDIC est d'effectuer une série de transformations 
  simples (addition/soustraction et décalage) réduisant la valeur de
  x à une valeur très faible en même temps qu'élaborant le résultat.     
  Chacune de ces transformations nécessite une valeur précalculée 
  de f (ou de son inverse). Le résultat est obtenu par une simple 
  interpolation linéaire (ou un développement en série si davantage
  de chiffres sont requis).
 
  Pour les 4 fonctions précédentes les tableaux L et A suffiront
  (pour obtenir plus de 12 chiffres de précision) :
  
   L= [ln(2),   ln(1.1),   ln(1.01),   ..., ln(1.000001)]
   A= [atan(1), atan(0.1), atan(0.01), ..., atan(0.0001)]

   (pour tanh et argtanh il faudrait en plus AH= [atanh(1),...] )


  On procède en deux étapes :
  
1. Ramener la valeur à évaluer dans l'intervalle où la méthode est 
   applicable en utilisant (par exemple) les transformations :
   (ln(10), Pi/2, Pi sont également précalculées et Pi/4= atan(1))
         
     - ln     sur [1, 10[     (1)  ln(x)= ln(x*10^(-n))+n*ln(10)
     - exp    sur [0, ln(10)[ (2)  exp(x)= exp(x-n*ln(10))*10^n
          
     - arctan sur [0, 1[           si x<0 atan(x)= -atan(-x) puis
                                   si x>1 atan(x)= Pi/2-atan(1/x)
     - tan    sur [0, Pi/4[   (3)  tan(x)= tan(x modulo Pi) puis
                                   si x>Pi/2 tan(x)= -tan(Pi-x) puis
                              (4)  si x>Pi/4 tan(x)= 1/tan(Pi/2-x)
                        
   En réalité les algorithmes restent valides pour des valeurs plus 
   grandes que ce qui est précisé mais perdent alors en efficacité.
        

2. Appliquer l'algorithme en itérant sur l'indice k de l'élément 
   précalculé (on commence toujours par le plus grand terme). 
   (L'erreur commise dans chaque cas est inférieure à 10^(-12))     

     - ln : Représentons x par le produit suivant :
            x= (1+1)^n0*(1+1/10)^n1*...*(1+1/10^6)^n6*(1+eps.)
            avec n0 entier positif maximal puis n1 maximal, etc..
            de sorte que ln(x)= n0*ln(1+1)+n1*ln(1+1/10)+... +ln(1+eps.)
          
       k= 0; y= 0; p= 1;       //p est le produit partiel plus haut
       TantQue (k <= 6)        
           TantQue (x >= p+p*10^(-k))
               y= y+L[k];      //ou L[k]= log(1+10^(-k))
               p= p+p*10^(-k);
           FinTant;
           k= k+1;             //à la fin on a :
       FinTant;                // x/p= (1+eps.) donc eps.= x/p-1
       Rendre y+(x/p-1);       //le terme suivant est -(x/p-1)^2/2
                               //réponse exacte : y+ln(x/p)

   - exp : On écrira cette fois :
             exp(x)= (1+1)^n0*(1+1/10)^n1*...*(1+1/10^6)^n6*(1+eps.)
                           
       k= 0; y= 1;             //y est le produit partiel précédent
       TantQue (k <= 6)
           TantQue (x >= L[k])
               x= x-L[k];
               y= y+y*10^(-k);
           FinTant;
           k= k+1;             //à la fin on a :
       FinTant;                //exp(x)=(1+eps.) donc eps.= exp(x)-1
       Rendre y+y*x;           //le terme suivant est +y*x^2/2!
                               //réponse exacte : y*exp(x)

   - arctan : (pour argtanh voir note (5))
                On utilise une représentation de type
                atan(x)= n0*A[0]+n1*A[1]+...+n4*A[4]+eps.
                obtenue en répétant la formule :
                atan(x/y)= atan(x'/y')+atan(10^(-k))
                avec x'= x-y*10^(-k) et y'= y+x*10^(-k) qui donne :
       
       k= 0; y= 1; r= 0;
       TantQue (k <= 4)
           TantQue (x < y*10^(-k))
               k= k+1;
           FinTant;
           xp= x-y*10^(-k);
           y= y+x*10^(-k);
           x= xp;
           r= r+A[k];          //où A[k]= atan(10^(-k))
       FinTant;                //à ce stade : atan(x/y)= eps.
       Rendre r+(x/y);         //le terme suivant est -(x/y)^3/3
                               //réponse exacte : r+atan(x/y)
     
   - tan : Cette fois si on a : (pour tanh voir note (6))
             x= n0*A[0]+n1*A[1]+...+n4*A[4]+eps.
             et si tan(s)=n/d alors tan(s+atan(10^(-k)))=n'/d'
             avec n'= n+d*10^(-k) et d'= d-n*10^(-k)

       k= 0; n= 0; d= 1;       //tan(somme partielle)= n/d= 0
       TantQue (k <= 4)
           TantQue (x >= A[k])
               x= x-A[k];      //reste de la somme partielle                      
               np= n+d*10^(-k);// n'
               d= d-n*10^(-k); // d'
               n= np;
           FinTant;
           k= k+1;
       FinTant;                //à ce stade x= eps.
       Rendre (n+x*d)/(d-x*n); //pour plus de précision remplacer 
                               //x par x+x^3/3
                               //exact : (n+d*tan(x))/(d-n*tan(x))
       (pour sinus et cosinus voir la note (7))


  Ce qui précède ne correspond qu'à une implémentation parmi d'autres 
  et on aurait pu préférer une table de racines carrées de (1+1/10^k)
  par exemple (avec l'avantage de traiter les racines carrées!).

  Les implémentations sur ordinateurs utilisent plutôt la base 2 
  (car travaillant en binaire plutôt qu'en BCD) ce qui conduit à
  remplacer tous les 10^n par 2^n (et... à précalculer davantage 
  de termes).
                
  On aurait également pu calculer moins de termes en utilisant un
  développement en série du second ordre ou davantage car les
  multiplications sont devenues très rapides (méthode encore bien 
  plus utile pour obtenir davantage de chiffres de précision et... 
  que ne permettent pas les méthodes qui suivent).
                
                
  Mais l'efficacité de la multiplication autorise également l'essor
  de techniques concurrentes comme les approximations polynômiales
  apparentées aux polynômes de Chebyshev (Tschebyscheff).
  On y construit des polynômes (au moyen de l'algorithme de Remez par
  exemple) de telle sorte que l'erreur maximale commise en remplacant 
  la fonction par son polynôme sur un intervalle fixé soit la plus
  petite possible. Un précurseur de ces méthodes est Hastings, C, Jr. 
  dans "Approximations for Digital Computers", Princeton University 
  Press, 1955. 

   Notes :
   (1) à ce stade la représentation flottante est utilisée donc il 
       suffit de calculer le logarithme de la mantisse et d'ajouter 
       l'exposant que multiplie ln(10). 
   (2) n est la partie entière de x divise par ln(10) qu'on pourra
       additionner directement à l'exposant.
   (3) le calcul de la tangente n'a pas de sens si |x| > 10^13
   (4) il vaut mieux ne faire cela que pour des valeurs proches
       de Pi/2 afin d'éviter la division.
   (5) l'implémentation de argtanh est presque identique pourvu de 
       commencer avec k= 1 puis de remplacer A[k] par AH[k] et
       y= y+x*10^(-k) par y= y-x*10^(-k).
   (6) l'implémentation de tanh s'en déduit en commençant avec k= 1,
       en remplaçant A[k] par AH[k], d=d-n*10^(-k) par d=d+n*10^(-k) 
       et (n+x*d)/(d-x*n) par (n+x*d)/(d+x*n).
   (7) si on ajoute  p= 1; à la ligne d'initialisation ainsi que
       p= p+p*10^(-2*k); à la boucle la plus interne et enfin
       p= p+p*x*x; tout à la fin alors le sinus est donné par 
        (n+x*d)/sqrt(p) et le cosinus par (d-x*n)/sqrt(p)
       (Les formules moins efficaces sin(x)= tan(x)/sqrt(1+tan(x)^2)
        et cos(x)= 1/sqrt(1+tan(x)^2) sont plus souvent utilisées).



========================================================================


VIII Références et remerciements.
     ===========================

1. Références.
   -----------

 a) Livres

On ne saurait trop répéter que les livres dépendent du niveau en
mathématiques du lecteur. Ainsi si vous êtes en terminale ne vous lancez
pas immédiatement dans la démonstration du dernier théorème de Fermat
par Andrew Wiles. Une approche des courbes elliptiques peut être
préférable, avant toute autre lecture. :o)

Sur l'histoire des mathématiques:

-- « Une histoire des mathématiques (Routes et dédales) »
      de A. Dahan-Dalmedico et J. Peifer aux éditions Point-Science.

-- « Histoire universelle des chiffres »
      de G. Iffrah aux éditions Seghers.

-- « Mathématique au fil des âges (épistémologie et histoire) »
      collectif du groupe I.R.E.M. aux éditions Gauthier-Villar.

-- « Eléments d'histoire des mathématiques »
      de N. Bourbaki aux éditions Hermann.

-- « Abrégé d'histoire des mathématiques 1700 - 1900 »
      sous la direction de J. Dieudonné.

-- « Les grands courants de la pensée mathématique »
      sous la direction de F. Le Lionnais, aux éditions PUF.

 b) News et autres FAQs

  Dans le "Big-8" :

 -- sci.math                      FAQ à l'adresse
       http://www.faqs.org/faqs/sci-math-faq/

 -- sci.math.num-analysis         FAQ à l'adresse
|      http://www.mathcom.com/corpdir/techinfo.mdir/scifaq/

 c) Web

L'Encyclopédie Électronique des Suites Entières de N. J. A. Sloane
    http://www.research.att.com/~njas/sequences/indexfr.html

La base de données MacTutor History of Mathematics archive, développée
et gérée par John O'Connor et Edmund Robertson à l'Université de
St-Andrews (Ecosse) http://www-groups.dcs.st-and.ac.uk/~history/

La page Web des nombres premiers,
|   http://primes.utm.edu/
|
| La base de donnée de prépublications ArXiV :
|   http://arxiv.org/archive/math
|
| Les mathématiques sur la Wikipédia francophone :
|   http://fr.wikipedia.org/wiki/Portail:Math%C3%A9matiques



2. Remerciements.
   -------------

Une version html de ce texte est disponible à l'adresse
                       <http://faq.maths.free.fr/> 
que Kristen Le Liboux et Régis Décamps entretiennent.

Nous tenions à remercier tous ceux qui ont participé volontairement,
par la rédaction de paragraphes entiers, ou involontairement, par leurs
contributions sur le forum, à cette FAQ.

En particulier,
Silvain Abadie, Guillaume Allègre, Frederic Bastok, Hubert Bayet,
Dominique Bernardi, Yann Chevalier, Jérôme Collet, Sébastien Dauby,
Daniel Dubuisson, Raphaël Giromini, Vincent Lefevre, Stéphane Ménart,
Jean-Pierre Minisini, Christian Radoux, Guillaume Réocreux, Fréderic
Schutz et Mehdi Tibouchi.

| D'émormes mercis à Guillaume Allègre, pour avoir entretenu sur son
| site la proto-faq du forum, à Frédéric Schutz, pour avoir rédigé la 
| première version de la FAQ, ainsi qu'à Raphaël Giromini, qui en était
| le précédent mainteneur.

De chaleureux remerceiments pour leurs relectures et leurs corrections :
Emmanuel Bresson, Petrut Constantine, Jean-Paul Delahaye, Paul Jobling,
Kristen Le Liboux et Olivier Miakinen.

| Pour toute remarque concernant cette FAQ, ou pour y incorporer de
| nouveaux paragraphes, s'adresser à son mainteneur Mehdi Tibouchi
| (medtib@alussinan.org).

=======================================================================

Les autres parties de cette FAQ se trouve dans les documents intitulés :
                 [FAQ] fr.sci.maths - partie 1/3
                 [FAQ] fr.sci.maths - partie 2/3
Ces documents sont disponibles sur fr.sci.maths ou à l'adresse :
            http://www.usenet-fr.net/fur/maths/maths-faq.html
            http://www.usenet-fr.net/fur/maths/maths-faq-2.html
.


Valid XHTML 1.0! [Retour au sommaire] Valid CSS!

Traduit en HTML par faq2html.pl le Wed Nov 3 05:42:13 2010 pour le site Web Usenet-FR.