Algoritmos y sus representaciones
El concepto de algoritmo es uno de los conceptos fundamentales de la Ciencia de la Computación y apareció mucho antes de que surgiesen las computadoras y vino a ser una de las nociones fundamentales de la matemática.
El término algoritmo se deriva del nombre de una matemático que vivió en el siglo IX, en Uzbekistán, llamado Al-Jwarizmi o Al-Khowarizmi, el cual, entre sus trabajos escribió un libro que trataba sobre las reglas para efectuar operaciones aritméticas.
De manera informal podemos definir el término algoritmo como:
Un conjunto finito de reglas (pasos u órdenes) que indican una secuencia de operaciones a ejecutar para alcanzar un resultado que soluciona un problema dado, esta secuencia de pasos debe poder ejecutarse aunque no se tenga conocimiento del problema que se resuelve.
Como se ve en la definición muy asociado al concepto de algoritmo está el concepto de “ejecutor” o “procesador” del algoritmo que es el ente que ejecuta los pasos que el algoritmo describe. El algoritmo es la guía de acción para el ejecutor; indica en una forma precisa e inteligible al ejecutar que ha de desarrollar una sucesión determinada de acciones para lograr el objetivo o solucionar un problema.
Ejemplo 1:
Se quiere hallar el área de la figura siguiente para una valor racional dado de la variable x, esto se puede hacer ejecutando el algoritmo que sigue:
Algoritmo1
Paso 1: Multiplicar el valor de x por sí mismo y poner el resultado en a.
Paso 2: Multiplicar el valor de a por 2 y poner el resultado en b.
Paso 3: Multplicar el valor de x por 3 y poner el resultado en c.
Paso 4: Sumar el valor de b con el valor de c y poner el resultado en r. En r tenemos el resultado final
Observar que se está evaluando la función f(x)= 2×2 + 3x que es la que permite calcular el área de la figura (área del rectángulo x.2x más el área del triángulo 2x.3/2).
En este algoritmo se utilizan dos acciones fundamentales o primitivas “multiplicar” y “poner el resultado en”. Se supone, entonces, que el ejecutor del algoritmo conoce estas acciones y puede ejecutarlas.
Las acciones que puede realizar un ejecutor son llamadas acciones primitivas y nuestros algoritmos tienen que estar enunciados a partir de estas acciones.
¿Este algoritmo es único? La respuesta obvia es NO, se puede, también, hacer lo siguiente:
Algoritmo 1a
Paso 1: Multiplicar el valor de x por 2 y poner el resultado en a.
Paso 2: Sumar el valor de a con 3 y poner el resultado en b.
Paso 3: Multiplicar el valor de b por el valor de x y poner el resultado en r. En r tenemos el resultado final.
Observar ahora se está evaluando la función f(x)= (2x + 3)x que en definitiva es la misma función f(x) = 2×2 + 3x.
Si se compara los algoritmos 1 y 1a se observa que el 1a hace que el ejecutor haga menos cantidad de pasos u operaciones, aunque con ambos se obtiene el mismo resultado.
Tener diversas variantes de algoritmos para resolver un mismo tipo de problema, supone la selección del mejor algoritmo para el problema dado; sin embargo en la práctica las cosas no son tan fáciles y en ocasiones no es tan obvio poder escoger un algoritmo entre un grupo, pues la cantidad de operaciones no siempre es el único criterio a tener en cuenta. También debe considerarse, por ejemplo, el tamaño del algoritmo, la claridad con que está expresado, etc. Estos criterios entran en contradicción al hacer el análisis. Una regla que se cumple generalmente en el trabajo de computación , es que cuando se ahorra tiempo se gasta más espacio y viceversa.
Características de los algoritmos
Los algoritmos tienen las siguientes características:
a) Finalidad
Todo algoritmo tiene el objetivo de resolver un tipo de problema y se ejecuta para obtener un resultado que es la solución de un caso particular de ese problema.
b) Orden
Los pasos del algoritmo tienen que ejecutarse en un orden preciso e indicado en el algoritmo. Si este orden se altera, generalmente no se obtiene el resultado deseado.
c) Finitud
El algoritmo tiene que ser finito en tres aspectos:
1. El algoritmo es una secuencia finita de pasos (no tiene sentido ninguno un algoritmo cuya descripción sea infinitamente larga)
2. La ejecución del algoritmo termina después de concluir un número finito de pasos
Nótese que este aspecto es diferente al anterior, pues podría tenerse una cantidad pequeña de pasos en la definición que se ejecutara repetidamente un número infinito de veces. Por ejemplo: “dividir un número racional mayor que 0 por dos repetidamente hasta que el cociente sea cero”.
3. La ejecución de un paso cualquiera del algoritmo tiene que poder ejecutarse en un tiempo finito.
Los tres aspectos relacionados con la finitud del algoritmo plantean que la ejecución de un algoritmo se efectúa en un tiempo finito. En realidad, cuando se habla de algoritmos no es suficiente, en la práctica, que estos sean finitos, sino que además esta finitud no sea muy “grande” . Se dan casos en que para determinados problemas se conocen algoritmos que dan su solución, pero la ejecución de ellos duraría decenas o cientos de años, aún por ejecutores veloces, y obviamente este tiempo sería finito, pero no constituye una forma práctica de resolver el problema.
d) Factibilidad y Claridad
Los pasos de un algoritmo tienen que estar bien definidos. Esto quiere decir que debe quedar claro para cualquier ejecutor qué es lo que hay que hacer en cado paso, que no quede ningún tipo de dudas. No puede existir ambigüedades en la definición de un paso. Además deben ser acciones primitivas que puedan ser realizadas por el ejecutor.
En este sentido el autor D.E Knuth en su libro “El arte de la programación de computadoras” establece una comparación entre algoritmos y recetas de cocina, planteando que estas últimas podrían verse como algoritmos sólo en algunos casos, pues la mayoría ofrece pasos no muy bien definidos para ejecutores que no sepan nada de cocina. A manera de ejemplo pone: “añadir una pizca de sal a la mezcla” y se pregunta ¿qué es una pizca? ¿por donde se añade? Esto hace que el paso no esté completamente definido. Para Knuth pocas recetas de cocinas son verdaderos algoritmos.
e) Entorno
El entorno de un algoritmo es el conjunto de elementos y condiciones que necesita el ejecutor para realizar su trabajo. Se incluyen aquí posibles valores a utilizar, condiciones en que se realiza el proceso, etc.
Ejemplo:
Se quiere hacer un algoritmo para que un comerciante pueda devolver el cambio de 50 pesos si tiene que cobrar $ 20.50
Consideremos tres entornos distintos:
e1: el comerciante dispone sólo de billetes de $10 y $1.
e2: el comerciante dispone sólo de billetes de $ 5 y monedas de 20 ¢ y 5 ¢.
e3: el comerciante dispone de billetes de $10, $5, $1 y monedas de 20 ¢ y 5 ¢.
En el primer caso, el ejecutor (comerciante) no puede, en función de su entorno (las monedas), efectuar el trabajo (dar el cambio). En los otros dos casos sí puede hacerlo.
Por lo tanto el algoritmo que se diseña tiene que tener en cuenta estas condiciones para que pueda ser efectivo.
Representación de algoritmos
Para escribir un algoritmo se utilizan varias notaciones:
a) Lenguaje natural
Se utiliza habitualmente cuando el ejecutor es el hombre y se utiliza su propio lenguaje para describir los pasos. Este es el caso del Algoritmo 1 descrito anteriormente.
b) Pseudocódigo
Es un sistema de designaciones y reglas destinado para la escritura uniforme de algoritmos, no hay reglas fijas, se pueden fijar en el contexto donde se trate.
Por ejemplo se puede convenir que:
Para las operaciones aritméticas se utilizarán los siguientes símbolos: + (suma), -(resta), *(multiplicación), / (división)
Para la operación “poner el resultado en” se utilizará el símbolo ?.
De tal manera que si se quiere expresar: “multiplicar x por 2 y poner el resultado en a” se escribirá:
a ? x * 2
El algoritmo 1 quedará entonces:
Paso 1: a ? x * x
Paso 2: b ? 2 * a
Paso 3: c ? 3 * x
Paso 4: r ? b + c
Para completar este algoritmo totalmente hacen falta dos operaciones que aquí se están asumiendo: conocer que x es un dato y por lo tanto tenemos que conocerlo antes de comenzar y por otro lado saber que el resultado del cálculo se queda en la variable r.
Para ello se introducen dos nuevas operaciones o pasos:
- lectura de datos: se utilizará la palabra leer, seguida de las variables que se tienen como datos iniciales.
- salida de los datos: se utilizará la palabra escribir, seguida de los valores que se desean se den como respuesta.
El algoritmo 1 queda:
Paso 1: leer x
Paso 2: a ? x * x
Paso 3: b ? 2 * a
Paso 4: c ? 3 * x
Paso 5: r ? b + c
Paso 6: escribir r
c) Diagramas de flujo (organigramas)
Esta notación se utilizó mucho en las décadas del 60 y 70, hoy en día ha caído en desuso, pero puede ayudar de manera notable a expresar los algoritmos de forma clara y legible, sin ambigüedades, también se utilizará en el curso.
En la notación se utilizan algunos símbolos:
Símbolo Significado
Inicio o Fin del algoritmo, es escribe la palabra correspondiente para indicar si es inicio o fin.
Operaciones de cálculo
Entrada de datos o salida de resultados, se escribe la palabra leer o escribir
Conector en la misma hoja (se escribe un número dentro)
Conector fuera de hoja (se escribe un número dentro)
Para conectar un símbolo con otro y denotar el flujo del proceso. Cuando el flujo es hacia abajo o a la derecha no se le pone saeta, en los otros casos sí.
De esta forma el algoritmo1 quedaría
d) Diagramas de Actividad
Hoy en día se utiliza mucho en la confección de sistemas un lenguaje denominado UML (Unified Modeling Language) , una de las herramientas que brinda este lenguaje son los llamados Diagramas de Actividad que tienen cierto parecido con los diagramas de flujo vistos anteriormente, aunque se simplifican un poco estos símbolos:
Símbolo Significado
Inicio del algoritmo.
Fin del algoritmo
Operaciones de cálculo
Para conectar un símbolo con otro y denotar el flujo del proceso.
e) Lenguajes de programación
Cuando se desea que el ejecutor del algoritmo sea una computadora, no queda alternativa que escribir el algoritmo en un lenguaje de programación.
Un algoritmo descrito con esta técnica se denomina programa.
Programar es entonces el “arte”(para unos) o la técnica (para otros) de describir algoritmos en un lenguaje de programación.
Ejemplo 2:
Escriba un algoritmo para calcular el volumen de una pirámide de base cuadrada, conociendo que su altura es de H metros y que uno de los lados de la base mide L metros.
Solución:
Volumen pirámide = (Ab H) / 3
Ab = L2
Algoritmo
P1: Leer H y L
P2: AreaBase ? L*L
P3: Volumen ? AreaBase * H / 3
P4: Escribir Volumen
Expresar el algoritmo como un diagrama de actividades.
Conclusiones
En el presente material se estudió:
- El concepto de algoritmo
- Características generales: Finalidad, Orden, Finitud, Factibilidad y Claridad, Entorno
- Formas de representar un algoritmo: lenguaje natural, pseudocódigo, diagramas de flujos, programas.