22. Annales des examens

Les examens de NFE204 durent 3 heures, les documents et autres soutiens ne sont pas autorisés, à l’exception d’une calculatrice.

Le but de l’examen est de vérifier la bonne compréhension des concepts et techniques vus en cours. Dans les rares cas où un langage informatique est impliqué, nous n’évaluons pas les réponses par la syntaxe mais par la clarté, la concision et la précision.

Examen du 3 février 2015

Première partie : recherche d’information (8 pts)

Voici quelques extraits d’un discours politique célèbre (un peu modifié pour les besoins de la cause). Chaque extrait correspond à un document, numéroté \(a_i\).

  1. (a1) Moi, président de la République, je ne serai pas le chef de la majorité, je ne recevrai pas les parlementaires de la majorité à l’Elysée.
  2. (a2) Moi, président de la République, je ne traiterai pas mon Premier ministre de collaborateur.
  3. (a3) Moi, président de la République, les ministres de la majorité ne pourraient pas cumuler leurs fonctions avec un mandat parlementaire ou local.
  4. (a4) Moi, président de la République, il y aura un code de déontologie pour les ministres et parlementaires qui ne pourraient pas rentrer dans un conflit d’intérêt.

Questions.

  • Rappeler la notion de stop word (ou “mot vide”) et donner la liste de ceux que vous choisiriez dans les textes ci-dessus.

  • Outre ces mots vides, pouvez-vous identifier certains mots dont l’idf tend vers 0 (en appliquant le logarithme)? Lesquels?

  • Présentez la matrice d’incidence pour le vocabulaire suivant: majorité, ministre, déontologie, parlementaire. Vous indiquerez l’idf pour chaque terme (sans logarithme), et le tf pour chaque paire (terme, document). Bien entendu, on suppose que les termes ont été fait l’objet d’une normalisation syntaxique au préalable.

  • Donner les résultats classés par similarité cosinus basée sur les tf (on ignore l’idf) pour les requêtes suivantes.

    • majorité; expliquez le classement;
    • ministre; expliquez le classement du premier document;
    • déontologie et ministre; qu’est-ce qui changerait si on prenait en compte l’idf?
    • majorité et ministre; qu’obtiendrait-t-on avec une requête Booléenne? Commentaire?
  • Calculez la similarité cosinus entre a3 et a4; puis entre a3 et a1. Qui est le plus proche de a3?

Seconde partie : Pig et MapReduce (6 pts)

Un système d’observation spatiale capte des signaux en provenance de planètes situées dans de lointaines galaxies. Ces signaux sont stockés dans une collection Signaux de la forme Signaux (idPlanète, date, contenu).

Le but est de déterminer si ces signaux peuvent être émis par une intelligence extra-terrestre. Pour cela les scientifiques ont mis au point les fonctions suivantes:

  1. Fonction de structure: \(f_S(c): Bool\), prend un contenu en entrée, et renvoie true si le contenu présente une certaine structure, false sinon.
  2. Fonction de détecteur d’Aliens: \(f_D(<c>): real\), prend une liste de contenus structurés en entrée, et renvoie un indicateur entre 0 et 1 indiquant la probabilité que ces contenus soient écrits en langage extra-terrrestre, et donc la présence d’Aliens!

Bien entendu, il y a beaucoup de signaux: c’est du Big Data.

Questions.

  1. Ecrire un programme Pig latin qui produit, pour chaque planète, l’indicateur de présence d’Aliens par analyse des contenus provenant de la planète.
  2. Donnez un programme MapReduce qui permettrait d’exécuter ce programme Pig en distribué (indiquez la fonction de Map, la fonction de Reduce, dans le langage ou pseudo-code qui vous convient).
  3. Ecrire un programme Pig latin qui produit, pour chaque planète et pour chaque jour, le rapport entre contenus structurés et non structurés reçus de cette planète.

Troisième partie : questions de cours (6 pts)

