1151040 Análisis y Diseño de Algoritmos
Trimestre 2016 Primavera
Instructor: Dr. Francisco Javier
Zaragoza Martínez.
Inicio y fin del curso:
lunes 9 de mayo a martes 6 de septiembre
de 2016.
Grupo: CSI01 (martes y
jueves de 9:15 a 11:30).
Asesorías: lunes, miércoles
y viernes de 11:30 a 13:00 en la oficina H-264.
Salón: E309.
Cupo: 40 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á. Guía para usar su cuenta de callix.
10/05:
Día feriado.
12/05:
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 19/05).
17/05: Correctitud de algoritmos
recursivos e iterativos.
19/05: Notación O y complejidad de
algoritmos. Tarea 2 (para el 26/05).
24/05:
Recursividad y ecuaciones de recurrencia.
26/05:
Primer examen parcial. Tarea 3 (para el 02/06).
31/05: Algoritmos de divide y
vencerás (búsqueda binaria, máximo y mínimo).
02/06: Algoritmos de divide y
vencerás (mezcla, quicksort, selección). Tarea
4 (para el 09/06).
07/06:
Algoritmos de divide y vencerás (hanoi, enteros, matrices).
09/06:
No hubo clase por causas de fuerza mayor.
Tarea 5 (para el 23/06).
14/06: Algoritmos de búsqueda con
retroceso (cadenas binarias con restricciones).
16/06: Algoritmos de búsqueda
con retroceso (reinas pacíficas, recorrido de caballo). Tarea 6
(para el 30/06 en clase).
21/06:
No hubo clase por
paro. Segundo examen parcial (para entregar el 30/06
en clase junto con la Tarea 6).
23/06:
Algoritmos de programación dinámica (memoización, Fibonacci, suma
de subconjuntos). Tarea 7 (para el 30/06).
28/06: No hubo clase por paro.
30/06: Algoritmos de programación
dinámica (problema del cambio, problema de la mochila,
recuperación de soluciones). Tarea 8 (para
el 07/07).
05/07:
Algoritmos de programación dinámica (subsecuencia creciente más
larga, subsecuencia común más larga).
06/07-25/07:
No hubo clase por
paro.
26/07: Algoritmos de programación
dinámica (recordatorio y más).
28/07: Tercer
examen parcial.
30/08:
Algoritmos de búsqueda local.
01/09:
Algoritmos glotones. Problemas
NP completos.
06/09: Envíenme
su usuario de OmegaUp y vengan a mi oficina (9:15 a 11:30) para
revisar lo que mandaron. Fin del curso.
12-14/09: Los invito a que asistan a
la Escuela de
algoritmos de aproximación.
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.