115117 Análisis 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 (martes y jueves
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: E309.
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 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 mejores cuatro
tareas (de un máximo de siete)
valdrán
un
total
de
40
puntos
y los cuatro exámenes un
total
de 60 puntos. No
habrá evaluación terminal. 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 que sean programas 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.
- 07/05:
Introducción e inducción
matemática
(Lectura previa 1-18 o si quieren pueden presentarse en el E304 de
11:30 a 13:00).
- 08/05:
Presentación del curso y de las
reglas de
evaluación. Correctitud
de algoritmos recursivos e iterativos (19-39). Tarea
1 (para el 24/05).
- 10/05: Día
feriado.
- 15/05: Día feriado.
- 17/05: Notación O y tipos de análisis
(40-60).
- 22/05:
Análisis de un algoritmo no recursivo: ordenamiento
por montículo
(61-77).
- 24/05:
Derivación y
solución de relaciones de
recurrencia
(78-88) y Teorema general (89-98). Tarea 2 (para
el 29/05).
- 25/05: Eliminatoria
del Noveno Concurso
de
Programación
de
la
UAM.
- 29/05: Primer examen
parcial: Introducción al análisis de algoritmos
(1-98).
- 31/05: Análisis de algoritmos de divide y vencerás
(99-123). Tarea 3
(para el 12/06).
- 05/06:
Análisis de un algoritmo de divide y
vencerás: quicksort (124-138).
- 07/06:
Análisis de otro algoritmo de divide y
vencerás: k-selección (139-152).
- 12/06: Segundo examen
parcial: Análisis de algoritmos de divide y
vencerás (99-152).
- 14/06:
Estaré en un congreso.
- 19/06:
Análisis de algoritmos de programación
dinámica (153-165). Tarea 4
(para el 28/06).
- 21/06:
Análisis de un algoritmo de
programación
dinámica: producto encadenado de matrices (166-174). Tarea 5 (para el 26/06).
- 22/06: Si quieren
pueden presentarse en el E304 de 11:30 a 13:00 para ver algo de
programación dinámica (subsecuencia común
más larga).
- 22/06: Final del
Noveno Concurso
de Programación de la UAM.
- 26/06: No habrá
clase por causas de fuerza mayor.
- 27/06: Si quieren pueden presentarse en el E304 de 11:30 a 13:00
para ver algo de programación dinámica (suma exacta).
- 28/06: Tercer examen
parcial: Análisis de algoritmos
de programación dinámica.
- 03/07:
Análisis de un
algoritmo glotón:
almacenamiento óptimo en
cintas y problema
continuo de la mochila (198-219). Tarea 6 (para
el 10/07).
- 05/07:
Análisis de un algoritmo glotón: problema de
unión y búsqueda (234-241).
- 10/07: Análisis de algoritmos de búsqueda con
retroceso: cadenas k-arias (253-274). Tarea 7
(para el 17/07).
- 12/07: Análisis de algoritmos de búsqueda con
retroceso: permutaciones (275-290).
- 17/07: Cuarto examen parcial:
Análisis
de algoritmos glotones y de búsqueda con
retroceso.
- 18/07: 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.
- 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.