[PDF] Calcul mathématique avec Sage

View - Download Calcul mathématique avec Sage

Previous PDF

Next PDF

Calcul mathématique avec

SAGE

Calcul mathématique avec Sage

Alexandre Casamayou Nathann Cohen

Guillaume Connan Thierry Dumont Laurent Fousse

François Maltey Matthias Meulien Marc Mezzarobba Clément Pernet Nicolas M. Thiéry Paul Zimmermann C Cette œuvre est mise à disposition selon les termes de la licenceCreative Commons Paternité - Partage dans les mêmes conditions 3.0 France(cc by-sa 3.0 fr). Extrait dehttp://creativecommons.org/licenses/by-sa/3.0/fr/deed.fr: Ceci est le résumé explicatif "lisible par les humains" du Code Juridique (la version intégrale de la licence).

Vous êtes libre de :

- partager - reproduire, distribuer et communiquer l"œuvre - remixer - adapter l"œuvre - d"utiliser cette œuvre à des fins commerciales

Selon les conditions suivantes :

b Attribution - Vous devez attribuer l"œuvre de la manière indiquée par l"auteur de l"œuvre ou le titulaire des droits (mais pas d"une manière qui suggérerait qu"ils vous approuvent, vous ou votre utilisation de l"œuvre). a Partage dans les Mêmes Conditions - Si vous modifiez, transformez ou adaptez cette œuvre, vous n"avez le droit de distribuer votre création que sous une licence identique ou similaire à celle-ci. comprenant bien que : Renonciation - N"importe laquelle des conditions ci-dessus peut être levée si vous avez l"autorisation du titulaire de droits. Domaine Public - Là où l"œuvre ou un quelconque de ses éléments est dans le domaine public selon le droit applicable, ce statut n"est en aucune façon affecté par la licence. Autres droits - Les droits suivants ne sont en aucune manière affectés par la licence : Vos prérogatives issues des exceptions et limitations aux droits exclusifs ou fair use; - Les droits moraux de l"auteur; Droits qu"autrui peut avoir soit sur l"œuvre elle-même soit sur la façon dont elle est utilisée, comme le droit à l"image ou les droits à la vie privée. Remarque - A chaque réutilisation ou distribution de cette œuvre, vous devez faire apparaître clairement au public la licence selon laquelle elle est mise à disposition. La meilleure manière de l"indiquer est un lien vers cette page web. Des parties de cet ouvrage sont inspirées de l"ouvrageCalcul formel : mode d"emploi. Exemples en Maplede Philippe Dumas, Claude Gomez, Bruno Salvy et Paul Zimmermann [DGSZ95], diffusé sous la même licence, notamment les sections2.1.5,2.3.5et5.3. Une partie des exemples Sage du chapitre15sont tirés du tutoriel des logiciels

MuPAD-Combinat [

HT04] et Sage-combinat. Le dénombrement des arbres binaires complets de §15.1.2est en partie inspiré d"un sujet de TP de Florent Hivert. L"exercice9sur le problème de Gauss est tiré d"un problème de François

Pantigny et l"exercice

17sur l"effet Magnus est extrait d"un TD de Jean-Guy

Stoliaroff.

Les graphiques de la figure4.9et leur interprétation reproduisent une partie du paragraphe III.4 du " Que sais-je? »Les nombres premiersde Gérald Tenenbaum et Michel Mendès France [TMF00].

Préface

