115117 Análisis de Algoritmos
Trimestre 2007 Primavera
Instructor: Dr. Francisco
Javier Zaragoza Martínez.
Inicio y fin del curso: lunes
23 de abril a viernes 6 de julio.
Grupo: CCT81 (martes y jueves
de
14:30 a 16:00).
Asesorías:
miércoles de 9:00 a 13:00 y jueves de 11:30 a 13:00 en la
oficina H-264.
Salón: E-309.
Cupo: 35 estudiantes incluyendo
a los 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 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 30
puntos
en los exámenes y al menos 20 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 son a los números de
página de las notas de
Parberry. Nota: Dada la
reciente extensión del trimestre ya no tendremos clases extras
en el resto del trimestre, pero no veremos en clase el tema de
análisis de algoritmos glotones.
- 24/04: Inicio del curso. Introducción (páginas 5 a
8).
- 25/04: Sesión especial de inducción
matemática (páginas 9 a 13). Clase extra de 16:00 a 17:30
en el F-210.
- 26/04: Correctitud de algoritmos recursivos (páginas 14 a
18).
- 01/05: Día feriado.
- 03/05: Notación O y tipos de análisis
(páginas 19 a 23). Primera tarea (para el
17/05).
- 08/05: Estuve en una junta.
- 10/05: Día feriado.
- 15/05: Día feriado.
- 17/05: Día perdido por
el paro.
- 22/05: Análisis de un algoritmo no recursivo: heapsort
(páginas 24 a 29).
- 23/05: Solución de relaciones de recurrencia
(páginas 30 a 34). Clase
extra de 10:00 a 11:30 en el
E-306.
- 24/05: Primer examen
parcial: Introducción al análisis de algoritmos
(páginas 5 a 34).
- 29/05: Análisis de algoritmos de divide y vencerás
(páginas 35 a 39).
- 31/05: Análisis de un algoritmo de divide y
vencerás: quicksort (páginas 40 a 44). Segunda
tarea (para el 12/06).
- 05/06: Análisis de otro algoritmo de divide y
vencerás: k-selección (páginas 45 a 49).
- 07/06: Análisis de algoritmos de programación
dinámica (páginas 50 a 54).
- 12/06: Análisis de un algoritmo de
programación
dinámica: producto encadenado de matrices (páginas 55 a
60).
- 14/06: Análisis
de otro algoritmo de
programación dinámica: árboles binarios
óptimos (páginas 61 a 65).
- 18/06 a 22/06: Estaré en una conferencia.
- 26/06: Segundo examen
parcial: Análisis de algoritmos de divide y
vencerás y de programación dinámica
(páginas 35 a 65).
- 28/06: Análisis de algoritmos de búsqueda con
retroceso (páginas 90 a 94). Tercera tarea
(para el 12/07).
- 03/07: Análisis de un algoritmo de búsqueda con
retroceso: permutaciones (páginas 95 a 99).
- 05/07: Análisis
de otro algoritmo de
búsqueda con
retroceso: combinaciones (páginas 100 a 104).
- 10/07: Clases de problemas P, NP y NPC (páginas
109 a 114). Cuarta tarea (para el 23/07).
- 12/07: Fin del curso. Problemas NP completos y reducciones
(páginas 115 a 119).
- 19/07: Tercer
examen parcial: Análisis de algoritmos de
búsqueda con retroceso y problemas NP completos (páginas
90 a 119) de 14:00 a 16:00 en el E107. Si por alguna razón no
llego,
entonces el examen será el lunes 23 de 10:00 a 13:00.
- 24/07: Entrega de calificaciones y del acta.
- 04/09: Examen de recuperación (16:00 a 19:00, Titular:
Francisco Zaragoza, Suplente: Germán Téllez).
Bibliografía
- Baase y Van Gelder. Algoritmos
computacionales: Introducción
al análisis y diseño. 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.