Livres 
Home
Page
Maths Info
|
Mathématiques et
informatique : exercices résolus, vol. 1 et 2
|
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.2 Résolution de systèmes linéaires 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.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.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
Chapitre B. Les bibliothèques 236
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.2 Sous-ensembles à k éléments 5
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.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
Chapitre B. Les bibliothèques 243
B.4 Nombres rationnels 246
B.5 Nombres complexes 247
B.7 Entiers en multiprécision 248
B.8 Arithmétique flottante 249
Index
Errata
Tome 1 :
Page 120, ligne 10, lire "totalement unimodulaire" au lieu de "modulaire".
Tome 2 :
Page 144, ligne -16, lire "EvalueMod" au lieu de "EvalMod".
Prev: Livres
Up: Home Page
Jean-Eric PIN, 5 Octobre 1996