Disperser - Disperser

En spredning er en ensidig avtrekksmaskin . Der en ekstraktor krever at hver hendelse får samme sannsynlighet under den jevne fordelingen og den ekstraherte fordelingen, er det bare den siste som kreves for en spredning. Så for en spredning, en begivenhet vi har: ${\ displaystyle A \ subseteq \ {0,1 \} ^ {m}}$${\ displaystyle Pr_ {U_ {m}} [A]> 1- \ epsilon}$

Definisjon (Disperser): En -disperser er en funksjon${\ displaystyle (k, \ epsilon)}$

${\ displaystyle Dis: \ {0,1 \} ^ {n} \ times \ {0,1 \} ^ {d} \ rightarrow \ {0,1 \} ^ {m}}$

slik at for hver distribusjon på med støtte fra distribusjonen er minst størrelse . ${\ displaystyle X}$ ${\ displaystyle \ {0,1 \} ^ {n}}$ ${\ displaystyle H _ {\ infty} (X) \ geq k}$ ${\ displaystyle Dis (X, U_ {d})}$ ${\ displaystyle (1- \ epsilon) 2 ^ {m}}$

Grafteori

En ( N , M , D , K , e ) -disperser er en tosidig graf med N- hjørner på venstre side, hver med grad D , og M- hjørner på høyre side, slik at hver delmengde av K- hjørner på venstre side er koblet til mer enn (1 -  e ) M- hjørner til høyre.

En ekstraktor er en relatert type graf som garanterer en enda sterkere egenskap; hver ( N , M , D , K , e ) -extraktor er også en ( N , M , D , K , e ) -disperser .

Andre betydninger

En dispergerer er en høyhastighets blandeanordning som brukes til å dispergere eller oppløse pigmenter og andre faste stoffer i en væske.

Se også

• Utvid grafen

Referanser

Denne kombinatorikkrelaterte artikkelen er en stubbe . Du kan hjelpe Wikipedia ved å utvide den . v t e