AL3. Algoritmos de Computación Fundamental. (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 (hash) incluyendo estrategias de solución para las coliciones.
• Á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 (hash) apropiada para una aplicación.
• Diseñar e implementar un algoritmo de resolución de colisiones para tablas hash.
• Discutir la eficiencia computacional de los principales algoritmos de ordenamiento, búsqueda y (hashing).
• Discutir factores distintos a la eficiencia computacional que influyen en la elección de los algoritmos, tales como tiempo de programación, mantenibilidad 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 una fuente y con múltiples fuentes, 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..