CAPP - Calculs algorithmes programmes et preuves

Les recherches sur les modèles de calcul conduisent souvent à des développements théoriques concernant l’étude des propriétés de ces modèles.

Ces études passent par l’élaboration de notations, de langages et de divers outils dédiés aux calculs comme leurs représentations, l’évaluation de leurs complexités, l’analyse de leurs comportements ou encore la vérification de leurs validités. Elles construisent des artéfacts logiciels ou matériel qui mettent en œuvre ou simulent ces calculs, puis elles les appliquent à des problèmes concrets qui tirent parti des spécificités de tel ou tel modèle.

Ces recherches sont toujours dominées par les modèles de calcul classiques (au sens de la physique classique Newtonienne et par opposition à la physique quantique) tels que la machine de Turing, la logique classique et le lambda-calcul.

En plus de ces fondements classiques, où il y a encore beaucoup à creuser, les recherches sur les modèles de calcul explorent aussi des modèles "non-classiques", issus de disciplines autres que l’informatique, telles la physique ou la biologie moléculaire.

On rencontre, dans ces domaines, des objets et des processus dont les propriétés sont intéressantes pour la représentation, le traitement et la communication de l’information. Par exemple, en algorithmique, certains de ces objets ou processus brisent des barrières de complexité érigées par l’informatique classique ; ils élargissent, ainsi, le territoire du "raisonnablement calculable".

L’équipe CAPP a pour ambition d’être un foyer où s’élaborent et s’étudient des modèles de calcul, classiques et non-classiques, avec trois domaines d’investigation privilégiés : l’algorithmique, la programmation et la preuve.