Tecnicas de diseño de algoritmos - ensayo

Ensayo Técnicas de diseño de algoritmos

ENSAYO TÉCNICAS DE DISEÑO DE ALGORITMOS
Mario Andrés Higuera Calixto
e-mail: mahc003@gmail.com

RESUMEN: Este artículo pretende dar una
introducción al tema de técnica de diseño de algoritmos y una visión de los algoritmos creados para la obtención de resultados óptimos a problemas de cierto tipo.

TECNICAS DE DISEÑO DE ALGORITMOS
Dentro delcampo científico, matemático e industrial surgen problemas en donde el análisis de grandes cantidades de datos, las funciones o procesos que se requieren para procesarlos, y el tiempo en el que se espera obtener un resultado optimo que brinde respuestas acertadas para desarrollar con éxito un trabajo de desarrollo, investigación o producción, son cruciales a la hora de realizar el diseño de unalgoritmo que nos de cómo resultado un Software competente que resuelva esos inconvenientes. Normalmente, dentro de nuestro proceso de aprendizaje nos basamos en nuestra experiencia con problemas similares a los planteados, un diseño básico y que cumpla con solucionar el problema para la escritura de un algoritmo; con este, se realizan pruebas de escritorio teniendo en cuenta la mayoría de los posiblescasos con los que se enfrentaría dicho algoritmo, solucionarlo y hacerlo algo robusto. Lo que siempre sucede es que pensamos en que la cantidad de datos que tendremos que manejas no serán demasiados, no a nivel industrial, por eso, se utilizan estructuras conocidas y manejables para el tratamiento de dichos datos que a la hora de enfrentarlo a la realidad no da los resultados esperados ya quepodría presentar problemas de memoria, tiempos demasiado largos (o no llegar nunca a la solución) y también que la respuesta no sea la esperada. Todo esto se puede resolver realizando algoritmos eficientes, basándose en técnicas ya elaboradas que permitan obtener mejores tiempos de repuestas con poco procesamiento, buen uso de los recursos disponibles y con resultados óptimos. Para verificar que nuestroalgoritmo es ideal a la hora de resolver un problema debemos, aparte de realizar las respectivas pruebas de escritorio, verificar el orden de complejidad para tener una idea clara de cómo serán los tiempos de respuesta obtenidos a medida que se manejen una mayor cantidad de datos. Recordemos, que de acuerdo a la estructura del algoritmo y las operaciones que este realice, podemos obtenerlos deorden:

O(1) O(log n) O(n) O(n log n) 2 O(n ) a O(n ) n O(a )

orden constante orden logarítmico orden lineal orden cuadrático orden polinomial (a > 2) orden exponencial (a > 2)

En donde obtener un Orden logarítmico es más eficiente que uno de orden exponencial en donde, como su nombre lo indica, el tiempo invertido en procesar una determinada cantidad de datos crece de forma exponencial conun pequeño aumento de los primeros, a diferencia del logarítmico que después de cierto volumen de datos, no importa cuánto aumenten el tiempo de ejecución varia de forma imperceptible. Con el fin de lograr obtener estos resultados, se han diseñado algoritmos que procesan información de una forma eficiente y que logran órdenes de complejidad deseados. Entre estos algoritmos están: divide yvencerás, algoritmos voraces, de programación dinámica, backtracking o vuelta atrás, cada uno con características que lo hacen implementable, por lo general, para un tipo de problema específico.

Divide y vencerás
Esta técnica consiste en la descomposición de un problema en subproblemas más pequeños pero todos con las mismas características, realizando esta subdivisión de forma recursiva para lossubproblemas encontrados, si es que aun lo ameritan, para llegar a el caso baso del problema, a partir del cual se comienzan a obtener las soluciones parciales y “sumarlas” para dar la solución completa. Este método para solución de problemas tiene un orden de complejidad logarítmico O(log n), ya que en cada paso realizamos una división del problema a la mitad, y sobre este la mitad de forma...