Ent?te

Logo du LIFL

Depuis le 1er janvier 2015 le LIFL et le LAGIS forment le laboratoire CRIStAL

  1. Actualités

Colloquium polaris

Colloquium Polaris : 7ème édition

jeudi 31 mai 2012 de à

Invité:

Qu'est-ce qu'un algorithme ? Qu'est-ce qu'une fonction calculable ? Où en est-on aujourd'hui de ces deux questions posées par Turing dans son article fondateur de 1936 ? Pendant longtemps la première question a été éclipsée par le succès de la réponse à la deuxième question. Pourtant, si différents modèles de calculs permettent de calculer les mêmes choses, les façons dont ils les calculent, c'est à dire les familles d'algorithmes qui leur sont associées, ne sont pas comparable. Bien sûr, on peut émuler les algorithmes d'un modèle par ceux d'un autre, mais - traduttore, traditore - il ne s'agit pas du tout des mêmes algorithmes. Styles de programmation et complexité algorithmique en montrent des différences rédhibitoires. Existe-t-il un modèle de calcul permettant d'avoir tous les algorithmes ? Soyons plus modeste car la notion d'algorithme est très diverse: algorithmes séquentiels traditionnels, algorithmes parallèles, interactifs, analogiques, quantiques. . . Est-il déjà possible d'avoir ceux en temps séquentiel et à pas de calcul bornés ? Yuri Gurevich a montré que c'est le cas grâce à la notion d'ASM (Abstract State Machine). Nous ferons le point des travaux sur ces questions. Nous montrerons aussi comment les ASM permettent de modéliser non seulement les algorithmes mais aussi, de façon très simple, les classes d'algorithmes associés aux modèles de calcul. Comment le Lambda calcul donne aussi une solution. Enfin, nous soulignerons l'impact dans ces travaux des idées de Turing. Tout particulièrement comment l'idée d'oracle est intrinsèque à celle d'algorithme, un fait a priori éloigné de l'intuition.

En savoir plus...

Ours

UMR 8022 - Laboratoire d'Informatique Fondamentale de Lille - Copyright © 2012 Sophie TISON - Crédits & Mentions légales

Page respectant XHTML et CSS.

Pour tout commentaire / Comments and remarks : webmaster