115116 Diseño de Algoritmos
Trimestre 2010 Otoño
Instructor: Dr. Francisco
Javier Zaragoza Martínez.
Inicio y fin del curso: lunes
20 de septiembre a viernes 3 de diciembre de 2010.
Grupo: CCT01 (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: F101.
Cupo: 50 estudiantes.
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 ocho tareas. Cada examen
valdrá 10 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 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.
- 20/09: Inicio del
curso. Presentación del curso y de las
reglas de
evaluación. Conceptos fundamentales.
- 22/09:
Recursión lineal.
- 23/09 a 28/09:
Examen eliminatorio del Séptimo Concurso de
Programación de la UAM. Forma de inscripción y examen eliminatorio (corregido).
- 24/09:
Recursión binaria y múltiple.
- 27/09: Divide y vencerás (Búsqueda binaria y
máximo y mínimo). Nos
cambiamos
al
F101.
- 29/09: Divide y vencerás (Torres de Hanoi y variantes). Primera tarea (para el 04/10). Calificaciones de pado y zeta.
- 01/10: Divide y
vencerás (Multiplicación de enteros
y de matrices).
- 04/10: Divide y
vencerás (Ordenamiento por mezcla y
quicksort). Segunda tarea (para el 08/10).
Calificaciones de curvac y hanoic.
- 06/10: Divide y
vencerás (Mediana y k-selección).
- 08/10: Primer examen
parcial: Conceptos fundamentales y
divide y vencerás. Tarea extra y calificaciones.
- 08/10 a 11/10:
Examen final
del Séptimo Concurso de Programación
de la UAM. Aquí está el examen.
- 11/10: Búsqueda
con
retroceso (Recorrido de caballo).
- 13/10: Búsqueda con retroceso (Reinas al ataque).
- 15/10: Búsqueda
con
retroceso
(Permutaciones).
Tercera
tarea
(para
el
24/10).
- 18/10:
Búsqueda con retroceso (Particiones).
- 20/10:
Búsqueda con retroceso (Juego de Nim).
- 22/10: Búsqueda
con
retroceso
(Mochila).
Cuarta
tarea
(para
el 05/11). Calificaciones de sumapq y ksumas.
- 25/10: Búsqueda con retroceso (Agente viajero). Clase cancelada por causas de fuerza
mayor.
- 27/10: Programación dinámica (Recursión y
memorización).
- 29/10: Programación dinámica (Subsecuencia
creciente
más larga). Quinta tarea (para el 08/11).
Calificaciones de padopd y zetapd.
- 01/11: Día
feriado.
- 03/11: Segundo examen
parcial: Búsqueda con retroceso.
- 05/11:
Programación dinámica (Mochila).
- 08/11: Programación dinámica (Subsecuencia
común más larga). Sexta tarea
(para el
15/11).
- 10/11: Programación dinámica (Suma de subconjuntos).
- 12/11: Programación dinámica (Producto encadenado
de matrices).
- 15/11: Tercer examen
parcial: Programación dinámica.
- 17/11:
Métodos
heurísticos
(Algoritmos
glotones). Séptima tarea (para el 29/11).
Calificaciones de grande y barato.
- 19/11:
Métodos
heurísticos
(Algoritmos aleatorios).
- 22/11: Estaré
en
un
congreso.
- 24/11: Estaré en un congreso.
- 26/11: Estaré en un congreso.
- 29/11:
Programación concurrente (Arquitectura PRAM y
máximo con PRAM). Octava tarea (para el
08/12).
- 01/12:
Programación concurrente (Máximo con PRAM de escritura
común).
- 03/12: Clase cancelada por causas de fuerza
mayor.
- 08/12: Cuarto examen
parcial: Métodos heurísticos y
programación
concurrente.
- 14/12: Entrega del acta. Si consideran que hubo algún error
en la calificación no duden en ponerse en contacto conmigo. En
caso de que tengan razón hacemos corrección de
calificación.
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.
