Aurélien Garivier  26.09.2002

𝔓𝔯𝔬𝔠𝔢́𝔡𝔲𝔯𝔢𝔰 𝔢𝔱 𝔰𝔱𝔲𝔠𝔱𝔲𝔯𝔢𝔰 𝔡𝔢 𝔠𝔬𝔫𝔱𝔯𝔬̂𝔩𝔢

Objectifs : révision des acquis de première année. Obtention d’automatismes en matière de syntaxe et de méthodes pour la programmation en maple. Les stuctures de données (listes, tableaux, etc...) seront vues ultérieurement.

Répondre aux questions dans l’ordre, à l’exception éventuellement des dernières de chaque partie.

1 Initiation

– Ré-écrire les fonctions abs, max, Heaviside.

– Ecrire une version simplifiée de sum qui prend en arguments une fonction f et un entier n, et qui retourne ∑_{i=1}^{n} f(i). Que vaut ∑_{i=1}^{n} i^{k} pour k ∈ ℕ? Comment le montre-t-on ? Que vaut ∑_{i=1}^{∞} \frac{1}{i^{2k}} pour k ∈ ℕ^{∗}? Comment le montre-t-on ?

– Tracer sur l’intervalle [−2, 2] la fonction f : x → \{ \begin{matrix}exp \frac{1}{x^{2}−1} & si |x| ⩽ 1 \\ 0 & sinon \end{matrix} . Qu’a-t-elle de remarquable ?

2 Arithmétique

– Ré-écrire la fonction isprime en implémentant la méthode du crible d’Erathostène.

Est-ce celle qui est utilisée par Maple ? Pourquoi ?

– Ecrire une fonction expo qui étant donnés x réel et n entier positif, calcule x^{n}.

Le faire d’abord de façon naturelle, puis en utilisant le fait que x^{n} = \{ \begin{matrix}1 & si & n = 0 \\ (x^{n/2})^{2} & si & n est pair \\ x.x^{n−1} & si & n est impair \end{matrix} .

Quel intérêt peut avoir cette nouvelle version ? (expliquer pourquoi elle s’appelle “exponentiation rapide”).

– Ré-écrire la fonction igcd, puis éventuellement igcdex et gcdex.

3 Suite de Fibonacci

La suite de Fibonacci est définie par la relation de récurrence : u_{n+2} = u_{n+1} + u_{n}, u_{0} = u_{1} = 1.

1. Ecrire une procédure récursive fib prenant en argument n et calculant u_{n} en utilisant la relation de récurrence. Essayer d’obtenir ainsi u_{32}. Que se passe-t-il ?

2. Ecrire une procédure prenant en argument n et permettant de calculer u_{n} en faisant max(n − 1, 0) additions et aucune autre opération arithmétique. Quels termes de la suite peut-elle donner en moins d’une seconde ?

3. Donner une formule close pour u_{n} et en déduire une nouvelle procédure.

Permet-elle d’aller plus loin ?

4. Vérifier que ( \begin{matrix}u_{n+1} \\ u_{n+2} \end{matrix} ) = ( \begin{matrix}0 & 1 \\ 1 & 1 \end{matrix} ) ( \begin{matrix}u_{n} \\ u_{n+1} \end{matrix} ). En utilisant une exponentiation rapide, calculer ainsi u_{2^{18}}.

5. Comparer graphiquement les performances de ces différentes versions en dessinant le logarithme du temps de calcul de u_{n} pour chacune d’entre elles en fonction de log n.

4 Que font-ils ?

myst1 := proc (n : :nonnegint) local x, y ;

x := 1 ; y := n ; while y > 0 do

x := x * y ; y := y - 1 end do ;

x end proc ; myst2 := proc (x : :nonnegative) local y, ech, a, b, m ;

y := x ; ech := 1 ;

while y > 1 do y := y / 4 ; ech := 2 * ech end do ; a := 0 ; b := 1 ; while b - a > 1e-5 do m := (a + b) / 2 ; if mˆ 2 < x then a := m else b := m end if

end do ;

ech * (a + b) / 2 end proc 1. Deviner ce que calcule le programme myst1, et en donner trois versions différentes utilisant respectivement for, une récursion

et la commande Maple prod.

2. Comprendre le fonctionnement du programme myst2 (commencer par x ∈ [0, 1]).