January 2008 - Annonce

article pour SAGT 2008
by Daniela Becker 31 Jan '08

31 Jan '08

We are pleased to announce that the following paper has been accepted for publication at the first Symposium on Algorithmic Game Theory (SAGT 2008) that will take place at Paderborn, Germany from April 30th to May 2nd. Sébastien Hémon, Miklos Santha and Michel de Rougemont. Approximate Nash Equilibria for multi-players Games. http://publis.lrde.epita.fr/2008-01-18-SAGT We consider Games of complete information with r players, and study the existence of polynomial time algorithms for \eps-approximate Nash equilibria in the additive and multiplicative sense. For the additive approximation, we prove an \frac{r-1}{r} lower bound on \eps for strategies using a support less than \sqrt[r-1]{\log{n}} where n is the maximum number of pure strategies, and give a polynomial time algorithm which computes an \frac{r-1}{r}-approximate Equilibrium. For the multiplicative approximation, we prove a Lipton-result to approximate a Nash Equilibrium. If we assume that the gains of the players at a Nash Equilibrium are greater than a value g, we find an \eps-approximate Nash equilibrium whose support is included in the support of the Nash equilibrium of size \frac{\log n.r}{g.\eps^2}. We exhibit a class of games where this hypothesis does not hold and where the support size of such an \eps-approximate Nash equilibrium is greater than \frac{n}{2.(1+\eps)}. -- Daniela Becker

1 0

[Annonce] Séminaire Performance et Généricité du LRDE le 30 Janvier
by Didier Verna 21 Jan '08

21 Jan '08

