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.

Contenido


 Tema          Material y Recursos
1. Introducción
1.1 Nociones básicas (algoritmo, programa, problema, instancia, operación básica)
1.2 Análisis de algoritmos
1.3 Diseño de algoritmos
1.4 Complejidad computacional
[Cormen09] Cap 1, Cap 2
[OCW2005] Lect. 1 (video y notas de clase)
Recursos de Python
[OCW2008] Python cost model
[Harel04] Cap 7 (pdf)
2. Análisis de Algoritmos
2.1 Notación asintótica
2.2 Dividir y conquistar
2.3 Recurrencias
2.4 Sustitución
2.5 Método maestro
[Cormen09] Cap 3, Cap 4
[OCW2005] Lect. 2 (video y notas de clase)
3. Algoritmos de Ordenamiento
3.1 Colas de prioridades
3.2 Heapsort
3.3 Quicksort
3.4 Ordenamiento en tiempo lineal
[Cormen09] Cap 6, Cap 7, Cap 8
[OCW2005] Lect. 4 (video y notas de clase)
[OCW2005] Lect. 5 (video y notas de clase)
4. Estructuras de Datos
4.1 Repaso de estructuras básicas
4.2 Tablas hash
4.3 Binary search trees
4.4 Vectores dinámicos y análisis amortizado
[Cormen09] 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)
5. Programación Dinámica
5.1 Funciones con memoria
5.2 Corte de la vara
5.3 Multiplicación de matrices
5.4 Secuencia común más larga
[Cormen09] Cap 15
[OCW2005] Lect. 15 (video y notas de clase)
Ejercicios de repaso de Programación Dinámica
6. Algoritmos en Grafos
6.1 Representación de grafos
6.2 Búsquedas sobre grafos
6.3 Arbol de expansion mínimo
6.4 Camino más corto
[Cormen09] Cap 22, 23, 24 
[OCW2005] Lect. 16 (video y notas de clase)
[OCW2005] Lect. 17 (video y notas de clase)


Programa 


Semana
Tema
Entregas
1 de Agosto (1.1) Presentación general del curso y de nociones básicas.
(1.2 y 1.3) Diseño y Análisis de Algoritmos.

8 de Agosto (1.4) Complejidad computacional.
Introducción a Python (Laboratorio).
Práctica Python
15 de Agosto  (2.1) Notación Asintótica.
(2.2) Dividir y Conquistar.

22 de Agosto (2.3) Recurrencias.
(2.4) Método de sustitución.

29 de Agosto  (2.4) Método basado en un árbol de recursión.
(2.5) Método maestro.

5 de Septiembre (3.1) Colas de prioridades.
(3.2) Algoritmo HeapSort.
Primer Examen Parcial
Entrega Taller I

12  de Septiembre  (3.3) Algoritmo QuickSort.
(3.4) Ordenamiento en tiempo lineal.
Quiz_3
Alg_Quick
19  de Septiembre  (4.1) Estructuras básicas.
26  de Septiembre  (4.2) Tablas hash. Práctica árboles
3 de Octubre (4.3) Árboles de búsqueda binaria.
21 de Noviembre   (4.3) Árboles rojo-negro.
(4.4) Vectores dinámicos y análisis amortizado.
 
28 de Noviembre (5.1) Funciones con memoria.
(5.2) Secuencia común más larga.

5 de Diciembre (5.3) Multiplicación de matrices.
Segundo examen Parcial
Entrega Taller II
12 de Diciembre (6.1) Representación de grafos.
(6.2) Búsquedas sobre grafos.

9 de Enero(6.3) Árbol de expansión mínimo.
(6.4) Camino más corto (camino simple).

16 de Enero  (6.4) Camino más corto (todas las parejas).
Examen Final 
Entrega Taller III


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.

El texto guía del curso es [Cormen09].

Evaluación


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

    PARCIALES (60%)

  • Primer parcial: 20% 
  • Segundo parcial: 20%
  • Examen final: 20%

    TRABAJOS (40%)

  • Quices
  • Talleres
  • Ejercicios
  • Implementaciones
  • Exposiciones

Notas

  • Grupo 01 (Definitivas, revisión Lunes 6 de Febrero 2:30pm, of 114)
  • Grupo 02 (Definitivas, revisión via correo electrónico, Actualizadas a Febrero 5)

Bibliografía

  • [Cormen09] Cormen, T. H., Stein, C., Rivest, R. L., and Leiserson, C. E. 2009 Introduction to Algorithms. 3rd. 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