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
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: 40%
Talleres, tareas, quices y proyecto: 20%
Extra-crédito trabajo en clase 10%
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:
Coursera Algorithms, Part II, Princeton.
Udacity CS212 Design of Computer Programs
Udacity CS213 Intro to Theoretical Computer Science
E. Demaine, R. Rivest and S. Devadas, Introduction to Algorithms Course, MIT OpenCourseware, 2008
Visualizing data structures and algorithms through animation
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:
Tutorial Oficial de Python: Inglés y Español (vaya primero a la sección 4)
Cursos interactivos de Python
R. González-Duque, Python para todos, 2010
Distribuciones:
Windows: distribución oficial, IronPython (basado en .net e integrado con Visual Studio)
Linux, FreeBSD, OS X y otros sabores de Unix: si es usuario de alguno de estos SO pues muy seguramente ya lo tiene instalado y además ya sabe que tiene que hacer ;)
On-line:
Online judges: so, you think you are good at programming? these are a couple of good places to test yourself.
Quicksort DISI Quicksort
Lecture 4: Quicksort, Randomized Algorithms MIT Introduction to Algorithms (SMA 5503 ) Fall 2005
Distributional Convergence for the Number of Symbol Comparisons Used by QuickSort from JA Fill, Johns Hopkings U.
QuickSelect Lecture 6: Order Statistics, Median MIT Introduction to Algorithms (SMA 5503 ) Fall 2005
Distributional Convergence for the Number of Symbol Comparisons Used by QuickSelect.from JA Fill, Johns Hopkings U
Montículos Heapsort DISI Heapsort
Lecture 4: Heaps and Heap Sort MIT Introduction to Algorithms( 6.006) Fall 2011
VisuAlgo - visualising data structures and algorithms through animation
Udacity CS 215 Lesson 4: It’s Who You Know Keeping track of your best friends using heaps
Programación dinámica
Lecture 15: Dynamic Programming, Longest Common Subsequence MIT Introduction to Algorithms (SMA 5503 ) Fall 2005
CS 97SI: IntroVduction to Programming Contests, Jaehyun Park, Stanford University, 04-dynamic-programming.pdf
CS3233 Competitive Programming (old teaching materials), Steven Halim, NUS, week04_dp_1.pdf, week04_dp_2.pdf
Camino más corto desde una fuente y camino más corto entre todas las parejas
Lecture 17: Shortest Paths I: Properties, Dijkstra's Algorithm, Breadth-first Search , Lecture 18: Shortest Paths II: Bellman-Ford, Linear Programming, Difference Constraints and Lecture 19: Shortest Paths III: All-pairs Shortest Paths, Matrix Multiplication, Floyd-Warshall, Johnson MIT Introduction to Algorithms (SMA 5503 ) Fall 2005
CS3233 Competitive Programming (old teaching materials), Steven Halim, NUS, week05_graph_1.pdf
Udacity CS 215 Lesson 5: Strong and Weak Bonds Working with social networks with edge weights.
Clases de complejidad
(6.2) Problemas NP-completos
DISI calculabilidad.zip
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.
Udacity CS 313 Intro to Theoretical Computer Science Lectures Lesson 1 and 2