Conocimientos - La divisa del nuevo milenio - Introducción a los Algoritmos

Un algoritmo es un conjunto finito de instrucciones precisas que realizan una tarea, la cual, dado un estado inicial, culminará por arrojar un estado final reconocible. Esta definición asume que la ejecución del algoritmo concluye en algún momento, dejando fuera los procedimientos que ejecutan permanentemente sin detenerse. Para incluir a éstos en la definición, algunos autores prefieren obviar la condición de que la ejecución concluya. Con lo cual basta con que un procedimiento sea una secuencia de pasos que puede ser ejecutada por una entidad para que se lo considere algoritmo. En el caso que no haya un estado final reconocible, el éxito del algoritmo no puede definirse como la culminación del proceso con un resultado significativo. En cambio, se requiere una definición de éxito que contemple secuencias ilimitadas de resultados, por ejemplo, un sistema de compresión/descompresión de datos en tiempo real (como los utilizados en el manejo de voz sobre IP); en este caso, el algoritmo no define por sí mismo la finalización del proceso, debiendo seguir su funcionamiento mientras haya datos para procesar. El éxito del algoritmo estará dado por el hecho de que los datos, una vez descomprimidos, sean iguales que antes de comprimirse.

El concepto de algoritmo se ilustra frecuentemente comparándolo con una receta: al igual que las recetas, los algoritmos habitualmente están formados por secuencias de instrucciones que probablemente se repiten (iteran) o que requieren decisiones (comparaciones lógicas) hasta que completan su tarea. Un algoritmo puede no ser correcto, con lo cual, por más que sus pasos se lleven a cabo correctamente, el estado final no será el esperado.

Normalmente, cuando un algoritmo está asociado con el procesamiento de información, se leen datos de una fuente o dispositivo de entrada, se procesan y se emiten por un dispositivo de salida, o bien se almacenan para su uso posterior. Los datos almacenados se consideran parte del estado interno de la entidad que ejecuta el algoritmo.

Dado que un algoritmo es una lista precisa de pasos, el orden de ejecución será casi siempre crítico para su funcionamiento. En general, se asume que las instrucciones se enumeran explícitamente, y deben ejecutarse “desde arriba hacia abajo”, lo cual se establece más formalmente según el concepto de flujo de control. Esta forma de “pensar” el algoritmo asume las premisas del paradigma de programación imperativa. Dicho paradigma es el más común, e intenta describir las tareas en términos “mecánicos” y discretos. Los paradigmas de la programación funcional y de la programación lógica describen el concepto de algoritmo en una forma ligeramente diferente.

Hasta aquí hemos dado una definición ciertamente informal del concepto de algoritmo. Para definirlo en forma matemáticamente precisa, Alan Mathison Turing –famoso matemático inglés (1912-1954), cuyas contribuciones en el campo de la matemática y de la teoría de la computación le han valido ser considerado uno de los padres de la computación digital– ideó un dispositivo imaginario al que denominó máquina de computación lógica (LCM, Logical Computing Machine), pero que ha recibido en su honor el nombre de máquina de Turing. Lo que confiere a este supuesto dispositivo su extraordinaria importancia es que es capaz de resolver cualquier problema matemático, a condición de que el mismo haya sido reducido a un algoritmo. Por este motivo, se considera que algoritmo es cualquier conjunto de operaciones que pueda ser ejecutado por la máquina de Turing (o, lo que es lo mismo, por un sistema Turing completo, tal como se explica más adelante).

Especificación de algoritmos

Para cualquier proceso computacional, el algoritmo correspondiente debe estar rigurosamente definido, es decir, debe especificarse la forma en que se aplica a cada posible circunstancia que pueda surgir. Todos los casos deben estar contemplados, y el criterio que determina cada uno de ellos debe ser claro y computable.

En general, no existe un único algoritmo para cada problema que se quiere resolver. Diferentes algoritmos pueden completar la misma tarea, requiriendo cada uno diferentes cantidades de tiempo, espacio o esfuerzo. Sin embargo, la especificación puede ser exactamente la misma para todos ellos.

Para especificar un algoritmo de forma tal que su implementación sea correcta –es decir, que haga exactamente lo que se espera de él– y que, a la vez, pueda implementarse con diferentes lenguajes o herramientas, un método consiste en definir sus entradas y salidas, con sus correspondientes precondiciones y poscondiciones.

A modo de ejemplo, veamos la especificación de un algoritmo que busca el máximo número en una lista:

Algoritmo: BuscarMaximo

• Datos de entrada: una lista l de n elementos numéricos.
• Datos de salida: un número m.
• Precondiciones:
n es un número natural.
n es mayor que cero (o sea, la lista no puede estar vacía).
todos los elementos de l son números racionales.
• Poscondiciones:
m es un número racional.
m es el mayor de los elementos de l.

Esta especificación define de manera inequívoca cómo debe funcionar nuestro algoritmo. Sin embargo, por estar expresado en lenguaje natural –con toda su carga de ambigüedades, puede prestarse a confusiones (quizá no en este caso, porque es un algoritmo muy simple, pero sí para casos más complejos). Por ese motivo, conviene expresar las especificaciones en un lenguaje más riguroso, como por ejemplo, las expresiones matemáticas usadas en el cálculo de predicados lógicos. Con tales consideraciones, podemos expresar nuestro algoritmo en forma más precisa:

Algoritmo: BuscarMaximo
• Datos de entrada: l1 ... ln
• Datos de salida: m
• Precondiciones:

• Poscondiciones:

Implementación de algoritmos

