%
% euri9709.tex
%
\documentclass[12pt,a4paper]{article}
%
\renewcommand{\thesection}{\arabic{section}. }
\renewcommand{\thesubsection}{\arabic{section}.\arabic{subsection}}
\def\bidng{\ensuremath{[\hspace{-0.45em}[}}
\def\bidnd{\ensuremath{]\hspace{-0.45em}]}}
\def\N{\mbox{I\hspace{-0.11em}N}}
\def\R{\mbox{l\hspace{-0.11em}R}}
\parindent      0.0cm
\parskip        0.5cm
%
%
\begin{document}
%{\Large \textbf{G. Hunault} \hspace{6cm}}
%\textit{Angers, sept. 97}
%
%{\Large Licence Informatique}\\[1.2cm]
%
\setcounter{page}{3}
\begin{center}
{\LARGE PARTIE \hspace{0.2cm} B\hspace{0.3cm}  --- \hspace{0.3cm} Informatique }
\end{center}
\vskip 2.3cm
%
Soit $U$ et $V$ deux vecteurs de $\R^n$ dont les composantes
sont not\'{e}es $U_i$ et $V_i$ pour $i$ de $1$ \`{a} $n$, impl\'{e}ment\'{e}s
sous forme de tableaux dont les \'{e}l\'{e}ments sont not\'{e}s
$U[i]$ et $V[i]$. On appelle distance euclidienne entre
$U$ et$V$ la quantit\'{e}
$$d_1(\ U,V\ )= \sqrt{\ \sum_{i=1}^n (U_i-V_i)^2\ }$$
\begin{itemize}
\item[\textbf{1)}]{
Donner un algorithme de calcul de $d_1(U,V)$ sachant $U$ et $V$.

On donnera le d\'{e}tail de la fonction ainsi d\'{e}crite, avec son en-t\^{e}te,
la d\'{e}claration des param\`{e}tres,
des variables locales et globales.
}
\end{itemize}

