Un dispersor es un extractor unilateral . [1] Cuando un extractor requiere que cada evento tenga la misma probabilidad bajo la distribución uniforme y la distribución extraída, solo se requiere esta última para un dispersor. Entonces, para un dispersor, un evento tenemos:
Definición (dispersor): A -disperser es una función
tal que para cada distribución en con el apoyo de la distribución es de tamaño al menos .
Teoría de grafos
Un dispersor ( N , M , D , K , e ) es un gráfico bipartito con N vértices en el lado izquierdo, cada uno con grados D y M vértices en el lado derecho, de modo que cada subconjunto de K vértices en el lado izquierdo está conectado a más de (1 - e ) M vértices a la derecha.
Un extractor es un tipo de gráfico relacionado que garantiza una propiedad aún más sólida; cada ( N , M , D , K , e ) -extractor es también un ( N , M , D , K , e ) -disperser .
Otros significados
Un dispersor es un dispositivo de mezcla de alta velocidad que se utiliza para dispersar o disolver pigmentos y otros sólidos en un líquido.
Ver también
Referencias
- ^ Shaltiel, Ronen (2002). "Desarrollos recientes en construcciones explícitas de extractores" . Boletín de la EATCS . 77 : 67–95 . Consultado el 10 de abril de 2018 .