Prof. Dr. Javier Campos

Diapositivas (curso 2020-21):

• Portada
• Introducción
• Algoritmos voraces
• Divide y vencerás
• Programación dinámica
• Búsqueda con retroceso
• Ramificación y poda
• Programación lineal y reducciones

Bibliografía:

Básica:

• T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to Algorithms (3rd edition), The MIT Press, 2009. (En la biblioteca.)
• S. Dasgupta, C. Papadimitriou, U. Vazirani. Algorithms (añadir chapx.pdf, x=0..10), McGraw-Hill, 2008. (En la biblioteca.) (También en este enlace.)
• G. Brassard, P. Bratley. Fundamentos de Algoritmia, Prentice Hall, 1997. (En la biblioteca.)

Complementaria:

• E. Horowitz, S. Sahni, and S. Rajasekaran. Computer algorithms, 2nd ed., Silicon Press, 2008.
• J. Kleinberg, E. Tardos. Algorithm Design, Addison-Wesley, 2005. (En la biblioteca.)
• I. Parberry and W. Gasarch. Problems on Algorithms (2nd edition), 2002.

Material adicional:

• Cuestiones previas:
  • “Chuleta” de fórmulas.
  • Apuntes de J.L. Balcázar sobre eficiencia de algoritmos.
  • Transparencias sobre eficiencia de algoritmos.
  • En clase escribiremos los algoritmos en una notación algorítmica en castellano (pseudocódigo) similar a la que suele aparecer en los libros de texto. Puede servir como guía la chuleta utilizada en alguna asignatura anterior, como ésta.

• Algoritmos voraces.
  • Corrección del algoritmo de Dijkstra (y análisis del coste) [CLRS09]. Lo mismo, pero según el libro [BB97].
  • Demostración de la propiedad fundamental de los árboles de recubrimiento de coste mínimo (del libro Data Structures and Algorithms, de Aho, Hopcroft y Ullman; ed. Addison-Wesley, 1983).
  • Demostraciones de la corrección de los algoritmos de Prim y de Kruskal [BB97].
  • Sobre conjuntos disjuntos o clases de equivalencia (union-find):
    • Transparencias de clase.
    • Explicación en Wikipedia.
    • Transparencias de una asignatura del plan en extinción.
    • Un Applet. Otro Applet.
  • Sobre la demostración de la corrección de algoritmos voraces (propiedades de la selección voraz y la subestructura óptima):
    • Páginas del libro de Cormen et al. [CLRS09].
  • Otras ideas sobre cómo demostrar corrección de algoritmos voraces (Universidad de Cornell):
    • Proof of greedy correction by exchange.
    • Proof of greedy correction by greedy stays ahead.
  • Repaso del concepto de montículo (heap) o cola con prioridades y su implementación: estas tranparencias o, más en detalle, en la lección 18 de estos apuntes.
  • Corrección del algoritmo de construcción de códigos de Huffman[CLRS09].
  • Visualización de códigos Huffman. Otro applet demostrativo de códigos de Huffman (enlace discontinuado).
  • Matroides y algoritmos voraces [CLRS09].
  • Matroides e independencia (D.C. Kozen. The Design and Analysis of Algorithms. Springer-Verlag, 1992).
  • Sobre el problema de planificación de tareas a plazo fijo (transp. 85 de algoritmos voraces): otra solución de coste prácticamente lineal.
• Divide y vencerás.
  • Mergesort in situ (J. Katajainen, T. Pasanen, J. Teuhola: “Practical in-place mergesort”. Nordic Journal of Computing vol. 3, pp. 27–40, 1996).
  • Métodos de ordenación en memoria externa (basados en la idea de la ordenación por mezcla o fusión):
    • Capítulo del libro Algorithms and Data Structures, de Niklaus Wirth.
    • Capítulo del libro Elements of File Structures, de Shashi Gadia.
  • Coste promedio del Quicksort [BB97].
  • Comparación práctica de velocidades de métodos de ordenación: un applet, otro applet