On suppose maintenant que $T$ est un tableau dont les lignes sont des vecteurs
de $\R^n$ et que
les $n_A$ premi\`{e}res lignes de $T$ d\'{e}terminent un ensemble ${\mathcal{A}}$
de vecteurs et que les $n_B$ lignes suivantes de $T$ d\'{e}terminent un ensemble
${\mathcal{B}}$
de vecteurs. On note $T[i,j]$ la $j$-i\`{e}me composante de la
$i$-i\`{e}me ligne.
On pose alors
$d_2(\ W,{\mathcal{C}}\ )=min\ \{\ d_1(W,Z)\ \}$
o\`{u} $W$ est un vecteur de $\R^n$,
$Z$ parcourt ${\mathcal{C}}$
et ${\mathcal{C}}$ est soit ${\mathcal{A}}$ soit ${\mathcal{B}}$.

\begin{itemize}
\item[\textbf{2)}]{
Donner un algorithme de calcul de $d_2(W,{\mathcal{A}})$ sachant $U$, $T$ et $n_A$.

On fournira une proc\'{e}dure avec son en-t\^{e}te $etc.$
}
\end{itemize}

On pose finalement
$d_3(\ {\mathcal{A}},{\mathcal{B}}\ )=%
max(\ max\{d_2(Y,A)\}\ ,\ max\{d_2(X,B)\}\ )$
o\`{u} $X$ parcourt ${\mathcal{A}}$
et $Y$ parcourt ${\mathcal{B}}$.

\begin{itemize}
\item[\textbf{3)}]{
Donner un algorithme de calcul de $d_3(A,B)$ sachant $T$, $n_A$ et $n_B$.

On fournira une proc\'{e}dure avec son en-t\^{e}te $etc.$
}
\end{itemize}
\newpage
La premi\`{e}re g\'{e}n\'{e}ralisation consiste \`{a} consid\'{e}rer non plus 2 ensembles
$A$ et $B$ mais $p$ ensembles not\'{e}s $A_j$ pour $j$ de $1$ \`{a} $p$ rang\'{e}s
successivement dans $T$ avec chacun $n_j$ lignes.

\begin{itemize}
\item[\textbf{4)}]{
Indiquez comment on
peut alors calculer $d_3(A_{j_1},A_{j_2})$.
On ne fournira que les algorithmes jug\'{e}s importants.
}
\end{itemize}

La seconde g\'{e}n\'{e}ralisation consiste \`{a} supposer que $T$ ne contient pas
$n$ colonnes mais $n+1$ colonnes, la premi\`{e}re indiquant \`{a} quel ensemble
appartient le vecteur d\'{e}fini par les $n$ colonnes suivantes de la m\^{e}me ligne.
On admet alors que $A_j$ est d\'{e}fini par les lignes dont la premi\`{e}re colonne
vaut $j$, les lignes de $A_j$ n'\'{e}tant pas forc\'{e}ment cons\'{e}cutives.

\begin{itemize}
\item[\textbf{5)}]{
Indiquez comment on
pourrait calculer $d_3(A_{j_1},A_{j_2})$.
On ne fournira que les algorithmes jug\'{e}s importants.
}
\end{itemize}
\end{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

 Question 1


    fonction dist1
     param\`{e}tres u,v (vecteurs)
     globale    n   (dimension de l'espace)
     locales    i   (indice de boucle)
                s   (somme des termes)
    d\'{e}but de dist1
      s <-- 0
      pour i de1a n
           s <-- s + (u[i]-v[i])*(u[i]-v[i])
      finpour
      s <-- racine( s )
      renvoyer s
    fin de dist1

 Question 2

    en fait, d2(u,a) est donne par dist2a(u)

    fonction dist2a
     param\`{e}tres u     (vecteur)
     globale    n     (dimension de l'espace)
                na    (nb. de vecteurs de a)
                dist1 (fonction pr\'{e}c\'{e}dente)
     locales    i,j   (indices de boucle)
                m     (distance min)
                d     (distance courante)
                x     (vecteur courant dans a)
    d\'{e}but de dist2a
      pour j de1a n
        x[j] <-- t[1,j]
      finpour
      m <-- dist1(u,x)
      pour i de1a na-1
         pour j de1a n
           x[j] <-- t[i,j]
         finpour
         d <-- dist1(u,x)
         si d < m alors
            m <-- d
         finsi
      finpour
      renvoyer m
    fin de dist2a


 Question 3

    en admettant qu'on a aussi ecrit une fonction dist2b
    qui utilise t[j,...] pour j de na+1 a na+1+nb.

    fonction dist3ab
     param\`{e}tres (aucun)
     globale    n   (dimension de l'espace)
     locales    i   (indice de boucle)
                ma  (maximum dans A)
                mb  (maximum dans A)
                m   (maxium  global)
    d\'{e}but de dist3

      pour j de1a n
        x[j] <-- t[1,j]
      finpour
      ma <-- dist2a(x)
      pour i de1a na-1
         pour j de1a n
           x[j] <-- t[i,j]
         finpour
         d <-- dist2a(x)
         si d < ma alors
            ma <-- d
         finsi
      finpour

      pour j de1a n
        x[j] <-- t[na+1,j]
      finpour
      mb <-- dist2a(x)
      pour i de1a nb-1
         pour j de1a n
           x[j] <-- t[i,j]
         finpour
         d <-- dist2b(x)
         si d < mb alors
            mb <-- d
         finsi
      finpour

      m <-- ma
      si mb < ma alors
         m <-- mb
      finsi
      renvoyer m

    fin de dist3

 Question 4

  il faudrait inventer une fonction dist2(x,j) qui donne la
  distance de x a A_j. ensuite dist3(j1,j2) est le meme
  algorithle que au-dessus avec dist2a(x) remplace par
  dist2(x,j1) et avec dist2b(x) remplace pardist2(x,j2)

  exemple de dist2(x,j) :

    fonction dist2
     param\`{e}tres x  (vecteur)
                    j  (numero de l'ensemble)
     globale    n      (dimension de l'espace)
                na     (nb. de vecteurs de a)
                dist1  (fonction pr\'{e}c\'{e}dente)
     locales    i,k    (indices de boucle)
                m      (distance min)
                d      (distance courante)
                y      (vecteur courant dans a)
    d\'{e}but de dist2
      i <- 1
      pour k de1a j
           i <-- i + n[j]
      finpour
      pour k de1a n
        y[k] <-- t[i,k]
      finpour
      m <-- dist1(x,v)
      pour i de1a na-1
         pour k de1a n
           y[k] <-- t[i,k]
         finpour
         d <-- dist1(x,y)
         si d < m alors
            m <-- d
         finsi
      finpour
      renvoyer m
    fin de dist2


 Question 5

 admettons que T ait p lignes.
 il faut encore modifier dist2(x,j) par

    fonction dist2
     param\`{e}tres x  (vecteur)
                    j  (numero de l'ensemble)
     globale    n      (dimension de l'espace)
                na     (nb. de vecteurs de a)
                dist1  (fonction pr\'{e}c\'{e}dente)
     locales    i,k    (indices de boucle)
                m      (distance min)
                d      (distance courante)
                y      (vecteur courant dans a)
    d\'{e}but de dist2
      m <- maxint
      pour k de1a p
           si t[i,1]=j alors
              pour k de1a n
                y[k] <-- t[i,k+1]
              finpour
              d <- dist1(x,y)
              si d < m alors
                 m <-- d
              finsi
           finsi
      finpour
      renvoyer m
    fin de dist2
