[PDF] Algorithmes de calcul formel et numérique

Ce texte regroupe donc des résultats mathématiques qui ont été ou sont utilisés dans 6 4 Lien avec l'algorithme du sous-résultant (calcul de PGCD) 105

Previous PDF

Next PDF

[PDF] Algorithmique au lycée

mathématique ▫ Au collège, les élèves ont rencontré des algorithmes ( algorithmes opératoires, algorithme des différences, algorithme d'Euclide, algorithmes

[PDF] Mathématiques Algorithmiques Notes de cours - LACIM - UQAM

Le but de ce cours est de présenter un point de vue algorithmique de divers domaine des mathématiques, en particulier dans le contexte d'algorithmes

[PDF] I Quest-ce quun algorithme ? II Un premier exemple - Free

Un algorithme est une suite d'instructions, qui une fois exécutée correctement, En comparant avec les algorithmes de mathématiques, on pourrait dire que les

[PDF] Algorithmes de calcul formel et numérique - Institut Fourier

Ce texte regroupe donc des résultats mathématiques qui ont été ou sont utilisés dans 6 4 Lien avec l'algorithme du sous-résultant (calcul de PGCD) 105

[PDF] LE PROGRAMME DALGORITHMIQUE SANS - Maths ac-creteil

cycle 4 : notion d'algorithme, branchement conditionnel, boucle, et variable informatique Chaque activité suit Marcel qui se prépare pour aller à l'école

[PDF] exercices corrigés algorithmepdf

Exercice 5 2 Ecrire un algorithme qui demande un nombre compris entre 10 et 20, jusqu'à ce que la réponse convienne En cas de réponse supérieure à 20,

[PDF] ALGORITHMIQUE ET APPRENTISSAGE DE LA PREUVE

et le rôle de l'algorithme dans la science mathématique gnants de mathématiques à enseigner l'algo- ressée à la programmation et à l'outil algorithme

[PDF] ALGORITHMIQUE & MATHEMATIQUES - José OUIN

ceux qui découvriront, grâce aux algorithmes, le plaisir de faire des mathématiques José OUIN Les sites Internet dont je suis l'auteur : - http://www joseouin net

Algorithmes de calcul formel et numérique

B. Parisse

Institut Fourier

UMR 5582 du CNRS

Université de Grenoble

2 Giac/Xcas est un logiciel libre de calcul formel dont une caractéristique est de nécessiter peu de ressources sans sacrifier les performances (en particulier sur les calculs polynomiaux). Ce document décrit une partie des algorithmes de calcul for- mel et numérique qui y sont impleémentés, l"objectif à long terme est de couvrir l"essentiel des algorithmes implémentés. Ce n"est pas le manuel d"utilisation de Xcas, ni un manuel de programmation ou d"exercices illustrés avec Xcas (voir le menu Aide, Manuels : Référence calcul formel, Programmation, Exercices, Amu- sements...). Ce texte regroupe donc des résultats mathématiques qui ont été ou sont utilisés dans Giac (ou sont susceptibles de l"être), ils sont en général accompagnés de preuves et souvent d"illustrations avec Xcas.

Pour plus d"informations sur Giac/Xcas, cf. :

N.B. : La version HTML de ce document comporte des champs de saisie inter- actifs, ceux-ci apparaissent comme des commandes "mortes" dans la version PDF (elles sont exécutées une fois pour toutes par la version non interactive degiac). La version HTML est optimisée pour le navigateur Firefox. Elle est générée avec hevea.inria.frde Luc Maranget, ou le fork de Yannick Chevallier pour le support mathjax, ainsi qu"une version modifiée deitex2MMLde Jacques Distler pour la conversion en MathML. Si vous avez une machine très puissante, vous pou- vez exécuter toutes les commandes interactives en cliquant sur le bouton Exécuter. En-dessous de ce bouton se trouve la console de l"interpréteur du logiciel de calcul formel.

Table des matières

1 Plan et index

2 Trousse de survie Xcas

2.1 Utilisation comme super-calculatrice

2.2 Calcul exact

2.2.1 Arithmétique

2.2.2 Algèbre linéaire exacte

2.3 Calcul scientifique

2.3.1 Analyse numérique

2.3.2 Algèbre linéaire numérique

3 Calculer sur ordinateur

3.1 Représentation des entiers

3.2 Les réels

3.2.1 Virgule fixe et flottante.

