Cours gratuits » Cours informatique » Cours programmation » Cours Oberon » Tp Empiriques Methodes et Langages de script Sous Oberon En pdf

Tp Empiriques Methodes et Langages de script Sous Oberon En pdf

Problème à signaler:

Télécharger



★★★★★★★★★★3.5 étoiles sur 5 basé sur 1 votes.
Votez ce document:

Empiriques Methodes et Langages de script Sous Oberon

1 Exercice 1: un concordancier

Un concordancier est un outil d’exploration de données textuelles, qui, étant donnéun corpus de textes et un mot, extrait les occurences de ce mot ainsi que les contextes gauche et droit dans lesquels ce mot apparaît.

On vous demande de programmer un tel concordancier. Si on fournissait, par exemple, à votre concordancier le paragraphe précédent et le mot un, il afficherait le résultat suivant:

">un concordancier est un outil d’expl... un concordancier est un outil d’exploration de donne... ..., qui, etant donne un corpus de textes et un mot,...

...un corpus de textes et             un mot, extrait les occur...

2 Exercice 2: les structures complexes et les références anonymes

Au moyen de r´eférences, on peut créer en Perl des structures arbitrairement complexes. Une référence sur une variable scalaire, une variable de tableau ou une variable de tableau associatif est obtenue en préfixant le symbole ’\’ à cette variable. Voici quelques exemples:

$i = 3.14159;

@a = (’log’, ’exp’, ’DIV’);

%h = (’Google’ => 1, ’Microsoft’ => 0);

$ri = \$i; # $ri pointe sur $i

$ra = \@a; # $ra pointe sur @a

$rh = \%h; # $rh pointe sur %h

On peut déréférencer un scalaire en mettant entre accolades la référence scalaire et en préfixant le type ($, @ ou %) de la variable référencée. Par

exemple:

$dri = ${$ri}; # $dri prend pour valeur le scalaire $i @dra = @{$ra}; # @dra prend pour valeur le tableau @a %drh = %{$rh}; # %drh prend pour valeur le tableau %h

Il y a deux façons d’accéder aux objets enregistrés dans un tableau as-sociatif ou non référencépar un scalaire:

1)

$k = ${$ri}[1]; # $k vaut le deuxieme scalaire du tableau @{$ri}

$l = ${$rh}{’Google’}; # $l vaut la valeur de la cle ’Google’ du hash %{$rh}

2)

$k = $ri->[1]; # $k vaut le deuxieme scalaire du tableau @{$ri}

$l = $rh->{’Google’}; # $l vaut la valeur de la cle ’Google’ du hash %{$rh}

Perl vous permet de créer des références sur des tableaux ou des hashes anonymes. Une référence sur un tableau anonyme est obtenue en plaçant les éléments de ce tableau entre ’[’ et ’]’. Une référence sur un tableau associatif anonyme est obtenue en plaçant les paires clé/valeur de ce tableau associatif entre ’{’ et ’}’. Voici deux exemples de références anonymes:

$ranoa = [’log’, ’exp’, ’DIV’];

# $ranoa pointe sur le tableau anonyme (’log’, ’exp’, ’DIV’)

$ranoh = {’Google’ => 1, ’Microsoft’ => 0};

# $ranoh pointe sur le hash anonyme (’Google’ => 1, ’Microsoft’ => 0)

Pour réaliser cet exercice, considérez les déclarations ci-dessous:

$pi = 3.14159;

@a = (’log’, ’exp’, ’DIV’);

%h = (’Google’ => 1, ’Microsoft’ => 0);

$rh = {

’pi’ => \$pi;

’ra’ => \@a;

’rh’ => \%h;

};

On vous demande d’écrire, de deux façons distinctes, le code qui affiche sur la sortie standard la valeur:

  1. de la clé’pi’ de la référence $rh
  2. du second élément du tableau référencéassociéa la cle ’ra’
  3. de la clé’Google’ du hash référencéassociéa la cle ’rh’

3 Exercice 3: Un module pour les anneaux

