115116 Diseño de Algoritmos
Trimestre 2012 Primavera
Instructor: Dr. Francisco
Javier Zaragoza Martínez.
Inicio y fin del curso: lunes 7
de mayo a miércoles 18 de julio de 2012.
Grupo: CSI01 (lunes,
miércoles y viernes de 11:30
a
13:00).
Asesorías: lunes,
miércoles y viernes de 10:00 a 11:30 en la
oficina H-264.
Salón: E304.
Cupo: 50 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.
- 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 al menos ocho tareas. Cada examen
valdrá 10 puntos y cada tarea valdrá al menos 10 puntos.
Se
requiere obtener
- al menos 25 puntos en los exámenes, 25 puntos en las
tareas y un total de al menos 60 puntos para acreditar con S,
- al menos 30 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 35 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 callix.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.79.29. 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.
- 07/05:
Presentación del curso y de las
reglas de
evaluación. Conceptos fundamentales (Inducción
matemática).
- 09/05:
Conceptos fundamentales (Recursión lineal).
- 11/05:
Conceptos fundamentales (Recursión binaria y múltiple). Tarea 1 (para el 18/05). Calificaciones de jacobs.
- 14/05: Divide y
vencerás (Búsqueda binaria y
máximo y mínimo).
- 16/05:
Divide y
vencerás (Torres de Hanoi y variantes).
- 18/05:
Divide y
vencerás (Multiplicación de enteros
y de matrices). Tarea 2 (para el 25/05).
Calificaciones de thtres.
- 21/05: Divide y
vencerás (Ordenamiento por mezcla y
quicksort).
- 23/05: Divide y
vencerás (Mediana y k-selección).
- 25/05: Primer examen
parcial: Conceptos fundamentales y
divide y vencerás. Tarea 3 (para el
29/05).
- 25/05: Eliminatoria
del Noveno Concurso
de
Programación
de
la
UAM.
- 28/05: Búsqueda
con
retroceso
(Recorrido
de
caballo).
- 30/05: Cuarto Concurso de
Programación de la ESCOM. Tarea 4
(para el 06/06). Calificaciones de acaba.
- 01/06: Búsqueda con
retroceso (Reinas al ataque).
- 04/06: Búsqueda con
retroceso (Particiones). Tarea 5 (para el
11/06).
Calificaciones de bituno.
- 06/06:
Búsqueda con
retroceso (Suma exacta).
- 08/06:
Búsqueda
con
retroceso
(Juego de Nim).
- 11/06: Segundo examen
parcial: Búsqueda con retroceso.
- 13/06:
Estaré en un congreso.
- 15/06: Estaré en un congreso.
- 18/06: Programación
dinámica (Recursión y
memoización). Tarea 6 (para el 22/06).
Calificaciones de mjacob.
- 20/06:
Programación dinámica (Subsecuencia
creciente
más larga).
- 22/06:
Programación dinámica (Subsecuencia común
más larga). Tarea 7 (para el 26/06).
- 22/06: Final del
Noveno Concurso
de Programación de la UAM.
- 25/06: No habrá
clase por causas de fuerza mayor.
- 27/06: Programación dinámica (Suma exacta).
- 28/06: Daré una plática sobre algoritmos de
aproximación de 11:30 a 13:00, los invito a asistir.
- 29/06: Programación dinámica (Mochila). Tarea 8
(para el 07/07).
- 02/07: Tercer examen
parcial: Programación dinámica.
- 04/07:
Métodos heurísticos (Algoritmos y heurísticas).
- 06/07:
Métodos
heurísticos
(Algoritmos
aleatorios y de aproximación). Tarea 9 y
Examen 4a (para el 13/07 y 16/07). Calificaciones de grande y barato.
- 09/07: No habrá
clase por causas de fuerza mayor.
- 11/07: Programación concurrente (Arquitectura PRAM y
máximo con PRAM). Tarea 10 y Examen 4b
(para el 18/07). Calificaciones.
- 13/07: Programación concurrente
(Máximo con PRAM de escritura común).
- 16/07: Cuarto examen
parcial: Métodos heurísticos y programación
concurrente.
- 18/07: Fin del
curso. Tal vez les interesen estos tres cursos de temas selectos para
el próximo trimestre: Programación
matemática, Métodos de
búsqueda dirigida y Laboratorio de
Optimización.
- 24/07: Estas son
las calificaciones finales.
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.