CORRECTION

EXERCICE 1

E = Rn−1 [X], B = 1, X, . . . , X n−1 sa base canonique, a1 , . . . , an , n réels vériant : a1 < a2 < · · · < an .

1. Soit l'application : T : P 7→ (P (a1 ) , . . . , P (an )).

/ Linéarité. Si α ∈ R, les applications E → R, P 7→ P (α) sont des formes linéaires. Ainsi T est une
application linéaire de E vers Rn .
/ Injectivité. Soit P ∈ ker(T ). On a T (P ) = 0 donc (P (a1 ) , . . . , P (an )) = (0, 0, . . . , 0) et donc P
s'annule en au moins n réels distincts : les ak . Ainsi P est un polynôme de degré inférieur ou égal
à n − 1 s'annule en au moins n points distincts, donc c'est le polynôme nul. On en déduit donc que
ker(T ) ⊂ {0E }.
Par ailleurs, ker(T ) est un sous-espace vectoriel de E donc on a l'inclusion réciproque. Donc
ker(T ) = {0E } donc par caractérisation de l'injectivité des applications linéaires, T est injec-
tive.
/ Bijectivité. On a dim(E) = n = dim (Rn ). Donc comme T est une application injective de E vers
Rn , on a par caractérisation des isomorphismes en dimension nie,
T est un isomorphisme de E vers Rn

2. E = (e1 , . . . , en ) base canonique de Rn et pour tout i ∈ [[1, n]], on note Li = T −1 (ei ) et B 0 = (L1 , . . . , Ln ).
T est un isomorphisme de E vers Rn donc sa bijection réciproque, T −1 est un isomorphisme de Rn vers
E . Or B 0 est l'image de E par T −1 . Comme l'image par un isomorphisme d'une base de l'espace de
départ est une base de l'espace d'arrivée , on en déduit que B0 = (L1 , . . . , Ln ) est une base de E .
n
Soit P ∈ E et (λ1 , λ2 , . . . , λn ) ses coordonnées dans la base B . On a P = λk Lk . On évalue cette
X
0

k=1
relation en aj , sachant que comme Li = T −1 (aj ) = 1 si i = j et 0 si i 6= j . On obtient alors P (aj ) = λj
n
ce qui donne la coordonnée selon Lk de P dans la base B0 . Ainsi .
X
P = P (ak ) Lk
k=1
On note M = (mi,j )16i,j6n la matrice de passage de la base B à la base B 0

3. Dans cette question uniquement, on suppose que n = 3, a1 = 0, a2 = 1 et a3 = 2.

3.1 Comme les Lk sont de degré 6 n − 1, s'annulent en les aj pour j 6= k et valent 1 enak , on trouve :
(X − 1)(X − 2) 3 1 X(X − 1) 1 1
L1 = = 1 − X + X 2 , L2 = −X(2 − X) = 0 + 2X − X 2 et L3 = = 0 − X + X2
2 2 2 2 2 2
.    
1 0 0 2 0 0
1
On en déduit la matrice de (L1 , L2 , L3 ) dans 1, X, X 2 : M = − 32 2 − 12  = −3 4 −1



1 2
2
−1 12 1 −2 1
 
0 0 0
1
3.2 M −I3 = −3 2 −1 qui est de rang 2 (une ligne nulle donc matrice non inversible et deux premières
2
1 −2 −1
colonnes non colinéaires donc rang supérieur ou égal à 2). Ainsi 1 est une valeur propre de M . De
plus on remarque que dans cette  matrice
 M − I3 , la somme des deux premières colonnes donne la
1
troisième, ce qui signie que  1  est dans le noyau de M − I3 donc il est dans le sous-espace
−1

5
 propre E1 (M ) de M relatif à la valeur propre 1. Or, comme le rang de M − I3 vaut 2, la dimension

