5.7.4.16 Algoritmos Fundamentales (3 horas) [Habilidades AG-C02,AG-C08,AG-C12]

Referencias Bibliográficas: [Brookshear and Brylow, 2019b]

Temas

1. Grafos (por ejemplo, [no]dirigidos, [a]cíclicos, [no]conexos y [no]ponderados):
   1. Representación de grafos: lista de adyacencia vs matriz
2. Algoritmos de búsqueda:
   1. Complejidad $O(n)$ (por ejemplo, búsqueda lineal/secuencial en arreglo/lista)
   2. Complejidad $O(\log_2 n)$ (por ejemplo, búsqueda binaria)
   3. Complejidad $O(\log_b n)$ (por ejemplo, búsqueda en árbol no informada en profundidad/amplitud)
3. Algoritmos de ordenamiento (por ejemplo, estables, inestables):
   1. Complejidad $O(n^2)$ (por ejemplo, inserción, selección)
   2. Complejidad $O(n \log n)$ (por ejemplo, quicksort, merge, timesort)
4. Algoritmos de grafos:
   1. Camino más corto (por ejemplo, Dijkstra, Floyd)
   2. árbol de expansión mínima (por ejemplo, Prim, Kruskal)

5. Algoritmos de ordenamiento:
   1. Complejidad $O(n \log n)$ heapsort
   2. Pseudo $O(n)$ complejidad (por ejemplo, bucket, counting, radix)
6. Algoritmos de grafos:
   1. Clausura transitiva (por ejemplo, Warshall)
   2. Ordenamiento topológico

Aprendizaje esperado (Learning Outcomes)

1. Para cada algoritmo en esta unidad explicar paso a paso cómo opera el algoritmo [Explicar]
2. Para cada enfoque algorítmico (por ejemplo, ordenamiento) en esta unidad aplicar un ejemplo prototípico del enfoque (por ejemplo, ordenamiento por mezcla) [Aplicar]
3. Dados los requisitos para un problema, desarrollar múltiples soluciones usando varias estructuras de datos y algoritmos. Posteriormente, evaluar la idoneidad, fortalezas y debilidades seleccionando un enfoque que satisfaga mejor los requisitos [Crear]
4. Explicar factores más allá de la eficiencia computacional que influyen en la elección de algoritmos, como el tiempo de programación, la mantenibilidad y el uso de patrones específicos de la aplicación en los datos de entrada [Explicar]