Complexité implicite

L’analyse de la complexité des programmes permet de donner des garanties sur l’exécution des programmes en temps limité et espace mémoire borné. Cette discipline a des applications par exemple pour la validation de programmes sur smartphones ou de code embarqué. Tandis que la théorie de la complexité utilise des machines comme modèle de base (machines de Turing, modèle RAM), la complexité implicite s’attache à caractériser les classes de complexité sans recourir à ces modèles de bas niveau. Elle permet par exemple d’obtenir des caractérisations des fonctions calculées en temps ou espace polynomial en utilisant des outils d’analyse statique. Elle peut ainsi s’appliquer à différents paradigmes de programmation (fonctionnel, impératif, objet…) pour produire des certificats de complexité sur des programmes réels.

L’objectif de ce cours est de présenter la notion de complexité implicite dans le cadre des systèmes complexes.