Diseño de Algoritmos

Algoritmo es una lista bien definida, ordenada y finita de operaciones que permite hallar la solución a un problema en un tiempo razonable.

El desarrollo de un algoritmo se realiza mediante varias etapas.

• Primero se modela el problema que se necesita resolver.
• Después se diseña la solución
• Se analiza está para determinar su grado de corrección y eficiencia
• Finalmente se traduce en instrucciones en un lenguaje de programación

El modelo especifica los supuestos que se tienen acerca de los datos de entrada y la capacidad computacional que tiene el algoritmo. El diseño se basa en los distintos métodos de resolución de problemas. Para la etapa de análisis de un algoritmo se deben de estudiar cuantas operaciones se realizan para resolver un problema.

Computacionalmente hablando cada algoritmo tiene un costo A(x) por resolver determinado problema x, definido por las operaciones que realiza para solucionar dicho problema. Al máximo valor de operaciones realizadas se le conoce como el peor caso, y el minimo de, como el mejor caso. El peor caso proporciona una cota superior al costo del algoritmo y es el comunmente estudiado, hay casos donde se puede obtener el caso promedio, para lo cual se define una probabilidad de ocurrencia p(x) de ciertas condiciones del problema y se calcula una suma ponderada, pero generalmente es muy dificíl de clacular o imposible de definir por la complejidad del problema.

Si es posible demostrar que no existe un algoritmo capaz de realizar menos operaciones para resolver un problema, se dice que el algoritmo es óptimo.