1151040 Análisis y Diseño de Algoritmos
Trimestre 2013 Otoño
Instructor: Dr. Francisco Javier
Zaragoza Martínez.
Inicio y fin del curso:
lunes 26 de agosto a martes 12 de noviembre 2013.
Grupo: CSI81 (lunes,
miércoles y viernes de 16:00 a 17:30).
Asesorías: lunes, miércoles
y viernes de 15:00 a 16:00 en la oficina H-264.
Salón: E309.
Cupo: 50.
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 por correo electrónico a la cuenta ada en callix.azc.uam.mx y deberán estar escritas en C o C++.
Su cuenta está en la misma máquina, a la que se pueden conectar
con ssh.
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á.
Guía para usar su cuenta de callix.
26/08:
Inicio del curso. Presentación del curso y de las reglas de
evaluación. Introducción e inducción matemática. Tarea 1 (para el 02/09).
28/08:
Correctitud de algoritmos recursivos e iterativos.
30/08:
Notación O y complejidad de algoritmos.
02/09: Recursividad y ecuaciones de
recurrencia. Tarea 2 (para el 09/09).
04/09: Teorema general de ecuaciones de recurrencia.
06/09: Primer
examen parcial.
09/09:
Algoritmos de divide y vencerás (mínimo, máximo y Fibonacci). Tarea 3 (para el 16/09).
11/09:
Algoritmos de divide y vencerás (multiplicación de enteros y
fractales).
13/09:
Algoritmos de divide y vencerás (ordenamiento por mezcla y
quicksort). Tarea 4 (para el 20/09).
16/09: Día
feriado.
18/09: Clase
cancelada por el paro.
20/09: Algoritmos de divide y
vencerás (suma de subconjuntos).
23/09:
Algoritmos de búsqueda con retroceso (recorrido del caballo). Tarea 5 (para el 30/09).
25/09:
Algoritmos de búsqueda con retroceso (problema de las reinas).
27/09:
Segundo examen parcial.
30/09: Algoritmos de programación
dinámica (recursión y memoización). Tarea 6
(para el 09/10).
02/10: Algoritmos de programación
dinámica (suma de subconjuntos).
04/10: Algoritmos de programación
dinámica (problema de la mochila).
07/10:
Algoritmos de programación dinámica (subsecuencia creciente más
larga).
09/10:
Clase cancelada por causas de fuerza mayor.
10/10:
Décimo aniversario de Ingeniería en
Computación. ¡No faltes!
11/10:
Algoritmos de programación dinámica (subsecuencia común más
larga). Tarea 7 (para el 18/10).
14/10: Algoritmos de búsqueda local.
16/10: Algoritmos de búsqueda local.
18/10: Tercer
examen parcial.
21/10:
Algoritmos glotones.
23/10:
Algoritmos glotones. Tarea 8 (para el
30/10).
25/10:
Problemas NP completos.
28/10: Problemas NP completos.
30/10: Problemas NP completos. Tarea 9 y cuarto examen parcial (para el
06/11).
01/11: Día
feriado.
04/11: Fin
del curso.
06/11:
Fin del curso.
08/11:
Concurso de
programación ACM-ICPC.
11/11: Examen global.
12/11: Coloquio Tlahuilcalli: El
hombre que tomaba café, cien años de Paul Erdös.
15/11: Estas
son las
calificaciones finales.
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.