Existen diversas formas de solucionar computacionalmente un problema, lo que conduce al dilema de escoger la más adecuada. Hay diferentes aspectos que se pueden evaluar para hacer tal escogencia. En este curso se enseña a calcular la complejidad espacio-temporal de una solución, con el fin de resolver un problema eficientemente. También se enseñan modelos matemáticos, tipos de datos abstractos, estructuras de datos y algoritmos clásicos, haciendo especial énfasis en la complejidad espacio-temporal de las implementaciones.
El objetivo general del curso es que el estudiante aprenda familias de algoritmos, tipos de datos abstractos y estructuras de datos asociados a modelos matemáticos, y analice su complejidad espacio-temporal para compararlos en términos de su eficiencia.
Durante este curso el estudiante desarrollará habilidades para:
- Usar modelos matemáticos, tipos de datos abstractos, estructuras de datos y algoritmos clásicos para resolver problemas.
- Demostrar la correctitud de un algoritmo iterativo, aplicando las técnicas correspondientes
- Analizar el comportamiento asintótico del tiempo de ejecución y del espacio requerido por un algoritmo o una estructura de datos para determinar su eficiencia.
- Diseñar e implementar estructuras de datos y algoritmos eficientes, para hacer un uso apropiado de los recursos computacionales.
- Diseñar e implementar algoritmos eficientes para resolver problemas de optimización.
| Objetivo específico | Eje temático | Desglose |
|---|---|---|
| 1,4 | Modelos matemáticos, tipos de datos abstractos y estructuras de datos. | Definiciones, propiedades y diferencias entre ellos. |
| 2 | Demostración de la correctitud de algoritmos iterativos | Invariante de un ciclo. Pasos de inicialización, mantenimiento y terminación. |
| 3 | Complejidad espaciotemporal de un algoritmo. | Cálculo del orden de duración de algoritmos recursivos, iterativos y con llamados a métodos o funciones, en el peor caso, caso promedio y mejor caso. Resolución de relaciones de recurrencia. |
| 1,3,4 | Modelos y tipos de datos abstractos | Listas, pilas, colas, árboles, conjuntos, diccionarios, colas de prioridad, relaciones y grafos. Operadores básicos, implementaciones, algoritmos asociados, aplicaciones, complejidad espacio-temporal de los algoritmos y sus implementaciones. |
| 1,3,4 | Estructuras de datos | Arreglos, listas enlazadas, árboles parcialmente ordenados, árboles de búsqueda binaria, árboles balanceados, tablas de dispersión. Estructuras de datos para la implementación de árboles, grafos y relaciones. Complejidad espacio-temporal. |
| 1,3,4 | Algoritmos de ordenamiento | Ordenamiento de burbuja, ordenamiento por selección, inserción, mezcla, montículos, residuos y ordenamiento rápido (quicksort), y su complejidad espacio-temporal. |
| 1,3,5 | Técnicas de resolución de problemas | Divide y vencerás, búsqueda exhaustiva, programación dinámica, algoritmos ávidos, y su complejidad temporal. |
| 1,3,4 | Algoritmos para grafos | Recorridos en anchura y en profundidad, árboles recubridores mínimos, rutas más cortas, y su complejidad espacio-temporal. |
- Cormen, T. H., Leiserson, C. E., Rivest, R. L. y Stein, C. Introduction to Algorithms, III ed. MIT Press, 2009.
- Aho, A. V., Ullman, J. D. y Hopcroft, J. E. Estructuras de Datos y Algoritmos. AddisonWesley Iberoamericana, 1988.
- Brassard, Gilles y Bratley, Paul. Fundamentos de Algoritmia. Prentice Hall. 1997.
- Heileman, Gregory. Estructuras de Datos, Algoritmos y Programación Orientada a Objetos. McGraw Hill. 1998.
- Sedgewick, Robert. Algoritmos en C++. Pearson Education. 1995
Este no es un documento oficial. Documentos oficiales se entregan en la secretaría de la escuela.