Algoritmia

Ricardo Baeza Yates, Dpto. de Cs. de la Computación, Univ. de ChileAlgoritmo, 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