Ce livre est destiné à tous ceux qui désirent utiliser efficacement un système de calcul mathématique, en particulier le logiciel Sage. Ces systèmes offrent une multitude de fonctionnalités, et trouver comment résoudre un problème donné n"est pas toujours facile. Un manuel de référence fournit une description analytique et en détail de chaque fonction du système; encore faut-il savoir le nom de la fonction que l"on cherche! Le point de vue adopté ici est complémentaire, en donnant une vision globale et synthétique, avec un accent sur les mathématiques sous-jacentes, les classes de problèmes que l"on sait résoudre et les algorithmes correspondants. La première partie, plus spécifique au logiciel Sage, constitue une prise en main du système. Cette partie se veut accessible à tous les étudiants scientifiques (BTS, IUT, classes préparatoires, licence), et dans une certaine mesure aux élèves des lycées. Les autres parties s"adressent à des étudiants au niveau agrégation. Contrairement à un manuel de référence, les concepts mathématiques sont claire- ment énoncés avant d"illustrer leur mise en œuvre avec Sage. Ce livre est donc aussi un livre sur les mathématiques. Pour illustrer cet ouvrage, le choix s"est porté naturellement vers Sage, car c"est un logiciel libre, que tout un chacun peut utiliser, modifier et redistribuer à loisir. Ainsi l"élève qui a appris Sage au lycée pourra l"utiliser quelle que soit sa voie professionnelle : en licence, master, doctorat, en école d"ingénieur, en entreprise, etc. Sage est un logiciel encore jeune par rapport aux logiciels concurrents, et malgré ses capacités déjà étendues, il comporte encore de nombreuxbogues. Mais par sa communauté très active de développeurs, Sage évolue très vite. Chaque utilisateur de Sage peut rapporter un bogue - et éventuellement sa solution - surtrac.sagemath.orgou via la listesage-support. Pour rédiger ce livre, nous avons utilisé la version 5.9 de Sage. Néanmoins, les exemples doivent fonctionner avec toute version ultérieure. Par contre, certaines affirmations pourraient ne plus être vérifiées, comme par exemple le fait que Sage utilise Maxima pour évaluer des intégrales numériques. Quand j"ai proposé en décembre 2009 à Alexandre Casamayou, Guillaume Connan, Thierry Dumont, Laurent Fousse, François Maltey, Matthias Meulien, Marc Mezzarobba, Clément Pernet et Nicolas Thiéry d"écrire un livre sur Sage, tous ont répondu présent, malgré une charge de travail déjà importante, comme Nathann Cohen qui nous a rejoint dans cette aventure. Je tiens à les remercier, no- tamment pour le respect du planning serré que j"avais fixé, et plus particulièrement iv Nathann Cohen, Marc Mezzarobba et Nicolas Thiéry pour leur investissement décisif dans la dernière ligne droite. Tous les auteurs remercient les personnes suivantes qui ont relu des versions préliminaires de ce livre : Gaëtan Bisson, Françoise Jung, Hugh Thomas, Anne Vaugon, Sébastien Desreux, Pierrick Gaudry, Maxime Huet, Jean Thiéry, Muriel Shan Sei Fan, Timothy Walsh, Daniel Duparc, Kévin Rowanet et Kamel Naroun (une mention spéciale à tous les deux qui ont relevé des coquilles qui avaient résisté à 17 relectures); ainsi qu"Emmanuel Thomé pour son aide précieuse lors de la réalisation de ce livre, Sylvain Chevillard, Gaëtan Bisson et Jérémie Detrey pour leurs conseils typographiques avisés et les erreurs qu"ils ont relevées. Le dessin de la couverture a été réalisé par Corinne Thiéry, sur une idée originale d"Albane Saintenoy. En rédigeant ce livre, nous avons beaucoup appris sur Sage, nous avons bien sûr rencontré quelques bogues, dont certains sont déjà corrigés. Nous espérons que ce livre sera utile à d"autres, lycéens, étudiants, professeurs, ingénieurs, cher- cheurs ou amateurs! Cet ouvrage comportant certainement encore de nombreuses imperfections, nous attendons en retour du lecteur qu"il nous fasse part de toute erreur, critique ou suggestion pour une version ultérieure; merci d"utiliser pour cela la pagesagebook.gforge.inria.fr.

Nancy, France

Mai 2013

Paul Zimmermann

Table des matières

I Prise en main de Sage1

1 Premiers pas3

