COMPUTABILIDAD Y COMPLEJIDAD

Mario de J. Perez Jimenez

Grupo de Investigacion en Computacion NaturalDpto. Ciencias de la Computacion e Inteligencia Artificial

ETS Ingenierıa Informatica, Universidad de Sevilla

marper@us.es

http://www.cs.us.es/~marper/

http://www.cs.us.es/cursos/cc/

Sevilla, 29 de septiembre de 2009

Computabilidad

I Estudio de la resolubilidad mecanica de problemas.

I Decidibilidad versus indecidibilidad.

2 / 35

Complejidad

I Estudio de la resolubilidad mecanica practica de problemas.

I Tratabilidad versus intratabilidad.

3 / 35

Objetivo del curso

I Estudio de recursos computacionales (tiempo y/o espacio)necesario para resolver problemas usando maquinas reales.

I Presentar dos modelos no convencionales bio–inspirados

4 / 35

Objetivo del curso

I Estudio de recursos computacionales (tiempo y/o espacio)necesario para resolver problemas usando maquinas reales.

I Presentar dos modelos no convencionales bio–inspirados

5 / 35

Problemas concretos vs Problemas abstractosUn problema concreto:

I Visitar 42 ciudades, coste cij entre dos ciudades.

I Hallar un circuito por las 42 ciudades de coste mınimo.

6 / 35

Otros problemas concretos del mismo tipo

I Visitar 3150 ciudades, coste c ′ij entre dos ciudades.

I Hallar un circuito por las 3150 ciudades de coste mınimo.

7 / 35

Problemas concretos vs Problemas abstractos

De un problema concreto (de la vida real) a un problema abstracto

I Fase de abstraccion

I Fase de modelizacion: problema abstracto

Problema abstracto: conjunto de problemas concretos

I Tamano de un problema concreto

Un problema abstracto: TSP

Dado un grafo no dirigido con pesos en sus aristas, deter-minar un circuıto hamiltoniano de peso mınimo

8 / 35

Otros problemas concretos modelizados por el TSP

I Sistemas de navegacion GPS

I Planificacion de movimientos de robots (Robotic machine)

I Diseno de circuitos (Printed Circuit Manufacturing)

I Elaboracion de mapas locales del genoma humano (Genome local maps)

I Vehıculos autoguiados (AGV)

I . . .

9 / 35

Otro problema concreto computacionalmente duro

10 / 35

Problemas concretos vs Problemas abstractos

Procedimiento de resolucion de un problema de la vida real

I Se modeliza a traves de un problema abstracto

I Se disena una solucion mecanica del problema abstracto

I Se implementa dicha solucion mediante un programa

I Se ejecuta el programa sobre una maquina electronica para los datosespecıficos del problema concreto

11 / 35

Tratabilidad computacional de problemas (I)

Diseno de una solucion mecanica de un problema abstracto

Implementacion de esa solucion en una maquina

Ejecucion de esa solucion para problemas concretos de tamano grande

I La maquina devuelve una respuesta en tiempo aceptable

I La maquina NO devuelve una respuesta en tiempo aceptable

12 / 35

Tratabilidad computacional de problemas abstractos (II)

I Problema tratableI Existe UN programa que resuelve el problema y proporciona

soluciones para entradas de tamano grande

I Problemas intratablesI NINGUN programa que resuelve el problema proporciona

soluciones para entradas de tamano grande

I Problema presuntamente intratableI NINGUN programa CONOCIDO que resuelve el problema

proporciona soluciones para entradas de tamano grande

13 / 35

El problema del campeonato de liga de futbol

Tras la jornada 25 del campeonato de liga de futbol deprimera division, un aficionado desea saber si su equipo tieneposibilidades matematicas de quedar campeon de liga

I Sistema antiguo de puntuacion (2, 1, 0): tratable

I Sistema nuevo de puntuacion (3, 1, 0): presuntamente intratable

14 / 35

El problema del campeonato de liga de futbol

Tras la jornada 25 del campeonato de liga de futbol deprimera division, un aficionado desea saber si su equipo tieneposibilidades matematicas de quedar campeon de liga

