Algoritmia

Página 1

Ricardo Baeza Yates,

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

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

El desarrollo de un algoritmo tiene varias etapas. 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.

https://users.dcc.uchile.cl/~rbaeza/inf/algoritmia.pdf