Annonce

annonce@lrde.epita.fr

1 participants
563 discussions

by Daniela Becker

Bonjour, nous avons le plaisir de vous présenter le n°15 du bulletin du LRDE. C'est un numéro Spécial Rentrée qui présente les activités de recherche, de développement et d'enseignement du LRDE ainsi que ses membres avec, d'une part le changement à la tête du labo : après plus de cinq ans Akim Demaille passe la main à Olivier Ricou. D'autre part, nous sommes heureux d'accueillir deux nouveaux permanents : Dalila Benboudjema, enseignant-chercheur, et Guillaume Lazzara, Ingénieur de Recherche. Sont présentés également plusieurs articles scientifiques qui ont été acceptés à des conférences internationales. Vous trouverez dans ce numéro également une présentation de l'option Calcul Scientifique et Image (CSI) à l'intérieur du cursus EPITA. Vous pouvez télécharger le bulletin en couleur à la page suivante : http://publis.lrde.epita.fr/200810-l-air-de-rien-15 -- Daniela Becker

16 years, 2 months

Séminaire Performance et Généricité du LRDE le 5 novembre 2008

by Akim Demaille

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 5 novembre 2008. Au programme: * Représentation efficace des données complexes dans un intergiciel schizophrène --- Thomas Quinot, AdaCore Dans un intergiciel schizophrène, une représentation intermédiaire des interactions entre composants applicatifs est construite et manipulée. Cette représentation est neutre vis-à-vis du choix d'une personnalité application (interface entre les composants et l'intergiciel) et d'une personnalité protocolaire (interface entre intergiciels distants). Elle rend possible le découplage entre ces deux aspects. Cette représentation doit préserver la structure des données associées aux interactions. Cependant, sa construction in extenso s'avère coûteuse dans le cas de données composites complexes. Cette conversion peut être économisée en remplaçant la réplication complète de la structure par la définition d'un emballage « fantôme » autour de celle-ci (et de chacun de ses composants) : il suffit que cet emballage fournisse les accesseurs permettant de parcourir la structure et de construire un message la représentant. Après avoir présenté un exemple concret de représentation neutre des données structurées, nous montrons comment cette optimisation peut être mise en oeuvre pour réaliser de manière efficace la fonction de représentation dans un intergiciel schirophrène. Nous concluons cette discussion par une évaluation du gain de performance ainsi obtenu. * Construire une application robuste sans faire exploser les coûts --- Samuel Tardieu, TELECOM ParisTech Le langage Ada est connu pour sa sûreté intrinsèque : son typage fort, ses mécanismes de contrôle de valeurs et son système d'exceptions notamment permettent d'avoir une grande confiance en les programmes. Comme dit le vieux proverbe, « En Ada, quand ça compile, ça marche ». Cependant, une des puissances d'Ada provient également de ses systèmes de vérification lors de l'exécution du programme. Par exemple, si une valeur se trouve en dehors de l'intervalle qui lui était autorisé, une exception, rattrapable par le langage, sera automatiquement levée. Ce système de vérification dynamique a bien évidemment un coût. Nous verrons comment le système de compilation GNAT mélange analyse statique et vérification lors de l'exécution pour fournir la totalité des garanties définies par le langage tout en minimisant les surcoûts et la perte de performance. 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.

16 years, 2 months

Publication: SAC'09: TWEAST: A Simple and Effective Technique to Implement Concrete-Syntax AST Rewriting Using Partial Parsing

by Roland Levillain

We are happy to announce that the following paper has been accepted for publication at the 24th Annual ACM Symposium on Applied Computing (SAC 2009) that will take place at Waikiki Beach, Honolulu, Hawaii, USA, on March 8 - 12, 2009: Akim Demaille (1), Roland Levillain (1,2), and Benoît Sigoure (1) TWEAST: A Simple and Effective Technique to Implement Concrete-Syntax AST Rewriting Using Partial Parsing http://publis.lrde.epita.fr/200903-SAC (1) EPITA Research and Development Laboratory (LRDE) (2) Université Paris-Est, LABINFO-IGM, UMR CNRS 8049, A2SI-ESIEE ASTs are commonly used to represent an input/output program in compilers and language processing tools. Many of the tasks of these tools consist in generating and rewriting ASTs. Such an approach can become tedious and hard to maintain for complex operations, namely program transformation, optimization, instrumentation, etc. On the other hand, concrete syntax provides a natural and simpler representation of programs, but it is not usually available as a direct feature of the aforementioned tools. We propose a simple technique to implement AST generation and rewriting in general purpose languages using concrete syntax. Our approach relies on extensions made in the scanner and the parser and the use of objects supporting partial parsing called Text With Embedded Abstract Syntax Trees (TWEASTS). A compiler for a simple language (Tiger) written in C++ serves as an example, featuring transformations in concrete syntax: syntactic desugaring, optimization, code instrumentation such as bounds-checking, etc. Extensions of this technique to provide a full-fledged concrete-syntax rewriting framework are presented as well. -- Roland Levillain - LRDE/EPITA - A2SI/ESIEE/UMLV-Paris Est Laboratoire de Recherche et de Développement de l'EPITA (LRDE) 14-16, rue Voltaire - FR-94276 Le Kremlin-Bicêtre Cedex - France Tél. : 01 53 14 59 45 - Fax : 01 53 14 59 22 - www.lrde.epita.fr

16 years, 2 months

Séminaire Performance et Généricité du LRDE le 24 septembre 2008

by Daniela Becker

Bonjour, 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 24 septembre 2008. Au programme: * 14h: Systèmes, algorithmes et applications : Efficacité et utilité des systèmes parallèles. Gaétan Hains, LACL, Université de Paris Est, Créteil * 15h15: Outils pour le parallèlisme : apports de la programmation générative Joël Falcou, LRI, Université de Paris-Sud, Orsay 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. -- Daniela Becker

16 years, 3 months

Publication: FSMNLP'08: An XML format proposal for the description of weighted automata, transducers, and regular expressions

by Alexandre Duret-Lutz

We are happy to announce that the following paper has been accepted for publication at the 7th International Workshop on Finite-State Methods and Natural Language Processing (FSMNLP'08) that will take place at Ispra, Italia, on September 11-12, 2008: An XML format proposal for the description of weighted automata, transducers, and regular expressions Akim Demaille (1), Alexandre Duret-Lutz (1), Florian Lesaint (1), Sylvain Lombardy (2), Jacques Sakarovitch (3), and Florent Terrones (1) (1) LRDE, EPITA (2) IGM, Univ. Marne-la-vallée (3) LTCI, CNRS/ENST http://publis.lrde.epita.fr/200809-FSMNLP We present an XML format that allows to describe a large class of finite weighted automata and transducers. Our design choices stem from our policy of making the implementation as simple as possible. This format has been tested for the communication between the modules of our automata manipulation platform Vaucanson, but this document is less an experiment report than a position paper intended to open the discussion among the community of automata software writers. -- Alexandre Duret-Lutz

16 years, 4 months

[Séminaire des étudiants CSI] : mercredi 9 juillet 2008

by Daniela Becker

Bonjour, Vous êtes tous cordialement invités à assister au séminaire qui aura lieu ce mercredi 9 juillet 2008 à 14 heures en Amphi masters au KB. ----------------------------------------------------------------------- Le programme : *Transformers et Vaucanson* http://publis.lrde.epita.fr/Seminar-2008-07-09 TRANSFORMERS 14h00 : Implémentation d’une extension du C++ dans Transformers : class namespace -- Vincent Ordy 14h30 : Centaur : Une infrastructure générique simplifiant les transformations de C++ -- Cedric Raud 15h00 : Désambiguïsation des patrons de type C++ avec les Grammaires Attribuées de Transformers -- Warren Seine VAUCANSON 15h45 : Interface graphique de Vaucanson -- Florent D'Halluin 16h15 : Amélioration de la composition des transducteurs dans Vaucanson –- Jerome Galtier ----------------------------------------------------------------------- Les Résumés des exposés : ************************** TRANSFORMERS Implémentation d’une extension du C++ dans Transformers : class namespace -- Vincent Ordy Les classes en C++ sont fermées, c’est-à-dire qu’on ne peut rien leur ajouter une fois leur définition terminée. Or, la plupart du temps, les programmeurs séparent la définition de l’implémentation, ce qui oblige à utiliser une syntaxe répétitive, en particulier dans le cas de patrons de classes ou de classes imbriquées. On se propose donc de faire une extension de la grammaire du C++ permettant via une syntaxe proche de celle des namespaces de définir plus aisément des méthodes ou attributs statiques déjà déclarés dans la définition de la classe. Dans ce but, nous utiliserons la grammaire du C++ implémentée dans Transformers, et des transformations écrites en Stratego. Centaur : Une infrastructure générique simplifiant les transformations de C++ -- Cedric Raud La grammaire du standard du C++ n’ayant pas été conçue pour etre aisément analysable, son utilisation dans le cadre de la manipulation de programme est comparable à la complexité de l’AST généré par celle-ci. Le rôle de Centaur au sein de Transformers est ainsi de fournir une infrastructure générique permettant de manipuler et de synthétiser cet AST : les transformations de programmes sont simplifiées gràce a un accès plus aisé aux informations contenues dans l’arbre syntaxique et ses annotations. Grâce à cette bibliotheque, les tâches répétitives et souvent génératrices d’erreurs, comme l’énumération des éléments d’un conteneur ou la recherche des classes parentes d’une classe, seront factorisées par un ensemble de fonctions correspondant à un modèle modulaire et extensible. 15h00 Désambiguïsation des patrons de type C++ avec les Grammaires Attribuées de Transformers -- Warren Seine Malgré sa sensibilité au contexte, le C++ est analysable avec une grammaire hors-contexte mais ambigüe. La désambiguïsation est ensuite nécéssaire pour sélectionner le seul arbre syntaxique sémantiquement valide. Transformers est une collection d’outils pour la transformation de programmes C++ qui utilise les grammaires attribuées pour réaliser cette étape. Une des plus difficiles ambiguités dans le langage concerne la métaprogrammation. Puisque du code est généré à l’instanciation, tous les types ne sont pas nécéssairement connus à la déclaration. La vérification des types est donc obligatoire pour traiter totalement le cas des patrons, ce qui pose un véritable défi. Ce rapport se concentre sur la désambiguïsation des patrons de type et détaille les problèmes et leur méthode de résolution, afin de fournir une meilleure plateforme de manipulation de sources. VAUCANSON Interface graphique de Vaucanson -- Florent D'Halluin Vaucanson est une plateforme de manipulation d’automates finis. Débuté en 2002, le projet attire de plus en plus d’utilisateurs. De ce fait, une interface utilisateur efficace est nécessaire. Pour l’utilisateur non expert, la manipulation d’automates peut s’effectuer via taf-kit, une suite d’outils accessible en ligne de commande. Une première interface graphique avait été esquissée en 2005, mais son fonctionnement était lent et compliqué car elle s’appuyait sur taf-kit pour réaliser chaque opération. Cette nouvelle interface graphique, branchée directement sur le coeur de la bibliothèque pour plus d’efficacité, simplifie la manipulation d’automates et rend accessible les algorithmes génériques de Vaucanson. Amélioration de la composition des transducteurs dans Vaucanson –- Jerome Galtier Vaucanson est une bibliothèque dont un des buts est de permettre un accès facilité à des automates et aux algorithmes qui leur sont associés. Elle met donc à notre disposition plusieurs algorithmes standard (et d’autres moins conventionnels) tels que la déterminisation, le calcul des états accessibles etc. L’un de ces algorithmes est la composition de transducteurs. Celuici n’est pas d’une nature aisée à aborder et son implémentation dans Vaucanson est perfectible. Améliorer l’implémentation d’un tel algorithme est alors un bon moyen de mettre à l’épreuve certains choix de conception dans Vaucanson. -- Daniela Becker

16 years, 5 months

CfParticipation: ELW'08, July 7, Paphos, Cyprus

by Didier Verna

+------------------------------------------------------------+ | CALL FOR PARTICIPATION | | 5th European Lisp Workshop | | July 7, Paphos, Cyprus - co-located with ECOOP 2008 | +------------------------------------------------------------+ The 5th European Lisp Workshop will be held on July 7, in Paphos, Cyprus, as part of this year's European Conference on Object-Oriented Programming (ECOOP 2008). The workshop will feature two keynote presentations: "Lisp for the 21st Century", by Mark Tarver, and "A detailed look at the Lisp Nature of Clojure", by Rich Hickey. We have also accepted four scientific papers about description logic systems, data parallelism for quantum simulation, interactive code generation, and a rant about make-method-lambda. Get all the programme details at http://elw2008.bknr.net/programme. Registration ************ Main registration is with ECOOP via the following page: https://cyprusconferences.org/ecoop08/form_ecoop.htm There is still room for attending the workshop, so if you want to participate, please contact me by email as well (didier(a)lrde.epita.fr). -- 5th European Lisp Workshop at ECOOP 2008, July 7: http://elw.bknr.net/2008/ 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

16 years, 5 months

[Séminaire des étudiants CSI] : mercredi 2 juillet 2008

by Daniela Becker

Bonjour, Vous êtes tous cordialement invités à assister au séminaire qui aura lieu le mercredi 2 juillet 2008 à 14 heures en Amphi 4 (KB). ----------------------------------------------------------------------- Le programme : *Olena, Vérification du Locuteur et Spot* http://publis.lrde.epita.fr/Seminar-2008-07-02 OLENA 14h00 : Cartes de distances -- Etienne Folio 14h30 : Les types de couleur dans Milena -- Caroline Vigouroux VÉRIFICATION DU LOCUTEUR 15h00 : Système de discriminants linéaires pour la vérification du locuteur -- Antoine Legrand SPOT 15h45 : Traduction d’une LTL étendue en TGBA dans Spot -- Damien Lefortier 16h15 : Front-end Promela dans Spot -- Guillaume Sadegh ----------------------------------------------------------------------- Les Résumés des exposés : ************************** OLENA Cartes de distances -- Etienne Folio Une carte de distances est une représentation sous forme d’image d’une fonction distance à un objet. Ces cartes sont utilisées dans de nombreuses applications, en particulier en analyse d’images de documents qui nous serviront d’illustration. Certaines méthodes de calcul de cartes moins génériques que d’autres peuvent s’avérer plus rapides : par exemple, des cartes calculées par propagation de fronts permettent de déterminer des plus courts chemins mais ne fonctionnent que lorsque le support est connu pour être non-convexe. Cette présentation fait un tour d’horizon des différents algorithmes de calculs de cartes de distances, met en évidence leurs atouts et faiblesses et explique les choix retenus. Les types de couleur dans Milena -- Caroline Vigouroux Le projet Olena fournit une bibliothèque générique pour le traitement d’images, Milena. Nous voulons que cette bibliothèque procure de nombreux types de valeur tels que l’utilisateur puisse toujours choisir le type adapté pour son application. Par exemple, nous fournissons de nombreux encodages en niveau de gris, de nombreux espaces de couleur, etc. Nous présentons la manière dont nous mettons en oeuvre les types de couleurs dans Milena. Il existe différents espaces de couleur (RGB, HSI, et bien d’autres) et il existe plusieurs encodages possibles pour les mêmes espaces de couleur (rgb_3x8, rgb_f, etc.). Nous voulons rendre les choses plus faciles pour l’utilisateur. Donc, notre objectif est de rendre possible l’utilisation des espaces de couleur sans se soucier des mécanismes internes. Par exemple, dans les formules de conversion, on ne veut pas faire apparaître les détails d’implémentation (division par 255). VÉRIFICATION DU LOCUTEUR Système de discriminants linéaires pour la vérification du locuteur -- Antoine Legrand Dans la reconnaissance du locuteur, les modèles GMM occupent une place très importante dans le développement des systèmes performants. Les méthodes de discrimination linéaire à base de SVM donnent actuellement de meilleurs résultats. On s’intéressera ici à un système de discriminant linéaire (le SVM-GLDS). Celui-ci utilise directement, sans passer par un modèle GMM, des statistiques issues de l’ensemble des paramètres de la parole pour définir le modèle de reconnaissance. On évaluera les performances d’un tel système sur la base de données NIST-SRE en le comparant avec les autres systèmes à base de SVM-GMM. SPOT Traduction d’une LTL étendue en TGBA dans Spot -- Damien Lefortier Spot repose sur l’approche automate du model checking. La bibliothèque permet de vérifier des propriétés exprimées en logique temporelle à temps linéaire (LTL) sur une modélisation d’un système représentée par un automate de Büchi généralisé basé sur les transitions (TGBA). Spot propose actuellement deux algorithmes de traduction de LTL en TGBA, une des deux étapes principales de l’approche automate. Nous présentons une nouvelle traduction en TGBA d’une logique LTL qui a été étendue en y ajoutant des opérateurs représentés par des automates finis. Cette traduction permet à Spot de vérifier des propriétés qui n’étaient pas exprimables auparavant. Front-end Promela dans Spot -- Guillaume Sadegh Spot est une bibliothèque de model checking. Pour vérifier des modèles, Spot utilise un format d’entrée représentant des automates de Büchi généralisés basés sur les transitions (TGBA). Ce format est peu pratique pour des utilisateurs, par son manque d’abstraction et par la taille des automates à représenter, souvent composés de millions d’états. Promela (Process Meta- Language) est un langage de spécification de systèmes asynchrones, utilisé par le model checker Spin. Il permet de représenter des systèmes concurrents dans un langage impératif de haut niveau. Nous allons présenter plusieurs approches pour l’ajout d’un front-end Promela dans Spot, qui devront permettre une exploration à la volée du graphe d’états, afin d’éviter de conserver en mémoire tous les états. -- Daniela Becker

16 years, 5 months

[ELW'08] Important news

by Didier Verna

Hello, here are some important news on the 5th European Lisp Workshop, July 7, Pahpos, Cyprus, co-located with ECOOP 2008: * The paper selection process is over; the final programme will be available shortly. Stay tuned for the upcoming call for participation! * We now have the abstracts for the two keynote presentations: Lisp for the 21st Century (Mark Tarver) As Lisp reaches its 50th anniversary, the talk looks at some of the reasons why Lisp has not found a wider acceptance amongst the programming community. Part of the reasons lie in a vicious cycle between education and industry within which Lisp is trapped. One solution is the L21 project - to produce a rationalized and revised update of Lisp for the C21. Qi fits many of the constraints of the L21 project. The talk concludes on what needs to be done within Qi and the Lisp world to bring Lisp to the center stage. A Detailed Look at the Lisp Nature of Clojure (Rich Hickey) The small essential core of Lisp makes dialects easy to define and implement. Most dialects are viewed skeptically by the community, as their features can be realized via the extensibility mechanisms of Scheme or Common Lisp. However, functional programming, interoperability, extensibility and concurrency objectives call for different decisions at many Lisp design points. Meeting those objectives in a Lisp dialect testifies to the continued vitality of the Lisp idea. This talk will provide a rationale for Clojure as a substantive and unique dialect of Lisp, and details of its design and implementation on the JVM. * Courtesy of EPITA, the workshop will have printed proceedings. A PDF version will also be made available on the website after the event. * Finally, please note that the official ELW website, http://elw.bknr.net, now contains an archive of all past occurrences of the workshop. -- 5th European Lisp Workshop at ECOOP 2008, July 7: http://elw.bknr.net/2008/ 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

16 years, 6 months

[Séminaire des étudiants CSI] : mercredi 25 juin 2008

by Daniela Becker

Bonjour, Vous êtes tous cordialement invités à assister au séminaire qui aura lieu le mercredi 25 juin 2008 à 14 heures en Amphi 4 (KB). Veuillez noter qu'après les étudiants, Sébastien Hémon présentera entre 16h45 et 17h45 l'article "Equilibres de Nash approchés dans les jeux multi-joueurs" de Sébastien Hémon, Miklos Santha and Michel de Rougemont présenté à SAGT 08 en mai 2008. http://www.lrde.epita.fr/cgi-bin/twiki/view/Publications/2008-01-18-SAGT ----------------------------------------------------------------------- Le programme du séminaire : *Olena et Théorie des Jeux* http://www.lrde.epita.fr/cgi-bin/twiki/view/Publications/Seminar-2008-06-25 OLENA 14h00 : Ligne de partage des eaux topologique -- Alexandre Abraham 14h30 : Taxonomie des images de Milena -- Nicolas Ballas 15h00 : Transformation des courbes de niveau rapide -- Matthieu Garrigues 15h30 : Recalage d'image rapide -- Ugo Jardonnet THEORIE DES JEUX 16h15 : Etude et implémentation du Fictitious Play alterné -- Antoine Leblanc 16h45 : Equilibres de Nash approchés dans les jeux multi-joueurs -- Sebastien Hemon et al. ----------------------------------------------------------------------- Les Résumés des exposés : ************************** OLENA Ligne de partage des eaux topologique -- Alexandre Abraham Segmenter une image consiste à en extraire les régions d’intérêt, par exemple pour séparer des cellules cancéreuses en imagerie médicale. L’approche par transformation de la ligne de partage des eaux (LPE) ou Watershed Transform permet d’obtenir une telle segmentation. Il en existe de nombreuses définitions, ainsi que diverses implémentations, dont certaines sont à la fois performantes et produisent un résultat avec de bonnes propriétés, comme le Topological Watershed. Cet exposé présentera l’implémentation d’un algorithme calculant cette LPE au sein de Milena, la bibliothèque C++ générique de traitement d’images de la plate-forme Olena, développée au LRDE. Nous nous intéresserons tout d’abord aux formats d’images “classiques”, puis à la généralisation à des formats d’images plus inhabituels (images à support de graphe généraux, etc.). Taxonomie des images de Milena -- Nicolas Ballas Milena est la bibliothèque de traitement d’images générique de la plate-forme Olena. Cette bibliothèque a pour but d’être performante tout en restant simple. L’introduction dans Milena de nouveaux types d’images basés sur des graphes a mis en évidence des problèmes de modélisation qui sont un frein pour sa généricité. Par exemple, nous avons toujours considéré que "les images ont des points". Néanmoins, certains types d’images possèdent des sites qui ne sont pas des points (mais des arrêtes, faces, ou même des ensembles de points). Une autre supposition erronée était de considérer que les sites étaient toujours localisés par un vecteur (càd, (x,y) dans le plan 2D). Cette supposition est fausse lorsque l’on manipule des sites qui ne sont pas "Pointwise". Il etait donc nécessaire de modifier les types d’images utilisés dans Milena et les propriétées qui leur sont associées. Pendant ce séminaire, nous présenterons une nouvelle classification d’images permettant de résoudre ces problèmes. Transformation des courbes de niveau rapide -- Matthieu Garrigues La transformation rapide des courbes de niveaux (FLLT) construit une représentation d’une image indépendante du contraste. Cet algorithme construit un arbre suivant les inclusions des formes. Pour un filtre, être invariant suivant le contraste est un plus. Par exemple, en analyse de document, cette représentation a le précieux avantage d’extraire facilement et rapidement les caractères indépendamment du fait qu’ils soient plus clairs ou plus foncés que leur voisinage. Ce document présente l’introduction de l’algorithme dans notre bibliothèque de traitement d’images et montre les résultats de quelques filtres connectés que peut engendrer cette représentation. Recalage d'image rapide -- Ugo Jardonnet Le recalage d’images est une technique classique en traitement d’images. Soit A et B deux images représentant le même objet (par exemple une radiographie et une image à résonance magnétique (IRM)), on calcule une transformation deAtelle que le recalage de l’objet dans A soit aligné sur l’objet dans B. Typiquement, cette technique peut permettre la lecture simultanée de deux mesures A et B. Cet exposé discutera des procédés de recalage rapide utilisés dans Milena, la bibliothèque C++ générique de traitement d’images de la plate-forme Olena, développée au LRDE. Certaines améliorations seront présentées. THEORIE DES JEUX Etude et implémentation du Fictitious Play alterné -- Antoine Leblanc Le calcul d’un équilibre de Nash dans un jeu fini est un problème démontré PPAD-complet, ce qui signifie qu’il paraît impossible de trouver une méthode de calcul efficace ; la complexité en pire cas des algorithmes usuels est 2O(n) pour un jeu de taille n. La recherche en ce domaine s’oriente donc vers le calcul d’équilibres approchés, à savoir des situations vérifiant les conditions d’un équilibre de Nash à ! près. L’algorithme du Fictitious Play s’inscrit dans cette démarche de recherche. Son principe est simple : à chaque itération, chacun des joueurs “renforce” celle de ses stratégies pures qui est la plus efficace face à ses adversaires. Pour certains jeux, cet algorithme converge vers un équilibre de Nash, fournissant ainsi un algorithme d’approximation efficace. La convergence ne peut toutefois être prouvée que pour un nombre limité de cas. Pour cette raison, il est intéressant d’étudier d’autres algorithmes basés sur le Fictitious Play, afin de trouver d’autres cas de convergence. Nous allons étudier ici le Fictitious Play alterné, dans lequel seul le joueur le plus “éloigné” de son gain optimal renforce sa stratégie la plus efficace. Equilibres de Nash approchés dans les jeux multi-joueurs -- Sebastien Hemon et al. Les équilibres de Nash sont des positions-clés de tout jeu admettant une représentation finie : en effet, quel que soit le nombre de joueurs et de stratégies, une telle position existe toujours. Lorsqu’elle est atteinte, elle dissuade tout joueur de vouloir se détourner de sa stratégie actuelle, d’où la notion d’équilibre. De nombreux problèmes y font appel mais calculer de façon effective l’équilibre demeure un problème difficile. En effet, le meilleur algorithme connu pour, dans le cas général, calculer un équilibre est exponentiel en le nombre de stratégies. Nous présenterons ici la notion d’équilibres approchés, et donnerons des résultats concernant leur calcul. Nous montrerons qu’il ne saurait exister d’algorithmes pouvant calculer un équilibre, même approché, sans utiliser au moins, pour un joueur, un nombre logarithmique de stratégies. Nous montrerons comment calculer un équilibre approché en temps sub-exponentiel nO( ln n 2 ), ce qui demeure actuellement, pour le cas général, la meilleure complexité en pire cas. Enfin, nous présenterons une approche inductive de transfert d’approximation d’une position d’un jeu à deux joueurs en une approximation pour un jeu à r joueurs, ce qui confère des résultats novateurs dans le domaine. -- Daniela Becker

16 years, 6 months

← Newer
1
...
44
45
46
47
48
49
50
...
57
Older →

Jump to page:

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

2005

2004

Annonce