I Sistema antiguo de puntuacion (2, 1, 0): tratable

I Sistema nuevo de puntuacion (3, 1, 0): presuntamente intratable

14 / 35

El problema del campeonato de liga de futbol

Tras la jornada 25 del campeonato de liga de futbol deprimera division, un aficionado desea saber si su equipo tieneposibilidades matematicas de quedar campeon de liga

I Sistema antiguo de puntuacion (2, 1, 0): tratable

I Sistema nuevo de puntuacion (3, 1, 0): presuntamente intratable

14 / 35

El problema del campeonato de liga de futbol

Tras la jornada 25 del campeonato de liga de futbol deprimera division, un aficionado desea saber si su equipo tieneposibilidades matematicas de quedar campeon de liga

I Sistema antiguo de puntuacion (2, 1, 0): tratable

I Sistema nuevo de puntuacion (3, 1, 0): presuntamente intratable

14 / 35

Clases de complejidad de problemas abstractos

I Clase de complejidad P

I Es la clase de los problemas tratables

I Clase de complejidad NP

I Existen problemas de la clase NP que son presuntamenteintratables.

I Clase de complejidad EXP

I Existen problemas de la clase EXP que son intratables.

15 / 35

EXP

NP

P

NP−Completo

P

16 / 35

Determinismo vs no determinismo

Modo determinista

Modo no–determinista

Se tiene que P⊆NP

P?= NP

El problema P versus NP: determinar si P y NP coinciden.

Premio del CMI: un millon de dolares.

17 / 35

Limitaciones de las maquinas electronicas

Maquinas: dispositivos finitos

Limitaciones en espacio (memoria) y en tiempo

I Espacio: miniaturizacion (R. Feymann, 1959)

I Tiempo: velocidad de calculo de los procesadores (R. Churchhouse, 1983)

Consecuencia:

I Existen problemas muy importantes de la vida real que nunca podran serresueltos por ordenadores electronicos (a menos que . . . )

18 / 35

Para mejorar la calidad de vida

Existen muchos problemas concretos que se han de resolver

I Economıa

I Biologıa Molecular

I Vida Artificial

I Paleontologıa

I Negocios

I Oncologıa

I Robotica

I Ecologıa

I . . .

19 / 35

Computacion no convencional

Modelo de computacion: formaliza el concepto de procedimiento mecanico

I Dispositivos del modelo : maquinas

Maquina convencional: soporte electronico

Maquina no convencional: otro soporte distinto

La Computacion Natural

I Redes Neuronales (W. McCulloch y W. Pitts , 1943)

I Algoritmos geneticos (J. Holland, 1975)

I Computacion molecular basada en ADN (L. Adlemann, 1994)

I Computacion celular con membranas (Gh. Paun, 1998–2000)

20 / 35

Maquinas moleculares (I)

I Procedimientos matematicos vs procesos biologicos.

I L. Adleman materializo esta similitud (nov. 1994).

I Julio de 2000: interruptor a partir de una molecula.

I Sustituye la luz por una reaccion quımica.I Pueden disponer de mas de mil procesadores en el espacio

ocupado por un procesador.I Pueden aumentar la velocidad cien mil millones de veces.I Pueden reproducir cien ordenadores convencionales en el

tamano de un grano de sal fina.

I Simulacion bioquımica de una MT (E.Shapiro, nov. 2001)

21 / 35

Maquinas moleculares (II)

I Cromosomas:

I Descritos por Holfmeister, 1848I Codifica la informacion genetica (Principios del s. XX)I Proteınas + ADN (Claude, Porter, 1943 y Mirsky, 1947).

I ADN (J. Watson y F. Crick, 1951–1953)

I Descifran la estructura.

I Descubren el principio de complementariedad.

I Demuestran que las moleculas de ADN codifican toda lainformacion genetica.

I Justifican el uso de ciertas tecnicas para su manipulacion.

22 / 35

23 / 35

24 / 35

Una maquina molecular basada en ADN

I Dispositivos moleculares que simulan acciones de seres vivos

I N. Seeman, S. Liao

Esquema de una maquina DNA que realiza movimientos de extension y

contraccion

P. Alberti, J.L. Mergny. DNA duplex–quadruplex exchande as the basis for a nanomolecular machine. PANS, 100,

4 (2003), 1569–157325 / 35

La celula (I)

Celula: unidad fundamental de todo organismo vivo.

I Estructura compleja y, a la vez, muy organizada.

I Permite ejecucion simultanea de reacciones quımicas.

Existen dos tipos de celulas:

I Procariotas: carecen de un nucleo bien definido (propias de losorganismos unicelulares).

I Eucariotas: poseen un nucleo rodeado por una doble membrana(especıficas de animales y plantas).

26 / 35

La celula (II)Realizan de manera similar unos procesos esenciales para la vida:

I Replicacion del ADN

I Produccion de energıa

I Sıntesis de proteınas

I Procesos metabolicos.

Modelo de mosaico fluido de Singer y Nicholson, 1973

27 / 35

La celula (III)

Partes de una celula eucariota

I Una especie de piel (membrana plasmica)

I El corazon de la celula (nucleo), que almacena el ADN

I El resto de la celula (citoplasma), que contiene:

I La mitocondria: se encarga de producir energıa

I El aparato de Golgi: fabrica de proteınas

I El retıculo endoplasmico, red de membranas interconectadas

I Los lisosomas: estomagos de las celulas

28 / 35

La celula (IV)

29 / 35

Las membranas biologicas

I Involucradas en la mayorıa de reacciones quımicas

I Canales selectivos de comunicacion (barreras semipermeables).

I Controlan un flujo de datos; es decir, de informacion:

I Premio Nobel de Quımica 2003: P. Agre y R. MacKinnon (canalesproteınicos de las membranas).

30 / 35

Celulas versus maquinas (I)

En una celula viva

I Cada membrana trabaja con compuestos quımicos de acuerdo con unasreacciones especıficas

En una maquina paralela

I Cada procesador trabaja con datos de acuerdo con un programa especıfico

Celula Maquina

Membranas Procesadores

Compuestos quımicos Datos

Reacciones quımicas Instrucciones

31 / 35

Celulas versus maquinas (II)

Muchos desarrollos en Informatica, se han producido bajo la inspiracion deprocesos que se dan en la naturaleza.

I ¿Es la celula una fuente de inspiracion para la informatica?

I ¿ Es posible definir un modelo de computacion inspirado en las celulas?

I ¿Es posible implementar computaciones a traves de las celulas vivas?

32 / 35

Modelos de computacion celular con membranas (I)

Computacion celular con Membranas: Gh. Paun, 1998–2000

I Modelo no determinista de tipo distribuido, paralelo y maximal.

La estructura de membranas:

I Conjunto de membranas

I Multiconjuntos de objetos situados en las regiones.

I Reglas de evolucion.

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

membranaelemental

membrana

región

piel

entorno

entorno

33 / 35

Algunas aplicaciones de la Computacion celular

I Simulacion de maquinas de Turing

I Caracterizacion de la relacion P = NP

I Resolucion eficiente de problemas muy difıciles

I Especificaciones de modelos economicos

I Computacion neuronal y a nivel de tejidos

I Simulacion del comportamiento de sociedades (colonias de abejas)

I Simulacion de procesos biologicos:

I Quorum Sensing (Vibrio Fischeri)I Regulacion de genes (Pseudomonas, Lac Operon, etc.)I Dinamica de los tumores cancerıgenosI Interacciones proteınicas que intervienen en la genesis de

tumores (p53, EGFR, apoptosis,...)

34 / 35

Algunos retos en la Computacion celular

I Implementacion del modelo celular

I Elaboracion de un lenguaje de programacion celular

I Diseno de estrategias de busqueda eficiente

I Simulacion de sistemas complejos (dinamica de poblaciones)

I Formalizacion de los sistemas de produccion

I Formulacion de hipotesis acerca de procesos biologicos

35 / 35