La implementación es el proceso que toma la especificación del algoritmo y la traduce a una forma que pueda aplicarse a la solución del problema para el cual fue diseñado. La implementación puede tomar formas muy diversas: podría significar la construcción de un circuito eléctrico o de un dispositivo mecánico que cumpla con las condiciones especificadas. Pero restrinjamos la definición al campo de la informática: en este sentido, implementar significa traducir el algoritmo a un lenguaje que pueda ser interpretado por un motor de ejecución.

Para el análisis y estudio de los algoritmos usualmente se utiliza una forma abstracta de implementación, la cual no utiliza un lenguaje de programación específico, sino que emplea formas de representar el algoritmo que luego pueden ser directamente traducidas a un lenguaje en particular. Algunas de estas formas son los diagramas de flujo, los diagramas de bloques y el seudo código. Este último es “casi” un lenguaje imperativo, con la salvedad de que no toma en cuenta los tipos de datos y, además, sus instrucciones pueden estar en idioma español o en cualquier otro, ya que no serán interpretadas por ninguna computadora. Un sencillo ejemplo de la implementación en seudo código de nuestro algoritmo BuscarMaximo sería la siguiente:

Función BuscarMaximo(lista)
   Mayor = lista(1)
   Contador = 2
   Mientras Contador < longitud(lista) hacer
    Si lista(Contador) > Mayor entonces
      Mayor = lista(Contador)
     Fin Si
     Contador = Contador + 1
     Fin Mientras
     Devolver Mayor
Fin Función

El seudo código tiene la ventaja de poder derivarse en casi cualquier lenguaje imperativo, como el Pascal o el C.

Eficiencia de los algoritmos

La especificación de un algoritmo puede incluir consideraciones sobre su eficiencia, dado que una implementación incorrecta puede hacer que demore en ejecutarse mucho más tiempo de lo aceptable. Para ello se utilizan notaciones que expresan la complejidad de los algoritmos en función del volumen de datos a procesar. Una de estas notaciones es la denominada “la gran O”, que indica la cantidad de veces que el algoritmo debe repetir su bloque principal de instrucciones para hacer su trabajo.

Clases de algoritmos

Una forma de clasificar los algoritmos consiste en diferenciarlos por su metodología de diseño. A continuación se presenta una síntesis de las metodologías más comunes, aplicables cada una a diferentes clases de problemas:

• Fuerza bruta: los algoritmos de fuerza bruta resuelven el problema con la estrategia más obvia de solución, que no siempre es la mejor según el número de operaciones que se requiere.
• Divide and conquer (divide y reinarás): esta metodología divide las instancias del problema a resolver en instancias cada vez más pequeñas, usualmente en forma recursiva, hasta llegar a una instancia en que el problema es resoluble en forma trivial o con unas pocas instrucciones. Los algoritmos de búsqueda binaria son un ejemplo de la metodología divide and conquer (Figura 1).

Figura 1. La metodología divide and conquer divide el problema en instancias cada vez más pequeñas, hasta llegar a una en que la solución es trivial.

• Programación dinámica: cuando un problema presenta una subestructura óptima–o sea, cuando la solución óptima de un problema se obtiene a partir de las soluciones óptimas de sus subproblemas–, se encuentra la solución resolviendo primero los subproblemas más sencillos y luego utilizando esas subsoluciones para resolver problemas incrementalmente difíciles. Por ejemplo, si se tiene una serie de puntos (definidos por coordenadas x, y) que delimitan una región, y se necesita saber si otro punto se encuentra dentro o fuera de esa región, una forma de resolver el problema consiste en comenzar formando cuadrados con puntos contiguos, para luego formar figuras cada vez más grandes y, por cada figura, determinar si el punto está dentro o fuera de ella (Figura 2). En cada paso se aprovecha la información de los pasos anteriores, hasta que, al completar todos los puntos, se obtiene el resultado del problema.

Figura 2. El problema de determinar si un punto está dentro o fuera del área delimitada por una serie de otros puntos se resuelve naturalmente por programación dinámica.

• Programación lineal: para resolver un problema utilizando programación lineal, se plantea una serie de inecuaciones y luego se busca maximizar (o minimizar) las variables, respetando las inecuaciones. Muchos problemas pueden plantearse en la forma de un conjunto de inecuaciones, para luego resolverlos utilizando un algoritmo genérico, como por ejemplo, el denominado método Simplex (en la sección de Servicios al lector se detallan sitios donde obtener más información sobre este método).
• Búsqueda y enumeración: muchos problemas (como por ejemplo, un juego de ajedrez) pueden modelarse con grafos y resolverse a partir de un algoritmo de exploración del grafo. Tal algoritmo especificará las reglas para moverse en el grafo en busca de la solución al problema. Esta categoría incluye también algoritmos de backtracking (vuelta atrás), los cuales van ensayando distintos caminos con posibles soluciones y vuelven atrás cuando no las encuentran. Por ejemplo, para encontrar la salida en un laberinto, cada vez que se llega al final de un camino se vuelve atrás hasta la última bifurcación, para probar con las distintas alternativas de esa bifurcación.
• Algoritmos heurísticos: el propósito de estos algoritmos no es necesariamente encontrar una solución final al problema, sino encontrar una solución aproximada cuando el tiempo o los recursos necesarios para encontrar la solución perfecta son excesivos. Muchos sistemas antivirus utilizan métodos heurísticos para detectar conductas de programas que podrían estar actuando en forma maliciosa.
• Algoritmos voraces: seleccionan la opción de solución (solución local) que tenga un costo menor en la etapa de solución en la que se encuentran, sin considerar si esa opción es parte de una solución óptima para el problema completo (solución global).

Fuente: tectimes.com