Algoritmia

Introducción
Algoritmo, según la Real Academia, es un conjunto ordenado y finito de operaciones que permite
encontrar la solución a un problema cualquiera. Ejemplos sencillos de algoritmos son una receta de
cocina o las instrucciones para armar una bicicleta. Los primeros algoritmos registrados datan de
Babilonia, originados en las matemáticas como un método para resolver un problema usandouna
secuencia de cálculos más simples. Esta palabra tiene su origen en el nombre de un famoso
matemático y erudito árabe del siglo IX, Al-Khorezmi, a quien también le debemos las palabras
guarismo y álgebra (ver anexo). Actualmente algoritmo se usa para denominar a la secuencia de
pasos a seguir para resolver un problema usando un computador (ordenador). Por esta razón, la
algoritmia o cienciade los algoritmos, es uno de los pilares de la informática (ciencia de la
computación en inglés).
En este artículo veremos distintos tipos de algoritmos y distintas técnicas para resolver problemas a
través de varios ejemplos, muchos de ellos no computacionales. Todos los ejemplos resuelven
variantes de un problema genérico: la búsqueda de información, un dilema que tenemos a diario. Elobjetivo final será encontrar el algoritmo que utilice menos operaciones o gaste menos recursos,
dependiendo del caso.

Diseño y Análisis de Algoritmos
El desarrollo de un algoritmo tiene varias etapas (ver figura). Primero se modela el problema que se
necesita resolver, a continuación se diseña la solución, luego ésta se analiza para determinar su
grado de corrección y eficiencia, y finalmentese traduce a instrucciones de un lenguaje de
programación que un computador entenderá. El modelo especifica todos los supuestos acerca de los
datos de entrada y de la capacidad computacional del algoritmo. El diseño se basa en distintos
métodos de resolución de problemas, muchos de los cuales serán presentados más adelante. Para el
análisis de un algoritmo debemos estudiar cuántas operacionesse realizan para resolver un
problema. Si tenemos un problema x diremos que el algoritmo realiza A(x) operaciones (costo del
algoritmo). Al valor máximo de A(x) se le denomina el peor caso y al mínimo el mejor caso. En la
práctica, interesa el peor caso, pues representa una cota superior al costo del algoritmo. Sin
embargo, en muchos problemas esto ocurre con poca frecuencia o sólo existe enteoría. Entonces se
estudia el promedio de A(x), para lo cual es necesario definir la probabilidad de que ocurra cada x,
p(x), y calcular la suma ponderada de p(x) por A(x). Aunque esta medida es mucho más realista,
muchas veces es difícil de calcular y otras ni siquiera podemos definir p(x) porque no conocemos
bien la realidad o es muy difícil de modelar. Si podemos demostrar que no existe unalgoritmo que
realice menos operaciones para resolver un problema, se dice que el algoritmo es óptimo, ya sea en
el peor caso o en el caso promedio, dependiendo del modelo. Por esta razón, el análisis realimenta
al diseño, para mejorar el algoritmo.

Problema

Modelo

Datos: x, p(x)

Diseño

Algoritmo

Análisis

Costo: A(x)

Programación

Programa

Búsqueda SecuencialVeamos un primer ejemplo. Supongamos que hemos comprado el número x de una rifa en que se
sortean n premios. El día del sorteo estamos presentes mientras se escogen los números ganadores.
¿Cuánto tiempo esperaremos para saber si hemos ganado algún premio? Analicemos el modelo.
Podemos decir que el tiempo es proporcional a cada número premiado, así que nuestra operación
básica será comparar x concada número premiado. Enumeraremos la secuencia de números
premiados de 1 a n y usaremos la notación número(j) para el j-ésimo número premiado. El diseño
de la solución es inmediato: comparamos x con cada número premiado hasta que ganamos o no
quedan más números. Veamos el análisis del peor caso: compararemos n veces, ya sea cuando
ganamos con el último número o si el sorteo termina y no...