Histoire d'algorithmes - Du caillou à la puce

Couverture......Page 1
Page de titre......Page 2
Introduction......Page 4
Chapitre 1. Algorithmes des opérations arithmétiques......Page 12
1. Divisions sumériennes......Page 14
2. Un algorithme babylonien pour le calcul des inverses......Page 16
3. Algorithmes arithmétiques égyptiens......Page 21
4. La multiplication à l'aide du tableau......Page 27
5. Optimisation des calculs......Page 35
6. Division simple par différence sur l'abaque......Page 38
7. Division sur le boulier......Page 43
8. Écriture décimale......Page 46
9. Arithmétique binaire......Page 49
10. Arithmétique des ordinateurs......Page 53
Post-Scriptum......Page 57
Bibliographie......Page 58
Chapitre 2. Les carrés magiques......Page 60
1. Une technique de carrés à enceintes......Page 65
2. Un procédé par pointages......Page 70
3. Le procédé par 2 et 3......Page 76
4. La méthode par enceintes d'Arnauld......Page 83
Bibliographie......Page 95
Chapitre 3. Autour des méthodes de fausse position......Page 96
1. Babylone : une fausse position géométrique (XVIIIe siècle av. J.-C.)......Page 100
2. Égypte : le problème 26 du Papyrus Rhind (XVIIIe siècle av. J.-C.)......Page 102
3. Chine: le chapitre VII du Jiuzhang suanshu......Page 105
4. Inde : Bhaskara formule la règle de simple fausse position (XIIe siècle)......Page 112
5. Qusta ibn Luqa : une justification géométrique (IXe siècle)......Page 114
6. Ibn al-Banna : la méthode des plateaux (XIIIe siècle)......Page 117
7. Fibonacci : la règle elchatayn, (1202)......Page 119
8. Pellos : règle de trois et méthode de simple fausse position......Page 122
9. Clavius : résolution d'un système d'équations......Page 124
Bibliographie......Page 129
1. L'algorithme d'Euclide......Page 130
2. Comparaison des rapports......Page 135
3. L'identité de Bézout......Page 140
4. Les fractions continues......Page 145
5. Le nombre de racines d'une équation......Page 152
Bibliographie......Page 158
Chapitre 5. De la mesure du cercle au calcul de Pi......Page 160
1. Le périmètre du cercle......Page 162
2. L'aire du cercle dans le Jiuzhang Suanshu......Page 168
3. La méthode des isopérimètres......Page 176
4. Quadrature arithmétique......Page 180
5. Utilisation des séries......Page 185
Épilogue......Page 189
Bibliographie......Page 190
Chapitre 6. Les méthodes de Newton......Page 194
1. La linéarisation de l'équation......Page 196
2. La formule de récurrence......Page 202
3. Les conditions initiales......Page 206
4. La mesure de la convergence......Page 211
5. Les racines complexes......Page 217
6. La règle et les petits parallélogrammes......Page 221
Bibliographie......Page 226
Chapitre 7. Résolutions d'équations par approximations successives......Page 228
Extractions de racines carrées......Page 230
1. La méthode de Héron d'Alexandrie......Page 232
2. La méthode de Théon d'Alexandrie......Page 233
3. Algorithmes binomiaux médiévaux......Page 235
4. Les tableaux d'al-Tusi......Page 238
5. La méthode de Viète......Page 244
6. L'équation de Kepler......Page 251
7. La méthode des séries récurrentes de Bernoulli......Page 255
8. L'approximation par fractions continues......Page 260
9. Le schéma de Ruffini-Budan......Page 264
Bibliographie......Page 270
Chapitre 8. Des algorithmes de l'arithmétique......Page 272
Diviseurs et multiples......Page 274
1. Le crible d'Ératosthène......Page 275
2. Critères de divisibilité......Page 278
3. Calcul de résidus quadratiques......Page 282
Tests de primalité......Page 286
4. La réciproque du théorème de Fermat......Page 287
5. Le test de Lucas......Page 291
6. Le test de Pépin......Page 296
Algorithmes de factorisation......Page 299
7. Factorisation par différence de deux carrés......Page 300
8. Factorisation par les résidus quadratiques......Page 303
9. Factorisation par les fractions continues......Page 306
L'équation de Pell-Fermat......Page 309
10. Les Arithmétiques de Diophante......Page 310
11. Le résultat de Lagrange......Page 312
Bibliographie......Page 318
Chapitre 9. Résolution de systèmes d'équations linéaires......Page 320
1. Les formules de Cramer......Page 322
2. La méthode des moindres carrés......Page 325
3. Le "pivot" de Gauss......Page 329
4. Une méthode itérative de Gauss......Page 334
5. La méthode de Jacobi......Page 338
6. La méthode de Seidel......Page 341
7. La rapidité de convergence selon Nekrasov......Page 345
8. La méthode du Commandant Cholesky......Page 348
Épilogue......Page 352
Bibliographie......Page 354
Chapitre 10. Tables et interpolation......Page 356
1. Les tables de cordes de Ptolémée......Page 359
2. Les logarithmes décimaux de Briggs......Page 366
3. La formule de Gregory-Newton......Page 370
4. Le polynôme d'interpolation de Newton......Page 374
5. Le polynôme d'interpolation de Lagrange......Page 380
6. Majoration de l'erreur......Page 383
7. L'algorithme de Neville......Page 388
Épilogue: l'algorithme C.O.R.D.I.C......Page 390
Bibliographie......Page 392
Chapitre 11. Quadratures approchées......Page 394
1. La formule de Gregory......Page 396
2. La règle des trois-huitièmes de Newton......Page 398
3. Les formules de Newton-Cotes......Page 400
4. Les formules correctives de Stirling......Page 402
5. La méthode composite de Simpson......Page 404
6. Les formules de quadrature de Gauss......Page 406
7. Le choix de Tchebychev......Page 410
Épilogue......Page 413
Bibliographie......Page 414
Chapitre 12. Résolutions approchées d'équations différentielles......Page 416
1. La méthode d'Euler......Page 418
2. L'existence d'une solution......Page 422
3. Les méthodes de Runge......Page 426
4. Les méthodes de Heun......Page 433
5. Les méthodes de Kutta......Page 437
6. Les méthodes d'Adams......Page 442
Épilogue......Page 447
Bibliographie......Page 448
Chapitre 13. Approximation de fonctions......Page 450
Approximation uniforme......Page 452
1. La formule de Taylor......Page 453
2. Le reste de Lagrange......Page 454
3. Le polynôme de meilleure approximation selon Tchebychev......Page 459
4. Approximation par fonctions splines cubiques......Page 465
Approximation en moyenne quadratique......Page 468
5. La série de Fourier......Page 470
6. La transformée de Fourier rapide......Page 473
Bibliographie......Page 476
Chapitre 14. Accélération de convergence......Page 478
1. La méthode de Stirling pour les séries......Page 479
2. La formule d'Euler-Maclaurin pour les intégrales......Page 484
3. Le calcul de la constante d'Euler......Page 489
4. La méthode d'Aitken pour les suites......Page 493
5. La méthode d'extrapolation de Richardson......Page 498
Bibliographie......Page 502
Vers un concept d'algorithme......Page 506
1. La définition de 1931......Page 510
2. Fonctions récursives générales au sens de Gödel......Page 512
3. La calculabilité effective de Church......Page 515
4. Fonctions récursives au sens de Kleene......Page 519
5. La machine de Turing......Page 522
6. La machine de Post......Page 528
Conclusion......Page 535
Bibliographie......Page 536
Bibliographie générale......Page 538
Notices biographiques......Page 541
Index des noms propres......Page 578
Index terminologique......Page 582
Table des matières (détaillée)......Page 586