UAM


1151040 Análisis y Diseño de Algoritmos
Trimestre 2018 Primavera

Instructor: Dr. Francisco Javier Zaragoza Martínez.
Inicio y fin del curso: lunes 7 de mayo a viernes 20 de julio de 2018.
Grupo: CSI01 (lunes, miércoles y viernes de 10:00 a 11:30).
Asesorías: lunes, miércoles y viernes de 9:00 a 10:00 en el G-210.
Salón: E309.
Cupo: 50 alumnos.

Contenido

Se cubrirá el contenido oficial del curso (el cual se detalla abajo). Es posible que el temario se cubra en un orden distinto al allí mencionado.
  1. Análisis de correctitud y complejidad.
  2. Recursividad y ecuaciones de recurrencia.
  3. Algoritmos de divide y vencerás.
  4. Algoritmos de búsqueda con retroceso.
  5. Algoritmos de programación dinámica.
  6. Algoritmos de búsqueda local.
  7. Algoritmos glotones.
  8. Problemas NP completos.

Evaluación

Habrá cuatro exámenes y al menos ocho tareas. Cada examen valdrá 15 puntos y cada tarea valdrá 5 puntos. No habrá examen global. Se requiere obtener
Las tareas se deberán entregar como se indique en clase y deberán estar escritas en C o C++. Recuerden que, de acuerdo al Reglamento de Alumnos de la UAM, es falta de los alumnos en contra de la Institución el suplantar o permitir ser suplantado en la realización de actividades académicas (Artículo 9) y se impondrá desde amonestación escrita hasta suspensión por dos trimestres (Artículo 13).

Calendario

El calendario de clases, de entrega de tareas y de evaluaciones que muestro abajo es tentativo e irá apareciendo paulatinamente. Las transparencias para los primeros temas están aquí. Los materiales para los otros temas están acá.

  • 07/05: Inicio del curso. Presentación del curso y de las reglas de evaluación.
  • 09/05: Introducción e inducción matemática. Tarea 1 (para el 16/05).
  • 11/05: Correctitud de algoritmos recursivos.
  • 14/05: Correctitud de algoritmos iterativos. Para aprender a usar Omegaup hagan estos ejercicios.
  • 16/05: Notación O y complejidad de algoritmos. Tarea 2 (para el 25/05).
  • 18/05: Complejidad de algoritmos iterativos.
  • 21/05: Recursividad y ecuaciones de recurrencia.
  • 23/05: Teorema general de ecuaciones de recurrencia.
  • 25/05: Primer examen parcial.
  • 28/05: Algoritmos de divide y vencerás (recursión, búsqueda binaria, potencias). Tarea 3 (para el 04/06).
  • 30/05: Algoritmos de divide y vencerás (ordenamiento por inserción y mezcla).
  • 01/06: Algoritmos de divide y vencerás (quicksort, selección, cadenas binarias, suma).
  • 04/06: Algoritmos de divide y vencerás (suma de subconjuntos).
  • 06/06: Algoritmos de divide y vencerás (multiplicación de enteros y de matrices). Tarea 4 (para el 11/06).
  • 08/06: Algoritmos de búsqueda con retroceso (suma de subconjuntos).
  • 11/06: Algoritmos de búsqueda con retroceso (recorrido del caballo). Tarea 5 (para el 15/06).
  • 13/06: Algoritmos de búsqueda con retroceso (problema de las reinas).
  • 15/06: Segundo examen parcial.
  • 18/06: Algoritmos de programación dinámica (recursión y memoización). Tarea 6 (para el 25/06).
  • 20/06: Algoritmos de programación dinámica (suma de subconjuntos).
  • 22/06: Algoritmos de programación dinámica (subsecuencia creciente más larga). Tarea 7 (para el 29/06).
  • 25/06: Algoritmos de programación dinámica (subsecuencia común más larga).
  • 27/06: Algoritmos de programación dinámica (problema de la mochila).
  • 29/06: Tercer examen parcial.
  • 02/07: Algoritmos de búsqueda local (introducción: ajedrez y cubo de Rubik).
  • 04/07: Algoritmos de búsqueda local (comesolo y gato). Tarea 8 (para el 11/07).
  • 06/07: Algoritmos de búsqueda local (juego de 16).
  • 09/07: Algoritmos glotones (planificación de intervalos). Tarea 9 (para el 16/07).
  • 11/07: Algoritmos glotones (compresión de Huffman).
  • 13/07: Algoritmos glotones (planificación minimizando la tardanza).
  • 16/07: Problemas NP completos (reducciones polinomiales).
  • 18/07: Problemas NP completos (las clases P y NP).
  • 20/07: Cuarto examen parcial. Fin del curso.
  • Bibliografía

    1. Baase y Van Gelder. Algoritmos computacionales: Introducción al análisis y diseño. Addison Wesley.
    2. Dasgupta, Papadimitriou, Vazirani. Algorithms. Mc Graw Hill.
    3. Kernighan y Ritchie. El lenguaje de programación C. Pearson.
    4. Kleinberg y Tardos. Algorithm Design. Addison Wesley.
    5. Knuth. The Art of Computer Programming: Vol. 3 Sorting and Searching. Addison Wesley.
    6. Parberry. Problems on Algorithms. Prentice Hall.
    7. Roberts. Thinking Recursively. Wiley.
    8. Sedgewick. Algoritmos en C++. Pearson.