6. La Programmation par Récurrence

6.0.1.11

6. La Programmation par Récurrence

1 Exercice 6.8.1

ERRATUM. La formule à démontrer est incorrecte, il faut la lire 12+22+...+n2 = n(n+1)(2n+1)/6

a) Si n=0, elle est clairement vérifiée.

b) Supposons-la vraie pour n-1 et prouvons-la pour n :

12+22+...+n2 = (12+22+...+(n-1)2) + n2 = (n-1)n(2n-1)/6 + n2 = n(n+1)(2n+1)/6 CQFD

2 Exercice 6.8.2

a) Si E est l’ensemble vide, il contient 20=1 éléments. Si E contient n > 0 éléments, soit x un élément de E et soit F = E - {x} qui contient n-1 éléments. Par hypothèse de récurrence, F contient 2n-1 parties. Or l’ensemble des parties de E est la réunion disjointe:

des parties de E ne contenant pas x, donc des parties de F, il y en a 2n-1.
des parties de E contenant x, en bijection avec les parties de F, il y en a aussi 2n-1.

Donc E contient 2n-1+2n-1=2n parties, CQFD.

b) Une permutation d’un ensemble E n’est autre qu’une bijection de E sur E. Soit cn le nombre de permutations d’un ensemble à n éléments. Si E est vide ou n’a qu’un élément, il n’y en a qu’une, c0=1. Si E = {x1,x2,...,xn}, il y a n possibilités pour permuter x1, et il restera cn-1 permutations possibles pour {x2,...,xn}. Donc c0=1 et cn=n*cn-1, on reconnaît la définition de n!.

c) Indication : isolez un élément x de E comme dans a).

3 Exercice 6.8.3

a) Raisonnez par récuurence. Pour n=0, il y a une seule région. Supposons connu le nombre Dn-1 de régions dans une configuration de n-1 droites. Si nous introduisons une n-ème droite dans cette configuration, combien de régions allons-nous rajouter ?...

Dn = Dn-1 + ...

(define (nb-regions n)

(if (= n 0)

(+ (nb-regions (- n 1)) ...)))

c) Introduisez un accumulateur.

d) Calculez les premiers termes de la suite Dn et pensez au Triangle de Pascal... Ou bien utilisez le théorème de la page 92 et résolvez un système d’équations...

4 Exercice 6.8.4

b) Le calcul est lent car on fait et on refait les mêmes calculs ! [pourquoi ?]

5 Exercice 6.8.5

a) Introduisez un accumulateur.

b) Utilisez le fait que (add x y) a un coût d’ordre x, et indépendant de y.

c) (add x y) a-t-il la même complexité que (add y x) ?...

6 Exercice 6.8.6

Récurrence sur x. L’hypothèse de récurrence ne se fait pas sur x-1 mais sur x-y, puisqu’on enlève des blocs de y chaque fois...

7 Exercice 6.8.7

Introduisez un accumulateur.

8 Exercice 6.8.8

On découpe l’intervalle d’intégration [a,b] en petits sous-intervalles de largeur dx, et l’on utilise la règle de Chasles, qui dit que l’intégrale de f sur [a,b] est la somme de son intégrale sur [a,a+dx] et de celle sur [a+dx,b]. Or sur [a,a+dx], il s’agit d’une aire de rectangle ! Le cas de base est a>b, car le test a=b risque de poser des problèmes de précision...

9 Exercice 6.8.9

Je vous laisse jouer avec les images. Utilisez above/align, beside, etc. pour juxtaposer tous les éléments, tête, cou, bras, jambes...

Pour la foule, utilisez scale pour diminuer la taille des rangées.

10 Exercice 6.8.10

Faites un pas à partir de A [vers le haut ou vers la droite], et envoyez une récurrence bien choisie. Attention, une fois ce premier pas fait, êtes-vous encore dans un carré ?...

11 Exercice 6.8.11

(define-struct intervalle (debut fin))

et l’on travaille sur des valeurs de type intervalle. On suppose que f(a) < 0 et f(b) > 0, quitte à considérer la fonction -f si c’est le contraire. L’itération consiste à améliorer l’intervalle I (qui vaut [a,b] au démarrage) jusqu’à ce qu’il soit de largeur inférieure à h.

(define (une-racine f I h)

; I = [e1,e2] avec f(e1)<0 et f(e2)>0

(local [(define (milieu I)

(/ (+ (intervalle-debut I) (intervalle-fin I)) 2))

(define (assez-bon? I)

(< (- (intervalle-fin I) (intervalle-debut I)) h))

(define (ameliore I)

(local [(define m (milieu I)) (define ym (f m))]

(if (< ym 0)

(make-intervalle m (intervalle-fin I))

(make-intervalle (intervalle-debut I) m))))

(define (iter I)

(if (assez-bon? I)

(iter (ameliore I))))]

(iter I)))

