Algoritmo

Algoritmia

Ricardo Baeza Yates,

Dpto. de Cs. de la Computación, Univ. de Chile

rbaeza@dcc.uchile.cl , www.baeza.cl

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 usando una

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 ciencia de 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. El

objetivo 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 finalmente se 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 operaciones se 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 en teorí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 un algoritmo 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 Diseño Análisis Programación

Datos: x, p(x) Algoritmo Costo: A(x) Programa

Búsqueda Secuencial

Veamos 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

...