Résumé : Pour étudier un algorithme de tri classique sur $n$ nombres réels distincts, il suffit d'étudier l'algorithme sur les antécédents de $(1,2,...,n)$, i.e. sur les $n!$ énumérations des éléments de l'ensemble $\{1,...,n\}$. L’exécution de l’algorithme sur l'ensemble de ces $n!$ énumérations permet de constater toutes les exécutions possibles de l'algorithme. Lorsque les algorithmes sont décrits à la manière des systèmes dynamiques symboliques, chaque exécution est une suite de transformations élémentaires. Afin de caractériser parmi tous les mots sur l'alphabet des transformations élémentaires, ceux qui correspondent à des traces d'exécutions, il suffit donc pour les tris classiques de considérer les traces d'exécutions sur un ensemble générique : l'ensemble des énumérations des éléments de l'ensemble $\{1,...,n\}$. Nous fournissons un cadre permettant d'exhiber de tels ensembles génériques d’entrées pour les algorithmes de recherche de séquence génératrice optimale dans une structure présentée (les tris en sont des exemples particuliers mais cela englobe aussi les algorithmes d’Euclide de Gauss et bien d'autres). Une structure présentée est une structure munie d'un squelette pour sa présentation (ou encore son codage) : un entier pour le cardinal d'une séquence génératrice et un ensemble de mots correspondants aux relateurs. Nous nous intéressons à de tels objets munis d'un préordre, lorsqu'ils possèdent beaucoup (éventuellement une infinité) de séquences génératrices. Nous considérons les algorithmes qui partant d’une séquence génératrice quelconque retournent une séquence génératrice satisfaisant certaines propriétés vis-à-vis du préordre.

Dernière modification : Monday 27 May 2024

Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr