Aux nouvelles
Notes du final
Vos notes à ce cours sont disponibles sous forme brute sur la page Studium. Comme je n'arrive pas à y importer vos notes lettrées, je vous ai envoyé à 22h30 un code secret qui vous permet d'identifier toutes vos notes (normalisées tel qu'indiqué dans le plan de cours: 15 points pour les exercices notés, 15 points pour chaque devoir, 25 points pour l'intra et 30 points pour le final) dans la page suivante. Prenez note qu'une permanence vous est donnée vendredi 9 janvier de 13h30 à 15h00 afin que vous puissiez passer voir votre examen final. Manifestez tout problème rencontré dans vos notes rapidement (tout ce qui concerne les exercices notés et les devoirs doit être envoyé aux démonstrateurs). À celles et ceux que je ne reverrai pas, bonne continuation et à tous, une bonne année 2015.
Devoir 2
Vous êtes plusieurs à me demander une extension pour le devoir 2, aussi la date limite à été reportée au 18 décembre (après, il sera difficile de corriger dans les temps). Bon temps des fêtes.
À propos du final
Rappel: examen final jeudi 11 décembre de 15h30 à 18h29. Vous avez été informé par courriel: l'examen se déroulera dans deux salles: G-715 (section A) et G-615 (section B) du pav. Roger Gaudry.
Vous avez le droit à 2 feuilles (US letter) de notes (recto-verso). Tout autre document est interdit. L'usage de votre ordinateur (ou téléphone intelligent) ne sera pas permi, pas plus que l'usage d'internet. La matière à l'examen porte sur tout ce que vous avez vu en cours à l'exclusion de l'introduction à la programmation fonctionnelle.
Examens passés
Les sujets des examens finaux des sessions automne 2012 et 2103 sont disponibles (voir le cours de la semaine du 1 au 5 décembre). Des exercices de ces examens seront traités en démonstration.
Exercice noté 7
Le sujet est disponible (suivre le lien travaux) et est à remettre via studium d'ici dimanche 30.
Devoir 2
Le sujet du devoir 2 est disponible (suivre le lien travaux) et est à remettre via studium le 15 décembre 2014. Le sujet sera présenté lors de la prochaine démonstration.
Exercice noté 6
Le sujet est disponible (suivre le lien travaux) et est à remettre via studium d'ici dimanche 23.
Exercice noté 5
Le sujet est disponible (suivre le lien travaux) et est à remettre via studium d'ici vendredi 14.
Interpréteur ligne de commande
L'interpréteur ligne de commande js
de SpiderMonkey a été
installé par l'équipe de support sur les machines d'enseignement. Il
vous est possible de l'invoquer en tapant js24
(ex: js24 algo-tab.js
si vous vous trouvez dans le
répertoire où se trouve algo-tab.js
). Notez que
l'interpréteur js
continue à exister, mais que les codes
que nou voyons en cours ne sont pas compatibles avec cet interpréteur.
Exercice noté 4
Le sujet est disponible sur Studium, la remise est prévue pour vendredi 7 novembre.
Changement de prof
Je donne le cours à partir de la semaine du 27 octobre 2014.
Attention: un changement de prof vient avec
des changements d'habitudes. Mes informations sont dans le lien
contacts
. N'hésitez pas à passer me voir ou à me
contacter
par email.
TP2: Javascript et la traduction
(voir ce sujet sans les cadres: [ici])
Cadre général
Dans ce devoir, vous allez mettre en pratique la programmation procédurale, la programmation orientée objet ainsi (probablement) que la récursivité. Votre but est de réaliser un mini système de traduction. Vous avez pour cela accès à une table de traduction (un lexique bilingue) qui servira de base à la génération de traductions. Cette table de traduction peut-être trop lourde pour être manipulée dans codeboot, aussi plusieurs versions de cette ressource sont disponibles (en ordre décroissant de taille):
- [ibm-0.0.js] (3.3Mo, 95k lignes)
- [ibm-0.5.js] (403K, 13k lignes)
- [ibm-0.9.js] (130K, 4.7k lignes)
- [ibm-0.5-1000.js] (31K, 1k lignes)
- [ibm-0.5-100.js] (3.1K, 100 lignes)
Chacune de ces versions (vous n'en avez besoin que d'une pour faire
votre devoir) déclare la variable lex
qui contient un
tableau de triplets qui sont respectivement: un mot en français, un
mot en anglais et la probabilité d'association de ces deux mots. Ainsi
dans l'extrait qui suit, la probabilité que navy
traduise marine
est de 0.636364
:
var lex = [ ["civilisations","civilisations",0.715347], ["blanco","blanco",0.692308], ["marine","navy",0.636364], ...
Afin de travailler avec ces données, vous devez inclure la commande
load
au tout début de votre programme (après le commentaire
initial qui identifie votre fichier) afin d'utiliser la
variable lex
comme dans l'exemple suivant. Il vous
appartient de copier la ressource dans votre répertoire de travail, ou
dans codeboot.
note:vous ne devez pas faire l'hypothèse que la
ressource lex
est triée (en fait certaines versions
distribuées plus haut ne le sont pas)
load("ibm-0.0.js"); // ou une autre ressource distribuee print(lex.slice(0,10)); // produira l'affichage suivant (sur une ligne): aaa,aaa,0.4,aac,acc,0.2,aad,aal,0.304348,aalto,aalto,0.75, aaltonen,aaltonen,0.761905,aamer,aamer,1,aan,aan,0.6, aarhus,aarhus,0.104784,aaron,aaron,1,aartsen,aartsen,0.382353
Note: si vous effectuez votre devoir sur codeboot, vous avez tout intérêt à prendre une table de petite taille. Les exemples d'exécution que je donne dans la suite sont produits avec la plus grande table.
Vous devez remettre un programme devoir2.js
qui offre un
ensemble de fonctionalités décrites ci-après. Vous êtes encouragés à
développer vos propres objets pour cela, mais n'attendez pas que nous
ayons couvert cette matière pour commencer: vous pouvez déjà réaliser
ce devoir de manière procédurale. Vous pourrez par la suite
réorganiser votre code à l'aide d'objets selon les suggestions qui
sont faites dans le sujet. Votre devoir doit accompagné d'un rapport
dont le contenu est détaillé plus loin.
Classe Lexique
Une partie de votre code est dédiée à la représentation du vocabulaire d'une langue (ou lexique). Les fonctionalités minimales d'un lexique que vous devez implémenter sont les suivantes:
add(word)
ajoute au lexique le mot passé en argument s'il n'existe pas déjàanagrams(word)
retourne la liste (tableau) des mots du vocabulaire qui sont des anagrames du mot passé en argument. Le mot passé en argument ne doit pas figurer dans le résultat, même s'il s'agit d'un mot du lexique.
Voici un exemple de programme qui pourrait être exécuté à l'aide de votre code.
load("ibm-0.0.js"); // definit la variable lex var lexique = new Lexique(); for (var i=0; i <lex.length; ++i) lexique.add(lex[i][0]); // le mot francais print(lexique.anagrams("rats")); // devrait produire: arts,star,tsar
Classe BiLexique
Afin de réaliser des traductions, vous devez représenter
efficacement le lexique bilingue de la table chargée en début de
programme (par la commande load
discutée plus haut). La
seule contrainte qui vous est donnée est que les traductions d'un mot
doivent être rangées en ordre décroissant de probabilité. La première
traduction accessible pour un mot source donné doit donc être la plus
probable selon la table que vous avez chargée. Aussi, pour des raisons
d'efficacité (surtout sous codeboot), vous pouvez encoder seulement
les n
meilleures traductions de chaque mot source
(où n
est un paramètre, par ex. 5
). Je vous
recommande pour cela d'écrire une classe qui doit
offrir minimalement les fonctionalités suivantes:
- un constructeur qui prend en argument le
tableau
lex
chargé en début de code et qui se chargera de représenter de manière efficace le lexique bilingue en mémoire. getTranslations(source)
retourne le tableau des traductions disponibles pour le mot source avec la probabilité associée, et ce, en ordre décroissant de probabilité.getScore(source,target)
retourne la probabilité d'association dans le lexique bilingue des deux mots. Si deux mots ne constituent pas une paire dans le lexique bilingue, alors 0 est retourné- il devrait être possible d'afficher un lexique de telle manière à ce que les traductions de chaque mot du lexique bilingue soient affichées en ordre décroissant de probabilité (voir l'exemple plus bas). Aucun tri ne devrait être effectué pour réaliser cet affichage.
Voici un exemple de programme qui pourrait être exécuté à l'aide de votre code.
load("ibm-0.0.js"); // definit la variable lex var bilex = new BiLexique("largest",lex); // largest le nom donné au lexique print(bilex); // pourrait produire qqchose comme le lexique largest est chargé et contient 95275 entrées pour 48573 mots sources ... abandonnant -> (abandoning,-3.01),(dropping,-4.01) abandonne -> (abandons,-1.39),(abandon,-3.60),(abandoning,-4.14),(abandoned,-4.38) abandonnent -> (abandon,-3.99),(abandoning,-4.14) abandonner -> (abandon,-1.25),(abandoning,-2.57),(abandoned,-3.15),(drop,-3.70),... ...
Classe Traducteur
Vous devez implémenter un traducteur qui exploite un lexique
bilingue. Les traductions sont produites en remplaçant chaque mot de
la phrase à traduire par l'une de ses traductions dans le lexique
bilingue. Les mots sources inconnus du lexique seront reproduits tel
quel dans la traduction. Le score d'une traduction est le produit des
probabilité de chaque association impliquée. Afin d'éviter les
problèmes rencontrés lorsqu'on multiplie ensemble plusieurs nombres
inférieurs à 1, on calculera le score dans le domaine des logs (avec
la fonction Math.log()
), aussi le score d'une traduction
sera-t-il donnée par la somme des log probabilités de chaque
association impliquée. On admettra que le log probabilité associé à un
mot inconnu (traduit par lui même) est -3
Les fonctionalités suivantes doivent être implémentées (des exemples sont fournis pour chaque fonctionalités):
set(phrase)
prend en argument un tableau de mots qui représente la phrase à traduire et en fait la phrase courante sur laquelle votre traducteur va travaillergetUnks()
retourne les mots de la phrase en cours qui ne sont pas connus du lexique bilingue.getNbTranslations()
qui retourne le nombre total de traductions qu'il est possible de former selon le processus décrit plus haut.gloss()
retourne une traduction (un tableau de mots) et sa probabilité en prenant pour chaque mot de la phrase en cours une traduction au hasard dans le lexique. Ainsi, si dans le lexique bilingue, les associations suivantes sont diponibles, alors une traduction produite pourrait être:["such", "be", "the", "job", "from", "eu", "eu", "european", "and"]
avec comme score-29.67
, la somme des logs probabilités de chaque association impliquée (en gras dans l'exemple-2.64-3.01-1.33-3.54-1.15-1.57-3.47-8.72-4.24
):telle -> (such,-2.64) (kind,-3.50) sera -> (will,-2.38) (be,-3.01) la -> (the,-1.33) (a,-3.33) tâche -> (task,-0.98) (job,-3.54) (tasks,-4.02) de -> (of,-0.77) (from,-1.15) (to,-1.62) l -> (europe,-1.14) (human,-1.46) (eu,-1.57) union -> (union,-1.47) (eu,-3.47) européenne -> (european,-0.72) (eu,-2.19) (europe,-3.99) . -> (.,-0.04) (and,-4.24) (,,-4.56)
On notera que deux appels àgloss
retourneront (à priori) des résultats différents. Si un mot dans la phrase en cours n'est pas connu, alors ce mot est laissé tel quel dans la traduction (il est sa propre traduction) et le score de l'association est fixée à-3
(domaine logarithmique).translate(n)
qui retourne un tableau des (au plus)n
meilleures traductions de la phrase en cours. Contrairement à la fonctiongloss
qui retourne une traduction aléatoire, vous chercherez ici à produire les traductions de meilleur coût (la somme de logprob la plus grande). Dans la mesure où le score d'une traduction est la somme des associations impliquées, la traduction de meilleur score est celle obtenue en prenant pour chaque mot source, sa traduction la plus probable. Dans l'exemple précédant, la traduction la plus probable est donc["such", "will", "the", "task", "of", "europe", "union", "european", "."]
. Votre fonction doit vérifier qu'aucune traduction ne contiendra le motan
suivi (directement) d'un mot commençant par une consonne, ni aucun mota
suivi (directement) d'un mot commençant par une voyelle.
load('ibm-0.0.js'); // definit la variable lex ... var tr = new Traducteur(...); // indique la phrase sur laquelle travailler tr.set(["je", "parle", "de", "la", "commission", "de", "la", "pêche", "."]);
tr.set(["je", "parle", "de", "la", "commission", "de", "la", "pêche", "."]); // affiche de les mots inconnus de la phrase source print('UNK', tr.getUnks().join(" "));
Test
Vous disposez de phrases de test ainsi que de leur traduction de
référence (traduction humaine) dans le
fichier test-100.js que
vous chargerez également au début de votre programme à l'aide de la
commande load
. Voici ce à quoi ressemble ce fichier:
var test = [ ["telle sera la tâche de l union européenne .", "that will be the task of the european union ."], ["ce n est pas le travail du parlement .", "this is not a job for parliament ."], ["le fait d avoir des évaluations différentes rend-il service ?", "is it laudable that different assessments have been made ?"], ... ];
Vous devez remettre une fonction tests()
qui passe en
revue chacune des phrases du tableau test
, affiche ses 10
meilleures traductions en ordre décroissant de (log) probabilité, la
traduction de référence, ainsi que la liste des mots de la phrase en
cours qui sont inconnus du lexique utilisé pour la
traduction. L'affichage que votre programme doit produire est prescrit
par l'exemple qui suit
(cliquer ici pour une trace
complète produit à l'aide de la plus grosse table):
--- SRC 1: telle sera la tâche de l union européenne . ANA 1: telle sare al tâche ed l union européenne . REF 1: that will be the task of the european union . UNK 1: NBT 1: 37632 GLO 1: kind will the job in europe eu european and -25.73 -- 1 such will the task of europe union european . -11.46 2 such will the task of europe union eu . -12.92 3 such will the task of europe union europe . -14.72 4 such will the task of europe union union . -15.00 5 such will the task of europe union european and -15.66 6 such will the task of europe union european , -15.98 7 such will the task of europe union eu and -17.13 8 such will the task of europe union eu , -17.44 9 such will the task of europe union europe and -18.93 10 such will the task of europe union europe , -19.24 --- SRC 2: ce n est pas le travail du parlement . ANA 2: ce n tes psa el travail du parlement . REF 2: this is not a job for parliament . UNK 2: NBT 2: 6065280 GLO 2: it cannot has step president job on house , -22.91 -- 1 this never is not president work parliament . -7.60 2 this never is not president work house . -8.80 3 this never is not president work of parliament . -9.11 4 this never is not president work of house . -10.31 5 this never is not president work parliament and -11.81 6 this never is not president work parliament , -12.12 7 this never is not president work house and -13.00 8 this never is not president work house , -13.31 9 this never is not president work of parliament and -13.32 10 this never is not president work of parliament , -13.63
Les choses suivantes sont affichées pour chaque paire de phrases
du tableau test
:
- La ligne préfixée par
SRC
qui indique la phrase source à traduire. - La ligne préfixée par
ANA
qui affiche une tranformation de la phrase source où chaque mot qui possède un anagramme dans le lexique est remplacé (aléatoirement) par un de ses anagrammes. - La ligne préfixée par
REF
qui indique la traduction de référence (celle fournie danstest
) - La ligne préfixée par
UNK
qui mentionne la liste des mots de la phrase source qui sont inconnus du lexique utilisé pour faire les traductions - La ligne préfixée par
NBT
qui indique le nombre de traductions différentes qu'il est possible de générer par le processus décrit plus haut - La ligne préfixée par
GLO
qui affiche une traduction produite à l'aide de la fonctiongloss
translate
.
Rapport
Vous devez remettre un rapport d'au plus 3 pages qui décrit
l'algorithme avec lequel vous avez produit vos traductions dans la
fonction translate
. Vous indiquerez également dans ce
rapport tout ce qui vous semble pertinent (encodage des données,
problèmes rencontrés, etc.). Ce rapport peut être au format pdf ou
simplement au format texte.
Notation
Votre code sera exécuté sur un interpréteur ligne de commande
compatible avec les codes vus en cours (js24
installé sur
les machines d'enseignement). La dernère ligne de votre programme doit
être un appel à la fonction tests
décrites plus
haut. Lors des tests, nous utiliserons une autre table de traduction
et un autre jeu de test que ceux chargés par votre programme,
possiblement plus grande que celle que vous avez utilisée.
Lorsqu'exécuté sur un interpréteur ligne de commande, votre programme doit être suffisamment rapide pour executer toutes les traductions en quelques secondes au plus (incluant le temps d'encodage du lexique en mémoire) pour le plus grand des lexiques. Vous devez donc réfléchir à la façon de représenter vos données en mémoire.
Ce travail est à faire de préférence en binôme, mais il est possible de le faire seul. Si vous travaillez en binôme, il est important que le nom des deux personnes soit indiqué en entête de tous les documents remis.
Conseil: Commencez à travailler dès maintenant. Si vous avez l'impression d'écrire souvent du code très similaire c'est que vous pouvez l'organiser plus efficacement.
Notation: La notation dépendra:
- de la lisibilité de votre code (2 points)
- de sa bonne organisation en fonctions et en objets (4 points)
- de la représentation en mémoire de la table de transfert (2 points)
- de l'exactitude avec laquelle vous réalisez la
fonction
translate
(3 points). Le code que j'ai utilisé pour produire les traces d'exécution ne parvient pas nécessairement à trouver les 10 meilleurs traductions d'une phrase source et n'aurait par conséquent pas la note maximale, - de votre rapport (2 points),
- du bon fonctionnement global de votre code.