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 25 Février 2014

Combien de mémoire ?

par Pierre McKenzie (Université de Montréal, actuellement sur chaire Digiteo, LSV/ENS Cachan et LIX/Ecole Polytechnique)

La théorie de la complexité du calcul cherche à quantifier les ressources (temps, mémoire, processeurs, etc.) requises à la résolution de tâches calculatoires. Cook en 1970 demandait si tout calcul polynomial peut être réorganisé de manière à réduire exponentiellement la quantité de mémoire nécessaire au calcul. Nous étudierons cette question sous l’angle d’un modèle de calcul appelé "branching program". A l’aide de tels programmes dédiés à la tâche d’évaluer un arbre (nous préciserons ce problème), nous développerons l’intuition qu’il n’est pas possible de comprimer la mémoire. Puis nous constaterons que malgré la force de cette intuition, celle-ci ne permet toujours pas aujourd’hui de répondre à la question posée et nous devons nous contenter de bornes de complexité affaiblies. Selon le temps disponible, nous terminerons avec un bref état de l’art.

(Résultats tirés en partie de l'article de Cook, McKenzie, Wehr, Braverman, Santhanam: Pebbles and branching programs for tree evaluation, ACM TOCT 2012)

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