3.2.2 Les flottants au formatdouble. . . . . . . . . . . . . .29

3.2.3 Opérations sur les flottants

3.2.4 Erreurs

3.2.5 Erreur absolue, relative, arrondi propagation des erreurs.

3.3 L"arithmétique d"intervalle.

3.4 Calcul exact et approché, types, évaluation.

3.5 Forme normale et reconnaissance du 0.

3.6 Valeur générique des variables et hypothèses

3.7 Structures de données

3.7.1 Maple, Mathematica, ...

3.7.2 Giac/Xcas

3.7.3 Calculatrices formelles HP48/49

3.7.4 Calculatrices formelles TI92/89/Voyage 200

3.8 Algorithmes et complexité.

3.8.1 Algorithmes modulaires ou p-adiques

3.8.2 Algorithmesdéterministes.Algorithmesprobabilistes:Las

Vegas et Monte-Carlo

3.9 Entiers et polynômes.

3.9.1 Petits et grands entiers

3.9.2 Opérations arithmétiques de base

3.9.3 Opérations de base sur les petits entiers.

3.9.4 Opérations de base sur les grands entiers

3.10 Euclide

52
3

4TABLE DES MATIÈRES

3.10.1 Division euclidienne.

3.10.2 Anneau euclidien

3.10.3 Le PGCD

3.10.4 L"identité de Bézout

3.10.5 Nombres premiers entre eux

3.10.6 Les restes chinois

3.10.7 Nombres premiers, factorisation

3.10.8 Remarque : la divisibilité est une relation d"ordre partiel

3.10.9 Prolongement : idéaux

3.11 Quelques algorithmes d"arithmétique de base.

3.11.1 Calcul de la racine carrée entière

3.11.2 Bezout sur les entiers et les fractions continues

3.11.3 La puissance rapide itérative

3.11.4 Application de la puissance rapide : trouver un g

´nérateur

deFp=Z=p. . . . . . . . . . . . . . . . . . . . . . .66

3.11.5 Application de la puissance rapide : cryptographie RSA

3.12 Algorithmes rapides sur les polynômes en une variable.

3.12.1 Inverse moduloxl. . . . . . . . . . . . . . . . . . . . .70

3.12.2 Division euclidienne.

3.12.3 Euclide

3.13 Pour en savoir plus.

3.14 Exercices sur types, calcul exact et approché, algorithmes de bases

4 Les générateurs de nombres pseudo-aléatoires.

4.1 Selon la loi uniforme

4.1.1 Les générateurs congruentiels à 1 cran.

4.1.2 Récurrence àkéléments. . . . . . . . . . . . . . . . . . 82

4.1.3 Mersenne twister.

4.2 Selon plusieurs lois classiques

5 Le PGCD de polynômes.

5.1 Le sous-résultant.

5.2 Le pgcd en une variable.

5.2.1 Le pgcd heuristique.

5.2.2 Le pgcd modulaire

5.3 Le pgcd à plusieurs variables.

5.3.1 Le pgcd heuristique.

5.3.2 Le pgcd modulaire multivariables.

5.3.3 EZGCD.

5.4 Quel algorithme choisir?

103

5.5 Pour en savoir plus.

103

6 Le résultant

105

6.1 Définition

105

6.2 Applications

106

6.2.1 Systèmes polynomiaux

107

6.2.2 Identité de Bézout dansZ[X].. . . . . . . . . . . . . . . 107

6.3 Résultant et degrés

108

TABLE DES MATIÈRES5

6.4 Lien avec l"algorithme du sous-résultant (calcul de PGCD)

109

6.5 Calcul efficace du résultant

111

7 Localisation des racines

113

7.1 Majoration

113

7.2 Les suites de Sturm.

113

7.3 Autres algorithmes

114

8 Exercices (PGCD, résultant, ...)

119

8.1 Instructions

119

8.1.1 Entiers

119

8.1.2 Polynômes

119

8.1.3 Calculs modulon. . . . . . . . . . . . . . . . . . . . . .120

8.2 Exercices PGCD

121

8.3 Exercice (Bézout modulaire)

122

8.4 Exercices (résultant)

123

8.5 Décalage entier entre racines.

124

8.6 Exemple de correction de géométrie et résultant

126
127

9.1 Ordre et réduction

127

9.2 Idéaux

128

9.3 Introduction

128

9.4 Checking a reconstructed Groebner basis

129

9.5 Speeding up by learning from previous primes

130

9.6 Giac/Xcas implementation and experimentation

131

9.7 Conclusion

134

9.8 Représentation rationnelle univariée (rur).

135

10 Courbes paramétriques et polaires

139

10.1 Introduction

139

10.2 Représentation graphique

144

10.3 Paramétrage

146

10.4 Étude analytique d"une courbe en paramétrique

146

10.4.1 Rappel sur les graphes de fonction

146

10.4.2 Domaine et périodicité

149

10.4.3 Branches infinies

150

10.4.4 Étude locale

151

10.5 Plan d"étude d"une courbe

159

10.6 Courbes en polaires

160

10.7 Coniques

168

10.7.1 Ellipse

169

10.7.2 Parabole

172

10.7.3 Hyperbole

174

10.7.4 Paramétrisation rationnelle

175

11 Propriétés métriques des courbes.

179

11.1 Longueur d"arc

179

11.2 Courbure, repère de Frenet, accélération normale et tangentielle.

181

6TABLE DES MATIÈRES

12 Représentation des courbes implicites.

189

13 Formes différentielles et intégrales curvilignes

191

13.1 Forme différentielle

191

13.2 Intégrale curviligne

193

13.3 Forme différentielle exacte

194

13.4 Intégrale curviligne et intégrales doubles.

196

14 Équations et systèmes différentiels.

199

14.1 Introduction et représentation graphique.

199

14.2 Existence et unicité

203

14.3 Quelques méthodes de résolution explicite.

206

14.3.1 Équations à variables séparables

206

14.3.2 Équations linéaires

206

14.3.3 Équations linéaires à coefficients constants

207

14.3.4 Systèmesdifférentielslinéairesàcoefficientsconstantsd"ordre

1. 210

14.3.5 Systèmes et équations

211

14.3.6 Allure des courbes en dimension 2.

212

14.3.7 Systèmes d"ordre plus grand que 1

214

14.3.8 Intégrales premières.

215

14.3.9 Le modèle proie-prédateur

217

14.3.10Quelques autres méthodes

218

14.4 Comportement asymptotique des solutions

218

14.4.1 Équations linéaires à coefficients constants d"ordre 1 et 2

218

14.4.2 Forçage périodique

219

14.4.3 Équation autonome sans second membre

220

14.4.4 Systèmes linéaires

221

14.4.5 Forçage près d"un point d"équilibre de système.

222

14.5 Résolution numérique

224

14.5.1 Méthodes à un pas

224

14.5.2 Méthodes de Runge-Kutta (explicites)

226

15 Introduction au calcul variationnel

229

16 Corps finis.

235

16.1 Rappels

235

16.2 Représentation des corps non premiers.

235

16.2.1 Cas général.

235

16.2.2 Corps de petit cardinal, cas de la caractéristique 2

236

16.3 Exercices

237

16.4 Rappels de quelques complexités de base

238

16.4.1 Polynomes denses et entiers

238

16.4.2 Algèbre linéaire dense

238

16.5 Codes linéaires et polynomiaux.

239

16.5.1 Le bit de parité.

239

16.5.2 Codes linéaires

239

16.5.3 Codes polynomiaux

240

16.5.4 Détection et correction d"erreur

240

TABLE DES MATIÈRES7

16.5.5 Distances

241

16.5.6 Correction au mot le plus proche

241

16.5.7 Codes de Hamming

242

16.6 Les codes de Reed-Solomon

244

16.6.1 Théorie

244

16.6.2 Preuve du calcul del. . . . . . . . . . . . . . . . . . . .245

16.6.3 Avec Xcas

246

17 Factorisation des entiers et primalité.

247

17.1 Le test de primalité de Pocklington.

248

17.2 La méthodede Pollard. . . . . . . . . . . . . . . . . . . . . . 249

17.3 Le crible quadratique

250

17.3.1 Recherche de racine carrée modulo p

251

18 Factorisation des polynômes.

253

18.1 Les facteurs multiples

253

18.2 Factorisation en une variable

256

18.2.1 Factorisation dansZ=pZ[X]. . . . . . . . . . . . . . . .256

18.2.2 Distinct degree factorization

256

18.2.3 La méthode de Cantor-Zassenhaus

258

18.2.4 La méthode de Berlekamp

260
quotesdbs_dbs45.pdfusesText_45

[PDF] [PDF] Algorithmes de calcul formel et numérique - Institut Fourier