1.1 Le logiciel Sage. . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.1.1 Un outil pour les mathématiques. . . . . . . . . . . . . 3

1.1.2 Accès à Sage. . . . . . . . . . . . . . . . . . . . . . . . . 5

1.1.3 Ressources. . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.2 Sage comme calculatrice. . . . . . . . . . . . . . . . . . . . . . . 8

1.2.1 Premiers calculs. . . . . . . . . . . . . . . . . . . . . . . 8

1.2.2 Fonctions élémentaires et constantes usuelles. . . . . . . . 11

1.2.3 Aide en ligne et complétion automatique. . . . . . . . . 13

1.2.4 Variables Python. . . . . . . . . . . . . . . . . . . . . . 13

1.2.5 Variables symboliques. . . . . . . . . . . . . . . . . . . . 15

1.2.6 Premiers graphiques. . . . . . . . . . . . . . . . . . . . . 16

2 Analyse et algèbre17

2.1 Expressions symboliques et simplification. . . . . . . . . . . . . 17

2.1.1 Expressions symboliques. . . . . . . . . . . . . . . . . . 17

2.1.2 Transformation d"expressions. . . . . . . . . . . . . . . . 18

2.1.3 Fonctions mathématiques usuelles. . . . . . . . . . . . . 20

2.1.4 Hypothèses sur une variable symbolique. . . . . . . . . . 22

2.1.5 Quelques dangers. . . . . . . . . . . . . . . . . . . . . . 22

2.2 Équations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

2.2.1 Résolution explicite. . . . . . . . . . . . . . . . . . . . . 24

2.2.2 Équations sans solution explicite. . . . . . . . . . . . . . 26

2.3 Analyse. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

2.3.1 Sommes. . . . . . . . . . . . . . . . . . . . . . . . . . . 27

2.3.2 Limites. . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.3.3 Suites. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

2.3.4 Développements limités. . . . . . . . . . . . . . . . . . . 30

2.3.5 Séries. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

2.3.6 Dérivation. . . . . . . . . . . . . . . . . . . . . . . . . . 33

2.3.7 Dérivées partielles. . . . . . . . . . . . . . . . . . . . . . 33

2.3.8 Intégration. . . . . . . . . . . . . . . . . . . . . . . . . . 34

2.4 Algèbre linéaire élémentaire. . . . . . . . . . . . . . . . . . . . . 35

2.4.1 Résolution de systèmes linéaires. . . . . . . . . . . . . . 36

viTABLE DES MATIÈRES

2.4.2 Calcul vectoriel. . . . . . . . . . . . . . . . . . . . . . . 36

2.4.3 Calcul matriciel. . . . . . . . . . . . . . . . . . . . . . . 37

2.4.4 Réduction d"une matrice carrée. . . . . . . . . . . . . . 38

3 Programmation et structures de données41

3.1 Syntaxe. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

3.1.1 Syntaxe générale. . . . . . . . . . . . . . . . . . . . . . . 42

3.1.2 Appel de fonctions. . . . . . . . . . . . . . . . . . . . . 43

3.1.3 Compléments sur les variables. . . . . . . . . . . . . . . 43

3.2 Algorithmique. . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

3.2.1 Les boucles. . . . . . . . . . . . . . . . . . . . . . . . . . 45

3.2.2 Les tests. . . . . . . . . . . . . . . . . . . . . . . . . . . 52

3.2.3 Les procédures et les fonctions. . . . . . . . . . . . . . . 53

3.2.4 Exemple : exponentiation rapide. . . . . . . . . . . . . . 56

3.2.5 Affichage et saisie. . . . . . . . . . . . . . . . . . . . . . 59

3.3 Listes et structures composées. . . . . . . . . . . . . . . . . . . 60

3.3.1 Définition des listes et accès aux éléments. . . . . . . . . 60

3.3.2 Opérations globales sur les listes. . . . . . . . . . . . . . 62

3.3.3 Principales méthodes sur les listes. . . . . . . . . . . . . 66

