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 12 Janvier 2016

Le problème du tri généralisé, un point de vue symbolique à propos des algorithmes réversibles

par Ali Akhavi (GREYC, Caen)

Nous présentons un cadre pour associer de manière originale et naturelle, un algorithme à un ensemble de règles de réécriture. Ici un algorithme est identifié avec l'ensemble de ses traces d'exécution. Les systèmes de réécriture sont définis sur les séquences de transformations élémentaires et sont tels que leurs formes normales sont exactement les traces d'exécution.

Les algorithmes que nous considérons sont ceux qui cherchent à résoudre une classe de problèmes que nous introduisons sous le nom des problèmes de tri généralisé. Il s'agit de la recherche d'une séquence génératrice particulière pour une algèbre présentée. Sous des hypothèses raisonnables, nous montrons que les traces d'exécution de ces algorithmes sont des diagrammes (i.e., graphes orientés et arc-colorés) couvrants des diagrammes de Cayley du groupe des automorphismes de l'algèbre présentée associé à l'algorithme (et donc des systèmes de réécriture).

En utilisant le formalisme des ASM introduit par Gurevich, nous montrons que tout algorithme qui est réversible (i.e., qui ne perd pas d'information durant une exécution) et qui s'arrête toujours, résout un problème de tri généralisé. Notre approche permet de relier dans les cas très simples une borne inférieure de complexité au diamètre d'un graphe de Cayley.

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