InforLorV4, PascalFrancis, Corpus, bibRecord, 000C70

The average-case complexity of determining the majority

Identifieur interne : 000C70 ( PascalFrancis/Corpus ); précédent : 000C69; suivant : 000C71

The average-case complexity of determining the majority

Auteurs : L. Alonso ; E. M. Reingold ; R. Schott

Source :

SIAM journal on computing [ 0097-5397 ] ; 1997.

RBID : Pascal:97-0236853

Descripteurs français

Pascal (Inist)
- Complexité calcul, Analyse algorithme, Arbre décision, Borne inférieure.

English descriptors

KwdEn :
- Algorithm analysis, Computational complexity, Decision tree, Lower bound.

Abstract

Given a set of n elements each of which is either red or blue, it is known that in the worst case n - v(n) pairwise equal/not equal color comparisons are necessary and sufficient to determine the majority color, where v(n) is the number of 1-bits in the binary representation of n. We prove that 2n/3 - √8n/9π + O(logn) such comparisons are necessary and sufficient in the average case.

Notice en format standard (ISO 2709)

Pour connaître la documentation sur le format Inist Standard.

A01	`01`	`1`		`@0 0097-5397`
A03		`1`		`@0 SIAM j. comput.`
A05				`@2 26`
A06				`@2 1`
A08	`01`	`1`	`ENG`	`@1 The average-case complexity of determining the majority`
A11	`01`	`1`		`@1 ALONSO (L.)`
A11	`02`	`1`		`@1 REINGOLD (E. M.)`
A11	`03`	`1`		`@1 SCHOTT (R.)`
A14	`01`			`@1 CRIN, INRIA-Lorraine, Université de Nancy I @2 54506 Vandoeuvre-lès-Nancy @3 FRA @Z 1 aut. @Z 3 aut.`
A14	`02`			`@1 ENS, 45 Rue d'Ulm @2 75005 Paris @3 FRA @Z 1 aut.`
A14	`03`			`@1 Department of Computer Science, University of Illinois at Urbana-Champaign, 1304 W. Springfield Avenue @2 Urbana, IL 61801 @3 USA @Z 2 aut.`
A20				`@1 1-14`
A21				`@1 1997`
A23	`01`			`@0 ENG`
A43	`01`			`@1 INIST @2 16063 @5 354000063211530010`
A44				`@0 0000 @1 © 1997 INIST-CNRS. All rights reserved.`
A45				`@0 11 ref.`
A47	`01`	`1`		`@0 97-0236853`
A60				`@1 P`
A61				`@0 A`
A64	`01`	`1`		`@0 SIAM journal on computing`
A66	`01`			`@0 USA`
C01	`01`		`ENG`	`@0 Given a set of n elements each of which is either red or blue, it is known that in the worst case n - v(n) pairwise equal/not equal color comparisons are necessary and sufficient to determine the majority color, where v(n) is the number of 1-bits in the binary representation of n. We prove that 2n/3 - √8n/9π + O(logn) such comparisons are necessary and sufficient in the average case.`
C02	`01`	`X`		`@0 001D02A05`
C03	`01`	`1`	`FRE`	`@0 Complexité calcul @3 P @5 01`
C03	`01`	`1`	`ENG`	`@0 Computational complexity @3 P @5 01`
C03	`02`	`X`	`FRE`	`@0 Analyse algorithme @5 51`
C03	`02`	`X`	`ENG`	`@0 Algorithm analysis @5 51`
C03	`02`	`X`	`SPA`	`@0 Análisis algoritmo @5 51`
C03	`03`	`X`	`FRE`	`@0 Arbre décision @5 52`
C03	`03`	`X`	`ENG`	`@0 Decision tree @5 52`
C03	`03`	`X`	`SPA`	`@0 Arbol decisión @5 52`
C03	`04`	`X`	`FRE`	`@0 Borne inférieure @5 53`
C03	`04`	`X`	`ENG`	`@0 Lower bound @5 53`
C03	`04`	`X`	`SPA`	`@0 Cota inferior @5 53`
N21				`@1 125`

