La théorie de la complexité algorithmique est née il y a plus de 50 ans de la volonté de comprendre ce qu’il était possible de calculer efficacement. La tâche de classification des problèmes/fonctions selon la quantité de ressources (e.g. temps et/ou espace) nécessaires pour les résoudre/calculer s'est avéré être une question extrêmement difficile. Cette difficulté a conduit au développement d’une grande variété d'approches distinctes.

Il est apparu que les développements à venir de la théorie de la complexité nécessiteront une compréhension fine des similitudes,
différences et limites des nombreuses approches actuelles. En effet, bien qu’elles étudient le même phénomène, celles-ci se développent aujourd'hui au sein de communautés disjointes, avec peu ou pas de communication entre elles (algorithmes, logique, théorie de la programmation, algèbre, etc.). Cette dispersion est regrettable car elle entrave le développement de méthodes hybrides et plus généralement l'avancement de la complexité algorithmique dans son ensemble.

L’objectif (et la particularité) de l’école Caleidoscope est de réunir en un seul événement plusieurs approches différentes de la complexité algorithmique; autant qu’il est raisonnable de programmer en une semaine. Cette école est à la fois destinée aux étudiants et aux chercheurs confirmés qui souhaitent s’initier aux autres approches du sujet.

Responsable(s) du colloque :

Anupam Das (U. Copenhagen), Arnaud Durand (U. Paris 7), Damiano Mazza (CNRS & U. Paris 13), Thomas Seiller (CNRS & U. Paris 13).

Plus d'informations