El concepto de algoritmo forma parte esencial de los fundamentos de la computación. La matemática discreta y en particular la matemática constructivista, son tan antiguas como la propia matemática, y trata aquellos aspectos para los cuales existe una solución constructivista; esto es, no se conforma con demostrar la existencia de solución, sino que se pregunta cómo encontrar dicha solución.
El término algoritmo es muy anterior a la era de la computación: proviene hasta donde se sabe de Mohammed al-Khowârizmî (cuyo apellido se tradujo al latín en la palabra algoritmus), quien era un matemático persa del siglo IX que enunció paso a paso las reglas para sumar, restar, multiplicar y dividir números decimales. En este mismo contexto también debe recordarse el algoritmo de Euclides obtenido aproximadamente 300 años antes de nuestra era.
Definición y conceptos.
En términos generales se define un
algoritmo, como el
método para resolver un determinado problema, donde el ejecutor de las instrucciones que realiza la tarea correspondiente se denomina
procesador.
Existen algoritmos que describen toda clase de procesos, por ejemplo:
- Las recetas de cocina.
- Las partituras musicales.
- Cambiar la llanta de un auto, etc.
El procesador realiza dicho proceso siguiendo o ejecutando el algoritmo correspondiente. La ejecución de un algoritmo requiere de la ejecución de cada uno de los pasos o instrucciones que lo conforman.
Por otro lado, un algoritmo debe estar expresado de tal forma que el procesador lo entienda para poder ejecutarlo. Se dice que el procesador es capaz de interpretar un algoritmo, si el procesador puede:
- Entender lo que significa cada paso.
- Llevar a cabo (procesar) la sentencia correspondiente.
Esto significa que para que un algoritmo pueda ser correctamente ejecutado, cada uno de sus pasos debe estar expresado de tal forma que el procesador sea capaz de entenderlos y ejecutarlos adecuadamente.
Ahora bien, el término de algoritmo puede tener diferentes connotaciones dependiendo del contexto del que se hable; en nuestro caso el contexto es el de programación, esto es, el de utilizar a la computadora como herramienta para la resolución de problemas.
En este sentido, se definirá un algoritmo como un conjunto finito de instrucciones que especifican la secuencia ordenada de operaciones a realizar para resolver un problema.
Con base en lo anterior, si el procesador del algoritmo es una computadora, el algoritmo debe estar expresado en forma de un programa, el cual se escribe en un lenguaje de programación. Un lenguaje de programación es lenguaje artificial que se utiliza para expresar programas de computadora, y a la actividad de expresar un algoritmo en un lenguaje de programación determinado se le denomina programar.
Cada paso del algoritmo se expresa mediante una instrucción o sentencia en el programa, por lo que un programa consiste en una secuencia de instrucciones en donde cada una de las cuales especifica ciertas operaciones a realizar por parte de la computadora.
Uso de la computadora en la resolución de problemas a través de programas.
En general, se escriben algoritmos para resolver problemas que no son tan fáciles de resolver a primera vista, y de los que se necesita especificar el conjunto de acciones que se llevarán a cabo para su resolución. Además, como lo que interesa es resolver problemas utilizando a la computadora como medio, los algoritmos tendrán la finalidad de ser traducidos en programas, razón por la cual es conveniente el mencionar el proceso general de resolución de problemas a través de programas, mismo que abarca desde que se dispone de un algoritmo, hasta que la computadora lo ejecuta.
El proceso general de resolución de problemas a través de programas se muestra a continuación:
- Algoritmo.
- Programación.
- Programa en lenguaje de alto nivel.
- Traducción.
- Programa en código de máquina.
- Ejecución.
Existen diferentes formas de traducir un algoritmo a un programa. En el proceso mostrado con anterioridad, se ha escogido la representación en un lenguaje de programación de alto nivel debido a que los lenguajes de éste tipo proporcionan un mayor nivel de abstracción y semejanza con el lenguaje natural (inglés).
Es importante recordar que las computadoras tienen su propio lenguaje (binario), por lo que es necesario un proceso de traducción (realizado por el compilador o intérprete), para que se traduzca el conjunto de sentencias escritas en un lenguaje de programación de alto nivel (código fuente), a un conjunto de instrucciones que sean comprensibles para la computadora (código de máquina o código objeto).
Aunque lo que sucede en cada una de las etapas del proceso involucrado es algo mucho más complejo que lo que aquí se ha sucintamente descrito, si todo está bien, el resultado de dicho proceso será la ejecución del programa basado en el algoritmo.
Teniendo en consideración lo anterior, debería ser claro que el papel del algoritmo es fundamental, ya que sin algoritmo no puede haber programas, y sin programas, no hay nada que ejecutar en la computadora.
Por otro lado, es importante también mencionar y enfatizar que un algoritmo es independiente tanto del lenguaje de programación en que finalmente se transcribe, como de la computadora en la que se ejecuta, por lo que no deberían ser diseñados en función de ello.
Finalmente, otro aspecto muy importante dentro de los algoritmos es el del análisis. El análisis y diseño formal de algoritmos es una actividad intelectual considerable y no trivial, ya que el diseño de buenos algoritmos requiere creatividad e ingenio por un lado, y por el otro que, en general, no existe un algoritmo que diseñe un algoritmo a partir de la descripción de un determinado problema. El análisis formal de algoritmos está fuera de los alcances de este blog.
Cinco importantes condiciones de un algoritmo.
Los algoritmos, además de ser un conjunto finito de reglas que dan lugar a una secuencia de operaciones para resolver un tipo específico de problemas, deben cumplir con cinco importantes condiciones [Abellanas] mismas que son descritas a continuación:
- Finitud: un algoritmo tiene que acabar siempre tras un número finito de pasos (un procedimiento que tiene todas las características de un algoritmo, salvo que posiblemente falla en su finitud, se conoce como método de cálculo.).
- Definibilidad: cada paso de un algoritmo debe definirse de modo preciso; las acciones a realizar deben estar especificadas para cada caso rigurosamente y sin ambigüedad.
- Conjunto de entradas: debe existir un conjunto específico de elementos donde cada uno de ellos, constituye los datos iniciales de un caso particular del problema que resuelve el algoritmo. A este conjunto de elementos se le denomina conjunto de entradas del algoritmo.
- Conjunto de salidas: debe existir un conjunto específico de elementos donde cada uno de ellos, constituye la salida o respuesta que debe obtener el algoritmo para los diferentes casos particulares del problema. A este conjunto de elementos se le denomina conjunto de salidas del algoritmo, y para cada entrada del algoritmo debe existir una correspondiente salida asociada, misma que constituye la solución al problema particular determinada por dicha entrada.
- Efectividad: un algoritmo debe ser efectivo. Todas las operaciones a realizar por el algoritmo deben ser lo bastante básicas para poder ser efectuadas de modo exacto y en un lapso de tiempo finito por el procesador que ejecute el algoritmo.
Las cinco condiciones anteriores reducen significativamente el espectro tan amplio que hasta ahora se ha manejado como algoritmo. Así por ejemplo, aunque una receta de cocina podría considerarse como un algoritmo, es común encontrar expresiones imprecisas en ella que dan lugar a ambigüedad (violando la condición 2), tales como “añádase una pizca de sal”, “batir suavemente", etc., invalidando con ello la formalidad de un algoritmo dentro del contexto que nos compete e interesa.
Estructura de un algoritmo.
Aunque no existe una única forma de representar un algoritmo (vea [Abellanas}, [Deitel], [Joyanes], [Ullman], [Wirth], etc., cada uno tiene formas diferentes aunque esencialmente iguales de representar un algoritmo), la estructura general de un algoritmo debería ser como la que se muestra a continuación:
Algoritmo <nombre_del_algoritmo>
Inicio
definición de constantes
definición de variables
sentencia 1
sentencia 2
.
.
.
sentencia n
Fin
Cuando se escribe un algoritmo es recomendable que, aunado a la estructura general y partiendo de la descripción del problema y de un análisis inicial, se determine la entrada, la salida y el proceso general de solución del algoritmo.
Con la finalidad de mostrar dicho procedimiento, a continuación se describirá brevemente un ejemplo clave y clásico en los algoritmos: el algoritmo de Euclides.
Algoritmo de Euclides: definición del problema.
Dados dos números enteros positivos
m y
n, encontrar su máximo común divisor (MCD), es decir, el mayor entero positivo que divide a la vez a
m y a
n.
Entrada: dos números enteros positivos m y n.
Salida: un número que representa el MCD (Máximo Común Divisor) de m y n.
Proceso: la solución está basada en el residuo de la división de los operandos m y n. Si el residuo es 0 entonces hemos terminado; en otro caso, habrá que hacer intercambio de valores y continuar con el proceso.
El ejemplo del algoritmo de Euclides se utilizará para mostrar el proceso de solución que se debería seguir para resolver un problema. A partir de este análisis inicial, la idea será entonces ir especificando la entrada, la salida y el proceso de solución en un refinamiento progresivo, de tal forma que eventualmente se genere un algoritmo más específico, definido, y funcional.
Pruebas de algoritmos.
Una vez que se ha generado un algoritmo que parece correcto, una de las partes más importantes dentro de su diseño es la referente a las pruebas. La fase de verificación y validación del algoritmo con respecto a los datos de entrada, es un aspecto sumamente importante de su diseño.
Una vez que se tiene una solución algorítmica de un problema, no se debería suponer que funcionará bien siempre. En el diseño del algoritmo se deben considerar al menos algunos casos de prueba. En este sentido, es habitual que el dominio de trabajo de un algoritmo sea un conjunto de elementos, en cuyo caso sería deseable el saber por ejemplo, ¿cómo se comporta el algoritmo en los límites del conjunto?, dado un mismo dato de entrada, ¿se obtiene siempre la salida esperada?, dado un mismo dato de entrada, ¿se obtiene siempre la misma salida?, etc.
La fase de prueba de los algoritmos es una parte fundamental dentro
del diseño del mismo, y debe ser una práctica habitual de cualquier
programador, ya que es una importante técnica de
programación, y un principio esencial de la Ingeniería de Software. Es
una grave defecto, y fuente de múltiples calamidades, el realizar las
pruebas una vez que el programa ha sido realizado, con el programa
pueden extenderse las pruebas, hacerse más pruebas, repetir las hechas
al algoritmo, pero no esperar a hacer pruebas hasta que el programa esté
hecho.
Las técnicas y métodos formales de pruebas están fuera de los alcances de este blog, pero a este nivel, es suficiente saber que es conveniente realizar pruebas sobre los algoritmos desarrollados.
En la entrada
Pruebas de escritorio se muestra un ejemplo de la realización de dicho tipo de pruebas para el algoritmo de Euclides.
