\parindent=0mm
\input psfig.sty
\setbox1=\hbox{\psfig{file=I97CM1Fa.eps,width=\hsize}}
\setbox2=\hbox{\psfig{file=I97CM1Fb.eps,width=\hsize}}
%***** Les fontes et les caract{\`e}res particuliers *****
\font\caml=cmtex10
\font\twelvern = cmbxsl10 at 12 pt
\font\itaten = cmti10
\font\quinze = cmbxsl10 at 15 pt
\font\tit=eufm10 at 25pt
\font\stit=eufm10 at 12pt
\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\PP{\hbox{\mp P}}
\def\RR{\hbox{\mp R}}
\def\EE{\hbox{\mp E}}
\def\BB{\hbox{\mp B}}
\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}}
\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{\'e}viations et compteur *****
\def\tvi{\vrule height 12pt depth 5pt
width 0pt}
\let\vect=\overrightarrow
\let\ds=\displaystyle
\let\ep=\varepsilon
\let\ssi=\Longleftrightarrow
\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\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\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
}
}
Martine PAGES \ \ \ Lyc{\'e}e Mass{\'e}na - Nice\par
tel.: 04 93 84 79 91\par
pages@pelat.ac-nice.fr
\par\vskip 15mm
\footline=
{\vbox{\null\vskip 12mm\hrule\vskip
6mm\line{\tenrm M.PAGES\hfil\tenrm
\folio\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{\'e}rons l'indice $k$ initialis{\'e} {\`a} 0 et incr{\'e}ment{\'e} de une unit{\'e} {\`a} chaque passage {\`a}
la ligne 10 (c'est {\`a} dire retour {\`a} la premi{\`e}re lettre du motif).\par
On peut consid{\'e}rer que l'on recommence alors la recherche sur le source priv{\'e} de ses
$k$ premiers caract{\`e}res (c'est une amorce de la m{\'e}thode recursive).\par
En sortie de boucle, les $k$ premiers {\'e}l{\'e}ments de source sont donc "rejet{\'e}s", et si
$i>0$,les {\'e}l{\'e}ments de source compris entre $k$ et $k+i-1=j-1$ co{\"\i}ncident avec les
{\'e}l{\'e}ments de motifs compris entre $0$ et $i-1$.
\bigskip
I.B.2) A chaque passage dans la boucle, soit $i$ augmente (mais reste inf{\'e}rieur {\`a} la
longueur $p$ du motif), soit $k$ augmente (mais reste inf{\'e}rieur {\`a} $j$ donc {\`a} la
longueur
$n$ du source). Donc, la boucle ne peut en aucun cas {\^e}tre effectu{\'e} plus de $np$ fois.
(On verra plus loin une am{\'e}lioration de cette majoration).\par
Lorsque l'on sort de la boucle, soit $i=p$ et les {\'e}l{\'e}ments compris entre $k$ et
$k+p-1$ de source correspondent au motif: on a trouv{\'e} le motif dans source, soit $i
'a vect -> bool =
#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$ {\'e}l{\'e}ments
du motifs, donc {\`a} partir des positions 0, 1, \dots,
$n-p$ dans source, on aura effectu{\'e} $p.(n-p+1)$
comparaisons. \par
Si source = $aaa\dots aac$ et motif =$aaa\dots aab$, on effectuera les $p(n-p)$
comparaisons precedentes, et on continuera en comparant le premier $a$ du motif
successivement aux {\'e}l{\'e}ments de source situ{\'e}s aux positions $n-p+k$ pour $k\in[1, p-1]$
soit encore $p-k$ comparaisons {\`a} chaque fois, soit au total:
$\ds p(n-p+1)+{p(p-1)\over2}={p\over 2}(2n-p+1) $ comparaisons.
\bigskip
I.C.
\par
I.C.1)
Note: conform{\'e}ment au texte du probl{\`e}me, la fonction est$\_$pr{\'e}fixe est utilis{\'e}e dans
recherche$\_$recursive. Pour compiler en Caml, il est bien s{\^u}r n{\'e}cessaire de l'{\'e}crire
avant.
\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 =
£
\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 =
#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{\^e}me r{\'e}sultat qu'{\`a} la question 1.B.4 puisque l'algorithme r{\'e}cursif est
bas{\'e} sur le m{\^e}me principe que l'algorithme it{\'e}ratif. Et le pire des cas {\'e}tudi{\'e} ci-dessus
donne le m{\^e}me r{\'e}sultat.
\bigskip
I.D.
\par\nobreak
I.D.1) Fonction recherche$\_$KMP:
\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 'a vect -> int vect -> bool =
#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;0|]
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,5)$.
\bigskip
I.D.3) Fonction calcule$\_$tab$\_$aux:
\verbatim
#let calcule_tab_aux motif= let p=vect_length motif in
let t=make_vect (p+1) (-1)
in
for j=0 to p-1 do let l=ref 0 in
for k=1 to j-1 do if prefixe motif (sub_vect motif (j-k+1) k) then l:=k done;
t.(j+1) <- !l
done;
t;;
calcule_tab_aux : 'a vect -> int vect =
#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; 5|]
£
\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{\'e}fini.
Le type noeudinterne est d{\'e}fini.
Le type karbre est d{\'e}fini.
£
\par
2.A.1)
Pour rechercher une cl{\'e}, il faut parcourir $l$ noeuds (o{\`u} $l$ repr{\'e}sente la longueur
commune des cl{\'e}s) et arriver {\`a} la feuille. Soit au total $l+1$, c'est {\`a} dire 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 {\'e}gale {\`a} $l$, chaque noeud 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{\'e}s de longueur $l$ sur cet alphabet), il y aura
$\ds{k^{l+1}-1\over k-1}$ tableaux de longueur $k$ (les noeuds internes) et $n=k^l$ mots
de longueur
$l$ (les feuilles).\par
\bigskip
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{\'e}fini.
Le type karbre_comprime est d{\'e}fini.
£
Recherche dans un arbre comprim{\'e}:
\verbatim
let rec recherche mot dictionnaire =
match dictionnaire with
| Nil -> false
| Feuille (x,m) when m.cle=mot -> true
| Noeud (x,t) -> recherche (sub_vect mot 1 (vect_length mot -1)) t.(mot.(0));;
£
\bigskip
2.B.2)
%\hskip 2mm \picture 8cm by 8cm (fig2b21 scaled 850)\par
\box1\vskip 6mm
%\hskip 2mm \picture 8cm by 8cm (fig2b22 scaled 850)\par
\box2\vskip 6mm
\bigskip
2.B.3) Le nombre de tableaux est alors inf{\'e}rieur {\`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{\'e}rieur (strictement) au nombre de
feuilles.\par Un arbre reduit {\`a} une feuille ne poss{\`e}de 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
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{\'e}rieure {\`a} $d$, il faut et il suffit qu'il
existe deux mots du dictionnaire ayant les m{\^e}mes $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{\'e}fixes 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{\'e}rieure {\`a} $d$ est $$N_d=C_{k^l}^n-C_{k^{d-1}}^n
k^{n(l-d+1)}=C_{k^l}^n-{k^l\over n!}\prod_{i=0}^{n-1}\left(1-{i\over
k^{d-1}}\right)$$
Or $\ds {k^l\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{\`e}re in{\'e}galit{\'e} {\'e}tant vrai {\'e}galement si $n>k^{d-1}$ car l'un des termes du
produit est alors nul et le deuxi{\`e}me 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}}=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{\'e}duit 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