Application au calcul approché de la racine carrée de 3, solution de x2-3 = 0 :

> (une-racine (lambda (x) (- (sqr x) 3))

(make-intervalle #i1 #i5)

#i0.0001)

#(struct:intervalle 1.73199462890625 1.7320556640625)

> (sqrt 3) ; pour vérifier

#i1.7320508075688772

> (< (abs (- 1.73199462890625 1.7320556640625)) 0.0001)

12 Exercice 6.8.12

Les arguments qui suivent relèvent d’une mathématique de combat, et ne sont là que pour forcer l’adhésion d’un lecteur pas trop pointilleux...

a) Les logarithmes étant tous égaux à une constante multiplicative près, je raisonne en base 10. Le nombre de chiffres de 10k est k+1, équivalent à k lorsque k est grand. Or k n’est autre que le logarithme de 10k en base 10. Donc le nombre de chiffres de n varie comme log(n).

b) On multiplie un nombre à log(p) chiffres par un nombre à log(q) chiffres. Lorsqu’on le fait à la main, le calcul s’inscrit dans une matrice rectangulaire de log(p) x log(q) chiffres.

c) log(n!) = n log(n-1) est équivalent à n log(n) lorsque n est grand.

d) Le coût cn de calculer n! = n x (n-1)! est obtenu en ajoutant le coût de calculer (n-1)! qui est cn-1 au coût de calculer le produit de n [qui a log(n) chiffres] par (n-1)! [qui a n log(n) chiffres]. Enfin, très sommairement, si l’on intègre n log2(n), on obtient une partie principale en n2 log2(n).

13 Exercice 6.8.13

Un grand classique, qui n’a hélas que peu d’utilité lorsque n est grand car il fait trop de calculs...

b) Si l’on n’a pas trouvé de diviseur de n dans [2,sqrt(n)], il ne peut y en avoir dans [sqrt(n),n[. Car sinon, soit d un tel diviseur. Alors d’=n/d serait aussi un diviseur de n, mais cette fois inférieur à sqrt(n), d’où la contradiction.

(define (ppdiv n) ; le plus petit diviseur de n dans[2,n]

(local [(define (iter d) ; d impair, aucun diviseur dans [2,d[

(cond ((> (sqr d) n) n) ; il est premier !

((zero? (modulo n d)) d) ; on le tient !

(else (iter (+ d 2)))))]

(if (even? n) 2 (iter 3))))

> (ppdiv 74959052506543)

2011

> (ppdiv 10000079) ; il est premier !

10000079

d) On divise l’exposant par 2 et l’on réduit modulo n pour que les calculs intermédiaires n’explosent pas !

(define (exptmod a e n) ; tres rapide !

(cond ((zero? e) 1)

((even? e) (modulo (sqr (exptmod a (quotient e 2) n)) n))

(else (modulo (* a (sqr (exptmod a (quotient e 2) n))) n))))

e) Il suffit de savoir tirer au hasard un entier de [2,n-1] qui soit premier avec n :

(define (random-base n)

(local [(define a (+ 2 (srandom (- n 2))))) ; srandom !! cf ci-dessous...

(if (= 1 (gcd a n))

(random-base n))))

MAIS ATTENTION, LE GENERATEUR DE RACKET EST UN PEU FAIBLARD, il ne dépasse pas 10 chiffres ! Je vous suggère de télécharger le fichier srandom.rkt qui est dû je crois (?) à Dorai Sitaram, et qui permet d’avoir des entiers aléatoires en précision "infinie". Ceci fait, il suffit de placer en haut de votre fichier-programme la directive d’importation de ce fichier (voir livre page 154) :

(require "srandom.rkt")

> (srandom 10000000000000000000000000000000000000000000000000)

6107557415962218298601574722182070394698558603264

f) Il s’agit de 1050 + 151

g) Il suffit de savoir construire l’entier 333...31 qui contient k fois le chiffre 3 :

(define (make31 k) ; 333...331 avec k fois le chiffre 3

(local [(define (make3 k) ; 333...33 avec k fois le chiffre 3

(if (= k 0)

(+ (* (make3 (- k 1)) 10) 3)))]

(+ (* (make3 k) 10) 1)))

> (make31 5)

333331

h) Si je ne m’abuse il y en a deux qui sont 10000019 et 10000079...