Diseño De Algoritmos Aplicados a Problemas

Diseño del algoritmo

Diseño de algoritmos busca eficiente solución a un problema. Un algoritmo realizar eficientemente puede utilizarse como plantilla para resolver una amplia gama de problemas similares. Lenguajes de programación de alto nivel proporcionan la implementación de algoritmos eficientes como estructuras de datos listo para su uso. Paradigma de diseño del algoritmo se ocupa de una variedad de técnicas como la fuerza bruta, dividir y conquistar, retroceso, rama y enlazado, transformar y conquistar y algoritmo voraz.

Divide y vencerás técnica:

Divide y vencerás resuelve un problema por derribar un problema en problemas más pequeños hasta el más pequeño problema convertido en sencillo y fácil de resolver de forma recursiva. Luego, las soluciones de los problemas más pequeños se combinan para producir la solución a un problema mayor. Esta técnica se aplica en quick sort, merge sort, análisis sintáctico y transformada de Fourier discreta. Divide y vencerás es una técnica poderosa para resolver un problema complejo como torre de rompecabezas de Hanoi a través de repetidas recursividad. Este enfoque funciona mejor en multi-processors sistemas con memoria compartida como cada subproblema distinto puede funcionar independientemente en procesadores separados. Divide y vencerás paradigma puede ser aplicado para producir algoritmos eficientes como algoritmo de Strassen o algoritmo de mergesort.

Como cada problema se divide en problemas más pequeños, este enfoque utiliza memoria caché eficientemente y se llama como caché inconsciente debido a su uso óptimo de la memoria caché. Divide y vencerás algoritmo funciona mejor para procedimientos recursivos siempre que haya suficiente espacio para almacenar datos recursivo; de lo contrario, puede provocar desbordamiento de pila.

Programación dinámica:

Programación dinámica es casi similar a dividir y conquistar excepto que ayuda a optimizar los cálculos. En un cálculo de recursiva mediante divide y vencerás, los cálculos se realizan varias veces resultando en subproblemas idénticos. Programación dinámica optimiza este enfoque mediante el almacenamiento de los resultados de subproblemas idénticos en una tabla, evitando así la necesidad de realizar la misma operación varias veces. Si el tamaño de entrada crece, los subproblemas también crecen junto con él; por lo tanto tener una solución optimizada para resolver el subproblema sólo una vez y almacenar el resultado en una tabla puede ahorrar mucho tiempo de procesamiento.

Enfoque de arriba hacia abajo:

Este enfoque es similar a la solución de un problema utilizando recursividad. Si un problema puede ser recursivamente solved resolviendo sus subproblemas y si los subproblemas se superponen entre sí, la solución a los subproblemas puede ser memorizada o almacenada en una tabla. Cuando surge un nuevo subproblema, la tabla se comprueba primero para ver si el subproblema ya ha sido resuelto o no; Si subproblema se ha resuelto, solo es reutilizado, de lo contrario, encontrar la solución a la subproblema y añadirlo a la tabla.

Enfoque de abajo hacia arriba:

Este enfoque es justo lo contrario de enfoque top-down. En este caso, primero se resuelven los subproblemas y las soluciones de los subproblemas se utilizan para derivar las soluciones de problemas mayores. Las soluciones de los subproblemas se almacenan en una tabla y son recursivamente iterada para encontrar una solución a un problema mayor. Por ejemplo, si se conoce la solución F30 y F31, es sencillo calcular su valor siguiente F32. Algunos de los algoritmos populares que utilizan programación dinámica son de Fibonacci, tablero de ajedrez, torre de Hanoi y el alineamiento de secuencias.







Politica de Privacidad