Colle Info Maple nOl Septembre2009

Description

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

Informations

• Publié par: pefav
• Nombre de lectures: 24
• Langue: Français

Extrait