1
de E1 (M ) vaut 1. Donc E1 (M ) = vect  1 
−1
3.3 Soit P ∈ R2 [X]. On l'écrit sous la forme P = a + bX + cX 2 . Comme M est la matrice de T −1 dans
les bases E de R3 et B de R[X], on a :    
a a
P = P (0) + P (1)X + P (2)X ⇐⇒ T (P ) = (a, b, c) ⇐⇒ P = T (a, b, c) ⇐⇒ b = M b .
2 −1   
    c c
a 1
Ainsi P = P (0) + P (1)X + P (2)X ⇐⇒ b ∈ ker (M − I3 ) = vect
2     1 . Ainsi les
c −1
polynômes P de R2 [X] vériant : P (X) = P (0) + P (1)X + P (2)X sont les polynômes :
2

λ 1 + X − X 2 lorsque λ décrit R

4. On revient au cas général.

4.1 M est la matrice de passage d'une base vers une autre donc M est inversible .
M −1 estla matrice de T dans les bases Bet E. Or :  n−1 
1 a1 a21 a1
1  a2   a2  an−1 
T (1) =  .. , T (X) =  .. , T X 2 =  .. , . . ., T X n−1 =  .. . Ainsi on obtient
   
 2
 2 
. . .  . 
2
1 an an an−1
n
 
1 a1 a21 . . . an−11
1 a2 a2 . . . an−1 
M −1 =  .. .. . .
2 2
.. . . . .. 
 
. . 
2 n−1
1 an an . . . an
4.2 On utilise l'expression obtenue à la question 2. avec le polynôme constant égal à 1. On obtient
n n
1 (ai ) Li donc Li = 1 .
X X
1=
i=1 i=1
n
4.3 Par dénition de M , on a pour tout j ∈ [[1, n]], Lj = mi,j X i−1 . Ainsi :
X

! i=1
n n n
X i−1 .
X X X
1= Lj = mi,j
j=1 i=1 j=1
n
En particulier, pour tout i ∈ [[1, n]], la somme mi,j représente le coecient en X i−1 du polynôme
X

j=1
n n n
Lj = 1. Donc et, si i ∈ [[2, n]], mi,j = 0 .
X X X
m1,j = 1
j=1 j=1 j=1
n
Remarque : On pouvait aussi constater que ces sommes mi,j correspondaient aux coecients
X

j=1
de la première colonne de la matrice produit de M par M −1
car la première colonne de M −1 n'est
constituée que de 1.
n n
4.4 On reprend l'expression Lj . On a alors, pour tout j ∈ [[1, n]],
X X
i−1
= mi,j X mi,j = Lj (1) =
i=1 i=1

6
 n n
Lj (a1 ) ici car a1 = 1. Ainsi et, si j ∈ [[2, n]], mi,j = 0 .
X X
mi,1 = 1
i=1 i=1
n
Remarque On pouvait aussi constater que ces sommes mi,j correspondaient aux coecients de
X

i=1
la première ligne de la matrice produit de M −1 par M car la première ligne de M −1 n'est constituée
que de 1 car a1 = 1.
5. n > 4, a1 = 0, a2 = 1, a3 = 2 et u l'endomorphisme de E déni par : u(P ) = P (0)L1 + P (1)L2 + P (2)L3
5.1 / Noyau. Soit P ∈ E . P ∈ ker(u) ⇐⇒ P (0) = P (1) = P (2) = 0 car (L1 , L2 , L3 ) est libre. Ainsi
n o
ker(u) = X(X − 1)(X − 2)Q Q ∈ Rn−4 [X]

/ Image. D'après le théorème du rang, Im(u) est de dimension dim(E) − dim(ker(u)) = 3. Or on

