Main

Télécharger au format pdf ou txt
Télécharger au format pdf ou txt
Vous êtes sur la page 1sur 315

Le Livre d’Exo d’Hadrien et Matthieu

Comment ne pas devenir meilleur en maths mais peut-être réussir ses concours.

Hadrien Chalandon-Goskrzynski
Matthieu Boyer
Table des matières

I Exercices de MPSI

1 Raisonnement, Ensembles, Applications et Relations . . . . . . . . . . . . . . . . . . . . . . . . 21

1.1 Raisonnements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.2 Ensembles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.3 Applications et Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.4 Digressions et Exercices Supplémentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

2 Réels, Complexes, Trigonométrie, Sommes et Produits . . . . . . . . . . . . . . . . . . . . . 27

2.1 Compléments sur les Réels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27


2.2 Complexes et Trigonométrie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.3 Sommes et Produits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.4 Digressions et Exercices Supplémentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

3 Fonctions Usuelles : Dérivées, Intégrales, Équations Différentielles . . . . . . . . . . . 29

3.1 Dérivées . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2 Intégrales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.3 Équations Différentielles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

4 Suites, Limites, Continuité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

4.1 Suites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.1.1 Suites Récurrentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.2 Limites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.3 Continuité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

5 Dérivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

5.1 Fonctions Dérivables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33


5.1.1 Quelques Calculs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
5.1.2 Exercices Plus Théoriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
5.2 Convexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
6 Analyse Asymptotique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

6.1 Analyse Asymptotique des Suites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37


6.2 Développements Limités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

7 Structures Algébriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

7.1 Groupes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
7.2 Anneaux et Corps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
7.3 Digressions et Exercices Supplémentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

8 Arithmétique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

8.1 Divisibilité, PGCD, PPCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41


8.2 Nombres premiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
8.3 Digressions et exercices supplémentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

9 Polynômes et Fractions Rationnelles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

9.1 Polynômes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
9.2 Fraction Rationnelles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
9.3 Digressions et Exercices Supplémentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

10 Algèbre Linéaire de Base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

10.1 Sous-Espaces et Applications Linéaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45


10.2 Dimension Finie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

11 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

12 Uniforme Continuité, Intégration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

13 Séries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

14 Déterminants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

14.1 Groupe Symétrique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53


14.2 Déterminants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

15 Espaces Vectoriels Préhilbertiens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

16 Dénombrement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

16.1 Théorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
16.2 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

17 Probabilités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
II Exercices de MP

18 Rappels et Compléments d’Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

18.1 Sous-Ensembles de R . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
18.2 Séries Numériques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

19 Intégrales Généralisées . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

20 Suites et Séries de Fonctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

20.1 Suites de Fonctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69


20.2 Séries de Fonctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

21 Intégrales à Paramètres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

22 Structures Algébriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

22.1 Groupes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
22.2 Anneaux et Corps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
22.2.1 Nombres et Entiers Algébriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
22.3 Digressions et Exercices Supplémentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

23 Topologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

23.1 Topologie des Espaces Vectoriels Normés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77


23.2 Topologie des Espaces Vectoriels Normés de Dimension Finie . . . . . . . . . . . . . . . . . . . 77
23.3 Séries vectorielles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
23.4 Connexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
23.5 Digressions et exercices supplémentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

24 Compléments d’Algèbre Linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

25 Réduction des Endomorphismes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

26 Probabilités de Spé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

26.1 Dénombrabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
26.2 Sommabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
26.3 Variables Aléatoires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
26.4 Séries Génératrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

27 Fonctions Vectorielles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
28 Séries Entières . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

28.1 Séries Génératrices en Dénombrement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

29 Espaces Euclidiens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

29.1 Isométries et Matrices Orthogonales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91


29.2 Endomorphismes Autoadjoints Positifs, Définis Positifs . . . . . . . . . . . . . . . . . . . . . . . . . 91

30 Équations Différentielles Linéaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

31 Calcul Différentiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

31.1 Géométrie Différentielle, un peu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

III Informatique en MP2I/MPI

32 Notions d’Architecture et de Système . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

33 Programmation Fonctionnelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

34 Programmation Impérative . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

35 Analyse des Programmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

35.1 Correction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107


35.2 Terminaison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
35.3 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
35.4 Induction Structurelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

36 Structures de Données . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

36.1 Structures Séquentielles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109


36.2 Structures Hiérarchiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

37 Graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

37.1 Notion et Représentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111


37.2 Algorithmique des Graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

38 Algorithmique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

38.1 Arithmétique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113


38.2 Méthodes Classiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
38.2.1 Algorithmes Gloutons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
38.2.2 Programmation Dynamique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
38.3 Algorithmes sur les Chaînes de Caractère . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
38.4 Algorithmes Probabilités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
38.5 Algorithmique pour l’IA et les Jeux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

39 Logique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

39.1 Logique Propositionnelle et du Premier Ordre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115


39.2 Déduction Naturelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

40 Bases de Données . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

40.1 Théorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117


40.2 SQL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

41 Langages Formels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

41.1 Langages Rationnels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119


41.2 Automates Finis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
41.3 Grammaires Hors-Contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

42 Calculabilité et Décidabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

42.1 Décidabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121


42.2 Classes de Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

43 Concurrence et Synchronisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

IV Astuces de MPSI
1 Raisonnement, Ensembles, Applications et Relations . . . . . . . . . . . . . . . . . . . . . . . 127

1.1 Raisonnements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127


1.2 Ensembles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
1.3 Applications et Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
1.4 Digressions et Exercices Supplémentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127

2 Réels, Complexes, Trigonométrie, Sommes et Produits . . . . . . . . . . . . . . . . . . . . 129

2.1 Compléments sur les Réels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129


2.2 Complexes et Trigonométrie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
2.3 Sommes et Produits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
2.4 Digressions et Exercices Supplémentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129

3 Fonctions Usuelles : Dérivées, Intégrales, Équations Différentielles . . . . . . . . . . 131

3.1 Dérivées . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131


3.2 Intégrales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
3.3 Équations Différentielles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
4 Suites, Limites, Continuité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133

4.1 Suites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133


4.1.1 Suites Récurrentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
4.2 Limites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
4.3 Continuité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133

5 Dérivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135

5.1 Fonctions Dérivables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135


5.1.1 Quelques Calculs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
5.1.2 Exercices Plus Théoriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
5.2 Convexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135

6 Analyse Asymptotique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137

6.1 Analyse Asymptotique des Suites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137


6.2 Développements Limités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137

7 Structures Algébriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139

7.1 Groupes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139


7.2 Anneaux et Corps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
7.3 Digressions et Exercices Supplémentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139

8 Arithmétique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141

8.1 Divisibilité, PGCD, PPCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141


8.2 Nombres premiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
8.3 Digressions et exercices supplémentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141

9 Polynômes et Fractions Rationnelles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143

9.1 Polynômes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143


9.2 Fraction Rationnelles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
9.3 Digressions et Exercices Supplémentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143

10 Algèbre Linéaire de Base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145

10.1 Sous-Espaces et Applications Linéaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145


10.2 Dimension Finie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145

11 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147

12 Uniforme Continuité, Intégration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149

13 Séries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
14 Déterminants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153

14.1 Groupe Symétrique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153


14.2 Déterminants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153

15 Espaces Vectoriels Préhilbertiens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155

16 Dénombrement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157

16.1 Théorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157


16.2 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157

17 Probabilités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159

V Astuces de MP
18 Rappels et Compléments d’Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163

18.1 Sous-Ensembles de R . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163


18.2 Séries Numériques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163

19 Intégrales Généralisées . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165

20 Suites et Séries de Fonctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167

20.1 Suites de Fonctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167


20.2 Séries de Fonctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167

21 Intégrales à Paramètres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169

22 Structures Algébriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171

22.1 Groupes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171


22.2 Anneaux et Corps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
22.2.1 Nombres et Entiers Algébriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
22.3 Digressions et Exercices Supplémentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171

23 Topologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173

23.1 Topologie des Espaces Vectoriels Normés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173


23.2 Topologie des Espaces Vectoriels Normés de Dimension Finie . . . . . . . . . . . . . . . . . . 173
23.3 Séries vectorielles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
23.4 Connexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
23.5 Digressions et exercices supplémentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173

24 Compléments d’Algèbre Linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175


25 Réduction des Endomorphismes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177

26 Probabilités de Spé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179

26.1 Dénombrabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179


26.2 Sommabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
26.3 Variables Aléatoires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
26.4 Séries Génératrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179

27 Fonctions Vectorielles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181

28 Séries Entières . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183

28.1 Séries Génératrices en Dénombrement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183

29 Espaces Euclidiens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185

29.1 Isométries et Matrices Orthogonales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185


29.2 Endomorphismes Autoadjoints Positifs, Définis Positifs . . . . . . . . . . . . . . . . . . . . . . . . 185

30 Équations Différentielles Linéaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187

31 Calcul Différentiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189

31.1 Géométrie Différentielle, un peu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189

VI Astuces d’Informatique en MP2I/MPI

32 Notions d’Architecture et de Système . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193

33 Programmation Fonctionnelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195

34 Programmation Impérative . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197

35 Analyse des Programmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199

35.1 Correction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199


35.2 Terminaison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
35.3 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
35.4 Induction Structurelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199

36 Structures de Données . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201

36.1 Structures Séquentielles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201


36.2 Structures Hiérarchiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
37 Graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203

37.1 Notion et Représentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203


37.2 Algorithmique des Graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203

38 Algorithmique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205

38.1 Arithmétique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205


38.2 Méthodes Classiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
38.2.1 Algorithmes Gloutons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
38.2.2 Programmation Dynamique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
38.3 Algorithmes sur les Chaînes de Caractère . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
38.4 Algorithmes Probabilités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
38.5 Algorithmique pour l’IA et les Jeux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205

39 Logique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207

39.1 Logique Propositionnelle et du Premier Ordre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207


39.2 Déduction Naturelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207

40 Bases de Données . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209

40.1 Théorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209


40.2 SQL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209

41 Langages Formels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211

41.1 Langages Rationnels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211


41.2 Automates Finis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
41.3 Grammaires Hors-Contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211

42 Calculabilité et Décidabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213

42.1 Décidabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213


42.2 Classes de Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213

43 Concurrence et Synchronisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215

VII Corrigés de MPSI

1 Raisonnement, Ensembles, Applications et Relations . . . . . . . . . . . . . . . . . . . . . . . 219

1.1 Raisonnements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219


1.2 Ensembles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
1.3 Applications et Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
1.4 Digressions et Exercices Supplémentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
2 Réels, Complexes, Trigonométrie, Sommes et Produits . . . . . . . . . . . . . . . . . . . . 221

2.1 Compléments sur les Réels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221


2.2 Complexes et Trigonométrie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
2.3 Sommes et Produits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
2.4 Digressions et Exercices Supplémentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221

3 Fonctions Usuelles : Dérivées, Intégrales, Équations Différentielles . . . . . . . . . . 223

3.1 Dérivées . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223


3.2 Intégrales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
3.3 Équations Différentielles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223

4 Suites, Limites, Continuité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225

4.1 Suites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225


4.1.1 Suites Récurrentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
4.2 Limites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
4.3 Continuité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225

5 Dérivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227

5.1 Fonctions Dérivables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227


5.1.1 Quelques Calculs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
5.1.2 Exercices Plus Théoriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
5.2 Convexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227

6 Analyse Asymptotique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229

6.1 Analyse Asymptotique des Suites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229


6.2 Développements Limités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229

7 Structures Algébriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231

7.1 Groupes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231


7.2 Anneaux et Corps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
7.3 Digressions et Exercices Supplémentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231

8 Arithmétique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233

8.1 Divisibilité, PGCD, PPCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233


8.2 Nombres premiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
8.3 Digressions et exercices supplémentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233

9 Polynômes et Fractions Rationnelles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235

9.1 Polynômes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235


9.2 Fraction Rationnelles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
9.3 Digressions et Exercices Supplémentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
10 Algèbre Linéaire de Base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237

10.1 Sous-Espaces et Applications Linéaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237


10.2 Dimension Finie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237

11 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239

12 Uniforme Continuité, Intégration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241

13 Séries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243

14 Déterminants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245

14.1 Groupe Symétrique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245


14.2 Déterminants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245

15 Espaces Vectoriels Préhilbertiens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247

16 Dénombrement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249

16.1 Théorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249


16.2 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249

17 Probabilités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251

VIII Corrigés de MP

18 Rappels et Compléments d’Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255

18.1 Sous-Ensembles de R . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255


18.2 Séries Numériques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255

19 Intégrales Généralisées . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257

20 Suites et Séries de Fonctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259

20.1 Suites de Fonctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259


20.2 Séries de Fonctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259

21 Intégrales à Paramètres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261

22 Structures Algébriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263

22.1 Groupes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263


22.2 Anneaux et Corps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
22.2.1 Nombres et Entiers Algébriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
22.3 Digressions et Exercices Supplémentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263

23 Topologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265

23.1 Topologie des Espaces Vectoriels Normés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265


23.2 Topologie des Espaces Vectoriels Normés de Dimension Finie . . . . . . . . . . . . . . . . . . 265
23.3 Séries vectorielles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
23.4 Connexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
23.5 Digressions et exercices supplémentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265

24 Compléments d’Algèbre Linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267

25 Réduction des Endomorphismes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269

26 Probabilités de Spé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271

26.1 Dénombrabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271


26.2 Sommabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
26.3 Variables Aléatoires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
26.4 Séries Génératrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271

27 Fonctions Vectorielles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273

28 Séries Entières . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275

28.1 Séries Génératrices en Dénombrement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275

29 Espaces Euclidiens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277

29.1 Isométries et Matrices Orthogonales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277


29.2 Endomorphismes Autoadjoints Positifs, Définis Positifs . . . . . . . . . . . . . . . . . . . . . . . . 277

30 Équations Différentielles Linéaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279

31 Calcul Différentiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281

31.1 Géométrie Différentielle, un peu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281

IX Corrigés d’Informatique en MP2I/MPI

32 Notions d’Architecture et de Système . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285

33 Programmation Fonctionnelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287

34 Programmation Impérative . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289


35 Analyse des Programmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291

35.1 Correction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291


35.2 Terminaison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291
35.3 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291
35.4 Induction Structurelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291

36 Structures de Données . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293

36.1 Structures Séquentielles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293


36.2 Structures Hiérarchiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293

37 Graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295

37.1 Notion et Représentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295


37.2 Algorithmique des Graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295

38 Algorithmique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297

38.1 Arithmétique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297


38.2 Méthodes Classiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297
38.2.1 Algorithmes Gloutons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297
38.2.2 Programmation Dynamique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297
38.3 Algorithmes sur les Chaînes de Caractère . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297
38.4 Algorithmes Probabilités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297
38.5 Algorithmique pour l’IA et les Jeux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297

39 Logique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299

39.1 Logique Propositionnelle et du Premier Ordre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299


39.2 Déduction Naturelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299

40 Bases de Données . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301

40.1 Théorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301


40.2 SQL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301

41 Langages Formels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303

41.1 Langages Rationnels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303


41.2 Automates Finis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303
41.3 Grammaires Hors-Contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303

42 Calculabilité et Décidabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305

42.1 Décidabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305


42.2 Classes de Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305
14

43 Concurrence et Synchronisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307

Bibliographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309

Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311
Préface

Avant d’avoir une face, on a une préface. Je crois ? J’ai pas fait de biologie moi !
Le problème c’est que j’utilise cette préface pour update le document réfulièrement. Ça fait que la
préface augmente beaucoup. . . Du coup là je dois obtain main.tex.
Introduction

Ce livre est une collection d’exercices de maths de prépa MPSI-MP/MP*. S’il est conçu pour des
élèves de MPSI et de MP, d’autres filières de prépa peuvent l’utiliser.
Le but du livre est de regrouper un maximum d’exercices intéressants. Des digressions offrant plus
de perspectives sur les maths hors programme de prépa sont insérées dans les sections appropriées.
Ces digressions peuvent procurer du pur plaisir mathématique et (peut-être) servir pour les concours
X-ENS (attention cependant à bien connaître ce qui et ce qui n’est pas au programme pour éviter de
perdre des points en utilisant des résultats hors programme) ou comme inspiration pour un TIPE de
maths.
Les exercices sont regroupés plus par thème que par chapitre (par exemple, les chapitres espaces
vectoriels normés et espaces vectoriels normés de dimension finie sont regroupés dans la section « To-
pologie »).
Certains exercices plus durs ont des astuces (données dans la partie « Astuces ») pour éviter de
regarder directement la correction (ainsi, faire ces exercices se rapproche d’une khôlle ou d’un oral où
l’examinateur donne des pistes de réflexion).
Il est très très vivement conseillé de ne pas regarder la correction (ou les astuces) d’un exercice
avant de l’avoir longuement cherché. Si vous êtes en prépa, votre ou vos prof(s) vous ont probablement
déjà prévenus.
Ce livre suppose le cours de prépa déjà connu et aucun rappel n’est en général fourni. Ce livre
n’est pas non plus un substitut pour des TDs avec un prof en chair et en os. Il est probablement mieux
utilisé pour réviser ou comme supplément de TD.
Si vous êtes prof/TDman/peut-importe comment vous vous désignez, oui, vous pouvez chourrer
des exos d’ici, personne vous jugera.
— Vous avez un exercice que vous pensez qui est bien et vous voudriez le voir ajouté au livre ?
— Vous pensez qu’un exercice est bien trop dur et a besoin d’une astuce ?
— Vous avez trouvé une erreur ?
— Vous avez envie de me traiter de noms d’oiseaux ?
Si vous avez répondu « oui » à au moins 12 question ci-dessus alors contactez moi ! //mettre adresse
mail maths 1

Comment utiliser ce livre


— Les exercices ne sont pas nécessairement à faire dans l’ordre.
— Les exercices comportant une astuce sont marqués d’une étoile (⋆).
— Certains exercices comportent un pictogramme qui désigne un exercice intéressant. Il y a trois
principaux pictogrammes :
— Ș pour les exercices proches du cours : Il suffit d’écrire.
— ƨpour les exercices nécessitant une intuition et illustrant une méthode/idée : Il faut pédaler
un peu, mais on va plus vite et plus loin.
— ίpour les exercices difficiles : La montée est difficile mais la vue vaut le détour.

1. adresse mail maths


18

