5.26.4.2 Algoritmos Fundamentales (6 horas) [Habilidades AG-C08,AG-C12]

Referencias Bibliográficas: [Cormen et al., 2022,Kleinberg and Tardos, 2005]

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
7. Emparejamiento:
   1. Emparejamiento eficiente de cadenas (por ejemplo, Boyer-Moore, Knuth-Morris-Pratt)
   2. Emparejamiento de subsecuencia común más larga
   3. Emparejamiento de expresiones regulares

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]
5. Para cada uno de los algoritmos y enfoques algorítmicos en los temas del Núcleo KA:
   1. Explicar un ejemplo prototípico del algoritmo, y
   2. Explicar paso a paso cómo opera el algoritmo.
   [Explicar]