La tendance actuelle est d’encourager les chercheurs \u00e0 faire beaucoup de publications et \u00e0 \u00e9valuer les chercheurs et les laboratoires sur la base du nombre de leurs publications en revues et conf\u00e9rences avec comit\u00e9s de lecture. En cons\u00e9quence, une contribution ayant une tr\u00e8s grande port\u00e9e scientifique publi\u00e9e dans un article de Workshop sera consid\u00e9r\u00e9e comme moins importante qu’une contribution de moins grande port\u00e9e, mais publi\u00e9e en revue. D’autres crit\u00e8res sont parfois aussi mis en avant, comme le nombre de fois o\u00f9 ces publications sont cit\u00e9es dans la litt\u00e9rature scientifique, mais toujours dans l’esprit de chiffrer les performances des chercheurs.\u00a0Un autre d\u00e9faut du syst\u00e8me est qu’il est difficile de savoir quelle est la contribution de chaque auteur dans un article publi\u00e9 par plusieurs chercheurs…<\/p>\n
Si vous vous int\u00e9ressez \u00e0 mes publications, vous pouvez les consulter via ces liens :<\/p>\n
Ce que je souhaite mettre en avant ici, ce sont mes principales contributions scientifiques, parce que le contenu me parait plus important que le contenant.<\/p>\n
Dans ma th\u00e8se, je propose des algorithmes permettant un \u00e9chantillonnage statistique uniforme de diff\u00e9rentes strates des paysages de recherche, c’est \u00e0 dire le tirage al\u00e9atoire d’assignations satisfaisant un nombre donn\u00e9 de clauses (toutes les clauses dans le cas limite de l’\u00e9chantillonnage des solutions). Mes algorithmes permettent \u00e9galement de mesurer la r\u00e9partition des assignations et des extremums locaux en fonction du nombre de clauses satisfaites. Ces outils ont pour vocation la r\u00e9alisation de mesures dans le cadre de l’\u00e9tude des algorithmes de recherches locale stochastique.<\/p>\n
En 1998, j’ai trouv\u00e9 une m\u00e9thode permettant d’utiliser un processus de recherche locale stochastique pour r\u00e9aliser une estimation non biais\u00e9e du nombre de solution d’un probl\u00e8me.<\/p>\n
J’ai co-encadr\u00e9 avec Jean-Jacques Chabrier la th\u00e8se d’Alain Sidaner, intitul\u00e9e \u00ab\u00a0Contribution \u00e0 l’\u00e9tude de l’algorithme de recherche locale stochastique WalkSAT sur des instances SAT al\u00e9atoires\u00a0\u00bb. Outre l’encadrement scientifique, une de mes contributions \u00e0 ce travail est l’id\u00e9e d’une m\u00e9trique et d’un algorithme efficace pour mesurer la dispersion spatiale des processus de recherche locale. Ces outils ont \u00e9t\u00e9 utilis\u00e9s par Alain Sidaner pour l’\u00e9tude des phases d’intensification et de diversification d’un algorithme de recherche locale stochastique appel\u00e9 WalkSat.<\/p>\n
J’ai introduit au cours de mes ann\u00e9es de doctorat une technique de production d’instances de probl\u00e8mes difficiles pour un algorithme donn\u00e9, bas\u00e9e sur l’utilisation de la recherche locale stochastique pour faire \u00e9voluer des instances du probl\u00e8me avec comme fonction objectif le temps de r\u00e9solution par l’algorithme cibl\u00e9. Cette technique peut \u00eatre utilis\u00e9e pour des mesures de robustesse de solveurs de probl\u00e8mes NP-difficiles.<\/p>\n
En 1999, j\u2019ai d\u00e9couvert un nouveau probl\u00e8me NP-complet qui pouvait facilement se d\u00e9composer, en faisant varier la valeur d\u2019un param\u00e8tre entier, en une collection in\u001cnie de probl\u00e8mes de complexit\u00e9 en temps lin\u00e9aire. Avec Pierre Marquis, nous avons \u00e9tudi\u00e9 la complexit\u00e9 de ce probl\u00e8me, que nous avons appel\u00e9 distance-sat, et de certaines variantes. Parall\u00e8lement, j\u2019ai propos\u00e9 un algorithme efficace pour la r\u00e9solution de ce probl\u00e8me.<\/p>\n
En 2001, j\u2019ai propos\u00e9 \u00e0 Emmanuel Sapin un sujet de th\u00e8se un peu ambitieux : la recherche par algorithmes \u00e9volutionnaire d\u2019automates cellulaires capables de r\u00e9aliser des calculs (par exemple par simulation de portes logiques), voire d\u2019automates ayant, \u00e0 l\u2019instar du jeux de la vie, la puissance d\u2019expression de la machine de Turing. Ce travail, que j’ai co-dirig\u00e9 avec Jean-Jaques Chabrier, \u00e0 donn\u00e9 lieu notamment \u00e0 la d\u00e9couverte d\u2019une plusieurs automates cellulaires calculateurs universels.<\/p>\n
En 2003, j’ai d\u00e9couvert un syst\u00e8me de codage de contraintes Bool\u00e9ennes de cardinalit\u00e9 en clauses propositionnelles (formule sous forme CNF) permettant \u00e0 la propagation unitaire de restaurer la consistance d’arcs. Valid\u00e9 et exp\u00e9riment\u00e9 en collaboration avec Yacine Boufkhad, ce codage a permis d’am\u00e9liorer l’efficacit\u00e9 de la r\u00e9solution par des solveurs SAT de probl\u00e8mes comportant des contraintes Bool\u00e9ennes de cardinalit\u00e9.<\/p>\n
En 2006, j’ai propos\u00e9 un codage sous forme CNF de contraintes pseudo-Bool\u00e9ennes qui permet \u00e0 la propagation unitaire, appliqu\u00e9e sur les clauses produites, de r\u00e9aliser les m\u00eames d\u00e9ductions que la restauration de la consistance d’arc sur les contraintes initiales. Ce codage a \u00e9t\u00e9 d\u00e9velopp\u00e9, valid\u00e9, et sa complexit\u00e9 a \u00e9t\u00e9 \u00e9tudi\u00e9e en collaboration avec Olivier Roussel et Yacine Boufkhad. Il a pour principal d\u00e9faut de produire, dans le pire des cas, un nombre de clauses exponentiel en fonction de la taille de la contrainte \u00e0 traduire.<\/p>\n
En 2009, j’ai d\u00e9couvert un codage sous forme CNF de contraintes pseudo-Bool\u00e9ennes ayant les m\u00eames propri\u00e9t\u00e9s, en terme de puissance de propagation, que celui de 2006 pr\u00e9c\u00e9demment mentionn\u00e9, mais avec une complexit\u00e9 polynomiale dans le pire des cas. Ce codage a \u00e9t\u00e9 valid\u00e9 et exp\u00e9riment\u00e9 en collaboration avec Olivier Roussel et Yacine Boufkhad, qui a par ailleurs propos\u00e9 une variante n\u00e9cessitant beaucoup moins de clause en contre partie d’une puissance de propagation plus faible.<\/p>\n