|
Analyse théorique de l'algorithme git bisect| old_uid | 19039 |
|---|
| title | Analyse théorique de l'algorithme git bisect |
|---|
| start_date | 2021/04/27 |
|---|
| schedule | 14h |
|---|
| online | no |
|---|
| summary | Dans le royaume des logiciels de gestion de versions, git est sûrement celui qui est assis sur le trône. Ce logiciel libre et populaire dispose de nombreuses fonctionnalités très intéressantes dont notamment une, peut-être plus méconnue, qui s'appelle git bisect. Il s'agit d'un algorithme qui permet de débusquer l'origine d'un bug qui s'est introduit dans un projet. L'ensemble des historiques d'un projet formant naturellement un graphe (plus précisément un DAG), git bisect peut tout simplement se voir comme un algorithme de graphes résolvant un problème connu pour être NP-complet. Toutefois, il est surprenant de voir qu'aucune étude théorique de sa complexité n'a été menée. Paul Dorbec, Romain Lecoq et moi-même, tous trois de l'Université de Caen Normandie, proposons de rectifier cela et vérifier les bonnes performances théoriques (ou non) de git bisect. Il s'agit de travaux en cours. Cet exposé présentera ainsi les faiblesses et les forces de git bisect. Tout d'abord, nous donnerons la forme des graphes pour lesquels la stratégie de git bisect est totalement catastrophique.
Ensuite, nous montrerons que pour une certaine classe de graphes qui est représentative des graphes "issus de la vie réelle", git bisect est en fait une bonne approximation de la stratégie optimale. Enfin, nous nous interrogerons sur l'existence d'un meilleur algorithme. |
|---|
| responsibles | Laporte |
|---|
| |
|