Concision et précision s’il vous plaît.

  • En recherche d’information, qu’est-ce que le rappel? qu’est-ce que la précision?

  • Deux techniques fondamentales vues en cours sont la réplication et le partitionnement. Rappelez brièvement leur définition, et indiquez leurs rôles respectifs. Sont-elles complémentaires? Redondantes?

  • Qu’est-ce qu’une architecture multi-nœuds, quels sont ses avantages et inconvénients?

  • Vous avez 500 TOs de données, et vous pouvez acheter des serveurs pour votre cloud avec chacun 32 GO de mémoire et 10 TOs de disque. Le coût unitaire d’un serveur eest de 500 Euros.

    Quelle est la configuration de votre grappe de serveurs la moins coûteuse (financièrement) et combien de temps prend au minimum la lecture complète de la collection avec cette solution?

  • Même situation: quelle est la configuration qui assure le maximum d’efficacité, et quel est son coût financier?

  • Rappelez le principe de l’éclatement d’un fragment dans le partitionnement par intervalle.

Examen du 14 avril 2015

Première partie : recherche d’information (8 pts)

Voici notre base documentaire:

  • d1: Le loup et les trois petits cochons.
  • d2: Spider Cochon, Spider Cochon, il peut marcher au plafond. Est-ce qu’il peut faire une toile? Bien sûr que non, c’est un cochon.
  • d3: Un loup a mangé un mouton, les autres moutons sont restés dans la bergerie.
  • d4: Il y a trois moutons dans le pré, et un autre dans la gueule du loup.
  • d5: L’histoire extraordinaire des trois petits loups et du grand méchant cochon.

On va se limiter au vocabulaire loup, mouton, cochon.

  • Donnez la matrice d’incidence booléenne (seulement 0 ou 1) avec les termes en ligne (NB: on suppose une phase préalable de normalisation qui élimine les pluriels, majuscules, etc.)

  • Expliquez par quelle technique, avec cette matrice d’incidence, on peut répondre à la requête booléenne “loup et cochon mais pas mouton”. Quel est le résultat?

  • Maintenant donnez une matrice d’incidence contenant les tf, et un tableau donnant les idf (sans le log), pour les trois termes précédents.

  • Donner les résultats classés par similarité cosinus basée sur les tf (on ignore l’idf) pour les requêtes suivantes.

    • cochon;
    • loup et mouton;
    • loup et cochon.
  • On ajoute le document d6: “Shaun le mouton: une nuit de cochon”.

    Quel est son score pour la requête “loup et mouton”, quel autre document a le même score et qu’est-ce qui change si on prend en compte l’idf?

  • Pour la requête “loup et cochon” et les documents d1 et d5, qu’est-ce qui change si on ne met pas de restriction sur le vocabulaire (tous les mots sont indexés)?

Seconde partie : Pig et MapReduce (6 pts)

Une organisation terroriste, le Spectre, envisage de commettre un attentat dans une station de métro. Heureusement, le MI5 dispose d’une base de données d’échanges téléphoniques et ses experts ont mis au point un décryptage qui identifie la probabilité qu’un message provienne du Spectre d’une part, et fasse référence à une station de métro d’autre part.

Après décryptage, les messages obtenus ont la forme suivante:

{
 "id": "x1970897",
 "émetteur": "Joe Shark",
 "contenu": "Hmm hmm hmmm",
 "probaSpectre": 0.6,
 "station": "Covent Garden"
 }

Il y en a des milliards: vous avez quelques heures pour trouver la solution.

  1. Spécifier les deux fonctions du programme MapReduce qui va identifier la station-cible la plus probable. Ce programme doit sélectionner les messages émis par le Spectre avec une probabilité de plus de 70%, et produire, pour chaque station le nombre de tels messages où elle est mentionnée.
  2. Quel est le programme Pig qui exprime ce traitement MapReduce?
  3. On veut connaître les 5 mots les plus couramment employés par chaque émetteur dans le contenu de ses messages. Expliquez, avec la formalisation de votre choix, comment obtenir cette information (vous avez le droit d’utiliser un opérateur de tri).

