MASCOTTE no longer exists => visit the new project-team
Seminaire MASCOTTEPermutation and sorting networks
par J.-C. Bermond
| Date : | 22/11/11 | | Time : | 10:30 | | Location : | Galois Coriolis |
Â' 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 (ProblÃ'¨me du monde 2 envoyÃ'© cet Ã'©tÃ'©).
Page des séminaires
| 