3.3.4 Exemples de manipulation de listes. . . . . . . . . . . . 68

3.3.5 Chaînes de caractères. . . . . . . . . . . . . . . . . . . . 69

3.3.6 Structure partagée ou dupliquée. . . . . . . . . . . . . . 70

3.3.7 Données modifiables ou immuables. . . . . . . . . . . . 72

3.3.8 Ensembles finis. . . . . . . . . . . . . . . . . . . . . . . 73

3.3.9 Dictionnaires. . . . . . . . . . . . . . . . . . . . . . . . . 74

4 Graphiques77

4.1 Courbes en 2D. . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

4.1.1 Représentation graphique de fonctions. . . . . . . . . . 77

4.1.2 Courbe paramétrée. . . . . . . . . . . . . . . . . . . . . 80

4.1.3 Courbe en coordonnées polaires. . . . . . . . . . . . . . 80

4.1.4 Courbe définie par une équation implicite. . . . . . . . . . 81

4.1.5 Tracé de données. . . . . . . . . . . . . . . . . . . . . . 83

4.1.6 Tracé de solution d"équation différentielle. . . . . . . . . 87

4.1.7 Développée d"une courbe. . . . . . . . . . . . . . . . . . . 91

4.2 Courbes en 3D. . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

5 Domaines de calcul97

5.1 Sage est orienté objet. . . . . . . . . . . . . . . . . . . . . . . . 97

5.1.1 Objets, classes et méthodes. . . . . . . . . . . . . . . . . 97

5.1.2 Objets et polymorphisme. . . . . . . . . . . . . . . . . . 99

5.1.3 Introspection. . . . . . . . . . . . . . . . . . . . . . . . . 100

5.2 Éléments, parents, catégories. . . . . . . . . . . . . . . . . . . . . 101

5.2.1 Éléments et parents. . . . . . . . . . . . . . . . . . . . . . 101

5.2.2 Constructions. . . . . . . . . . . . . . . . . . . . . . . . 102

5.2.3 Complément : catégories. . . . . . . . . . . . . . . . . . 103

TABLE DES MATIÈRESvii

5.3 Domaines de calcul à représentation normale. . . . . . . . . . . 103

5.3.1 Domaines de calcul élémentaires. . . . . . . . . . . . . . 105

5.3.2 Domaines composés. . . . . . . . . . . . . . . . . . . . . 109

5.4 Expressions versus domaines de calcul. . . . . . . . . . . . . . . . 111

5.4.1 Les expressions comme domaine de calcul. . . . . . . . . . 111

5.4.2 Exemples : polynômes et formes normales. . . . . . . . 112

5.4.3 Exemple : factorisation des polynômes. . . . . . . . . . 113

5.4.4 Synthèse. . . . . . . . . . . . . . . . . . . . . . . . . . . 114

II Algèbre et calcul formel117

6 Corps finis et théorie des nombres119

6.1 Anneaux et corps finis. . . . . . . . . . . . . . . . . . . . . . . . 119

6.1.1 Anneau des entiers modulon. . . . . . . . . . . . . . . . 119

6.1.2 Corps finis. . . . . . . . . . . . . . . . . . . . . . . . . . . 121

6.1.3 Reconstruction rationnelle. . . . . . . . . . . . . . . . . 122

6.1.4 Restes chinois. . . . . . . . . . . . . . . . . . . . . . . . 123

6.2 Primalité. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

6.3 Factorisation et logarithme discret. . . . . . . . . . . . . . . . . 127

6.4 Applications. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128

6.4.1 La constanteδ. . . . . . . . . . . . . . . . . . . . . . . . 128

6.4.2 Calcul d"intégrale multiple via reconstruction rationnelle129

7 Polynômes131

7.1 Anneaux de polynômes. . . . . . . . . . . . . . . . . . . . . . . 132

7.1.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . 132

7.1.2 Construction d"anneaux de polynômes. . . . . . . . . . 132

