6.15.4.3 AL/Algoritmos Fundamentales. (12 horas) [Nivel Bloom 4]

Referencias Bibliográficas: [Cormen et al., 2009,Fager et al., 2014]

Tópicos

  1. Algoritmos numéricos simples.
  2. Búsqueda secuencial y binaria.
  3. Algoritmos cuadráticos de ordenamiento (selección, inserción).
  4. Algoritmos de tipo $ O(N log N)$ (Quicksort, heapsort, mergesort).
  5. Tablas de (hash) incluyendo estrategias de solución para las colisiones.
  6. Árboles de búsqueda binaria.
  7. Representación de grafos (Listas y Matrices de adyacencia).
  8. Recorridos por amplitud y profundidad.
  9. El algoritmo del camino más corto (algoritmos de Dijkstra y Floyd).
  10. Cerradura transitiva (algoritmo de Floyd).
  11. Árbol de expansión mínima (algoritmos de Kruskal y Prim).
  12. Ordenamiento Topológico.

Objetivos

  1. Implementar los algoritmos cuadráticos más comunes y los algoritmos de ordenamiento $ O(N log N)$.
  2. Diseñar e implementar una función de (hash) apropiada para una aplicación.
  3. Diseñar e implementar un algoritmo de resolución de colisiones para tablas de hash.
  4. Discutir la eficiencia computacional de los principales algoritmos de ordenamiento, búsqueda y (hashing).
  5. Discutir otros factores, además de la eficiencia computacional, que influyen en la elección de los algoritmos, tales como tiempo de programación, mantenimiento y el uso de patrones específicos de aplicación en los datos de entrada.
  6. Resolver problemas usando los algoritmos de grafos fundamentales, incluyendo búsqueda por amplitud y profundidad; caminos más cortos con uno y múltiples orígenes, cerradura transitiva, ordenamiento topológico y al menos un algoritmo de árbol de expansión mínima.
  7. Demostrar las siguientes capacidades: evaluar algoritmos, seleccionar una opción de un rango posible, proveer una justificación para tal elección e implementar el algoritmo..

Generado por Ernesto Cuadros-Vargas , Sociedad Peruana de Computación-Peru, Universidad Católica San Pablo, Arequipa-Peru
basado en el modelo de la Computing Curricula de IEEE-CS/ACM