Un problema es resuelto algorítmicamente, si se puede
escribir un programa que pueda producir la respuesta correcta de forma que para
cualquier posible entrada, el programa puede ser ejecutado el tiempo (finito)
suficiente para resolverlo y cuenta además con el espacio requerido para
resolverlo.
A principios del siglo XX, hubo una gran actividad para
formalizar y estudiar el concepto de algoritmo. Los algoritmos se consideraron
desde entonces como un conjunto de instrucciones simples, las cuales pueden ser
interpretadas fácilmente, de modo que al seguirlas se resuelva un problema ó se
calcule el valor de una función.
Dentro de los investigadores de principios del siglo XX,
destaca Allan Turing, por dos razones:
1) El desarrollo de la Máquina de Turing y su relación con
los algoritmos. Dicha relación establece que todo algoritmo puede ser
conceptualizado como una máquina, que ejecuta sus instrucciones.
2) La demostración de que no se puede resolver el problema
denominado "Halting Problem". Este problema consiste en determinar si
existe ó no un algoritmo que determine si un programa arbitrario de
computadora, eventualmente termina para una entrada cualquiera del programa. De
acuerdo con Turing no existe ningún programa de computadora que resuelva este
problema.
Estos dos aspectos llevaron al desarrollo de la Teoría de la
Computabilidad (TC). Esta área está ahora conformada por Teoría de la
Computación, Análisis de Algoritmos, Teoría de la Información y Lógica
Computacional.
Se hace notar que el hecho de que exista un procedimiento
para resolver un problema, puede o no ser suficiente para que este sea resuelto
realmente en una computadora. Se podría, por ejemplo pensar en un procedimiento
para que una máquina juegue ajedréz perfecto, tomando en cuenta lo siguiente:
1) Existe solo un número finito de formas de arreglar las
piezas de ajedrez sobre el tablero.
2) Bajo ciertas reglas, el juego termina después de un
número finito de movimientos.
3) Considerar para cada posible movimiento de la
computadora, todas las posibles respuestas del oponente y, para cada una de
estas, las posibles respuestas de la computadora y, así sucesivamente, hasta
que cada secuencia alcance el final. Entonces, conociendo el último resultado
de cada movimiento, todo lo que se tendría que hacer es escoger el mejor
movimiento inicial.
Sin embargo, hay un inconveniente serio en el procedimiento
anterior, el número de posibles arreglos de piezas es alrededor de 10 50, de
modo que un buen programa podría tardar varios miles de años!!.
Como consecuencia, no obstante que existe un procedimiento
para el juego perfecto de ajedrez, no existe aún un algoritmo, no obstante que
alguien podría escribir un programa siguiendo dicho procedimiento
Como el anterior, hay muchos problemas, para las cuales se
puede escribir un procedimiento y por tanto podríamos decir que pueden ser
resueltas; es decir que se pueden escribir programas para dichas aplicaciones y
que por tanto podríamos pensar que existen algoritmos para ellos. Sin embargo,
los requerimientos de tiempo y espacio de almacenamiento son tan grandes que
ésos programas no son de importancia práctica. Estos aspectos se estudian en un
área denominada Complejidad Computacional y, a la cual le dedicaremos una
sesión mas adelante.
La Complejidad Computacional cubre varios aspectos; una de
ellas trata con aspectos formales, que tratan sobre las bases matemáticas para
probar la computabilidad de funciones computables. Esto es de interés para
saber si en teoría, para un problema existe o no un algoritmo. Otro aspecto
tiene que ver con la eficiencia de los algoritmos desde el punto de vista de
tiempo y espacio. En este último aspecto, se centra el Análisis de Algoritmos.
El análisis de algoritmos estudia de esta forma en dos aspectos:
1) El análisis de problemas específicos.
2) El análisis de algoritmos específicos.
Autor: Janet Alvarez Cruz (2004)
