Capítulo 1 - Conceptos Básicos: Definición de algoritmo.

Un algoritmo es un conjunto finito de instrucciones no ambiguas y efec­tivas que indican cómo resolver un problema, producen al menos una salida, reciben cero o más entradas y, para ejecutarse, necesitan una cantidad finita de recursos.


Una instrucción es no ambigua cuando la acción a ejecutar está perfecta­mente definida, por ejemplo, instrucciones del tipo:

x <-- log(0) ó x<-- (10 o 35)/3

no pueden formar parte de un algoritmo.


Una instrucción es efectiva cuando se puede ejecutar en un intervalo finito de tiempo, por ejemplo, las instrucciones

x <— 2 + 8, mensaje <— Une('Hola', 'Mundo')

son efectivas, mientras que

x <— cardinalidad(números naturales)

no lo es.

Si un conjunto de instrucciones tiene todas las características de un al­goritmo, excepto ser finito en tiempo se le denomina proceso computational. Los sistemas operativos son el mejor ejemplo de proceso computacional, pues están diseñados para ejecutar tareas mientras las haya pendientes, y cuando éstas se terminan, el sistema operativo entra en un estado de espera, hasta que llegan más, pero nunca termina.

Se asume que un problema tiene solución algorítmica si además de que el algoritmo existe, su tiempo de ejecución es razonablemente corto. Por ejem­plo, es posible diseñar un algoritmo para jugar ajedrez que triunfe siempre: el algoritmo elige la siguiente tirada examinando todas las posibles secuencias de movimientos desde el tablero actual hasta uno donde sea claro el resultado y elige la tirada que le asegure el triunfo; el pequeño inconveniente de este algoritmo es que dicho espacio de búsqueda se ha estimado en 100040 tableros por lo que puede tardarse miles de años en tomar una decisión. Por lo tanto, para fines prácticos se considera que si un problema tiene una solución que toma años en computar, dicha solución no existe.

Considérese ahora el problema de ordenar un conjunto de valores, si el conjunto tiene 2 elementos es más fácil resolverlo que si tiene 20, análoga­mente un algoritmo que resuelva el problema tardará más tiempo mientras más grande sea el conjunto y requerirá una cantidad de memoria mayor para almacenar los elementos del conjunto.

En general la cantidad de recursos que consume un algoritmo para re­solver un problema se incrementa conforme crece el tamaño del problema. Dependiendo del problema en particular, uno o varios de sus parámetros será elegido como tamaño del problema. Haciendo una cuidadosa observación, es relativamente fácil efectuar una elección atinada.

En la Figura 1 se presenta una serie de problemas y una sugerencia acerca del parámetro que se puede elegir como tamaño del problema.

Referencias: http://docencia.izt.uam.mx/pece/pagina_academica/AA/