Tesis doctoral de Agustín Riscos Núñez
La memoria se sitúa en el marco teórico de la computación celular con membranas. Se trata de un modelo de computación no convencional introducido en 1998 por gh. Paun, inspirado en el funcionamiento de la célula. concretamente, se introduce formalmente una variante de sistemas de computación celular con membranas que se usa como modelo para atacar la resolución de problemas np-completos: los sistemas celulares reconocedores de lenguajes con membranas activas. en la memoria se define, además, una clase de complejidad polinomial que proporciona un concepto de resolubilidad eficiente de problemas a través de sistemas celulares reconocedores; es decir, un concepto de tratabilidad en este nuevo marco no convencional (por el momento a nivel teórico, ya que aún no existen implementaciones en soporte electrónico ni bioquímico de los sistemas celulares). en este marco, se incluyen en la memoria el diseño, análisis y verificación formal de soluciones celulares eficientes para tresproblemas numéricos np-completos: subset sum, knapsack y partición. tras el estudio de dichas soluciones, quedan patentes una serie de similitudes entre ellas que dan pie a abordar la tarea de diseñar un lenguaje de programación celular, en el sentido de que se puede considerar que ciertos grupos de reglas se encargan de ejecutar tareas específicas y que, por tanto, pueden ser tratadas de manera independiente, a modo de las macros de un modelo de computación orientado a programas. en la memoria se estudia, además, un programa informático escrito en prolog capaz de simular, paso a paso, una computación de cualquier sistema celular con membranas activas. Se ha programado un módulo para dicho simulador que es capaz de generar automáticamente, dada una instancia de uno de los tres problemas mencionados anteriormente, los ficheros prolog correspondientes a la configuración inicial y al conjunto de reglas del sistema celular encargado de r
Datos académicos de la tesis doctoral «Programación celular: resolución eficiente de problemas numéricos np-completos«
- Título de la tesis: Programación celular: resolución eficiente de problemas numéricos np-completos
- Autor: Agustín Riscos Núñez
- Universidad: Sevilla
- Fecha de lectura de la tesis: 23/09/2004
Dirección y tribunal
- Director de la tesis
- Mario De Jesús Pérez Jiménez
- Tribunal
- Presidente del tribunal: Juan Pazos sierra
- María n Gheorghe (vocal)
- oscar H. ibarra (vocal)
- gheorghe Paun (vocal)