Tesis doctoral de Miguel Angel Díaz Martínez
La informática teórica es una disciplina básica ya que la mayoría de los avances en informática se sustentan en un sólido resultado de esa materia. en los últimos años, tal vez debido al incremento de la potencia de los ordenadores como a la cercanía del límite físico en la miniaturización de los componentes electrónicos, resurge el interés por modelos formales de computación alternativos a la arquitectura clásica de von neumman. Muchos de estos modelos se inspiran en la forma en la que la naturaleza resuelve eficientemente problemas muy complejos. La mayoría son computacionalmente completos e intrínsecamente paralelos. Por este motivo se les está llegando a considerar como nuevos paradigmas de computación (computación natural). Se dispone, por tanto, de un abanico de arquitecturas abstractas tan potentes como los computadores convencionales y, a veces, más eficientes: alguna de ellas mejora el rendimiento, al menos temporal, de problemas np-completos proporcionando costes no exponenciales. La representación formal de las redes de procesadores evolutivos requiere de construcciones tanto independientes como dependientes del contexto, dicho de otro modo, en general una representación formal completa de un nep implica restricciones tanto sintácticas como semánticas, es decir, que muchas representaciones aparentemente (sintácticamente) correctas de casos particulares de estos dispositivos no tendrían sentido porque podrían no cumplir otras restricciones semánticas. La aplicación de evolución gramatical semántica a los neps pasa por la elección de un subconjunto de ellos entre los que buscar los que solucionen un problema concreto. en este trabajo se ha realizado un estudio sobre un modelo inspirado en la biología celular denominado redes de procesadores evolutivos, esto es redes cuyos nodos son procesadores muy simples capaces de realizar únicamente un tipo de mutación puntual (inserción, borrado o sustitución de un símbolo). Estos nodos están asociados con un filtro que está definido por alguna condición de contexto aleatorio o de pertenencia. Las redes están formadas a lo sumo de seis nodos y teniendo los filtros definidos por una pertenencia a lenguajes regulares son capaces de generar todos los lenguajes enumerables recursivos independientemente del grafo subyacente. Este resultado no es sorprendente ya que semejantes resultados han sido documentados en la literatura. Si se consideran redes con nodos y filtros definidos por contextos aleatorios – que parecen estar más cerca a las implementaciones biológicas – entonces se pueden generar lenguajes mas complejos como lenguajes no in-dependientes del contexto. Sin embargo, estos mecanismos tan simples son capaces de resolver problemas complejos en tiempo polinomial. Se ha presentado una solución lineal para un problema np-completo, el problema de los 3-colores. como primer aporte significativo se ha propuesto una nueva dinámica de las redes de procesadores evolutivos con un comportamiento no determinista y masivamente paralelo, y por tanto todo el traba jo de investigación en el área de la redes de procesadores se puede trasladar a las redes masivamente paralelas. Por ejemplo, las redes masivamente paralelas se pueden modificar de acuerdo a determinadas reglas para mover los filtros hacia las conexiones. cada conexión se ve como un canal bidireccional de manera que los filtros de entrada y salida coinciden. A pesar de esto, estas redes son computacionalmente completas. Se pueden también implementar otro tipo de reglas para extender este modelo computacional. Se reemplaza las mutaciones puntuales asociadas a cada nodo por la operación de splicing. Este nuevo tipo de procesador se denomina procesador splicing. Este modelo computacional ansp es semejante en cierto modo a los sistemas distribuidos en tubos de ensayo basados en splicing. Se ha definido un nuevo modelo -redes de procesadores evolutivos con filtros en las conexiones- en el cual los procesadores tan sólo tienen reglas y los filtros se han trasladado a las conexiones. Dicho modelo es equivalente, bajo determinadas circunstancias, a las redes de procesadores evolutivos clásicas. Sin dichas restricciones el modelo propuesto es un superconjunto de los neps clásicos. La principal venta ja de mover los filtros a las conexiones radica en la simplicidad de la modelización. sobre el término «procesador evolutivo» empleado en esta tesis, el proceso computacional descrito aquí no es exactamente un proceso evolutivo en el sentido darwiniano. Pero las operaciones de reescritura que se han considerado pueden interpretarse como mutaciones y los procesos de filtrado se podrían ver como procesos de selección. a lo largo de esta tesis se ha tomado como definición de la medida de complejidad para los ansp, una que denotaremos como tamaño (considerando tamaño como el número de nodos del grafo subyacente). Se ha mostrado que cualquier lenguaje enumerable recursivo puede ser aceptado por un ansp en el cual el número de procesadores está linealmente acotado por la cardinalidad del alfabeto de la cinta de un máquina de turing que reconoce dicho lenguaje. Siguiendo el concepto de ansp universales, se ha demostrado que un ansp con una estructura de grafo fija puede aceptar cualquier lengua je enumerable recursivo. Un ansp se puede considerar como un ente capaz de resolver problemas, además de tener otra propiedad relevante desde el punto de vista practico: se puede definir un ansp universal como una subred, donde sólo un cantidad limitada de parámetros es dependiente del lengua je. La anterior característica se puede interpretar como un método para resolver cualquier problema np en tiempo polinomial empleando un ahenp de tamaño constante, concretamente treinta y uno. Esto significa que la solución del cualquier problema np es uniforme en el sentido de que la red, exceptuando la subred universal, se puede ver como un programa: adaptándolo a la instancia de problema a resolver, se escogerán los filtros y las reglas que no pertenecen a la subred universal.
Datos académicos de la tesis doctoral «Modelo de computación conexionista inspirado en las redes de procesadores evolutivos y su aprendiza je«
- Título de la tesis: Modelo de computación conexionista inspirado en las redes de procesadores evolutivos y su aprendiza je
- Autor: Miguel Angel Díaz Martínez
- Universidad: Politécnica de Madrid
- Fecha de lectura de la tesis: 13/07/2009
Dirección y tribunal
- Director de la tesis
- Luis Fernando De Mingo Lopez
- Tribunal
- Presidente del tribunal: Juan b. Castellanos peñuela
- jacinto Martín jiménez (vocal)
- Antonio De amescua seco (vocal)
- víctor Mitrana (vocal)