Livres

Home Page

Jean Berstel, Jean-Éric Pin et Michel Pocchiola

McGraw-Hill France, 1991.

Présentation

Depuis quelques années, l'introduction d'une épreuve d'informatique aux concours d'entrée dans les grandes écoles scientifiques a créé un intérêt accru pour des exemples d'algorithmes et de programmes qui s'inspirent du programme des classes préparatoires.

Partant de sujets posés aux concours d'entrée à l'ENS d'Ulm, ce livre propose à la fois des solutions aux questions mathématiques et des programmes types pour les questions algorithmiques. Les réponses sont, la plupart du temps, accompagnées de développements qui permettent de replacer le problème dans son cadre mathématique et le programme dans un contexte informatique. Dans cette forme élargie, le livre intéresse également les étudiants des premier et deuxième cycles universitaires en mathématiques et en informatique; il est aussi un complément pour la préparation de l'option d'informatique de l'agrégation.

Chaque sujet est présenté sous forme d'un triptyque. La première partie est un énoncé, la deuxième partie donne une solution aux questions mathématiques et la troisième partie contient les procédures ou fonctions qui répondent aux questions de programmation.

Les thèmes traités concernent principalement l'algèbre linéaire et les polynômes (volume 1), la combinatoire, la géométrie et l'arithmétique (volume 2).

Les programmes présentés dans ce livre fonctionnent en Pascal sur des ordinateurs compatibles PC ou sur des ordinateurs Macintosh.

Table des matières du volume I

Avant-propos

Partie I : Algèbre linéaire 1

Chapitre 1. Calcul matriciel 3

1.1 Une bibliothèque 3
1.2 Résolution de systèmes linéaires 9
1.2.1 Méthode de Gauss 9
1.2.2 Méthode de Jordan 15
1.3 Rang d'une matrice 18

Chapitre 2. Manipulation de matrices 23

2.1 Pseudo-inverses 23
2.1.1 Enoncé : pseudo-inverses 23
2.1.2 Solution : pseudo-inverses 24
2.1.3 Programme : pseudo-inverses 27
2.2 Matrices trigonalisables 32
2.2.1 Enoncé : matrices trigonalisables 32
2.2.2 Solution : matrices trigonalisables 34
2.2.3 Une bibliothèque de manipulation des matrices complexes 40
2.2.4 Programme : matrices trigonalisables 45

Chapitre 3. Décompositions 51

3.1 Décomposition LU 51
3.2 Décomposition de Choleski 57
3.3 Décomposition QR 59
3.3.1 Enoncé : décomposition QR (méthode de Givens) 59
3.3.2 Solution : décomposition QR (méthode de Givens) 60
3.3.3 Programme : décomposition QR (méthode de Givens) 61
3.3.4 Décomposition QR (méthode de Householder) 65

Chapitre 4. Matrices tridiagonales 69

4.1 Opérations sur les matrices tridiagonales 69
4.1.1 Système tridiagonal d'équations 69
4.1.2 Décomposition LU 71
4.1.3 Décomposition de Choleski 72
4.2 Tridiagonalisation 72
4.2.1 Enoncé : tridiagonalisation (méthode de Givens) 73
4.2.2 Solution : tridiagonalisation (méthode de Givens) 74
4.2.3 Programme : tridiagonalisation (méthode de Givens) 75
4.3 Tridiagonalisation (méthode de Householder) 78
4.3.1 Enoncé : tridiagonalisation (méthode de Householder) 79
4.3.2 Solution : tridiagonalisation (méthode de Householder) 80
4.3.3 Programme : tridiagonalisation (méthode de Householder) 81

Chapitre 5. Valeurs et vecteurs propres 85

5.1 Méthode de Jacobi 85
5.1.1 Enoncé : méthode de Jacobi 85
5.1.2 Solution : méthode de Jacobi 87
5.1.3 Programme : méthode de Jacobi 90
5.2 Méthode QR 96
5.3 Valeurs propres de matrices tridiagonales 100
5.3.1 Enoncé : valeurs propres de matrices tridiagonales 100
5.3.2 Solution : valeurs propres de matrices tridiagonales 101
5.3.3 Programme : calcul par dichotomie 102
5.3.4 Programme : calcul par suites de Sturm 107
5.4 Méthode LR de Rutishauser 110

Chapitre 6. Matrices en combinatoire 117

6.1 Matrices unimodulaires 117
6.1.1 Enoncé : matrices unimodulaires 117
6.1.2 Solution : matrices unimodulaires 119
6.1.3 Programme : matrices unimodulaires 124
6.2 Matrices irréductibles 130
6.2.1 Enoncé : matrices irréductibles 130
6.2.2 Solution : matrices irréductibles 132
6.2.3 Programme : matrices irréductibles 136

Partie II : Polynômes 143

Chapitre 7 : Polynômes 145

