5.26.4.4 Estrategias Algorítmicas (24 horas) [Habilidades AG-C08,AG-C12]

Referencias Bibliográficas: [Cormen et al., 2022,Dasgupta et al., 2006]

Temas

1. Paradigmas:
   1. Fuerza Bruta (por ejemplo, búsqueda lineal, ordenamiento por selección, viajante de comercio, mochila)
   2. Disminuir y Vencer:
      1. Por una Constante (por ejemplo, ordenamiento por inserción, ordenamiento topológico)
      2. Por un Factor Constante (por ejemplo, búsqueda binaria)
      3. Por un Tamaño Variable (por ejemplo, Euclides)
   3. Dividir y Vencer (por ejemplo, búsqueda binaria, quicksort, mergesort, Strassen)
   4. Voraz (por ejemplo, Dijkstra, Kruskal, Mochila)
   5. Transformar y Vencer:
      1. Simplificación de instancia (por ejemplo, encontrar duplicados mediante preordenamiento de lista)
      2. Cambio de representación (por ejemplo, heapsort)
      3. Reducción de problema (por ejemplo, mínimo común múltiplo, programación lineal)
      4. Programación dinámica (por ejemplo, Floyd, Marshall, Bellman-Ford)
   6. Compromisos espacio vs tiempo (por ejemplo, hash)
2. Manejo del crecimiento exponencial (por ejemplo, heurística A*, ramificación y poda, retroceso)
3. Iteración vs recursión (por ejemplo, factorial, búsqueda en árbol)
4. Paradigmas:
   1. Algoritmos de aproximación
   2. Mejora iterativa (por ejemplo, Ford-Fulkerson, simplex)
   3. Algoritmos aleatorizados/estocásticos (por ejemplo, corte máximo, bolas y cubos)

5. Computación cuántica

Aprendizaje esperado (Learning Outcomes)

1. Para cada uno de los paradigmas en esta unidad:
   1. Explicar sus características definitorias
   2. Explicar un ejemplo que demuestre el paradigma incluyendo cómo este ejemplo satisface las características del paradigma.
   [Explicar]
2. Para cada uno de los algoritmos en la unidad Fundamentos Algorítmicos (AL) -FoundationalDataStructuresAlgorithms, explicar el paradigma utilizado por el algoritmo y cómo ejemplifica este paradigma [Explicar]
3. Dado un algoritmo, explicar el paradigma utilizado por el algoritmo y cómo ejemplifica este paradigma [Explicar]
4. Dar un problema del mundo real, evaluar paradigmas algorítmicos apropiados y algoritmos de estos paradigmas que aborden el problema incluyendo evaluar los compromisos entre los paradigmas y algoritmos seleccionados [Evaluar]
5. Dar ejemplos de algoritmos iterativos y recursivos que resuelvan el mismo problema, explicar los beneficios y desventajas de cada enfoque [Explicar]
6. Evaluar si un enfoque voraz conduce a una solución óptima [Evaluar]
7. Explicar varios enfoques para abordar problemas computacionales cuyas soluciones algorítmicas son exponenciales [Explicar]