a clairement Im(u) ⊂ vect (L1 , L2 , L3 ) qui est de dimension 3 car (L1 , L2 , L3 ) est libre. Ainsi
Im(u) = vect (L1 , L2 , L3 )
/ Supplémentaires. Soit P ∈ ker(u) ∩ Im(u). Il existe (a, b, c) ∈ R3 tel que P = aL1 + bL2 + cL3 .
En évaluant en 0, 1 et 2, on trouve respectivement a = 0, b = 0, c = 0. Donc P = 0E : Im(u)
et ker(u) sont en somme directe. Mais comme la somme de leurs dimensions est dim(E) par le
théorème du rang, on en déduit que Im(u) et ker(u) sont supplémentaires dans E
5.2 On sait déjà que 0 est valeur propre d'ordre de multiplicité n − 3 car ker(u) est de dimension
n − 3. Par ailleurs on vérie aisément que u (L1 ) = L1 , u (L2 ) = L2 et u (L3 ) = L3 . ainsi, comme
(L1 , L2 , L3 ) est une base de Im(u), on en déduit que u induit sur Im(u) l'endomorphisme identique
de Im(u) : 1 est une valeur propre de u et l'espace propre associé est Im(u).
Ainsi u est diagonalisable (car la somme des dimensions des sous-espaces propres est n la dimension
de E ) et ses valeurs propres sont 0 et 1.
Donc u est le projecteur d'axe Im(u) parallèlement à ker(u) Déterminer les éléments
propres de u et caractériser géométriquement u

7
 EXERCICE 2

