0% ont trouvé ce document utile (0 vote)
282 vues44 pagesAlgo Dunod 2
Transféré par
Libasse Laye MbengueCopyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF ou lisez en ligne sur Scribd
0% ont trouvé ce document utile (0 vote)
282 vues44 pagesAlgo Dunod 2
Transféré par
Libasse Laye MbengueCopyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF ou lisez en ligne sur Scribd
Chapitre 1
Preuve et complexité
Un algorithme (O, V, S) est formé d’un ensemble fini © d’opérations liées par une
structure de contréle S et dont les opérandes portent sur un ensemble fini V de va-
riables. Un algorithme résout le probléme P si pour tout énoncé I de P (stocké dans
le sous-ensemble des variables d’ entrée de V), d’une part la suite des opérations exé-
cutées est finie (condition de terminaison) et si d’ autre part, lors de la terminaison,
le sous-ensemble des variables de sortie de V contient le résultat associé a I’énoncé
1 (condition de validité). Prouver un algorithme, c’est démontrer mathématiquement
que la propriété précédente est satisfaite. Une mesure de complexité d’un algorithme
est une estimation de son temps de calcul, mémoire utilisée ou de toute autre unité
significative. On s’intéresse le plus souvent a la recherche d’une estimation par ex-
cés A une constante positive multiplicative prés du cas le plus défavorable sur le sous-
ensemble des énoncés de taille fixée n (complexité dite « pire-cas »). On obtient ainsi
le taux asymptotique de croissance de la mesure indépendamment de la machine sur
laquelle l’algorithme est exécuté et l’on peut alors comparer les complexités pire-cas
de plusieurs algorithmes résolvant un méme probléme.
Ce chapitre propose d’exercer cette démarche d’analyse sur des algorithmes de base,
itératifs et récursifs, en demandant le développement détaillé des preuves & l’ aide
de questions progressives. Afin de définir rigoureusement la notion de mesure de
complexité, nous introduisons les trois notations de Landau relatives aux ensembles
de fonctions O(g), Ag) et (8), lorsque g est une fonction de N dans N. 1+ Preuve et comp,
—OMPIeyi,
Définition 1.1 Borne supérieure asymptotique
O(g(n)) = {f : N— N| 3k > Oet ng > 0 tels que
Van > no 9 N| 3k > Oetng > Otels que
Va > m9 O 0, by > Det no > Otels’que
Va 2m O< A gn) < fin) m
Sil’on prend k = 10° et no = 1, il est évident que
Ww 1
done n? € O(10-n°).
Pour la seconde relation, remarquons tout d’abord que
25n* — 19? + 132 < 25n* + 190? + 13m? < (25+ 19 + 13)n* Yn > 1
On en déduit que 25n4 — 19n? + 13n? € O(n’).
I suffit en effet de choisir k = 25+ 19 + 13 = 57 etmo = 1.
Finalement, soit k = 2! et no = 0, il est évident que
2mt100 < k2" Wn > mo
2. Mest évident que O(1) ¢ O(n) C7?) C O(n), puisque
t1 : ro
1 + Preuve et compleritg
On ue
4 également O(1) C O(logn) C O(n) C O(n logn), puisque
1 3 6.
et
logn I i
et pour la méme raison, O(n logn) C O(n").
On montre facilement que O(n) C O(2"). En effet, 2
mw <2" & logn’ < log2" < 3logn < nlog(2) oO
qui est vrai & partir dune certaine valeur de n puisque logn € O(n). Po
Loordre d’inclusion est done finalement =
O11) C Otlogn) C O(n) C Olnlogn) C O(n?) < OVW) < OR") D
Un algorithme ayant une complexité logarithmique sera donc meilleur (en terme de a
complexité) qu'un algorithme linéaire, lui-méme meilleur qu'un algorithme polyno- Pe
mial, A son tour meilleur qu'un algorithme exponentiel.
3. Le tableau suivant est calculé en utilisant un logarithme népérien : D
8.
nm
s
Test intéressant de remarquer que 1,15 x 10"? s = 36 $58 ans. c
4, Sif(n) € O(g(n)), alors il existe k > O-et no > Otels que
f(n) < kein) Yn 2 no I
‘On déduit de l’expression précédente que ‘
tpn) M0 1
Donc g(n) est en Mf(n)). j
5. Sif(n) € O(g(n)), alors il existe k > O et no > 0 tels que
f(n) < kg(n) Yn 2 M0
On déduit de l'expression précédente que
f(n) + gin) < (k + gin) Yn 2 20
Done f(n) + g(n) est en O(g(n)). 1 * Preuve et complexité
6. De facon évidente,
max(F(n),8(n)) < fin) + gin) < 2max(f(n),g(n)) Yn > 0
fin) + a(n) est done en @(max(f(n),g(n)))
7. Pour montrer I’ égalité des deux ensemb
faut montrer la double inclusion, bss OFC) + gla) et Oman fin). gem, i
O(f(n) + g(x) C OCmax(f(n),g(n))) +
Pour toute fonction h(n) € O(f(n) + g(n)), i existe k > O-et no > Otels que
h(n) < k(n) + g(n)) < 2k max(fin),g(n)) Yn > mp
Done h(n) est donc en O(max(/(n),g(n))).
Otmax(f(n),g(n))) C O(F(n) + gin) :
Pour toute fonction h(n) € O(max(f(n),g(n))), il existe k > O et no > Otels que
h(n) < kmax(f(n),g(n)) < k(f(n) + gn) Yn > no
Done h(n) est en O(f(n) + g(n)).
8 Si S(n) € O(f(n)) et T(n) € O(g(n), alors il existe k > 0, K > 0,m > Oet
ny > Otels que
Sin) < kf(n) Yn > no
T(n) < K’g(n) Yn > my
Si f(n) € O(e(n)), alors il existe K” > O et nj > Otels que
Fn) < K'g(n) Yn > mo
On définit alors K = kk” + K/ et mg = max(no,np.ng). De fagon évidente :
S(n) + Tin) < p(n) + Ki gin) < (KK" + Kain) = Kg(n) in > mo
Done S(n) + T(n) est en O(g(n))-
Si dans un algorithme, on a une premiére partie en Of
d'une seconde partie en O(g(n)) et que fin) € O(8(")).
lement en O(g(n)).
(n)) suivie (séquentiellement)
alors l’algorithme est globa-
9. De la méme fagon, si on définit K = Kk et my = max(no,np), on a de fagon
évidente :
S(n)T(n) < Kf(n)g(n) Vn > mo
Done S(n)T(n) est en O(f(n)g(”))-
Si dans un algorithme, on a une pre!
uée une seconde partie en O(g()) 2
mitre partie en O(f(n)) dans laquelle est imbri-
ors l’algorithme est globalement en O(f(n)g(n)). Exe
we 1.2 Somme des éléments d'
‘OIA un tableau de n entiers (n> 1).
1. Ecrire un alg
Cet algorithme.
‘un tableau
orithme itératif qui calcute la somme des éléments de A et prow
Wer
2. Déterminer la complexité de cet algorithme.
3. Ecrire un algorithme récursif
eee qui calcule la somme des éléments de A et prow.
4. Déterminer la complexité de cet algorithme récursif.
Solution de I’exercice
1. Lalgorithme calculant la somme des n éléments du tableau A est le suivant :
Somme : entier
Somme — 0
pour i — | an faire
Somme — Somme + A(i]
fin pour
Pour prouver cet algorithme il faut démontrer deux choses : la terminaison et la
validité de I'algorithme.
La terminaison de I’algorithme est triviale puisque la boucle est exécutée m fois et que
Je corps de la boucle n'est constitué que d'une somme et d'une affectation, opérations
qui s’exécutent en un temps fini.
Pour démontrer la validité, nous allons considérer la propriété suivante : « Ala fin
de Vitération i, la variable Somme contient la somme des i premiers éléments &
tableau A ». Notons Somme; la valeur de la variable Somme & la fin de Vitération
ct Sommer = 0 sa valeur initiale. On effectue alors un raisonnement par récuren®
sur i, La propriété est trivialement vraie pour i = | puisqu’a I'issue de la premiere
itération Somme (initialisée a 0) contient la valeur A[1] :
Somme, = Somme + Al) = All]
Maintenant, si on suppose que la propriété est vraie pour une eee
i
Somme; =) AUI
jel
fin &
A la fin de l'itération i + 1, Somme contiendra la valeur qu'elle contenait
Vitération i, donc la somme des i premiers éléments, plus A[i+ 1] qui ia
riety 1 + Preuve et complexite
1+ Preuve et complexité
— _,
ari
itération i+ 1. Somme ser, i
@ done bien la somme des j
S i+] premiers 616
S éléments de A :
Sommeis1 = Somme; +Ali+
1=Yaui+au+y =>
xy ] Lau
Vraie initialement, la propriété reste vraie ach; itérati
lement, la propriété aque nouvelle itération. Cette
est done Ea ere llgorithme. On pared imariant de boucle Lalgcrthone
terminant, & la fin de V’itération n, il aura donc bien caleulé I élémen
tereinat, a somme des n éléments
2. On s'intéresse au nombre a(n) d additions effectuées par lalgorithme. De fagon
évidente, a(n) = n. On en déduit que Valgorithme est en O(n). I est a noter, que
Vinégalité a(n) < n suffisait 4 aboutir a cette
conclusion. On peut par ailleurs déduire
de l’inégalité a(n) > n que l’algorithme est en ((n) et donc finalement conclure qu'il
est en O(n).
3. La fonction récursive calculant la somme des éléments du tableau A est la sui-
vante :
fonction Somme_Rec(A : tableau ; n : entier) : entier
sin<0
alors
retourner(0)
sinon
retourner(Somme_Rec(A, n — 1)+A[n})
fin si
a
inai écurrence sur i. De fagon évidente
"bord la terminaison, par ré -Defagon évidente
i eal gyno Somme_Rec avec le paramétre 0 se eon a a,
Fran eesomge Tappel de la fonction Somme.Ree avec un pa ee
Si on suppose aie cometion Somme_Rec avec le parametren + 1, appelle la fonction
mine, I’appel de la fonts mercer hypotheses termine, sot ' sla
ea de At te pararine. Don quelle que soit a valeur du paramétre app
la valeur de A[r] e .
™ ine.
de la fonction Somme_Ree 8°17) appel de la fonction Somme_Rec avec le
ir retourmée par AFP a relation mathématique de réeur-
On note Sommen la valeur retoumO
dont la solution (évidente) est a(n) = n. On en déduit, & nouveau, que l’algorithme
est & la fois en O(n) et en 1(n), donc globalement en O(n).
Exercice 1.3 Fonctions F et G mystéres
4. Soit la fonction récursive F d'un paramétre entier n suivante :
ee
fonction F(n : entier) : entier
sin=0
alors
retourner(2)
sinon
retourner(F(n — 1) * F(n — 1)
fin si
ae
Que calcule cette fonction ? Le prouver.
2 Déterminer la complexité de la fonction F. Comment améliorer cette com
plexité?
3. Soit la fonction itérative G suivante :
ee
fonction G(n : entier) : entier
R:entier
Re2
pour i — 1 an faire
R—R*R
fin pour
retourner(R)
ee
|
ammaeonzmeer> is Freuve et complexité
Que calcule cette fonction? Le Prouver.
4, Déterminer la complexité de la fonction G.
Solution de I'exercice
1. On calcule les premieres valeurs calculées par la fonction F
FO) =2
Fl) =242=22
FQ) = 2? «22
De fagon intuitive, on obtient Iexpression générale de F(n) :
F(n) = 2”
Afin de le prouver, il faut démontrer la terminaison et la validité de lalgorithme.
La terminaison de la fonction F se démontre par récurrence sur n. De fagon évi-
dente, Iappel de la fonction F avec un paramétre 0 se termine immédiatement. Si on
suppose que l’appel de la fonction F avec un parametre n se termine, I’appel de la
fonction F avec le paramétre n+1 appelle deux fois la fonction F avec le paramatre n,
ces deux appels se terminant par hypothése, multiplie les deux résultats (identiques)
obtenus et se termine.
Sion note F, la valeur retournée par I’appel de la fonction F avec le paramétre n, la
fonction récursive F reproduit la relation mathématique suivante :
0
Frit =F) sin>0
On montre alors par récurrence sur n que la solution de cette relation de récurrence
est:
satisfaite pour n = 0. Si on la suppose satisfaite pour n,
Cet ion est bien 5
sales ia relation de récurrence :
F, = 2%, on calcule Fnsi & partir de |
Fo = FR = OPP =
foe
On montre done bien par récurrence que, Pour tout n > 0, Fy, = 2°.
2. On s’intéresse au nombre m(n) de multiplications effectuées. m() est solution de
l’équation de récurrence :
0 sin=0
min) = {3 424m —1) sin>0 1+ Preuve et comy
On mo rs
ntre tr&s faci
tres facilement par récurrence que m(n) = > 2! = 2" ~ 1. On en dédiy
jue I ‘=o
5 algorithme est en @(2") et posséde donc une complexité exponentielle,
our amé
“Our améliorer l’algorithme, il suffit bien évidemment d’éviter le double appel rg
Cursif; la fonction F s*écrit alors
fonction F(n: entier) : entier
sin=0
alors
retourner(2)
sinon
retourner(F(n — 1)°)
fin si
On calcule alors la complexité par rapport au nombre c(n) d’appels de la fonction
« carré », e(n) est solution de I’équation de récurrence :
ee sin=0
(= Vem—1)+1 sin>0
De fagon évidente, c(n) = n. On en déduit que le nouvel algorithme est en ©(n)
3. La fonction G calcule la méme valeur que la fonction F. Pour le démontrer il faut
prouver la terminaison et la validité de l’algorithme.
La terminaison est triviale puisque I’algorithme effectue n itérations.
Pour prouver la validité, il faut déterminer un invariant de boucle. On se propose de
prouver que la propriété suivante en est un : « A la fin de ’itération i, R = 2° ».
Cette propriété est vérifiée a la fin de la premitre itération, puisque R (initialisé &
2) vaut alors 4 = 2. Si on suppose que la propriété est vraie pour i, & la fin &
Vitération i+ 1, R = 22 * 2% = 22", La propriété est done bien un invariant de
boucle. Elle est donc vraie a la terminaison de l'algorithme. Celui-ci caleule done
bien 2”.
4, Si m(n) est & nouveau le nombre de multiplications effectuées par Lalgorithme,
de fagon évidente, m(n) = n. On en déduit que I’algorithme est en @(n)-
Exercice 1.4 Produit matriciel
A
On considare deux matrices carrées (d’entiers) d’ordre n, A et B. Le produit
par B est une matrice carrée C définie par :
Cus = Din Bes
a
1+ Preuve
1, Dor
forme |
Doit-o
plexité
2. Mo
Ja mat
Solution
1, Lialgo
i,j. ken
pour i —
pour j
Cli
pou
¢
fin |
fin po
fin pour
Silons
Falgoritt
rithme e
2. Valg
ijkee
Pour i «
Pour.
Cli
por
(
fin
fin pe
fin pou
Le noml
Onend 1+ Preuve et complexité
1. Donner un algorithme calculant le produit
n produit de deux matri
forme d’un tableau & deux dimensions, Calcul exit
Doit-on préciser dans quels cas (pire cas,
plexité est obtenue ?
S Teprésentées sous
ler la complexité de cet algorithme
meilleur des cas, cas moyen) cette com.
2. Modifier l’algorithme précédent lorsque la matrice A est de dimension (5
d 0 n ‘st de dimension (m,n) et
la matrice B de dimension (n,p). Quelle est alors la complexité de algorithms?
v
Solution de I’exercice
1, L’algorithme calculant le produit des deux matrices A et B est le suivant :
i,j,k: entier
pour i — 1 An faire
pour j— 1 An faire
Clij] — 0
pour k — 1 An faire
Cli] — Clif) + AULA x BU]
fin pour
fin pour
fin pour
ae eee eee
Si l'on s*intéresse au nombre a(n) d’additions (ou de multiplications) effectuées par
Palgorithme, on obtient de fagon immédiate que a(n) = n°. On en déduit que I'algo-
rithme est en (n°). II n’y a donc ici ni meilleur ni pire des cas.
2. L’algorithme modifié est le suivant :
i,j,k: entier
pour ij — | am faire
pour j — | ap faire
oe of an fail
our k — 1 an faire P
recta — Cll + AUEAL « BE
fin pour
fin pour
fin pour
coor
multiplications) effectuées est cette fois-ci a(n) = npm.
peering :
Lenombre d’additions (ou de roit donc linéairement par rapport &
On en déduit que I’algorithme est en O(npm) etc 1 Prin tt complery
et
chacune des dimenc;
noter cepen alimensions des deux matrices d’entrée prises individuellement. jg,
que cet algorithme ne sera pas globalement qualifié de « lingaire
Exercice 1.5 Complexité en fonction de deux paramétres
Déterminer la complexité des algorithmes suivants (par rapport au nombre qi
Tations effectuées), od m et n sont deux entiers positifs. ”
Algorithme A
ie lsjel
tant que (i < m) et (j < n) faire
iceit+l
jojtl
fin tant que
Algorithme B
ielsjeol
tant que (i < m) ou (j < n) faire
icitl
joj+l
fin tant que
Algorithme C
ie ljjel
tant que j < n faire
sii TU) xx"
On en déduit que la fonction Calcul évalue le polynéme de degré n dont les coeffi
cients sont les valeurs du tableau 7, au point x:
so= DOT x¥
0
On vient en fait de démontrer la validité de l’algorithme. Il reste & vérifier la termi-
naison. Celle-ci est bien stir triviale puisque I'algorithme n’est constitué que d'une
boucle de n itérations.
3. Une fonction récursive réalisant le méme calcul est donnée ci-dessous :
fonction Calcul(T : tableau; x: réel; n,j :entier) : réel
sij=n
alors
retourner(T{n})
sinon
retourner(T{j] +x x Calcul(T, x, n,j + 1))
fin si
oo
0.Siot
L’appel initial de la fonction Calcul doit s’effectuer avec le paramétre i
note Calcul; la valeur retournée par l’appel de la fonction Calcul avec le parame
cette fonction récursive reproduit la relation mathématique de récurrence suiv#"™
Calcul, = T{n} et Calcul; = TU] +x x Calculjs1
1s Prewwe|
Cette relat
prouver I
Ja méme fe
Exercice
On con
On che
tableau
on rect
1. Do
un invé
2. Ac
rithme
3B A
Valgo
4. Bo
avec c
5. Pr
6. Ce
silor
Solutior
1, Des
suivant :
fonctior
Pos : en
Pos — 1
tant qu
Pos «
fin tant
retourn
Nest ar 1+ Preuve et complexité
— 4s
Cette relation est exactement la mér
’ me que i
prouver l'algorithme itératif, La prouve de Va Scat
Ja méme fagon que précédemment.
mn de récurrence permettant de
algorithme récursif s’effectue done de
Exercice 1.7 Recherche séquentielle
on consider on bl 4 de : éléments, que I’on suppose trié en ordre croissant.
in algorithme permettant de savoir &
; i s quel endroit du
tableau se trouve une valeur clé. (On supposera que clé est bien dans le tableau et
on recherchera la premigre occurrence de cette valeur.)
4, Donner un algorithme itératif qui résout ce probléme. Indiquer et démontrer
un invariant de boucle pour cet algorithme.
2. A quoi correspond le pire des cas? En déduire la complexité en O de I'algo-
rithme.
3. A quoi correspond le meilleur des cas? En déduire la complexité en O de
Valgorithme.
4, Kerire cet algorithme sous forme récursive et l’exécuter sur le tableau suivant
avec clé = 18.
78 9 12 15 [18 [22 [30 [31]
5. Prouver l’algorithme récursif.
6. Comment faut-il modifier ces versions (itérative et récursive) de algorithme
§;l’on n'est pas sir que clé appartienne au tableau ?
Solution de I’exercice
4. Das que I’on est str que elé appartient bien au tableau A, I’algorithme est le
suivant :
sentier
fonction Cherche_Seq_lt(A = tableau; n, clé : entier)
Pos: entier
Pos—1
tant que A[Pos] # clé faire
Pos — Pos +1
fin tant que
retourner(Pos)
Test 4 noter que l’algorithme ne tire pas profit du fait que le tableau soit trié. a 1° Pr
Tl faut @abora i
@Ppartient bien a
xing
Montrer que cet algorithme se termin ,
wtableaud: joeete
3k clé)
alors
retourner(Nondéfini)
sinon
si A[r] = clé
alors
retourner(n — r+ 1)
sinon
retourner(Cherche_Seq_Rec(A, n, clé, r— 1))
fin si
fin si
So
ee
Exercice 1.8 Recherche dichotomique
On se place dans les mémes conditions que celles de l’exercice 1.7 (A est ®
tableau trié de n éléments). On définit l’algorithme suivant :
fonction Cherche_Dich_I(A : tableau ; n, clé : entier) : entier
d Of — 1; trouve — faux
répéter
pe (oth ie ontié é et y
m3 -\% Partie entiére inferieure de “ % 2
si A[i] = clé clé
alors tab
trouve — vrai ine
sinon la
siA[i] < clé alors d — i+ 1 sinonf — i— 1 fin si
fin si
jusqu’a trouve
retourner(i)
come 1» Preuve et complexité a
4, Développer cet algorithme sur le tableau suivant avec clé = 30,
1} 7/8] 9] 12] 15] 18] 22 [30] 31]
2. Indiquer un invariant de boucle répéter pour cet algorithme.
3. On suppose que le tableau A[1..n] contient n = 2* éléments (oi k est un entier
positif). Combien d’itérations I’algorithme effectuera-t-il au maximum ?
4, En déduire la complexité (en O) de l’algorithme.
5. Pour k = 100 comparer les complexités des algorithmes de recherche séquen-
tielle et dichotomique.
6. Ecrire I’algorithme sous forme récursive et I'exécuter sur I’exemple de la
question 1.
7. Prouver la validité de cet algorithme.
8. Déterminer la complexité (en Q) de I’ algorithme récursif.
9. Comment faut il modifier ces versions (itérative et récursive) de l’algorithme
sil’on n’est pas sfir que clé appartienne au tableau ?
Solution de I’exercice
4. On représente les valeurs des variables i, d, fet trouve, & V initialisation et & la fin
de chaque itération :
i|d| f | trowe
nit |—[1]10| faux
Finit.1] 5 [6 | 10| faux
Fin it.2 | 8 | 9 | 10| faux
Fin it.3 | 9] 9 | 10] vrai
2. Invariant de boucle : « A la fin de la °"* itération, soit Afi] contient la valeur
clé, soit l intervalle (d..f] a diminué (par rapport a litération précédente) et le sous-
tableau Afd.,f] contient la valeur clé ». En convenant, comme habituellement, qu’en
indexant par k une variable, on fait référence & la valeur de cette variable & la fin de
la" jtération, I’invariant précédent s’écrit =
Soit {Alig] = clé et trouver = vrai},
soit {dy < fi et clé € Aldy-fil et (de > dk ou fi < fi} wewtlUlUlUlUlUrC—
=
ing
Cet invariant
tableay le N'est vrai que si le tableau A est trié et si clé est bien un éléme
effet 8 ch ret de Prouver la fois la terminaison et Ia vaidité du programme
strictem, laque itération, soit on a trouvé Ja valeur clé, soit on obtient un interyaj,
io lent plus petit que celui de I'itération précédente, dont on est sir qu'il con le
valeur clé. Au pire lalgorithme se terminera donc sur un sous-tableay A(q,
réduit a un seul élément, avec Aldi] = Alfil = clé. ‘fl
3. Pour tout entier n > 0, vn représente le nombre maximum d’itérations de j
fonction Cherche_Dich_It pour un tableau de n éléments qui contientlaclé,
Pour n = 1, onav; = 1. Pourn = 2! avec k > 0, alors chaque sous-tableau poss,
au plus 24! éléments et vx < 1 + vz-1. On en déduit que vx 0, soit k = flog, n]. On observe que n < 24 et ainsi v, <),
Or, d’aprés la question précédente, vy. < 1+k = 1+ [logy n]. On en déduit done que
Vn < 1+ [log n] et que l’algorithme est en O(log,(n)) = O(log(n)).
5. Pour k = 100 (et dans le pire des cas) l’algorithme séquentiel effectuer,
2100 ~ 10% itérations, alors que l’algorithme dichotomique n’en effectuera que
100. (Si l’on considére une machine trés puissante, capable d’effectuer 1 million de
boucles en 1 seconde, I’algorithme récursif prendra 3 10'° années de calcul, alors
que l’algorithme dichotomique fournira le résultat en moins d'une milliseconde !)
6. L’algorithme récursif est le suivant :
ee
fonction Cherche_Dich_Rec(A : tableau; n, clé, d, f : entier) : entier
/ att
i-lyd
si Ali] = clé
alors
si A[i] < clé
alors
retourner(Cherche_Dich_Rec(A, n, clé, i+ 1p)
sinon
tourner(Cherche_Dich_Rec(A, n, clé, d, i — 1)
fin si
fin si
Sa a
L’exécution est la suivante :
Cherche_Dich_Rec(A, 10, 30, 1, 10) 5 et A[5] = 12 < 30
active Cherche_Dich_Rec(A, 10, 30,6, 10) i= 8 et A[8] =
active Cherche_Dich_Rec(A, 10, 30,9, 10) i=9etA[91=
2< 30
30
ies
rete
retour
retourne
7. Onva
que l'app
sous-tabl
(et que c
Cette pre
et I’appe
valeur i.
On supp
f-d+l
parametr
Ie « mili
Si Ali] =
tel que A
Si Ali] <
paraméti
ou égal
clé est f
appel se
Si Ali] >
paramét
est infér
la « bon
termine
Done I’
et renvo
8. Lal;
gueur (
méme ¢
est diff
rithme
identiq
9%. Sil
Suivant, 1+ Preuve et complexité
retourne 9
retourne 9
retourne 9
7. On va montrer par récurrence sur le nombre d’éléments du tableau k =f —d+1
que l’appel de la fonction Cherche_Dich_Rec se termine et renvoie un l'indice i du
sous-tableau A(d.,f] tel que Ali] = clé, si clé appartient bien au sous-tableau Ald. f]
(et que ce tableau est bien trié par ordre croissant).
Cette propriété est bien str vraie pour k = 1, car sid =f, par hypothése
Ali) = Ald] = Alf] = clé
et 'appel de la fonction Cherche_Dich_Rec se termine immédiatement et retourne la
valeur i.
On suppose que la propriété est vraie pour toutes valeurs de d et f telles que
f —d+1 clé, 1a fonction renvoie la valeur de I'appel récursif de la fonction avec les
paramétres d et i — 1. A nouveau, le nombre d’éléments du sous-tableau Ald..i- 1)
est inférieur ou égal Ak (i — 1) —d+1 = id < &), et la fonction se rappelle sur
la « bonne » partie du tableau Afd..i — 1}. Par hypothése de récurrence, cet appel se
termine et renvoie I'indice du sous-tableau contenant la valeur clé,
Done I’appel de la fonction Cherche_Dich_Rec avec les paramétres d et f se termine
et renvoie bien I"indice du sous-tableau contenant la valeur clé.
& Llalgorithme récursif « coupe » le tableau en deux sous-tableaux de méme lon-
= +.
‘gueur (A une unité prés), teste la valeur « milieu » i = (et | et se rappelle lui-
méme sur la moitié du tableau contenant I’élément clé, tant que I’élément milieu
est différent de la valeur clé. I s'agit exactement du méme algorithme que I’algo-
Tithme dichotomique itératif. Le calcul de complexité (et donc le résultat) sont donc
identiques. On en déduit que I’algorithme est en Olox(n)).
9. Si on n'est pas sir que clé appatienne au tableau, I'algorithme itératif est le
suivant. A nouveau, Nondéfini correspond 2 une valeur non définie et pourra étre © Pr
+ Preuve et com
22
1
Py
Teprésentée par une valeur en i ri
tigre n’appartenant pas a | qe
tableau, Pe et arp
— eee
fonction Cherche_Dich_It(A : tableau ; n, clé : entier) : entier
delifen
trouve — faux; fin — faux
répéter
sid>f
alors
fin — vrai
sinon
fin:
i
|
ie (St
si Ali] = clé
alors r
trouve — vrai 1
sinon
si A[i] < clé
alors
d-itl
sinon
fei-l
fin si
fin si
fin si
jusqu’a trouve ou fin
si trouve
alors
retourner(i)
sinon
retourner(Nondéfini)
La version récursive est la suivante :
fonction Cherche_Dich_Rec(A : tableau ; n, clé, d, f : entier) : entier
sid>f
alors
retourner(Nondéfini)
sinon
. dt+f 1
fey
si A[i] = clé
alors
retourner‘(i) 1+ Preuve et complexité
sinon
si Ali] < clé
alors
retourner( Cherche_Dich_Rec(A, n, clé, i+ 1. f))
|
retourner(Cherche_Dich_Rec(A, n, clé, aga
Exercice 1.9 Facteurs premiers
La décomposition en facteurs premiers d'un nombre entier consiste & représenter
cet entier de la maniére suivante : n = a}'a3" ...a{* od les a; sont des nombres
premiers tels que a; < a; pour i < jet les b, sont des entiers strictement positifs.
1, Montrer que la décomposition en facteurs premiers d'un entier est unique.
Un entier n peut donc étre représenté par un tableau T A deux entrées. Le premier
champ de la? position (T[i,1]) contient a, et le deuxitme (7[i,2]) contient by.
Soient T; et T; les tableaux représentant deux entiers m; et mz. On note Taille, et
Taille; les tailles des tableaux T; et Tz (par rapport & la premiére entrée).
Soit la fonction PGCD suivante :
_
fonction PGCD(T;, T : tableau): entier
pecd, p\, p2: entier
pecd —1;pl—1;p2—1
tant que (p1 < Taille,) et (p2 < Taille) faire
si Ty[p1.1] = T2lp2.1)
alors
m — min(T;{p1,21T21p2.2))
peed — pged x (Tilpl.1"
pl—pl+l
p2— p2+l
sinon
si T)[pt.1] < Talp21)
alors
plepitl
sinon
p2 + p2+
si
fin si
fin tant que
retourmertpgcd) 2. Prouvey
rf 7 ‘i :
nh; wee in la fonction PGCD calcule le PGCD (Plus grand commun ive,
3. Déterminer la complexité de la fonction PGCD.
Solution de rexercice
1. On considére deux décompositions m et nz d’un méme entiern, Supposer que cg,
deux décompositions sont différentes équivaut & dire qu’a partir d'un cenaine Valey
££¢s deux décompositions different, soit parce qu'un facteur premier appara
Pune et pas dans I’autre :
my = ab? a
1 gh pea
m= abd... i
avec
soit parce que la puissance d'un méme facteur premier est différente dans une
dans autre :
avec
bp #B,
Dans le premier cas, on suppose (sans perte de généralités) que ay < ai, On monte
alors que n; est divisible par a, alors que nz ne I’est pas. En effet, aucun des facteus
de nz n'est divisible par ap : ni les aj, i < p — 1, puisque, par convention de le
décomposition en facteurs premiers de n), aj < dp pour tout i < p et les a sont fous
des nombres premiers; ni les aj, p < i < q/, puisque a’; > a’, pour tout i 2?
et les a’; sont des nombres premiers. On en déduit que n; 4 np, ce qui contredit
Vhypothése que m; et nz sont deux décompositions d’un méme entier n.
i
Dans le deuxitme cas, on suppose que by < bj. ny est alors divisible par ay’ oar
que n; ne l’est pas. Une démonstration similaire a la précédente peut étre est
en déduit quem, # np, ce qui contredit & nouveau I'hypothése que m; et mz sont
décompositions d’un méme entier n.
son Pune ds
2. On monte d’abord Ia terminaison de Valgorthme. A chaque itération, Pune
deux variables p1 et p2 (ou les deux) augmente d’une unité et I’algorithme s Tet
lorsque I’une de ces deux valeurs a dépassé la taille du tableau correspondant.
clair dans ces conditions que I’algorithme se termine.
Afin de
est un
tableat
différe
On me
rithme
re
Alaf
premic
contie!
soit ils
Te PGC
Sions
Ia fin
La prc
Lorsq
pli
sont v
rithme
etlav
déron:
fin de
que, n
que le
Tl faut
Alaf
On p
Palgo
Mainj
que p
condi
On e1
obtie:
n'ont
que k
conti 1+ preuve et complexité
‘Afin de démontrer la validité de I’algorithme, on introduit la notation suivante. Si
at un tableau représentant un entier n = aba? ...a!, on note 7” (p < ky le sou :
rentier aa ...a?? i i .
tableau représentant l'entier aa’? ... af”. Par ailleurs, on indice par i la valeur des
différentes variables de I’algorithme a la fin de la ime itération de la boucle tant que.
On montre alors que la propriété suivante est un invariant de boucle pour I’algo-
rithme : « A la fin de 'itération i, pgcd; contient la valeur du PGCD de T{"""! et de
a “1 1
A la fin de la premiére itération, cette propriété est vraie. En effet, soit les deux
premiers facteurs premiers de T; et T2 sont identiques (T} [1,1] = 73[1,1)) et peed,
contient alors, par construction, le PGCD de 7} et de 7} ( HE MEL ALTELAD
soit ils sont différents et pgcd; contient alors la valeur initiale 1, qui représente bien
le PGCD de T? = Let de T} , ou de T} et de 3 = 1.
Si on suppose que la propriété est vraie a la fin de l’itération i, elle le sera également a
Ja fin de l’itération i+ 1, la démonstration étant, 4 nouveau, similaire a la précédente.
La propriété est donc bien un invariant de I’algorithme.
Lorsque I’algorithme se termine (ce qui correspond & une itération i), alors soit
pl; = Taille, + 1, soit p2; = Taille; + 1. Dans le cas ou Jes deux égalités précédentes
sont vraies simultanément, l’invariant démontre immédiatement la validité de l’algo-
rithme puisque, dans ces conditions, 77!""' = Ty" = Ty et TE! = Thal = T,,
et la valeur finale de la variable pgcd contient donc bien le PGCD de 7; et T2. Consi-
dérons maintenant le cas ob p1; = Taille, +1 et p2; < Taille. D'aprés V invariant, & la
fin de ’algorithme pgcd contient le PGCD de 7; et 78", On se rend alors compte
que, méme si cela peut paraitre évident, rien dans invariant ne permet de démontrer
que le PGCD de 7; et 7”! est le méme que celui de 7; et To.
1 faut done rajouter dans V’invariant la propriété suivante :
A afin de l'itération i,
sipl)=pliat) alors Tifplia1] < Talp2-11)
sip) =p%1+1 alors Tolp2ivt] p2i-1) sont donc forcément plus grands
que le plus grand facteur premier de T- On en déduit qu’a la fin de Yalgorithme pgcd
Contient bien le PGCD de T; et T2- een,
3. A chag .
dune unité ee de I'algorithme l'une des deux variables, p! ou p2, ay
taille dogs algorithme sate lorsque Tune de ces deux valeurs ade"
iate, une So reed Taille, ov Taille;. On obtient donc, de fagon me
» Une complexité en O(Taille, + Taille2) (en suy t que lex;
une variable s’effectue en O(1)). ‘ ae PONENtiation 5
Exercice 1.10 Suite de Fibonacci
Les propriétés de cette suite sont trés utiles pour calculer la complexité de cena
algorithmes. Nous rappelons la définition de la suite de Fibonacci :
0 sin=0
F,=41 sin=1
Fai +Fa-2 sin >2
1. Ecrire un algorithme récursif qui calcule F,.
1+V5
2
2. Montrer que F, = k(o" ~ $) pour tout n > 0 (odd =
v5
nombre d'or et & + est son conjugué).
3. Montrer que F, > (" ~ 1) pour tout 20.
est
4. Soit a(n) le nombre d’additions effectuées par V'algorithme. Montrer gx
a(n) = Fri — 1.
5. En déduire la complexité de I'algorithme récursif.
6. Proposer un algorithme itératif de meilleure complexité.
Solution de I’exercice
1 La fonction Fibo suivante calcule le 1°" terme de la suite de Fibonacci :
fonction Fibo(n : entier) : entier
sin=0
alors
retourner(0)
sinon
sin=1
alors
retourner(1)
sinon
retourner(Fibo(n — 1) + Fibo(n — 2)) 1 Preuve et complexité
27
fin si
fin si
oo
2. Nous allons résoudre I’équation de récurrence :
Fy = Fy. + Fra
avec comme conditions initiales F; = 1 et Fy = 0.
Pour cela, il faut d’abord déterminer la solution générale de cette équation, puis trou-
ver parmi toutes ces solutions, une solution qui satisfasse aux conditions initiales.
Pour déterminer la solution générale, on associe I’ équation de récurrence
Fy — Fr—1 — Fn_2 = 0,
T’équation caractéristique suivante :
#-g-1=0
dont les racines sont :
1+V5 5 1-V5
b= at b=
La solution générale de I’ équation de récurrence est alors de la forme
Cid" + Cod"
Il reste a déterminer les valeurs des constantes C; et C2 en utilisant les conditions
initiales. La condition Fy = 0 implique que C) = —C). Et en remplagant C2 par
=C, dans la deuxiéme condition (F; = 1), on obtient :
1
al-
Fp =Cid-CG=1 + C=
o-¢
La solution de cette équation de récurrence est done :
1 =n.
=l¢"- 9)
haa
3. Ona montré que
1
Fr= we -¢)
Or || < 1 done $" < 1, ce qui implique que
1
"1
F,2 Gq@"-D 28 SB
i et comple
4. Soi
; ee) le nombre d’additions effectuées par l'algorithme pour le calcul du yx
le la suite de Fibonacci. a(n) s*exprime de la fagon suivante =
_ fo sin=Ooun=1
260) = (oon — san 2)41 sin>2
On s’apergoit que lorsque n > 2 la forme de I’équation récursive donnant a(n) ey
similaire a celle qui relie les nombres de Fibonacci. Plus précisément, les premier,
€léments des deux suites sont :
nm [oltj2[3/4[5[6|7]| 8
f }o{1|1/2[3|5| 8 | 13] 2
ain) | 0[o[1|2]4]7| 12 | 20| 33
On montre alors par récurrence que a(n) = F41 ~ 1. Cette relation est bien str vai
pour n = Let n = 2. On suppose la proposition vraie pour tout k 1. L’algorithme a une complexité exponentel
6. Pour calculer le n?"* nombre de Fibonacci, il suffit uniquement de connaitre
done de mémoriser) le (n — 1)* et le (n — 2)'"* nombre de Fibonacci.
fonction Fibo_It(n : entier) : entier
x,y, 2: entier
sin=0
alors
retourner(0)
sinon
xeOyelszel
pour i — 2 an faire
zeoxty
xey
yeu
fin pour
fin si
retourner(z) Dans ce cas, le nombre d’additions effectuées par l'algorithme es
terminé par le nombre d'itérations (n — 2). Lalgorithme est en On Me™
n).
Exercice 1.11 Calcul récursif du PGCD
Nous allons utiliser les résultats de l’exercice 1.10 pour analyser la complexité de
Lalgorithme de calcul récursif du PGCD (Plus grand commun diviseur) de deux
nombres.
1. Soient x et y, deux entiers tels que x > y > 0. Que vaut PGCD(x,0)?
Montrez. que PGCD(x,y) = PGCD(y,x mod y). En déduire la fonction récursive
PGCD(x, y : entier) avec x > y > 0 qui calcule le PGCD de ces deux valeurs.
2. Soit n(x.y) le nombre de divisions (« mod ») effectuées par lalgorithme. Mon-
trer que
_ fo siy=0
nay) = i +n(y,x mod y) _sinon
Nous allons montrer que pour x > y > 0: (xy) = k => x > Fay2 00 Fig est le
(+2)? terme de la suite de Fibonacci.
3. Montrer que la proposition est vraie pour k = Oet k= 1.
Nous supposons maintenant k 2 2.
4. Montrer la proposition par récurrence.
5. En déduire que /5x+1 > $?.
6. En déduire que n(x,y) < logy(V5x + 1) ~ 2 et done que n(xy) € O(log x).
Solution de I’exercice
i iers tels que x > y > 0. Siy = 0, PGCD(x,0) = x. On
cena 0. (On noe P ~p6cp(e) et p! = PGCD(y,x mod y).
Soit q et r le quotient et le reste de la division Euclidienne de x par y. Par définition,
x=qgytr.
— Par définition de p, p|x et ply. Done, p|r et donc pip.
— Par définition de p’, p'ly et p'|r- Done, p’ bx et done pp.
On en déduit que p =P’.
Lalgorithme d’Euclide calculant le PGCD de x et y s’écrit de la fagon suivante :
fonction PGCD(x, y : entier) : enter
siy=0
alors
retourner(x) sinon
retou
fingp TPGCDLy, x mod y))
rr
2 Siy =
Roa 0, Valgorithme retourne 1a valeur 0 sans faire aucune division, dog.
Supposons que y > 0. Soient z = x mod y et n();2) le nombre de divisions effects,
Par l’algorithme pour le calcul du PGCD de y et z. Il est évident que le premier appe|
de l'algorithme effectue une division pour le calcul de z = x mod y, puis appelie
PGCD(y,2), done n(x,y) = 1 + nly,
3. Si k = 0, aucune division n'est effectuée par I'algorithme, cela implique que
y =0.Commex > y,x > F2=1.
Si k = 1, une seule division est effectuée par I'algorithme, impliquant que y > 0«
x mod y = 0, donc x = qy. Or par hypothése x > y. Done q > Oet x > Fy = 2
4. On suppose que si n(x,y) = j.
si n(xy) = k+ 1, alors x > Fias-
x et y peuvent alors se mettre sous la forme
alors x > Fx,2, pour tout j < k. On va montrer que
x=qytz0 Fy.2, et que n(z,t) = k — Let done z > Fei. Or
X=QytTDY+Z > Fasr + Fest = Firs.
La propriété est donc vraie.
5. Utilisant le résultat de I’exercice 1.10, Fk > 3(¢* — 1). Alors,
Le ghz
at 1
x2 ye? )
En réarrangeant |’ expression précédente, on en déduit que
VSx+1 > gh?
6. En passant au logarithme (A base 4) dans VSx +1 > $2, on obtient
k < logg(V5x + 1) ~ 2. La complexité de I'algorithme PGCD est done en 0108
et est donc linéaire en la taille (log x) du codage de l’entrée.
= Sel
te rr com, 11 © Preuve et complexité
Exercice 1.12 PGCD de rn entiers
On considére le probléme du calcul du PGCD. (plus grand commun diviseur) de
n entiers a1, ~ ,dy strictement positifs et inférieurs A une constante ¢
Ds titre K.
Une donnée du probléme est constituée d'une liste L = @1,--- ay) Games
rangés dans un sous-tableau T{i. j] d'un tableau T 08 j — i+1 ~ ». On admet par
convention que le plus grand commun diviseur d'un seul entier strictement positif
est cet entier lui-méme. La longueur d'un énoncé est mesurée par n
1. Quelle hypothése justifie cette mesure de la longueur d'un énoncé ?
On considére alors la fonction récursive PGCD_Gen(T.i,j) définie comme suit
oi la fonction PGCD(x,y), de complexité O(log(max{p.q})). implémente I'algo-
rithme d’Euclide (cf. exercice 1.11) pour calculer le plus grand commun diviseur
de deux entiers positifs x et y.
fonction PGCD_Gen(T : tableau ; i, j : entie!
nej-i+l
kei+l¥-1
p — PGCD_Gen(T, i, k)
q— PGCD_Gen(T, k +1,))
retourner(PGCD(p, ))
fin si
So
consik i j= = 8,6, 12,27]. Repré-
i la donnée i = 1, j = 7 et TU1..7] = [6.15,21.1 n
Se reecas appels récursifs en étiquetant chaque sommet par le couple (i,j)
des indices associés & cet appel. 7
3. Donner la liste chronologique des appels a la fonction PGCD(p,q) en indiquant
pour chaque appel les valeurs de p et q- /
4. On veut prouver la fonction PGCD_Gen\T,i,j) par récurrence sur n = j—i+1.
1. Formuler la propriété & démontrer. :
ue cette propriété est vraic pour n = ; /
> Mone i" quoi correspondent les Apo ra 7 ea récursif des
eae i,k) et PGCD_Gen(T.k + 1,j)?
Conieed PACD Geni) par la fonction PGCD_Gen(T.i,) est le plus
ac eal aoe des entiers du tableau 7{i..j]. En déduire que la pro-
comm
priété est vraie pour tout 7. =
Soit GC
n) la foncti
_. tion ité
n= co i,
Fist eeu’ ” complet de PGCD_Gen(Tij) mesurée par es
. : €n compte toutes les opérations élémentair; u
. Exp eS Usuel,
Pliquer Pourquo; i
exécutée 3 la qa i, quelle que soit 1a donnée 7[i..], le nombre do rt
esten oxi), faa Te ligne de la fonction PGCD_Gen (retourner(PGC D2
: ‘duire qu’en dehors des di I ra)
ration OD 8 des deux appels récursifs, le nombre 2)
ONS exécutées par PGCD_Gen(Tij) est en O(1). ~
6. Justifier alors po
urn > I Vinégalité (i) ci-dessous ott C est une
Strictement positive : oe
OM 1, Végalite (iy
U=C+Uy+Uin Gi
Démontrer par récurrence sur n que G(n) < Uy.
8. Ecrire (ii) pour n = 2* et montrer que si I’on pose Vi = Uy, ona:
v,-f a sik=0
FE | C#Mi1 sik
En déduire qu'il existe une constante strictement positive M telle que
Uy < M2
9. Démontrer que U, est une suite croissante. Montrer que pour 2 1,
tj ste d’entie®
tion PGCD_Gen(Z,i,) renvoie le plus grand commun diviseur de la liste ¢
(TULT[i+ 1], +++ TE). »
ts rt Om Plen,
ane haem
pmeuwe
<< 1+ Preuve et complexité
33
an
Sr 47)
(4) 3)
«s) en
a2 23] [ao] fen ib a
Figure 1.12.1 Arbre des appels récursifs
2. Pour j — i+ 1 = 1, la valeur retournée est T[i] qui est bien, d’aprés la convention
de I’énoncé pour une liste d’un seul entier, le PGCD recherché.
3. Supposons la propriété vraie pour toute valeur de j — i+ 1 < met soit une donnée
Tli.,j] telle que j — i +1 = n > 1. Comme les deux sous-tableaux T{i..k] et
T[k + 1.,/] sont de taille strictement inférieure & n, les valeurs de p et q calculées
sont respectivement égales au PGCD des listes d’entiers de T{i..k] et Tlk + 1..j].
D’apras ce qui précéde, un diviseur commun & p et & gest un diviseur commun
de la liste des entiers de T[i..j]. Réciproquement, un diviseur commun de la liste
des entiers de T[i..j] est un diviseur de la liste des entiers de T{i..k] et de la liste
des entiers de T{k + 1.,j], donc un diviseur commun de p et de g. Tl en résulte que
PGCD(p,q) est le PGCD de la liste des entiers de Tli.,].
5. Comme p (resp. q) est le PGCD de la liste des entiers de T1i..k] (resp. TIk+ 1),
onap < Ketq < K. Comme la complexité de l’algorithme d'Euclide est
O(log(max{p,q})), le nombre d’opérations exécutées en dehors des deux appels
récursifs est majoré par une constante C > log(K) > 0.
i TMi. is cas, le nombre d’opéra-
6. Si T[i.,j] est une donnée correspondant au plus mauvais cas, :
tions exteutses par l’appel récursif PGCD_Gen(Ti,k) (resp. PGCD_Gen(T.k + 1,))
est au plus G(\!}) (resp. G([$]))- Hen résulte l’inégalité (i).
—1.0n
7 = 1 = Uj. Supposons que G(p) < Up pour 1
1, on a
8. Pourn = 2, ona |B) = (7) = Yj, = G(\). En remplagant itérativement (de
Vi = C+2Vj-1. Pour k = 0, 008 Vo =
j=k—1j = 1) Vjparssa valeur, il vient
Y= (28 +2! pe 21) 4 FG) Ten Tésulte oN
at Uys et User) > Urer. then
WE Uns > C+ U3) + Ups) = Uy. Un est done une suite crcneante ee
Fupposons que 2* Vous aimerez peut-être aussi
