Estructura de datos inconsciente

Goldreich y Ostrovsky propusieron este término en relación con la protección del software.

El acceso a la memoria de la RAM ciega es probabilístico y la distribución de probabilidad es independiente de la entrada. En el artículo compuesto por Goldreich y Ostrovsky hay un teorema sobre la RAM ciega: Sea RAM( m ) una RAM con m ubicaciones de memoria y acceso a una máquina oráculo aleatoria . Entonces, t pasos de un programa arbitrario de RAM( m ) pueden simularse por menos de ⁠${\displaystyle O(t(\log _{2}t)^{3})}$⁠ pasos de un despistado ⁠${\displaystyle \mathrm {RAM} (m(\log _{2}m)^{2})}$Cada simulación inconsciente de RAM( m ) debe hacer al menos${\displaystyle \max\{m,(t-1)\log _{2}m\}}$accesos para simular t pasos.

Ahora tenemos el algoritmo de raíz cuadrada para simular el funcionamiento de la RAM sin que se den cuenta.

1. Para cada${\displaystyle {\sqrt {m}}}$accesos, permutar aleatoriamente primero${\displaystyle m+{\sqrt {m}}}$memoria.
2. Primero, verifique las palabras del refugio si queremos acceder a una palabra.
3. Si la palabra está presente, accede a una de las palabras ficticias. Si la palabra no está presente, encuentra la ubicación permutada.

Para acceder a la RAM original en t pasos necesitamos simularla con${\displaystyle t+{\sqrt {m}}}$ pasos para la RAM inconsciente. Para cada acceso, el costo sería O(${\displaystyle {\sqrt {m}}\cdot \log m}$).

Otra forma de simular es mediante un algoritmo jerárquico. La idea básica es considerar la memoria del refugio como un búfer y extenderla a múltiples niveles de búferes. Para el nivel I , hay${\displaystyle 4^{i}}$⁠ cubos y para cada cubo hay log t elementos. Para cada nivel hay una función hash seleccionada aleatoriamente .

La operación es como la siguiente: Primero, carga el programa hasta el último nivel, que se puede decir que tiene ⁠${\displaystyle 4^{t}}$Cubos . Para leer, consulte el cubo .${\displaystyle h_{i}(V)}$Desde cada nivel, si (V,X) ya se encuentra, elige un cubo al azar para acceder, y si no se encuentra, verifica el cubo .${\displaystyle h_{i}(V)}$⁠ , solo hay una coincidencia real y las restantes son entradas ficticias. Para escribir, coloque (V,X) en el primer nivel, y si los primeros niveles I están llenos, mueva todos los niveles I a ⁠${\displaystyle I+1}$niveles y vaciar los primeros niveles I.

El costo de tiempo para cada nivel es O (log t); el costo para cada acceso es${\displaystyle O((\log t)^{2})}$; El costo del Hashing es ;${\displaystyle O(t(\log t)^{3})}$⁠ .

Un árbol ajeno a la realidad es un árbol con raíz que posee la siguiente propiedad:

• Todas las hojas están al mismo nivel.
• Todos los nodos internos tienen un grado como máximo de 3.
• Solo los nodos situados en el extremo derecho del árbol pueden tener grado uno.

El árbol ciego es una estructura de datos similar al árbol 2-3 , pero con la propiedad adicional de ser ciego. El camino más a la derecha puede tener grado uno y esto puede ayudar a describir los algoritmos de actualización. El árbol ciego requiere aleatorización para lograr un ⁠${\displaystyle O(\log(n))}$Tiempo de ejecución para las operaciones de actualización. Y para dos secuencias de operaciones M y N que actúan sobre el árbol, la salida del árbol tiene las mismas distribuciones de probabilidad de salida. Para el árbol, hay tres operaciones:

CREATE (L)

Construye un nuevo árbol que almacene la secuencia de valores L en sus hojas.

INSERT (b, i,T)

insertar un nuevo nodo hoja que almacene el valor b como la i ^-ésima hoja del árbol T.

DELETE (i, T)

Retire la i- ^ésima hoja de T.

Paso de creación: La lista de nodos en el nivel i ^se obtiene recorriendo la lista de nodos en el nivel i+1 de izquierda a derecha y repitiendo lo siguiente:

1. Elija d {2, 3} uniformemente al azar.
2. Si quedan menos de d nodos en el nivel i+1, establezca d igual al número de nodos restantes.
3. Crea un nuevo nodo n en el nivel I con los siguientes d nodos en el nivel i+1 como hijos y calcula el tamaño de n como la suma de los tamaños de sus hijos.

   

Por ejemplo, si los lanzamientos de moneda de d {2, 3} tienen un resultado de: 2, 3, 2, 2, 2, 2, 3 almacena la cadena “OBLIVION” como el siguiente árbol de olvido.

Tanto INSERT (b, I, T)como DELETE(I, T)tienen un tiempo de ejecución esperado de O (log n ). Y para INSERTy DELETE tenemos:

INSERTAR (b, I, CREAR (L)) = CREAR (L [1] + …….., L[ i], b, L[i+1]………..) ELIMINAR (I, CREAR (L)) = CREAR (L[1]+ ………L[I - 1], L[i+1], ………..)

Por ejemplo, si se ejecuta la CREATE (ABCDEFG)operación OR INSERT (C, 2, CREATE (ABDEFG)), se obtienen las mismas probabilidades de resultado entre estas dos operaciones.