Séminaire Histoire et Philosophie des Sciences :

Le 09 février 2016 à 17:30 - Amphithéâtre de Polytech, UM, campus Triolet

Présentée par Durand Arnaud - Université paris Diderot - Paris 7

Complexité algorithmique : un point de vue logique

La complexité est la discipline informatique qui mesure les ressources machines nécessaires (temps ou mémoire, par exemple) pour résoudre un problème algorithmique. Comme science mathématique, elle étudie aussi les liens entre ces mesures elles-mêmes ; résoudre certaines des questions majeures de ce domaine (comme le fameux problème P=NP) représente un défi mathématique important. On fera dans cet exposé une brève introduction aux questions et aux enjeux de la complexité. Dans la seconde partie de l'exposé, on adoptera un point de vue de logicien sur la complexité. On montrera notamment comment on peut capturer la plupart des mesures algorithmiques à travers le langage en substituant à la notion de calcul celle de « définition » logique. Ce point de vue s'est avéré particulièrement fructueux en théorie des bases de données lorsqu'il s'agit de mesurer le pouvoir d'expression des langages de requêtes, c'est-à-dire leur capacité à poser des questions « complexes » à une base de données. A travers un certain nombre d'exemples, cet exposé illustrera les liens unissant complexité et logique.