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

[PDF] Exercices dalgorithmique en seconde ➢ Calcul ➢ Fonctions

Équipe Académique Mathématiques Page 2/3 Bordeaux - 2009 a Traduire cet algorithme en programme pour la calculatrice b Faire fonctionner ce 

[PDF] Ressources pour la classe de seconde - Maths Bordeaux

Plus généralement le mot « algorithme » désigne tout procédé de calcul systématique voire automatique S'ajoute à cela la notion de « finitude » On définit 

[PDF] Que faire en algorithmique en classe de seconde ? - lAPMEP

mathématiques et les problèmes posés doivent être en relation avec les autres parties Algorithme 1 : On donne le programme de calcul suivant (algorithme) :

[PDF] Algorithmique au lycée

égal à 15 ? Ecrire l'algorithme associé à ce programme de calcul mathématiques et les problèmes posés doivent être en relation avec les autres parties du 

[PDF] Algorithme exercices - Lycée dAdultes

2) Ecrire cet algorithme en pseudo-code puis avec votre calculatrice Vérifier les résultats obtenus 3) Comment choisir un nombre pour que s'afficher le nombre 

[PDF] ALGORITHMIQUE

Equation du second degré Page 27 Voici l'algorithme qui correspond au programme de calcul Variables Partie 1 : d'après le livre Math'x de 2de Voici un 

[PDF] Cours dalgorithmique pour la classe de 2nde - Mathsfg - Free

8 juil 2009 · Un programme est la traduction d'un algorithme dans le langage de programmation associés aux calculatrices programmables partie enti`ere d'un nombre a (menu MATH NUM iPart sur TI, menu OPTN NUM Int sur

[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 3 14 Exercices sur types, calcul exact et approché, algorithmes de bases 70 unique non seulement avec comme second membre 1 mais avec n'importe quel

[PDF] EXERCICES – ALGORITHME SECONDE Exercice 51 Ecrire un

Ecrire un algorithme qui demande à l'utilisateur un nombre compris entre 1 et NB : on souhaite afficher uniquement le résultat, pas la décomposition du calcul

[PDF] Algorythme 1ère Mathématiques

[PDF] algorythme 2nde Mathématiques

[PDF] Algorythme ( fonction) 2nde Mathématiques

[PDF] ALgotithmique 1 ere S svp svp aide !!!!!!!!!!! 1ère Mathématiques

[PDF] ALGOTRITHME FACILE niveau 2ND 3ème Mathématiques

[PDF] algues vertes algues rouges et photosynthèse PDF Cours,Exercices ,Examens

[PDF] alhambra mathématiques PDF Cours,Exercices ,Examens

[PDF] Alias ou Aka 5ème Anglais

[PDF] alice a placé un trésor dans un coffre ? trois serrures correction PDF Cours,Exercices ,Examens

[PDF] Alice achète x stylos 5ème Mathématiques

[PDF] Alice adventures in Wonderland 2nde Anglais

[PDF] alice au pays des merveilles 3ème Anglais

[PDF] alice au pays des merveilles 6ème Français

[PDF] alice au pays des merveilles analyse PDF Cours,Exercices ,Examens

[PDF] alice au pays des merveilles chapitre 1 analyse PDF Cours,Exercices ,Examens

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

11

2 Trousse de survie Xcas

17

2.1 Utilisation comme super-calculatrice

17

2.2 Calcul exact

19

2.2.1 Arithmétique

19

2.2.2 Algèbre linéaire exacte

21

2.3 Calcul scientifique

22

2.3.1 Analyse numérique

22

2.3.2 Algèbre linéaire numérique

23

3 Calculer sur ordinateur

25

3.1 Représentation des entiers

25

3.2 Les réels

26

3.2.1 Virgule fixe et flottante.

26

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

3.2.3 Opérations sur les flottants

30

3.2.4 Erreurs

30

3.2.5 Erreur absolue, relative, arrondi propagation des erreurs.

31

3.3 L"arithmétique d"intervalle.

35

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

36

3.5 Forme normale et reconnaissance du 0.

37

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

39

3.7 Structures de données

39

3.7.1 Maple, Mathematica, ...

40

3.7.2 Giac/Xcas

41

3.7.3 Calculatrices formelles HP48/49

41

3.7.4 Calculatrices formelles TI92/89/Voyage 200

43

3.8 Algorithmes et complexité.

44

3.8.1 Algorithmes modulaires ou p-adiques

44

3.8.2 Algorithmesdéterministes.Algorithmesprobabilistes:Las

Vegas et Monte-Carlo

46

3.9 Entiers et polynômes.

47

3.9.1 Petits et grands entiers

47

3.9.2 Opérations arithmétiques de base

49

3.9.3 Opérations de base sur les petits entiers.

51

3.9.4 Opérations de base sur les grands entiers

52

3.10 Euclide

52
3

4TABLE DES MATIÈRES

3.10.1 Division euclidienne.

53

3.10.2 Anneau euclidien

54

3.10.3 Le PGCD

54

3.10.4 L"identité de Bézout

55

3.10.5 Nombres premiers entre eux

56

3.10.6 Les restes chinois

57

3.10.7 Nombres premiers, factorisation

59

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

59

3.10.9 Prolongement : idéaux

60

3.11 Quelques algorithmes d"arithmétique de base.

60

3.11.1 Calcul de la racine carrée entière

62

3.11.2 Bezout sur les entiers et les fractions continues

63

3.11.3 La puissance rapide itérative

65

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

67

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

70

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

3.12.2 Division euclidienne.

70

3.12.3 Euclide

71

3.13 Pour en savoir plus.

72

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

73

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

77

4.1 Selon la loi uniforme

77

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

77

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

4.1.3 Mersenne twister.

83

4.2 Selon plusieurs lois classiques

83

5 Le PGCD de polynômes.

85

5.1 Le sous-résultant.

86

5.2 Le pgcd en une variable.

89

5.2.1 Le pgcd heuristique.

89

5.2.2 Le pgcd modulaire

92

5.3 Le pgcd à plusieurs variables.

95

5.3.1 Le pgcd heuristique.

95

5.3.2 Le pgcd modulaire multivariables.

96

5.3.3 EZGCD.

99

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

18.2.5 Remontée (Hensel)

261

18.2.6 Combinaison de facteurs

264

18.3 Factorisation à plusieurs variables

265

18.4 Preuve de l"identité de Bézout généralisée

268

18.5 Algorithme de Bézout généralisé

268

18.6 Factorisation rationnelle et sur une extension

269

18.7 Factorisation absolue

270

18.8 Compléments

271

18.9 Exercices (factorisation des polynômes)

273

19 Intégration formelle.

275

19.1 Introduction

275

19.2 Fonctions élémentaires

276

19.2.1 Extensions transcendantes, tour de variables

276
quotesdbs_dbs18.pdfusesText_24