Format Inist (serveur)

NO :	PASCAL 97-0236853 INIST
ET :	The average-case complexity of determining the majority
AU :	ALONSO (L.); REINGOLD (E. M.); SCHOTT (R.)
AF :	CRIN, INRIA-Lorraine, Université de Nancy I/54506 Vandoeuvre-lès-Nancy/France (1 aut., 3 aut.); ENS, 45 Rue d'Ulm/75005 Paris/France (1 aut.); Department of Computer Science, University of Illinois at Urbana-Champaign, 1304 W. Springfield Avenue/Urbana, IL 61801/Etats-Unis (2 aut.)
DT :	Publication en série; Niveau analytique
SO :	SIAM journal on computing; ISSN 0097-5397; Etats-Unis; Da. 1997; Vol. 26; No. 1; Pp. 1-14; Bibl. 11 ref.
LA :	Anglais
EA :	Given a set of n elements each of which is either red or blue, it is known that in the worst case n - v(n) pairwise equal/not equal color comparisons are necessary and sufficient to determine the majority color, where v(n) is the number of 1-bits in the binary representation of n. We prove that 2n/3 - √8n/9π + O(logn) such comparisons are necessary and sufficient in the average case.
CC :	001D02A05
FD :	Complexité calcul; Analyse algorithme; Arbre décision; Borne inférieure
ED :	Computational complexity; Algorithm analysis; Decision tree; Lower bound
SD :	Análisis algoritmo; Arbol decisión; Cota inferior
LO :	INIST-16063.354000063211530010
ID :	97-0236853

Links to Exploration step