• Programación dinámica.
  • Algoritmo de Floyd-Warshall: ¿por qué basta con una única matriz D[1..n,1..n] y no hace falta considerar el subíndice k?.
  • Planteamiento general (no visto en clase) del algoritmo de Floyd-Warshall para el cálculo de caminos mínimos entre todos los pares de vértices de un grafo dirigido (extraído de la primera edición del libro de Cormen et al.; en la 2ª y 3ª edición [CLRS09] este material ya no está presente) (acceso restringido).
  • Árboles binarios de búsqueda óptimos, ideas para la demostración de la reducción del coste temporal de O(n³) a O(n²) (del libro The Art of Computer Programming, Volume 3: Sorting and Searching, de D.E. Knuth).
  • Problema del viajante de comercio (Algorithmics. Theory and Practice, de Gilles Brassard y Paul Bratley, ed. Prentice Hall, 1988).
  • El ejemplo del recorte óptimo de varillas y las dos soluciones típicas de programación dinámica (top-down con memoization versus bottom-up), del libro [CLRS09].
• Ramificación y poda.
  • Capítulo sobre ramificación y poda del libro Computer Algorithmsde Ellis Horowitz, Sartaj Sahni y Sanguthevar Rajasekaran (la copia es de la primera edición, de 1998; existe una 2ª edición de Silicon Press del año 2007, pero este capítulo es prácticamente el mismo).
  • Capítulo sobre ramificación y poda de un libro similar de 1978 titulado Fundamentals of Computer Algorithms de Ellis Horowitz y Sartaj Sahni (contiene más información).
  • Sección sobre ramificación y poda del libro Fundamentos de Algoritmia de Gilles Brassard y Paul Bratley (ed. Prentice Hall, 1997).
• Programación lineal y reducciones.
  • Lecturas recomendadas:
    • Capítulo 29 del libro de Cormen et al. de la bibliografía.
    • Capítulo 7 del libro de Dasgupta et al. de la bibliografía.
  • Transparencias de la Universidad de Princeton (PDF)
  • Herramientas:
    • Una herramienta en línea para resolver problemas de programación lineal: simplex method tool.
    • Otra herramienta en línea: PHPSimplex.
    • El algoritmo Simplex en la herramienta Maxima: manual.
    • Programación lineal en la herramienta Sage: página web.
    • Software GNU: GLPK / lp_solve.
    • Herramienta comercial (para problemas grandes): CPLEX(tiene versión gratuita para profesores y estudiantes de Unizar, pero hay que registrarse)
    • Varias bibliotecas Python:
      • Python-MIP
      • Python-PuLP
      • Python-docplex (wrapper que se basa en IBM ILOG CPLEX Optimization Studio)
      • Python-PyGLPK (wrapper que se basa en GLPK)
      • Python-scipy (scipy.optimize.linprog)
  • Algunas lecturas históricas:
    • Karmarkar en la prensa norteamericana (1984-1988).
    • Artículo: “George Dantzig’s impact on the theory of computation“, Richard M. Karp, publicado en Discrete Optimization, vol. 5, no. 2, pp. 174-185, 2008.
    • Artículo: “A Brief History of Linear and Mixed-Integer Programming Computation“, Robert E. Bixby, publicado en Documenta Mathematica. Journal der Deutschen Mathematiker-Vereinigung Gegründet 1996. Extra Volume. Optimization Stories. 21st International Symposium on Mathematical Programming, pp. 107-121, Berlin, August 19–24, 2012.
    • Artículo: “Who Invented the Interior-Point Method?“, David Shanno, publicado en Documenta Mathematica. Journal der Deutschen Mathematiker-Vereinigung Gegründet 1996. Extra Volume. Optimization Stories. 21st International Symposium on Mathematical Programming, pp. 55-64, Berlin, August 19–24, 2012.