Chers collègues, la prochaine session du séminaire Performance et Généricité du LRDE (Laboratoire de Recherche et Développement de l'EPITA) aura lieu le 30 Janvier. Au programme: * 14h: Robustesse, efficacité et généricité dans la bibliothèque CGAL Sylvain Pion, chargé de recherche, INRIA Sophia Antipolis * 15h15: Morph-M et généricité en traitement d'images Romain Lerallut, ingénieur R&D chez A2iA Raffi Enficiaud, ingénieur de recherche chez DxO Labs L'entrée du séminaire est libre. Pour plus de renseignements, consultez http://seminaire.lrde.epita.fr/. Merci de bien vouloir diffuser cette information le plus largement possible. -- Didier Verna, didier(a)lrde.epita.fr, http://www.lrde.epita.fr/~didier EPITA / LRDE, 14-16 rue Voltaire Tel.+33 (0)1 44 08 01 85 94276 Le Kremlin-Bicêtre, France Fax.+33 (0)1 53 14 59 22 didier(a)xemacs.org

1 0

[Annonce] [Séminaire CSI] : mercredi 16 janvier 2008
by Daniela Becker 10 Jan '08

10 Jan '08

Bonjour, Vous êtes tous cordialement invités à assister au séminaire qui aura lieu le mercredi 16 janvier 2008 à 14 heures en Amphi Masters (KB). ----------------------------------------------------------------------- Le programme : *Transformers, Théorie des Jeux & Vérification du locuteur* http://www.lrde.epita.fr/cgi-bin/twiki/view/Publications/Seminar-2008-01-16 TRANSFORMERS 14h00 : revCPP : Un préprocesseur C++ réversible -- Quentin Hocquet 14h30 : Transformation de programmes en syntaxe concrète en C++ -- Benoit Sigoure 15h00 : Propagation automatique des attributs pour des grammaires attribuées modulaires -- Nicolas Pierron 15h30 : Désambiguïsation guidée par la sémantique: Comparaison de différentes méthodes -- Renaud Durlin THEORIE DES JEUX 16h15 : La tablette de chocolat transfinie -- Nicolas Neri VERIFICATION DU LOCUTEUR 16h45 : Combinaison de noyaux à partir de systèmes SVM en vérification du locuteur -- Charles Alban Deledalle ----------------------------------------------------------------------- Les Résumés des exposés : ************************** TRANSFORMERS revCPP : Un préprocesseur C++ réversible -- Quentin Hocquet Le but du projet Transformers est de créer un framework générique pour de la transformation source à source de code C++. Une transformation "source à source" consiste à retravailler le code et produire un fichier de code source modifié. Ce code peut être relu, ré-utilisé, modifié ... par des programmeurs et doit donc être lisible. De plus, il doit respecter le coding style d'origine. Ce processus de préservation de la mise en page est appelé "High fidelity program transformation". Transformers cible les langages C et C++. Contrairement à de nombreux langages, le C++ est un langage préprocessé pour obtenir le code source effectif. Dans le contexte de la transformation de programmes, il faut dé-préprocesser le code pour le rendre lisible au programmeur. Ce document présente le travail de recherche que nous avons mené pour implémenter un préprocesseur de C++ réversible et un postprocesseur, c'est-à-dire un outil permettant d'obtenir le code d'origine à partir du code préprocessé. Transformation de programmes en syntaxe concrète en C++ -- Benoit Sigoure La transformation de programmes dans des langages généralistes tels que le C++ est fastidieuse car elle nécessite de manipuler l'AST du programme transform en syntaxe abstraite (c'est-à-dire dans le langage hôte, ici le C++). Le code à écrire est lourd et coûteux à maintenir. Le but de ce séminaire est de présenter la mise en œuvre de nouvelles techniques de transformation de programmes en syntaxe concrète (c'est-à-dire utilisant directement le langage du programme transformé) dans un environnement C++ standard. Notre approche utilise l'analyseur syntaxique l'exécution pour appliquer des règles de transformation dynamiques. Un compilateur de Tiger servira de support à la présentation. Propagation automatique des attributs pour des grammaires attribuées modulaires -- Nicolas Pierron Les grammaires attribuées sont plus adaptées pour décrire (des parties de) la sémantique d'un langage de programmation : accrochées sur les règles de production syntaxique, elles permettent d'exprimer des relations locales qui sont par la suite liées entre elles globalement par un évaluateur générique. Cependant elles ne passent pas à l'échelle quand on travaille avec des langages volumineux et complexes. Premièrement les attributs qui sont requis quasiment partout ont besoin d'être véhiculés par chaque règle de production. Deuxièmement, ces contraintes cassent la modularité car le fait d'étendre une grammaire nécessite la propagation des nouveaux attributs à travers le reste du langage. Ce papier montre comment résoudre ces problèmes en introduisant un système de propagation automatique des attributs qui complète l'ensemble des règles sémantiques. Nous avons défini formellement les contraintes de propagations de manière optimisée afin d'éviter l'ajout de règles sémantiques inutiles. Ainsi les grammaires attribuées sont devenus plus maintenables, modulaires et facile à utiliser. Désambiguïsation guidée par la sémantique: Comparaison de différentes méthodes -- Renaud Durlin Modularité, extensibilité et expressivité, trois aspects fondamentaux pour un système de désambiguïsation. La désambiguïsation est l'étape survenant juste après l'analyse syntaxique qui consiste à analyser la sortie obtenue lors de l'utilisation d'un parseur LR généralisé. Le but de cette étape étant de sélectionner, parmi toute une forêt, l'unique arbre valide correspondant à l'entrée en prenant en compte les règles de sémantique contextuelles. Au travers d'une comparaison avec deux autres techniques reposant sur SDF (le formalisme ASF et le langage Stratego), le système de grammaires attribuées utilisé dans Transformers sera évalu par rapport à ces aspect fondamentaux pour en faire ressortir les avantages et inconvénients. THEORIE DES JEUX La tablette de chocolat transfinie -- Nicolas Neri Dans ce rapport technique, nous nous attardons sur le jeu de la tablette de chocolat. On dispose d'une tablette de chocolat dont le carré inférieur gauche est empoisonné. Les joueurs jouent à tour de rôle. Un coup consiste à choisir un carré de chocolat et à le manger ainsi que tous les carrés qui sont à sa droite et au dessus de lui. Le joueur qui mange le carré empoisonné perd la partie. Dans cet exposé, nous nous intéresserons particulièrement au cas où les dimensions du jeu sont de classe cardinale infinie. On présentera également, pour une meilleure compréhension, les nombres ordinaux et leur ordre associé. VERIFICATION DU LOCUTEUR Combinaison de noyaux à partir de systèmes SVM en vérification du locuteur -- Charles Alban Deledalle Les meilleurs systèmes de Verification du Locuteur (VL) sont fondés sur la fusion des scores de décision de plusieurs approches. Les méthodes basées sur les Séparateurs à Vaste Marge (SVM) donnent des résultats très performants. En conséquence, l'apport de ces méthodes est très important pour la fusion. Dans notre approche, nous proposons une nouvelle méthode de fusion des systèmes de VL basés sur les méthodes SVM en construisant une nouvelle fonction noyau à partir d'une combinaison linéaire de plusieurs fonctions. Dans cette combinaison, les poids utilisés varient selon les locuteurs, ce qui diffère des approches par fusion de score qui elles utilisent des poids universels. -- Daniela Becker

1 0

[Annonce] Special session on Lisp at ACCU 2008
by Didier Verna 08 Jan '08

08 Jan '08

Hello, I'm happy to announce that I will hold a special 90 minutes session on Lisp at the next ACCU conference, April 2008, Oxford. The abstract is given below. Performance and Genericity: the forgotten power of Lisp Lisp is one of the eldest languages around, and probably still is the most versatile of them. In our current times where there seem to be a regain of interest for dynamic and functional programming, many of those recent languages (Ruby to name one) acknowledge the fact that they were inspired by Lisp, but not quite as powerful. So why is it that so many people seem to acknowledge the power of Lisp but so few of us are actually using it? Two important reasons are that people either still think it is slow, or think that being so old, it must be dead, so they simply have forgotten all about it. The purpose of this session of twofold: first we want to remind people of the power of Lisp, and second, we want to break the myth of slowness. In a first step, we illustrate the expressive power of Lisp by showing how straightforward it is to implement binary methods, a concept otherwise difficult to reach in traditionnal OO languages. This will allow us to provide a "guided-tour" of some of the powerful features of Common Lisp: CLOS (the Object System) and its multiple-dispatch paradigm, the CLOS MOP (the Meta-Object Protocol) and it's ability to let us rewrite new, specialized, objet-systems for our own purpose, and finally the Common Lisp particular package system. In a second step, we present a recent research demonstrating that Lisp can run as fast as C, given that it is properly typed and optimized. This is done by analyzing the behavior and performance of pixel access and arithmetic operations in equivalent Lisp and C code for some simple image processing algorithms. -- Didier Verna, didier(a)lrde.epita.fr, http://www.lrde.epita.fr/~didier EPITA / LRDE, 14-16 rue Voltaire Tel.+33 (0)1 44 08 01 85 94276 Le Kremlin-Bicêtre, France Fax.+33 (0)1 53 14 59 22 didier(a)xemacs.org

1 0

[Annonce] L'air de rien 12
by Daniela Becker 07 Jan '08

07 Jan '08

Bonjour, nous avons le plaisir de vous présenter le n°12 du bulletin du LRDE. C'est un numéro spécial consacré aux deux sessions du séminaire CSI en janvier 2008 avec les résumés de toutes les présentations. Les étudiants de la promo 2008 y présenteront leur travail concluant les années passées au LRDE. Dates de séminaire à retenir : les 9 et 16 janvier 2008. Vous pouvez télécharger le bulletin en couleur à la page suivante : http://publis.lrde.epita.fr/200801-l-air-de-rien-12 -- Daniela Becker

1 0

[Annonce] [Séminaire CSI] : mercredi 09 janvier 2008
by Daniela Becker 07 Jan '08

07 Jan '08

Bonjour, Vous êtes tous cordialement invités à assister au séminaire qui aura lieu le mercredi 09 janvier 2008 à 14 heures en Amphi 2 (KB). ----------------------------------------------------------------------- Le programme : *Olena, DD, Vérification du locuteur, Théorie des Jeux & Vaucanson* http://www.lrde.epita.fr/cgi-bin/twiki/view/Publications/Seminar-2008-01-09 OLENA 14h00 : Une introduction à SCOOP, un paradigme C++ orienté objet -- Thomas Moulard DD 14h30 : Homolib -- Samuel Charron VERIFICATION DU LOCUTEUR 15h00 : SVM-MLLR et fusion pour la vérification du locuteur -- Geoffroy Querol THEORIE DES JEUX 15h45 : Étude du fictitious play dans le cas d'un jeu à fonctions d'utilité identiques -- Jean Philippe Garcia Ballester VAUCANSON 16h15 : Booster la généricité de Vaucanson -- Guillaume Lazzara 16h45 : Transducteurs synchronisés -- Guillaume Leroi ----------------------------------------------------------------------- Les Résumés des exposés : ************************** OLENA Une introduction à SCOOP, un paradigme C++ orienté objet -- Thomas Moulard Le C++ a réussi à supporter à la fois la programmation orienté objet classique et la programmation générique, cependant certains problèmes récurrents restent difficiles à résoudre. SCOOP est un paradigme orienté objet dont le but est de mélanger approche orienté objet classique et programmation générique afin d'allier élégance, sécurité et rapidité. Le paradigme fournit des méthodes virtuelles, les arguments covariants, les types virtuels et les multi-méthodes typées statiquement sans avoir besoin d'étendre le langage. SCOOP fournit également des mécanismes d'écriture de morphers qui permettent d'exprimer en C++ des fonctions de type vers type. Cette présentation fait un tour d'horizon de SCOOP en présentant d'une part le paradigme en lui-même et d'autre part son utilisation en C++ au travers d'exemples. DD Homolib -- Samuel Charron Les Diagrammes de Décision sont une famille de structures de données permettant de représenter avec peu de mémoire de grands ensembles de données. Ces structures peuvent être de taille fixe (un tuple) ou variable (une liste, un conteneur associatif, ...), la manipulation du DD ne se faisant pas de la même manière. Les Data Decision Diagrams et Set Decision Diagrams manipulent des données de taille variable grâce à des opérations, les homomorphismes. Cependant la définition d’une opération correcte peut dérouter l’utilisateur, et passe souvent par de nombreuses erreurs, difficiles à identifier. Ce séminaire propose une bibliothèque d’algorithmes fournissant une vue plus abstraite que les homomorphismes "bruts" des données manipulées, en reprenant les algorithmes définis dans les modules "List" et "Map" d’Objective Caml. L’utilisateur peut se concentrer sur les parties spécifiques à son problème. VERIFICATION DU LOCUTEUR SVM-MLLR et fusion pour la vérification du locuteur -- Geoffroy Querol Afin d'améliorer la performance globale des systèmes de vérification du locuteur, il faut diversifier les approches. Le but de ce travail est d'étudier les performances d'un système SVM-MLLR. Cette méthode se base sur la construction, à partir du modèle du monde, d'une transformation linéaire des vecteurs moyennes (mean supervectors) maximisant la vraisemblance du modèle transformé par rapport aux données locuteur. On évaluera deux approches différentes : logarithme du rapport de vraisemblance (GMM-MLLR) et utilisation des SVMs pour évaluer les scores de décision. THEORIE DES JEUX Étude du fictitious play dans le cas d'un jeu à fonctions d'utilité identiques -- Jean Philippe Garcia Ballester Le fictitious play, en théorie des jeux, est une règle d'apprentissage dans laquelle chaque joueur suppose que ses adversaires jouent une stratégie fixe (potentiellement mixte, c'est-à-dire une distribution de probabilité sur un ensemble de stratégies). À chaque tour, chaque joueur joue ainsi le meilleur coup contre la stratégie de ses adversaires, déterminée de manière empirique à partir de leurs coups précédents. La convergence de telles stratégies n'est pas assurée, mais on sait que si il y a convergence, alors les stratégies jouées correspondront statistiquement à un équilibre de Nash. Il est donc très intéressant de connaître les critères de convergence. Nous nous intéresserons pour cette présentation au cas des jeux où les fonctions d'utilité (le gain d'un joueur en fonction des stratégies jouées) de chaque joueur sont identiques. Nous étudierons d'abord des résultats de convergence dans ce cas particulier. Afin de réduire la complexité en temps, nous verrons une variante de cet algorithme, qui consiste à autoriser une erreur dans la meilleure réponse des joueurs. Nous présenterons enfin un exemple d'application du fictitious play pour résoudre un problème a priori non lié à la théorie des jeux : un problème d'optimisation, c'est-à-dire calculer le maximum des valeurs prises par une fonction. VAUCANSON Booster la généricité de Vaucanson -- Guillaume Lazzara L'architecture du projet Vaucanson a été conçue initialement autour du design pattern Element. Ce dernier a l'énorme avantage de distinguer à la fois les concepts et les implémentations. C'est à dire que pour un type d'automate comme les automates booléens, on peut théoriquement avoir plusieurs implémentations qui se côtoient dans un même programme. Malgré toutes ces précautions, aujourd'hui, ajouter une nouvelle structure s'avère très délicat et remet en cause de nombreux points au sein du projet. C'est pour cette raison que durant ce séminaire nous tenterons de répondre à ces problèmes. Les problèmes de performances qu'a pu rencontrer le projet sont également une bonne motivation pour s'attaquer à ce sujet : il est aujourd'hui indispensable de proposer des nouvelles structures plus efficaces, notamment implémentées avec la bibliothèque Boost. Transducteurs synchronisés -- Guillaume Leroi Lors de cette présentation, un algorithme de resynchronisation sera décrit ainsi que son implémentation dans Vaucanson. De plus, des explications sont données sur l'ajout des transducteurs a délai borné, ainsi que sur les difficultés qui peuvent être rencontrées lors de l'extension de la hierarchie de classes de Vaucanson. -- Daniela Becker

1 0