| Vol. 2, Núm. 4, invierno de 2009, en curso | Acerca de Epistemowikia | Contacto: conomun{EN}gmail{punto}com |
| Epistemowikia es parte de
 CALA → ALA | Communitas | Evolvere | Editio | Epistemowikia | Exercitatio | Fictor | Flor | ||
| Diseñado para navegadores cumplidores con los estándares, como Firefox, Lynx/Links2 o Safari - NO Internet Explorer.
| ||
Límites de la computación
De Epistemowikia
Tabla de contenidos |
Introducción a la Teoría de la Computabilidad y Teoría de la Complejidad Computacional
La Teoría de la Complejidad Computacional estudia los recursos necesarios para hayar la solución a un problema. Estos recursos son el tiempo y el espacio.
La Teoría de la Computabilidad muestra su interés en expresar problemas como algoritmos sin tener en cuenta la información que necesita de los recursos para ello.
La Máquina de Turing utiliza como referente para abstraer las variaciones sobre los diferentes sistemas computacionales. Se considera como un modelo de máquina isofórmica con respecto a cualquier Sistema Informático.
La Tesis de Church-Turing dice que si la máquina de Turing no puede hayar la solución a un problema,entonces, ninguna computadora lo conseguirá,ya que no existe algoritmo para hayar la solución a un problema. Como consecuencia de esto, estas limitaciones son debidos a los procesos computacionales y no a la tecnología.
Definición de Complejidad
La complejidad se defina como la cantidad de recursos necesarios para hayar la solución a:
- Un problema
- Un algoritmo
- Un proceso de cálculo
Los dos recursos principales que se analizan son:
- Tiempo (pasos, operacciones elementeales, ...). La complejidad para hayar la solución a este problema se llama: Complejidad temporal
- Espacio (celdas, posiciones de memoria). La complejidad para haya la solución a este tipo de problemas se llama: Complejidad espacial
Esta definición varía en función del sistema computacional.El sistema de referencua es considerado la Máquina de Turing.
Clases de Complejidad
Clase P
Problemas de decisión computables: Por una Máquina de Turin o un algoritmo determinista. Estos se solucionan en tiempo polinómicos.
Clase NP
Problemas de decisión No computables:
Por una Máquina de Turin o un algoritmo determinista. Estos se solucionan en tiempo polinómicos.
Problemas NP difícil
Este tipo de problemas se pueden reducir en tiempo polinómico problemas NP
NP-Completo
Son NP difíciles y están en NP.
Ejemplos de problemas:
- Viajante de comercio
- Ciclo hamiltoniano
- Buscaminas
- Tetris
- Sudoku
Para aclarar dudas se va a exponer un pequeño resumen. En definitiva los problemas NP están formador por problemas P Y NP-Completo
Más tipos de Complejidad
Complejidad temporal
- EXPTIME : complejidad exponencial
- NEXPTIME : tiempo exponencial para una máquina deterninista
Complejidad espacial
- L : espacio logarítmico con tiempo ilimitado
- NL : espacio logarítmo en máquina no determinista
- PSPACE : espacio polinómico en máquina no deternista
- EXPSPACE: espacio exponencial con tiempo ilimitado
Tipos de Problemas
A continuación se va a clasificar los problemas en función de la complejidad que necesita para resolverse. Se distingue dos tipos y dentro de estos hay varias subtipos.
Problemas Decidibles
Son problemas computables y existe al menos un algoritmo capaz de resolverlos.
Problemas Tratables
Son aquellos que se recuelve por algoritmos de complejidad polinomica.
Problemas Intratables
Problemas que se resuelven por algoritmos con complejidad superpolinómica como por ejemplo la complejidad exponencial.
Estos problemas a pesar de llevar mucho tiempo para su resolución son computables.
Problemas NO Decidibles
Son problemas que no son factibles optener su solución.Aquí distinguimos dos subgrupos.
Problemas NO Computables
Un ejemplo de problema NO Computable lo constituye el famoso problema de Las Torres de Hanoi
Problemas Fuertemente No Computables
Un ejemplo de este lo constituye La Aritmética de PestBurger. Y cualquier algoritmo criptográfico como RSA, DES ...
Búsqueda de Soluciones
Para los problemas No Computables se pueden buscar otros métodos alternativos para llegar la solución. Algunos de ellos son:
- Sistemas Paralelos: estos son sistemas que poseen una arquitectura específica que permite desarrollar SW de Sistemas y aplicaciones que soporten el paralelismo.
- Computación Molecular: trata de representar la información al procesar con molécular orgánicas pues las introducen en un tubo de ensayo para que reaacionesny así logrén conseguir la solución a un problema.
- Computación Cuántica: combina las propiedades físicarsy de las ciencias computaciones para tratar de hayar la solución a problemas NO computables.
Enunciado de algunos problemas
- Camino Hamiltoniano su finalidad es encontrar un camnio que vaya desde un punto de inicio hasta punto final pasando por los demás puntos una sola vez
- Problema del Viajante de Comercio supongamos N ciudades (Cáceres, Badajoz, Villanueva de la Serena...). La distancia entre dos ciudades se representa por una matriz cuadrada de NxN. La distancia entre dos ciudades se encuentra en el valor de cada celda de esta. El objetvo de este problema consiste en encontrar una ruta en la que comenzado y terminando por una ciudad, pase una vez solo por cada una de las ciudades y a la vez se minimice la distancia recorrida por el viajante. Este problema es pareceido al anterior pero además se tiene en cuenta la distancia recorridad para conseguir que sea mínima.
- Problema de las Torres de Hanoi es un juego matemático que a partir de tres varillas verticales y un número indeterminado de discos de diferente tamaño. El juego trata de pasar todos los discos a la tercera varilla colocados de mayor a menor de forma ascendente. Ha de tenerse en cuenta que a mayor cantidad de disco mayor será la complejidad para resolver el problema.
Fuentes
- Computación cuántica
- Computación Molecular
- Teoría de la Computabilidad
- Tesis de Church-Turing
- Augusto Cortéz. Teoría de la Complejidad Computacional y Teoría de la Computabilidad. Rev. investig. sist. inform. RISI 1(1), 102-105, 2002 .pdf
Licencia
|
