\parindent=0mm


%***** Les fontes et les caract\`eres particuliers *****

\font\caml=cmtex10

\font\twelvern = cmbxsl10 at 12 pt
\font\itaten = cmti10
\font\bfsl=cmbxti10
\font\quinze = cmbxsl10 at 15 pt
\font\dix = cmbxsl10 at 11 pt

\font\tit=eufm10 at 25pt
\font\stit=eufm10 at 12pt
\font\mpa=eufm10

\def\rmat{{\bf R}}
\def\qmat{{\bf Q}}
\def\cmat{{\bf C}}
\def\nmat{{\bf N}}
\def\zmat{{\bf Z}}
\def\kmat{{\bf K}}

\font\mp=cmbsy10
\def\CC{\hbox{\mp C}}
\def\PP{\hbox{\mp P}}
\def\RR{\hbox{\mp R}}
\def\EE{\hbox{\mp E}}
\def\BB{\hbox{\mp B}}
\def\GG{\hbox{\mp G}}
\def\LL{\hbox{\mp L}}
\def\MM{\hbox{\mp M}}
\def\mm{\hbox{\mp M}}
\def\SS{\hbox{\mp S}}
\def\FF{\hbox{\mp F}}

\def\p{\hbox{\mpa p}}
\def\B{\hbox{\itaten B}}

\newfam\bbfam
\font\tenbb=cmbx10 
\textfont\bbfam=\tenbb \scriptfont\bbfam=\tenbb
\def\bb{\fam\bbfam\tenbb}

\def\R{\hbox{\bb R}}
\def\Z{\hbox{\bb Z}}
\def\Q{\hbox{\bb Q}}
\def\K{\hbox{\bb K}}
\def\C{\hbox{\bb C}}
\def\N{\hbox{\bb N}}

\def\im{\mathop{\rm Im}\nolimits}

\def\ch{\mathop{\rm ch}\nolimits}
\def\sh{\mathop{\rm sh}\nolimits}
\def\th{\mathop{\rm th}\nolimits}
\def\argch{\mathop{\rm argch}\nolimits}
\def\argsh{\mathop{\rm argsh}\nolimits}
\def\argth{\mathop{\rm argth}\nolimits}



%***** a10 Le format et les accents *****


%font black board de AMS

\catcode`\@=11

\hsize=150 true mm       \vsize=245 true mm
\hoffset=3.5mm       \voffset=-10mm
\pretolerance=500  \tolerance=1000  \brokenpenalty=5000

\catcode`\;=\active
\def;{\relax\ifhmode\ifdim\lastskip>\z@
\unskip\fi\kern.2em\fi\string;}

\catcode`\:=\active
\def:{\relax\ifhmode\ifdim\lastskip>\z@\unskip\fi
\penalty\@M\ \fi\string:}

\catcode`\!=\active
\def!{\relax\ifhmode\ifdim\lastskip>\z@
\unskip\fi\kern.2em\fi\string!}

\catcode`\?=\active
\def?{\relax\ifhmode\ifdim\lastskip>\z@
\unskip\fi\kern.2em\fi\string?}

\frenchspacing

\catcode`\@=12

%\catcode`\\'e=\active\def\'e{\'e} 
%\catcode`\\c{c}=\active\def\c{c}{\c c} 
%\catcode`\\`e=\active\def\`e{\`e} 
%\catcode`\\`a=\active\def\`a{\`a} 
%\catcode`\\`u=\active\def\`u{\`u}
%\catcode`\\^a=\active\def\^a{\^a}        % option i, then  a
%\catcode`\\^e=\active\def\^e{\^e}        % option i, then  e
%\catcode`\\^{\i}=\active\def\^{\i}{\^\i}       % option i, then  i
%\catcode`\\^o=\active\def\^o{\^o}        % option i, then  o
%\catcode`\\^u=\active\def\^u{\^u}        % option i, then  u
%\catcode`\\"{\i}=\active\def\"{\i}{\"\i}       %
%\catcode`\\"e=\active\def\"e{\"e}


%***** am20 Abr\'eviations et compteur *****

\def\tvi{\vrule height 12pt depth 5pt
width 0pt}

\let\vect=\overrightarrow
\let\ds=\displaystyle
\let\ep=\varepsilon
\let\ssi=\Longleftrightarrow

