Algoritmia Dise o y An lisis de Algoritmos

Algoritmia 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 deprogramació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 endistintos 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 serealizan 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 denominael 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 estoocurre 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), ycalcular 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) porqueno 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 diceque 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.