Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Complexité de la communication
Résumé
La complexité de la communication ou complexité de communication est une notion étudiée en informatique théorique. Le dispositif abstrait classique est le suivant : Alice et Bob ont chacun un message, et ils veulent calculer un nouveau message à partir de leurs messages, en se transmettant un minimum d'information. Par exemple, Alice et Bob reçoivent un mot chacun, et ils doivent décider s'ils ont reçu le même mot ; ils peuvent bien sûr s'envoyer leur mot l'un à l'autre et comparer, mais la question est de minimiser le nombre de messages.
Utiliser une ressources en communication est le fait d'envoyer une information à l'autre. Alice peut ainsi envoyer la première lettre de son mot à bob, ceci a un coût de 1.
La théorie de la complexité de communication a donc pour but de calculer quelles sont les ressources en communication nécessaires pour effectuer certaines tâches dans un contexte de calcul distribué. Contrairement à la théorie de la complexité classique, on ne compte pas les ressources nécessaires aux calculs (temps et espace par exemple).
Cette notion a été définie en 1979 par Andrew Yao et est utilisée notamment pour l'étude des algorithmes en ligne et le design des circuits VLSI.
Soit trois ensembles , et , et une fonction , typiquement et . Alice reçoit un élément de et Bob un élément de , et ils veulent calculer (Alice et Bob sont appelés les « joueurs »).
Un protocole qui calcule est une décomposition d'étapes. Dans chaque étape, Alice (resp. Bob) calcule en fonction de son entrée et des bits déjà échangés et décide soit de terminer car elle a fini de calculer soit d'envoyer un bit à Bob (resp. Alice). Un protocole se représente généralement sous la forme d'un arbre. Un exemple est donné ci-dessous. Les nœuds de l'arbre sont étiquetés si c'est Alice qui calcule ou si c'est Bob. Les arêtes sont étiquetées 1 si le bit envoyé vaut 1 et zéro s'il vaut zéro.
Selon les modèles, on peut accepter un protocole qui est correct seulement avec une bonne probabilité ou utilisant même des bits quantiques.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.