Algoritmia

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 lasecuencia 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 losejemplos 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, acontinuació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 unacota 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 siquierapodemos 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 ModeloDiseñ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 que eltiempo es proporcional 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:...