PARTIE B — Informatique

Soit U et V deux vecteurs de lR^{n} dont les composantes sont notées U_{i} et V_{i} pour i de 1 à n, implémentés sous forme de tableaux dont les éléments sont notés U[i] et V [i]. On appelle distance euclidienne entre U etV la quantité

d_{1}( U, V ) = \sqrt{∑_{i=1}^{n}(U_{i} − V_{i})^{2}}

1) Donner un algorithme de calcul de d_{1}(U, V) sachant U et V.

On donnera le détail de la fonction ainsi décrite, avec son en-tête, la déclaration des paramètres, des variables locales et globales.

On suppose maintenant que T est un tableau dont les lignes sont des vecteurs de lR^{n} et que les n_{A} premières lignes de T déterminent un ensemble A de vecteurs et que les n_{B} lignes suivantes de T déterminent un ensemble B de vecteurs. On note T [i, j] la j-ième composante de la i-ième ligne. On pose alors d_{2}( W, C ) = min { d_{1}(W, Z) } où W est un vecteur de lR^{n}, Z parcourt C et C est soit A soit B.

2) Donner un algorithme de calcul de d_{2}(W, A) sachant U, T et n_{A}.

On fournira une procédure avec son en-tête etc.

On pose finalement d_{3}( A, B ) = max( max{d_{2}(Y, A)} , max{d_{2}(X, B)} ) où X parcourt A et Y parcourt B.

3) Donner un algorithme de calcul de d_{3}(A, B) sachant T, n_{A} et n_{B}.

On fournira une procédure avec son en-tête etc.

La première généralisation consiste à considérer non plus 2 ensembles A et B mais p ensembles notés A_{j} pour j de 1 à p rangés successivement dans T avec chacun n_{j} lignes.

4) Indiquez comment on peut alors calculer d_{3}(A_{j_{1}}, A_{j_{2}}). On ne fournira que les algorithmes jugés importants.

La seconde généralisation consiste à supposer que T ne contient pas n colonnes mais n + 1 colonnes, la première indiquant à quel ensemble appartient le vecteur défini par les n colonnes suivantes de la même ligne. On admet alors que A_{j} est défini par les lignes dont la première colonne vaut j, les lignes de A_{j} n’étant pas forcément consécutives.

5) Indiquez comment on pourrait calculer d_{3}(A_{j_{1}}, A_{j_{2}}). On ne fournira que les algorithmes jugés importants.