— Les exercices sont généralement classés par sous-thème puis par difficulté. Par exemple, dans le
chapitre de première année sur les déterminants, les Variations sur Vandermonde sont rangées
par difficulté croissante, mais sont possiblement plus difficiles que des exercices venant après.
— Certains exercices utilisent des résultats d’exercices précédents.
Si l’exercice dont on utilise les résultats n’est pas dans le même chapitre, alors l’exercice utilisé
est soit mentionné dans l’énoncé, soit (s’il n’est pas strictement nécessaire ou jugé retrouvable)
précisé dans la partie « astuces ».
— Il ne sert à rien de tout faire ! Enchaîner les exos sans prendre le temps d’y réfléchir est contre-
productif !
— Il ne sert à rien de regarder les exercices de ce livre sans connaître son cours ! Si certains des
premiers exercices de la plupart des chapitres sont des applications directes du cours et peuvent
aider à mémoriser le cours, les suivants deviendront vite difficiles et parfois impossibles sans
connaître son cours. Ce livre ne remplace pas une bonne connaissance du cours, et n’est qu’un
complément pour aller au delà des cours.
I Exercices de MPSI

1 Raisonnement, Ensembles, Appli- 7.3 Digressions et Exercices Supplémentaires 39


cations et Relations . . . . . . . . . 21
1.1 Raisonnements . . . . . . . . . . . . . . . . . 21 8 Arithmétique . . . . . . . . . . . . . . . 41
1.2 Ensembles . . . . . . . . . . . . . . . . . . . . 22 8.1 Divisibilité, PGCD, PPCM . . . . . . . . . 41
1.3 Applications et Relations . . . . . . . . . . 22 8.2 Nombres premiers . . . . . . . . . . . . . . . 41
1.4 Digressions et Exercices Supplémentaires 24 8.3 Digressions et exercices supplémentaires 41

2 Réels, Complexes, Trigonométrie, 9 Polynômes et Fractions Ration-


Sommes et Produits . . . . . . . . . 27 nelles . . . . . . . . . . . . . . . . . . . . . . 43
2.1 Compléments sur les Réels . . . . . . . . . 27 9.1 Polynômes . . . . . . . . . . . . . . . . . . . . 43
2.2 Complexes et Trigonométrie . . . . . . . . 27 9.2 Fraction Rationnelles . . . . . . . . . . . . . 43
2.3 Sommes et Produits . . . . . . . . . . . . . 27 9.3 Digressions et Exercices Supplémentaires 43
2.4 Digressions et Exercices Supplémentaires 28
10 Algèbre Linéaire de Base . . . . 45
3 Fonctions Usuelles : Dérivées, In- 10.1 Sous-Espaces et Applications Linéaires . 45
tégrales, Équations Différentielles 10.2 Dimension Finie . . . . . . . . . . . . . . . . 45
29
3.1 Dérivées . . . . . . . . . . . . . . . . . . . . . . 29 11 Matrices . . . . . . . . . . . . . . . . . . . 47
3.2 Intégrales . . . . . . . . . . . . . . . . . . . . . 29
3.3 Équations Différentielles . . . . . . . . . . . 29 12 Uniforme Continuité, Intégration
49
4 Suites, Limites, Continuité . . . 31
4.1 Suites . . . . . . . . . . . . . . . . . . . . . . . 31
4.2 Limites . . . . . . . . . . . . . . . . . . . . . . 31
13 Séries . . . . . . . . . . . . . . . . . . . . . . 51
4.3 Continuité . . . . . . . . . . . . . . . . . . . . 31
14 Déterminants . . . . . . . . . . . . . . . 53
5 Dérivation . . . . . . . . . . . . . . . . . . 33 14.1 Groupe Symétrique . . . . . . . . . . . . . . 53
5.1 Fonctions Dérivables . . . . . . . . . . . . . 33 14.2 Déterminants . . . . . . . . . . . . . . . . . . 53
5.2 Convexité . . . . . . . . . . . . . . . . . . . . . 34
15 Espaces Vectoriels Préhilbertiens
6 Analyse Asymptotique . . . . . . . 37 57
6.1 Analyse Asymptotique des Suites . . . . 37
6.2 Développements Limités . . . . . . . . . . . 37 16 Dénombrement . . . . . . . . . . . . . 59
16.1 Théorie . . . . . . . . . . . . . . . . . . . . . . 59
7 Structures Algébriques . . . . . . . 39 16.2 Applications . . . . . . . . . . . . . . . . . . . 59
7.1 Groupes . . . . . . . . . . . . . . . . . . . . . . 39
7.2 Anneaux et Corps . . . . . . . . . . . . . . . 39 17 Probabilités . . . . . . . . . . . . . . . . 61
1. Raisonnement, Ensembles, Applications et
Relations

1.1 Raisonnements

Exercice 1.1 — Ș Montrer que 2 est irrationnel. Généraliser à d’autres nombres.

Exercice 1.2 — Ș Soit n ∈ Z. Montrer que si n2 est impair, n l’est aussi.

Exercice 1.3 — ƨ Soit f : R → R continue telle que

∀(x, y) ∈ R2 , f (x + y) = f (x) + f (y)

1. Montrer que
∃a ∈ R, ∀n ∈ Z, f (n) = an
2. En déduire que
∀r ∈ Q, f (r) = ar
3. Prolonger ce résultat en
∀x ∈ R, f (x) = ax
(il est possible que cette question demande du cours qui n’a pas encore été vu ; si c’est le cas,
attendre le cours sur les nombres réels)

Exercice 1.4 — Ș Montrer que

1 1 1 1
∀n ∈ N∗ , 1 + 2
+ 2 + ··· + 2 ≤ 2 −
2 3 n n

Exercice 1.5 — Ș Intervertir des quantificateurs ?. Soient A et B deux ensembles et P (x, y) un


prédicat dépendant de deux variables x et y avec x ∈ A, y ∈ B. Considérons les deux prédicats

∀x ∈ A, ∃y ∈ B, P (x, y) (1.1)

∃y ∈ B, ∀x ∈ A, P (x, y) (1.2)

A-t-on (1) =⇒ (2) ? A-t-on (2) =⇒ (1) ?

Exercice 1.6 — Ș Soit (un )n∈N une suite réelle.


1. Exprimer à l’aide de quantificateurs les phrases suivantes puis donner leur négation :
a. (un )n∈N est majorée.
22 Chapitre 1. Raisonnement, Ensembles, Applications et Relations

b. (un )n∈N est bornée.


c. (un )n∈N est décroissante.
d. (un )n∈N est monotone.
2. (un peu plus dur mais important) Une sous-suite de (un ) est une suite (uφ(n) ) où φ : N → N
est strictement croissante. Reformuler a. et b. sous la forme « il existe une sous-suite de (un )
qui vérifie P »où P est une propriété.

Exercice 1.7 — Soient R, S, T des propositions. Montrer à l’aide de tables de vérité puis à l’aide de
raisonnement déductif (avec des mots, en décortiquant les formules) que les propositions suivantes
sont vraies :
1. R =⇒ (S =⇒ R).
2. (R =⇒ S) =⇒ ((S =⇒ T ) =⇒ (R =⇒ T ))
3. (R ∨ S) ⇐⇒ ((R =⇒ S) =⇒ S)
4. (R =⇒ (S ∨ T )) ⇐⇒ (S ∨ ¬R ∨ T )
5. (R =⇒ S) =⇒ ((R ∧ T ) =⇒ (S ∧ T ))
6. (R ⇐⇒ S) =⇒ ((T =⇒ R) ⇐⇒ (T =⇒ S))

1.2 Ensembles
Exercice 1.8 — Soient A, B, C, D quatre ensembles. On suppose :
(1) A ⊂ C
(2) B ⊂ D
(3) C ∩ D = ∅
(4) A ∪ B = C ∪ D
Montrer qu’alors A = C et B = D.

Exercice 1.9 — Soit E non vide et A, B ⊂ E. Discuter de l’équation

(A ∩ X) ∪ (B ∩ X) = ∅

Où l’inconnue X est une partie de E et X son complémentaire dans E.

Exercice 1.10 — Soit E un ensemble. On dit que E est transitif si

∀x ∈ E, x ⊂ E

1. Les ensembles suivants sont-ils transitifs ?

E1 = ∅ E2 = {∅} E3 = {∅, {∅}} E4 = {{∅}}

2. Montrer que si E est transitif, E ∪ {E} l’est aussi.


3. Montrer que si E est transitif, P(E) l’est aussi. S T
4. Montrer que si (Ei )i∈I est une famille d’ensembles transitifs, alors i∈I Ei et i∈I Ei le sont
aussi.

Exercice 1.11 — ƨ Théorème de Cantor. Soit E un ensemble. Montrer qu’il n’existe pas de
surjection de E dans P(E).

1.3 Applications et Relations


1.3 Applications et Relations 23

Exercice 1.12 — Ș Soit E un ensemble et A, B ∈ P(E). Soit f : P(E) → P(A) ∩ P(B) .


X 7→ (X ∩ A, X ∩ B)
1. Donner une condition nécessaire et suffisante pour que f soit injective.
2. Même question pour que f soit surjective.

Exercice 1.13 — Ș Lemme SI. Soient E, F, G trois ensembles et f : E → F , g : F → G. Montrer


que :
(i) Si g ◦ f est surjective, g est surjective
(ii) Si g ◦ f est injective, f est injective

Exercice 1.14 — ƨ Soit f : N → N une bijection.


1. Montrer que limn→+∞ f (n) = +∞.
2. Le résultat subsiste-t-il si on suppose seulement f injective ? Surjective ?

Exercice 1.15 — Soient E, F, E ′ , F ′ des ensembles. On se donne u : E ′ → E et v : F → F ′ .



On pose Φ : F E → (F ′ )E .
f 7→ v ◦ f ◦ u
1. Montrer que si u est surjective et v injective, alors Φ est injective.
2. Montrer que si u est injective et v surjective, alors Φ est surjective.
3. Étudier les réciproques.

Exercice 1.16 — Soient E, F deux ensembles et f : E → F .


1. Montrer que f est injective si et seulement si pour tout ensemble G et toutes applications
g, h : G → E, f ◦ g = f ◦ h implique g = h.
2. Montrer que f est surjective si et seulement si pour tout ensemble G et toues applications
g, h : F → G, g ◦ f = h ◦ f implique g = h.

R L’exercice précédent donne une reformulation de l’injectivité et de la surjectivité qui ne fait


pas intervenir les éléments des ensembles. C’est une perspective plus « extérieure ». Ainsi, f
est injective si elle est simplifiable à gauche et surjective si elle est simplifiable à droite. Ce
comportement se généralise par les notions catégoriques de monomorphisme et d’épimorphisme.

Exercice 1.17 — Soit P une fonction polynomiale de R dans R.


1. Montrer que P est surjective si et seulement si deg P est impair.
2. Montrer que si P est injective, alors deg P est impair.
3. La réciproque de 2. est-elle vraie ?

Exercice 1.18 — ƨ Soit R une relation binaire réflexive et transitive sur un ensemble E. On
définit la relation S par xSy si et seulement si xRy et yRx.
Montrer que S est une relation d’équivalence et que R permet de définir une relation d’ordre sur
les classes d’équivalence de S.

■ Vocabulaire 1.1 Une relation binaire réflexive et transitive s’appelle un préordre. L’exercice ci-dessus

justifie l’appellation !

Exercice 1.19 — ƨ Soient X, Y deux ensembles, f : Y → X injective, S une relation d’équivalence


sur Y . On définit une relation R sur X par :

∀x, x′ ∈ X, xRx′ ⇐⇒ (∃(y, y ′ ) ∈ S, f (y) = x, f (y ′ ) = x′ ) ou (x = x′ )


24 Chapitre 1. Raisonnement, Ensembles, Applications et Relations

1. Montrer que R est une relation d’équivalence.


2. Décrire ses classes d’équivalence.

■ Vocabulaire 1.2 Si (E, ≤) est un ensemble ordonné, un élément maximal de E est un élément x de
E tel qu’il n’existe aucun autre élément de E supérieur à lui, ou plus formellement :

x est maximal dans E ⇐⇒ ∀y ∈ E, ¬(x ≤ y)

Exercice 1.20 — 1. Montrer que tout ensemble ordonné fini admet un élément maximal.
2. En déduire que si (E, ≤) est un ensemble ordonné fini de cardinal n, il existe φ : (E, ≤) → [[1, n]]
bijective et croissante.

Exercice 1.21 — Ș Soient X, Y deux ensembles non vides et f : X × Y → R majorée. Montrer :

sup {f (x, y) | (x, y) ∈ X × Y } = sup {sup {f (x, y) | y ∈ Y } | x ∈ X}

Exercice 1.22 — ί Soit σ : N → N une bijection. On pose :

A = {n ∈ N | σ(n) < n} et B = {n ∈ N | σ(n) ≥ n}

Est-il possible que :


(a) A et B soient tous deux finis ?
(b) A et B soient tous deux infinis ?
(c) A soit fini et B soit infini ?
(d) (plus difficile) A soit infini et B soit fini ?

1.4 Digressions et Exercices Supplémentaires


Le but de cet exercice est de démontrer le théorème suivant, dû à Georg Cantor et Sergueï Bern-
stein :
Théorème 1.1 Si E et F sont deux ensembles tels qu’il existe une injection de E dans F et une
injection de F dans E, alors il existe une bijection de E dans F .
■ Vocabulaire 1.3 On dit que deux ensembles sont équipotents si et seulement si ils sont en bijection.

Exercice 1.23 — ί Théorème de Cantor-Bernstein. Soit E et F deux ensembles et i : E → F et


j : F → E deux injections. On note :

A0 = E \ j(F ), An+1 = (j ◦ i) (An ) ∀n ∈ N

et [
B= An , C = E \ B
n≥0

1. Construction de l’Application :
a. Démontrer que si x ∈ C, il existe un unique z ∈ F tel que x = j(z). On notera φ(x) cet
élément.
b. Pour x ∈ B, on note φ(x) = i(x). Démontrer que l’on a ainsi bien défini une application
φ de E dans F .
2. Injectivité :
a. Démontrer que les restrictions de φ à B et C sont injectives.
b. Considérons x ∈ C et y ∈ B tels que φ(x) = φ(y). Démontrer que x = (j ◦ i) (y).
1.4 Digressions et Exercices Supplémentaires 25

c. Conclure sur l’injectivité de φ.


3. Surjectivité : Démontrer que φ est surjective.
4. Des exemples :
a. En utilisant le théorème de Cantor-Bernstein, montrer que N et Z sont équipotents.
b. On introduit l’application

ψ: N2 → N
(p, q) 7→ 2p (2q + 1)

i. Montrer que N est équipotent à N2 .


ii. En déduire que pour tout d ≥ 1, N et Nd sont équipotents.
iii. Peut-on en déduire que N est en bijection avec NN ? Et avec l’ensemble N(N) des
suites nulles à partir d’un certain rang ?
c. On s’intéresse désormais aux nombres rationnels.
i. Exhiber une injection de Q dans Z × N∗
ii. En déduire que Q est équipotent à N.
2. Réels, Complexes, Trigonométrie, Sommes et
Produits

2.1 Compléments sur les Réels


2.2 Complexes et Trigonométrie

Exercice 2.1 — Soit θ ∈]0, π[. Simplifier 1+e
1−eiθ
.

Exercice
π
 2.2 —
π
Ș Calculer de deux façons les racines carrées de 1 + i. En déduire les valeurs de
cos 8 et sin 8 .

Exercice 2.3 — Ș Trouver tous les z ∈ C tels que z, z1 et z − 1 aient le même module.

Exercice 2.4 — Ș Résoudre, pour n ∈ N, l’équation z n = z.

Exercice 2.5 — ƨ Soit z ∈ U. Calculer |z − 1|2 + |z + 1|2 et interpréter géométriquement.

π
 
Exercice 2.6 — En exprimant 12 en fonction de π3 et π4 , trouver les valeurs de cos 12
π π
et sin 12 .

Exercice 2.7 — Déterminer sans étude de fonction le maximum de x 7→ sin(x) cos(x) sur R.

Exercice 2.8 — Résoudre dans [0, 2π] l’équation cos(2x) + cos(x) = 0.

Exercice 2.9 — Ș 1. Donner la définition de l’argument d’un nombre complexe non nul.
2. Soit n ∈ N∗ .
Donner, en justifiant, les solutions de l’équation z n = 1 dans C.
3. En déduire, pour n ∈ N∗ , les solutions dans C de l’équation (z + i)n = (z − i)n et démontrer
que ce sont des nombres réels.

2.3 Sommes et Produits


Exercice 2.10 — En l’écrivant sous la forme d’une somme, montrer que 0, 999999... = 1.

Exercice 2.11 — Calculs de somme doubles. Calculer :


28 Chapitre 2. Réels, Complexes, Trigonométrie, Sommes et Produits

X
n X
n X
n X
n
i X
n X
n
i+j
1. 1 4. 7.
j j
i=0 j=0 i=0 j=i i=0 j=i
Xn X n Xn X n
i2 Xn X n
(i + j)2
2. (j − i) 5. 8.
j j
i=0 j=0 i=0 j=i i=0 j=i
Xn X n Xn X n Xn X n  
j
3. (j − i) 6. min{i, j} 9.
i
i=0 j=i i=0 j=0 i=0 j=i

Exercice 2.12 — Calculs de produits. Calculer :

Y
n n 
Y  Yn
1 k+2
1. (2k) 3. 1− 5.
k k
k=1 k=2 k=1
Yn Yn Yn
2. (2k + 1) 4. (k(n + 1 − k)) 6. (4k 2 − 1)
k=1 k=1 k=1

Y
n a
Exercice 2.13 — Calculer cos où a ∈]0, 2π[.
2k
k=1

Exercice 2.14 — ƨ Soit


X EXun ensemble de cardinal n.
1. En considérant 1, calculer :
X∈P(E) x∈X X
|X|
X∈P(E)

2. Appliquer la même méthode pour calculer :


X
|X ∩ Y |
(X,Y )∈P(E)2


Exercice 2.15 — Soit (un )n∈N∗ ∈ (R+∗ )N une suite telle que
!2
X
n X
n

∀n ∈ N , u3k = uk
k=1 k=1

Déterminer (un ).

Exercice 2.16 — 1. Rappeler l’expression de tan(a − b) pour a, b ∈ R avec a − b 6≡ π


2 [π].
2. Calculer  
X
n
1
arctan 2
k +k+1
k=0

2.4 Digressions et Exercices Supplémentaires


3. Fonctions Usuelles : Dérivées, Intégrales,
Équations Différentielles

3.1 Dérivées
3.2 Intégrales
3.3 Équations Différentielles
4. Suites, Limites, Continuité

4.1 Suites
Exercice 4.1 — Ș Soit u une suite réelle monotone admettant une sous-suite convergente. Montrer
que u converge.

Exercice 4.2 — ƨ Lemme des pics. Soit u ∈ RN . On pose E = {n ∈ N | ∀k ≥ n, uk ≤ un }.


1. Montrer que si E est infini, u possède une sous-suite décroissante.
2. Montrer que si E est fini, u possède une sous-suite croissante.
3. En déduire le théorème de Bolzano-Weierstrass.

4.1.1 Suites Récurrentes


4.2 Limites
4.3 Continuité
5. Dérivation

5.1 Fonctions Dérivables


5.1.1 Quelques Calculs
Exercice 5.1 — Ș Calcul. Calculer les dérivées des fonctions suivantes :

1. f (x) = x+1 26. f (x) = 3x5/4


x−1  
2. f (x) = 5x2 − 3 x2 + x + 4 27. f (x) = 54 x2/3
3. f (x) = x55 28. f (x) = −4x−5
4. f (x) = x55 + x32 29. f (x) = x33

5. f (x) = √1x 30. f (x) = −2 4 x
√ √
6. f (x) = 1
√ 31. f (x) = 3 x + 5 x

x
3
x
√ 32. f (x) = 4x4x−3x
3
5 −4
2

7. f (x) = x2
+ x
4 33. f (x) = 3x4 +2
8. f (x) = x2 + 3x − 2 3x3 −2
√ 4x5 +2x2
4
9. f (x) = q x5 − x3 − 2 34. f (x) = 3x4 +5
4x4 −4x2 +5
2
10. f (x) = 3 xx2 +1 35. f (x) =
−1

2x5/3 +3 
36. f (x) = arccos −5x3
11. f (x) = 10 x
2 37. f (x) = arcsin −2x2
12. f (x) = e3−x
2x 38. f (x) = arctan 2x4
13. f (x) = ex2 3
2√ 39. f (x) = arcsin 5x2
14. f (x) = 32x x  3
15. f (x) = ln 2x4 −x3 + 3x2 − 3x 40. f (x) = arcsin 3x5 + 1
2
ex +1 41. f (x) = arccos 4x2
16. f (x) = ln ex −1 3
q 42. f (x) = arccos −2x3 − 3
1+x
17. f (x) = ln 43. f (x) = ln ln 2x4
p 1−x
18. f (x) = ln qx (1 − x) 44. f (x) = ln ln 3x3
3x
19. f (x) = ln 3 x+2 45. f (x) = cos ln 4x3
3x2
(x−2) 3 46. f (x) = ee
20. f (x) = ln √ 3 2
2x−1 47. f (x) = e(4x +5) 
21. f (x) = sin 2x3 48. f (x) = ln 4x2 −x3 − 4
22. f (x) = tan x5   5
 4
23. f (x) = 2x5 + 3 cos x2 49. f (x) = ln − x4x
3 −3

−2x2 −5 e5x
4
24. f (x) = cos(2x 50. f (x) =

3)
3 e4x2 +3
25. f (x) = sin x5

Exercice 5.2 — Ș Déterminer les limites des expressions suivantes :


34 Chapitre 5. Dérivation

1. ch(x)
en +∞. 6. e3x ch3 (x) − sh3 (x) en −∞.
x
2. ch(x) 7. arcsin (th(x))
 en +∞
ex en +∞.
sh(x) 8. tan π2 th(x) en −∞
3. en +∞.
e2x +1 9. xx en 0
arctan(x) ch3 (x) x
4. e3x −2e2x +4
en +∞ 10. xx en 0.
th(x)
5. e−x +3
en −∞

Exercice 5.3 — Ș Dresser le tableau de variations de chacun des fonctions suivantes :

1. x 7→ ln (ex − x) − x 3. x 7→ x2 +4x+1
2x ex
2. x →7 2x − 3ex + e2 4. x 7→ (x+3)e2x
(x+2)3

Exercice 5.4 — Ș Préparation à Gamma. Après avoir justifié son existence, calculer la dérivée
n-ème de x 7→ tx et−1 .

5.1.2 Exercices Plus Théoriques


Exercice 5.5 — Ș Soit M : f, g ∈ C 1 (x0 ) 7−→ (x 7→ max f (x), g(x)). Quel est le type de la fonction
M ? C’est-à-dire, dans quel ensemble se situe son image ? Le vérifier en utilisant l’expression de la
valeur absolue comme maximum de deux réels.

Exercice 5.6 — Ș Dérivation et Caractère Lipschitzien. 1. Montrer qu’une application réelle dé-
rivable est lipschitzienne si et seulement si sa dérivée est bornée sur R.
2. Montrer que toute application C 1 sur un segment de R est lipschitzienne sur S.

Les deux exercices qui suivent illustrent le fait que f ′ contrôle f et non l’inverse.

Exercice 5.7 — Soient λ ∈ R, f une fonction dérivable de R+ dans R telle que :

f ′ (x) −−−−→ λ
x→+∞

Montrer que :
f (x)
−−−−→ λ
x x→+∞
On pourra commencer par le cas où f est de classe C 1

Exercice 5.8 — Soit f une fonction dérivable de R+ dans R, bornée sur R+ et telle que f (0) = 0.
Montrer qu’il existe C > 0 tel que :

∀x ∈ R+ , |f (x)| ≤ Cx.

Exercice 5.9 — Donner un exemple de fonction f de classe C 1 sur R+ , à valeurs dans R, admettant
une limite en +∞, mais telle que f ′ ne tende pas vers 0 en +∞.

5.2 Convexité
Exercice 5.10 — Ș Inégalités. Prouver, d’abord par l’étude de fonctions, puis par des arguments
5.2 Convexité 35

de convexité, les inégalités ci-dessous :


1. ∀x ∈ R, ex ≥ x + 1
2. ∀x ∈ R∗+ , ln x ≤ x − 1
h π i 2x
3. ∀x ∈ , , ≤ sin x ≤ x
2 π
4. Inégalité de Young : Pour p ∈ ]1, +∞[ , q ∈ R tel que
1 1
+ =1
p q
a et b dans R∗+ , on a :
a p bq
ab ≤ +
p q
6. Analyse Asymptotique

6.1 Analyse Asymptotique des Suites


6.2 Développements Limités
7. Structures Algébriques

7.1 Groupes
7.2 Anneaux et Corps
7.3 Digressions et Exercices Supplémentaires
8. Arithmétique

8.1 Divisibilité, PGCD, PPCM


8.2 Nombres premiers
8.3 Digressions et exercices supplémentaires
9. Polynômes et Fractions Rationnelles

9.1 Polynômes
9.2 Fraction Rationnelles
9.3 Digressions et Exercices Supplémentaires
10. Algèbre Linéaire de Base

10.1 Sous-Espaces et Applications Linéaires


10.2 Dimension Finie
11. Matrices

 
1 1
Exercice 11.1 — Ș Soit A = .
1 1
1. Calculer A pour tout n ∈ N.
n

2. Peut-on généraliser ceci pour n ≤ 0 ?


3. Généraliser ceci dans le cas où Ap est la matrice p × p remplie de 1.

R D’après Wikipédia, Attila, né peut-être vers 395-400 dans les plaines du Danube et mort en mars
453 dans la région de la Tisza dans l’Est de la Hongrie actuelle, fréquemment appelé Attila le Hun,
est le souverain des Huns de 434 jusqu’à sa mort en mars 453. Le lecteur attentif aura compris le
rapport avec l’exercice précédent.
■ Notation 11.1 La matrice Ap est parfois appelée J.

 
3 −2
Exercice 11.2 — Ș On considère A =
2 −1
2
1. Exprimer A en fonction de A et de I2
2. Déterminer An pour tout n ∈ N. On exprimera notamment le résultat en fonction de A et de
I2 .
3. La formule précédente est-elle valable pour n ≤ 0 ?

 
3 1
Exercice 11.3 — ƨ Fibonacci. On considère A = . On rappelle que la suite de Fibonacci
−5 2
(Fn ) est déterminée par :

F0 = 0, F1 = 1, ∀n ∈ N, Fn+2 = Fn+1 + Fn

1. Comment peut-on définir F−1 pour que la relation soit correcte ?


2. Montrer que pour tout n ∈ N, An = Fn A + Fn−1 I2 .
3. Montrer que A est inversible, et déterminer A−1 en fonction de A et de I2 . En déduire An
pour n ∈ Z.
12. Uniforme Continuité, Intégration
13. Séries

Dans les deux exercices suivants, on va chercher à prouver le Théorème de Réarrangement de Rie-
mann. La preuve étant difficile, on en donne deux squelettes, l’un légèrement plus simple que l’autre.

On considère dans la suite des séries dites semi-convergentes :


P
Définition 13.1 Une série an est dite semi-convergente si elle est convergente mais pas absolument
convergente.

On a alors le théorème suivant :


P
Théorème 13.1 — de Réarrangement de Riemann Soit an une série réelle semi-convergente et
X
+∞
α ∈ R. Il existe alors σ ∈ S (N) telle que aσ(n) = α.
P n=0
Autrement dit, l’ensemble aσ(n) | σ ∈ S(N) est dense dans R.

Exercice 13.1 — ί ίίThéorème de Réarrangement, Difficile. Démontrer le théorème.

Exercice 13.2 — ί Théorème de Réarrangement, cas fini, difficile mais faisable. On pose E + =
{n ∈ N | an ≥ 0} et E − = N \ E + .
1. Montrer que E − et E + sont infinis.
Pn σ : N → N de la manière suivante +: σ(0) = 0 et pour σ(0), . . . , σ(n) construits,
On construit
— Si Pk=0 aσ(k) < α, alors σ(n + 1) = inf E \ {σ(0), . . . , σ(n)}
— Si nk=0 aσ(k) ≥ α, alors σ(n + 1) = inf E − \ {σ(0), . . . , σ(n)}
2. Justifier que σP est une bijection.
On pose alors Sn = nk=0 aσ(k) pour n ≥ 0. On fixe ε > 0.
3. Montrer qu’il existe un entier N tel que :
— N ∈ E + et N + 1 ∈ E − .
— ∀n ≥ N, aσ(n) ≤ ε
4. Montrer que si n ≥ N , |Sn − α| ≤ ε
5. Conclure.
14. Déterminants

14.1 Groupe Symétrique


Exercice 14.1 — Ș Soit E un ensemble fini. Soit f : E → E une involution (c’est-à-dire f ◦ f =
IdE ). On pose P = {x ∈ E | f (x) = x}. Montrer que Card(P ) ≡ Card(E) [2].

14.2 Déterminants
Exercice 14.2 — ί Formule de Miller a . Soit A ∈ Mn (K) telle que a(1,1) 6= 0. Montrer que
!
1 a1,1 a1,j
det A = det
an−2
1,1
ai,1 ai,j i,j=2,...,n

En déduire que le déterminant d’une matrice de taille n à coefficients dans {−1, 1} est divisible par
2n−1 .
a. Ou comment illustrer une idée géniale

R Cette formule a un grand avantage sur le développement selon une ligne ou une colonne. D’une
part sa complexité est moindre : On calcule

X
n−1
n(n − 1)(n − 2)
i2 = 6 ≤ n3 3
i=1
/

déterminants d’ordre 2 au lieu de n!. D’autre part, calculer un déterminant de la sorte est, pour
le cas général, bien plus agréable à faire et à présenter que d’écrire tous les cofacteurs.

Exercice 14.3 — Ș Le Déterminant n’est PAS linéaire.. 1. Trouver toutes les matrices A de Mn
telles que :
∀M ∈ Mn , det (A + M ) = det A + det M
2. En déduire que si det(A + M ) = det(B + M ) pour toute matrice M , alors A = B.

Exercice 14.4 — ƨ Soit A et B deux matrices réelles qui commutent.


1. Donner une condition nécessaire et suffisante sur det(A + B) pour avoir det(Ap + B p ) ≥ 0
pour tout entier p ≥ 1.
2. Peut-on modifier cette condition en remplaçant ≥ 0 par > 0 ?

Exercice 14.5 — Ș Soient A, B, C, D quatres matrices carrées de même dimension.


54 Chapitre 14. Déterminants

1. Montrer que, si A ou D est inversible et commute avec C, on peut écrire :

A B
= det(AD − BC)
C D

On cherchera pour cela à multiplier la grosse matrice pour obtenir une matrice triangulaire
par blocs.
2. La formule reste-t-elle valable si A et D ne sont plus supposées inversibles ?
3. Et si C ne veut plus commuter ?

L’exercice suivant utilise une partie du programme de deuxième année sur la théorie des groupes.

Exercice 14.6 — ί Formule de Williamsom. Soit (Ai,j )1≤i,j≤n une famille de matrice carrées
commutant deux à deux. Montrer que
!
X Y
n
det (Ai,j ) = det ε(σ) Ai,σ(i)
σ∈Sn i=1

Exercice 14.7 — Un lemme inutile illustrant une idée encore plus géniale. Pour une matrice A ∈ Mn
et I une partie de {1, . . . , n}, on notera AI la matrice extraite (ai,j )i,j∈I . Montrer que la quantité
P
|I|=k det AI est invariante par conjugaison.
On pourra pour cela remarquer que :

1 0
det A =
0 A

Exercice 14.8 — ί Comatrice d’un Produit. Soit R un anneau de caractéristique différente de 2.


Montrer que Com(AB) = ComAComB. Avant d’aborder le cas général, on traitera successivement
les cas suivants :
1. R est le corps des réels ou des complexes.
2. R est un corps quelconque.
3. R est un anneau intègre.

Exercice 14.9 — ί Formule de Cauchy-Binet. Pour une matrice A et deux p-uplets d’indices
i1 < i2 < · · · < ip et k1 < k2 < · · · < kp , on note A ki11ki22...i...kp
p
le mineur de A obtenu en prenant les
lignes i1 , . . . , ip et les colonnes k1 , . . . , kp .
Soit A ∈ Mn,m (K), B ∈ Mm,n (K) et C = AB. Montrer que si n > m, alors det C = 0. Montrer
sinon que :    
X k1 k2 . . . k n 12 . . . n
det C = A B
12 . . . n k1 k2 . . . k n
1≤k1 <k2 <...<kn ≤m

Exercice 14.10 — ƨ Déterminant d’Hurwitz — Variation sur Vandemonde 1. Soit a, b, x1 , . . . , xn≥1


14.2 Déterminants 55

des scalaires sur un corps K. On veut évaluer :

x1 a ··· ··· a
.. ..
b x2 . .
.. .. .. .. .. = D
. . . . . a,b
.. ..
. . xn−1 a
b ··· ··· b xn

Y
n
On pose P = (xi − X).
i=1
1. On suppose tout d’abord a 6= b. En rajoutant un x à chaque coordonée, considérer D comme
un polynôme en x de degré 1 et montrer que :

bP (a) − aP (b)
Da̸=b =
b−a
2. Dans le cas a = b, se placer dans le corps des fractions rationnelles sur K pour obtenir :

Da,a =P (a) − aP ′ (a)


 X 
a
=P (a) 1 −
xi − a

Exercice 14.11 — ƨ Déterminant de Cauchy — Variation sur Vandermonde 2. Soient ⃗a, ⃗b une
famille
 de2n scalaires tels que ai + bj n’est jamais nul. Calculer le déterminant dit de Cauchy
1
de ai +b j
de deux manières différentes, par le calcul direct et en utilisant des fractions
1≤i,j≤n
rationnelles.

Exercice 14.12 — Variation sur Vandermonde 3. Soient α1 < · · · < αn des réels strictement positifs
et a1 , . . . , an des réels non tous nuls.
1. Montrer que la fonction définie par f (x) = a1 xα1 + · · · + an xαn admet au plus n − 1 zéros
distincts dans R∗+
2. Soient t1 , . . . , tn des réels tels que 0 < t1 < · · · < tn . Montrer que le déterminant de la matrice
α
des ti j est strictement positif.

Exercice 14.13 — Variation sur Vandermonde


 4. Soit i1 , i2 , . . . , ik dans N∗ et n = i1 +· · ·+ik . Pour x ∈
R, on note C(x) = 1, x, x2 , . . . , xn−1 . On se donne x1 , . . . , xk dans R et on considère la matrice M
′ (i−1) ′ (ik −1)
(x1 )
dont les lignes successives sont C (x1 ) , C 1! (x1 )
, . . . , C (i1 −1)! , . . . , C(xk ), C (xk)
1! , . . . ,
C (xk )
(ik −1)! . Cal-
culer son déterminant.

Exercice 14.14 — Soit A, B dans Mn (R) et X un vecteur non nul de Rn . On suppose que AX = 0
et qu’il existe Y ∈ Rn tel que AY = BX. P
On note Aj la matrice obtenue en remplaçant la j-ième
colonne de A par celle de B. Montrer que nj=1 det Aj = 0.
56 Chapitre 14. Déterminants

Exercice 14.15 — ƨ Matrice Circulante. Soit p premier et (a0 , a1 , . . . , ap−1 ) ∈ Zp . Montrer que :

a0 a1 a2 · · · ap−1
ap−1 a0 a1 · · · ap−2
ap−2 ap−1 a0 · · · ap−3 ∼
= a0 + a1 + · · · + ap−1 mod p
.. .. ..
. . .
a1 a2 a3 · · · a0

Exercice 14.16 — ί Déterminant de Smith. En notant di,j le nombre de diviseurs communs à i


et j, calculer les déterminants des matrices (di,j )1≤i,j≤n et (i ∧ j)1≤i,j≤n . On pourra introduire ap,q
qui vaut 1 si q | p et 0 sinon.

Exercice 14.17 — Soit A1 , . . . , Ap des parties distinctes de {1, . . . , n} telles que l’intersection de
deux quelconques distinctes soit de cardinal c > 0 fixé. Montrer que p ≤ n.
On pourra introduire la matrice d’incidence A définie par ai,j = 1Aj (i) et s’intéresser à tAA.

Les deux exercices qui suivent nécessitent de connaître le cours sur les espaces préhilbertiens et la
notion de matrice de Gram, présentée dans le chapitre associé.
■ Notation 14.1 On notera G(x1 , . . . , xn ) le déterminant de MG (x1 , . . . , xn ) ou MG est la matrice de
Gram.

Exercice 14.18 — Soit n ∈ N∗ . Montrer que, si F est un sous-espace vectoriel d’un espace euclidien
E, muni d’une base (e1 , · · · , en ), on a :

G(e1 , . . . , en , x)
d(x, F )2 =
G(e1 , . . . , en )

Définition 14.1 Si (x1 , . . . , xn ) est une famille libre, on définit le parallélotope engendré par les
vecteurs x1 , . . . , xn par :
( )
X
n
n
P(x1 , . . . , xn ) = ti xi (t1 , . . . , tn ) ∈ [0, 1]
i=1

Si C est une base orthonormée de Vect(x1 , . . . , xn ), on définit le volume du parallélotope comme :

Vol (P(x1 , . . . , xn )) = det(x1 , . . . , xn )


C

Exercice 14.19 — ƨ Volume d’un Parallélotope. Montrer que la définition du volume d’un parallélo-
tope ne dépend pas de la base orthonormée choisie. Montrer de plus que le volume du parallélotope
engendré par une famille libre est la racine carrée du déterminant de Gram de cette famille.
15. Espaces Vectoriels Préhilbertiens

Définition 15.1 On définit la matrice de Gram des vecteurs x1 , . . . , xn notée MG (x1 , . . . , xn ) par
 
hx1 , x1 i hx1 , x2 i · · · hx1 , xn i
 hx2 , x1 i hx2 , x2 i · · · hx2 , xn i 
 
MG (x1 , . . . , xn ) =  .. .. .. 
 . . . 
hxn , x1 i hxn , x2 i · · · hxn , xn i

Exercice 15.1 — ί Rang de la Matrice de Gram. Montrer que

rg (MG (x1 , . . . , xn )) = rg(x1 , . . . , xn )


16. Dénombrement

16.1 Théorie
16.2 Applications
Exercice 16.1 — Ș Soient n ∈ N∗ , E un ensemble de cardinal n et P(E) l’ensemble des parties
de E.
1. Déterminer le nombre de couples (A, B) ∈ P(E)2 tels que A ⊆ B.
2. Déterminer le nombre de couples (A, B) ∈ P(E)2 tels que A ∩ B = ∅.
3. Déterminer le nombre de triplets (A, B, C) ∈ P(E)3 tels que A ∪ B ∪ C = E avec A, B, C
disjoints.

Exercice 16.2 — ί On considère 1000 points du plan R2 . On veut montrer qu’il existe une droite
ayant au sens strict, 500 points d’un côté et 500 points de l’autre. On va procéder de deux manières :
1. Par dénombrement : On note Dm,p la droite d’équation y = mx + p dans le repère orthonormé
direct canonique. On note M l’ensemble des 1000 points.
a. Montrer que l’ensemble des réels m tels qu’il existe p ∈ R tel que |Dm,p ∩ M| ≥ 2 est
fini.
b. Quel est le plus petit cardinal possible de l’ensemble précédent ? Quel est son plus grand
cardinal possible ?
Indication : e est transcendant sur Q, c’est à dire qu’il n’existe pas P ∈ Q[X] dont e est
racine.
c. Etablir l’existence de m0 ∈ R tel que φ : R → N qui à p associe |Dm0 ,p ∩ M| soit à
valeurs dans {0, 1}.
d. Conclure
2. Algébriquement : En étudiant un repère adapté du plan, retrouver le résultat.
17. Probabilités

Exercice 17.1 — ƨ 1. Soit X la variable aléatoire donnant le nombre de points fixes d’une
permutation. Calculer l’espérance et la variance de X. On pourra noter pour i dans {1, . . . , n}
Xi la variable aléatoire de Bernoulli indicatrice de l’évènement « i est point fixe de σ ».
2. Soit Y la variable aléatoire donnant la longueur du cycle contenant 1 dans la décomposition
canonique d’une permutation. Quelle est la loi de Y ?
3. Soit Z la variable aléatoire donnant le nombre de cycles dans la décomposition canonique
d’une permutation. Si t est un réel, montrer que :

 1 Y
n
E t 2
= (t + k)
n!
k=1

En déduire l’espérance et la variance de Z.

Exercice 17.2 — Soit (Xi,j )1≤i,j≤n une famille de variables aléatoires centrées réduites mutuelle-
ment indépendantes.
1. Calculer l’espérance et la variance de la variable aléatoire D, égale au déterminant de la
matrice (Xi,j )1≤i,j≤n .
2. Si A > 0, montrer que  √  1
P |D| ≥ A n! ≤ 2
A
II 18
Exercices de MP

Rappels et Compléments d’Analyse . . . . 65


18.1 Sous-Ensembles de R . . . . . . . . . . . . . . . . . . . . . . . 65
18.2 Séries Numériques . . . . . . . . . . . . . . . . . . . . . . . . . 66

19 Intégrales Généralisées . . . . . . . . . . . . . . . 67

20 Suites et Séries de Fonctions . . . . . . . . . . 69


20.1 Suites de Fonctions . . . . . . . . . . . . . . . . . . . . . . . . 69
20.2 Séries de Fonctions . . . . . . . . . . . . . . . . . . . . . . . . 69

21 Intégrales à Paramètres . . . . . . . . . . . . . . . 71

22 Structures Algébriques . . . . . . . . . . . . . . . . 73
22.1 Groupes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
22.2 Anneaux et Corps . . . . . . . . . . . . . . . . . . . . . . . . . 74
22.3 Digressions et Exercices Supplémentaires . . . . . . . . . 74

23 Topologie . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
23.1 Topologie des Espaces Vectoriels Normés . . . . . . . . . 77
23.2 Topologie des Espaces Vectoriels Normés de Dimension Fi-
nie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
23.3 Séries vectorielles . . . . . . . . . . . . . . . . . . . . . . . . . 77
23.4 Connexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
23.5 Digressions et exercices supplémentaires . . . . . . . . . . 78

24 Compléments d’Algèbre Linéaire . . . . . . . 79

25 Réduction des Endomorphismes . . . . . . . 81

26 Probabilités de Spé . . . . . . . . . . . . . . . . . . 83
26.1 Dénombrabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
26.2 Sommabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
26.3 Variables Aléatoires . . . . . . . . . . . . . . . . . . . . . . . . 84
26.4 Séries Génératrices . . . . . . . . . . . . . . . . . . . . . . . . 84

27 Fonctions Vectorielles . . . . . . . . . . . . . . . . 87

28 Séries Entières . . . . . . . . . . . . . . . . . . . . . . . 89
28.1 Séries Génératrices en Dénombrement . . . . . . . . . . . 89

29 Espaces Euclidiens . . . . . . . . . . . . . . . . . . . 91
29.1 Isométries et Matrices Orthogonales . . . . . . . . . . . . 91
29.2 Endomorphismes Autoadjoints Positifs, Définis Positifs 91

30 Équations Différentielles Linéaires . . . . . 93

31 Calcul Différentiel . . . . . . . . . . . . . . . . . . . . 95
31.1 Géométrie Différentielle, un peu . . . . . . . . . . . . . . . 95
18. Rappels et Compléments d’Analyse

Exercice 18.1 — ƨ Notion de Limite Supérieure. Soit (un ) une suite réelle. On définit :

lim sup un = lim sup{uk | k ≥ n}


n→+∞

1. Justifier que lim sup un existe dans R.n


2. Calculer lim sup(−1)n et lim sup (−1)
n .
3. On suppose que lim sup un ∈ R. Montrer que c’est la plus grande valeur d’adhérence de (un ).

■ Vocabulaire 18.1 On peut définir de même un opérateur lim inf :

lim inf un = lim inf {uk |k ≥ n}


n→+∞

C’est la plus petite valeur d’adhérence d’une suite.


■ Notation 18.1 On rencontre parfois la notation lim pour la limite supérieure et lim pour la limite
inférieure.

Exercice 18.2 — Pour n ∈ N∗ , on pose σ(n) la somme des diviseurs de n. Montrer que pour
n∈ N∗ , σ(n) ≤ n(ln(n) + 1).

On rappelle d’abord le théorème de Cesàro 1 :

Théorème 18.1 — Cesàro Si un −−−→ l ∈ R, alors


n→∞

1X
n
Sn = uk −−−→ l
n n→∞
k=1

Exercice 18.3 — La réciproque du lemme de Cesàro est-elle vraie ?


La réciproque est-elle vraie pour une suite monotone ?
Supposons que (un ) ∈ RN vérifie
 
1 X
n
1
uk −−−−−→ ℓ ∈ R et un+1 − un = o
n+1 n→+∞ n
k=0

Montrer que un −−−−−→ ℓ.


n→+∞

18.1 Sous-Ensembles de R
On replace cet exercice classique ici :
1. Qui n’était pas au programme de MP de mon temps
66 Chapitre 18. Rappels et Compléments d’Analyse

Exercice 18.4 — ƨ Groupes Additifs. Soit G ⊂ R un sous-groupe de (R, +). Montrer que ou bien
G est de la forme aZ avec a ∈ R, ou bien G est dense dans R.

De ce résultat utile découlent quelques applications :

Exercice 18.5 — Classification des Treillis. Soit H = aZ + bZ avec (a, b) ∈ R × R∗ . Montrer que H
est dense dans R si et seulement si a
b ∈
/ Q.


Exercice 18.6 — Que dire d’une fonction continue f : R → R admettant 1 et 2 comme périodes ?

Exercice 18.7 — Caractériser les sous-groupes de (U, ×).

18.2 Séries Numériques


Pn p.
Exercice 18.8 — Donner un équivalent simple quand n tend vers +∞ de p=1 p

Exercice 18.9 — ƨ Théorème de Pringsheim. Soit (un ) une  suite de réels strictement positifs
P
décroissante telle que un converge. Montrer que un = o n1 . Le résultat subsiste-t-il si (un ) n’est
plus supposée décroissante ?

Exercice 18.10 — ƨ Critère de D’Alembert. Soit (un )n∈N une suite de réels strictement positifs et
l un réel positif strictement inférieur à 1. P
1. Démontrer que si limn→∞ uun+1 n P
= l alors la série un converge.
n!
2. Quelle est la nature de la série nn ?

X
+∞
1
Exercice 18.11 — Donner un développement asymptotique à l’ordre 4 de .
k2
k=n+1

N
Exercice 18.12 — ƨίOral Ulm. Soit α ∈ C, d ∈ R∗+ . On se donne zn ∈ (C∗ ) telle que ∀m 6=
X
+∞
n, |zm − zn | > d. Étudier la nature de zn−α . On portera particulièrement attention aux cas où
n=0
<α > 2.
19. Intégrales Généralisées

Z +∞
ln(x)
Exercice 19.1 — Ș Étudier l’existence de dx.
0 x2 − 1

Z +∞
Exercice 19.2 — Ș Donner la nature de l’intégrale cos(ex ) dx.
0

Z +∞
Exercice 19.3 — Ș Déterminer la nature de cos(t2 + t) dt.
0
1
Indication : écrire cos(t2 + t) = (2t + 1) cos(t2 + t) 2t+1 pour t ∈ R+ .

Z +∞
2
Exercice 19.4 — Ș Montrer que eix dx converge.
0

Z +∞  x
1
Exercice 19.5 — Ș Nature de e− 1+ dx.
1 x

Z Z
e−x
+∞ +∞ 2
ln(x)
Exercice 19.6 — Ș Déterminer la nature de dx et de p dx.
0 1 + ex −∞ |x|

Exercice 19.7 — Montrer l’équivalent


Z 1
1 1
dx ∼
0 x3 +a 2 a→+∞ a2

Z
e−t +∞
Exercice 19.8 — Soit x > 0. On pose f (x) = dt.
0 t+x
1. Montrer que pour x > 0, l’intégrale définissant f (x) est convergente.
2. Déterminer un équivalent simple de f (x) quand x tend vers 0.

Z +∞
x2
e−t dt quand x tend vers + inf ty.
2
Exercice 19.9 — ƨ Trouver un équivalent simple de e
x
68 Chapitre 19. Intégrales Généralisées

Exercice 19.10 — ƨ Pour n ∈ N∗ , on pose

X
n
1
un = − ln(n) et f : ]0, +∞[ → R+
k
k=1 t 7→ t−⌊x⌋
t2
R +∞
1. Montrer que 1 f (t) dt est bien définie et convergente.
2. Montrer que
Z +∞ +∞ 
X 
1
f (t) dt = ln(j + 1) − ln(j) −
1 j+1
j=1
R +∞
3. Montrer que (un ) converge vers 1 − 1 f (t) dt.

Exercice 19.11 — ƨ Soit (an ) décroissante de limite nulle. On pose pour x > 0, N (x) = Card{n ∈
P
N | an ≥ x}. Montrer que N est intégrable sur ]0, +∞[ si et seulement si la série an converge.

Z +∞
1
Exercice 19.12 — ƨ Une suite d’Intégrales. Pour n ∈ N∗ , on pose In = dt.
0 (1 + t2 )n
1. Montrer que In converge.
2. Trouver une relation de récurrence entre In+1 et In .
3. En déduire une expression pour In .

Exercice 19.13 — ƨ Soit n ∈ N∗ .



1. Montrer que pour tout x ∈ [0, n],
 n  −n
x2 x2
≤ e−x ≤
2
1− 1+
n n

2. En
Z effectuant des changements de variable en cos et tan, en déduire la valeur de l’intégrale en
e−x dx.
2

R Z π r
2 π
On pourra se rappeler les intégrales de Wallis : cos x dx ∼
n
0 2n
20. Suites et Séries de Fonctions

20.1 Suites de Fonctions


Exercice 20.1 — Étudier la convergence simple, uniforme et localement uniforme de la suite de
fonctions définie par
nx
fn (x) =
1 + n2 x 2

Exercice 20.2 — Pour n ∈ N∗ , on définit fn : [0, 1] → R


x +xe−x
x → 7 (x2 + 1) ne n+x
1. Montrer que (fn ) converge uniformément sur [0, 1].
Z 1
nex + xex
2. En déduire lim (x2 + 1) dx.
n→+∞ 0 n+x

Exercice 20.3 — Étudier la convergence (simple, uniforme ou localement uniforme) sur R de la


suite de fonctions définie par
 πx 
∀n ∈ N, ∀x ∈ R, fn (x) = n(1 − x)n sin
2

Exercice 20.4 — Suite de Fonctions Lipschitziennes. Soit (fn ) une suite de fonctions de [a, b] dans
R lipschitziennes de même rapport M > 0 convergeant simplement sur [a, b] vers f . Montrer que la
convergence est uniforme.

Exercice 20.5 — Soit Pn une suite de fonctions polynomiales convergeant uniformément sur R
vers f . Montrer que f est polynomiale.

Exercice 20.6 — Algèbre Linéaire et Analyse. 1. Soient f1 , . . . , fn des applications de R dans C.


Montrer qu’elles forment une famille libre si et seulement si il y a n réels a1 , . . . , an tel que la
matrice des fi (aj ) est inversible.
2. Soit F un sev de dimension finie des applications continues bornées de R dans C. Montrer
qu’une suite de F converge simplement si et seulement si elle converge uniformément.

20.2 Séries de Fonctions


X
+∞ n
x sin(nx)
Exercice 20.7 — Soit f (x) = .
n
n=1
70 Chapitre 20. Suites et Séries de Fonctions

1. Montrer que f est de classe C 1 sur ] − 1, 1[.


2. Calculer f ′ (x). En déduire l’expression de f sur ] − 1, 1[.

X
+∞
(−1)n−1
Exercice 20.8 — Soit f (x) = .
ln(nx)
n=1
1. Vérifier que f est bien définie sur ]1, +∞[.
2. Donner les limites en +∞ et 1+ de f .
3. Montrer que f est de classe C 1 sur ]1, +∞[ et dresser son tableau de variation.

X
+∞ n
x
Exercice 20.9 — 1. Montrer que pour x ∈ [0, 1[, − ln(1 − x) =
n
n=1
Z X
+∞
1
ln(t) ln(1 − t) 1
2. Montrer que dt =
0 t n3
n=1

Z 1 X
+∞
1
Exercice 20.10 — Montrer que x−x dx =
0 nn
n=1

Exercice 20.11 — Série de Primitives. Soit f0 : [a, b] → R continue. On définit fn par récurrence
Rx P∞
par fn+1 (x) = fn pour n ∈ N et x ∈ [a, b]. Etudier et évaluer la fonction g : x 7→ n=1 fn (x)
a

Exercice 20.12 — Décomposition en Série de Fonctions de la Valeur Absolue - Horriblement Difficile


et si peu Intéressant. Soit f la fonction 1-périodique définie par f (x) = x2 pour |x| ≤ 12 . Montrer
que, si x ∈ R :
X
+∞ x
2 f n = |x|
n

n=−∞
2
21. Intégrales à Paramètres

Exercice 21.1 — Ș Soit f : [0, 1] → R continue par morceaux sur [0, 1], strictement croissante et
telle que f (0) = 0, f (1) = 1. Montrer que
Z 1
lim f (t)n dt = 0
n→+∞ 0

Z 1 X
+∞
−x 1
Exercice 21.2 — Ș Montrer que x dx =
0 nn
n=1

Z +∞
sin(xt) −t
Exercice 21.3 — Ș Pour x ≥ 0, on pose I(x) = e dt.
0 t
1. Justifier que I est bien définie sur [0, +∞].
2. Montrer que I est dérivable sur [0, +∞].
3. En déduire I.

Z +∞
1
Exercice 21.4 — Ș Pour n ∈ N∗ et x ∈]0, +∞[, on pose In (x) = dt.
0 (t2 + x2 ) n
1. Calculer la dérivée de laZfonction In sur ]0, +∞[.
+∞
1
2. En déduire la valeur de dt.
0 (t + 1)3
2

Z +∞
x
Exercice 21.5 — ƨ Calculer dx.
0 ex −1

Z +∞
arctan(xt)
Exercice 21.6 — Pour x ≥ 0, on pose F (x) = dt.
0 t(1 + t2 )
1. Montrer que F est définie et de classe C 1 sur R+ .
2. Calculer F ′ (x) pour x 6= 1, puis montrer que l’expression obtenue fonctionne aussi en x = 1.
3. En déduire
Z +∞une expression simple de F (x).
arctan2 (t)
4. Calculer dt.
0 t2

Z +∞
sin(t)
Exercice 21.7 — ƨ Astuce de Feynman. On veut calculer dt. Pour ce faire, on consi-
0 t
72 Chapitre 21. Intégrales à Paramètres

dère : Z +∞
sin(t) −xt
I : x 7→ e dt
0 t
1. Justifier que I est bien définie sur [0, +∞[.
2. Montrer que f est de classe C 1 sur ]0, +∞[.
3. En déduire f (x) pour x ∈ R+∗ .
4. Montrer que f est continue en 0. Conclure.

Exercice 21.8 — ί D’Alembert-Gauss avec des intégrales à paramètres. On admet que si f ∈


C 1 (R, C∗ ), alors alors on dispose de ρ, θ ∈ C 1 (R, R) avec ρ à valeurs dans R+∗ telles que f = ρeiθ .
Soit f ∈ C 1 (R, C∗ ) 2π-périodique. On pose
Z
1 2π
f ′ (t)
I(f ) = dt
2iπ 0 f (t)

1. Montrer que I(f ) ∈ Z.


2. Soit P ∈ C[X]. Pour r ≥ 0, on pose Pr : t 7→ P (reit ).
a. On suppose que P ne s’annule pas. Soit J : r → I(Pr ).
i. Montrer que J est constante.
′ (z)
ii. Soit n = deg P . Étudier z 7→ zP P (z) quand |z| tend vers l’infini puis établir une
contradiction. Que vient-on de démontrer ?
b. Montrer que pour r ≥ 0, I(Pr ) est le nombre de racines de P comptées avec leur multi-
plicité dont le module est strictement inférieur à r.
3. Montrer la supposition énoncée au début.
22. Structures Algébriques

22.1 Groupes
■ Notation 22.1 — On considérera des groupes d’élément neutre e.
— Quand la loi de composition interne d’un groupe n’est pas précisée, on adoptera la notation
multiplicative : x ∗ y sera noté xy et x−1 sera l’inverse de x.
— On notera o(x) l’ordre d’un élément x ∈ G.
.
Exercice 22.1 — ƨ Démontrer que tout sous-groupe de (R, +) est soit de la forme αZ avec α ∈ R
 R. On pourra pour cela considérer, pour un sous-groupe G non trivial, le nombre
soit dense dans
inf G ∩ R∗+ . 
En déduire que 2n 3m | (n, m) ∈ Z2 est dense dans R.

Exercice 22.2 — ƨ Soit G un groupe abélien.


1. Soient a, b ∈ G d’ordres finis. Montrer que o(ab) est d’ordre fini et que si o(a) ∧ o(b) = 1, alors
o(ab) = o(a)o(b).
2. Le résultat subsiste-t-il si G n’est plus abélien ?

Exercice 22.3 — Ș Soit G un groupe. On pose Z(G) = {x ∈ G | ∀y ∈ G, xy = yx} le centre de


G. Montrer que Z(G) est un sous-groupe de G.

Exercice 22.4 — ί Soit G un groupe fini non commutatif. Montrer que la probabilité que deux
éléments de G choisis au hasard (uniformément) commutent est inférieure à 5/8.

La structure présentée ci-dessous permet notamment la difficile classification des groupes simples.

Exercice 22.5 — ί Dévissage en produit direct interne. 1. Soit G un groupe et H, K deux sous-
groupes de G. On suppose H ∩ K = 1, G = HK et enfin hk = kh pour tout (h, k) ∈ H × K.
Montrer que G ' H × K.
2. Soit G un groupe et f : G → Z un morphisme surjectif. Montrer G ' ker f × Z.
3. Classer les groupes d’ordre 6.

L’exercice classique par excellence sur les groupes est le théorème de Lagrange sur les groupes finis.
Ce théorème n’est pas au programme de CPGE mais son utilisation dans d’autres exercices sur les
groupes est commune.
Exercice 22.6 — ƨ Théorème de Lagrange. Soit G un groupe fini. Soit H un sous-groupe de G.
Montrer que Card(H) | Card(G).

Le corollaire du théorème de Lagrange est un résultat au programme de MP. La preuve n’est cependant
74 Chapitre 22. Structures Algébriques

exigible que dans le cas abélien. Le théorème de Lagrange permet de donner une démonstration générale
de son corollaire.
Exercice 22.7 — Ș Corollaire du théorème de Lagrange. Soit G un groupe fini. Soit x ∈ G. Montrer
que xCard(G) = e.

Ces relations de divisibilité dans les groupes finis les lient à des notions d’arithmétique.

Exercice 22.8 — ί Soit G un groupe fini d’ordre p premier. Que dire de la structure de G ?

22.2 Anneaux et Corps


22.2.1 Nombres et Entiers Algébriques
■ Vocabulaire 22.1 On dit qu’un nombre complexe a ∈ C est algébrique s’il existe P ∈ Q[X] tel que
P (a) = 0.

Exercice 22.9 — ί Corps des Nombres Algébriques. 1. Montrer que 5 et i sont algébriques.
2. Montrer que pour z ∈ C, {P ∈ Q[X] | P (z) = 0} est un idéal de K[X].
3. Montrer que 31/2 + 21/3 est algébrique. Essayer de généraliser la méthode pour montrer que
si x, y sont algébriques alors x + y l’est aussi.
4. Montrer que si x est algébrique non nul, x1 l’est aussi.

22.3 Digressions et Exercices Supplémentaires


En prépa, on a tendance à définir un corps comme étant commutatif. Certains auteurs, notamment
dans la tradition mathématique française, ne demandent pas cette hypothèse d’un corps.
Dans cet exercice, nous allons démontrer que tout corps fini est commutatif. Nous allons utiliser
pour cela un lemme présenté dans le chapitre d’Arithmétique :

Théorème 22.1 Pour (q, n, d) ∈ (N∗ ) , avec q ≥ 2, on a l’équivalence suivante :


3

d | n ⇐⇒ q d − 1 | q n − 1

Nous utiliserons également les polynômes cyclotomiques (dont les propriétés ont été vues dans le
chapitre de première année correspondant). On rappelle simplement leur définition :

Définition 22.1 On note Φn le n-ème polynôme cyclotomique, défini par :


Y  
2ikπ
Φn = X − exp
n
0<k<n,k∧n=1

Nous avons démontré deux propriétés utiles sur ces polynômes :


Y
∀n ∈ N∗ , X n − 1 = Φd (X) et Φn (X) ∈ Z[X]
d|n

On reprend dans cet exercice des notions introduites dans les exercices précédents. Cet exercice
étant difficile, on en propose deux versions, plus ou moins guidées.

Exercice 22.10 — ίίThéorème de Wedderburn, Version Difficile. Dans la suite, on prend K un


corps fini.
1. On note Z le centre de K. En étudiant la structure de Z et son cardinal, montrer que |K| = q n .
2. On suppose dans la suite que K est non-commutatif. En utilisant l’ensemble Stab(x) ∪ {0}
22.3 Digressions et Exercices Supplémentaires 75

pour x ∈ K, montrer que :

|K ∗ | qn − 1
|Orb(x)| = = d
|Stab(x)| q −1

3. Montrer que si d < n : Y


Φn (q) | |Orb(x)| = Φm (q)
m|n,m∤d

où Φn est le n-ème polynôme cyclotomique.


4. Montrer que |Φn (q)| ≤ q − 1. On pourra pour cela utiliser l’équation aux classes.
5. En utilisant la définition des polynômes cyclotomiques, montrer que :

|Φn (q) > q − 1|

et en déduire le résultat

Exercice 22.11 — ί Théorème de Wedderburn, Version Facile. Dans la suite, on prend K un corps
fini.
1. On note Z le centre de K.
a. Montrer que Z est un sous-corps commutatif de K de cardinal q ∈ N \ {0, 1}.
b. En déduire que |K| = q n .
2. On suppose dans la suite que K est non-commutatif, donc que n > 1. Le groupe K ∗ agit sur
lui-même par conjugaison.
a. En utilisant l’ensemble Stab(x) ∪ {0} pour x ∈ K, montrer que |Stab(x)| = q d − 1.
b. Utiliser le Théorème de Lagrange pour en déduire :

|K ∗ | qn − 1
|Orb(x)| = = d
|Stab(x)| q −1

3. En déduire, en utilisant les propriétés des polynômes cyclotomiques, que si d < n :


Y
Φn (q) | |Orb(x)| = Φm (q)
m|n,m̸|d

4. On se donne {x1 , . . . , xr } un système de représentants des orbites non triviales.


a. Montrer que :

X
r X
r
∗ ∗
|K | = |Z | + |Orb(xi )| ⇐⇒ q − 1 = q − 1 +
n
|Orb(xi )|
i=1 i=1

b. Justifier Φn (q) | q − 1.
c. En déduire que |Φn (q)| ≤ q − 1.
5. On note ζi , 1 ≤ i ≤ r les racines primitives n-èmes de l’unité.
a. Montrer que ζi ∈ / R+ .
b. En déduire que
|Φn (q) > q − 1|
c. Conclure.

■ Notation 22.2 On notera Fp le corps fini à p éléments. Celui-ci est unique et isomorphe à Z/pZ.

Exercice 22.12 — ί Corps Fq . Soit p ∈ P, n ≥ 2 a . Montrer que si P ∈ Fp [X] est irréductible de


76 Chapitre 22. Structures Algébriques

degré n, alors Fp [X]/P est un corps. Quel est son cardinal ?


a. On pourrait prendre n = 1, mais ça n’aurait aucun intérêt

Proposition 22.1 — Caractérisation des Corps Finis. La construction ci-dessus permet d’obtenir tous les
corps finis à partir des corps Z/pZ. En particulier, le cardinal d’un corps fini K est une puissance d’un
nombre premier p qui est sa caractéristique. De plus, si ce corps est de cardinal pn , tout sous-corps de
K est de cardinal pd où d divise n. C’est la base de la Théorie de Galois !

Définition 22.2 On appelle Groupe Spécial Linéaire d’ordre n sur un corps K le sous-groupe SLn (K) =
ker det de Mn (K).

n (C). On identifiera C aux matrices scalaires complexes.


Exercice 22.13 — ί On se place dans M(
G∩C= {1}
Soit G un sous-groupe de SLn (C) tel que .
SLn (C) = GC
1. Montrer qu’il existe un morphisme surjectif f de G dans Z/nZ.
2. Montrer que f s’annule sur les transvections.
3. En déduire que n = 1.
23. Topologie

23.1 Topologie des Espaces Vectoriels Normés


Exercice 23.1 — Borne Supérieure du Déterminant. On note S l’ensemble des matrices A = (ai,j ) ∈
Mn (R) telle que pour tous i, j, |ai,j | ≤ 1. On considère α = supS det. Montrer que α est fini, puis
que A est un entier divisible par 2n−1 .

Exercice 23.2 — Caractérisation des Boules. Soit (E, k·k) un espace vectoriel normé. On rappelle
qu’une partie X de E est dite convexe si x, y ∈, t ∈ [0, 1] =⇒ tx + (1 − t)y ∈ X. C’est à dire, si
x, y ∈ X, [x, y] ⊆ X.
Montrer que pour B ⊆ E, il y a équivalence entre :
1. Il existe une norme N sur E telle que B soit la boule unité fermée pour N .
2. B est une partie fermée, bornée de E, convexe, symétrique en 0 et contenant une boule de
centre 0.

23.2 Topologie des Espaces Vectoriels Normés de Dimension Finie


Exercice 23.3 — Soit (E, k·k) un R-espace vectoriel normé. Rappelons qu’une forme linéaire l sur E
est continue si et seulement si elle est bornée sur la sphère unité. |||l||| désigne alors le suprememum
des valeurs prises.
1. Montrer que |||·||| est une norme sur E ∗ l’ensemble des formes linéaires continues.
2. Supposons E de dimension finie, soit l ∈ E ∗ . En considérant l’application x ∈ E 7→ kxk +
kl(x)k, montrer que l est continue.
3. Réciproquement, si E est de dimension infinie, construire une forme linéaire discontinue. On
pourra admettre que tout sous-espace vectoriel de E admet un supplémentaire.

23.3 Séries vectorielles

23.4 Connexité
Exercice 23.4 — Soit R un ensemble de rangs dans {0, . . . , n} et MR l’ensemble des matrices
réelles dont le rang est dans R. On cherche une condition nécessaire et suffisante pour que MR soit
connexe par arcs.
On pourra traiter successivement les cas :
— R = {n}.
— R = {r} où r < n.
— R = {r, n} où r < n.
— R = {r, r′ } où r, r′ < n.
78 Chapitre 23. Topologie

23.5 Digressions et exercices supplémentaires


Il est recommandé d’avoir fait le chapitre de deuxième année sur les structures algébriques (et tout
particulièrement ses digressions) avant de s’attaquer aux deux exercices suivants. Toutefois, cela n’est
absolument pas nécessaire, et aucun résultat hors programme n’est à connaître.

Exercice 23.5 — Normes Lp et quotients d’espaces vectoriels. On définit pour p ≥ 1 et f ∈ Cm ([0, 1]),
s
Z 1
|f (t)|p dt
p
Np (f ) =
0

Vérifier que Np est homogène. Montrer qu’elle est sous-additive pour p = 1 et p = 2. On admet que
toutes les Np sont sous-additives. Np est-elle séparée ?
Notons ker Np = {x ∈ Cm ([0, 1]) | Np (x) = 0}. Montrer que ker Np est un sous-espace vectoriel de
E.
Montrer que f ∼ g ⇔ f − g ∈ ker Np est une relation d’équivalence sur Cm ([0, 1]).
On note Lp ([0, 1]) l’ensemble de ses classes d’équivalences. Justifier que Lp ([0, 1]) possède une
structure d’espace vectoriel et que Np induit une norme sur Lp .

Exercice 23.6 — Points Fixes de Groupes. Soient (E, k·k) un R-espace vectoriel euclidien et G un
sous-groupe fini de GLn (R). Soit K une partie convexe de E.
1. On pose pour x ∈ E, N (x) = supu∈G ku(x)k. Vérifier que N est une norme sur E.
2. Supposons que N (x + y) = N (x) + N (y). Montrer que x et y sont positivement liés, i.e. qu’il
existe λ ≥ 0 tel que x = λy.
3. On suppose que N possède un minimum x0 sur K. Montrer que x0 est stable par chaque
élément de G.
24. Compléments d’Algèbre Linéaire
25. Réduction des Endomorphismes

Dans l’exercice qui suit, on n’utilisera pas le théorème de Cayley-Hamilton. Celui-ci est toutefois
très difficile, et nécessite la connaissance du cours sur les structures algébriques.

Exercice 25.1 — ί Une autre preuve du théorème de Cayley-Hamilton. Soient k un corps et n un


entier.
1. Montrer que si M  ∈ Mn (k), alors
 χM annule M .
On pose K = k (Xi,j )1≤i,j≤n le corps de fractions rationelles en n2 indéterminées et K̄ un
corps algébriquement clos contenant K (dont on admet l’existence). On note U la matrice
universelle (Xi,j ), dont les coefficients sont indéterminés et χU ∈ K [T ] = det (T In − U ).
2. Montrer
Y que les racines α1 , . . . , αn2 de χU dans K̄ sont simples. On pourra admettre que :
(αi − αj ) ∈ K.
1≤i̸=j≤n
3. En déduire que U est diagonalisable dans K, puis démontrer le théorème de Cayley-Hamilton.
26. Probabilités de Spé

26.1 Dénombrabilité
Exercice 26.1 — Ș L’ensemble des complexes de module 1 est-il dénombrable ? Celui des racines
de l’unité (i.e. l’ensemble des z ∈ C tels qu’il existe n ∈ N, z n = 1).

Exercice 26.2 — Ș Les ensembles P (N) et NN sont-ils dénombrables ?

■ Vocabulaire 26.1 Une suite à support fini est une suite nulle à partir d’un certain rang. On note
souvent E (N) l’ensemble des suites à support fini à valeurs dans E. Les suites à support fini sont
isomorphes aux polynômes à coefficient dans E, d’où le fait qu’on les appelle parfois polynôme.

Exercice 26.3 — Ș L’ensemble des suites entières à support fini est-il dénombrable ?

■ Vocabulaire 26.2 On dit qu’un nombre complexe est algébrique lorsqu’il est racine d’un polynôme
non nul à coefficients entiers.

Exercice 26.4 — ƨ Montrer que l’ensemble des nombres algébriques est dénombrable.

Exercice 26.5 — ί Soit E un C-ev à base dénombrable. On suppose que E est un corps. Montrer
que E = C.

Exercice 26.6 — ί Oral Ulm 2016. L’ensemble des bijections de N dans lui-même est-il dénom-
brable ?

26.2 Sommabilité
P  
1 π2 (−1)mn
Exercice 26.7 — Ș On admet que n≥1 n2 = 6 . Montrer que la famille m2 n2
est
(m,n)∈N2∗
sommable et calculer sa somme.

Exercice 26.8 — Ș Convergence des Séries de Laurent. Montrer que la famille (un )n∈Z est sommable
P P
si et seulement si les deux séries un et u−n sont absolument convergentes.

Exercice 26.9 — Ș Pour quelles valeurs des nombres complexes a et b la famille (am bn )(m,n)∈N×N
est-elle sommable ? Calculer alors sa somme.
84 Chapitre 26. Probabilités de Spé
P P k
Exercice 26.10 — Série de Zeta. Démontrer que les deux séries k≥2 (ζ(k) − 1) et k≥2 (−1) (ζ(k) − 1)
convergent, et les calculer.

P
Exercice 26.11 — ƨ Analyticité d’une somme de série entière. Soit an z n une série entière de
rayon de convergence R > 0. On note f sa somme, définie sur D(0, R). Soit a un point de ce disque
ouvert. En utilisant une suite double sommable, démontrer qu’il existe une suite (bn ) telle que, pour
tout nombre complexe h tel que |h| < R − |a|,

X
+∞
f (a + h) = b n hn
n=0

■ Vocabulaire 26.3 On dit que la somme d’une série entière est analytique sur son domaine de définition.

Exercice 26.12 — ƨ Produit Eulérien pour Zeta. Montrer que, si s > 1, si P est l’ensemble des
nombres premiers,
Y 1 X 1
+∞

−s
=
1−p ns
p∈P n=1

On pourra, si p1 , . . . , pN sont les N premiers nombres premiers, écrire (en le justifiant !) que :
!
YN
1 YN X
+∞

−s = p−sn
i
i

i=1
1 − p i i=1 n =0i

26.3 Variables Aléatoires


26.4 Séries Génératrices
Définition 26.1 — Processus Stochastique. Un processus stochastique est généralement défini comme
une suite de variables aléatoires sur un même espace de probabilités.

Dans l’exercice qui suit, on va s’intéresser à un certain type de processus stochastique, appelé
marche aléatoire.
■ Vocabulaire 26.4 — Loi de Rademacher. On appelle loi de Rademacher la loi de la variable aléatoire
X sur {−1, 1} telle que P(X = 1) = P(X = −1) = 21 .

Exercice 26.13 — ƨ Marche Aléatoire sur Z. On se donne (Xn )n≥1 une suite de variables aléatoires
X
n
i.i.d. de loi de Rademacher. Pour n ≥ 1, on pose Sn = Xk . La suite (Sn ) modélise une marche
k=1
aléatoire centrée sur Z.
26.4 Séries Génératrices 85

Figure 26.1 – Marche Aléatoire sur Z

On s’intéresse à la probabilité que la marche aléatoire revienne en 0, c’est-à-dire, en notant


T = inf {n ≥ 1 | Sn = 0}, à la probabilité P (T < ∞). Dans ce développement, on va montrer que
P (T < ∞) = 1.
1. Préliminaires : Calculer le développement en série entière de la fonction :

]−1, 1[ → R
x 7→ √1−x
1
2

On pose dans la suite pn = P (Sn = 0) et qn = P (T = n). On notera P et Q les séries


génératrices des suites pn et qn . On va chercher à déterminer Q(1).
2. Montrer que : (
0 si n = 0 mod 2
pn = 
2n 1
n 4n sinon
En déduire la valeur de P .
3. Donner une relation de récurrence entre les pn et les qn .
4. En déduire la valeur de Q et conclure.
27. Fonctions Vectorielles

Exercice 27.1 — Soit A ∈ Mn (K). On note à la transposée de la comatrice de A. Montrer que Ã


est un polynôme en A. On traitera succesivement les cas K = R, K infini et K quelconque.

Définition 27.1 Une R-algèbre de dimension finie est un R-espace vectoriel (E, +, ×) de dimension
fini muni d’une loi de produit interne · tel que (E, +, ·) soit un anneau.

Définition 27.2 Une norme d’algèbre sur (E, +, ×, ·) est une norme sur l’espace vectoriel (E, +, ×)
telle que kM · N k ≤ kM k kN k.

Exercice 27.2 — Ș Soit A une R-algèbre de dimension finie d’unité e et munie d’une norme notée
k·k.
1. Soit u un élément de A de norme
P n au plus 1.
a. Démontrer que la série u est convergente. P n
et que (e − u)−1 =
b. Démontrer que (e − u) est inversibleP u
n
2. Démontrer que pour tout u ∈ A, la série u
n! converge.

Exercice 27.3 — Ș On se place sur (Mn (R) , +, ×, ·).


1. Donner une norme d’algèbre sur cet espace.
P Mn
2. Soit M ∈ Mn (R). Justifier que la série n converge. On note exp M sa limite.
3. Justifier que M commute avec exp M . On suppose que M commute avec N , justifier que
exp(M + N ) = exp M exp N puis que exp M commute avec exp N . En déduire que exp M est
inversible.
4. L’application exp est-elle un morphisme de groupes de GLn (R) ?

Exercice 27.4 — ƨ Une Démonstration du Théorème de Cayley-Hamilton. On se place sur C.


On assimilera ici C et CIn où n ∈ N, et on note A−1 = A1 même pour une matrice.
On fixe A ∈ Mn (C).
1. Montrer que pour z ∈ C suffisamment grand, det(z − A) 6= 0
2. En déduire que pour r assez grand, l’intégrale

Z+π
(reiθ )k+1 dθ
reiθ − A 2π
−π

a un sens.
88 Chapitre 27. Fonctions Vectorielles

3. Montrer que si A est suffisamment ’petite’ :

1 X +∞
= Ak
1−A
k=0

4. En déduire la valeur de l’intégrale de la question 2.


5. Calculer χA (A). Quel résultat retrouve-t-on ?

Exercice 27.5 — Espaces de Banach. On considère R[X] muni de la norme 2 dans la base canonique.
n
Montrer que la série de terme général Xn est absolument convergente mais pas convergente. On
pourra admettre qu’une projection orthogonale sur un sous-espace de dimension finie est séquen-
tiellement continue. Faire de même dans R[X], |·|.

Exercice 27.6 — ƨί. On va étudier la similitude de matrices dans différents espaces. Ici, on
considèrera principalement l’espace auquel appartiennent les matrices de passage.
1. Soient A, B deux matrices réelles semblables dans Mn (C). Montrer qu’elles sont semblables
dans Mn (R).
2. Généraliser le résultat à tout sur-corps de R de dimension finie, i.e. isomorphe à un Rn .
3. Que se passe-t-il si on remplace R par un corps infini abstrait K ?

R Si l’on voulait remplacer R par un corps fini, le résultat resterait valable, mais en donner une
preuve sans utiliser des outils hors programme (notamment les invariants de similitude) semble
très difficile.
28. Séries Entières

Exercice 28.1 — Ș 1. Donner la définition du rayon de convergence d’une série entière de la


variable complexe. P
2. Soit (an )n∈N une suite
P bornée telle que la série an diverge. Quel est le rayon de convergence
de la série entière n
an z ? Justifier.
P √ (−1)n  
3. Quel est le rayon de convergence de la série entière n ln 1 + √1n z n ?

28.1 Séries Génératrices en Dénombrement


Exercice 28.2 — ƨ Des Partitions d’un Ensemble fini. On note bn le nombre de partitions d’un
ensemble à n éléments.
1. Calculer b0 , . . . , b3
2. Trouver une relation de récurrence entre les bn
P
∞ n
3. Exprimer bn xn!
n=0
4. Donner une expression de bn
29. Espaces Euclidiens

29.1 Isométries et Matrices Orthogonales


Exercice 29.1 — Soient n points du plan R2 qui vérifient la propriété suivante :

Toute droite contenant deux points du plan en contient un troisième.

Montrer qu’ils sont tous alignés.

29.2 Endomorphismes Autoadjoints Positifs, Définis Positifs


Exercice 29.2 — ƨ Décomposition polaire. Soit u ∈ Gl(E). Montrer qu’il existe un unique couple
(o, s) ∈ O(E) × S ++ (E) tel que u = os.

Exercice 29.3 — Ș Racine carrée d’un endomorphisme positif. Soit u un endomorphisme autoadjoint
positif de E.
1. Montrer qu’il existe v endomorphisme autoadjoint positif de E tel que v 2 = u et que si u est
défini positif, v l’est aussi.
2. Montrer que v ∈ R[u].
30. Équations Différentielles Linéaires
31. Calcul Différentiel

Exercice 31.1 — Différentielle du Déterminant. 1. Montrer que φ : GLn (R) → Mn (R) qui à X
associe (det X) X −1 admet un et un seul prolongement continu φ̄ à Mn (R).
2. Soient A, B deux matrices. Prouver que :
 
d
(det (A + tB)) = Tr (φ̄ (A) B)
dt t=0

Exercice 31.2 — Un DL du Déterminant. Montrer que :


 
X
n X
det(A + tIn ) =  det AI  tk
k=0 |I|=n−k

R On peut généraliser : X Y
det (A + Diag(t1 , . . . , tn )) = det AI ti
I i∈I
/

31.1 Géométrie Différentielle, un peu


Exercice 31.3 — ƨ Dans cet exercice, on considère les figures inscrites dans une ellipse.
1. Quels sont les triangles inscrits dans une ellipse qui sont d’aire maximale ?
2. Quels sont les rectangles inscrits dans une ellipse qui sont d’aire maximale ?
3. Si n ≥ 3, quels sont les n-gones inscrits dans une ellipse qui sont d’aire maximale ?

L’exercice suivant est tiré de [ ?]

Exercice 31.4 — Soit K ⊆ R2 un compact convexe dont la frontière ∂K est une courbe (fermée)
de classe C ∞ . Montrer que pour tout n ≥ 2, on peut, en jouant au billard dans K, faire n rebonds
et revenir au même point de départ.
On rappelle que la trajectoire d’une boule de billard parfaite suit la loi de Snell-Descartes de la
réflexion.
III Informatique de MP2I/MPI

32 Notions d’Architecture et de Système . 101

33 Programmation Fonctionnelle . . . . . . . . 103

34 Programmation Impérative . . . . . . . . . . . 105

35 Analyse des Programmes . . . . . . . . . . . . 107


35.1 Correction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
35.2 Terminaison . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
35.3 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
35.4 Induction Structurelle . . . . . . . . . . . . . . . . . . . . . 107

36 Structures de Données . . . . . . . . . . . . . . 109


36.1 Structures Séquentielles . . . . . . . . . . . . . . . . . . . . 109
36.2 Structures Hiérarchiques . . . . . . . . . . . . . . . . . . . . 109

37 Graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
37.1 Notion et Représentation . . . . . . . . . . . . . . . . . . . 111
37.2 Algorithmique des Graphes . . . . . . . . . . . . . . . . . . 111

38 Algorithmique . . . . . . . . . . . . . . . . . . . . . . 113
38.1 Arithmétique . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
38.2 Méthodes Classiques . . . . . . . . . . . . . . . . . . . . . . 113
38.3 Algorithmes sur les Chaînes de Caractère . . . . . . . . 113
38.4 Algorithmes Probabilités . . . . . . . . . . . . . . . . . . . 113
38.5 Algorithmique pour l’IA et les Jeux . . . . . . . . . . . . 113

39 Logique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
39.1 Logique Propositionnelle et du Premier Ordre . . . . . 115
39.2 Déduction Naturelle . . . . . . . . . . . . . . . . . . . . . . . 115

40 Bases de Données . . . . . . . . . . . . . . . . . . . 117


40.1 Théorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
40.2 SQL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

41 Langages Formels . . . . . . . . . . . . . . . . . . . 119


41.1 Langages Rationnels . . . . . . . . . . . . . . . . . . . . . . 119
41.2 Automates Finis . . . . . . . . . . . . . . . . . . . . . . . . . 119
41.3 Grammaires Hors-Contexte . . . . . . . . . . . . . . . . . . 119

42 Calculabilité et Décidabilité . . . . . . . . . . 121


42.1 Décidabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
42.2 Classes de Complexité . . . . . . . . . . . . . . . . . . . . . 121

43 Concurrence et Synchronisation . . . . . . 123


Introduction

Les exercices qui suivent sont des exercices adaptés au programme d’informatique de MP2I/MPI.
Ils peuvent (pour ceux portant sur le programme correspondant) être utiles aux élèves d’Option
Informatique en MPSI/MP. Il est possible qu’une partie sur l’Informatique pour Tous finisse par voir
le jour, mais ce n’est pas sûr.
32. Notions d’Architecture et de Système
33. Programmation Fonctionnelle
34. Programmation Impérative
35. Analyse des Programmes

35.1 Correction
35.2 Terminaison
35.3 Complexité
Exercice 35.1 — Ș Tableaux Binaires. On considère le problème suivant :

Minimum Change Binary Matrix


Entrée : Une matrice M ∈ Mn,m ({0, 1})
Sortie : Le nombre minimum de coefficient à changer pour que chaque ligne
et chaque colonne ait un nombre pair de 1

Proposer un algorithme qui résout le problème en O(mn). Montrer sa correction.

35.4 Induction Structurelle


Exercice 35.2 — On dispose d’un stock illimité de billets et de pièces de valeurs c1 , . . . , cp . On
souhaite dénombrer le nombre de manières possibles d’obtenir une somme donnée avec ces espèces.
Écrire une fonction récursive prenant en paramètre la somme à atteindre et la liste des valeurs de
pièces et calculant cette quantité.

Exercice 35.3 — Soit T un tableau de taille 2n dont les valeurs sont dans {0, 1, 2}. On dit que T
est tricoloré si :
∀0 ≤ i < N, T [i] 6= T [2i + 1] 6= T [2i + 2] 6= T [i]
Dénombrer le nombre de tableau tricolorés de longueur 2k − 1

Exercice 35.4 — ƨ Tours de Hanoï. Les tours de Hanoï est est un puzzle inventé par le mathé-
maticien français Édouard Lucas : il est constitué de trois tiges sur lesquelles peuvent être enfilés n
disques de diamètres différents. Au début du jeu, ces disques sont tous enfilés sur la même tige, du
plus grand au plus petit.
108 Chapitre 35. Analyse des Programmes

A C

On ne peut déplacer qu’un disque à la fois, l’objectif étant déplacer tous les disques sur une autre des
tours. Donner le code d’une fonction résolvant le jeu en imprimant tous les mouvements effectués.
On pourra pour cela utiliser la fonction suivante :

let print_coup t1 t2 = print_string t1; print_string "->"; print_string t2; print_newline ();
36. Structures de Données

36.1 Structures Séquentielles


Exercice 36.1 — Ș Permutations. On représente une permutation σ comme un tableau T de lon-
gueur n tel que ∀i < N, T [i] = σ(i).
Donner le code d’une fonction qui à une permutation de J0, N K représenté par T retourne la pro-
chaine permutation de J0, N K dans l’ordre lexicographique.

36.2 Structures Hiérarchiques


37. Graphes

37.1 Notion et Représentation


37.2 Algorithmique des Graphes
38. Algorithmique

38.1 Arithmétique
38.2 Méthodes Classiques
38.2.1 Algorithmes Gloutons
38.2.2 Programmation Dynamique
38.3 Algorithmes sur les Chaînes de Caractère
38.4 Algorithmes Probabilités
38.5 Algorithmique pour l’IA et les Jeux
39. Logique

39.1 Logique Propositionnelle et du Premier Ordre


39.2 Déduction Naturelle
40. Bases de Données

40.1 Théorie
40.2 SQL
41. Langages Formels

41.1 Langages Rationnels


41.2 Automates Finis
41.3 Grammaires Hors-Contexte
42. Calculabilité et Décidabilité

42.1 Décidabilité
42.2 Classes de Complexité
43. Concurrence et Synchronisation
IV Astuces de MPSI

1 Raisonnement, Ensembles, Appli- 7.3 Digressions et Exercices Supplémentaires 139


cations et Relations . . . . . . . . 127
1.1 Raisonnements . . . . . . . . . . . . . . . . 127 8 Arithmétique . . . . . . . . . . . . . . 141
1.2 Ensembles . . . . . . . . . . . . . . . . . . . 127 8.1 Divisibilité, PGCD, PPCM . . . . . . . . 141
1.3 Applications et Relations . . . . . . . . . 127 8.2 Nombres premiers . . . . . . . . . . . . . . 141
1.4 Digressions et Exercices Supplémentaires 127 8.3 Digressions et exercices supplémentaires 141

2 Réels, Complexes, Trigonométrie, 9 Polynômes et Fractions Ration-


Sommes et Produits . . . . . . . . 129 nelles . . . . . . . . . . . . . . . . . . . . . 143
2.1 Compléments sur les Réels . . . . . . . . 129 9.1 Polynômes . . . . . . . . . . . . . . . . . . . 143
2.2 Complexes et Trigonométrie . . . . . . . 129 9.2 Fraction Rationnelles . . . . . . . . . . . . 143
2.3 Sommes et Produits . . . . . . . . . . . . 129 9.3 Digressions et Exercices Supplémentaires 143
2.4 Digressions et Exercices Supplémentaires 129
10 Algèbre Linéaire de Base . . . 145
3 Fonctions Usuelles : Dérivées, In- 10.1 Sous-Espaces et Applications Linéaires 145
tégrales, Équations Différentielles 10.2 Dimension Finie . . . . . . . . . . . . . . . 145
131
3.1 Dérivées . . . . . . . . . . . . . . . . . . . . . 131 11 Matrices . . . . . . . . . . . . . . . . . . 147
3.2 Intégrales . . . . . . . . . . . . . . . . . . . . 131
3.3 Équations Différentielles . . . . . . . . . . 131 12 Uniforme Continuité, Intégration
149
4 Suites, Limites, Continuité . . 133
4.1 Suites . . . . . . . . . . . . . . . . . . . . . . 133
4.2 Limites . . . . . . . . . . . . . . . . . . . . . 133
13 Séries . . . . . . . . . . . . . . . . . . . . . 151
4.3 Continuité . . . . . . . . . . . . . . . . . . . 133
14 Déterminants . . . . . . . . . . . . . . 153
5 Dérivation . . . . . . . . . . . . . . . . . 135 14.1 Groupe Symétrique . . . . . . . . . . . . . 153
5.1 Fonctions Dérivables . . . . . . . . . . . . 135 14.2 Déterminants . . . . . . . . . . . . . . . . . 153
5.2 Convexité . . . . . . . . . . . . . . . . . . . . 135
15 Espaces Vectoriels Préhilbertiens
6 Analyse Asymptotique . . . . . . 137 155
6.1 Analyse Asymptotique des Suites . . . 137
6.2 Développements Limités . . . . . . . . . . 137 16 Dénombrement . . . . . . . . . . . . 157
16.1 Théorie . . . . . . . . . . . . . . . . . . . . . 157
7 Structures Algébriques . . . . . . 139 16.2 Applications . . . . . . . . . . . . . . . . . . 157
7.1 Groupes . . . . . . . . . . . . . . . . . . . . . 139
7.2 Anneaux et Corps . . . . . . . . . . . . . . 139 17 Probabilités . . . . . . . . . . . . . . . 159
1. Raisonnement, Ensembles, Applications et
Relations

1.1 Raisonnements
1.2 Ensembles
1.3 Applications et Relations
1.4 Digressions et Exercices Supplémentaires
2. Réels, Complexes, Trigonométrie, Sommes et
Produits

2.1 Compléments sur les Réels


2.2 Complexes et Trigonométrie
2.3 Sommes et Produits
2.4 Digressions et Exercices Supplémentaires
3. Fonctions Usuelles : Dérivées, Intégrales,
Équations Différentielles

3.1 Dérivées
3.2 Intégrales
3.3 Équations Différentielles
4. Suites, Limites, Continuité

4.1 Suites
4.1.1 Suites Récurrentes
4.2 Limites
4.3 Continuité
5. Dérivation

5.1 Fonctions Dérivables


5.1.1 Quelques Calculs
5.1.2 Exercices Plus Théoriques
5.2 Convexité
6. Analyse Asymptotique

6.1 Analyse Asymptotique des Suites


6.2 Développements Limités
7. Structures Algébriques

7.1 Groupes
7.2 Anneaux et Corps
7.3 Digressions et Exercices Supplémentaires
8. Arithmétique

8.1 Divisibilité, PGCD, PPCM


8.2 Nombres premiers
8.3 Digressions et exercices supplémentaires
9. Polynômes et Fractions Rationnelles

9.1 Polynômes
9.2 Fraction Rationnelles
9.3 Digressions et Exercices Supplémentaires
10. Algèbre Linéaire de Base

10.1 Sous-Espaces et Applications Linéaires


10.2 Dimension Finie
11. Matrices
12. Uniforme Continuité, Intégration
13. Séries
14. Déterminants

14.1 Groupe Symétrique


14.2 Déterminants
15. Espaces Vectoriels Préhilbertiens
16. Dénombrement

16.1 Théorie
16.2 Applications
17. Probabilités
V 18
Astuces de MP

Rappels et Compléments d’Analyse . . . 163


18.1 Sous-Ensembles de R . . . . . . . . . . . . . . . . . . . . . . 163
18.2 Séries Numériques . . . . . . . . . . . . . . . . . . . . . . . . 163

19 Intégrales Généralisées . . . . . . . . . . . . . . 165

20 Suites et Séries de Fonctions . . . . . . . . . 167


20.1 Suites de Fonctions . . . . . . . . . . . . . . . . . . . . . . . 167
20.2 Séries de Fonctions . . . . . . . . . . . . . . . . . . . . . . . 167

21 Intégrales à Paramètres . . . . . . . . . . . . . . 169

22 Structures Algébriques . . . . . . . . . . . . . . . 171


22.1 Groupes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
22.2 Anneaux et Corps . . . . . . . . . . . . . . . . . . . . . . . . 171
22.3 Digressions et Exercices Supplémentaires . . . . . . . . 171

23 Topologie . . . . . . . . . . . . . . . . . . . . . . . . . . 173
23.1 Topologie des Espaces Vectoriels Normés . . . . . . . . 173
23.2 Topologie des Espaces Vectoriels Normés de Dimension Fi-
nie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
23.3 Séries vectorielles . . . . . . . . . . . . . . . . . . . . . . . . 173
23.4 Connexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
23.5 Digressions et exercices supplémentaires . . . . . . . . . 173

24 Compléments d’Algèbre Linéaire . . . . . . 175

25 Réduction des Endomorphismes . . . . . . 177

26 Probabilités de Spé . . . . . . . . . . . . . . . . . 179


26.1 Dénombrabilité . . . . . . . . . . . . . . . . . . . . . . . . . . 179
26.2 Sommabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
26.3 Variables Aléatoires . . . . . . . . . . . . . . . . . . . . . . . 179
26.4 Séries Génératrices . . . . . . . . . . . . . . . . . . . . . . . 179

27 Fonctions Vectorielles . . . . . . . . . . . . . . . 181

28 Séries Entières . . . . . . . . . . . . . . . . . . . . . . 183


28.1 Séries Génératrices en Dénombrement . . . . . . . . . . 183

29 Espaces Euclidiens . . . . . . . . . . . . . . . . . . 185


29.1 Isométries et Matrices Orthogonales . . . . . . . . . . . 185
29.2 Endomorphismes Autoadjoints Positifs, Définis Positifs 185

30 Équations Différentielles Linéaires . . . . 187

31 Calcul Différentiel . . . . . . . . . . . . . . . . . . . 189


31.1 Géométrie Différentielle, un peu . . . . . . . . . . . . . . 189
18. Rappels et Compléments d’Analyse

18.1 Sous-Ensembles de R
18.2 Séries Numériques
19. Intégrales Généralisées
20. Suites et Séries de Fonctions

20.1 Suites de Fonctions


20.2 Séries de Fonctions
21. Intégrales à Paramètres
22. Structures Algébriques

22.1 Groupes
22.2 Anneaux et Corps
22.2.1 Nombres et Entiers Algébriques
22.3 Digressions et Exercices Supplémentaires
23. Topologie

23.1 Topologie des Espaces Vectoriels Normés


23.2 Topologie des Espaces Vectoriels Normés de Dimension Finie
23.3 Séries vectorielles
23.4 Connexité
23.5 Digressions et exercices supplémentaires
24. Compléments d’Algèbre Linéaire
25. Réduction des Endomorphismes
26. Probabilités de Spé

26.1 Dénombrabilité
26.2 Sommabilité
26.3 Variables Aléatoires
26.4 Séries Génératrices
27. Fonctions Vectorielles
28. Séries Entières

28.1 Séries Génératrices en Dénombrement


29. Espaces Euclidiens

29.1 Isométries et Matrices Orthogonales


29.2 Endomorphismes Autoadjoints Positifs, Définis Positifs
30. Équations Différentielles Linéaires
31. Calcul Différentiel

31.1 Géométrie Différentielle, un peu


VI Astuces d’Informatique de
MP2I/MPI

32 Notions d’Architecture et de Système . 193

33 Programmation Fonctionnelle . . . . . . . . 195

34 Programmation Impérative . . . . . . . . . . . 197

35 Analyse des Programmes . . . . . . . . . . . . 199


35.1 Correction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
35.2 Terminaison . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
35.3 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
35.4 Induction Structurelle . . . . . . . . . . . . . . . . . . . . . 199

36 Structures de Données . . . . . . . . . . . . . . 201


36.1 Structures Séquentielles . . . . . . . . . . . . . . . . . . . . 201
36.2 Structures Hiérarchiques . . . . . . . . . . . . . . . . . . . . 201

37 Graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
37.1 Notion et Représentation . . . . . . . . . . . . . . . . . . . 203
37.2 Algorithmique des Graphes . . . . . . . . . . . . . . . . . . 203

38 Algorithmique . . . . . . . . . . . . . . . . . . . . . . 205
38.1 Arithmétique . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
38.2 Méthodes Classiques . . . . . . . . . . . . . . . . . . . . . . 205
38.3 Algorithmes sur les Chaînes de Caractère . . . . . . . . 205
38.4 Algorithmes Probabilités . . . . . . . . . . . . . . . . . . . 205
38.5 Algorithmique pour l’IA et les Jeux . . . . . . . . . . . . 205

39 Logique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
39.1 Logique Propositionnelle et du Premier Ordre . . . . . 207
39.2 Déduction Naturelle . . . . . . . . . . . . . . . . . . . . . . . 207

40 Bases de Données . . . . . . . . . . . . . . . . . . . 209


40.1 Théorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
40.2 SQL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209

41 Langages Formels . . . . . . . . . . . . . . . . . . . 211


41.1 Langages Rationnels . . . . . . . . . . . . . . . . . . . . . . 211
41.2 Automates Finis . . . . . . . . . . . . . . . . . . . . . . . . . 211
41.3 Grammaires Hors-Contexte . . . . . . . . . . . . . . . . . . 211

42 Calculabilité et Décidabilité . . . . . . . . . . 213


42.1 Décidabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
42.2 Classes de Complexité . . . . . . . . . . . . . . . . . . . . . 213

43 Concurrence et Synchronisation . . . . . . 215


32. Notions d’Architecture et de Système
33. Programmation Fonctionnelle
34. Programmation Impérative
35. Analyse des Programmes

35.1 Correction
35.2 Terminaison
35.3 Complexité
35.4 Induction Structurelle
36. Structures de Données

36.1 Structures Séquentielles


36.2 Structures Hiérarchiques
37. Graphes

37.1 Notion et Représentation


37.2 Algorithmique des Graphes
38. Algorithmique

38.1 Arithmétique
38.2 Méthodes Classiques
38.2.1 Algorithmes Gloutons
38.2.2 Programmation Dynamique
38.3 Algorithmes sur les Chaînes de Caractère
38.4 Algorithmes Probabilités
38.5 Algorithmique pour l’IA et les Jeux
39. Logique

39.1 Logique Propositionnelle et du Premier Ordre


39.2 Déduction Naturelle
40. Bases de Données

40.1 Théorie
40.2 SQL
41. Langages Formels

41.1 Langages Rationnels


41.2 Automates Finis
41.3 Grammaires Hors-Contexte
42. Calculabilité et Décidabilité

42.1 Décidabilité
42.2 Classes de Complexité
43. Concurrence et Synchronisation
VII Corrigés de MPSI

1 Raisonnement, Ensembles, Appli- 7.3 Digressions et Exercices Supplémentaires 231


cations et Relations . . . . . . . . 219
1.1 Raisonnements . . . . . . . . . . . . . . . . 219 8 Arithmétique . . . . . . . . . . . . . . 233
1.2 Ensembles . . . . . . . . . . . . . . . . . . . 219 8.1 Divisibilité, PGCD, PPCM . . . . . . . . 233
1.3 Applications et Relations . . . . . . . . . 219 8.2 Nombres premiers . . . . . . . . . . . . . . 233
1.4 Digressions et Exercices Supplémentaires 219 8.3 Digressions et exercices supplémentaires 233

2 Réels, Complexes, Trigonométrie, 9 Polynômes et Fractions Ration-


Sommes et Produits . . . . . . . . 221 nelles . . . . . . . . . . . . . . . . . . . . . 235
2.1 Compléments sur les Réels . . . . . . . . 221 9.1 Polynômes . . . . . . . . . . . . . . . . . . . 235
2.2 Complexes et Trigonométrie . . . . . . . 221 9.2 Fraction Rationnelles . . . . . . . . . . . . 235
2.3 Sommes et Produits . . . . . . . . . . . . 221 9.3 Digressions et Exercices Supplémentaires 235
2.4 Digressions et Exercices Supplémentaires 221
10 Algèbre Linéaire de Base . . . 237
3 Fonctions Usuelles : Dérivées, In- 10.1 Sous-Espaces et Applications Linéaires 237
tégrales, Équations Différentielles 10.2 Dimension Finie . . . . . . . . . . . . . . . 237
223
3.1 Dérivées . . . . . . . . . . . . . . . . . . . . . 223 11 Matrices . . . . . . . . . . . . . . . . . . 239
3.2 Intégrales . . . . . . . . . . . . . . . . . . . . 223
3.3 Équations Différentielles . . . . . . . . . . 223 12 Uniforme Continuité, Intégration
241
4 Suites, Limites, Continuité . . 225
4.1 Suites . . . . . . . . . . . . . . . . . . . . . . 225
4.2 Limites . . . . . . . . . . . . . . . . . . . . . 225
13 Séries . . . . . . . . . . . . . . . . . . . . . 243
4.3 Continuité . . . . . . . . . . . . . . . . . . . 225
14 Déterminants . . . . . . . . . . . . . . 245
5 Dérivation . . . . . . . . . . . . . . . . . 227 14.1 Groupe Symétrique . . . . . . . . . . . . . 245
5.1 Fonctions Dérivables . . . . . . . . . . . . 227 14.2 Déterminants . . . . . . . . . . . . . . . . . 245
5.2 Convexité . . . . . . . . . . . . . . . . . . . . 227
15 Espaces Vectoriels Préhilbertiens
6 Analyse Asymptotique . . . . . . 229 247
6.1 Analyse Asymptotique des Suites . . . 229
6.2 Développements Limités . . . . . . . . . . 229 16 Dénombrement . . . . . . . . . . . . 249
16.1 Théorie . . . . . . . . . . . . . . . . . . . . . 249
7 Structures Algébriques . . . . . . 231 16.2 Applications . . . . . . . . . . . . . . . . . . 249
7.1 Groupes . . . . . . . . . . . . . . . . . . . . . 231
7.2 Anneaux et Corps . . . . . . . . . . . . . . 231 17 Probabilités . . . . . . . . . . . . . . . 251
1. Raisonnement, Ensembles, Applications et
Relations

1.1 Raisonnements
1.2 Ensembles
1.3 Applications et Relations
1.4 Digressions et Exercices Supplémentaires
2. Réels, Complexes, Trigonométrie, Sommes et
Produits

2.1 Compléments sur les Réels


2.2 Complexes et Trigonométrie
2.3 Sommes et Produits
2.4 Digressions et Exercices Supplémentaires
3. Fonctions Usuelles : Dérivées, Intégrales,
Équations Différentielles

3.1 Dérivées
3.2 Intégrales
3.3 Équations Différentielles
4. Suites, Limites, Continuité

4.1 Suites
4.1.1 Suites Récurrentes
4.2 Limites
4.3 Continuité
5. Dérivation

5.1 Fonctions Dérivables


5.1.1 Quelques Calculs
5.1.2 Exercices Plus Théoriques
5.2 Convexité
6. Analyse Asymptotique

6.1 Analyse Asymptotique des Suites


6.2 Développements Limités
7. Structures Algébriques

7.1 Groupes
7.2 Anneaux et Corps
7.3 Digressions et Exercices Supplémentaires
8. Arithmétique

8.1 Divisibilité, PGCD, PPCM


8.2 Nombres premiers
8.3 Digressions et exercices supplémentaires
9. Polynômes et Fractions Rationnelles

9.1 Polynômes
9.2 Fraction Rationnelles
9.3 Digressions et Exercices Supplémentaires
10. Algèbre Linéaire de Base

10.1 Sous-Espaces et Applications Linéaires


10.2 Dimension Finie
11. Matrices
12. Uniforme Continuité, Intégration
13. Séries
14. Déterminants

14.1 Groupe Symétrique


14.2 Déterminants
Correction 14.16 L’idée est d’écrire la matrice concernée comme un produit de deux matrices dont
le déterminant est plus ou moins simple à calculer.
On a :
(
X X
n X
n
t t 1 si p | q
di,j = 1= ai,k aj,k = Ai,k Ak,j = (A A)i,j où ap,q =
k|i∧k|j k=1 k=1
0 sinon

La matrice A étant triangulaire, son déterminant est le produit de ses coefficients diagonaux, d’où
det A = 1, qui est le déterminant recherché. P
De même, si on se souvient miraculeusement de n = d|n φ(d), on écrit :
(
X X
n
φ(q) si q | p
δi,j = φ(k) = Φi,k tAk,j = (Φ tA)i,j où Φp,q =
k|i∧j k=1
0 sinon
Qn
La matrice Φ étant triangulaire, le déterminant cherché vaut k=1 φ(k).
15. Espaces Vectoriels Préhilbertiens
16. Dénombrement

16.1 Théorie
16.2 Applications
17. Probabilités
VIII 18
Corrigés de MP

Rappels et Compléments d’Analyse . . . 255


18.1 Sous-Ensembles de R . . . . . . . . . . . . . . . . . . . . . . 255
18.2 Séries Numériques . . . . . . . . . . . . . . . . . . . . . . . . 255

19 Intégrales Généralisées . . . . . . . . . . . . . . 257

20 Suites et Séries de Fonctions . . . . . . . . . 259


20.1 Suites de Fonctions . . . . . . . . . . . . . . . . . . . . . . . 259
20.2 Séries de Fonctions . . . . . . . . . . . . . . . . . . . . . . . 259

21 Intégrales à Paramètres . . . . . . . . . . . . . . 261

22 Structures Algébriques . . . . . . . . . . . . . . . 263


22.1 Groupes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
22.2 Anneaux et Corps . . . . . . . . . . . . . . . . . . . . . . . . 263
22.3 Digressions et Exercices Supplémentaires . . . . . . . . 263

23 Topologie . . . . . . . . . . . . . . . . . . . . . . . . . . 265
23.1 Topologie des Espaces Vectoriels Normés . . . . . . . . 265
23.2 Topologie des Espaces Vectoriels Normés de Dimension Fi-
nie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
23.3 Séries vectorielles . . . . . . . . . . . . . . . . . . . . . . . . 265
23.4 Connexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
23.5 Digressions et exercices supplémentaires . . . . . . . . . 265

24 Compléments d’Algèbre Linéaire . . . . . . 267

25 Réduction des Endomorphismes . . . . . . 269

26 Probabilités de Spé . . . . . . . . . . . . . . . . . 271


26.1 Dénombrabilité . . . . . . . . . . . . . . . . . . . . . . . . . . 271
26.2 Sommabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
26.3 Variables Aléatoires . . . . . . . . . . . . . . . . . . . . . . . 271
26.4 Séries Génératrices . . . . . . . . . . . . . . . . . . . . . . . 271

27 Fonctions Vectorielles . . . . . . . . . . . . . . . 273

28 Séries Entières . . . . . . . . . . . . . . . . . . . . . . 275


28.1 Séries Génératrices en Dénombrement . . . . . . . . . . 275

29 Espaces Euclidiens . . . . . . . . . . . . . . . . . . 277


29.1 Isométries et Matrices Orthogonales . . . . . . . . . . . 277
29.2 Endomorphismes Autoadjoints Positifs, Définis Positifs 277

30 Équations Différentielles Linéaires . . . . 279

31 Calcul Différentiel . . . . . . . . . . . . . . . . . . . 281


31.1 Géométrie Différentielle, un peu . . . . . . . . . . . . . . 281
18. Rappels et Compléments d’Analyse

18.1 Sous-Ensembles de R
18.2 Séries Numériques
19. Intégrales Généralisées
20. Suites et Séries de Fonctions

20.1 Suites de Fonctions


20.2 Séries de Fonctions
21. Intégrales à Paramètres
22. Structures Algébriques

22.1 Groupes
22.2 Anneaux et Corps
22.2.1 Nombres et Entiers Algébriques
22.3 Digressions et Exercices Supplémentaires
23. Topologie

23.1 Topologie des Espaces Vectoriels Normés


23.2 Topologie des Espaces Vectoriels Normés de Dimension Finie
23.3 Séries vectorielles
23.4 Connexité
23.5 Digressions et exercices supplémentaires
24. Compléments d’Algèbre Linéaire
25. Réduction des Endomorphismes
26. Probabilités de Spé

26.1 Dénombrabilité
26.2 Sommabilité
26.3 Variables Aléatoires
26.4 Séries Génératrices
27. Fonctions Vectorielles
28. Séries Entières

28.1 Séries Génératrices en Dénombrement


29. Espaces Euclidiens

29.1 Isométries et Matrices Orthogonales


29.2 Endomorphismes Autoadjoints Positifs, Définis Positifs
30. Équations Différentielles Linéaires
31. Calcul Différentiel

31.1 Géométrie Différentielle, un peu


IX Corrigés d’Informatique de
MP2I/MPI

32 Notions d’Architecture et de Système . 285

33 Programmation Fonctionnelle . . . . . . . . 287

34 Programmation Impérative . . . . . . . . . . . 289

35 Analyse des Programmes . . . . . . . . . . . . 291


35.1 Correction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291
35.2 Terminaison . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291
35.3 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291
35.4 Induction Structurelle . . . . . . . . . . . . . . . . . . . . . 291

36 Structures de Données . . . . . . . . . . . . . . 293


36.1 Structures Séquentielles . . . . . . . . . . . . . . . . . . . . 293
36.2 Structures Hiérarchiques . . . . . . . . . . . . . . . . . . . . 293

37 Graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295
37.1 Notion et Représentation . . . . . . . . . . . . . . . . . . . 295
37.2 Algorithmique des Graphes . . . . . . . . . . . . . . . . . . 295

38 Algorithmique . . . . . . . . . . . . . . . . . . . . . . 297
38.1 Arithmétique . . . . . . . . . . . . . . . . . . . . . . . . . . . 297
38.2 Méthodes Classiques . . . . . . . . . . . . . . . . . . . . . . 297
38.3 Algorithmes sur les Chaînes de Caractère . . . . . . . . 297
38.4 Algorithmes Probabilités . . . . . . . . . . . . . . . . . . . 297
38.5 Algorithmique pour l’IA et les Jeux . . . . . . . . . . . . 297

39 Logique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
39.1 Logique Propositionnelle et du Premier Ordre . . . . . 299
39.2 Déduction Naturelle . . . . . . . . . . . . . . . . . . . . . . . 299

40 Bases de Données . . . . . . . . . . . . . . . . . . . 301


40.1 Théorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301
40.2 SQL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301

41 Langages Formels . . . . . . . . . . . . . . . . . . . 303


41.1 Langages Rationnels . . . . . . . . . . . . . . . . . . . . . . 303
41.2 Automates Finis . . . . . . . . . . . . . . . . . . . . . . . . . 303
41.3 Grammaires Hors-Contexte . . . . . . . . . . . . . . . . . . 303

42 Calculabilité et Décidabilité . . . . . . . . . . 305


42.1 Décidabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305
42.2 Classes de Complexité . . . . . . . . . . . . . . . . . . . . . 305

43 Concurrence et Synchronisation . . . . . . 307


32. Notions d’Architecture et de Système
33. Programmation Fonctionnelle
34. Programmation Impérative
35. Analyse des Programmes

35.1 Correction
35.2 Terminaison
35.3 Complexité
Correction 35.1 On pose I les lignes ayant un nombre de 1 impair, et J les colonnes ayant un
nombre de 1 impair. On a alors :
— |I| + |J| = 0 mod 2, ce qui se démontre par récurrence sur le nombre de 1 dans le tableau.
— On ne peut pas faire mieux que max (|I| , |J|), car il faut au moins changer une valeur sur
chaque ligne et colonne erronnée.
— Enfin, on donne un algorithme qui résout bien ce problème en O(mn) :
— D’abord, on élimine des paires (ligne erronée, colonne erronée) en changeant la valeur à
leur intersection.
— Ensuite, ou bien on a fini, ou il reste ou un nombre pair non nul de ligne erronées ou un
nombre pair non nul de colonnes erronées.
— On peut enfin éliminer les paires de lignes (resp. de colonnes) en inversant deux valeurs
sur une même colonne (resp. ligne).
Cet algorithme agit bien en O(mn) puisque pour calculer I et J, il faut parcourir l’entièreté
de la matrice en O(mn). La résolution du problème se fait quant à elle en O(m + n) =
O(max(m, n))

35.4 Induction Structurelle


Correction 35.2 On note ν (X) le nombre de manière d’obtenir X avec c1 , . . . , cp . On va utiliser la
relation de récurrence suivante :
X
p
ν (X) = 1ci ≤X × ν (X − ci )
i=1

On propose alors le code OCamL suivant :

coins = [1, 2, 5, 10, 20, 50] (*On récupère les pièces sous forme de liste*)

let rec count = function


^^I| 0 -> 1
^^I| n ->
^^Ilet rec sumlist = function
^^I^^I| [] -> 0
^^I^^I| h::t -> h + (sumlist t)
^^Iin sumlist (List.map (k -> if k <= n then count (n - k) else 0))
;;
292 Chapitre 35. Analyse des Programmes

Correction 35.3 On montre par récurrence sur k que Nk = 3 × 22 −1


k

— Pour k = 1, il n’y a aucune condition sur l’unique case, on a donc 3 choix, et N1 = 3 =


3 × 20 = 3 × 22 −1
0

— Par récurrence, soit une configuration de la première moitié du tableau, on a maintenant la


deuxième moitié du tableau à choisir. Pour chaque couple (T [2i + 1], T [2i + 2]), on a que deux
choix, qui sont les deux couleurs (a puis b ou b puis a) non utilisées par T [i]. On trouve donc
k−2
Nk+1 = Nk × 22 . En résolvant la relation de récurrence, on obtient bien le résultat.
36. Structures de Données

36.1 Structures Séquentielles


Correction 36.1 Dans la représentation d’une permutation, aucun élément ne peut apparaître deux
fois, on ne peut pas avoir une sous-chaîne plus grande pour l’ordre lexicographique. Ainsi, le tableau
J0, N K est minimal, et le tableau N, N − 1, · · · , 0 est maximal.
La première étape consiste à trouver la plus grande partie à droite du tableau qui est triée dans
l’ordre décroissant, et se termine par 0. On prend alors l’élément précédant la partie triée du tableau
(s’il n’existe pas alors on a atteint la dernière permutation et on décidera d’une valeur arbitraire de
renvoi), et on l’échange avec le premier élément supérieur dans la partie triée. Enfin, on ré-inverse
la suite décroissante, pour avoir l’élément le plus petit possible.

36.2 Structures Hiérarchiques


37. Graphes

37.1 Notion et Représentation


37.2 Algorithmique des Graphes
38. Algorithmique

38.1 Arithmétique
38.2 Méthodes Classiques
38.2.1 Algorithmes Gloutons
38.2.2 Programmation Dynamique
38.3 Algorithmes sur les Chaînes de Caractère
38.4 Algorithmes Probabilités
38.5 Algorithmique pour l’IA et les Jeux
39. Logique

39.1 Logique Propositionnelle et du Premier Ordre


39.2 Déduction Naturelle
40. Bases de Données

40.1 Théorie
40.2 SQL
41. Langages Formels

41.1 Langages Rationnels


41.2 Automates Finis
41.3 Grammaires Hors-Contexte
42. Calculabilité et Décidabilité

42.1 Décidabilité
42.2 Classes de Complexité
43. Concurrence et Synchronisation
Bibliographie
Index

Congruences . . . . . . . . . . . . . . . . . . . . . . . . . . 21
A Conjugaison . . . . . . . . . . . . . . . . . . . . . . . . . . 54
Connexité. . . . . . . . . . . . . . . . . . . . . . . . . . . . .77
Algèbre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 Construction
Algébricité . . . . . . . . . . . . . . . . . . . . 59, 74, 83 d’une Application . . . . . . . . . . . . . . . . . 24
Alignement . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 Continue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
Analyse Continuité . . . . . . . . . . . . . . . . . . . . . . . . 21, 77
Complexe . . . . . . . . . . . . . . . . . . . . . . . . . 72 Contrôle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
Analyticité. . . . . . . . . . . . . . . . . . . . . . . . . . . .84 Convexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
Anneau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 Corps . . . . . . . . . . . . . . . . . . . . . . 74, 83, 87, 88
Application . . . . . . . . . . . . . . . . . . . . . . . 23, 24 Extension. . . . . . . . . . . . . . . . . . . . . . . . .88
Arctangente . . . . . . . . . . . . . . . . . . . . . . . . . . 28 Fini . . . . . . . . . . . . . . . . . . . . . . . . . . . 74, 75
Argument. . . . . . . . . . . . . . . . . . . . . . . . . . . . .27 Fractions . . . . . . . . . . . . . . . . . . . . . . . . . 81
Arithmétique . . . . . . . . . . . . . . . . . . . . . . . . . 74 Critère
Attila . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 de Cauchy . . . . . . . . . . . . . . . . . . . . . . . . 89
de D’Alembert . . . . . . . . . . . . . . . . . . . . 66
B

Banach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 D
Base
D’Alembert . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
Orthonormée . . . . . . . . . . . . . . . . . . . . . 56
Densité . . . . . . . . . . . . . . . . . . . . . . . . . . . 66, 73
Bijection . . . . . . . . . . . . . . . . . . . . . . 23, 24, 83
Diagonalisabilité . . . . . . . . . . . . . . . . . . . . . . 81
Billard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
Différentielle . . . . . . . . . . . . . . . . . . . . . . . . . . 95
Borne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
Distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
Supérieure . . . . . . . . . . . . . . . . . . . . . . . . 24
Diviseurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
Boule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
Divisibilité . . . . . . . . . . . . . . . . . . . . . . . . 53, 74
Droite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59, 91
C
Décomposition
Caractérisation . . . . . . . . . . . . . . . . . . . . . . . 77 Polaire . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
Cardinal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 Dénombrabilité . . . . . . . . . . . . . . . . 24, 51, 83
Cercle Unité . . . . . . . . . . . . . . . . . . . . . . . . . . 66 Dénombrement . . . . . . . . . . . . 53, 56, 59, 89
Cesàro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 Dérivée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
Classe Déterminant . . . . . . . . 53–56, 61, 69, 77, 95
C 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 d’Hurwitz . . . . . . . . . . . . . . . . . . . . . . . . 54
C ∞ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 de Cauchy . . . . . . . . . . . . . . . . . . . . . . . . 55
D1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 de Gram . . . . . . . . . . . . . . . . . . . . . . . . . . 56
Classes d’équivalence. . . . . . . . . . . . . . . . . .23 de Smith . . . . . . . . . . . . . . . . . . . . . . . . . 56
Comatrice . . . . . . . . . . . . . . . . . . . . . . . . . 54, 87 de Vandermonde . . . . . . . . . . . . . . 54, 55
Combinatoire . . . . . . . . . . . . . . . . . . . . . 54, 56 Développement
Commutativité . . . . . . . . . . . . . 47, 53, 73–75 Asymptotique . . . . . . . . . . . . . . . . . . . . 66
Compacité . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 Développement Limité . . . . . . . . . . . . . . . . 95
Complémentaire . . . . . . . . . . . . . . . . . . . . . . 22 Dévissage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
312 Index

Interversion
E Dérivée-Intégrale. . . . . . . . . . . . . . . . . .71
Dérivée-Somme . . . . . . . . . . . . . . . . . . . 69
Ellipse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 Limite-Intégrale . . . . . . . . . . . . . . . 69, 71
Elément Limite-Somme . . . . . . . . . . . . . . . . . . . . 70
Maximal . . . . . . . . . . . . . . . . . . . . . . . . . . 24 Somme-Intégrale . . . . . . . . . . . . . . 70, 71
Endomorphisme Somme-Somme . . . . . . . . . . . . . . . . . . . 84
Autoadjoint. . . . . . . . . . . . . . . . . . . . . . .91 Intégrabilité . . . . . . . . . . . . . . . . . . . . . . . . . . 68
Orthogonal . . . . . . . . . . . . . . . . . . . . . . . 91 Intégrale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
Ensemble . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 Généralisée . . . . . . . . . . . . . . . . 67, 68, 71
Fini . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 Vectorielle . . . . . . . . . . . . . . . . . . . . . . . . 87
Transitif . . . . . . . . . . . . . . . . . . . . . . . . . . 22 Wallis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
Equation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .27 Involution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
Equipotence . . . . . . . . . . . . . . . . . . . . . . . . . . 24 Inégalité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
Equivalent . . . . . . . . . . . . . . . . . . . . . . . . 66, 67 Irrationalité . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
Espace
Euclidien . . . . . . . . . . . . . . . . . . . . . . . . . 78 L
Exponentielle
Matrice . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 Lemme
des pics . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
F SI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
Limite . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23, 34
Famille Limite Inférieure . . . . . . . . . . . . . . . . . . . . . . 65
Libre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 Limite Supérieure . . . . . . . . . . . . . . . . . . . . . 65
Feynman. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .71 Linéarité . . . . . . . . . . . . . . . . . . . . . . . . . . 21, 53
Figure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 Lipschitz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
Fonction Loi
Caractéristique . . . . . . . . . . . . . . . . . . . 61 de Rademacher . . . . . . . . . . . . . . . . . . . 84
Polynômiale . . . . . . . . 23, 69, 77, 87, 91 de Snell-Descartes . . . . . . . . . . . . . . . . 95
Forme Linéaire . . . . . . . . . . . . . . . . . . . . . . . . 77 Uniforme . . . . . . . . . . . . . . . . . . . . . . . . . 61
Formule
de Cauchy-Binet . . . . . . . . . . . . . . . . . . 54 M
de Williamsom. . . . . . . . . . . . . . . . . . . .54
Fractions Rationelles . . . . . . . . . . . . . . . . . . 81 Marche Aléatoire . . . . . . . . . . . . . . . . . . . . . 84
Frontière . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 Matrice . . . . . . . . . . . . . . . . . . . . . . . . 47, 69, 77
Circulante . . . . . . . . . . . . . . . . . . . . . . . . 56
G d’Incidence . . . . . . . . . . . . . . . . . . . . . . . 56
de Gram . . . . . . . . . . . . . . . . . . . . . . 56, 57
Gamma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 Extraite . . . . . . . . . . . . . . . . . . . . . . . . . . 54
Groupe . . . . . . . . . . . . . . . . . . . . . . . . . . . 73, 78 Maximum. . . . . . . . . . . . . . . . . . . . . . . . . . . . .34
Abélien . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 Module . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
Centre . . . . . . . . . . . . . . . . . . . . . . . . 73–75
Fini . . . . . . . . . . . . . . . . . . . . . . . . . . . 73, 74 N
Non-Abélien . . . . . . . . . . . . . . . . . . . . . . 73
Réel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 Nombre
Spécial Linéaire . . . . . . . . . . . . . . . . . . . 76 Complexe . . . . . . . . . . . . . . . . . . . . . . . . . 27
Symétrique. . . . . . . . . . . . . . . . . . . .53, 61 Norme . . . . . . . . . . . . . . . . . . . . . . . . . 77, 78, 88
Géométrie . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 Algèbre . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
d’Opérateur . . . . . . . . . . . . . . . . . . . . . . 77
I
O
Injection . . . . . . . . . . . . . . . . . . . . . . . . . . 23, 24
Inscrit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 Oral
INDEX 313

CCP . . . . . . . . . . . . . . . . . . . . . . . . . . 27, 89 Suite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21, 68


Ulm . . . . . . . . . . . . . . . . . . . . . . . 56, 66, 83 de Matrices . . . . . . . . . . . . . . . . . . . . . . . 47
X . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54, 70 Fonction . . . . . . . . . . . . . . . . . . . . . . . . . . 69
Orbite . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74, 75 Fonctions . . . . . . . . . . . . . . . . . . . . . . . . . 71
Ordre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 Monotone. . . . . . . . . . . . . . . . . . . . . . . . .21
Récurrente. . . . . . . . . . . . . . . . . . . . . . . .68
P Support Fini . . . . . . . . . . . . . . . . . . . . . . 83
Suite monotone . . . . . . . . . . . . . . . . . . . . . . . 31
Parallélotope. . . . . . . . . . . . . . . . . . . . . . . . . .56 Surjection. . . . . . . . . . . . . . . . . . . . . . . . . . . . .23
Parties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 Série
Partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 de Laurent . . . . . . . . . . . . . . . . . . . . 70, 83
Permutation . . . . . . . . . . . . . . . . . . . . . . 51, 56 Entière. . . . . . . . . . . . . . . . . . . . . . . .84, 89
Point. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .59, 91 Fonction . . . . . . . . . . . . . . . . . . . . . . 69, 70
Point Fixe . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 Génératrice . . . . . . . . . . . . . . . . . . . 84, 89
Polynôme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 Numérique
Cyclotomique . . . . . . . . . . . . . . . . . 74, 75 Complexe, 66, 83
Irréductible . . . . . . . . . . . . . . . . . . . . . . . 75 Entière, 66
Polynômes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 Réelle, 51, 66, 83, 84
Probabilité . . . . . . . . . . . . . . . . . . . . . . . . 73, 84 Vectorielle . . . . . . . . . . . . . . . . . . . . . . . . 87
Probabilités . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
Processus Stochastique . . . . . . . . . . . . . . . . 84 T
Produit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
Produit Eulérien . . . . . . . . . . . . . . . . . . . . . . 84 Table de vérité . . . . . . . . . . . . . . . . . . . . . . . . 22
Préordre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 Théorie
Période . . . . . . . . . . . . . . . . . . . . . . . . . . . 66, 70 de Galois . . . . . . . . . . . . . . . . . . . . . . . . . 76
Théorème
Q de Bolzano-Weierstrass . . . . . . . . . . . 31
de Cantor . . . . . . . . . . . . . . . . . . . . . . . . 22
Quantificateurs . . . . . . . . . . . . . . . . . . . . . . . 21 de Cantor-Bernstein . . . . . . . . . . . . . . 24
Quotient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 de Cayley-Hamilton . . . . . . . . . . . 81, 87
de Cesàro . . . . . . . . . . . . . . . . . . . . . . . . . 65
de D’Alembert-Gauss . . . . . . . . . . . . . 72
R
de Lagrange . . . . . . . . . . . . . . . . . . . 73, 74
Racine Carrée . . . . . . . . . . . . . . . . . . . . . 21, 91 de Pringsheim . . . . . . . . . . . . . . . . . . . . 66
Racine de l’Unité . . . . . . . . . . . . . . . . . . . . . 27 de Réarrangement de Riemann . . . . 51
Racines de l’Unité . . . . . . . . . . . . . . . . . . . . 83 de Weierstrass . . . . . . . . . . . . . . . . . . . . 69
Rang . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57, 77 Transvection . . . . . . . . . . . . . . . . . . . . . . . . . . 76
Rationnels . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 Treillis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
Rayon de Convergence . . . . . . . . . . . . . . . . 89 Trigonométrie . . . . . . . . . . . . . . . . . . . . . . . . . 27
Relation
d’Ordre . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 V
d’Équivalence . . . . . . . . . . . . . . . . . 23, 78
Réels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 Valeur d’Adhérence . . . . . . . . . . . . . . . . . . . 65
Variable
S Aléatoire . . . . . . . . . . . . . . . . . . . . . . . . . 61
Variable Aléatoire. . . . . . . . . . . . . . . . . . . . .84
Semi-Convergence. . . . . . . . . . . . . . . . . . . . .51 Volume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
Similitude . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
Sommabilité . . . . . . . . . . . . . . . . . . . 68, 83, 84
Somme
Double . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
Sous-Groupe. . . . . . . . . . . . . . . . . . .66, 73, 74
Sous-suite . . . . . . . . . . . . . . . . . . . . . . . . . 21, 31

Vous aimerez peut-être aussi