Itérations (while)
Algo & Prog avec R
A. Malapert, B. Martin, M. Pelleau, et J.-P. Roy
4 octobre 2021
Université Côte d’Azur, CNRS, I3S, France
[Link]@[Link]
Problème → Algorithme → Programme
I Partons d’un problème.
I Soit à faire calculer la somme des entiers de [1, n], avec n entier ≥ 1.
S = 1 + 2 + 3 + ... + n − 1 + n
I Cette somme S dépendant de n, intéressons-nous à la fonction S(n).
n
X
S(n) = 1 + 2 + 3 + . . . + n − 1 + n = i
i=1
I Il s’agit de construire un algorithme de calcul de S(n) : une méthode
mécanique permettant d’arriver au résultat.
I Une fois un tel algorithme obtenu, il s’agira de coder la fonction S
dans un langage de programmation, ici R.
I Pour produire au final un programme exécutable sur machine.
1/13
Calculs répétitifs
Je veux calculer S(1000)
Faire le calcul à la main est facile, long et prodigieusement ennuyeux :
1 + 2 + 3 + 4 + 5 + 6 + 7 + . . . + 1000. Ouf.
Je ne veux pas FAIRE le calcul
je veux le FAIRE FAIRE par un ordinateur (computer).
Il me faut donc écrire un programme court qui explique à la machine par
quelles étapes passer. La taille du programme ne dépendra pas de n, mais
le temps de calcul probablement.
Trois méthodes classiques pour construire un algorithme
I Le calcul direct.
I La récurrence.
I La boucle.
2/13
Les calculs répétitifs : CALCUL DIRECT !
Rarement possible, demande souvent un peu d’astuce, comme celle de
Gauss vers ses 14 ans :
S(n) = 1 + 2 + 3 + ... + n − 1 + n
S(n) = n + n − 1 + n − 2 + ... + 2 + 1
2 × S(n) = n + 1 + n + 1 + n + 1 + . . . + n + 1 + n + 1
En R
> S < - f u n c t i o n ( n ) { r e t u r n ( n * ( n + 1) / 2) }
> cat ( ’S (1000) = ’ , S (1000) , ’\ n ’)
S (1000) = 500500
I La taille du programme (longueur de son texte) ne dépend pas de n,
qui ne sera fourni qu’à l’exécution.
I Le temps d’exécution du calcul de S(1000) est immédiat.
Il coûte 3 opérations.
3/13
Les calculs répétitifs : RÉCURRENCE
Appréciée des matheux, elle permet souvent d’attaquer des problèmes
difficiles en . . . supposant le problème résolu !
Il s’agit de réduire le problème S(n) à un problème S(k) avec k < n. On
prend souvent k = n − 1 ou n ÷ 2. On remarque ici que pour n > 0 :
S(n) = (1 + 2 + 3 + . . . + n − 1) + n = S(n − 1) + n
Si l’on sait calculer S(n − 1), on sait donc calculer S(n). Or on sait
calculer S(1) = 1, d’où un calcul de proche en proche :
S(2) = S(1) + 2 = 3 S(3) = S(2) + 3 = 6 S(4) = S(3) + 4 = 10
Récurrence (math) → récursivité (info)
Une fonction récursive s‘appelle elle-même.
S <- f u n c t i o n (n) {
i f ( n <= 0) r e t u r n (0)
e l s e r e t u r n ( S ( n - 1) + n )
}
4/13
Les calculs répétitifs : RÉCURRENCE
Récurrence (math) → récursivité (info)
Une fonction récursive s‘appelle elle-même.
S <- f u n c t i o n (n) {
i f ( n <= 0) r e t u r n (0)
e l s e r e t u r n ( S ( n - 1) + n )
}
I La taille du programme ne dépend toujours pas de n, qui ne sera
fourni qu’à l’exécution.
I Le temps d’exécution du calcul de S(1000) est linéaire.
Il coûte n opérations.
R n’encourage pas la récurrence et ne l’optimise pas !
> S (1000)
Erreur : é valuations trop profond é ment imbriqu é es : r é
cursion infinie / . . .
4/13
Les calculs répétitifs : BOUCLES
Plus populaire chez les programmeurs, elle tâche de présenter le calcul
comme une succession d’étapes identiques portant sur des variables qui
changent de valeur à chaque étape.
L’important est la situation et non l’action.
I Qu’allons-nous faire ? I Où en sommes-nous ?
I Comment procéder ? I Quelle est la situation générale ?
I J’ai commencé à calculer S(n). En plein milieu du calcul, où en
suis-je ?
I Par exemple, j’ai déjà calculé 1 + 2 + 3 + . . . + i. Introduisons une
variable acc représentant cette accumulation. Nous gérons donc
deux variables i et acc.
INITIALISATION ITÉRATION TERMINAISON
Trouver les valeurs Passer à Détecter si
initiales des variables. l’étape suivante. le calcul est terminé.
5/13
Construire une itération
Une fois la situation générale trouvée, voici les trois temps de la
construction d’une itération :
Passer à l’étape suivante (ITÉRATION)
Étant en possession de acc = 1 + 2 + · · · + i, on voudra obtenir la valeur
de 1 + 2 + . . . + i + (i + 1). Il suffira donc d’ajouter i + 1 à acc et
d’ajouter 1 à i.
Détecter si le calcul est terminé (TERMINAISON)
On aura terminé lorsque i sera égal à n puisqu’alors acc vaudra S(n).
Trouver les valeurs initiales des variables (INITIALISATION)
Au début du calcul, je peux prendre i = 1 et acc = 1.
Je pourrais aussi prendre i = 0 et acc = 0 . . .
Le tout, c’est que ma situation générale acc = 1 + 2 + . . . + i soit vraie
en début de boucle.
Si l’une de ces étapes s’avère trop difficile, il faudra envisager de trouver
une autre situation générale
6/13
Visualiser une boucle
i <- 0 FALSE FIN
INV i <n ?
acc <- 0 Le résultat est acc.
TRUE
i <- i + 1
acc <- acc + i
À chaque entrée dans la boucle, au point INV, la situation générale
acc = 1 + 2 + · · · + i est vérifiée !
S <- f u n c t i o n (n) {
i <- 0
acc < - 0 On boucle tant que i < n. Une des
w h i l e (i < n) { manières d’exprimer une boucle
i <- i + 1
acc < - acc + i
consiste à utiliser le mot-clé while
} qui signifie "tant que".
r e t u r n ( acc )
7/13
}
Commutation d’instructions
MISE EN GARDE : deux instructions ne commutent pas en général.
Les deux suites d’instructions ci-dessous ne sont PAS équivalentes.
i <- i + 1 i = 2 RUN i = 3
acc < - acc + i acc = 3 −−→ acc = 6
Cette suite d’instruction serait fausse.
acc < - acc + i i = 2 RUN i = 3
i <- i + 1 acc = 3 −−→ acc = 5
Il s’agit d’un point noir des boucles dans les langages impératifs.
Deux instructions peuvent commuter si elles sont indépendantes.
Or ci-dessus, l’affectation de i modifie la valeur de i dans l’affectation de
acc.
Problème important à l’heure des processeurs à plusieurs cœurs.
Si chaque cœur modifie des variables . . .
8/13
Mise au point ou debuggage
Il arrive aux meilleurs programmeurs de produire des programmes
incorrects.
Comment puis-je m’aider à détecter une erreur ?
Réponse : en espionnant la boucle . . .
La méthode classique du printf
On fait afficher les variables de boucle (les variables qui varient dans la
boucle), ici acc et i. Observe-t-on une anomalie ?
w h i l e (i < n) {
cat ( ’i = ’ , i , ’ acc = ’ , acc , ’\ n ’)
...
La méthode plus avancée du browser
La fonction browser interrompt l’exécution de votre programme et
permet l’inspection de l’environnement d’où a été appelée browser.
w h i l e (i < n) {
browser ()
...
9/13
Comment savoir si un nombre est premier ?
Les nombres premiers 2, 3, 5, 7, 11... jouent un rôle important dans les
codes secrets (cartes bancaires, mots de passe, etc).
Un entier n est toujours divisible par 1 et n, qui sont ses diviseurs
triviaux. Par exemple 12 est divisible par 1 et 12 (et par d’autres) . . .
Un entier n est premier s’il est ≥ 2 et si ses seuls diviseurs sont les
diviseurs triviaux. Par exemple 13 est premier, mais pas 12.
Test de primalité (algorithme naïf)
Pour savoir si un nombre n ≥ 2 est premier, il suffit donc d’examiner les
nombres entiers d de [2, n − 1] à la recherche d’un diviseur de n.
I Si l’on en trouve un, on s’arrête au premier avec le résultat FALSE.
I Sinon, le résultat sera TRUE.
Quelle est la situation générale ?
J’en suis au nombre d que je n’ai pas encore examiné, et je n’ai toujours
pas trouvé de diviseur.
10/13
Implémentation du test de primalité
EstPremier < - f u n c t i o n ( n ) {
i f ( n < 2) r e t u r n ( FALSE ) # 0 et 1 ne sont pas p r e m i e r s
d < - 2 # le premier d i v i s e u r non trivial
w h i l e ( d < n) {
i f ( n %% d = = 0) r e t u r n ( FALSE ) # É c h a p p e m e n t
d <- d + 1
}
r e t u r n ( TRUE )
}
> cat ( ’ 2001 est premier : ’ , EstPremier (2001) , ’\ n ’)
2001 est premier : FALSE
> cat ( ’ 2003 est premier : ’ , EstPremier (2003) , ’\ n ’)
2003 est premier : TRUE
Quel est le nombre d’opérations de notre test de primalité ?
> EstPremier (2 * * 31 - 1)
Ctrl-D ou Ctrl-C (Keyboard interrupt)
11/13
Les boucles infinies et l’instruction break
Boucle while
Il est essentiel de s’assurer que la boucle termine, w h i l e ( < test >) {
donc que le <test> finit par prendre la valeur < instruction >
< instruction >
FALSE . Sinon le programme entre dans une ...
boucle infinie et . . . on perd la main, il plante ! }
Boucle repeat
Pourtant certains programmeurs optent pour un repeat {
style de boucle infinie dans lequel la décision < instruction >
< instruction >
d’échappement est prise parmi les instructions du ...
corps de la boucle avec l’instruction break. }
x <- 1
x <- 1
repeat {
w h i l e ( x <= 5) {
⇐⇒ i f ( x > 5) b r e a k
x <- x +1
x <- x +1
}
} 12/13
Boucle repeat
repeat {
L’instruction break provoque une sortie < instr >
brutale de la boucle, mais le programme i f ( x > 5) b r e a k
< instr >
continue son exécution après la boucle ! }
# reprise ici
Quel intérêt ? Il se trouve que certaines boucles de ce type vont avoir le
test de sortie en milieu ou en fin de boucle. Il pourrait même y avoir
plusieurs tests de sortie . . .
x <- 1 [1] 3
repeat { [1] 7
i f ( x %% 11 = = 0) b r e a k [1] 15
RUN
i f ( x %% 17 = = 0) b r e a k
x <- 2 * x +1
−−→ [1]
[1]
31
63
print ( x ) [1] 127
} [1] 255
Cette boucle est donc la plus générale mais elle suppose que l’on
13/13
garantisse bien sa terminaison, sinon GARE !
Questions?
Retrouvez ce cours sur le site web
[Link]/~malapert/R
13/13
Calcul de la somme harmonique
Somme harmonique
n
1 1 1 1 X1
S(n) = 1 + + + ... + + =
2 3 n−1 n k
k=1
Oresme (1360) savait déjà que S(n) tend vers +∞ lorsque n → +∞, les
matheux disent que la série harmonique diverge.
Récurrence Itération
S <- f u n c t i o n (n) { S <- f u n c t i o n (n) {
i f ( n <= 0) r e t u r n (0) i f ( n <= 0) r e t u r n (0)
e l s e r e t u r n ( S ( n - 1) + 1 / n ) acc < - 1
} i <- 1
w h i l e (i < n) {
i <- i + 1
Vectorisation (plus tard) acc < - acc + 1 / i
S <- f u n c t i o n (n) { }
i f ( n <= 0) r e t u r n (0) r e t u r n ( acc )
e l s e r e t u r n ( sum (1 / (1 : n ) ) }
}
la série harmonique diverge lentement . . .
Combien faut-il de termes dans la somme pour que S(n) ≥ 8 ?
Avec la fonction S Avec un code dédié
> n <- 1 > acc < - 1 ;
> w h i l e ( S ( n ) < 8) { n < - n + 1} > n <- 1;
> n > w h i l e ( acc < 8) {
[1] 1674 + n <- n + 1
+ acc < - acc + 1 / n
+ }
> n
[1] 1674
Quelle est l’approche la plus sûre ? La plus efficace ?
Et pour que S(n) ≥ 16 ?
> w h i l e ( acc < 16) {
+ n <- n + 1
+ acc < - acc + 1 / n
+ }
> n
[1] 4989191
