Estrategias de Diseño de Algoritmos 2022

ESTRATEGIAS DE DISEÑO DE ALGORITMOS ANÁLISIS DE ALGORITMOS Profesora: Diana Heredia Vizcaíno 2022  Estrategias de diseño Las estrategias de diseño de algoritmos Hay problemas, que por su naturaleza, Las estrate...

ESTRATEGIAS DE DISEÑO DE ALGORITMOS ANÁLISIS DE ALGORITMOS Profesora: Diana Heredia Vizcaíno 2022  Estrategias de diseño Las estrategias de diseño de algoritmos Hay problemas, que por su naturaleza, Las estrategias más conocidas son: son técnicas que permiten, en ciertos pueden ser resueltos de forma eficiente casos, construir algoritmos eficientes. aplicando varias estrategias de diseño; otros problemas, solo pueden ser resueltos mediante una sola estrategia. Algoritmos exhaustivos. “Divide and conquer”. Programación dinámica. Greedy algorithms.  Esta estrategia también se conoce como “Fuerza bruta” (Brute force). Algoritmos En esta estrategia, se exploran todas las posibles alternativas hasta encontrar la solución. exhaustivos Este tipo de algoritmos siempre encuentra la solución. No son algoritmos “inteligentes”, pues no hay algún tipo de criterio que le permita identificar alternativas que no conducirán a la solución. El tiempo de ejecución de estos algoritmos será proporcional a la cantidad de alternativas; puede ser bastante grande.  Divide y Vencerás (Divide and Conquer) es una estrategia de diseño de algoritmos que se aplica a problemas grandes que pueden ser divididos en subproblemas: “Divide y Se divide el problema en subproblemas más pequeños (Divide). Vencerás” Se resuelven los subproblemas (Conquer). Se combinan las soluciones anteriores, para obtener así la solución al problema inicial (Combine). Generalmente, en esta estrategia se aplica recursión: Divide: Llamados recursivos. Conquer: Cuando llega al caso base. Combine: Retorna los resultados. Ejemplo: Ordenamiento por mezclas (Merge sort): https://www.programiz.com/dsa/merge-sort  Esta estrategia permite construir algoritmos óptimos para solucionar problemas donde se presenta “overlapping” o subproblemas Programación “superpuestos”. dinámica “Overlapping” se presenta cuando la solución de un subproblema se necesita obtener de nuevo más adelante. La programación dinámica permite utilizar una estructura de datos apropiada para guardar la solución de cada subproblema a medida que se obtenga, de tal manera que pueda utilizarse dicha solución más adelante cuando sea requerida de nuevo. Ejemplos: Cálculo de los números de Fibonacci  Los algoritmos voraces (Greedy Algorithms) resuelven un problema por medio de la selección de la mejor opción que se presente en el momento, sin importar si el mejor Algoritmos resultado actual conduce a la solución óptima. Voraces A diferencia de los algoritmos exhaustivos, en los algoritmos voraces existen criterios para descartar las alternativas que no parecen adecuadas para lograr la solución. El algoritmo nunca reversa una decisión ya tomada, aún si ésta no fue la correcta. En ocasiones, el algoritmo voraz puede no lograr la solución óptima, pero si una buena aproximación. Ejemplo de algoritmo voraz: Algoritmo de Dijkstra para buscar el camino más corto entre dos vértices de un grafo.