Ingenieria

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 primerosalgoritmos 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 depasos 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 ejemplosresuelven 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 sediseñ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 cualesserá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 delalgoritmo. 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 noconocemos 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ónDatos: 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 que el tiempo esproporcional a cada número premiado, así que nuestra operación básica será comparar x con cada 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...