S'authentifier
Séminaire SPACE Tours

Séminaire commun avec ROOT(LIFAT)

par Jean Charles Billaut (LIFAT, université de Tours), Andrew Elvey Price (IDP, Université de Tours)

→ Europe/Paris
E1 2100 (Tours)

E1 2100

Tours
Description

Il y aura deux exposé:



Permutoèdre (Jean-Charles Billaut)

On s'intéresse à un problème d'ordonnancement simple et très connu. On dispose de n jobs, chaque job a une durée et une date de fin souhaitée. On dispose d'une machine. Le problème consiste à séquencer les jobs de sorte à minimiser le plus grand retard algébrique. Ce problème à été résolu dans les années 50, il suffit de trier les travaux par date due croissante. On sait également que ce problème a un très grand nombre de solutions optimales. On considère maintenant que les travaux sont numérotés dans cet ordre.  Une séquence de jobs est une permutation. On se place dans le treillis des permutations. Ce treillis commence par la permutation 1234 (si n=4) (disons au niveau n-1) et se termine par 4321 au niveau 0. On cherche une solution au problème le plus bas possible dans le treillis des permutations. Cette solution permettrait de caractériser très facilement un très grand nombre de solutions optimales.



Permutations triable par des piles (Andrew Elvey Price)

Dans « The Art of Computer Programming », Knuth a abordé des permutations pouvant être triées par une pile. Il a considéré (et résolu) deux problèmes : quel sont les permutations qui peuvent être trié par une pile, et combien y a-t-il de ces permutations de chaque longueur ? Je vais d'abord parler des ces problems et leurs résolutions. Plus tard, West a défini l’application de tri par pile de manière déterministe, de sorte qu’en appliquant répétitivement cette application à une permutation de longueur n, on obtient la permutation identité après au plus n-1 étapes. Le nombre de permutations triées par k applications de cette fonction n’est connu que pour k≤2. Je présenterai des travaux sur le cas k=3, en particulier je décrirai un algorithme que nous avons utilisé pour énumérer ces permutations jusqu’à une longueur n=1000. Ce travail est en collaboration avec Colin Defant et Anthony J. Guttmann.