Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 24 Avril 2007

Le problème de la recherche d'une séquence génératrice optimale d'une structure présentée

par Ali Akhavi (LIAFA, GREYC)

Il s'agit d'un essai pour unifier l'analyse d'algorithmes a priori aussi différent que des algorithmes de tris, d'Euclide, de réduction de réseaux. Dans la modélisation proposée, inspirée des systèmes dynamiques, les algorithmes sont itératifs, prennent comme entrée une séquence génératrice et retournent une séquence génératrice optimale. A chaque étape une transformation élémentaire est appliquée à la donnée. Ainsi une trace d'exécution est un mot sur l'alphabet des transformations élémentaires. Par analyser un algorithme, nous entendons ici répondre au problème réciproque, i.e. caractériser les traces d'exécution. Nous les caractérisons ici comme les formes normales d'un système de réécritue sur les mots construits sur l'alphabet des transformations élémentaires.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr