Séminaire doctorant.e.s

Titre : Un peu d’ordre dans le BTP extraterrestre

Résumé : nous Terriens avons inventé les ponts, les tunnels, et la priorité à droite, qui nous permettent de construire des routes et des villes sans trop nous poser de questions. Mais tous les peuples de la galaxie n’ont pas eu cette idée. Comment font-ils alors pour savoir quels sont les réseaux routiers constructibles ? Sur les planètes plates ou rondes, le problème est bien connu. Mais quid des planètes en forme de tore, de bretzel ou de bouteille de Klein ? Les informaticiens proposent une solution simple, en quelques lignes, à ce problème difficile, en utilisant un peu de la théorie des ordres. La notion de beau pré-ordre permet ainsi aux extraterrestres de savoir en temps quadratique si un réseau routier est ou non constructible, et ce quelque soit la forme de leur planète. Ces beaux pré-ordres ont d’ailleurs bien d’autres applications en algèbre, en topologie et en informatique. On parlera même à la fin de leur lien avec les JO de Paris.