Un anneau ou une queue circulaire (en anglais ring buffer) est une structure de données de type FIFO: les données sont retirées dans l’ordre dans lequel elles ont étéinsérées. Ces structures circulaires sont typiquement utilisées pour transmettre des données entre deux processus asynchrones, un proces¬sus producteur et un processus consommateur. Le processus producteur pro¬duit des données insérées en queue d’anneau et le processus consommateur consomme les données en tête d’anneau.

Une queue circulaire est formée d’un tableau dont la capacitéa étéfixée. Les scalaires de ce tableau sont des références sur des hashes dont les clés sont ’_object’ et ’_next’. La valeur d’une clé’_object’ est l’objet que le client enregistre dans l’anneau. La valeur d’une clé’_next’ est

l’indice du prochain scalaire du tableau. Par exemple, si l’anneau est forméd’un tableau @buffer de 3 scalaires, alors $buffer[0]->{’_next’} vaut 1,

$buffer[1]->{’_next’} vaut 2, et, puisque la queue est circulaire,

$buffer[2]->{’_next’} vaut 0.

Pour insérer des éléments en queue ou retirer des éléments en tête, on utilise deux scalaires $head et $tail, qui sont, respectivement, les indices du pre

mier et du dernier élément de la queue. Le scalaire $head est incrémentélorsqu’un élément est retiré, et le scalaire $tail est incrémentélorsqu’ un

élément est inséré. Bien entendu, aucun élément ne peut être retiréd’un anneau vide et aucun élément ne peut être insérédans un anneau plein. On vous demande de compléter le module ci-dessous et de coder un pro¬gramme qui teste votre module complété:

#!/usr/bin/perl

use strict; use warnings;

package ModuleRingBuffer;

BEGIN {

sub init($); # initialize ring buffer with given capacity

sub store($); # store a scalar argument in ring buffer

sub retrieve; # return element at front of buffer

sub printringb; # print ring buffer

sub full; # decide whether buffer is full or not

sub empty; # decide whether buffer is empty or nor

use Exporter;

our @ISA = qw/Exporter/;

our @EXPORT = qw/init store retrieve printringb full empty/; # exported subs

}

# ...

END { }

1;

4 Exercice 4: l’évaluation de références anonymes, les expressions régulières et les modules

PERL permet de créer des références sur des objets anonymes. Par exemple, le code suivant

$r-ano-array = [ ’a’, ’b’, ’c’ ];

crée un tableau (’a’, ’b’, ’c’) et retourne une référence affectée à $r-ano-array. PERL interprète donc [ ’a’, ’b’, ’c’ ] comme une référence sur un tableau. On dit que ce tableau est anonyme, car on ne peut y accéder que via la référence $r-ano-array.

On peut former des structures anonymes plus complexes: il suffit qu’un élément du tableau soit une référence sur un tableau anonyme. Par exem¬ple, le code suivant

$r-ano-array = [’*’, ’a’, [’-’, ’b’, ’c’, ’d’]];

crée une structure enchassée qu’on peut interpréter comme un arbre et sur laquelle le scalaire $r-ano-array pointe.

La fonction eval de PERL est magique: elle interprète son argument, qu’elle considère comme du code PERL, et retourne sa valeur. Elle permet donc d’appeler l’interpréteur PERL dans le corps d’un programme. Il s’ensuit que si on lui passait une chaîne telle que

‘‘[’*’, ’a’, [’-’, ’b’, ’c’, ’d’]]”elle retournerait une référence sur la structure anonyme

[’*’, ’a’, [’-’, ’b’, ’c’, ’d’]]. On vous demande de coder un programme

  • qui prend en entrée la représentation parenthésée d’un arbre syntax¬ique (vous trouverez dans le fichier syns.dat quelques exemples à traiter),
  • qui la transforme au moyen d’expressions régulières de telle sorte qu’elle puisse être interprétée par la fonction eval comme une struc¬ture complexe
  • et, enfin, qui affiche cette structure complexe en appelant la fonction print-tree que le module PrettyPrinting.pm exporte.

Méthodes Empiriques et Langages de Script

1 Exercice 1: Une classe pour les heaps

