4.3.3 AL/Algoritmos Fundamentales. (12 horas)

Tópicos

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

Objetivos

• Implementar los algoritmos cuadráticos más comunes y los algoritmos de ordenamiento $O(N log N)$.
• Diseñar e implementar una función de (hash) apropiada para una aplicación.
• Diseñar e implementar un algoritmo de resolución de colisiones para tablas de hash.
• Discutir la eficiencia computacional de los principales algoritmos de ordenamiento, búsqueda y (hashing).
• 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.
• 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.
• 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..