Complejidad Computacional y Redes Neuronales Artificiales: Conceptos Clave

Complejidad Computacional

La complejidad computacional considera globalmente todos los posibles algoritmos para resolver un problema dado. Estamos interesados en la distinción que existe entre los problemas que pueden ser resueltos por un algoritmo en tiempo polinómico y los problemas para los cuales no conocemos ningún algoritmo polinómico, es decir, el mejor es no-polinómico.

Problemas NP-Completos

La definición formal de NP-Completo usa reducciones o transformaciones de un problema a otro.

Así, tenemos que los siguientes problemas son NP-Completos: rutas y circuitos de Hamilton, asignación de trabajos con penalizaciones, el agente viajero, el problema de la mochila.

Problemas Intratables

Un problema se dice intratable si es muy difícil que un algoritmo de tiempo no polinomial lo resuelva.

La comunidad computacional acepta que un buen algoritmo es aquel para el cual existe un algoritmo polinomial determinístico que lo resuelva.

Algoritmos No Determinísticos

Dos fases:

• No Determinística: Alguna cadena de caracteres, s, completamente arbitraria es escrita a partir de algún lugar de memoria designado. Cada vez que el algoritmo corre, la cadena escrita puede diferir.
• Determinística: Un algoritmo determinístico (es decir, ordinario) es ejecutado. Además de la entrada del problema de decisión, el algoritmo puede leer s, o puede ignorarla. Eventualmente, este para con una salida de sí o no, o puede entrar en un ciclo infinito y nunca parar.

El número de pasos llevados a cabo durante la ejecución de un algoritmo no determinístico es definido como la suma de los pasos en ambas fases; esto es, el número de pasos tomados para escribir s (simplemente el número de caracteres en s) más el número de pasos ejecutados por la segunda fase determinística.

Redes Neuronales Artificiales

Tipo de sinapsis: excitatoria, inhibitoria.

Neurona Artificial

Autómata caracterizado por:

• Un estado interno
• Señales de entrada
• Funciones de activación y transferencia

Tipos de neuronas:

• Producto punto
• Distancia

Aprendizaje

Capacidad de una neurona (o red neuronal) para ajustar las conexiones (pesos) de modo de obtener una respuesta deseada o que satisfaga ciertos criterios.

Regla de Hebb

Cuando una neurona i repetida y persistentemente excita a una neurona j, algún proceso de crecimiento o metabólico se produce en una o ambas neuronas de modo que la eficiencia de excitación de i sobre j aumenta.

Redes Neuronales Artificiales (RNA)

Consisten en un conjunto de neuronas interconectadas entre sí.

Quedan completamente caracterizadas por:

• Número de neuronas
• Arquitectura de interconexión
• Valor de los pesos
• Funciones de activación y transferencia

Las RNA pueden trabajar de dos modos:

• Aprendizaje:
  • Supervisado (vía ejemplos)
  • No supervisado
• Reconocimiento o simulación: Se usa la RNA para procesar información.