Troisième partie : questions de cours (6 pts)

  • En recherche d’information, que signifient les termes “faux positifs” et “faux négatifs”?
  • Je soumets une requête \(t_1, t_2, \cdots, t_n\). Quel est le poids de chaque terme dans le vecteur représentant cette requête? La normalisation de ce vecteur est elle importante pour le classement (justifier)?
  • Donnez trois bonnes raisons de choisir un système relationnel plutôt qu’un système NoSQL pour gérer vos données.
  • Donnez trois bonnes raisons de choisir un système NoSQL plutôt qu’un système relationnel pour gérer vos données.
  • Rappeler la règle du quorum (majorité des votants) en cas de partitionnement de réseau, et justifiez-la.
  • Dans un traitement MapReduce, peut-on toujours se contenter d’un seul reducer? Avantages? Inconvénients?

Examen du 15 juin 2015

Première partie : documents structurés (6 pts)

Une application s’abonne à un flux de nouvelles dont voici un échantillon.

<myrss version="2.0">
  <channel>
    <item>
        <title>Angela et nous</title>
        <description>Un nouveau sommet entre la France et l'Allemagne
            est prévu en Allemagne la semaine prochaine pour relancer l'UE.
        </description>
        <links>
            <link>lemonde.fr</link>
            <link>lesechos.fr</link>
        </links>
    </item>
    <item>
        <title>L'Union en crise</title>
        <description> L'Allemagne, la France, l'Italie doivent à nouveau se
            réunir pour étudier les demandes de la Grèce.
        </description>
        <links>
            <link>lefigaro.fr</link>
        </links>
    </item>
    <item>
        <title>Alexis à l'action</title>
        <description>Le nouveau premier ministre de la Grèce
            a prononcé son discours d'investiture.
        </description>
        <links>
            <link>libe.fr</link>
        </links>
    </item>
    <item>
        <title>Nos cousins transalpins</title>
        <description>La France et l'Italie partagent plus qu'une frontière
            commune: le point de vue de l'Italie.
        </description>
        <links>
            <link>courrier.org</link>
        </links>
    </item>
  </channel>
</myrss>

Chaque nouvelle (item) résume donc un sujet et propose des liens vers des médias où le sujet est développé. Les quatre éléments item seront désignés respectivement par d1, d2, d3 et d4.

  1. Donnez la forme arborescente de ce document (ne recopiez pas tous les textes: la structure du document suffit).
  2. Proposez un format JSON pour représenter le même contenu (idem: la structure suffit).
  3. Dans une base relationnelle, comment modéliser l’information contenue dans ce document?
  4. Quelle est l’expression XPath pour obtenir tous les éléments link?
  5. Quelle est l’expression XPath pour obtenir les titres des items dont l’un des link est lemonde.fr?

Deuxième partie : recherche d’information (6 pts)

On veut indexer les nouvelles reçues de manière à pouvoir les rechercher en fonction d’un pays. Le vocabulaire auquel on se restreint est donc celui des noms de pays (Allemagne, France, Grèce, Italie).

  1. Donnez une matrice d’incidence contenant les tf pour les quatre pays, et un tableau donnant les idf (sans appliquer le log). Mettez les noms de pays en ligne, et les documents en colonne.

  2. Donner les résultats classés par similarité cosinus basée sur les tf (on ignore l’idf) pour les requêtes suivantes. Expliquez brièvement le classement.

    • Italie;
    • Allemagne et France ;
    • France et Grèce.
  3. Reprenons la dernière requête, “France et Grèce” et les documents d2 et d3. Qu’est-ce que la prise en compte de l’idf changerait au classement?

Troisième partie : MapReduce (4 pts)

Voici quelques analyses à exprimer avec MapReduce et Pig.

  1. On veut compter le nombre de nouvelles consacrées à la Grèce publiées par chaque média. Décrivez le programme MapReduce (fonctions de Map et de Reduce) qui produit le résultat souhaité. Donnez le pseudo-code de chaque fonction, ou indiquez par un texte clair son déroulement.

    Vous disposez d’une fonction contains($texte, $mot) qui renvoie vrai si $texte contient $mot.

  2. Quel est le programme Pig qui exprime ce traitement MapReduce?

Quatrième partie : questions de cours (6 pts)

Questions reprises des Quiz.

Examen du 1er juillet 2016 (FOD)

Exercice corrigé: documents structurés et MapReduce (8 pts)

