115117 Análisis de Algoritmos
Trimestre 2008 Invierno
Instructor: Dr. Francisco
Javier Zaragoza Martínez.
Inicio y fin del curso: lunes
14 de enero a miércoles 4
de junio de 2008.
Grupo: CCT81 (lunes,
miércoles y viernes de 15:00
a
16:00).
Asesorías: lunes,
miércoles y viernes de 10:00 a 11:30 en la
oficina H-264.
Salón: E-309.
Cupo: 35 estudiantes y 10
oyentes.
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 cinco tareas
valdrán un total de 50
puntos y los dos
exámenes un
total
de 50 puntos. No
habrá examen global. Además de obtener al menos 30
puntos
en los exámenes y al menos 30 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 gabrijela.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.67.155. 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 de
Parberry. Aquí están las notas
actualizadas hasta el 26 de
mayo.
- 14/01: Inicio del curso. Presentación del curso y de las
reglas de
evaluación.
- 16/01: Introducción: Complejidad de algoritmos (1-4).
- 18/01: Inducción: Varios ejemplos (5-9).
- 21/01: Correctitud: Algoritmos recursivos (10-14).
- 23/01: Correctitud: Algoritmos iterativos (10-14).
- 25/01: Análisis 1: Notación O, Omega y Theta (15-19)
- 28/01: Análisis 2: Ordenamiento por montículo
(20-25).
- 30/01: Análisis 3: Relaciones de recurrencia (26-30). Tarea 1 (para el 16/04).
- 01/02 a 04/04: Huelga.
- 07/04: Reinicio de curso.
- 09/04: Análisis 3: Relaciones de recurrencia (26-30)
[Repaso].
- 11/04: Divide y vencerás 1: Multiplicación
de enteros (31-33).
- 14/04: Divide y vencerás 2: Multiplicación de
matrices (34-35). Tarea 2 (para el 28/04).
- 16/04: Divide y vencerás 3: Quicksort (36-40).
- 18/04: Divide y vencerás 4: Cota inferior para
ordenamiento (36-40).
- 21/04: Divide y vencerás 5: Selección lineal y
búsqueda binaria (41-45).
- 23/04: Programación dinámica 1: Coeficientes
combinatorios y mochila (46-50). Tarea 3 (para
el 02/05).
- 25/04: Programación dinámica 2: Producto encadenado
de matrices (51-56).
- 28/04: Programación dinámica 3: Árboles
binarios de búsqueda óptimos (57-61).
- 30/04: Programación dinámica 4: Algoritmos de Floyd
y Warshall (62-67).
- 02/05: Primer examen
parcial (13:00-16:00).
- 05/05: Día feriado.
- 07/05: Algoritmos glotones 1: Almacenamiento óptimo en
cintas (68-72). Tarea 4 (para
el 19/05).
- 09/05: Algoritmos glotones 2: Mochila continua (68-72)
- 12/05: Algoritmos glotones 3: Algoritmo de Dijkstra (73-78).
- 14/05: Algoritmos glotones 4: Unión y búsqueda
(79-85).
- 16/05: Algoritmos glotones 5: Árboles abarcadores
mínimos (79-85).
- 19/05: Búsqueda con retroceso 1: Cadenas binarias y
k-arias (86-90). Tarea 5 (para el 10/06).
- 11/05: Búsqueda con retroceso 2: Permutaciones (91-95).
- 23/05: Búsqueda con retroceso 3: Combinaciones (96-100).
- 26/05: Búsqueda con retroceso 4: Gráficas (101-104).
- 28/05: Segundo examen
parcial (13:00-16:00).
- 30/05: Terminó el curso.
- 02/06: Terminó el curso.
- 04/06: Fin del curso.
- 10/06: Ya entregué
el acta.
- 19/06: Examen de recuperación (16: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.
