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

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

2. Análisis de Algoritmos

2.1 Tipos de grafos

2.2 Notación asintótica

2.3 Recurrencias

2.4 Método maestro

3. Algoritmos Básicos en Grafos

3.1 Búsqueda en profundidad

3.2 Búsqueda en amplitud

3.3 Componentes conexas y conectividad

3.4 Puentes

4. Quicksort, Mediana,, Estadísticas de Orden, Quickselect, M ontículos y Heapsort

4.1 Media, Mediana y Estadísticas de orden

4.2 Quicksort

4.3 Quickselect

4.4 Montículos

4.5 Heapsort

5. Programación Dinámica

5.1 Funciones con memoria

5.2 Secuencia común más larga

5.3 Numero de formas de dar cambio en monedas

5.4 Corte de la vara

6. Camino más Corto

6.1 Camino más corto desde una fuente

6.2 Camino más corto entre todas las parejas

7. Complejidad Computacional

7.1 Clases de complejidad

7.2 Problemas NP-completos

Udacity CS 215

Lesson 1: A Social Network Magic Trick

Becoming familiar with algorithm analysis

Lesson 2: Growth Rates in Social Networks

Using mathematical tools to analyze how things are connected

Lesson 3: Basic Graph Algorithms

Finding the quickest route to Kevin Bacon

Lesson 4: It’s Who You Know

Keeping track of your best friends using heaps

Lesson 5: Strong and Weak Bonds

Working with social networks with edge weights.

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

Udacity CS 215 Lesson 6: Hardness of Network Problems Exploring what it means for a social network problem to be harder than other.

Udacity CS 215 Lesson 7: Conclusion Using your knowledge.

Extracredito 5%

Udacity CS 313 Intro to Theoretical Computer Science

Problem Set 4 - Reduced Satisfaction SAT

Programa

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: 30%

  • Talleres, tareas, quices: 15%

  • Proyecto - desarrollar una estrategia de algorítmica de trading en Quantopian: 15%

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

Cursos en línea sobre algoritmos:

Visualizing data structures and algorithms through animation

Pancake sorting problem

C. Leiserson and E. Demaine, Introduction to Algorithms Course, MIT OpenCourseware, 2005

http://disi.unal.edu.co/~algoritmos

CMU Great Theoretical Ideas In Computer Science http://www.cs.cmu.edu/~15251/

Python: