LRDE Seminar: 17 Mai 2006, EPITA, Amphi P004

VAUCANSON

14h00 : Remodélisation du projet Vaucanson -- Robert Bigaignon^?

Vaucanson est une bibliothèque générique de manipulation d'automates finis conçue en 2001. Son but est de permettre la manipulation efficace de n'importe quel type d'automate tout en restant fidèle au cadre algébrique établi par la théorie des automates. Ceci au prix d'une écriture parfois lourde et souvent difficile.

Aujourd'hui, nous envisageons la refonte du coeur de la bibliothèque afin de tirer parti des dernières avancées notamment en termes de programmation C++. Ainsi, nous présenterons lors de cet exposé une comparaison de techniques de modélisations appliquées à un sous-ensemble représentatif de Vaucanson.

14h30 : On m'a dit que 275 604 541 était premier -- Michael Cadilhac^?

Quand sont évoqués conjointement l'arithmétique et la cryptographie, un des premiers points communs qui vient à l'esprit se trouve dans la propriété de primalité des nombres.

La méthode la plus simple pour tester si un nombre est premier est de reprendre la définition, c'est-à-dire lister les diviseurs de ce nombre et vérifier qu'il y en a exactement 2. Mais cet algorithme naïf est extrêmement coûteux, il s'agira donc non pas de passer par la définition, mais par les propriétés des nombres premiers.

Nous présenterons un large éventail d'algorithmes de test de primalité, qu'ils soient probabilistes ou déterministes, chacun a son domaine d'utilisation. Nous étudierons des tests rapides pour petits nombres, ou pour nombres probablement premiers, aussi bien que des algorithmes généraux dont, en particulier, celui montrant que le test de primalité est dans la classe de complexité P.

15h00 : Extension du format XML -- Florent Terrones^?

Proposé lors des différentes conférences CIAA (Conference on Implementation and Application of Automata), le format XML de description d'automates présenté par l'équipe Vaucanson a pour but de permettre et faciliter le transfert des informations d'un automate entre les différents logiciels qui les manipulent. On peut en effet charger en mémoire un automate stocké dans un fichier XML et le modifier dans Vaucanson, ou au contraire sauvegarder un automate en format XML.

Mais un détail gêne encore la parfaite portabilité de ce format: les étiquettes des transitions sont pour l'instant de simples chaînes de caractères. Elles sont donc dépendantes des syntaxes utilisées par chaque logiciel, à l'instar de Vaucanson. Le but de ce séminaire est de faire le point sur les propriétés que cette extension doit satisfaire, puis d'écrire cette dernière. Enfin, certaines parties du contenu de Vaucanson seront modifiées afin de supporter ces changements.

TRANSFORMERS

15h45 : Preprocessing & Unpreprocessing du C et C++ -- Thomas Largillier^?

L'objectif du projet Transformers est de fournir des transformations de source à source pour les langages C et C++. Ces transformations se doivent d'être les plus fidèles possibles. Les directives de compilation sont omniprésentes dans des sources C/C++. L'utilisateur souhaite naturellement les retrouver après avoir transformé son fichier source.

Il est donc impossible d'utiliser les outils libres existants puisque ceux-ci ne font le travail que dans un seul sens.

Après un exposé des problèmes rencontrés dans une telle démarche, il vous sera présenté une implémentation réalisée, dans le cadre du projet Transformers, avec les outils de Stratego/XT.

16h15 : Grammaires hors-contexte et désambiguïsation -- Renaud Durlin

Les grammaires hors-contexte sont de plus en plus utilisées car elles permettent d'analyser des langages réels en utilisant un formalisme simple et naturel. De manière générale, les grammaires hors-contexte permettent de spécifier des langages ambigus.

En utilisant de telles grammaires, un analyseur syntaxique généralisé produit non pas un arbre mais une forêt de parse. La désambiguïsation consiste alors à analyser cette forêt pour obtenir l'unique arbre correspondant à l'entrée en prenant en considération les règles sémantiques contextuelles.

Nous verrons trois méthodes pour effectuer la désambiguïsation : la réécriture de termes guidée par des spécifications algébriques (ASF+SDF), l'utilisation de stratégies (Stratego/XT) et le formalisme des grammaires attribuées (Transformers). Nous discuterons des points forts et des points faibles de chacune de ces approches.

16h45 : Vectorisation automatique grâce à la transformation de programme -- Alexandre Borghi^?

La majorité des processeurs sur le marché permet de tirer parti de la vectorisation. Cependant, les langages et le code existants n'y sont pas particulièrement adaptés. Les derniers compilateurs essaient d'auto-vectoriser mais les résultats sont rarement satisfaisants.

Le C étant intrinsèquement séquentiel, il exprime un grand nombre de dépendances qui n'ont pas lieu d'être. Ceci rend difficile la vectorisation automatique. Les outils d'auto-vectorisation doivent en particulier considérer les boucles pour en extraire un maximum d'information suivant des analyses de dépendances parfois très élaborées.

Il s'agit ici de transformer un fichier source C afin de le rendre plus facilement vectorisable par les derniers compilateurs à l'aide de Transformers et des outils de transformation de programmes qu'il fournit.
to top