G. Hunault Angers, sept. 97

Licence M.A.S.S.

Examen de Langages et Styles de Programmation

1. Algorithmes

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.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.

1.2) Donner un algorithme de calcul de d_{2}(U, 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.

1.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.

1.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.

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

2. Langage

Le langage PGHL qui a été inventé en juin 97 est un langage basé sur la réécriture. Nous fournissons sur la page suivante trois exemples de programmes dans ce langage.

# Exemple 1 #############################################
#
# bonjour.pghl :
#  pose une question, demande un nom et dit au revoir
#  avec traduction en majuscules du nom
#
axiom
 BJR
rules
  BJR -> Intro Question Bye
  Intro -> out 'Bonjour, quel est votre nom ?'
  Question -> in $pren
  Bye -> out 'au revoir à ' $date() ' ' $upper($pren)
#               **************************************
#               * Exécution                          *
#               *      Bonjour, quel est votre nom ? *
#               *      gm                            *
#               *      au revoir à 27/09/97 GM       *
#               **************************************

# Exemple 2 ############################################
#
# fact.pghl :
#   produit en n réécritures l'expression A(n!,n+1)
#
axiom
  A(1,1)
rules
  A(x,y) -> A(x*y,y+1)
options
  runlength 3
  trace
  fwrite    fact.sor

#       **************************************************
#       * Exécution (résultats dans le fichier fact.sor) *
#       *      1 : A(1,2)                                *
#       *      2 : A(2,3)                                *
#       *      3 : A(6,4)                                *
#       **************************************************

# Exemple 3 ############################################
#
# table de multiplication
#
axiom
  T(1,5)
rules
  T(a,x) -> {
     out $format($a,2) ' fois ' $x ' = ' $format($a*$x,5)
     nl
     T(a+1,x)
  }
options
   parameters {
     ' de quel nombre voulez-vous la table ? ' 3  1000
     ' montant ''
   }
  runlength  10
#                  ********************************
#                  * Exécution                    *
#                  *   (comme d'hab !)            *
#                  ********************************

Après avoir lu attentivement ces programmes, en essayant de repérer la syntaxe, le fonctionnement et la logique interne de l’écriture des programmes, répondez aux deux questions suivantes.

2.1) Décrivez ce langage.

2.2) Essayez de donner un programme en pghl qui demande un nombre n, qui calcule la somme des n premiers cubes et qui affiche le résultat.

3. Culture informatique

La mode est aujourd’hui aux outils graphiques de développement, aux ateliers de génie logiciel, aux éditeurs de dialogues et autres constructeurs automatiques de menus, d’interfaces. Quels sont les avantages et les inconvénients de tels outils pour un développeur d’applications ? On distinguera les applications locales (c’est à dire intra-entreprises) des applications commerciales (qui sont donc vendues, diffusées en grand public).