Département de Formation Premier Cycle Année 2001 – 2002 Session de Janvier 2002 GU : TCA UE : TCA101 Epreuve d’informatique Date : 2002-01-14 Durée : 1,5h Tous documents autorisés. Votre voisin n’est pas un document Epreuve de M Strandh et M Musumbu

Exercice 1. (5p)

On suppose les nombres entiers représentés sur un octet avec leur signe. Soit x = 01011010 et y = 10100101

Question 1 Quels sont les nombres représentés par x et y en décimal?

Réponse (0.5 point) x = (90)_{10} et y = (165)_{10} en décimal non signé. En signé y = (−91)_{10}

Question 2 Donner la conversion de x et y en hexadécimal.

Réponse (0.5 point) x = (5A)_{16} et y = (−5B)_{16}

Question 3 Que vaut x + y en décimal?

Réponse (0.5 point) x + y = (−1)_{10}

Question 4 Soit n le nombre déduit de m en échangeant les 0 et les 1 dans leurs représentations binaires, comme dans l’exemple précédent avec x et y. Quelle est la relation qui lie m et n? Faire la preuve.

Réponse (0.5 point) m et n sont complémentaire l’un de l’autre.

Question 4 La gestion de l’horloge interne des ordinateurs est assez simple. Elle consiste à incrementer un compteur à chaque seconde depuis le 1 janvier 1970. La valeur du compteur est un entier signé, codé sur 32 bits. Quelle année cette méthode risque de ne plus fonctionner?

Réponse (2 point) Comme le compteur utilise 32 bits et que les entieres représentés sont signés, ceci implique que le bit de poid fort est reservé au signe. Il nous reste donc 31 bits de libres ce qui donne un total de 2^{31} = 2147483648. Or, il y a en moyenne environ 365,25 jours dans l’année et un jour fait 24×3600s On obtient donc 68 années et des pouusières. Un debordement aura lieu au cours de l’année 2038. Exercice 2. (5p)

Soit la procédure MAPLE suivante :

mystere := proc(A, B::integer)
local x, y, r;
    x := A;
    y := B;
    r := x - y;
    while r <> 0 do
        y := x;
        x := r;
        r := abs(x - y);
    od;
    x;
end

Rappel : la fonction abs retourne la valeur absolue d’un nombre.

Question 1 Simuler l’exécution de mystere(27,15); et mystere(31,14); à l’aide d’un tableau clair des valeurs successives des variables x,y et r.

Réponse (2 point) mystere(27,15);

\begin{matrix}x & y & r \\ 27 & 15 & 12 \\ 12 & 27 & 15 \\ 15 & 12 & 3 \\ 3 & 15 & 12 \\ 12 & 3 & 9 \\ 9 & 12 & 3 \\ 3 & 9 & 6 \\ 6 & 3 & 3 \\ 3 & 3 & 3 \\ 3 & 3 & 0 \end{matrix}

résultat= 3

Réponse (1 point) mystere(31,14);

\begin{matrix}x & y & r \\ 31 & 14 & 17 \\ 17 & 31 & 14 \\ 14 & 17 & 3 \\ 3 & 14 & 11 \\ 12 & 3 & 9 \\ 11 & 3 & 8 \\ 8 & 11 & 3 \\ 3 & 8 & 5 \\ 5 & 3 & 2 \\ 2 & 5 & 3 \\ 3 & 2 & 1 \\ 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 0 \end{matrix}

résultat= 1

Question 2

Que calcule cette procédure?

Réponse (1 point) Elle calcule le P GCD de deux entiers relatifs

Question 3

Comment peut-on améliorer cette procédure ? Répondez de façon succinte, soit par un programme Maple, soit par une ou deux lignes de commentaires.

Réponse (1 point)

mystere := proc (A, B::integer)
local x, y, r;
if A < B then x := A; y := B
         else x := B; y := A
fi;
r := irem(y,x);
while r <> 0 do
      y := x;
      x := r;
      r := irem(y,x)

od;
x;
end

Avec cette modification on obtient la trace suivante mystere(31,14);

\begin{matrix}x & y & r \\ 31 & 14 & 3 \\ 14 & 3 & 2 \\ 3 & 3 & 0 \end{matrix}

résultat= 1. Cette version est beaucoup plus rapide.

Exercice 3. (5p)

Voici trois procédures Maple, numérotées pr1, pr2 et pr3:

pr1 := proc(n)
local p, i;
i := n;
p := 0;
while i <> 0 do
  if i mod 2 = 1 then
    p := p + 1;
  fi;
  i := iquo(i, 2);
od;
p;
end;
pr2 := proc(l)
local i, j, temp, ll;
ll := l;
for i from 2 to nops(ll) do
  for j from nops(ll) to i by -1 do
    if ll[j-1] > ll[j] then
      temp := ll[j-1];
      ll[j - 1] := ll[j];
      ll[j] := temp;
    fi;
  od;
od;
ll;
end;
pr3 := proc(n)
local f, i;
f := 1;
for i from 1 to n do
  f := f * i;
od;
f;
end;

Les courbes suivantes donnent le temps d’exécution des trois procédures en fonction de la valeur du paramètre n (pr1 et pr3) ou du nombre d’éléments de la liste l (pr2).

Étant donné que l’échelle des courbes est linéaire, faire correspondre chaque procédure à une courbe.

Réponse pr1 et courbe A, pr2 et courbe C, pr3 et courbe B. Une réponse avec une seule correspondance correcte aura la note 2p. Exercice 4. (5p) Indiquer le degré d’acceptabilité pour chacun des courriers électroniques suivants (0 = inacceptable, 1 = moyen, 2 = OK)

• Un fichier Word à un ami ayant Word sur sa machine

• Un fichier Excel à la secretaire du 1^{∘} cycle

• Un fichier PDF à la secretaire du 1^{∘} cycle

• Un fichier PDF à un enseignant

• Un texte ISO-latin-1 à un utilisateur de Windows.

Word = traitement de texte de Microsoft Excel = tableur de Microsoft PDF = format ouvert de Adobe

Réponse

• Un fichier Word à un ami ayant Word sur sa machine (2 = OK)

• Un fichier Excel à la secretaire du 1^{∘} cycle (0 = inacceptable)

• Un fichier PDF à la secretaire du 1^{∘} cycle (1 = moyet)

• Un fichier PDF à un enseignant (1 = moyet)

• Un texte ISO-latin-1 à un utilisateur de Windows. (2 = OK)

Chaque réponse sera notée 1p (bien), 1/2p (moyen) ou 0p (mauvais). La somme totale sera arrondie à l’entier supérieur.