115116 Diseño de Algoritmos
Trimestre 2008 Primavera
Instructor: Dr. Francisco
Javier Zaragoza Martínez.
Inicio y fin del curso:
miércoles 18 de junio a miércoles 27 de agosto de 2008.
Grupo: CCT01 (lunes,
miércoles y viernes de 11:30
a
13:00).
Asesorías: lunes,
miércoles y viernes de 16:00 a 17:30 en la
oficina H-264.
Salón: F-309.
Cupo: 40 estudiantes incluyendo
a los oyentes.
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.
- Conceptos fundamentales.
- Dividir y vencer.
- Programación dinámica.
- Búsqueda con retroceso.
- Métodos heurísticos.
- Programación concurrente.
Evaluación
Habrá cuatro exámenes y cinco tareas. Cada examen
valdrá 15 puntos y cada tarea valdrá 10 puntos. Se
requiere obtener
- al menos 30 puntos en los exámenes, 25 puntos en las
tareas y un total de al menos 60 puntos para acreditar con S,
- al menos 35 puntos en los exámenes, 30 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, 35 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 dda en gabrijela.azc.uam.mx. Su cuenta
está en la misma máquina, a la que se pueden conectar con
ssh y que tiene
dirección IP 148.206.67.155. 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.
- 18/06: Inicio del curso. Presentación del curso y de las
reglas de
evaluación. Conceptos fundamentales.
- 20/06: Estaré
dando
una conferencia en UAM Cuajimalpa.
- 23/06: Inducción matemática. Primera
tarea (para el
30/06).
- 25/06: Recursión lineal.
- 27/06: Recursión binaria y múltiple.
- 30/06: Divide y vencerás (Búsqueda binaria y
máximo y mínimo).
- 02/07: Divide y vencerás (Torres de Hanoi y variantes). Segunda tarea (para el 14/07). Recalificación de pseudo e invers.
- 04/07: Divide y vencerás (Multiplicación de enteros
y de matrices).
- 07/07: Divide y vencerás (Ordenamiento por mezcla y
quicksort).
- 09/07: Divide y vencerás (k-selección).
- 11/07: Primer examen
parcial: Conceptos fundamentales y
divide y vencerás. Promedio
8.8 de 15.
- 14/07: Búsqueda con retroceso (Reinas al ataque).
- 16/07: Búsqueda con retroceso (Permutaciones). Tercera
tarea (para el 28/07). Recalificación
de torres
y sumasi.
- 18/07: Búsqueda con retroceso (Juego de Nim).
- 21/07: Búsqueda con retroceso (Mochila).
- 23/07: Búsqueda con retroceso (Agente viajero).
- 25/07: Segundo examen
parcial: Búsqueda con retroceso. Promedio 7.4 de 15.
- 28/07: Programación dinámica (Recursión y
memorización).
- 30/07: Programación dinámica (Juego de Nim). Cuarta
tarea (para el 15/08).
Recalificación
de lucas y salva.
- 01/08: Programación dinámica (Mochila).
- 04/08: Programación dinámica (Multiplicación
de matrices).
- 06/08: Programación dinámica (Obtención de
soluciones).
- 08/08: Tercer examen
parcial: Programación dinámica. Promedio 9.5 de 15.
- 11/08: Métodos heurísticos (Algoritmos glotones).
- Ya está
funcionando la conexión a mi maquina.
- Usen el IP 148.206.75.15
(también funciona el servidor de nombres).
- Tendrán
hasta el 15/08 para entregarme la cuarta tarea.
- 13/08: Métodos heurísticos (Algoritmos aleatorios).
Quinta tarea (para el 25/08). Calificaciones de grande y barato.
- 15/08: Métodos heurísticos (Algoritmos de
aproximación).
- 18/08: Programación concurrente (Arquitectura PRAM y
máximo con PRAM).
- 20/08 a 27/08: Etapa eliminatoria del Quinto Concurso de
Programación de la UAM.
- 20/08: Programación concurrente (Suma y
multiplicación de matrices con PRAM).
- Ya puedes descargar el examen
eliminatorio del Quinto Concurso de Programación de la UAM.
Aclaraciones: Problema 2.
- Asiste hoy a las 14:30 en la sala D001 a la visita de la
compañía alemana Continental
Corporation líder en el desarrollo de sistemas
electrónicos para el automóvil.
- 22/08: Programación concurrente
(Máximo con PRAM de escritura común). Sexta
tarea (para el 26/08). Los
que la entregaron recibieron 1 punto.
- 25/08: Cuarto
examen parcial: Métodos
heurísticos y programación concurrente. Promedio 9.3 de 15.
- 27/08: Fin del curso.
- 29/08: Examen global (no habrá).
- 02/09: Entrega de
calificaciones finales y del acta.
- 02/09 a 04/09: Nueva fecha límite para entrega de
solicitudes de Becas Erasmus.
- 02/10: Examen de recuperación (Titular: Francisco
Zaragoza, Suplente: Silvia González, 13:00).
Bibliografía
- Baase y Van Gelder. Algoritmos
computacionales: Introducción
al análisis y diseño. Addison Wesley.
- Bentley. Programming
Pearls. Addison Wesley.
- Berlioux y Bizard. Algorithms. Wiley.
- Cormen, Leiserson, Rivest y Stein. Introduction
to
Algorithms. Mc Graw Hill.
- Dasgupta, Papadimitriou, Vazirani. Algorithms.
Mc Graw Hill.
- Gregorio et
al. Ejercicios de
programación creativos y recreativos en C++. Prentice Hall.
- Kleinberg
y Tardos. Algorithm Design.
Addison Wesley.
- Kreher y Stinson. Combinatorial
Algorithms: Generation, Enumeration, and Search. CRC
Press.
- Parberry. Problems on Algorithms.
Prentice Hall.
- Peña
Mari. Diseño de programas, formalismo y abstracción.
Prentice Hall.
- Roberts.
Thinking Recursively. Wiley.
- Rohl. Recursion
via Pascal. Cambridge.
- Sedgewick.
Algoritmos en C++. Pearson.
- Skiena. The
Algorithm Design Manual. Telos.
- Skiena
y Revilla. Programming
Challenges. Springer Verlag.
- Wilf. Algorithms and
Complexity. A K Peters Ltd.