En Perl, une classe n’est rien d’autre qu’un package qui met à disposition d’un client un constructeur d’instances ou d’objets de cette classe. Typique¬ment, un objet est une référence sur un tableau associatif. Les clés de ce tableau associatif renvoie aux champs ou attributs de l’objet. Pour associer une référence à un module (autrement dit, pour construire un objet d’une classe), Perl utilise l’opérateur bless qui prend une référence et un nom de module comme arguments. Voici, par exemple, une classe pour des objects qui peuvent être enregistrés dans une queue de priorité:

#!/usr/bin/perl

use strict; use warnings;

package PriorityQueueObject;

sub new { # constructor

my $class = shift;

my $priority = shift;

my $object = shift;

my $pqo = {

_priority => $priority,

_object => $object

};

bless $pqo, $class;

return $pqo;

}

sub priority {

my $pqo = shift;

return $pqo->{_priority};

}

sub object {

my $pqo = shift;

return $pqo->{_object};

}

1;

Et voici comment un client pourrait utiliser la classe PriorityQueueObject:

#!/usr/bin/perl

use strict; use warnings;

use PriorityQueueObject;

my $obj = ’Google’;

my $pqo = PriorityQueueObject->new(128, $obj);

print $pqo->object, ":", $pqo->priority, "\n";

Etant donnée la classe PriorityQueueObject, on vous demande de pro¬grammer une classe PriorityQueueHeap qui implémente les queues de pri¬oritéau moyen des heaps (littéralement, des tas). Vous trouverez une de-scription des queues de prioritéet de leur implémentation en Oberon dans le document …, réalisépar Luka Nerima. Il vous suffit donc de traduire le code orienté¬object Oberon en code orienté-object Perl. Vous devez également écrire un programme Perl qui test votre classe PriorityQueueHeap.

2 Exercice 2: Commentaire des modules Sexpr.pm et SexprNode.pm.

3 Exercice 3: un classifieur Naive Bayes pour la classification de documents textuels

On vous demande de programmer un classifieur bayésien naïf capable d’apprendre à classer des documents textuels. Le pseudo-code que vous devez implémenter en Perl vous a récemment étéprésentépar Paola.

Le pseudo-code de Paola spécifie deux procédures: la procédure d’apprentissage et la procédure de classification. Bien que le pseudo-code de ces deux procédures soit correcte, son implémentation exige quelques modifications. En effet, l’algorithme bayésien naïf demande de calculer un produit dont les facteurs sont des probabilités comprises entre 0 et 1. Or, le produit de nom¬bres compris entre 0 et 1 pourrait bien être plus petit que le plus petit nombre qu’une machine puisse représenter. Pour résoudre ce problème d’underflow, il suffit de substituer à une probabilitéson logarithme (la fonction loga

rithme étant croissante, maximiser un produit de probabilités équivaut à maximiser son logarithme). Rappelez-vous que la classe retournée par le NAiVE BAYES est la classe c qui maximise le produit P(c) × fli P(wi|c)

Or le logarithme d’un produit de facteurs est la somme des logarithmes de ces facteurs. Par conséquent, votre programme devra retounrner la classe c qui maximise la somme

logP(c) + Ei log P(wi|c)

Cette archive contient des messages de newsgroups. Sauvegardez cette archive et désarchivez-la au moyen de la commande tar -xzvf tp7_newgroups.tar.gz.

Il en résultera 7 répertoires: comp.sys.mac.hardware, comp.windows.x, etc. Chacun de ces répertoires correspond à une classe de newsgroups qui contient des messages. Partionnez ces messages en messages d’entraînement (99 % des messages de chaque répertoire) et messages de test (1 % des messages de chaque répertoire). Les messages n’ont pas étéprétraités: ils contiennent donc des mots (ou d’autres signes) qui ne sont pas utiles à la classification. Tâchez d’éliminer ces mots ou signes inutiles.

Rapportez également toutes les mesures de performance qui vous paraissent les plus pertinentes pour évaluer votre classifieur.

Vous devez me faire parvenir votre code et vos résultats au plus tard le 17 janvier 2007 à midi.


116