En ciencias de la computación , y más específicamente en la teoría de la computabilidad y la teoría de la complejidad computacional , un modelo de computación es un modelo que describe cómo se calcula una salida de una función matemática dada una entrada. Un modelo describe cómo se organizan las unidades de cálculos, memorias y comunicaciones. [1] La complejidad computacional de un algoritmo se puede medir dado un modelo de computación. El uso de un modelo permite estudiar el rendimiento de los algoritmos independientemente de las variaciones que son específicas de implementaciones particulares y tecnología específica.
Modelos
Los modelos de cálculo se pueden clasificar en tres categorías: modelos secuenciales, modelos funcionales y modelos concurrentes.
Los modelos secuenciales incluyen:
Los modelos funcionales incluyen:
Los modelos concurrentes incluyen:
- Autómata celular
- puertas lógicas y circuitos digitales
- Redes de procesos Kahn
- Redes de Petri
- Flujo de datos sincrónico
- Redes de interacción
- Modelo de actor
Los modelos se diferencian por su poder expresivo; por ejemplo, cada función que puede ser calculada por una máquina de estados finitos también puede ser calculada por una máquina de Turing , pero no al revés.
Un modelo de cálculo no determinista está asociado con algunos de estos modelos de cálculo. Los modelos no deterministas no son útiles para el cálculo práctico; se utilizan en el estudio de la complejidad computacional de algoritmos.
Usos
En el campo del análisis en tiempo de ejecución de algoritmos , es común especificar un modelo computacional en términos de operaciones primitivas permitidas que tienen costo unitario, o simplemente operaciones de costo unitario . Un ejemplo de uso común es la máquina de acceso aleatorio , que tiene un costo unitario para el acceso de lectura y escritura a todas sus celdas de memoria. A este respecto, se diferencia del modelo de máquina de Turing mencionado anteriormente.
Categorías
Existen muchos modelos de cálculo, que se diferencian en el conjunto de operaciones admisibles y su costo de cálculo. Se clasifican en las siguientes categorías generales:
- Máquina abstracta y modelos equivalentes a ella (por ejemplo, el cálculo lambda es equivalente a la máquina de Turing ): se utiliza en pruebas de computabilidad y límites superiores de complejidad computacional de algoritmos.
- Modelos de árboles de decisión : se utilizan en pruebas de límites inferiores en la complejidad computacional de problemas algorítmicos.
Ver también
- Máquina de pila ( máquina de 0 operandos)
- Máquina acumuladora ( máquina de 1 operando)
- Registrar máquina (2,3, ... operando máquina)
- Máquina de acceso aleatorio
- Modelo de sonda celular
- Modelo de consulta de Robertson – Webb
Referencias
- ^ "Modelos de computación" (PDF) .
Otras lecturas
- Fernández, Maribel (2009). Modelos de Computación: Introducción a la Teoría de la Computabilidad . Temas de Pregrado en Informática. Saltador. ISBN 978-1-84882-433-1.
- Savage, John E. (1998). Modelos de computación: exploración del poder de la computación . Addison-Wesley. ISBN 978-0201895391.