Bonjour, Vous êtes tous cordialement invités à assister au séminaire qui aura lieu le mercredi 23 mai 2007 à 14 heures en Amphi 2 (KB). ----------------------------------------------------------------------- Le programme : *Vaucanson, Théorie des Jeux et Parallélisme* http://www.lrde.epita.fr/cgi-bin/twiki/view/Publications/Seminar-2007-05-23 VAUCANSON 14h00 : Un format universel de description d'automates et son utilisation dans Vaucanson -- Florian Lesaint 14h30 : Boosting Vaucanson - partie 1 -- Guillaume Lazzara 15h00 : Boosting Vaucanson - partie 2 -- Jimmy Ma 15h45 : Suppression des transitions spontanées -- Vivien Delmon 16h15 : Transducteurs synchronisés -- Guillaume Leroi THEORIE DES JEUX 16h45 : Méthodes algorithmiques de recherche d'équilibres de Nash -- Antoine Leblanc PARALLELISME 17h15 : Conception d'une bibliothèque générique de parallélisation en C ++ s'appuyant sur l'existant -- Elie Bleton ----------------------------------------------------------------------- Les Résumés des exposés : ************************** VAUCANSON Un format universel de description d'automates et son utilisation dans Vaucanson -- Florian Lesaint La proposition XML présentée à CIAA 2005 (Conference on Implementation and Application of Automata) montre certaines lacunes. Le but est de finaliser la proposition d'un format universel pour la description d'automates afin de faciliter la communication entre les divers outils qui leur sont consacrés. Une seconde étape consistera à modifier VAUCANSON pour lui permettre de supporter ce format, via une réimplémentation de son parseur XML. Ce sera l'occasion de passer d'un modèle DOM à un modèle SAX, afin d'en réduire l'utilisation mémoire et espérer ainsi pallier les piètres performances de VAUCANSON. Boosting Vaucanson - partie 1 -- Guillaume Lazzara Suite aux séminaires de l'année dernière, il en ressort que les performances globales de Vaucanson pouvaient largement être améliorées par l'usage de tables de hachage et plus particulièrement celles de la bibliothèque Boost Multi Index. Pour ce séminaire, nous chercherons à tirer parti des nouvelles fonctionnalités offertes par Boost. Ceci impliquera l'apparition d'une nouvelle implémentation de graphe. L'étude de cette nouvelle implémentation ayant été réalisé indépendament de Vaucanson, nous présenterons les enjeux induits par son intégration dans Vaucanson. Boosting Vaucanson - partie 2 -- Jimmy Ma Au cours de ces séminaires, Vaucanson a été muni d'une nouvelle implémentation d'automates. Notre but étant d'évaluer l'impact de ces changements sur les performances, en particulier dans les algorithmes. Dans un premier temps, nous dresserons un bilan brut sur les nouvelles performances. Le but étant de trouver les algorithmes où les nouvelles fonctionnalités apportées ne sont pas pleinement exploitées. Dans un deuxième temps, nous fournirons une nouvelle implémentation de certains algorithmes en utilisant la nouvelle API. Enfin, nous dresserons un bilan global sur l'état actuel de Vaucanson. Enfin, nous dresserons un bilan global sur l'état actuel de Vaucanson. Suppression des transitions spontanées -- Vivien Delmon Beaucoup d'algorithmes sur les automates prennent en entrée des automates sans transitions spontanées. L'algorithme de suppression de ces dernières est donc un point central dans Vaucanson. L'implémentation actuelle de l'algorithme générique est assez rapide mais gourmande en mémoire. Une autre version proposée par Sylvain Lombardy devrait être moins gourmande et plus rapide par la même occasion. Par ailleurs, un algorithme a été publié par Mehryar Mohri des AT&T Labs et sera également mis à l'épreuve lors de ce séminaire. Ces deux algorithmes seront implémentés d'une part sur l'API actuelle de Vaucanson et d'autre part sur la future API qui devrait apporter de nouvelles fonctions grâce notamment à l'intégration d'une structure basée sur les Boost Multi Index. Transducteurs synchronisés -- Guillaume Leroi Un transducteur synchronisé est un transducteur dont les étiquettes sont des couples de lettre et les fonctions finales sont de la forme (L,1) ou (1,L) (où 1 est le mot vide et L un langage rationnel). Une opération de base dans le calcul d'un transducteur synchronisé est la circulation des sorties d'un transducteur. La circulation consiste à déplacer un mot w en arrière à travers un état. Ce mot w est un préfixe commun à toutes les étiquettes des transitions sortantes de cet état. On le supprime donc pour le rajouter en suffixe de toutes les transitions entrantes de ce même état. Cette opération de circulation est nécessaire pour permettre, par exemple, la minimisation d'un transducteur séquentiel ou la resynchronisation d'un transducteur. Ce séminaire se propose de présenter l'implémentation de ces algorithmes dans Vaucanson, ainsi que de proposer une structure de données pour les transducteurs synchronisés adaptable aux transducteurs à plus de deux bandes. THEORIE DES JEUX Méthodes algorithmiques de recherche d'équilibres de Nash -- Antoine Leblanc La théorie des jeux est généralement décrite comme une approche mathématique de problèmes de prise de décisions. Les équilibres de Nash sont l'un des principaux concepts qu'elle a introduits. Dans un jeu, un équilibre de Nash est une position dans laquelle aucun des joueurs n'a intérêt à changer sa stratégie. L'un des problèmes majeurs engendrés par ces équilibres est celui de la complexité algorithmique... Le but de cet exposé sera non seulement de faire le point sur les avantages et inconvénients des algorithmes usuels, mais également de présenter une nouvelle méthode de calcul basée sur une approche géométrique du problème. PARALLELISME Conception d'une bibliothèque générique de parallélisation en C ++ s'appuyant sur l'existant -- Elie Bleton Nous avons pour but la conception d'une bibliothèque générique de parallélisation et de distribution d'application en C++, la libpapa. Cette bibliothèque cible les développeurs souhaitant paralléliser ou répartir soit une application existante basée sur du code non modifiable, soit une nouvelle application, qui peut alors tirer le meilleur parti de la bibliothèque. La libpapa n'a pas vocation à remplacer les solutions existantes mais à fournir des abstractions de haut niveau pour le développeur. Ce séminaire abordera les solutions existantes que libpapa se propose de reprendre ou d'encapsuler, les choix faits au niveau de la modélisation de cette bibliothèque ainsi que des exemples d'utilisation possible. -- Daniela Becker