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.
- Análisis de correctitud y complejidad.
- Recursividad y ecuaciones de recurrencia.
- Algoritmos de divide y vencerás.
- Algoritmos de búsqueda con retroceso.
- Algoritmos de programación dinámica.
- Algoritmos de búsqueda local.
- Algoritmos glotones.
- 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
- al menos 30 puntos en los exámenes, 20 puntos en las tareas y
un total de al menos 60 puntos para acreditar con S,
- al menos 35 puntos en los exámenes, 25 puntos en las tareas y
un total de al menos 73 puntos para acreditar con B y
- al menos 40 puntos en los exámenes, 30 puntos en las tareas y
un total de al menos 87 puntos para acreditar con MB.
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
- Baase y
Van Gelder. Algoritmos
computacionales: Introducción
al
análisis y diseño. Addison Wesley.
- Dasgupta, Papadimitriou,
Vazirani.
Algorithms.
Mc Graw Hill.
- Kernighan y Ritchie. El lenguaje de programación C. Pearson.
- Kleinberg
y Tardos.
Algorithm Design.
Addison Wesley.
- Knuth.
The
Art of Computer Programming: Vol. 3 Sorting and Searching.
Addison Wesley.
- Parberry. Problems on
Algorithms. Prentice Hall.
- Roberts.
Thinking Recursively. Wiley.
- Sedgewick.
Algoritmos en C++. Pearson.