Pascal:97-0236853

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">The average-case complexity of determining the majority</title>
<author><name sortKey="Alonso, L" sort="Alonso, L" uniqKey="Alonso L" first="L." last="Alonso">L. Alonso</name>
<affiliation><inist:fA14 i1="01"><s1>CRIN, INRIA-Lorraine, Université de Nancy I</s1>
<s2>54506 Vandoeuvre-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>3 aut.</sZ>
</inist:fA14>
</affiliation>
<affiliation><inist:fA14 i1="02"><s1>ENS, 45 Rue d'Ulm</s1>
<s2>75005 Paris</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Reingold, E M" sort="Reingold, E M" uniqKey="Reingold E" first="E. M." last="Reingold">E. M. Reingold</name>
<affiliation><inist:fA14 i1="03"><s1>Department of Computer Science, University of Illinois at Urbana-Champaign, 1304 W. Springfield Avenue</s1>
<s2>Urbana, IL 61801</s2>
<s3>USA</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Schott, R" sort="Schott, R" uniqKey="Schott R" first="R." last="Schott">R. Schott</name>
<affiliation><inist:fA14 i1="01"><s1>CRIN, INRIA-Lorraine, Université de Nancy I</s1>
<s2>54506 Vandoeuvre-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>3 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">INIST</idno>
<idno type="inist">97-0236853</idno>
<date when="1997">1997</date>
<idno type="stanalyst">PASCAL 97-0236853 INIST</idno>
<idno type="RBID">Pascal:97-0236853</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000C70</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">The average-case complexity of determining the majority</title>
<author><name sortKey="Alonso, L" sort="Alonso, L" uniqKey="Alonso L" first="L." last="Alonso">L. Alonso</name>
<affiliation><inist:fA14 i1="01"><s1>CRIN, INRIA-Lorraine, Université de Nancy I</s1>
<s2>54506 Vandoeuvre-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>3 aut.</sZ>
</inist:fA14>
</affiliation>
<affiliation><inist:fA14 i1="02"><s1>ENS, 45 Rue d'Ulm</s1>
<s2>75005 Paris</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Reingold, E M" sort="Reingold, E M" uniqKey="Reingold E" first="E. M." last="Reingold">E. M. Reingold</name>
<affiliation><inist:fA14 i1="03"><s1>Department of Computer Science, University of Illinois at Urbana-Champaign, 1304 W. Springfield Avenue</s1>
<s2>Urbana, IL 61801</s2>
<s3>USA</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Schott, R" sort="Schott, R" uniqKey="Schott R" first="R." last="Schott">R. Schott</name>
<affiliation><inist:fA14 i1="01"><s1>CRIN, INRIA-Lorraine, Université de Nancy I</s1>
<s2>54506 Vandoeuvre-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>3 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
</analytic>
<series><title level="j" type="main">SIAM journal on computing</title>
<title level="j" type="abbreviated">SIAM j. comput.</title>
<idno type="ISSN">0097-5397</idno>
<imprint><date when="1997">1997</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><title level="j" type="main">SIAM journal on computing</title>
<title level="j" type="abbreviated">SIAM j. comput.</title>
<idno type="ISSN">0097-5397</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithm analysis</term>
<term>Computational complexity</term>
<term>Decision tree</term>
<term>Lower bound</term>
</keywords>
<keywords scheme="Pascal" xml:lang="fr"><term>Complexité calcul</term>
<term>Analyse algorithme</term>
<term>Arbre décision</term>
<term>Borne inférieure</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Given a set of n elements each of which is either red or blue, it is known that in the worst case n - v(n) pairwise equal/not equal color comparisons are necessary and sufficient to determine the majority color, where v(n) is the number of 1-bits in the binary representation of n. We prove that 2n/3 - √8n/9π + O(logn) such comparisons are necessary and sufficient in the average case.</div>
</front>
</TEI>
<inist><standard h6="B"><pA><fA01 i1="01" i2="1"><s0>0097-5397</s0>
</fA01>
<fA03 i2="1"><s0>SIAM j. comput.</s0>
</fA03>
<fA05><s2>26</s2>
</fA05>
<fA06><s2>1</s2>
</fA06>
<fA08 i1="01" i2="1" l="ENG"><s1>The average-case complexity of determining the majority</s1>
</fA08>
<fA11 i1="01" i2="1"><s1>ALONSO (L.)</s1>
</fA11>
<fA11 i1="02" i2="1"><s1>REINGOLD (E. M.)</s1>
</fA11>
<fA11 i1="03" i2="1"><s1>SCHOTT (R.)</s1>
</fA11>
<fA14 i1="01"><s1>CRIN, INRIA-Lorraine, Université de Nancy I</s1>
<s2>54506 Vandoeuvre-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>3 aut.</sZ>
</fA14>
<fA14 i1="02"><s1>ENS, 45 Rue d'Ulm</s1>
<s2>75005 Paris</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</fA14>
<fA14 i1="03"><s1>Department of Computer Science, University of Illinois at Urbana-Champaign, 1304 W. Springfield Avenue</s1>
<s2>Urbana, IL 61801</s2>
<s3>USA</s3>
<sZ>2 aut.</sZ>
</fA14>
<fA20><s1>1-14</s1>
</fA20>
<fA21><s1>1997</s1>
</fA21>
<fA23 i1="01"><s0>ENG</s0>
</fA23>
<fA43 i1="01"><s1>INIST</s1>
<s2>16063</s2>
<s5>354000063211530010</s5>
</fA43>
<fA44><s0>0000</s0>
<s1>© 1997 INIST-CNRS. All rights reserved.</s1>
</fA44>
<fA45><s0>11 ref.</s0>
</fA45>
<fA47 i1="01" i2="1"><s0>97-0236853</s0>
</fA47>
<fA60><s1>P</s1>
</fA60>
<fA61><s0>A</s0>
</fA61>
<fA64 i1="01" i2="1"><s0>SIAM journal on computing</s0>
</fA64>
<fA66 i1="01"><s0>USA</s0>
</fA66>
<fC01 i1="01" l="ENG"><s0>Given a set of n elements each of which is either red or blue, it is known that in the worst case n - v(n) pairwise equal/not equal color comparisons are necessary and sufficient to determine the majority color, where v(n) is the number of 1-bits in the binary representation of n. We prove that 2n/3 - √8n/9π + O(logn) such comparisons are necessary and sufficient in the average case.</s0>
</fC01>
<fC02 i1="01" i2="X"><s0>001D02A05</s0>
</fC02>
<fC03 i1="01" i2="1" l="FRE"><s0>Complexité calcul</s0>
<s3>P</s3>
<s5>01</s5>
</fC03>
<fC03 i1="01" i2="1" l="ENG"><s0>Computational complexity</s0>
<s3>P</s3>
<s5>01</s5>
</fC03>
<fC03 i1="02" i2="X" l="FRE"><s0>Analyse algorithme</s0>
<s5>51</s5>
</fC03>
<fC03 i1="02" i2="X" l="ENG"><s0>Algorithm analysis</s0>
<s5>51</s5>
</fC03>
<fC03 i1="02" i2="X" l="SPA"><s0>Análisis algoritmo</s0>
<s5>51</s5>
</fC03>
<fC03 i1="03" i2="X" l="FRE"><s0>Arbre décision</s0>
<s5>52</s5>
</fC03>
<fC03 i1="03" i2="X" l="ENG"><s0>Decision tree</s0>
<s5>52</s5>
</fC03>
<fC03 i1="03" i2="X" l="SPA"><s0>Arbol decisión</s0>
<s5>52</s5>
</fC03>
<fC03 i1="04" i2="X" l="FRE"><s0>Borne inférieure</s0>
<s5>53</s5>
</fC03>
<fC03 i1="04" i2="X" l="ENG"><s0>Lower bound</s0>
<s5>53</s5>
</fC03>
<fC03 i1="04" i2="X" l="SPA"><s0>Cota inferior</s0>
<s5>53</s5>
</fC03>
<fN21><s1>125</s1>
</fN21>
</pA>
</standard>
<server><NO>PASCAL 97-0236853 INIST</NO>
<ET>The average-case complexity of determining the majority</ET>
<AU>ALONSO (L.); REINGOLD (E. M.); SCHOTT (R.)</AU>
<AF>CRIN, INRIA-Lorraine, Université de Nancy I/54506 Vandoeuvre-lès-Nancy/France (1 aut., 3 aut.); ENS, 45 Rue d'Ulm/75005 Paris/France (1 aut.); Department of Computer Science, University of Illinois at Urbana-Champaign, 1304 W. Springfield Avenue/Urbana, IL 61801/Etats-Unis (2 aut.)</AF>
<DT>Publication en série; Niveau analytique</DT>
<SO>SIAM journal on computing; ISSN 0097-5397; Etats-Unis; Da. 1997; Vol. 26; No. 1; Pp. 1-14; Bibl. 11 ref.</SO>
<LA>Anglais</LA>
<EA>Given a set of n elements each of which is either red or blue, it is known that in the worst case n - v(n) pairwise equal/not equal color comparisons are necessary and sufficient to determine the majority color, where v(n) is the number of 1-bits in the binary representation of n. We prove that 2n/3 - √8n/9π + O(logn) such comparisons are necessary and sufficient in the average case.</EA>
<CC>001D02A05</CC>
<FD>Complexité calcul; Analyse algorithme; Arbre décision; Borne inférieure</FD>
<ED>Computational complexity; Algorithm analysis; Decision tree; Lower bound</ED>
<SD>Análisis algoritmo; Arbol decisión; Cota inferior</SD>
<LO>INIST-16063.354000063211530010</LO>
<ID>97-0236853</ID>
</server>
</inist>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/PascalFrancis/Corpus

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000C70 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/PascalFrancis/Corpus/biblio.hfd -nk 000C70 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    PascalFrancis
   |étape=   Corpus
   |type=    RBID
   |clé=     Pascal:97-0236853
   |texte=   The average-case complexity of determining the majority
}}

This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022

	Serveur d'exploration sur la recherche en informatique en Lorraine
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur la recherche en informatique en Lorraine

The average-case complexity of determining the majority

The average-case complexity of determining the majority

Source :

Descripteurs français

English descriptors

Abstract

Notice en format standard (ISO 2709)

Format Inist (serveur)

Links to Exploration step

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri