[PDF] Algorithmes de calcul formel et numérique

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

É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

[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

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

quotesdbs_dbs13.pdfusesText_19

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