Certains logiciels de gestion de versions comme Git et Mercurial organisent l’historique d’un projet sous la forme d’un graphe orienté acyclique, les sommets représentant les différentes versions du projet et les arêtes indiquant les changements intervenus entre elles.
À l’origine, avec Paul Dorbec et Romain Lecoq (Univ. Caen Normandie), on a analysé la complexité dans le pire des cas d’un algorithme de graphes issu de Git, qui s’appelle git bisect. Cet algorithme sert à débusquer l’introduction d’un bug dans un graphe. Nous avons montré que git bisect avait une stratégie totalement catastrophique pour certains graphes particuliers. Mais qu’en est-il en moyenne ?
Derrière cette épineuse question, il faut d’abord s’interroger sur la forme typique d’un graphe représentant l’historique d’un projet dans un logiciel de gestion de versions. En théorie n’importe quel graphe acyclique peut être obtenu, mais dans la pratique, la forme de ces graphes est contrainte par des conventions de « bonne pratique ».
Je vais donc introduire une famille de graphes à la fois simples et réalistes, qu’on a appelés « graphes de Git ». Je vais alors vous présenter le problème de comptage de ces graphes, ainsi que des générateurs aléatoires. Il s’agit ici d’une collaboration avec Martin Pépin Univ. Caen Normandie.
Localisation
Salle de séminaire 4B125 (bâtiment Copernic)
5 Boulevard Descartes 77420 Champs-sur-Marne