Mathematiques assistees par ordinateur Chapitre Introduction

De
Publié par

Mathematiques assistees par ordinateur Chapitre 1 : Introduction Michael Eisermann Mat249, DLST L2S4, Annee 2008-2009 www-fourier.ujf-grenoble.fr/˜eiserm/cours _ mao Document mis a jour le 6 juillet 2009 1/28

  • cote ordinateur

  • lettre ecrite au moyen age

  • calcul exact dans z

  • nombres reels

  • arithmetique des entiers nombres rationnels


Publié le : mardi 19 juin 2012
Lecture(s) : 53
Source : www-fourier.ujf-grenoble.fr
Nombre de pages : 28
Voir plus Voir moins
Math´ematiquesassist´eesparordinateur Chapitre 1 : Introduction
Michael Eisermann
Mat249,DLSTL2S4,Ann´ee2008-2009 www-fourier.ujf-grenoble.fr/˜eiserm/cours # mao Documentmis`ajourle6juillet2009
/182
Objectifs de ce chapitre Le principal but de ce premier chapitre est de donner une introduction rapide au calcul sur ordinateur, afin de poser les fondements et de consolider les premie` res expe´ riences pratiques en TD et TP. On commence par la repre´ sentation des nombres entiers, rationnels, re´ els, complexes et les ope´ rations de calcul qui leur sont propres. De cote´ mathe´ matique, je suppose acquis la de´ finition/construction des entiersZ, des rationnelsQ,dr´eslseeR, et des complexesC. De cote´ ordinateur, il faut distinguer le calcul exact dansZetQet le calcul approche´ dansRetC menter. Aucun ordinateur ne peut imple´ les nombres re´ els ou complexes, tant aime´ s des mathe´ maticiens ! La dichotomie«xecasatvropp´ech»nous occupera tout le long du semestre,etilvautmieuxsefamiliariserde`sled´ebutavecses particularite´ s, notamment du calcul approche´ . Concre` tement, dans ce premierchapitre,ilfautbienassimilertouteslesr`eglesdebonsens. 2/28
Sommaire
1
2
3
Nombres entiers et rationnels, calcul exact Num´erationpositionnelle Arithme´ tique des entiers Nombres rationnels
Nombres re´ els, calcul approche´ , propagation d’erreurs Laprobl´ematiqueillustr´eeparlexemple2 s a v gu Nombre`irleottanteetcalculapproch´e Propagation d’erreurs : la prudence s’impose !
Typescompos´es:expressions,fonctions,conteneurs,... Nombres complexes Polynˆomesetfractionsrationnelles Expressions et fonctions Conteneurs, vecteurs et matrices
3/28
§.1
Avantdecalculerilfautrepr´esenterlesnombres
1
Dabordnouscherchonsunenum´erationquiseprˆetebienaucalcul.
DXXXVII 537 MMVIII 2008 XLIII 43 +LXXIX+79LXXIX79×LXXIX×79 DMXVI 616 MCMXXIX 1929 MMMXXXIIIX 3397
La nume´ ration romaine ne facilite pas le calcul. Voici un extrait d’une lettre ´ ite au ecr moyenaˆgeparunsavant`aunrichemarchand.Cederniercherchaitconseilpour savoi`uenvoyersonenfant´etudierlasciencedesnombresetducalcul. r o Si tu de´ sires l’initier a` la pratique de l’addition ou de la soustraction, n’importe quelle universite´ franc¸ aise, allemande ou anglaise fera l’affaire. Mais, pour la maıtrise de l’art de multiplier ou de diviser, je te recommande ˆ plutoˆ t de l’envoyer dans une universite´ italienne.
Lanum´erationpositionnelleadepuisre´volutionne´lecalcul! Ainsielleacontribue´a`d´emocratiserlesmathe´matiques.
/482
§.1
Num´erationpositionnelledesnombresentiers Rappelonscemerveilleuxoutilquiestlanum´erationpositionnelle. En base 10 :2008dec=2103+0102+0101+8100 En base 2 :1011bin=123+022+121+120= 11dec
1
Commentobtenirled´eveloppementenbase2?
1011bin= (((12 +0)2 +1)2 +1 | {z } |{z} q2 +r
Algorithme de conversion : On ite` re la division euclidienne. a= 2quo + rem 11 = 25 +1 5 = 22 +1 2 = 21 +0 1 = 20 +1
Cet algorithme marche pour tout entier, en n’importe quelle base. Lemˆemealgorithmenousserviraplustardpourlespolynoˆmes.
/528
§1.
La division euclidienne
1
Proposition (division euclidienne des entiers)
Pour touta, bZou`b6= 0il existe un unique coupleq, rZtel que
a=qb+ret0r <|b|.
On appelleq=:aquoblequotientetr=:aremblerestede la division euclidienne deaparb.
D´emonstration.E!no´eersivircxeedic
Corollaire SoitBaZ=te±l qPu`eB2. Tout entieraZequ´ecsnamedtirinuere`i commek0=1akBktel queak∈ {0,1, . . . , B1}eta`16= 0.
D´emonstration.xe!Eoincsricveire´de
On appelle`Nlalongueurentdppemveloud´edeaen baseB. On la notelenB(a) :=`; quandB= 2on e´ critlen(a) := len2(a).
6/28
Les ordinateurs calculent en binaire Onpeuteffectuerlesop´erationsarithm´etiquesenbase2. Exemple : 01101011 01101011 + 01001111 - 01001111 10111010 00011100 Les microprocesseurs utilisent de tels entiers«machine»: tailleenm´emoireplagedesentiersquipeuventˆetrerepr´esent´ees min max 1 octet = 8 bits0 281 = 255 variantesign´ee27=128 27 1271 = 2 octets = 16 bits0 216 655351 = variantesign´ee215=32768 2151 = 32767 4 octets = 32 bits0 232 42949672951 = variantesign´ee231=2147483648 2311 = 2147483647 8 octets = 64 bits0 264 184467440737095516151 = variantesign´ee62=39223372036854775808 263 92233720368547758071 = Avantage : les calculs sont tre` s rapides. Inconv´enient:latailleestlimite´eetxe´edavance. §1.1 7/28
Imple´ mentation des grands entiers Le processeur ne fournit que des entiers a` 64 bits (au plus). Toutcalculd´epassant0, . . . ,2641qu´e.Exeseratron:elpm 263+ 263= 0 ! bits 64avec des entiers machine a` Comment calculer donc avec des grands entiers ? Solution : a=P`1akBko`uB= 232 k=0. Un grand entier est un tableau de petits entiers (chiffres). sntaoip´erLeso+,,,quo,remneet´lmeipmsole.´ece`alcomm Toutlogicieldecalculformelimpl´ementeainsilesgrandsentiers: 263+ 263= 18446744073709551616 50!=30414093201713378043612608166064768844377641568960512000000000000 Pluslesentierssontlongs,pluslescalculssontcoˆuteux. Addition et soustraction sont de complexit ´e line´ aire :O(`). Multiplication et division sont de complexite´ quadratique :O(`2). Pour les grands entiers il existe des algorithmes sous-quadratiques (Karatsuba, FFT) donc plus efficaces que l’algorithme scolaire. §1.2 8/28
§1.
L’algorithme d’Euclide Tous les calculs nume´ riques, aussi complexes qu’ils soient, sont bas´essurlesope´rationse´le´mentaires+,,,quo,remdes entiers.
2
Voiciunpremierexemplece´l`ebre:
Algorithme 1pgcd de deux entiers selon Euclide Entre´ e:deux entiersa, bZ Sortie:le pgcd positif deaetb tant queb6= 0faire raremb,ab,br fin tant que sia <0alorsa← −a retournera
Proposition
Pour touta, bZl’algorithme ci-dessus se termine et renvoie le pgcd positif deaetbln.Iluseaupssit´ece2 len(a)ite´ rations.
De´ monstration. vision !Exercice de re´
9/28
§.1
Nombres rationnels Onsaitrepr´esenterlesentiersa, bZns.e´tpfrfecteauotireelrueos
3
Tout nombre rationnelxQomtcme´sircex=abaveca, bZ,b6= 0.
On re´ duit chaque fraction de sorte quepgcd(a, b) = 1etb >0. urPorepr´esenterxon stocke simplementaetb. iu:tmmsehm´earitescotiquelet´postaresnoiniOl´mpenem ba±dc=bda±abd,cbdc=ac/ba,,cbdbdac = d bien suˆ r suivi de la re´ duction des fractions (calcul du pgcd dansZ).
Tous les calculs nume´ aussi complexes qu’ils soient, sont riques, bas´essurlesop´erations´el´ementaires+,,,quo,remdes entiers.
Conclusion Les calculs avec les rationnels sont exacts et a priori sans limitation. Lesseulsfacteurslimitantsontletempsetlam´emoiredisponibles.
10/28
Un de´ faut des nombres rationnels Proposition Il n’existe pas de nombre rationnelrQtel quer2= 2. De´ monstration.Soitr=batel quea, bZetb6= 0Qu.teitr´`aiudeer la fractionab, on peut supposer quepgcd(a, b) = 1. Supposons que r2=ba22= 2. Alorsa2= 2b2. Comme2divisea2, l’entieradoit eˆ tre pair, donca= 2¯aaveca¯Z. On a alorsa2= 4¯a2= 2b2et ainsi b2= 2a2. Maintenant2diviseb2, l’entierberapri.dtnoˆctessauoiid Ceci contredit notre hypothese quepgcd(a, b) = 1. Il n’existe donc ` pas de nombre rationnelrtel quer2= 2. Les nombres rationnels ne sont pas«complets». Ainsi ils ne suffisent pas pour l’analyse (limites, de´ rive´ es, inte´ grales). §2.1 11/28
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.