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
A Two-level Auction for Resource Allocation in Mul
Réseaux sans fil et mobiles
Friday 09 March 2018 - 14h30
Salle : 445 - PCRI-N
Mira Morcos .............................................

Binary pattern of length greater than 14 are abeli
Combinatoire
Friday 09 February 2018 - 14h30
Salle : 445 - PCRI-N
Matthieu Rosenfeld .............................................

Approximate Bayesian Computation and Random Forest
Thursday 08 February 2018 - 00h00
Salle : 455 - PCRI-N
Valentin Thouzeau .............................................

A concurrent lock-free algorithm for computing a f
Combinatoire
Friday 12 January 2018 - 14h30
Salle : 445 - PCRI-N
James Mitchell .............................................

Acyclic Partitioning of Large Directed Acyclic Gra
Calcul à haute performance
Tuesday 09 January 2018 - 10h30
Salle : 465 - PCRI-N
Julien Herrmann .............................................