Tema 1

Computaci´on Bio–inspirada
Mario de J. P´erez Jim´enez
Grupo de Investigaci´
on en Computaci´
on Natural
Dpto. Ciencias de la Computaci´
on e Inteligencia Artificial
Universidad de Sevilla
marper@us.es
http://www.cs.us.es/~marper/

Sevilla, Noviembre de 2009

Tema I: Introducci´on. Computaci´on Natural

Planteamiento y resoluci´
on de de problemas abstractos.
Mejora de la calidad de vida.
B´usqueda de procedimientos sistem´
aticos.
Resoluci´
on mec´
anica de problemas:
Transferencia del conocimiento.
Apoyo a la resoluci´
on.

Computabilidad (I)

Algoritmo: m´etodo especial de resoluci´
on de un cierto tipo de problemas.
Ab´
u J´
afar Mohammed ibn al–Khowarizmi: procedimientos mec´
anicos para el
´
Algebra
(a˜
no 825 d.C.)
Primer algoritmo no trivial: m´
aximo com´
un divisor de dos n´umeros enteros
(Euclides entre 400 y 300 a. C.).
Existencia de problemas resolubles mec´
anicamente

Computabilidad (II)
A finales del siglo XVII Leibnitz formula
Necesidad de disponer de un lenguaje universal (lingua characteristica)
Necesidad de mecanizar cualquier tipo de razonamiento (calculus
ratiocinator).
D. Hilbert (en 1928) formula tres cuestiones sobre las Matem´
aticas:
1. ¿Soncompletas?
2. ¿Son consistentes?
3. ¿Son decidibles? (Entscheidungsproblem).

Computabilidad (III)

Respuestas negativas a las dos primeras cuestiones: teoremas de incompletitud
de K. G¨
odel (1931).
No es posible encontrar una axiomatizaci´
on completa de las Matem´
aticas.
K. G¨
odel dej´
o sin responder la tercera cuesti´
on.
Aparecen problemas de los que no se conocen soluciones mec´
anicas.Cuesti´
on 1: Dado un problema, determinar si existe un procedimiento
mec´
anico que lo resuelve.
Soluciones positivas versus soluciones negativas.

Computabilidad (IV)

Formalizaci´
on del concepto de procedimiento mec´
anico: modelos de
computaci´
on
Funciones recursivas (K. G¨
odel, 1931–1933).
λ–c´
alculo (A. Church y S. Kleene, 1931).
M´
aquinas de Turing (A. Turing, 1936).
Modelo de computaci´
on:sintaxis y sem´
antica.
Procedimiento mec´
anico.
Funciones computables.
M´
aquinas

Computabilidad (V)

Limitaciones de los modelos de computaci´
on
Existencia de problemas indecidibles.
L´
ogica de primer orden (Church y Turing, 1936).
Problema de la parada (Turing, 1936).
La tesis de Church–Turing.
Equivalencia modelos de computaci´
on (Turing, 1936).

Complejidad Computacional (I)

Aparici´on de los primeros ordenadores de prop´
osito general (implementaci´
on
pr´
actica de ideas de J. von Neumann).
M´
aquina convencional: soporte electr´
onico
M´
aquina no convencional: otro soporte distinto
¿Qu´e problemas resuelven las m´
aquinas reales?
Resolubilidad mec´
anica pr´
actica de problemas.
Cantidad de recursos computacionales necesarios (tiempo y espacio).
An´
alisis comparativo dedistintas soluciones.

Complejidad Computacional (II)
Cuesti´
on 2: Dado un problema hallar el mejor algoritmo que lo resuelva.

B´
usqueda de algoritmos o
´ptimos.
Hallar una cota inferior de los recursos necesarios para ejecutar cualquier
algoritmo que resuelva el problema.
Hallar un algoritmo que resuelva el problema y que use una cantidad de
recursos del orden de la cota.
Complejidadcomputacional inherente a un problema.
A veces, es imposible encontrar algoritmos o
´ptimos
(teorema de aceleraci´
on de Blum).

Clases de complejidad

Necesidad de analizar la complejidad de problemas de manera global:
Clases de complejidad.
Ingredientes necesarios para definir una clase de complejidad:
Un modelo de computaci´
on.
Un modo de computaci´
on.
Una medida de complejidad.
Una funci´
on totalcomputable (cota superior de recursos).
Las clases de complejidad L, P y EXP.

La clase P

Resolubilidad a trav´es de ordenadores reales.
Tratabilidad e intratabilidad de problemas.
Algoritmo eficiente: la cantidad de recursos necesarios para su ejecuci´
on est´
a
acotada por un polinomio.
¿Por qu´e los polinomios para establecer la frontera?
Es una clase de funciones estables por suma y...