Cinvestav
Departamento de Computación

Contenido del Curso de

Análisis y Diseño de Algoritmos


Cuatrimestre agosto a diciembre de 2021

Objetivo:

Presentar las técnicas para analizar y diseñar algoritmos y revisar la teoría computacional relacionada con la clasificación de problemas. En este curso se revisará el proceso de análisis de algoritmos, así como las técnicas utilizadas para diseñar algoritmos eficientes. En la primera parte se introducirán algunos conceptos matemáticos necesarios para el análisis de algoritmos. Se revisarán los modelos computacionales más utilizados y se definirá de manera breve lo que se entiende por complejidad computacional. En la segunda parte se ejemplificará la complejidad de los algoritmos mediante el análisis de algoritmos típicos como ordenamiento, búsquedas, algoritmos sobre gráficas, etc. En la tercera parte se presentarán técnicas de diseño de algoritmos generales como programación dinámica, algoritmos ávidos y métodos branch-and-bound. Finalmente, en la cuarta parte se presentarán algunos resultados que determinan las clases de complejidad. Se introducirá la clasificación de los problemas de decisión, los problemas difíciles y los problemas completos, los problemas polinomiales y no-polinomiales.

Contenido:

  1. Introducción
    1. Motivación
    2. Algoritmos
  2. Parte uno: Fundamentos
    1. Nociones matemáticas y terminología
    2. Análisis de algoritmos
      1. Diseño de algoritmos
      2. Ejemplos básicos
    3. Crecimiento de funciones
      1. Notación asintótica
      2. Las funciones más comunes
    4. Divide y vencerás y métodos para resolver recurrencias
      1. Dos problemas que se resuelven usando divide y vencerás:
        1. El problema del sub-arreglo máximo
        2. Multiplicación de matrices: algoritmo de Strassen
      2. El método de sustitución para resolver recurrencias
      3. Árbol de recursión para resolver recurrencias
      4. El método maestro
    5. Análisis probabilístico y algoritmos aleatorizados
      1. Un problema que se resuelve usando algoritmos aleatorizados
      2. Variables indicadoras
      3. Algoritmos aleatorizados y su análisis
  3. Parte dos: Ordenación y Estadísticas de orden
    1. Algoritmos básicos de ordenación
      1. Heapsort
      2. Quicksort
    2. Ordenación en tiempo lineal
      1. Cota inferior de ordenación
      2. Counting sort, bucket sort, radix sort
    3. Medianas y otras estadísticas de orden
      1. Mínimo y máximo
      2. i-ésima estadística de orden en línea
  4. Parte tres: Estructura de datos
    1. Árboles binarios de búsqueda (Binary Search Trees)
      1. Operaciones básicas
      2. BST construidos aleatoriamente
    2. Árboles rojos y negros
      1. Propiedades
      2. Operaciones básicas
    3. Estructura de datos dinámicas (augmenting data structures)
      1. Estadísticas de orden dinámicas
      2. Cómo aumentar una estructura de datos
      3. Una estructura de datos dinámica: Árboles de intervalos
  5. Parte cuatro: Técnicas avanzadas de diseño y análisis
    1. Programación dinámica
      1. Dos problemas que se resuelven usando programación dinámica:
        1. Rod cutting
        2. Multiplicación de cadenas de matrices
      2. El método de la programación dinámica
      3. Subsecuencia común más larga
    2. Algoritmos glotones (greedy algorithms)
      1. Un problema que se resuelve usando algoritmos glotones: el problema de la selección de actividades
      2. Los algoritmos glotones
      3. Códigos de Huffman
    3. Análisis amortizado (*opcional)
      1. Análisis agregado (aggregate analysis)
      2. El método de la contabilidad (the accounting method) y el método del potencial (the potential method)
      3. Tablas dinámicas
  6. Parte cinco: Algoritmos en gráficas
    1. Algoritmos elementales en gráficas
      1. BFS, DFS
      2. Topological sort
      3. Componentes conexas
    2. Árboles generadores de peso mínimo
      1. Propiedades
      2. Algoritmo de Prim y Kruskal
    3. Caminos más cortos
      1. Caminos más cortos desde una sola fuente. Algortimo de Bellman-Ford y Dijkstra
      2. Caminos más cortos para todas las parejas. Algoritmo de Floyd-Warshall y de Johnson

Bibliografía básica

  1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms, Third Edition (3rd ed). The MIT Press.
  2. Jon Kleinberg and Eva Tardos. 2005. Algorithm Design. Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA.
  3. Alfred V. Aho, and John E. Hopcroft, 1974 The Design and Analysis of Computer Algorithms. (1st ed.) Addisson-Wesley Longman Publishing Co., Inc., Boston, MA, USA.

Bibliografía complementaria

  1. Robert Sedgewick, Kevin Wayne. 2011. Algorithms, Fourth Edition (4th ed.). Addison-Wesley Professional.
  2. George Heineman, Gary Pollice, and Stanley Selkow. 2008. Algorithms in a Nutshell. O’Reilly Media, Inc.
  3. Thomas H. Cormen. 2013. Algorithms Unlocked (1 ed). The MIT Press.
  4. Peter Brass. 2008. Advanced Data Structures (1 ed.). Cambridge University Press, New York, NY, USA.

Luis Gerardo de la Fraga
Última actualización: 30 de agosto, 2021