2.2.2 AL/Algoritmos Fundamentales

Temas:
Core

• Grafos (por ejemplo, [no]dirigidos, [a]cíclicos, [no]conexos y [no]ponderados):
  1. Representación de grafos: lista de adyacencia vs matriz
• 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)
• 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)
• Algoritmos de grafos:
  1. Camino más corto (por ejemplo, Dijkstra, Floyd)
  2. árbol de expansión mínima (por ejemplo, Prim, Kruskal)
• Algoritmos de ordenamiento:
  1. Complejidad $O(n \log n)$ heapsort
  2. Pseudo $O(n)$ complejidad (por ejemplo, bucket, counting, radix)
• Algoritmos de grafos:
  1. Clausura transitiva (por ejemplo, Warshall)
  2. Ordenamiento topológico
• 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):
Core:

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]