5.1.4.7 Estrategias Algorítmicas (6 horas) [Habilidades AG-C08,AG-C12]

Referencias Bibliográficas: [Guttag, 2013,Cormen et al., 2009]

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. Iteración vs recursión (por ejemplo, factorial, búsqueda en árbol)
3. Estrategias de descomposición de problemas.
4. Técnicas de diseño de algoritmos.
5. Estrategias de depuración y prueba.
6. Seguimiento de la ejecución del programa.

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.
   [Familiarizarse]
2. Dar ejemplos de algoritmos iterativos y recursivos que resuelvan el mismo problema, explicar los beneficios y desventajas de cada enfoque [Usar]
3. Evaluar si un enfoque voraz conduce a una solución óptima [Evaluar]
4. Aplicar técnicas sistemáticas de depuración para localizar y corregir errores. [Usar]
5. Analizar la complejidad algorítmica para problemas simples. [Familiarizarse]