Romain Lecoq (GREYC, Caen)

Au cours de cette présentation, nous allons étudier le problème de recherche de régression.

On modélise un dépôt de projet issu d’un logiciel de gestion de versions (notamment git) par un graphe orienté acyclique (DAG). Chaque sommet correspond à une version, et les arêtes représentent les modifications d’une version à une autre. Dans le problème de recherche de régression, on suppose qu’une version du dépôt comporte un bug qui s’est propagé aux versions ultérieures. On souhaite avec un nombre minimum de requêtes (tests sur une version) identifier de façon sûre la version qui introduit le bug.

Le problème est réputé NP-complet, mais en pratique un algorithme polynomial appelé git bisect est couramment utilisé dans le logiciel git. Nous étudions les performances de cet algorithme dans le pire des cas et nous proposons un nouvel algorithme avec de meilleures garanties sur le pire cas, au nom mystérieux de golden bisect.

Cet exposé sera l’occasion de lever le mystère !