7.1.3 Polynômes. . . . . . . . . . . . . . . . . . . . . . . . . . 134

7.2 Arithmétique euclidienne. . . . . . . . . . . . . . . . . . . . . . 137

7.2.1 Divisibilité. . . . . . . . . . . . . . . . . . . . . . . . . . 137

7.2.2 Idéaux et quotients. . . . . . . . . . . . . . . . . . . . . 140

7.3 Factorisation et racines. . . . . . . . . . . . . . . . . . . . . . . . 141

7.3.1 Factorisation. . . . . . . . . . . . . . . . . . . . . . . . . 142

7.3.2 Recherche de racines. . . . . . . . . . . . . . . . . . . . 143

7.3.3 Résultant. . . . . . . . . . . . . . . . . . . . . . . . . . . 145

7.3.4 Groupe de Galois. . . . . . . . . . . . . . . . . . . . . . 146

7.4 Fractions rationnelles. . . . . . . . . . . . . . . . . . . . . . . . 147

7.4.1 Construction et propriétés élémentaires. . . . . . . . . . 147

7.4.2 Décomposition en éléments simples. . . . . . . . . . . . 147

7.4.3 Reconstruction rationnelle. . . . . . . . . . . . . . . . . 149

7.5 Séries formelles. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151

7.5.1 Opérations sur les séries tronquées. . . . . . . . . . . . . 152

7.5.2 Développement de solutions d"équations. . . . . . . . . . 154

7.5.3 Séries paresseuses. . . . . . . . . . . . . . . . . . . . . . 155

7.6 Représentation informatique des polynômes. . . . . . . . . . . . 156

viiiTABLE DES MATIÈRES

8 Algèbre linéaire159

8.1 Constructions et manipulations élémentaires. . . . . . . . . . . 159

8.1.1 Espaces de vecteurs, de matrices. . . . . . . . . . . . . . 159

8.1.2 Construction des matrices et des vecteurs. . . . . . . . . . 161

8.1.3 Manipulations de base et arithmétique sur les matrices. 162

8.1.4 Opérations de base sur les matrices. . . . . . . . . . . . 164

8.2 Calculs sur les matrices. . . . . . . . . . . . . . . . . . . . . . . 164

8.2.1 Élimination de Gauss, forme échelonnée. . . . . . . . . . 165

8.2.2 Résolution de systèmes; image et base du noyau. . . . . 172

8.2.3Valeurs propres, forme de Jordan et transformations de

similitude. . . . . . . . . . . . . . . . . . . . . . . . . . . 174

9 Systèmes polynomiaux183

9.1 Polynômes à plusieurs indéterminées. . . . . . . . . . . . . . . . 183

9.1.1 Les anneauxA[x1,...,xn]. . . . . . . . . . . . . . . . . 183

9.1.2 Polynômes. . . . . . . . . . . . . . . . . . . . . . . . . . 185

9.1.3 Opérations de base. . . . . . . . . . . . . . . . . . . . . 187

9.1.4 Arithmétique. . . . . . . . . . . . . . . . . . . . . . . . . 187

9.2 Systèmes polynomiaux et idéaux. . . . . . . . . . . . . . . . . . 188

9.2.1 Un premier exemple. . . . . . . . . . . . . . . . . . . . . 188

9.2.2 Qu"est-ce que résoudre?. . . . . . . . . . . . . . . . . . 192

9.2.3 Idéaux et systèmes. . . . . . . . . . . . . . . . . . . . . 192

9.2.4 Élimination. . . . . . . . . . . . . . . . . . . . . . . . . 197

9.2.5 Systèmes de dimension zéro. . . . . . . . . . . . . . . . 203

9.3.1 Ordres monomiaux. . . . . . . . . . . . . . . . . . . . . 208

9.3.2 Division par une famille de polynômes. . . . . . . . . . 209

9.3.5 Calcul. . . . . . . . . . . . . . . . . . . . . . . . . . . . 217

