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 aborda dos aspectos principales: el análisis de algoritmos y el diseño de algoritmos eficientes. El análisis de algoritmos estudia las herramientas matemáticas que permiten caracterizar la eficacia y eficiencia, en términos de tiempo y memoria, de un algoritmo. El diseño de algoritmos estudia diversos tipos de problemas y técnicas para resolverlos de manera eficiente.

Contenido


 Tema          Udacity CS 215  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 Dividir y conquistar
Lesson 1: A Social Network Magic Trick
Becoming familiar with algorithm analysis
[Cormen09] Cap 1, Cap 2
IPython notebook: corrección y análisis de algoritmos 
2. Análisis de Algoritmos
2.1 Tipos de grafos
2.2 Notación asintótica
2.3 Recurrencias
2.4 Método maestro
Lesson 2: Growth Rates in Social Networks
Using mathematical tools to analyze how things are connected
[Cormen09] Cap 3, Cap 4

3. Algoritmos Básicos en Grafos
3.1 Componentes conexas
3.2 Conectividad
3.3 Búsquedas
3.4 Puentes
Lesson 3: Basic Graph Algorithms
Finding the quickest route to Kevin Bacon
[Cormen09] Cap 22
IPython notebook: búsquedas
Taller 1
4. Montículos y Estadísticas de Orden
4.1 Mediana
4.2 Estadísticas de orden
4.3 Montículos
4.4 Heapsort
Lesson 4: It’s Who You Know
Keeping track of your best friends using heaps
[Cormen09] Cap 9, 6
IPython notebook: montículos

5. Camino más Corto
5.1 Camino más corto desde una fuente
5.2 Camino más corto entre todas las parejas
Lesson 5: Strong and Weak Bonds
Working with social networks with edge weights.
[Cormen09] Cap 24, 25
Taller: camino más corto desde una fuente
6. Complejidad Computacional
6.1 Clases de complejidad
6.2 Problemas NP-completos

Lesson 6: Hardness of Network Problems
Exploring what it means for a social network problem to be harder than other.
Lesson 7: Conclusion
Using your knowledge
[Cormen09] Cap 34

7. Estructuras de Datos
7.1 Tablas hash
7.2 Árboles binarios de búsqueda
  [Cormen09] Cap 11, 12
8. Programación Dinámica
8.1 Funciones con memoria
8.2 Corte de la vara
8.3 Secuencia común más larga
  [Cormen09] Cap 15 
Taller 2: grafos, complejidad, programación dinámica


Programa 


Semana
Tema
Entregas
25 de febrero (1.1) Presentación general del curso y de nociones básicas.

4 de marzo (1.2 y 1.3) Diseño y Análisis de Algoritmos.
Introducción a python

11 de marzo (1.4) Dividir y conquistar

18 de marzo (2.1) Tipos de grafos
(2.2) Notación asintótica

25 de marzo (2.3) Recurrencias.
(2.4) Método maestro

8 de abril  (3.1) Componentes conexas
(3.2) Conectividad


22 de abril  (3.3) Búsquedas
(3.4) Puentes

29 de abril Examen 1 
6 de mayo (4.1) Mediana
(4.2) Estadísticas de orden

13 de mayo (4.3) Montículos
(4.4) Heapsort

20-27 de mayo (5.1) Camino más corto desde una fuente
3 de junio (5.2) Camino más corto entre todas las parejas
 
10 de junio(6.1) Clases de complejidad
(6.2) Problemas NP-completos

17 de junio (8.1) Funciones con memoria
(8.2) Corte de la vara
 
24 de junio (7.1) Tablas Hash
26 de junio Examen Final


Evaluación


La calificación final se obtiene según la siguiente distribución de porcentajes:
  • Examen parcial: 20% 
  • Examen final:    20%
  • Laboratorio y Udacity:   40%
  • Talleres, tareas, quices: 20%
Nota:
Como alternativa de obtener crédito extra se puede cursar el curso de Coursera Algorithms, Part II. La condición es aprobar el 100% de las actividades para recibir 10% adicional de nota.

Bibliografía

  • [Cormen09] Cormen, T. H., Stein, C., Rivest, R. L., and Leiserson, C. E. 2009 Introduction to Algorithms. 3rd. McGraw-Hill Higher Education
  • [Dasgupta07] Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani, "Algorithms" , McGraw Hill, 2007. Book Website
  • [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