En donnant quelques mots en entrée à votre moteur de recherche, celui-ci renvoie une immense quantité de pages internet pertinentes. Produire ainsi de nombreuses réponses à partir d’une simple entrée, c’est le domaine des algorithmes d’énumération que nous présentons ici. C’est un peu le contraire de l’apprentissage en intelligence artificielle (IA) qui utilise d’énormes masses de données en entrée, typiquement des millions de photos annotées, pour ensuite être capable de répondre à une question comme “est-ce que cette photo représente un chat ?”. Nous allons d’abord donner quelques exemples pour illustrer le concept de problèmes d’énumération et son intérêt. La plupart de ces exemples sont modélisés par des graphes, car ce sont des problèmes simples et facilement visualisables, mais on rencontre aussi énormément de problèmes d’énumération dans les bases de données, en logique, en bio-informatique, en cryptographie…

Interstices est une revue de culture scientifique en ligne, créée par des scientifiques pour vous inviter à explorer les sciences du numérique.

Interstices est publiée par Inria, institut national de recherche en sciences et technologies du numérique, elle a été lancée en 2004 à son initiative. Le suivi scientifique de la revue est assuré par le comité éditorial, qui rassemble des personnes d’Inria, du CNRS, de plusieurs universités ainsi que des associations professionnelles du domaine, notamment la SIF et la SMAI.