10 Équations différentielles et récurrences221

10.1 Équations différentielles. . . . . . . . . . . . . . . . . . . . . . . . 221

10.1.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . 221

10.1.2 Équations différentielles ordinaires d"ordre 1. . . . . . . 222

10.1.3 Équations d"ordre 2. . . . . . . . . . . . . . . . . . . . . 230

10.1.4 Transformée de Laplace. . . . . . . . . . . . . . . . . . . . 231

10.1.5 Systèmes différentiels linéaires. . . . . . . . . . . . . . . 233

10.2 Suites définies par une relation de récurrence. . . . . . . . . . . 235

10.2.1 Suites définies parun+1=f(un). . . . . . . . . . . . . . 235

10.2.2 Suites récurrentes linéaires. . . . . . . . . . . . . . . . . 237

10.2.3 Suites récurrentes " avec second membre ». . . . . . . . 238

TABLE DES MATIÈRESix

III Calcul numérique239

11 Nombres à virgule flottante241

11.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241

11.1.1 Définition. . . . . . . . . . . . . . . . . . . . . . . . . . . 241

11.1.2 Propriétés, exemples. . . . . . . . . . . . . . . . . . . . 242

11.1.3 Normalisation. . . . . . . . . . . . . . . . . . . . . . . . 242

11.2 Les nombres flottants. . . . . . . . . . . . . . . . . . . . . . . . 243

11.2.1 Quel type de nombres choisir?. . . . . . . . . . . . . . . 245

11.3 Propriétés des nombres à virgule flottante. . . . . . . . . . . . . 245

11.3.1 Des ensembles pleins de trous. . . . . . . . . . . . . . . 245

11.3.2 L"arrondi. . . . . . . . . . . . . . . . . . . . . . . . . . . 246

11.3.3 Quelques propriétés. . . . . . . . . . . . . . . . . . . . . 246

11.3.4 Nombres flottants complexes. . . . . . . . . . . . . . . . . 251

11.3.5 Méthodes. . . . . . . . . . . . . . . . . . . . . . . . . . . 252

11.4 En guise de conclusion. . . . . . . . . . . . . . . . . . . . . . . . 253

12 Équations non linéaires255

12.1 Équations algébriques. . . . . . . . . . . . . . . . . . . . . . . . 255

12.1.1 MéthodePolynomial.roots(). . . . . . . . . . . . . . . 255

12.1.2 Représentation des nombres. . . . . . . . . . . . . . . . 256

12.1.3 Théorème de d"Alembert. . . . . . . . . . . . . . . . . . 257

12.1.4 Distribution des racines. . . . . . . . . . . . . . . . . . . 257

12.1.5 Résolution par radicaux. . . . . . . . . . . . . . . . . . . 258

12.1.6 MéthodeExpression.roots(). . . . . . . . . . . . . . . 260

12.2 Résolution numérique. . . . . . . . . . . . . . . . . . . . . . . . . 261

12.2.1 Localisation des solutions des équations algébriques. . . 262

12.2.2 Méthodes d"approximations successives. . . . . . . . . . 264

13 Algèbre linéaire numérique277

13.1 Calculs inexacts en algèbre linéaire. . . . . . . . . . . . . . . . . 278

13.1.1 Normes de matrices et conditionnement. . . . . . . . . . 278

13.2 Matrices pleines. . . . . . . . . . . . . . . . . . . . . . . . . . . . 281

13.2.1 Résolution de systèmes linéaires. . . . . . . . . . . . . . . 281

13.2.2 Résolution directe. . . . . . . . . . . . . . . . . . . . . . 282

13.2.3 La décompositionLU. . . . . . . . . . . . . . . . . . . . 282

13.2.4La décomposition de Cholesky des matrices réelles symé-

triques définies positives. . . . . . . . . . . . . . . . . . 283

13.2.5 La décompositionQR. . . . . . . . . . . . . . . . . . . . 283

