Conozco algunas formas, siempre que esté bien, introduciendo un margen de error en la representación o confiando en las probabilidades estadísticas.
En un ejemplo simple, suponga que tiene una aplicación de conteo que tiene 2 bits de memoria con posibles estados {00, 01, 10 y 11}. Una aplicación de conteo tradicional puede incrementar un poco de memoria cada tick de “conteo”, lo que da como resultado estados potenciales 1, 2, 3 y 4 antes de quedarse sin memoria.
Supongamos, en cambio, que su aplicación solo tiene un 10% de posibilidades de aumentar un poco en la memoria cada tick “contando”, por lo que, en promedio, tomará diez ticks antes de 00 transiciones a 01, otras diez antes de que 01 incremente a 10, y otros diez antes de 10 incrementos a 11. Esto se traduce en el estado 00 que representa estadísticamente los valores 0-10 (para tamaños de muestra grandes), el estado 01 representa los valores 10-20, 10 representa 20-30 y el estado 11 representa 30- 40 antes de que se nos acabe la memoria nuevamente. Esto da como resultado 2 bits de memoria que representan 40 estados.
- ¿Cómo podría uno enseñar la administración del sistema a alguien que nunca antes ha usado una computadora?
- ¿Es completo un sistema computacional de Turing si y solo si no se puede detener-decidir?
- ¿Herman Cain entiende conceptos como la abstracción, el almacenamiento en caché, etc. ya que tiene un título en informática?
- Cómo formatear una tarjeta SD protegida contra escritura
- Cómo obtener un bajo uso de CPU en un servicio de alojamiento gratuito como un servidor web en cpanel
Por supuesto, puede extender esto de cualquier manera (más bits, o menos posibilidades de aumentar) para representar aún más estados. Por ejemplo, una probabilidad del 1% de aumentar representa una extensión de 400 estados potenciales (con márgenes de error que disminuyen a medida que agrega más bits de representación o tiene un mayor número de pruebas), y una probabilidad del 0.1% que representa 4,000 estados, y así sucesivamente .
Otro enfoque que puede tomar es usar códigos de identificación y no permitir falsos negativos mientras permite falsos positivos. Esto le permite representar 2 ^ 2 ^ n estados con n bits [1] con márgenes de error mínimos que tienden a cero a medida que n crece.
Para un ejemplo concreto, suponga que ejecuta una lista de correo de elogio. Dado que no permite falsos negativos, garantiza que si el cónyuge de un suscriptor muere, recibirá un correo electrónico informándole. Sin embargo, dado que permite falsos positivos, los suscriptores saben que tienen un poco de trabajo por su parte para verificar la veracidad de la notificación (ya que su cónyuge puede no estar realmente muerto si recibe una notificación, pero se garantiza que no está muerto si no lo hace ‘t).
Esto significa que puede permitir colisiones de identificación entre suscriptores y representar múltiples estados (la muerte del cónyuge de Alice versus la muerte del cónyuge de Bob) bajo la misma secuencia de bits. En este escenario, puede usar códigos de identificación no únicos para esas secuencias de bits.
Para ver esto en acción, suponga que le estamos dando a cada suscriptor dos códigos separados de 3 dígitos que, cuando cualquiera de los dos está presente en el boletín de elogios, debe representar la posible muerte de su cónyuge (y, por lo tanto, la falta de este debe representar la garantía no muerte de su cónyuge). El documento vinculado anteriormente describe un enfoque para diseñar una serie de conjuntos distintos dados n bits (con muchas matemáticas que no pertenecen aquí), pero con tres bits y dos códigos de tres dígitos dados por suscriptor, podemos manejar hasta 29 suscriptores con solo un 50% de tasa de falsos positivos por código de bit (que tiende a la baja a medida que aumenta el número de bits disponibles).
Entonces, vemos que los primeros siete suscriptores (2 ^ n – 1) obtienen un código de identificación común 000, mientras que cada uno obtiene adicionalmente cada permutación de bits en los tres bits restantes como su código secundario (por ejemplo, {001, 010, 011, … 111} ) En los siguientes seis suscriptores (2 ^ n – 2), seguimos un patrón similar de darles un código de identificación común 001, al tiempo que asignamos las permutaciones de bits restantes de 010 a 111; y así sucesivamente hasta el suscriptor final (2 ^ n – 7) a quien se le asignan los dos códigos finales 110 y 111. Lo que finalmente resulta es que cada suscriptor tenga dos códigos de tres bits y cada código de tres bits que represente a siete suscriptores ( a la capacidad de la lista).
Con esa configuración, puede asumir que el cónyuge de nuestro primer suscriptor muere para verlo en acción. En este caso, sus códigos de bits asignados son 000 y 001. Elegimos uno al azar (según el documento) y publicamos ese código en la lista de correo. Independientemente del código que elijamos (al azar), los siguientes hechos son ciertos:
- Nuestro primer suscriptor recibirá un aviso de que su cónyuge ha fallecido
- Otros seis suscriptores recibirán un falso positivo de que su cónyuge ha fallecido (con un 50% de posibilidades de que no hubieran recibido este mensaje si hubiéramos elegido el código alternativo para nuestro primer suscriptor)
- Todos los demás suscriptores sabrán que su cónyuge no ha muerto
Con este fin, básicamente estamos cambiando algo de “procesamiento” a los canales de recepción con el fin de minimizar las huellas de memoria en el remitente. Este ejemplo representa 29 estados con 3 bits (que de lo contrario se correlacionarían con ocho estados) con tasas de error del 50%, pero un número mayor de n escala el número de estados posibles exponencialmente, mientras que la tasa de error tiende cada vez más pequeña (en comparación con el tamaño de muestra completo ) Por ejemplo, con 16 bits, este sistema admite hasta 20 ^ 19728 estados (en comparación con los 16 bits que normalmente tienen un límite de 65.536 estados).
Anexo divertido: cuando n = 0, puede asumir un estado de referencia independiente que técnicamente satisface 1 estado (2 ^ 0 == 1) con 0 bits.
Notas al pie
[1] https: //www.math.uni-bielefeld.d…
