Français Anglais
Accueil Annuaire Plan du site
Accueil > Evenements > Séminaires
Séminaire d'équipe(s)
Permutation and sorting networks
Jean-Claude BERMOND

23 March 2012, 16h00 - 23 March 2012, 17h00
Salle/Bat : 455/PCRI-N
Contact :

Activités de recherche :

Résumé :
(The talk will be according to the choice of the attendance in English or in French. The slides are in Français mais les figures et videos sont en English.)

Nous commencerons par exposer un problème posé par Alcatel Space Industries. Il s'agit de construire un réseau reliant des entrées (ici des signaux) à des sorties (ici des amplificateurs ou des abonnés). Le réseau est embarqué dans un satellite de télécommunications qui permet de transmettre des données (exemple Eutelsat, Astra, ...). Le réseau est formé de commutateurs (switches) avec 4 liens (guide d'ondes) et doit tolérer des pannes (soit pannes d'amplis soit blocage des commutateurs).

Plusieurs problèmes différents se posent. Nous regarderons celui ou une entrée doit être dirigée sur une sortie bien précise avec éventuellement blocage de commutateurs. Le but est de construire un réseau ayant le moins de commutateurs possibles. Nous montrerons comment modéliser le problème et qu'en fait ce problème se pose dans de nombreux autres contextes comme les réseaux de tri : on cherche a trier n nombres en utilisant des comparateurs (un comparateur prend 2 nombres en entrées et renvoie en sortie le plus grand sur le fil du haut et le plus petit sur le fil du bas). Nous donnerons des constructions récursives de bons réseaux. Nous examinerons ensuite le cas ou les commutateurs ont 3 entrées et 3 sorties et reviendrons sur les problèmes de tri avec des comparaisons des éléments 3 par 3.

En fait ceci est motivé par le problème posé dans le Monde 2 affaires de Logique du 13 Juillet 2011 :

"Du tiercé au classement général :
Neuf chevaux ont participé à la course, mais quand Bob se connecte à son site de pari, le logiciel Ordex, grippé, affiche l’ordre d’arrivée de huit d’entre eux, refusant d’annoncer la performance de Pégase, sur lequel Bob avait pourtant misé. Bob se retourne alors vers le logiciel Triplex qui lui permet, en entrant le nom de trois chevaux, de connaître l’ordre dans lequel ils sont arrivés. En combien d’essais, au maximum, connaîtra-t-il la place de Pégase ? La semaine suivante, 80 chevaux sont au départ d’une maxicourse. Quand Bob se connecte sur son site favori pour en connaître le résultat, il constate que le logiciel Ordex est définitivement hors de service, et doit se contenter de Triplex pour s’informer de l’ordre d’arrivée. En combien d’essais, au plus, Bob finira-t-il par connaître le classement général des 80 chevaux ?"

Pour en savoir plus :
Séminaires
Programmation mathématique multi-objectif pour la
Thursday 13 December 2018 - 14h30
Salle : unknown - unknown
Audrey Legendre .............................................

Redundancy in Distributed Proofs
Algorithmique distribuée
Tuesday 04 December 2018 - 00h00
Salle : 465 - PCRI-N
Ami Paz .............................................

Some recent results on the integer linear programm
Théorie des graphes
Friday 30 November 2018 - 00h00
Salle : 445 - PCRI-N
Hung Nguyen .............................................

Scalable and exhaustive screening of metabolic fun
Wednesday 28 November 2018 - 11h00
Salle : 465 - PCRI-N
Clémence Frioux .............................................

Studying the three-dimensional structure of DNA fr
Thursday 22 November 2018 - 15h00
Salle : unknown - unknown
Nelle Varoquaux .............................................