13.2.6 La décomposition en valeurs singulières. . . . . . . . . . 284

13.2.7 Application aux moindres carrés. . . . . . . . . . . . . . 285

13.2.8 Valeurs propres, vecteurs propres. . . . . . . . . . . . . 288

13.2.9 Ajustement polynomial : le retour du diable. . . . . . . 293

13.2.10 Implantation et performances. . . . . . . . . . . . . . . 295

13.3 Matrices creuses. . . . . . . . . . . . . . . . . . . . . . . . . . . 296

13.3.1 Origine des systèmes creux. . . . . . . . . . . . . . . . . 297

13.3.2 Sage et les matrices creuses. . . . . . . . . . . . . . . . 298

xTABLE DES MATIÈRES

13.3.3 Résolution de systèmes linéaires. . . . . . . . . . . . . . 298

13.3.4 Valeurs propres, vecteurs propres. . . . . . . . . . . . . 300

13.3.5Thème de réflexion : résolution de très grands systèmes

non linéaires. . . . . . . . . . . . . . . . . . . . . . . . . . 301

14 Intégration numérique303

14.1 Intégration numérique. . . . . . . . . . . . . . . . . . . . . . . . 303

14.1.1 Fonctions d"intégration disponibles. . . . . . . . . . . . 309

14.2 Résolution d"équations différentielles. . . . . . . . . . . . . . . . 315

14.2.1 Exemple de résolution. . . . . . . . . . . . . . . . . . . . 317

14.2.2 Fonctions de résolution disponibles. . . . . . . . . . . . 318

IV Combinatoire321

15 Dénombrement et combinatoire323

15.1 Premiers exemples. . . . . . . . . . . . . . . . . . . . . . . . . 324

15.1.1 Jeu de poker et probabilités. . . . . . . . . . . . . . . . 324

15.1.2 Dénombrement d"arbres par séries génératrices. . . . . 326

15.2 Ensembles énumérés usuels. . . . . . . . . . . . . . . . . . . . . 333

15.2.1 Exemple : les sous-ensembles d"un ensemble. . . . . . . 333

15.2.2 Partitions d"entiers. . . . . . . . . . . . . . . . . . . . . 334

15.2.3 Quelques autres ensembles finis énumérés. . . . . . . . . 336

15.2.4 Compréhensions et itérateurs. . . . . . . . . . . . . . . . 339

15.3 Constructions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346

15.4 Algorithmes génériques. . . . . . . . . . . . . . . . . . . . . . . 347

15.4.1 Génération lexicographique de listes d"entiers. . . . . . 347

15.4.2 Points entiers dans les polytopes. . . . . . . . . . . . . . 349

15.4.3 Espèces, classes combinatoires décomposables. . . . . . 350

15.4.4 Graphes à un isomorphisme près. . . . . . . . . . . . . . 352

16 Théorie des graphes355

16.1 Construire un graphe. . . . . . . . . . . . . . . . . . . . . . . . 355

16.1.1 À partir de zéro. . . . . . . . . . . . . . . . . . . . . . . 355

16.1.2 Les constructeurs disponibles. . . . . . . . . . . . . . . . 357

16.1.3 Unions disjointes. . . . . . . . . . . . . . . . . . . . . . 360

16.1.4 Affichage des graphes. . . . . . . . . . . . . . . . . . . . . 361

16.2 Méthodes de la classeGraph. . . . . . . . . . . . . . . . . . . . 364

16.2.1 Modification de la structure d"un graphe. . . . . . . . . 365

16.2.2 Opérateurs. . . . . . . . . . . . . . . . . . . . . . . . . . 365

16.2.3 Parcours de graphes et distances. . . . . . . . . . . . . . 366

16.2.4 Flots, connectivité, couplage (matching). . . . . . . . . 367

16.2.5 Problèmes NP-complets. . . . . . . . . . . . . . . . . . . 368

16.2.6 Reconnaissance et test de propriétés. . . . . . . . . . . . 370

