Colle Info Maple nOl Septembre2009

Publié par

Colle Info Maple nOl Septembre2009 Suites récurrenteset Algèbre linéaire Exercice 1 : DébutdusujetdeCentrale2008: L'exponentiation rapide La questionpréliminairedonnel'algorithmedel'exponentiationrapidequ'ilfaut recon- naître. Complémentsurcetalgorithme: La manièrenaïved'évaluernumériquementxnpourn entierpositif,enécrivant: xn=xx x...xx- ~.... n fois n'estpasla manièrelaplusrapidecarellenécessiten multiplications.Pour allerplus vite,onpeutappliquerleprincipe« diviserpourmieuxrègner»: xn = { (x2)i x x (x2)n;l s't n estpair s't n estimpair quiconsisteà effectuerunetâche(calculerxn) enseramenantà deuxsous-tâchesiden- tiques(calculeruneseulefois (x2)i) dontlenombredemultiplicationsestplusfaibleque celuidela tâcheinitiale.La soustâches'effectuensuiteselonle mêmetypededécom- position,et ainsi desuite,jusqu'àarriverau calculd'unrésultatconnu(ici, XO= 1). L'exponentiationdexn selonceprincipedemadeenfait environlog2(n)multiplications, cequipourdegrandesvaleursden estbieninférieurauxn multiplicationsdela méthode naïve.

  • pourbut depréparernotrepremièrecolled'informatique

  • tracerf etp surunmêmegraphe

  • exercice sur les polynômesde lagrange

  • ondonnelaséquenced'instructionsdéfinissantci-dessouslafonctionf


Publié le : lundi 18 juin 2012
Lecture(s) : 24
Source : cpge-brizeux.fr
Nombre de pages : 3
Voir plus Voir moins