Corrigé de l'épreuve d'informatique TCA 101
Janvier 2000

Exercice 1 (5 points)

  1. On peut représenter 642 = 212 = 4K entiers avec deux caractères dans ce système de numération. Le plus grand d'entre eux, m, est codé // en base 64, et FFF en base 16 (douze chiffres binaires égaux à 1).
  2. Un bloc de trois octets contient 24 chiffres binaires, soit 4 chiffres en base 64 (un chiffre en base 64 correspond à une suite de 6 chiffres binaires, car 64 = 26).
  3. Chaque chiffre (caractère) en base 64 est transmis sur un octet (code ASCII) dans un courrier électronique. D'après la question précédente, trois octets sont codés par quatre caractères, soit quatre octets : si le document original a pour taille 6Ko, le message envoyé a donc pour taille 6*4/3 = 8Ko.

    Ce codage permet d'envoyer n'importe quel document sous forme d'un texte ne contenant que des caractères standard (voir la RFC 1521 pour les détails). Le prix à payer est une augmentation de la taille du document, mais celle-ci est raisonnable (1/3).

Exercice 2 (5 points)

  1. Valeurs successives des variables i et y :
    i   2 3 4 5 6 7
    y 5   6   9    
  2. Cette procédure calcule quel est, dans la liste t, le nombre y le plus proche de x.
  3. Pour calculer l'indice de y dans la liste au lieu de sa valeur :
      mystere := proc(t, x)
        j := 1;
        for i from 2 to nops(t) do
          if abs(x - t[i]) < abs(x - t[j]) then j := i fi;
        od;
        j;
      end;
    

Exercice 3 (5 points)

  1. Le codage RGB de la couleur d'un lien hypertexte vaut 6495ed (chiffres hexadécimaux), d'où la table :

    Couleur primaire Rouge Vert Bleu
    Intensité hexadécimale 64 95 ed
    Intensité décimale 6*16 + 4 = 100 9*16 + 5 = 149 14*16 + 13 = 237

  2. L'URL de l'image comporte le protocole (http) et le nom du serveur (medias.lemonde.fr), tandis que les URL des articles ne comportent pas ces renseignements, ce qui signifie que les articles sont sur le même serveur (www.lemonde.fr) que le document étudié.

    Note : la différence de format des fichiers (gif pour une image, html pour les articles) est intéressante à signaler (et rapporte un demi-point), mais la question portait sur le format des URL.

  3. Ne pas oublier de spécifier le nom du serveur : <A HREF="http://www.lemonde.fr/article/37446.html">centrale du Blayais</A>
  4. Autres balises :

Exercice 4 (4 points)

  1. La commande tracert donne la liste des routeurs qui acheminent un paquet de la machine locale vers une autre machine (ici www.w3.org).
  2. Les numéros qui apparaissent entre crochets sont les adresses IP (Internet Protocol) des routeurs.
  3. Les adresses IP sont converties en noms de machines (et de domaines) par un serveur DNS (Domain Name Service), qui sert d'annuaire .

Note : les questions 2 et 3 de cet exercice sont de simples "questions de cours" ; les réponses "ne s'inventent pas", tandis que la simple reconnaissance des adresses IP (question 2) rapporte deux points.

La réponse à la question 1 demande un peu d'intuition, mais les noms des domaines (bordeaux, puis niort, puis nice) indiquent clairement qu'il s'agit d'une "route" (tracert est l'abréviation de "trace route"). Comme certains étudiants l'ont noté, w3c1.inria.fr a la même adresse IP que www.w3.org : ce serveur niçois de l'INRIA est un serveur miroir pour le consortium w3. L'étudiant qui s'est étonné, dans sa copie, qu'on fasse de la recherche informatique à Nice, est probablement un Parisien égaré "en province" :-)

Exercice 5 (6 points)

  1. x = 23 = 16 + 4 + 2 + 1 s'écrit donc 10111 en numération binaire.
  2. La représentation binaire de 2x + 1 s'obtient en ajoutant un chiffre 1 à droite de celle de x, soit 101111.
  3. Pour obtenir la représentation binaire de 3x + 1 il suffit de faire l'addition des deux représentations précédentes :
       101111
     +  10111
      -------
      1000110
    
    La représentation binaire de f(x) est donc 100011 (la division par deux correspond à la suppression du zéro final).

    Il y a bien des façons de formuler l'algorithme général, par exemple : lire la représentation binaire de n de droite à gauche, et additionner chaque chiffre avec le suivant, en tenant compte des retenues, avec la retenue initialisée à 1.

  4. Simulation de l'exécution de g (23) :
    y 23 35 53 80
    k 0 1 2 3

    La procédure g calcule combien de fois il faut itérer f pour transformer n en un entier pair.

  5. L'examen de l'algorithme de la question 3 montre que si la représentation binaire de n se termine par exemple par 0111, celle de f(n) se termine par 011, celle de f∙f(n) par 01, et celle de f∙f∙f(n) par 0. Donc g(n) est égal au nombre de 1 consécutifs situés à droite de la représentation binaire de n.

Note : le calcul correct (et intelligent) des représentations binaires de x, 2x+1, et f(x) (questions 1, 2, 3) rapporte trois points. La question 4 rapporte deux points.