Descripción del Curso

Justificación

Aunque la capacidad de procesamiento y almacenamiento de los computadores sigue aumentando, también es cierto que los volúmenes de datos y la complejidad de las tareas asignadas a estos es cada vez mayor. Adicionalmente, desde mucho antes de la aparición del computador se han estudiado cientos de problemas de gran aplicación práctica, para los cuales no se conocen procesos algorítmicos eficientes ni se cree que aparezcan en el futuro.

El ingeniero de sistemas debe estar en capacidad de estimar matemáticamente la complejidad computacional de los problemas a los que se enfrenta en su actividad profesional y además, debe ser capaz de proponer, evaluar y elegir acertadamente soluciones para esos de problemas, siendo consciente de antemano, del desempeño que tendrán una vez estén implantadas.


Objetivo

El objetivo del curso es estudiar los principios fundamentales de la solución de problemas a través de algoritmos computacionales. El curso se divide en dos partes principales: el análisis de algoritmos y el diseño de algoritmos eficientes. En al primera parte se estudian las herramientas matemáticas que permiten caracterizar el desempeño de un algoritmo en términos del uso que hace de los recursos computacionales, principalmente tiempo y memoria. En la segunda parte se estudian diversos tipo de problemas y técnicas para resolverlos de manera eficiente.

Programa 


 Tema          Material y Recursos Tareas y evaluaciones
1. Introducción
1.1 Nociones básicas (algoritmo, programa, problema, instancia, operación básica)
1.2 Corrección de algoritmos
1.3 Eficiencia de algoritmos
[Cormen01] Cap 1, Cap 2 (Sect 2.1)
[OCW2005] Lect. 1 (video y notas de clase)
Recursos de Python
[OCW2008] Python cost model
Taller I: Análisis de Algoritmos
insertion_sort.py (programa ejemplo)
2. Análisis de Algoritmos
2.1 Notación asintótica
2.2 Recurrencias
2.3 Sustitución
2.4 Método maestro
[Cormen01] Cap 3, Cap 4
[OCW2005] Lect. 2 (video y notas de clase)
 
3. Introducción al Diseño de Algoritmos
3.1 Dividir y conquistar
3.2 Quicksort
3.3 Heapsort
3.4 Colas de prioridades
3.5 Ordenamiento en tiempo lineal
[Cormen01] Cap 6, Cap 7, Cap 8
[OCW2005] Lect. 4 (video y notas de clase)
[OCW2005] Lect. 5 (video y notas de clase)
Taller II:
Análisis y Diseño de Algoritmos

4. Estructuras de Datos
4.1 Repaso de estructuras básicas
4.2 Vectores dinámicos y análisis amortizado
4.3 Tablas hash
4.4 Binary search trees
[Cormen01] Cap 10, 11, 12, 13, 17
[OCW2005] Lect. 7 (video y notas de clase)
[OCW2005] Lect. 8 (video y notas de clase)
[OCW2005] Lect. 9 (video y notas de clase)
[OCW2005] Lect. 10 (video y notas de clase)
[OCW2005] Lect. 13 (video y notas de clase)
Práctica árboles
Taller III: Estructuras de Datos
Parcial Tema A
Parcial Tema B
5. Programación Dinámica
5.1 Funciones con memoria
5.2 Secuencia común más larga
5.3 Multiplicación de matrices
   
6. Algoritmos en Grafos
6.1 Arbol de expansion mínimo
6.2 Camino más corto
  Taller IV: Programación dinámica y grafos.
7. Complejidad Computacional
7.1 Clasificación de problemas
   


Metodología

En las horas de clase el profesor presenta los temas de curso y los estudiantes desarrollan talleres y resuelven problemas representativos de cada tema. De forma paralela a la discusión de los temas en clase, los estudiantes hacen ejercicios escritos y de programación en los que se aplicarán y criticarán los conceptos y técnicas estudiadas. Periódicamente se efectúan pruebas escritas, con el propósito de tener información gradual y oportuna de los logros y dificultades del grupo en cada unidad del curso.

Como texto de curso se puede usar [Cormen01].

Evaluación


NOTAS_GRUPO_1
NOTAS_GRUPO_2

La calificación final se obtiene según la siguiente distribución de porcentajes:

    PARCIALES (45%)

  • Primer Parcial (15% teórico).
  • Parcial Final (15% teórico, 15% práctico).

    TRABAJOS (55%)

  • Quices
  • Talleres
  • Ejercicios
  • Implementaciones
  • Exposiciones

Bibliografía

  • [Cormen01] Cormen, T. H., Stein, C., Rivest, R. L., and Leiserson, C. E. 2001 Introduction to Algorithms. 2nd. McGraw-Hill Higher Education
  • [Skiena03] Skiena, S. S. and Revilla, M. A. 2003. Programming challenges: the programming contest training manual. Springer-Verlag.
  • [Harel04] Harel D, Feldman Y. Algorithmics: The Spirit of Computing (3rd Edition). Addison Wesley; 2004.
  • [Goodrich02] MT Goodrich, R Tamassia. 2002. Algorithm design: foundations, analysis, and Internet examples. Wiley. 
  • [Bentley00] Bentley, J. 2000 Programming Pearls (2nd Ed.). ACM Press/Addison-Wesley Publishing Co.

Otros Recursos

Subpages (1): Taller 4