Le problème de la recherche d’une séquence génératrice optimale d’une structure présentée

Il s’agit d’un essai pour unifier l’analyse d’algorithmes a priori aussi différent que des algorithmes de tris, d’Euclide, de réduction de réseaux. Dans la modélisation proposée, inspirée des systèmes dynamiques, les algorithmes sont itératifs, prennent comme entrée une séquence génératrice et retournent une séquence génératrice optimale. A chaque étape une transformation élémentaire est appliquée à la donnée. Ainsi une trace d’exécution est un mot sur l’alphabet des transformations élémentaires. Par analyser un algorithme, nous entendons ici répondre au problème réciproque, i.e. caractériser les traces d’exécution. Nous les caractérisons ici comme les formes normales d’un système de réécritue sur les mots construits sur l’alphabet des transformations élémentaires.