\def\uplet#1#2{(#1_1,#1_2,\dots,#1_#2)}
\def\resetcountCX{\count110=0}
\def\incrementeCX{\global\advance\count110 by 1}
\def\resetcountCC{\count112=0}
\def\incrementeCC{\global\advance\count112 by
1\resetcountCX} 
\resetcountCC
\def\chap{\number\count112}
\def\exo{\number\count110}
\def\itemitemitem{\par\indent\indent
\hangindent=3\parindent \textindent}

\def\section#1{\incrementeCC\resetcountCX{\twelvern \par\vskip
7mm\leftskip=0mm\number\count 112 {.\ #1}\par\vskip 4mm}\leftskip=10mm}
\def\ssection#1{\incrementeCX \par\vskip 3mm{\leftskip=5mm\dix\number\count 112
{.}\number\count 110 {.\ #1}\par\vskip 2mm}}
\def\titre#1{{\centerline{\mpth{\quinze #1}}} }
\def\exe{\incrementeCX\par\vskip 3mm{\hskip -10mm {\bf{Ex.\exo:$\ \ $}}}}

\def\LAcancel#1#2{\ooalign{$\hfil#1\mkern0mu/\hfil$\crcr$#1#2$}}
\def\not#1{\mathrel{\mathpalette\LAcancel#1}}

\def\boxit#1#2{\vbox{\hrule\hbox{\vrule\vbox
spread#1{\vfil\hbox
spread#1{\hfil#2\hfil}\vfil}\vrule}\hrule}}

\def\mpth#1{\vtop{\hrule\hbox{\vrule\vbox
spread 3pt{\vfil\hbox
spread 3pt{\hfil{\vbox{\hrule\hbox{\vrule\vbox
spread 15pt{\vfil\hbox
spread
15pt{\hfil#1\hfil}\vfil}\vrule}\hrule}}\hfil}\vfil}\vrule}
\hrule}}

\def\bboxit#1#2#3{\hbox{\vrule \hskip#1\vrule\vbox
spread#2{\vfil
 \hbox spread#2{\hfil #3\hfil}\vfil}}}

\def\mpdef#1{\vtop{\hbox{\vrule \hskip
2pt\vrule\vbox spread 6pt{\vfil
 \hbox spread 15pt{\hfil #1\hfil}\vfil}}}}

\def\mpprop{\par\hskip 0mm\hbox{{\underbar{Prop.}}\hskip  2mm{\vbox{\null
\vrule
\vtop spread 6pt{\vfil
 \hbox spread 15pt{\hfil {\box10}\hfil}\vfil}}}}\par}


\def\mpntend{\mathrel{\mathop{\kern
0pt{\longrightarrow}}\limits_{\scriptscriptstyle
n\rightarrow +\infty}}}

\def\mpxtend{\mathrel{\mathop{\kern
0pt{\longrightarrow}}\limits_{\scriptscriptstyle
x\rightarrow +\infty}}}

\def\mptend#1#2{\mathrel{\mathop{\kern
0pt{\longrightarrow}}\limits_{\scriptscriptstyle
#1\rightarrow #2}}}

\def\tsvp{
\def\page{Tournez S.V.P.}
\footline={\ifodd\pageno
{\hfil\tenrm\folio\hfil\tenrm
\page}\else {\hfil\tenrm\folio\hfil}\fi}}

\def\mpchap#1{\goodbreak\vskip
2cm\incrementeCC\centerline{\bf
\chap.--- #1:}\par\nobreak\vskip 5mm}

\def\mpexo{\vskip 6mm
\incrementeCX \ifnum\exo>1 \filbreak \fi{\bf
exercice
\chap.\exo : }\nobreak\par\vskip 2mm}

\def\mppar#1{\vskip 6mm
\incrementeCX \ifnum\exo>1 \filbreak \fi{\bf 
\chap.\exo. -- #1 :}\nobreak\par\vskip 2mm}


%***** Verbatim *****

\chardef\other=12%
\def\deactivate{%
			\catcode`\\=\other    \catcode`\{=\other
   \catcode`\}=\other    \catcode`\$=\other
   \catcode`\&=\other    \catcode`\#=\other
   \catcode`\%=\other    \catcode`\~=\other
   \catcode`\^=\other    \catcode`\_=\other
   \catcode`\:=\other
}

\def\makeactive#1{\catcode`#1=\active\ignorespaces}
{% The group delimits the text over wich ^^M is active.
    \makeactive\^^M%
    \gdef\obeywhitespace{%
    % Use \gdef so the definition survives the group.
        \makeactive\^^M %
        \let^^M=\newline %
        \aftergroup\removebox % Kill extra paragraph at end.
        \obeyspaces % sans lui on a un passage \`a la ligne
    }%
}

\def\newline{\par\indent}
\def\removebox{\setbox0=\lastbox}



{\catcode`�=\active
\gdef\verbatim{%
   \begingroup\tt\deactivate\obeywhitespace%
   \catcode`�=\active
   \def�{\endgroup} }}

%***** Dessins *****

\overfullrule =0pt
\def\picture #1 by #2 (#3){
 \vbox to #2{
    \hrule width #1 height 0pt depth 0pt
    \vfill
    \special{picture #3} % this is the low-level interface
    }
  }


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%\footline=
%{\vbox{\null\vskip 12mm\hrule\vskip
%6mm\line{\tenrm M.PAGES\hfil\tenrm
%\folio/6\hfil\tenrm
%Centrale 97 Informatique}}}



\centerline{\quinze CENTRALE-SUPELEC  97  }
\par\vskip 15mm
\centerline{\quinze INFORMATIQUE }
\par\vskip 20mm




\hrule\vskip 5mm
\centerline{\bf  PARTIE 1 - Recherche de motif}
\vskip 5mm
\hrule\vskip 8mm

\par
I.B.
\par
I.B.1) 
Consid\'erons l'indice $k$ initialis\'e \`a 0 et incr\'ement\'e de une unit\'e \`a chaque passage \`a
la ligne 10 (c'est \`a dire retour \`a la premi\`ere lettre du motif).\par
On a toujours: $k=j-i$: c'est vrai au d\'ebut, puisque: $k=i=j=0$, et si c'est vrai en
entr\'ee de boucle, alors  soit $j$ et $i$ sont incr\'ement\'es de 1 et $k$ ne change pas,
donc on a toujours $k=(j+1)-(i+1)$ soit $k$ devient $k'=k+1$, $j$ devient $j'=j-i+1$ et
$i$ devient $i'=0$, $k'=k+1=j-i+1=j'-i'$.\par
On peut consid\'erer que l'on recommence alors
la recherche sur le source priv\'e de ses
$k$ premiers caract\`eres (c'est une amorce de la m\'ethode recursive).\par
En sortie de boucle, les $k$ premiers \'el\'ements de source sont donc "rejet\'es", et si 
$i>0$, les \'el\'ements de source compris entre $k$ et $k+i-1=j-1$ co\"{\i}ncident avec les
\'el\'ements de motifs compris entre $0$ et $i-1$.
\bigskip

I.B.2) A chaque passage dans la boucle , soit $i$ augmente (6) (mais reste inf\'erieur \`a
la longueur $p$ du motif), soit $k$ augmente (mais reste inf\'erieur \`a $j$ donc \`a la
longueur
$n$ du source).  Donc, la boucle ne peut en aucun cas \^etre effectu\'e plus de $np$
fois, ce qui prouve la terminaison de l'algorithme (On verra plus loin une am\'elioration
de cette majoration).\par Lorsque l'on sort de la boucle, soit $i=p$ et les \'el\'ements
compris entre $k$ et
$k+p-1$ de source correspondent au motif: on a trouv\'e le motif dans source, soit $i<p$
et $j=n$, donc on a \'epuis\'e la source sans avoir trouv\'e le motif.
\bigskip

I.B.3) Fonction recherche$\_$iterative$\_$brute:
\verbatim

#let recherche_iter_brute motif source=
let p=vect_length motif and n=vect_length source and i=ref 0 and j=ref 0 in
while (!i<p) && (!j<n) do
     if motif.(!i)=source.(!j) then (i:= !i+1; j:= !j+1)
                               else (j:= !j- !i+1; i:=0)   done;
!i=p ;;

recherche_iter_brute : 'a vect -> 'a vect -> bool = <fun>

#let motif=[|1;2;1;2;3|] and source=[|1;2;2;1;2;1;2;3;1;2|] 
     in recherche_iter_brute motif source;;
- : bool = true

#let motif=[|1;2;1;2;3|] and source=[|1;2;2;1;2;1;1;3;1;2|]
     in recherche_iter_brute motif source;;
- : bool = false
�
\bigskip

I.B.4) Dans le pire des cas, imaginons que l'on regarde \`a chaque fois les $p$ \'el\'ements
du motifs, donc \`a partir des positions 0, 1, \dots,
$n-p$ dans source, on aura effectu\'e $p.(n-p+1)$
comparaisons. \par
C'est le cas, par exemple, si source = $aaa\dots aa$ et motif =$aaa\dots aab$.\par
La complexit\'e, dans le pire des cas, est $O(np)$.
\bigskip

I.C.
\par

I.C.1)
 Note: conform\'ement au texte du probl\`eme, la fonction est$\_$pr\'efixe est utilis\'ee dans
recherche$\_$recursive. Pour compiler en Caml, il est bien s\^ur n\'ecessaire de l'\'ecrire
avant.\par
Note: Je n'ai pas red\'efini les op\'erations ListeVide, Construit, Tete et Queue, j'ai
utilis\'e les fonctions Caml correspondantes.
\par
Fonction recherche$\_$recursive:

\verbatim

#let rec recherche_recursive motif source=
     if est_prefixe motif source then true 
     else if source=[] then false 
     else recherche_recursive motif (tl source);;

recherche_recursive : 'a list -> 'a list -> bool = <fun>
�
\bigskip

I.C.2) Fonction est$\_$prefixe:
\verbatim

#let rec est_prefixe motif source=
      if source=[] then false
      else if motif=[] then true
      else if hd motif<>hd source then false 
      else est_prefixe (tl motif) (tl source);;

est_prefixe : 'a list -> 'a list -> bool = <fun>

#let motif=[1;2;3] and source=[1;2;3;4;5] in est_prefixe motif source;;
- : bool = true

#let motif=[1;2;3] and source=[1;2;4;4;5] in est_prefixe motif source;;
- : bool = false
�

\bigskip

I.C.3) C'est le m\^eme r\'esultat qu'\`a la question 1.B.4 puisque l'algorithme r\'ecursif est
bas\'e sur le m\^eme principe que l'algorithme it\'eratif. Et le pire des cas \'etudi\'e ci-dessus
donne le m\^eme r\'esultat.
\bigskip



I.D.
\par\nobreak

I.D.1) Fonction recherche$\_$KMP:\par
 On utilise le tableau obtenu par la fonction de calcul du tableau auxilliaire.\par
On initialise la recherche \`a l'indice $k$ pour motif
 et $i$ pour source, \`a chaque \'etape:
{\parindent=10mm
\item{$\bullet$ }  si $0\leq k<p$ et $i<n$, on compare motif.($k$) et source.($i$):
\itemitem{-- } s'ils sont \'egaux, on incremente $i$ et $k$ et on recommence
\itemitem{-- } s'ils sont distincts, on ne change pas $i$, $k$ devient tableau.($k$)
\item{$\bullet$ }  si $k=-1$, on incremente $i$ et $k$ prend la valeur 0, c'est \`a dire
on incremente $i$ et $k$.
\item{$\bullet$ }  Si $k<p$ et $i=n$, on a \'epuis\'e la source sans trouver le motif
\item{$\bullet$ }  Si $k=p$, on atrouv\'e la source dans le motif.
\par}
On en d\'eduit la fonction Caml suivante:\par

\verbatim

#let recherche_KMP  motif source tableau=
let p=vect_length motif and n=vect_length source 
and  k= ref 0 and i=ref 0  in
while (!k<p) && (!i<n) do
   if !k<0 or motif.(!k)=source.(!i) then (i:=!i+1;k:=!k+1)
   else k:=tableau.(!k)
done;
!k<p ;;

recherche_KMP : 'a vect -> 'a vect -> int vect -> bool = <fun>

#let motif=[|1;2;1;2;3|] and source=[|1;2;1;2;1;2;3;1;2|] and tableau=[|-1;0;0;1;2|]
in recherche_KMP motif source tableau;; 
- : bool = true
�
\bigskip

I.D.2) 
Le tableau auxiliaire pour le motif "abaabababaabaab" est
$(-1,0,0,1,1,2,3,2,3,4,5,6,4)$.
\bigskip

I.D.3) Fonction calcule$\_$tab$\_$aux:\par
 On initialise un tableau auxilliaire de longueur $p$ \`a -1.
\par
Ensuite, pour $j$ variant de 1 \`a $p-1$, on recherche  si le sous\_mot de motif allant des
indices $j-k$ \`a $j-1$ forment un pr\'efixe de motif, et cela pour $k$ variant de 1 \`a $j-1$
(on veut un pr\'efixe strict.).\par
On utilise la fonction prefixe qui est la version vecteur de la fonction est\_prefixe
pr\'ec\'edente.
\verbatim

#let calcule_tab_aux motif= let p=vect_length motif in 
let t=make_vect (p) (-1) 
in  
for j=1 to p-1 do let l=ref 0 in 
   for k=1 to j-1 do if prefixe (sub_vect motif (j-k) k) motif then l:=k done;
t.(j) <- !l
done;
t;;

calcule_tab_aux : 'a vect -> int vect = <fun>

#let motif=[|1;2;1;1;2;1;2;1;1;2;1;1;2|] in calcule_tab_aux motif;;
- : int vect = [|-1; 0; 0; 1; 1; 2; 3; 2; 3; 4; 5; 6; 4|]
�


\hrule\vskip 5mm
\centerline{\bf  PARTIE 2 - Recherche dans un dictionnaire}
\vskip 5mm
\hrule\vskip 8mm

\par


2.A.
\verbatim

#type info = {cle : int vect ; valeur : int}
and noeudinterne = Nil | Feuille of info | Noeud of (noeudinterne vect)
and karbre = noeudinterne ;;

Le type info est d\'efini.
Le type noeudinterne est d\'efini.
Le type karbre est d\'efini.
�

\par

2.A.1)
Pour rechercher une cl\'e, il faut parcourir $l$ n\oe uds (o\`u $l$ repr\'esente la longueur
commune des cl\'es) et arriver \`a la feuille. Soit au total $l+1$, c'est \`a dire 1 plus la
hauteur de l'arbre.
\bigskip

2.A.2)
S'il y a $n$ mots de longueur $l$ sur un alphabet \`a $k$ symboles, la hauteur de
l'arbre est \'egale \`a $l$, chaque n\oe ud interne est un tableau de longueur $k$. Il y en
a au plus 1 \`a la racine, $k$ au niveau 1, $k^2$ au niveau 2 etc...\par
Si $n=k^{l}$ (nombre maximum de cl\'es de longueur $l$ sur cet alphabet), il y aura
$\ds{k^{l+1}-1\over k-1}$ tableaux  de longueur $k$ (les n\oe uds internes) et $n=k^l$
mots de longueur
$l$ (les feuilles).\par
Si $n\leq k$, au pire les premiers \'el\'ements sont 2 \`a 2 distincts,, il y aura $1+nl$
n\oe uds  et toujours $n$ feuilles.\par
Si $k^p\leq n<k^{p+1}$, puisque \`a chaque niveau $m$, le nombre de n\oe uds est major\'e
par $max(k^m,n)$, au pire on remplit les
$p+1$ premiers niveaux, soit
$1+k+\dots +k^p$ et il reste ensuite $(l-p-1)$ "niveaux" \`a $n$ n\oe uds. Soit
$\ds{k^{p+1}-1\over k-1}+(l-p-1)n$ n\oe uds, et encore $n$ feuilles.
\bigskip

\vfill\eject


2.B. 
\par

2.B.1) Type arbre comprim\'e:
\verbatim

#type nouveaunoeud = Nil | Feuille of int*info | Noeud of ((int*nouveaunoeud) vect)
and karbre_comprime=nouveaunoeud;;

Le type nouveaunoeud est d\'efini.
Le type karbre_comprime est d\'efini.
�

Recherche dans un arbre comprim\'e:
\verbatim

let recherche  = 
let rec recherche_niveau niveau  cle = function
  | Nil -> false
  | Feuille (x,m) -> m.cle=cle
  | Noeud v -> let(decalage, branche)=v.(cle.(niveau)) in
               recherche_niveau (niveau + decalage) cle branche
in recherche_niveau 0 ;;
�
\bigskip

2.B.2) 

\hskip 2mm \picture 8cm by 8cm (fig2b21 scaled 850)\par
\vskip 6mm

\hskip 2mm \picture 8cm by 8cm (fig5 scaled 850)\par
\vskip 6mm

\bigskip

2.B.3) Le nombre de tableaux est alors inf\'erieur \`a $n-1$.\par
En effet, tous les noeuds internes ont au moins deux fils. Montrons que dans un tel
arbre, le nombre de noeuds internes est inf\'erieur (strictement) au nombre de
feuilles.\par Un arbre reduit \`a une feuille ne poss\`ede aucun noeud interne.\par
Soit $A$ un arbre ayant $n$ feuilles ($n>1$)et $p$ noeuds internes, la racine a donc au
moins deux fils. Soient $A_1$, $A_2$,  \dots, $A_k$ ($k\geq 2$) les branches issues de
la racines, $n_i$ et $p_i$ le nombre de feuilles et le nombre de noeuds internes de la
branche $A_i$. Par induction structurelle, pour tout $i$, $p_i\leq n_i-1$.
$$p=\sum_{i=1}^k p_i+1\qquad n=\sum_{i=1}^k n_i\qquad p\leq
\sum_{i=1}^k(n_i-1)+1=n-k+1\leq n-1$$ 
\bigskip
La complexit\'e en temps est au pire encore la m\^eme: si tous les n\oe uds internes ont
deux fils , il faudra parcourir les
$l$ n\oe uds pour  diff\'erencier les feuilles ( On peut imaginer un dictionnaires dans
lequel les mots v\'erifient cette propri\'et\'e ).\par 
Mais, l'arbre n'est en g\'en\'eral pas "plein", le
gain en moyenne peut \^etre consid\'erable, par exemple dans l'arbre comprim\'e ci-dessus, le
nombre moyen de n\oe uds parcourus est $\ds{1\over 10}(2+3+3+2+1+2+2+2+2+2)=2,1$ au lieu
de 4.
\par


\bigskip
2.C.
\par

2.C.1) A chaque dictionnaire correspond un $k$-arbre. Le nombre de dictionnaires est
$C_{k^l}^n$.\par 
Pour que la profondeur soit strictement sup\'erieure \`a $d$, il faut et il suffit qu'il
existe deux mots du dictionnaire ayant les m\^emes $d-1$ premiers symboles.\par
Si $n>k^{d-1}$ c'est toujours vrai donc $N_d= C_{k^l}^n$, sinon le nombre de
dictionnaires pour lesquels tous les mots ont des pr\'efixes de longueur $d-1$ distincts
est $C_{k^{d-1}}^n k^{n(l-d+1)}$, donc les dictionnaires dont le $k$-arbre comprim\'e
est de profondeur strictement sup\'erieure \`a $d$ est 
$$N_d=C_{k^l}^n-C_{k^{d-1}}^nk^{n(l-d+1)}
=C_{k^l}^n-{k^{nl}\over k^{n(d-1)}}\ {\ds \prod_{i=0}^{n-1}\left(k^{d-1}-i\right)\over
n!} =C_{k^l}^n-{k^{nl}\over n!}\prod_{i=0}^{n-1}\left(1-{i\over
k^{d-1}}\right)$$ Or $\ds {k^{nl}\over n!}\geq C_{k^l}^n$ donc:
$$N_d\leq C_{k^l}^n\left[1-\prod_{i=0}^{n-1}\left(1-{i\over
k^{d-1}}\right)\right]$$
Cette derni\`ere in\'egalit\'e \'etant vrai \'egalement si $n>k^{d-1}$ car l'un des termes du
produit est alors nul et le deuxi\`eme membre vaut $ C_{k^l}^n=N_d$
\bigskip

2.C.2) $$\overline{d_n}=\sum_{d\geq 1}d(q_{d-1}-q_d)=\sum_{d\geq 0}q_d $$

$$q_d={N_d\over C_n^{k^l}}\leq 1-\prod_{i=0}^n\left(1-{i\over k^{d-1}}\right)\leq
1-e^{-n^2\over k^{d-1}}$$
Ce dernier terme est $\leq 1$ et aussi $\leq \ds{n^2\over k^{d-1}}$ (car, pour tout $x$,
$e^x\geq 1+x$). Donc:
$$q_d\leq min\left(1,{n^2\over k^{d-1}}\right)$$
On en d\'eduit donc:
$$\overline{d_n}\leq\sum_{d\geq 0}q_d \leq \sum_{d\geq 0}min\left(1,{n^2\over
k^{d-1}}\right)$$ 
Soit $\alpha=\log_kn$, si $d\geq 2\alpha+1$ (c'est \`a dire $d\geq \lceil 2\alpha\rceil
+1$),
$\ds min\left(1,{n^2\over k^{d-1}}\right)={n^2\over k^{d-1}}$, sinon, $\ds
min\left(1,{n^2\over k^{d-1}}\right)=1$, soit
$$\overline{d_n}\leq\lceil 2\alpha\rceil +\sum_{d\geq \lceil 2\alpha\rceil+1}{n^2\over
k^{d-1}}$$
$$\sum_{d\geq \lceil 2\alpha\rceil+1}{n^2\over k^{d-1}}={n^2\over k^{\lceil
2\alpha\rceil}}{k\over k-1}\leq {k\over k-1}=O(1)$$
Donc,
$$\overline{d_n}\leq2\lceil \log_kn\rceil+O(1)$$
car $\lceil 2\alpha\rceil\leq2\lceil\alpha\rceil$.
\bigskip


\bye