115117 Análisis de Algoritmos
Trimestre 2012 Otoño
Instructor: Dr. Francisco Javier
Zaragoza Martínez.
Inicio y fin del curso:
lunes 10 de septiembre a jueves 29 de noviembre de 2012.
Grupo: CSI01 (martes y
jueves de 10:00 a 11:30).
Asesorías: lunes,
miércoles y viernes de 10:00 a 11:30 en la oficina H-264.
Salón: martes en B005
y jueves en B004.
Cupo: 70 alumnos.
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 seis tareas
valdrán en total al menos 40 puntos y los tres
exámenes un total de 60 puntos. Se requiere obtener:
- al menos 25 puntos en los exámenes, 25 puntos en las
tareas y un total de 60 puntos para acreditar con S,
- al menos 30 puntos en los exámenes, 30 puntos en las
tareas y un total de 73 puntos para acreditar con B y
- al menos 35 puntos en los exámenes, 35 puntos en las
tareas y 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.
- 11/09:
Presentación del curso y de las reglas de
evaluación. Introducción e inducción
matemática (1-18).
- 13/09:
Correctitud de algoritmos recursivos e iterativos (19-39).
- 18/09: Notación O y tipos de análisis (40-60). Tarea 1 (para el 25/09).
- 20/09: Análisis de un algoritmo no recursivo:
ordenamiento por montículo (61-77).
- 25/09:
Derivación y solución de relaciones de recurrencia
(78-88) y Teorema general (89-98). Tarea 2
(para el 04/10).
- 27/09:
Análisis de algoritmos de divide y vencerás
(99-123).
- 02/10: Debido al paro de actividades se
cambió de lugar y fecha el examen.
- 04/10: [G206] Primer
examen parcial: Introducción al análisis
de algoritmos (1-98).
- 09/10:
Análisis de un algoritmo de divide y vencerás:
quicksort (124-138).
- 11/10:
Análisis de otro algoritmo de divide y vencerás:
k-selección (139-152). Tarea 3
(para el 18/10).
- 16/10:
Análisis de algoritmos de programación
dinámica (153-165).
- 18/10:
Análisis de un algoritmo de programación
dinámica: producto encadenado de matrices (166-174). Tarea 4 (para el 25/10).
- 23/10: [B007]
Análisis de un algoritmo de programación
dinámica: árboles binarios óptimos
(175-188).
- 25/10: Segundo examen parcial:
Análisis de algoritmos de divide y vencerás y
programación dinámica (99-188).
- 30/10: Análisis de un algoritmo glotón:
almacenamiento óptimo en cintas y problema continuo de la
mochila (198-219). Tarea 5 (para el
13/11).
- 01/11: Día feriado.
- 06/11:
Análisis de un algoritmo glotón: Dijkstra
(220-233).
- 08/11:
Análisis de un algoritmo glotón: Dijkstra
(220-233).
- 13/11: Análisis de algoritmos de búsqueda con
retroceso: cadenas k-arias (253-274). Tarea 6
(para el 22/11).
- 15/11: No hubo clases por causas de
fuerza mayor.
- 20/11:
Día feriado.
- 22/11: Tercer examen parcial:
Análisis de algoritmos glotones y de búsqueda con
retroceso (198-290).
- 10/12: 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.
- Zaragoza. Problemas,
algoritmos y optimización. UAM Azcapotzalco.
