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 29 Novembre 2016

Programmation par formules de Horn et temps linéaire sur automates cellulaires

par Étienne Grandjean (GREYC, Caen)

Bon nombre de problèmes algorithmiques se définissent naturellement par induction: produits de polynômes ou d’entiers par la méthode de Horner, tris par échanges locaux, etc. Dans de nombreux cas aussi, on peut montrer qu’une telle induction se caractérise de façon géométrique par un ensemble fixé de vecteurs (qu’on appellera son système d’induction) qui, naturellement, fournit une méthode pour calculer les objets définis par l’induction, par un calcul local et parallèle. On en déduit un programme d’automate cellulaire pour le problème algorithmique considéré.

S’appuyant sur quelques exemples simples, l’exposé tentera de suggérer l’intuition du passage de la formule inductive (une formule de Horn) qui définit un problème algorithmique à l’automate cellulaire qui le calcule. On verra aussi que l’automate cellulaire ainsi obtenu fonctionne en temps linéaire, donc optimal.

C’est un travail en collaboration avec Nicolas Bacquey, INRIA, Lille, et Frédéric Olive, LIF, Université de Marseille).

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