16.3 Graphes en action. . . . . . . . . . . . . . . . . . . . . . . . . . 372

16.3.1 Coloration gloutonne des sommets d"un graphe. . . . . . 372

16.3.2 Générer des graphes sous contraintes. . . . . . . . . . . 374

TABLE DES MATIÈRESxi

16.3.3Appliquer un algorithme probabiliste pour trouver un

grand ensemble indépendant. . . . . . . . . . . . . . . . 375

16.3.4 Trouver un sous-graphe induit dans un graphe aléatoire. 376

16.4 Quelques problèmes modélisés par des graphes. . . . . . . . . . 378

16.4.1 Une énigme du journal " Le Monde 2 ». . . . . . . . . . 378

16.4.2 Affectation de tâches. . . . . . . . . . . . . . . . . . . . 379

16.4.3 Planifier un tournoi. . . . . . . . . . . . . . . . . . . . . 380

17 Programmation linéaire383

17.1 Définition. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383

17.2 Programmation entière. . . . . . . . . . . . . . . . . . . . . . . 384

17.3 En pratique. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384

17.3.1 La classeMixedIntegerLinearProgram. . . . . . . . . . 384

17.3.2 Variables. . . . . . . . . . . . . . . . . . . . . . . . . . . 385

17.3.3 Problèmes infaisables ou non bornés. . . . . . . . . . . . 386

17.4 Premières applications à la combinatoire. . . . . . . . . . . . . 387

17.4.1 Sac à dos. . . . . . . . . . . . . . . . . . . . . . . . . . . 387

17.4.2 Couplages. . . . . . . . . . . . . . . . . . . . . . . . . . 388

17.4.3 Flot. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 389

17.5 Génération de contraintes et application. . . . . . . . . . . . . . . 391

Annexes399

A Solutions des exercices399

A.1 Premiers pas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 399 A.2 Analyse et algèbre avec Sage. . . . . . . . . . . . . . . . . . . . 399 A.4 Graphiques. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408 A.5 Domaines. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411 A.6 Corps finis et théorie élémentaire des nombres. . . . . . . . . . 412 A.7 Polynômes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 417 A.8 Algèbre linéaire. . . . . . . . . . . . . . . . . . . . . . . . . . . . 421 A.9 Systèmes polynomiaux. . . . . . . . . . . . . . . . . . . . . . . . 422 A.10 Équations différentielles et récurrences. . . . . . . . . . . . . . . 426 A.11 Nombres à virgule flottante. . . . . . . . . . . . . . . . . . . . . 427 A.12 Équations non linéaires. . . . . . . . . . . . . . . . . . . . . . . 430 A.13 Algèbre linéaire numérique. . . . . . . . . . . . . . . . . . . . . 433 A.14 Intégration numérique. . . . . . . . . . . . . . . . . . . . . . . . 434 A.15 Dénombrement et combinatoire. . . . . . . . . . . . . . . . . . . 435 A.16 Théorie des graphes. . . . . . . . . . . . . . . . . . . . . . . . . . 441 A.17 Programmation linéaire. . . . . . . . . . . . . . . . . . . . . . . 442

B Bibliographie445

C Index449

xiiTABLE DES MATIÈRES

Première partie

quotesdbs_dbs27.pdfusesText_33

[PDF] sujet bac géothermie corrigé

[PDF] exercice géothermie ts

[PDF] factoriser en ligne avec étapes

[PDF] sujet bac geothermie

[PDF] développer en ligne

[PDF] factorisation en ligne avec détails

[PDF] epices marocaine pour poulet

[PDF] les epices marocaine en arabe et francais

[PDF] tableau épices cuisine

[PDF] utilisation des epices et aromates

[PDF] bienfaits des épices et aromates

[PDF] quels sont les bienfaits des épices

[PDF] liste épices marocaines

[PDF] géothermie et propriétés thermiques de la terre cours

[PDF] sujet bac corrigé svt géologie