I = [0, +∞[. E le R−espace vectoriel constitué des éléments f de C (I, R) tels que f 2 est intégrable sur I .
Questions de cours
1 2
Soit (a, b) ∈ R2 . On a (a − b)2 > 0 i.e. a2 + b2 > 2ab Ainsi ∀(a, b) ∈ R2 , ab 6 a + b2 .


1.
2
2. Soit (f, g) ∈ E 2 . D'après l'inégalité précédente, qui est également vrai en changeant a et −a, on a
1 2
f + g 2 . Or f et g sont dans E donc elles sont continues et leurs carrés f 2 et g 2 sont


fg 6
2
1
intégrables sur I . Ainsi par majoration, comme f g est continue positive et majorée par f 2 + g 2


2
qui est continue positive intégrable sur I , f g est intégrable sur I donc f g est intégrable sur I . Ainsi
le produit de deux éléments de E est intégrable sur I
3. / Existence. ϕ est bien dénie sur E et à valeurs dnas R car si (f, g) ∈ E 2 , f g est intégrable sur I .
/ Symétrie. Par commutativité du produit de fonctions à valeurs dans R, ϕ est symétrique.
Z Z Z
/ Bilinéarité. Soit (f, g, h) ∈ E et (a, b) ∈ R . ϕ(af + bh, g) = (af + bh)g = a f g + b hg par
3 2
I I I
linéarité de l'intégration. Ainsi ϕ(af + bh, g) = aϕ(f, g) + bϕ(h, g) : ϕ est linéaire à gauche. Par
symétrie, on en déduit que ϕ est bilinéaire.
/ Positivité. Soit
Z f ∈ E . f est une fonction continue positive intégrable sur I donc par positivité de
2

l'intégration, f 2 > 0 i.e. ϕ(f, f ) > 0 : ϕ est positive.

I
/ Dénie positivité. Soit f ∈ E telle que ϕ(f, f ) = 0. f 2 est une fonction continue positive intégrable
sur I et son intégrale sur I est nulle, donc f 2 est la fonction nulle sur I et donc f est la fonction
nulle sur I . Comme on a déjà vérié que ϕ était positive, on en déduit que ϕ est dénie positive
Ainsi ϕ dénie bien un produit scalaire sur E

Partie 1
Z +∞
Soit h élément de C (I, R), tel que l'intégrale h(t) dt converge.
0
Z +∞
1. On note H la primitive de h s'annulant en 0. Comme h(t) dt converge, H possède une limite nie
Z +∞ 0

en +inf ty et cette limite vaut ` = h(t) dt. Mais alors H(n) et H(n + 1) tendent vers ` lorsque n
0
tend vers +∞. Ainsi leur diérence, H(n + 1) − H(n) = Jn tend vers ` − ` = 0 lorsque n tend vers +∞.
Ainsi lim Jn = 0 .
n→+∞

2. Soit n ∈ N. la restriction de h à [n, n + 1] est continue sur ce segment donc est minorée et atteint son
minimum. On considère an ∈ [n, n + 1] tel que |h (an )| = min h − t) .
t∈[n,n+1]
Si h (an ) = 0, on a évidemment 0 6 |h (an )| 6 |Jn |.
Si h (an ) > 0. Alors comme h est continue sur le Zsegment [n, n + 1], h ne s'annulant pas sur [n, n + 1], h
n+1
est de signe constant sur [n, n + 1]. Donc |Jn | = h(t) dt > |h (an )|.
n
Dans tous les cas 0 6 |h (an )| 6 |Jn |. Ainsi par le théorème des gendarmes, on en déduit que h (an ) tend
vers 0 lorsque n tend vers +∞. Mais comme n 6 an , an tend vers +∞ lorsque n tend vers +∞. Ainsi
on a bien trouvé une suite (an )n∈N ∈ I N telle que : lim an = +∞ et lim h (an ) = 0 .
n→+∞ n→+∞

Partie 2
8
 Z +∞ Z +∞
F ensemble des applications f ∈ C (I, R), telles que t [f (t)] dt et [f 0 (t)] dt convergent. Soit
1 2 2 2

0 0
f ∈ F.
1. / f 2 est une fonction continue sur I . De plus ∀t ∈ [1, +∞[, f 2 (t) 6 t2 f 2 (t) et la fonction t ∈
[1, +∞[7→ t2 f 2 (t) est continue intégrable sur [1, +∞[. Donc par majoration, f 2 est intégrable sur
[1, +∞[. Or f 2 est continue sur le segment [0, 1] donc intégrable sur ce segment.
Z +∞
Ainsi f est intégrable sur I i.e.
2
[f (t)]2 dt converge .
0

/ On pose g1 et g2 les fonctions t ∈ I 7→ tf (t) et t ∈ I 7→ f 0 (t). g1 et g2 sont continues sur

I et de carré intégrable sur I , i.e. g1 et g2 sont dans E . Ainsi d'après la question de cours 2.,
Z +∞
le produit g1 g2 est intégrable sur I i.e. tf (t)f 0 (t) dt converge
0
.
2. On pose h la fonction dénie sur I par h(t) = t2 f 2 (t). h est continue et intégrable sur I = R+ . On choisit
une suite (an )n∈N ∈ I N telle que : lim an = +∞ et lim h (an ) = 0. Pour n ∈ N∗ , on intègre par parties
n→+∞
an n→+∞an a
tf 2 (t) n 1 an 2 h (an ) 1 an 2
Z Z Z Z
tf (t)f (t) dt. On obtient :
0
tf (t)f (t) dt = 0
− f (t) dt = − f (t) dt
0 0 2 0 2 0 2an 2 0
( remarquons queZan > 0 car an > nZ> 0).
+∞ +∞
Or les intégrales [f (t)]2 dt et tf (t)f 0 (t) dt sont convergentes et an tend vers +∞ lorsque n
0 Z an 0 Z +∞ Z an Z +∞
tend vers +∞ donc lim 0
tf (t)f (t) dt = tf (t)f (t) dt et lim
0 2
f (t) dt = f 2 (t) dt.
n→+∞ 0 0 n→+∞ 0 0
h (an )
Enn, lim = 0. Ainsi en passant à la limite dans la relation ci-dessus, on obtient :
n→+∞ 2an
Z +∞
1 +∞
Z
0
tf (t)f (t) dt = − [f (t)]2 dt .
0 2 0

3. On reprend les fonctions g1 : t ∈ I 7→ tf (t) et g2 : t ∈ I 7→ f 0 (t). Ces deux fonctions sont bien des
éléments de E car elles sont continues sur I et de carré intégrable sur I . Donc d'après l'inégalité de
Cauchy-Schwarz pour le produit scalaire ϕ de E , on a : g1 g2 6 g1 g2 .
2 2 2

Donc, en traduisantavec les intégrales, on a :

 Z +∞ 2 Z +∞ Z +∞
[f 0 (t)] dt.
0 2 2 2
tf (t)f (t) dt 6 t f (t) dt
0 0 0
Ainsi compte-tenu de l'égalité obtenue à la question précédente :
Z +∞ 2 Z +∞  Z +∞ 
2 2 2 0 2
[f (t)] dt 6 4 t [f (t)] dt [f (t)] dt (∗)
0 0 0

On a égalité dans (∗) si et seulement si on a égalité dans l'inégalité de Cauchy-Schwarz g1 g2 6

2
4.
g2 donc si et seulement si g1 et g2 sont colinéaires. Donc ceci est réalisé si et seulement si la
2 2
g1
fonction f est nulle ou si f est solution d'une équation diérentielle du type : f 0 (t) = atf (t) (H). Or les
solutions de (H) sont les fonctions : ja,λ : t ∈ I 7→ λeat /2 . Par toutes ces fonctions ja,λ les fonctions qui
2

sont dans F sont celles pour lesquelles soit λ est nul soit a est strictement négative.
Ainsi : les fonctions f pour lesquelles il y a égalité dans (∗) sont :
les fonctions t 7→ λe−α t avec (α, λ) ∈ R2
2 2

9
 EXERCICE 3

On considère une expérience aléatoire dont l'ensemble des résultats possibles est noté Ω.
Soient k ∈ N∗ et T une variable aléatoire dénie sur Ω et à valeurs dans [[0, k]].
On considère alors une suite (Xi )i∈[[0,k]] de variables aléatoires de même loi et toutes à valeurs dans Z.
On suppose que les variables aléatoires X0 , X1 , . . . , Xk et T sont mutuellement indépendantes.
T (ω)
On dénit la variable aléatoire Y par :
X
∀ω ∈ Ω, Y (ω) = Xi (ω)
i=0
1. Comme ([T = j])j∈[[0,k]] constitue un système complet d'événements, on a d'après la formule des proba-
bilités totales, on a :
k k
∀n ∈ Z, P(Y = n) = P(T = j, X0 + · · · + Xj = n).
X X
P(Y = n, T = j) =
j=0 j=0
Or les T et les Xi sont mutuellement indépendantes donc par le lemme des coalitions T et X0 + · · · + Xj
k
sont indépendantes. Ainsi ∀n ∈ Z, P(Y = n) = P(T = j)P (X0 + · · · + Xj = n).
X

j=0

On veut montrer que les séries nP(Y = n) et −nP(Y = −n) sont absolument convergentes donc,
X X

n∈N n∈N
comme les probabilités sont positives, on veut montrer que la série n (P(Y = n) + P(Y = −n)) est
X

n∈N
absolument convergente.
Or X0 , X1 , . . ., Xk admettent une espérance nie donc c'est aussi le cas pour X0 , X0 + X1 , . . .X0 +
X1 + · · · + Xk .X
Ainsi les séries n (P(X0 = n) + P(X0 = −n)), n (P(X0 + X1 = n) + P(X0 + X1 = −n)), . . .,
X X
n (P(X
n∈N n∈N n∈N
sont absolument convergentes. Comme la série n (P(Y = n) + P(Y = −n)) est une combinaison li-
X

n∈N
néaire des séries précédentes avec les coecients P(T = j), on en déduit qu'elle est absolument conver-
gente donc que
Y possède une espérance nie
La série n (P(Y = n) + P(Y = −n)) est combinaison linéaire des séries n (P(X0 = n) + P(X0 = −n)),
X X
2.
n∈N n∈N
..., n (P(X0 + X1 + · · · + Xk = n) + P(X0 + X1 + · · · + Xk = −n)) donc la somme de cette série est
X

n∈N
la combinaison linéaire des sommes de ces séries.
Or ces sommes sont les espérances respectives de X0 , X0 + X1 , ., X0 + · · · + Xk .
k
Ainsi E(Y ) = P(Y = j)E (X0 + · · · + Xj ).
X

j=0
Or par linéarité de l'espérance, on a E (X0 + · · · + Xj ) = E (X0 ) + · · · + E (Xj ) = (j + 1)E (X0 ) car les
Xj ont la même espérance. Ainsi :
k k k
jP(Y = j)E (X0 )+ (P(Y = j)E (X0 ) = E (X0 ) E(T )+E (X0 ).
X X X
E(Y ) = (j+1)P(Y = j)E (X0 ) =
j=0 j=0 j=0

Donc E(Y ) = (E(T ) + 1) E (X0 ) .

3. On suppose que E (X0 ) = 0 et que X02 possède une espérance.
On en déduit donc que! l'espérance de Y est nulle également.
k 2 k k k
On a Y 6 Xi2 . Ainsi
X X X X X X
2
Xi2 Xi2 Xi2 Xj2


Xi = +2 Xi Xj 6 + + 6 (k + 1)
i=0 i=0 i<j i=0 i<j i=0
Y 2 a une espérance nie.

10
La série n2 (P(Y = n) + P(Y = −n)) est combinaison linéaire des séries
X X
n2 (P(X0 = n) + P(X0 = −n))
n∈N n∈N
..., n (P(X0 + X1 + · · · + Xk = n) + P(X0 + X1 + · · · + Xk = −n)) donc la somme de cette série est
X
2

n∈N
la combinaison linéaire des sommes de ces séries.
Or ces sommes sont les espérances respectives de X02 , (X0 + X1 )2 , ., (X0 + · · · + Xk )2 .
De plus, par indépendance linéaire et linéarité de l'espérance, on a :
j
E (Xi ) E (Xk ) = (j + 1)E X02 car les espérances des Xi
X X
E (X0 + · · · + Xk )2 = E Xi2 +




i=0 06i<k6j
sont nulles. Ainsi par linéarité de l'espérance :
k
X k
X
2

2
(j + 1)P(Y = j)E (X0 )2


E Y = P(Y = j)E (X0 + · · · + Xj ) =
j=0 j=0
k k
Ainsi E Y 2 = (P(Y = j)E (X0 )2 = E (X0 )2 E(T ) + E (X0 )2 .
X X
jP(Y = j)E (X0 )2 +


j=0 j=0
Or d'après la formule de Koenig-Huygens, V(Y ) = E Y 2 − E(Y )2 , donc comme E(X0 ) = E(Y ) = 0,

on obtient alors : V(Y ) = (E(T ) + 1) V (X0 ) .

11
 EXERCICE 4

PARTIE A. Recherche de zéro d'une fonction

1. 1. La fonction f est continue et change de signe sur l'intervalle [a, b] donc, d'après le théorème des
valeurs intermédiaires, f s'annule sur [a, b] .
2. La recherche par dichotomie d'un zéro d'une fonction revient à construire les suites (an ) et (bn )
suivantes, dénies par a0 = a, b0 = b et pour tout n dans N,
  
a + b
bn si f (an )f
  n n
 an + bn si f (a )f an + bn 6 0,

6 0,


2

n
an+1 = 2 2 , bn+1 =
an sinon  an + bn sinon
 

2
D'où le programme suivant
1def rech_dicho (f ,a ,b , eps ):
2 """ f est une fonction continue telle que f(a )*f (b) <0,
3 avec a <b , eps un flottant >0 """
4 an = a # Initialisation
5 bn = b
6 while bn -an > eps : # Critere d ' arret
7 cn =( an + bn ) /2
8 if f( an )*f ( cn ) <=0:
9 bn = cn
10 else :
11 an = cn
12 return an , bn

2. 1. Posons g : x 7→ f (x) − x. Alors g(0) = f (0) − 0 > 0, g(1) = f (1) − 1 6 1. 0 ∈ [g(1), g(0)], g est
continue sur l'intervalle [0, 1] donc, d'après le théorème des valeurs intermédiaires, on dispose de
c ∈ [0, 1] tel que g(c) = 0, i.e. f (c) = c .
2. On va utiliser l'idée de la preuve de la question précédente, et appliquer la dichotomie à la fonction
x 7→ f (x) − x.
1def rech_pt_fixe (f ,x , eps ):
2 """ f est une fonction de [0 ,1] dans [0 ,1] , continue """
3 def g (x) : # Definition de la fonction auxilliaire
4 return f( x) - x
5 return rech_dicho (g ,0 ,1 , eps )

12
PARTIE B. Recherche dans une liste

1. 1.
1>>> L = [2 ,4 ,5 ,7 ,7 ,8 ,10] 1>>> rech_dicho (L ,0 ,5 ,1)
2>>> rech_dicho (L ,1 ,5 ,6) 2a= 0 , b= 5
3a= 1 , b= 5 3a= 0 , b= 2
4a= 1 , b= 3 4a= 0 , b= 1
53 50

2. Le programme rech_dicho(L,g,d,x) recherche et renvoie une position i entre g et d telle que

L[i-1]6 x 6 L[i], sachant que l'on suppose L[g:d+1] triée.
ak + b k ak + b k
3. Si ak et bk sont les valeurs de a et b à la k-ième étape, alors − 1 6 ck 6 . Alors
2 2
selon les deux cas de gure du test if, on obtient
ak + bk b k − ak
bk+1 − ak+1 = ck − ak 6 − ak 6 ,
2 2
ak + bk b k − ak
ou bien bk+1 − ak+1 = bk − (ck + 1) = bk − ck − 1 6 bk − 6 ,
2 2
donc, par une récurrence immédiate, bk − ak 6 2−k (d − g + 1), donc le programme s'arrête lorsque
bk − ak < 1, en particulier lorsque 2−k (d − g + 1) < 1, i.e. k > log2 (d − g + 1), d'où une complexité
en O(ln(d − g)).
2. Pour trier par insertion une liste L, on part du premier élément de L, puis on insère le deuxième élément
avant ou après ce premier élément, puis, de manière générale, lorsqu'on a une liste dont les k premiers
éléments sont triés, on insère le k + 1-ème dans ces k premiers éléments. Cette insertion se fait en deux
étapes : la recherche de la position de l'élément à proprement parler, puis l'insertion de l'élément. On
va eectuer cette insertion avec des permutations successives. On propose donc l'algorithme suivant :
1def tri_dicho (L ):
2 for k in range (1 , len (L )):
3 if L[k ]<L[k -1]: # Si on a besoin de bouger les elements
4 i = rech_dicho (L ,0 ,k -1 , L[ k ]) # On recherche la position
5 # de l ' element a inserer .
6 for j in range (k ,i , -1) : # On fait des permutations ,
7 L[ j], L[j -1] = L[j -1] , L [j] # en partant de la fin

3. Dans le programme précédent et si n = len(L),

• Il y a une première boucle à n − 1 étapes.
• Dans la boucle, on appelle rech_dicho, qui eectue O(ln(n)) comparaisons, d'où O(n ln(n)) com-
paraisons.
n
• Dans la boucle, on eectue k − i = O(k) aectations, d'où O( k) = O(n2 ) aectations.
X

k=1
Le tri par insertion classique est similaire, sauf pour la recherche de la position, pour laquelle on eectue
O(k) comparaisons. D'où, pour le tri par insertion classique, O(n2 ) aectations et O(n2 ) comparaisons.
Ainsi, le tri par insertion dichotomique permet un gain de complexité en termes de comparaisons, mais
pas en termes d'aectations.

13