Abstract FR:

Cette these aborde des problemes de communications dans les reseaux d'interconnexion. Nous nous interessons aux protocoles qui permettent de minimiser le nombre d'etapes necessaires pour effectuer une communication. Nous supposons des messages de petite taille et nous n'autorisons ni concatenation ni decoupage des messages. Nous traitons essentiellement deux problemes. Le premier est le probleme de l'echange total en mode commutation de messages. Nous donnons un protocole en modele full-duplex, -port pour une famille de graphes de cayley possedant une rotation complete, pour laquelle la borne inferieure sur le nombre d'etapes est atteinte ; cette famille comprend le tore, l'hypercube, et le star-graph. Nous etudions egalement le cas de la grille avec un nombre de sommets impair et nous donnons en modele f*, un protocole qui permet d'effectuer un echange total en temps optimal. Le deuxieme probleme est celui de la diffusion en mode commutation de circuits, plus particulierement sur l'hypercube. Nous donnons des protocoles en modele full-duplex, -port dans l'hypercube qui utilisent la theorie des codes cycliques lineaires. Ces protocoles fournissent des bornes quasi optimales