115116 Diseño de Algoritmos
Trimestre 2012 Otoño
Instructor: Dr. Francisco Javier
Zaragoza Martínez.
Inicio y fin del curso:
lunes 10 de septiembre a jueves 29 de noviembre 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: Byron.
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 5
puntos. Se requiere obtener
- al menos 25 puntos en los exámenes, 25 puntos en las
tareas y un total de 60 puntos para acreditar con S,
- al menos 30 puntos en los exámenes, 30 puntos en las
tareas y un total de 73 puntos para acreditar con B y
- al menos 35 puntos en los exámenes, 35 puntos en las
tareas y un total de 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.
- 10/09:
Presentación del curso y de las reglas de
evaluación. Conceptos fundamentales (Inducción
matemática).
- 12/09: Conceptos
fundamentales (Recursión lineal).
- 14/09: Conceptos
fundamentales (Recursión binaria y múltiple). Tarea 1 (para el 24/09). Calificaciones de
catalan y stirling.
- 17/09: Divide y vencerás (Búsqueda binaria y
máximo y mínimo).
- 19/09: Divide y vencerás (Torres de Hanoi y variantes).
- 21/09: Divide y vencerás (Multiplicación de
enteros y de matrices). Tarea 2 (para el
28/09). Calificaciones de hanoic y pfijo.
- 24/09: Divide y
vencerás (Ordenamiento por mezcla y quicksort).
- 26/09: Divide y
vencerás (Mediana y k-selección).
- 28/09: Primer examen parcial: Conceptos
fundamentales y divide y vencerás.
- 01/10: Búsqueda con retroceso (Suma exacta).
- 03/10: Búsqueda
con retroceso (Mochila). Tarea 3 (para el
12/10). Calificaciones de divtor.
- 05/10: Búsqueda con retroceso (Particiones).
- 08/10: Búsqueda con
retroceso (Juego de Nim).
- 10/10:
Búsqueda con retroceso (Recorrido de caballo). Tarea 4 (para el 19/10). Calificaciones de
ksuma y nofijo.
- 12/10:
Día feriado.
- 15/10: Búsqueda con retroceso (Reinas al ataque).
- 17/10:
Búsqueda con retroceso (Permutaciones).
- 19/10: Segundo examen parcial: Búsqueda con
retroceso. Nos cambiamos a la sala Ada Byron.
- 22/10: Programación
dinámica (Recursión y memoización).
- 24/10:
Programación dinámica (Suma exacta).
- 26/10:
Programación dinámica (Cambio y obtención
de soluciones). Tarea 5 (para el 31/10).
Calificaciones de catampd y stirmpd.
- 29/10: Programación dinámica (Mochila y
obtención de soluciones).
- 31/10: Estaré en una conferencia.
- 02/11: Día feriado.
- 05/11:
Programación dinámica (Subsecuencia creciente
más larga). Tarea 6 (para el
12/11). Calificaciones de muerde y
cortac.
- 07/11:
Programación dinámica (Subsecuencia común
más larga).
- 09/11: No habrá clase.
- 12/11: Tercer examen
parcial: Programación dinámica.
- 14/11: Métodos heurísticos.
- 16/11: Métodos heurísticos (Algoritmos
glotones).
- 19/11:
Métodos heurísticos (Algoritmos aleatorios). Tarea 7 (para el 23/11).
- 21/11:
Programación concurrente (Arquitectura PRAM).
- 23/11:
Programación concurrente (Máximo con PRAM de
escritura común). Tarea 8 (para
el 29/11).
- 26/11: Cuarto examen
parcial: Programación
concurrente.
- 28/11: Fin del curso.
- 11/12: 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.
