Sujet de stage
Au cours de ce stage, nous analyserons un algorithme issu du logiciel de gestion de versions git, communément appelé git bisect.
Cet algorithme explore l'ensemble des révisions (ou commits) d'un dépôt pour rechercher la révision par laquelle un bug a été
introduit. Il applique des tests aux différentes versions, tests pouvant potentiellement être lents. Chaque test indique si oui ou non
le bug est déjà présent dans la version correspondante. Un algorithme naïf qui testerait toutes les versions trouverait à coup sûr
la révision d'introduction du bug, mais serait très coûteux en temps. Dans git bisect, seul un sous-ensemble des versions est testé,
en utilisant une heuristique inspirée de la recherche dichotomique.
Le problème d'optimisation correspondant au plus petit nombre de tests à effectuer sur un graphe générique pour trouver la
révision d'introduction du bug est réputé NP-complet. Néanmoins, les graphes provenant de versionnages de projet ont une
structure spécifique et l'algorithme git bisect semble expérimentalement performant sur ces graphes. Le but de ce stage est de
vérifier cette hypothèse et de comprendre pourquoi. En particulier, le stage consistera à :
- Proposer un modèle aléatoire de graphes de versions.
- Analyser l'espérance du nombre de tests effectués par
git bisect. - Déterminer si l'algorithme
git bisectest optimal pour l'ensemble des graphes de version. - S'il n'est pas optimal, vérifier son comportement sur le modèle aléatoire, et la distance des solutions fournies avec l'algorithme optimal.
Le cas de familles de graphes plus générales et d’autres algorithmes pourront être considérés par la suite.
Le stage sera rémunéré et s'il est concluant, pourra être poursuivi par une offre de thèse.
Mots clefs
complexité, algorithmique, complexité en moyenne, graphe aléatoire.
Avec qui ?
Avec Paul Dorbec (paul point dorbec arobase unicaen.fr) et moi-même (julien point courtiel arobase unicaen.fr). Ne pas hésiter à nous contacter !
Où ça ?
à Caen, au GREYC, dans l'équipe AMACC.