7.1 Suites de Sturm 145
7.1.1 Enoncé : suites de Sturm 145
7.1.2 Solution : suites de Sturm 146
7.1.3 Programme : suites de Sturm 151
7.2 Polynômes symétriques 158
7.2.1 Enoncé : polynômes symétriques 158
7.2.2 Solution : polynômes symétriques 160
7.2.3 Programme : polynômes symétriques 167
7.3 Factorisation de polynômes 178
7.3.1 Enoncé : factorisation de polynômes 178
7.3.2 Solution : factorisation de polynômes 180
7.3.3 Programme : factorisation de polynômes 187

Annexes

Chapitre A. Un environnement 203

A.1 Conseils de programmation 203
A.2 Variations en Pascal 209
A.3 Bibliothèques 210
A.3.1 Généralités 212
A.3.2 Polynômes 216
A.3.3 Les complexes 222
A.4 Menus 229

Chapitre B. Les bibliothèques 236

B.1 Généralités 236
B.2 Calcul matriciel 237
B.3 Polynômes 238
B.4 Nombres complexes 239

Table des matières du volume II

Partie III : Combinatoire 1

Chapitre 8. Exemples combinatoires 3

8.1 Génération d'objets combinatoires 3
8.1.1 Sous-ensembles 3
8.1.2 Sous-ensembles à k éléments 5
8.1.3 Permutations 7
8.2 Nombres de Bernoulli 11
8.2.1 Enoncé : nombres de Bernoulli 11
8.2.2 Solution : nombres de Bernoulli 11
8.2.3 Programme : nombres de Bernoulli 13
8.3 Partitions d'entiers 16
8.3.1 Enoncé : partitions d'entiers 16
8.3.2 Solution : partitions d'entiers 18
8.3.3 Programme : partitions d'entiers 26

Chapitre 9. Combinatoire des mots 35

9.1 Terminologie 35
9.2 Mots de Lukasiewicz 38
9.2.1 Enoncé : mots de Lukasiewicz 38
9.2.2 Solution : mots de Lukasiewicz 40
9.2.3 Programme : mots de Lukasiewicz 43
9.3 Mots de Lyndon 48
9.3.1 Enoncé : mots de Lyndon 48
9.3.2 Solution : mots de Lyndon 49
9.3.3 Programme : mots de Lyndon 51
9.4 Suite de Thue-Morse 61
9.4.1 Enoncé : suite de Thue-Morse 61
9.4.2 Solution : suite de Thue-Morse 63
9.4.3 Programme : suite de Thue-Morse 66

Partie IV : Géométrie 73

Chapitre 10. Géométrie algorithmique 75

10.1 Polyèdres et enveloppes convexes 76
10.2 Quelques primitives géométriques 86
10.3 Triangulation de Delaunay 93
10.3.1 Enoncé : triangulation de Delaunay 93
10.3.2 Solution : triangulation de Delaunay 95
10.3.3 Programme : triangulation de Delaunay 102
10.4 Galerie d'art 109
10.4.1 Enoncé : galerie d'art 109
10.4.2 Solution : galerie d'art 111
10.4.3 Programme : galerie d'art 115

Partie V : Arithmétique 121

Chapitre 11. Problèmes arithmétiques 123

11.1 Entiers de Gauss 123
11.1.1 Enoncé : entiers de Gauss 123
11.1.2 Solution : entiers de Gauss 124
11.1.3 Programme : entiers de Gauss 129
11.2 Arithmétique modulaire 138
11.2.1 Enoncé : arithmétique modulaire 138
11.2.2 Solution : arithmétique modulaire 139
11.2.3 Programme : arithmétique modulaire 142

Chapitre 12. Grands nombres 149

12.1 Entiers en multiprécision 149
12.1.1 Enoncé : entiers en multiprécision 149
12.1.2 Solution : entiers en multiprécision 150
12.1.3 Programme : entiers en multiprécision 153
12.2 Arithmétique flottante 168
12.2.1 Enoncé : arithmétique flottante 168
12.2.2 Solution : arithmétique flottante 169
12.2.3 Programme : arithmétique flottante 170
12.3 Calcul de PI par arctangente 181
12.3.1 Enoncé : calcul de PI par arctangente 181
12.3.2 Solution : calcul de PI par arctangente 183
12.3.3 Programme : calcul de PI par arctangente 188
12.4 La formule de Brent-Salamin 192
12.4.1 Enoncé : la formule de Brent-Salamin 192
12.4.2 Solution : la formule de Brent-Salamin 193
12.4.3 Programme : la formule de Brent-Salamin 200

Annexes

Chapitre A. Un environnement 207

A.1 Conseils de programmation 207
A.2 Variations en Pascal 213
A.3 Bibliothèques 214
A.3.1 Généralités 216
A.3.2 Polynômes 220
A.3.3 Les complexes 226
A.3.4 Les rationnels 233
A.4 Menus 236

Chapitre B. Les bibliothèques 243

B.1 Généralités 243
B.2 Calcul matriciel 244
B.3 Polynômes 245
B.4 Nombres rationnels 246
B.5 Nombres complexes 247
B.6 Mots 248
B.7 Entiers en multiprécision 248
B.8 Arithmétique flottante 249
B.9 Géométrie 250

Index

Errata