115116 Diseño de Algoritmos
Trimestre 2007 Primavera
Instructor: Dr. Francisco
Javier Zaragoza Martínez.
Inicio y fin del curso: lunes
23 de abril a viernes 6 de julio.
Grupo: CCT81 (martes,
miércoles y jueves de 16:00
a
17:30).
Asesorías:
miércoles de 9:00 a 13:00 y jueves de 11:30 a 13:00 en la
oficina H-264.
Salón: F-210.
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 seis tareas. Cada examen
valdrá 15 puntos y cada tarea valdrá 10 puntos. Se
requiere obtener
- al menos 25 puntos en los exámenes, 30 puntos en las
tareas y un total de al menos 60 puntos para acreditar con S,
- al menos 30 puntos en los exámenes, 35 puntos en las
tareas y un total de al menos 73 puntos para acreditar con B y
- al menos 35 puntos en los exámenes, 40 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.
- 24/04: Inicio del curso. Conceptos fundamentales.
- 25/04: Inducción matemática.
- 26/04: Recursión lineal.
- 27/04: Recursión binaria y múltiple. Clase extra de 16:00 a 17:30 en el
F-210.
- 01/05: Día feriado.
- 02/05: Día perdido por
el paro. Primera tarea (para el 07/05).
Calificaciones de curvad y curvag.
- 03/05: Divide y vencerás (Búsqueda binaria y
máximo y mínimo).
- 04/05: Divide y vencerás (Torres de Hanoi y variantes). Clase extra de 16:00 a 17:30 en el
F-210.
- 08/05: Divide y vencerás (Multiplicación de enteros
y de matrices). Segunda tarea (para el 18/05).
Calificaciones de modulo y thtres.
- 09/05: No estaré en la
UAM.
- 10/05: Día feriado.
- 15/05: Día feriado.
- 16/05: Divide y vencerás (Ordenamiento por mezcla y
Quicksort).
- 17/05: Divide y vencerás (k-selección). Clase perdida por
el paro.
- 18/05: Búsqueda con retroceso (Reinas al ataque). Clase extra de 16:00 a 17:30 en el
F-210.
- 22/05: Primer examen
parcial: Conceptos fundamentales y
divide y vencerás.
- 23/05: Búsqueda con retroceso (Permutaciones). Tercera tarea (para el 31/05). Calificaciones de bituno y nofijo.
- 24/05: Búsqueda con retroceso (Juego de Nim).
- 29/05: Búsqueda con retroceso (Mochila).
- 30/05: Búsqueda con retroceso (Agente viajero).
- 31/05: Búsqueda con retroceso (Particiones).
- 05/06: Segundo examen
parcial: Búsqueda con retroceso.
- 06/06: Programación dinámica (Recursión y
memorización).
- 07/06: Programación dinámica (Juego de Nim). Cuarta tarea (para el 26/06). Calificaciones de series y muerde.
- 12/06: Programación dinámica (Mochila).
- 13/06: Programación dinámica (Multiplicación
de matrices).
- 14/06: Programación dinámica (Obtención de
soluciones).
- 19/06: Tercer examen
parcial: Programación dinámica.
- 18/06 a 22/06: Estaré en una conferencia.
- 26/06: Métodos heurísticos (Algoritmos glotones:
asignación de intervalos). Quinta tarea
(para el 09/07).
- 27/06: Métodos heurísticos (Algoritmos aleatorios:
agente viajero).
- 28/06: Métodos heurísticos (Algoritmos de
aproximación: balance de carga).
- 03/07: Programación concurrente (Arquitectura PRAM y
máximo con PRAM). No
habrá sexta tarea (se duplicará la calificación
más alta).
- 04/07: Programación concurrente (Suma y
multiplicación de matrices con PRAM).
- 05/07: Programación concurrente
(Máximo con PRAM de escritura común).
- 10/07: Cuarto
examen parcial: Métodos
heurísticos y programación concurrente
- 11/07: No habrá clase.
- 12/07: Fin del curso.
- 20/07: Entrega de calificaciones y del acta.
- 04/09: Examen de recuperación (16:00 a 19:00, Titular:
Francisco Zaragoza, Suplente: Josué Figueroa).
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.
- Gregorio et
al. Ejercicios de
programación creativos y recreativos en C++. Prentice Hall.
- 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.
