Modelo de sonda celular

---

En informática , el modelo de sonda celular es un modelo de cálculo similar a la máquina de acceso aleatorio , excepto que todas las operaciones son gratuitas, excepto el acceso a la memoria. Este modelo es útil para probar límites inferiores de algoritmos para problemas de estructura de datos.

El modelo de sonda de celda es una modificación menor del modelo de máquina de acceso aleatorio , en sí mismo una modificación menor del modelo de máquina contador , en el que el costo computacional solo se asigna al acceso a unidades de memoria llamadas celdas.

En este modelo, la computación se enmarca como un problema de consultar un conjunto de celdas de memoria. El problema tiene dos fases: la fase de preprocesamiento y la fase de consulta. La entrada a la primera fase, la fase de preprocesamiento, es un conjunto de datos a partir de los cuales se construye alguna estructura a partir de celdas de memoria. La entrada a la segunda fase, la fase de consulta, es un dato de consulta. El problema es determinar si el dato de la consulta se incluyó en el conjunto de datos de entrada original. Las operaciones son gratuitas excepto para acceder a las celdas de memoria.

Este modelo es útil en el análisis de estructuras de datos. En concreto, el modelo muestra claramente un número mínimo de accesos a memoria para solucionar un problema en el que hay datos almacenados sobre los que nos gustaría ejecutar alguna consulta. Un ejemplo de tal problema es el problema dinámico de suma parcial . ^{[1] [2]}

En el artículo de 1981 de Andrew Yao "¿Deberían ordenarse las tablas?", ^[3] Yao describió el modelo de sonda de celda y lo usó para dar un número mínimo de "sondas" de celda de memoria o accesos necesarios para determinar si existe un dato de consulta dado. dentro de una tabla almacenada en la memoria.

Dado un conjunto de datos, construya una estructura que consta de celdas de memoria, cada una de las cuales puede almacenar bits. Luego, cuando se le proporcione un elemento de consulta, determine si es correcto accediendo a las celdas de memoria. Tal algoritmo se denomina algoritmo -error -probe que usa celdas con tamaño de palabra . ^[4]${\ Displaystyle S}$${\ Displaystyle c}$${\ Displaystyle w}$${\ Displaystyle s}$${\ Displaystyle s \ in S}$${\ Displaystyle 1- \ varepsilon}$${\ Displaystyle t}$${\ Displaystyle \ varepsilon}$${\ Displaystyle t}$${\ Displaystyle c}$${\ Displaystyle w}$

---