Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Colle Info Maple nOl Septembre2009

3 pages
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


Voir plus Voir moins
Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin