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
Material y Recursos
[Cormen09] Cap 1, Cap 2
IPython notebook: corrección y análisis de algoritmos
[Cormen09] Cap 3, Cap 4
IPython notebook: ordenamiento por mezcla
[Cormen09] Cap 22
[Cormen09] Cap 9, 6
Lecture 4: Quicksort, Randomized Algorithms MIT Introduction to Algorithms (SMA 5503 ) Fall 2005
Lecture 6: Order Statistics, Median MIT Introduction to Algorithms (SMA 5503 ) Fall 2005
Order Statistic -- from Wolfram MathWorld
Computer Generation of Statistical Distributions
Quicksort form interactivepython.org
IPython notebook:quicksort from interactivepython.org
IPython notebook: randomquicksort distr comps(tiempo)
IPython notebook: quicksort two finger comp distrib (tiempo)
Distributional Convergence for the Number of Symbol Comparisons Used by QuickSort from JA Fill, Johns Hopkings U.
Distributional Convergence for the Number of Symbol Comparisons Used by QuickSelect.from JA Fill, Johns Hopkings U.
[Cormen09] Cap 15
IPython notebook: timeitexmaples
Lecture 15: Dynamic Programming, Longest Common Subsequence MIT Introduction to Algorithms (SMA 5503 ) Fall 2005
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
CS 97SI: Introduction to Programming Contests - Jaehyun Park - Stanford University, 04-dynamic-programming.pdf change-integer partitions
Ch15 Dynamic Programming Rod Cutting UMass Lowell Computer Science 91.503 Analysis of Algorithms Prof. Giampiero Pecelli 2010
CS3233 Competitive Programming - old teaching materials - Steven Halim - NUS, week04_dp_1.pdf, week04_dp_2.pdf
[Cormen09] Cap 24, 25
IPython notebook: Djkstra_eppstein
IPython notebook: FloydWarshall
DISI decompositions_of_graphs.rar
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.
[Cormen09] Cap 34
Complejidad computacional
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.
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:
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:
On-line: on-line Python interpreter at compileonline.com
ICPC
Slides talk D. Niquefa - Grupo de Maratones UN - www.facebook.com/groups/maratonesunbogota/
CS 97SI: Introduction to Programming Contests - Jaehyun Park - Stanford University
CS3233 Competitive Programming - old teaching materials - Steven Halim - NUS
IEEEXtreme
Slides talk J.S. Dussan IEEEXtreme 10.0 UN
CONCURSO de Estrategias de Algorítmicas de Negociación en la Bolsa Millonaria
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