115116 Diseño de Algoritmos
Trimestre 2007 Invierno
Instructor: Dr. Francisco
Javier Zaragoza Martínez.
Inicio y fin del curso: lunes
15
de enero a viernes 30 de marzo.
Grupos: CCT01 (lunes,
miércoles y viernes de
13:00
a
14:30).
Asesorías: lunes,
miércoles y viernes de 11:30 a 13:00, martes de 9:00 a 10:00 y
de 16:00 a 18:00 en la oficina H-264.
Salón: E-109.
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.
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.
- 15/01: Inicio del curso. Conceptos fundamentales.
- 17/01: Recursión (ejemplos más sencillos).
- 19/01: Recursión (ejemplos más complicados).
- 22/01: Divide y vencerás (Torres de Hanoi).
- 24/01: Divide y vencerás (Máximo y mínimo).
- 26/01: Divide y vencerás (Multiplicación de enteros
y de matrices).
- 29/01: Divide y vencerás (Mergesort). Primera
tarea (para el 02/02). Calificaciones.
- 31/01: Divide y vencerás (Quicksort y Mediana).
- 02/02: Primera evaluación
en clase (Recursión y
Divide y vencerás).
- 05/02: No hay clases (día feriado).
- 07/02: Búsqueda con retroceso (Recorrido de caballo). Segunda tarea (para el 14/02). Calificaciones.
- 09/02: Búsqueda con retroceso (Reinas al ataque).
- 12/02: Búsqueda con retroceso (Nim).
- 14/02: Búsqueda con retroceso (Mochila).
- 16/02: Búsqueda con retroceso (Agente viajero). Tercera
tarea (para el 02/03). Calificaciones.
- 19/02: Segunda evaluación
en clase (Búsqueda con retroceso).
- 21/02: Programación dinámica (Recursión y
memorización).
- 23/02: Programación dinámica (Mochila). Cuarta tarea (para el 09/03). Calificaciones.
- 26/02 y 28/02: No hay clases (estaré
en una conferencia).
- 02/03: Programación dinámica (Nim).
- 05/03: Programación dinámica (Multiplicación
de matrices).
- 07/03: Programación dinámica (Cambio).
- 09/03: Programación dinámica (Obtención de
soluciones).
- 12/03: Tercera evaluación
en clase (Programación dinámica).
- 14/03: Métodos heurísticos (Algoritmos glotones). Quinta tarea (para el 23/03). Calificaciones.
- 16/03: Métodos heurísticos (Algoritmos aleatorios).
- 19/03: Métodos heurísticos (Algoritmos de
aproximación).
- 21/03: No hay clases (día feriado).
- 23/03: Por causas de fuerza mayor no daré clase. Sexta
tarea (para el
30/03). Calificaciones.
- 26/03: Programación concurrente (PRAM y máximo).
- 28/03: Programación concurrente (Suma y
multiplicación de matrices con PRAM).
- 30/03: Fin del curso. Programación concurrente (Máximo con PRAM de escritura
común).
- 02/04: Cuarta evaluación
(métodos heurísticos y programación
concurrente).
- 09/04: Entrega de acta a las 16:00. Nota: si ven que alguna
calificación falta es porque no me llegó ese programa y
si ven que es más baja de lo que creen es muy probable que sea
porque su programa escribe letreros y mi evaluador no sabe que hacer
con ellos. En estos casos, requiero que me reenvíen sus
programas a más tardar el lunes 9 de abril a las 13:00.
- 18/04: El examen de recuperación está programado de
10:00 a 13:00 en el E208 pero lo más probable es que lo hagamos
en el Laboratorio de Base de Datos pues tendrán que escribir
programas.
Bibliografía
- [BB] Algorithms, Berlioux y Bizard, Wiley.
- [Be] Programming
Pearls, Bentley, Addison Wesley.
- [BV] Algoritmos
computacionales: introducción
al análisis y diseño, Baase y Van Gelder, Pearson.
- [CL] Introduction
to
Algorithms, Cormen,
Leiserson, Rivest y Stein, Mc Graw Hill.
- [GL] Ejercicios de
programación creativos y recreativos en C++, Gregorio et
al., Prentice Hall.
- [KS] Combinatorial
Algorithms: Generation, Enumeration, and Search, Kreher y Stinson, CRC
Press.
- [Pa] Problems
on Algorithms, Parberry,
Prentice Hall.
- [PM] Diseño de programas, formalismo y abstracción,
Peña
Mari, Prentice Hall.
- [Rb] Thinking Recursively, Roberts,
Wiley.
- [Rh] Recursion
via Pascal, Rohl, Cambridge.
- [Se] Algoritmos en C++, Sedgewick,
Pearson.
- [Sk] The
Algorithm Design Manual, Skiena, Telos.
- [SR] Programming
Challenges, Skiena
y Revilla,
Springer Verlag.