Note

Ce premier exercice (légèrement modifié et étendu) est corrigé entièrement. Les autres exercices consistaient en un énoncé classique de recherche d’information (8 points) et 4 brèves questions de cours (4 points).

Question 3: MapReduce et la notion de document “autonome”

Question

On veut implanter, par un processus MapReduce, le calcul de la moyenne des notes d’un étudiant. Quelle est la représentation la plus appropriée parmi les trois précédentes (une en relationnel, deux en documents structurés), et pourquoi?

La première représentation est très bien adaptée à MapReduce, puisque chaque document contient l’intégralité des informations nécessaires au calcul. Si on prend le document pour Jean Dujardin par exemple, il suffit de prendre le tableau des UE et de calculer la moyenne. Donc, pas besoin de jointure, pas besoin de regroupement. Le calcul peut se faire intégralement dans la fonction de Map, et la fonction de Reduce n’a rien à faire.

C’est l’iiustration de la notion de document autonome: pas besoin d’utiliser des références à d’autres documents (ce qui mène à des jointures en relationnel) ou de distribuer l’information nécsesaire dans plusieurs documents (ce qui mène à des regroupements en MapReduce).

Si on a choisit de construire les documents structurés en les centrant sur le UEs, il y a beaucoup plus de travail, comme le montre la question suivante.

Question 4: MapReduce, outil de restructuration/regroupement

Question

Spécifiez le calcul du nombre d’étudiants par UE, en MapReduce, en prenant en entrée des documents centrés sur les étudiants (exemple donné ci-dessus).

Cette fois, il va falloit utiliser toutes les capacités du modèle MapReduce pour obtenir le résultat voulu. Comme suggéré par la question précédente, la représentation centrée sur les UE serait beaucoup plus appropriée pour disposer d’un document autonome contenant toutes les informations nécessaires. C’est exactement ce que l’on va faire avec MapReduce: transformer la représentation centrée sur les étudiants en représentation centrée sur les UEs, le reste est un jeu d’enfant.

La fonction de Map

Une fonction de Map produit des paires (clé, valeur). La première question à se poser c’est: quelle est la clé que je choisis de produire? Rappelons que la clé est une sorte d’étiquette que l’on pose sur chaque valeur et qui va permettre de les regrouper.

Ici, on veut regrouper par UE pour pouvoir compter tous les étudiants inscrits. On va donc émettre une paire intermédiaire pour chaque UE mentionnée dans un document en entrée. Voici le pseudo-code.

function fonctionMap ($doc) # doc est un document centré étudiant
{
  # On parcourt les UEs du tableau UEs
  for    [$ue in $doc.UEs] do
     emit ($ue.id, $doc.nom)
  done
}

Quand on traite le premier document de notre exemple, on obtient donc trois paires intermédiaires:

{"ue:11", "Jean Dujardin"}
{"ue:27", "Jean Dujardin"}
{"ue:37", "Jean Dujardin"}

Et quand on traite le second document, on obtient:

{"ue:13", "Vanessa Paradis"}
{"ue:27", "Vanessa Paradis"}
{"ue:76", "Vanessa Paradis"}

Toutes ces paires sont alors transmises à “l’atelier d’assemblage” qui les regroupe sur la clé. Voici la liste des groupes (un par UE).

{"ue:11", ["Jean Dujardin"]}
{"ue:13", "Vanessa Paradis"}
{"ue:27", ["Jean Dujardin", "Vanessa Paradis"]}
{"ue:37", "Jean Dujardin"}
{"ue:76", "Vanessa Paradis"}

Il reste à appliquer la fonction de Reduce à chaque groupe.

function fonctionReduce ($clé, $tableau)
{
  return ($clé, count($tableau)
}

Et voilà.

Question 5: MapReduce = group-by SQL

Question

Quelle serait la requête SQL correspondant à ce dernier calcul sur la base relationnelle ?

Avec SQL, c’est direct, à condition d’accepter de faire des jointures.

select u.id, u.titre, count(*)
from Etudiant as e, Inscription as i, UE as u
where e.id = i.idEtudiant
and   u.id = i.idUE
group by u.id, u.titre