115117 Análisis de Algoritmos
Trimestre 2009 Otoño
Instructor: Dr. Francisco
Javier Zaragoza Martínez.
Inicio y fin del curso: lunes
21 de septiembre a lunes 7 de diciembre de 2009.
Grupo: CCT01 (lunes y
miércoles
de 13:00 a 14:30).
Asesorías: lunes,
miércoles y viernes de 16:00 a 17:30 en la
oficina H-264.
Salón: E-309.
Cupo: 40 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 matemáticos básicos.
- Relaciones de recurrencia.
- Comportamiento asintótico de funciones.
- Complejidad computacional de algoritmos.
Evaluación
La calificación será como sigue: Las cuatro tareas
valdrán un total de 40 puntos y los tres exámenes un
total
de 60 puntos. No
habrá examen global. Además de obtener al menos 36
puntos
en los exámenes y al menos 24 puntos en las tareas, se
requiere:
- obtener al menos un total de 60 puntos para acreditar con S,
- obtener al menos un total de 73 puntos para acreditar con B y
- obtener al menos un total de 87 puntos para acreditar con MB.
Las tareas se deberán entregar por correo electrónico a
la cuenta aa 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
exámenes escritos que muestro abajo es tentativo e irá
apareciendo paulatinamente. Las referencias entre paréntesis son
a los números de
página de las notas.
- 21/09: Inicio del
curso. Introducción e inducción matemática (1-18).
- 23/09: Clase cancelada para que
puedan asistir a la plática "Minería de datos
geométrica" impartida por el Dr. Ángel Kuri (13:00-14:00
en B008).
- 25/09: Reposición de clase:
Correctitud
de algoritmos recursivos (19-39).
Ya están listas sus cuentas.
- 28/09: Notación O y tipos de análisis
(40-60).
- 30/09: Análisis de un algoritmo no recursivo: ordenamiento
por montículo
(61-77).
- 01/10 a 05/10: Examen eliminatorio del Sexto Concurso de
Programación de la UAM.
- 05/10:
Derivación y solución de relaciones de
recurrencia
(78-98).
- 07/10: Primer examen
parcial: Introducción al análisis de algoritmos
(1-98).
- 12/10: Día feriado. Examen final del Sexto Concurso de
Programación de
la UAM. Tarea 1 (para el 19/10).
- 14/10: Análisis de algoritmos de divide y vencerás
(99-123).
- 19/10:
Análisis de un algoritmo de divide y
vencerás: quicksort (124-138).
- 21/10:
Análisis de otro algoritmo de divide y
vencerás: k-selección (139-152).
- 23 y 24/10: Concurso
Regional de Programación
ACM-ICPC.
- 26/10: Análisis de algoritmos de programación
dinámica (153-165).
- 28/10: Clase cancelada
para que
puedan asistir a la plática de Softtek (13:00-14:30 en F001). Tarea
2 (para el 09/11).
- 30/10: Reposición
de clase:
Análisis de un algoritmo de
programación
dinámica: producto encadenado de matrices (166-174).
- 02/11: Día
feriado.
- 04/11: Clase cancelada
por falta de electricidad.
- 06/11: Reposición
de clase:
Análisis
de un algoritmo de
programación dinámica: árboles binarios
óptimos (175-188).
- 09/11: Análisis
de un algoritmo de
programación dinámica: Floyd y Warshall (189-197) . Tarea
3 (para el 23/11).
- 11/11: Clase cancelada
debido a que las instalaciones estuvieron cerradas.
- 16/11:
Análisis de dos algoritmos glotones:
almacenamiento óptimo en
cintas (198-206) y problema
continuo de la mochila (207-219).
- 18/11: Segundo examen
parcial: Análisis de algoritmos de divide y
vencerás y de programación dinámica
(99-197).
- 23/11: Análisis de un algoritmo glotón: problema de
unión y búsqueda (234-241).
- 25/11: Clase cancelada
debido a la autoevaluación de CACEI.
- 30/11: No habrá
clase (estaré en el INM).
- 02/12:
Análisis de algoritmos de búsqueda con
retroceso: cadenas k-arias (253-263). Tarea 4
(para el 09/12).
- 04/12:
Análisis de algoritmos de búsqueda con
retroceso: aplicaciones (264-274).
- 07/12: No habrá
clase.
- 09/12: Tercer
examen parcial: en OpenOffice y PDF (entregar en PDF a más tardar a las
16:00 del 9 de diciembre).
- 14/12: Calificaciones finales (aclaraciones el 14/12 de 16:00 a 17:30).
- 06/01: Examen de recuperación (10:00 a 13:00).
Bibliografía
- Baase y Van Gelder. Algoritmos
computacionales: Introducción
al análisis y diseño. Addison Wesley.
- Dasgupta, Papadimitriou, Vazirani. Algorithms.
Mc Graw Hill.
- Kleinberg
y Tardos. Algorithm Design.
Addison Wesley.
- Parberry. Lecture Notes on
Algorithm Analysis and Computational Complexity. University of
North Texas. [Notas del curso.]
- Parberry. Problems on Algorithms.
Prentice Hall. [Libro de problemas.]
- Sedgewick y Flajolet. An Introduction
to the Analysis of Algorithms. Addison Wesley. [Libro más
avanzado.]
- Wilf. Algorithms and
Complexity. A K Peters Ltd.