Docentes

Descripción del Curso

Noticia: Las notas del grupo 1 se encuentran en la sección de evaluación

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 Secuencia común más larga
5.3 Multiplicación de matrices
[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 Arbol de expansion mínimo
6.2 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
7 de febrero(1.1) Presentación general del curso y de nociones básicas.
(1.2 y 1.3) Diseño y Análisis de Algoritmos.

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

28 de febrero(2.3) Recurrencias.
(2.4) Método de sustitución.

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

14 de marzo(3.1) Colas de prioridades.
(3.2) Algoritmo HeapSort.
Primer Examen Parcial (Marzo 19 7-9am)
Entrega Taller I
Heapsort
21 de marzo(3.3) Algoritmo QuickSort.
(3.4) Ordenamiento en tiempo lineal.
Quiz
28 de marzo(4.1) Estructuras básicas.


4 de abril(4.2) Tablas hash.Práctica árboles
11 de abril(4.3) Árboles de búsqueda binaria.
18* de abrilSemana santa.
25 de abril (4.3) Árboles rojo-negro.
(4.4) Vectores dinámicos y análisis amortizado. 
 
2 de mayo(5.1) Funciones con memoria.
Segundo examen Parcial
Entrega Taller II
9 de mayo(5.2) Secuencia común más larga.
(5.3) Multiplicación de matrices.

16 de mayo

(6) Representación de grafos.
(6) Búsquedas sobre Grafos.

23 de mayo(6.1) Árbol de expansión mínimo.
(6.2) Camino más corto (camino simple).

30 de mayo(6.2) Camino más corto (todas las parejas).
Examen Final (Junio 4 7-9am) 
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 1 (solución de dudas por correo o el Jueves 9 de Junio de 2pm-3pm)

Notas Grupo 2 (solución de dudas por correo o el Viernes 10 de Junio de 9am-11:30am)

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