Los Algoritmos

Los Algoritmos

¿QUÉ SON 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.

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.

 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.

Los paradigmas de la programación funcional y de la programación lógica describen el concepto de algoritmo en una forma ligeramente diferente.

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).

La máquina de Turing

Una máquina de Turing es un autómata que se mueve sobre una secuencia lineal de datos. En cada instante, la máquina puede leer un único dato de la secuencia (generalmente un carácter) y realizar ciertas acciones en base a una tabla que tiene en cuenta su estado actual (interno) y el último dato leído. Entre las acciones que puede realizar, está la posibilidad de escribir nuevos datos en la secuencia, recorrer la secuencia en ambos sentidos y cambiar de estado dentro de un conjunto finito de estados posibles.

Un sistema Turing completo es aquel que puede simular el comportamiento de una máquina de Turing. Dejando de lado las limitaciones impuestas por la capacidad de almacenamiento o la memoria, las computadoras actuales y los lenguajes de programación de propósito general definen sistemas Turing completos.

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.

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 susentradas 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

Especificación de algoritmos

• 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 cargade ambigüedades, podemos expresar nuestro algoritmo en forma más precisa:

Algoritmo: BuscarMaximo

• Datos de entrada: l1 ... ln

• Datos de salida: m

• Precondiciones:

n ∈ N

n > 0

l i ∈ Q ∀ 1 ≤ i ≤ n

• Poscondiciones:

m ∈ Q

m ≥ l i ∀ 1 ≤ i ≤ n

No cabe duda de que esta especificación es más rigurosa, aunque seguramente es más difícil de entender para quien no domina esta clase de expresiones matemáticas.

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.

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

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.

El ciclo principal del algoritmo Buscar Maximo recorre una vez toda la lista de n elementos para determinar cuál es el mayor. Su bloque principal (el delimitado entre Mientras y Fin Mientras) se repite tantas veces como elementos haya en la lista. Por lo tanto, se dice que su complejidad es O(n) o que tiene complejidad lineal, ya que el tiempo que demora en ejecutarse el algoritmo aumentará proporcionalmente a la cantidad de elementos que tenga la lista.

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

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–

• 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.

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.

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 perfectason excesivos.

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).

LOS ALGORITMOS EN LA HISTORIA

El origen del término "algoritmo" se remonta al siglo IX y

se le atribuye su invención al matemático árabe Abu Ja’far

Muhammad ibn Musa al-Khwarizmi

La palabra algoritmo se refería originalmente sólo a las reglas de la aritmética con números arábigos. Recién en el siglo XVIII se expandió su significado para abarcar en su definición a toda clase de procedimientos utilizados con el propósito de resolver problemas o realizar determinadas tareas.

El primer caso de una algoritmo escrito para una computadora se considera que son las notas escritas por Ada Byron en 1842 para el motor analítico de Charles Babbage. Por esta razón, se considera a Ada Byron como la primera programado ra de la historia. Sin embargo, dado que Babbage nunca terminó su motor analítico, el algoritmo jamás llegó a implementarse.