| Property |
Value |
| dbo:abstract
|
- 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. (fr)
- 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. (fr)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 11307 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:année
|
- 1979 (xsd:integer)
- 2006 (xsd:integer)
- 2009 (xsd:integer)
|
| prop-fr:isbn
| |
| prop-fr:lienAuteur
|
- Andrew Yao (fr)
- Noam Nisan (fr)
- Andrew Yao (fr)
- Noam Nisan (fr)
|
| prop-fr:lieu
|
- Université Paris-Sud XI (fr)
- Université Paris-Sud XI (fr)
|
| prop-fr:lireEnLigne
| |
| prop-fr:natureOuvrage
|
- thèse de doctorat en Sciences (fr)
- thèse de doctorat en Sciences (fr)
|
| prop-fr:nom
|
- Yao (fr)
- Kaplan (fr)
- Nisan (fr)
- Kushilevitz (fr)
- Yao (fr)
- Kaplan (fr)
- Nisan (fr)
- Kushilevitz (fr)
|
| prop-fr:pagesTotales
| |
| prop-fr:passage
| |
| prop-fr:prénom
|
- Marc (fr)
- Eyal (fr)
- Noam (fr)
- Andrew Chi-Chih (fr)
- Marc (fr)
- Eyal (fr)
- Noam (fr)
- Andrew Chi-Chih (fr)
|
| prop-fr:titre
|
- Communication complexity (fr)
- Some complexity questions related to distributive computing (fr)
- Méthodes Combinatoires et Algébriques en Complexité de la Communication (fr)
- Communication complexity (fr)
- Some complexity questions related to distributive computing (fr)
- Méthodes Combinatoires et Algébriques en Complexité de la Communication (fr)
|
| prop-fr:titreOuvrage
|
- Proceedings of the eleventh annual ACM symposium on Theory of computing (fr)
- Proceedings of the eleventh annual ACM symposium on Theory of computing (fr)
|
| prop-fr:wikiPageUsesTemplate
| |
| prop-fr:éditeur
| |
| dct:subject
| |
| rdfs:comment
|
- 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. (fr)
- 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. (fr)
|
| rdfs:label
|
- Communication complexity (en)
- Complexité de la communication (fr)
- Kommunikationskomplexität (de)
- Độ phức tạp truyền thông (vi)
|
| rdfs:seeAlso
| |
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
