Importancia de los Algoritmos.

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)