BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//CERN//INDICO//EN
BEGIN:VEVENT
SUMMARY:Séminaire commun avec ROOT(LIFAT)
DTSTART:20260410T083000Z
DTEND:20260410T095000Z
DTSTAMP:20260411T124000Z
UID:indico-event-16104@indico.math.cnrs.fr
DESCRIPTION:Speakers: Andrew Elvey Price (IDP\, Université de Tours)\, Je
 an Charles Billaut (LIFAT\, université de Tours)\n\nIl y aura deux expos
 é:\nPermutoèdre (Jean-Charles Billaut)\n\nOn s'intéresse à un problèm
 e d'ordonnancement simple et très connu. On dispose de n jobs\, chaque jo
 b 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 g
 rand 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 égalem
 ent que ce problème a un très grand nombre de solutions optimales. On co
 nsidè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 pe
 rmutations. 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. Cett
 e solution permettrait de caractériser très facilement un très grand no
 mbre de solutions optimales.Permutations triable par des piles (Andrew Elv
 ey Price)\n\nDans « 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 tr
 ié par une pile\, et combien y a-t-il de ces permutations de chaque longu
 eur ? 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étermi
 niste\, 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 trava
 ux sur le cas k=3\, en particulier je décrirai un algorithme que nous avo
 ns utilisé pour énumérer ces permutations jusqu’à une longueur n=100
 0. Ce travail est en collaboration avec Colin Defant et Anthony J. Guttman
 n.\n\nhttps://indico.math.cnrs.fr/event/16104/
LOCATION:E1 2100 (Tours)
URL:https://indico.math.cnrs.fr/event/16104/
END:VEVENT
END:VCALENDAR