115117 Análisis de Algoritmos
Trimestre 2013 Invierno
Instructor: Dr. Francisco Javier
Zaragoza Martínez.
Inicio y fin del curso:
lunes 14 de enero a martes 2 de abril de 2013.
Grupo: CSI81 (martes y
jueves de 16:30 a 18:00).
Asesorías: lunes, miércoles
y viernes de 16:30 a 18:00 en la oficina H-264.
Salón: E309.
Cupo: 50 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.
- 15/01:
Presentación del curso y de las reglas de evaluación.
Introducción e inducción matemática (1-18).
- 17/01:
Correctitud de algoritmos recursivos e iterativos (19-39).
- 22/01: Notación O y tipos de análisis (40-60). Tarea 1 (para el 29/01).
- 24/01: Análisis de un algoritmo no recursivo: ordenamiento por
montículo (61-77). Tarea 2 (para el 04/02).
- 29/01:
Derivación y solución de relaciones de recurrencia (78-88).
- 31/01: Teorema
general (89-98).
- 05/02: Día feriado.
- 07/02: Primer examen
parcial: Introducción al análisis de algoritmos (1-98).
- 12/02: Análisis
de algoritmos de divide y vencerás (99-123).
- 14/02: Análisis
de un algoritmo de divide y vencerás: quicksort (124-138). Tarea 3 (para el 21/02).
- 19/02: Análisis
de otro algoritmo de divide y vencerás: k-selección (139-152).
- 21/02: Análisis
de algoritmos de programación dinámica (153-165).
- 26/02: Análisis
de un algoritmo de programación dinámica: producto encadenado de
matrices (166-174). Tarea 4 (para el
05/03).
- 28/02: Análisis
de un algoritmo de programación dinámica: árboles binarios
óptimos (175-188).
- 05/03: Segundo examen
parcial: Análisis de algoritmos de divide y vencerás y
programación dinámica (99-188).
- 07/03: Análisis de un algoritmo glotón: almacenamiento óptimo
en cintas y problema continuo de la mochila (198-219).
- 12/03: Análisis
de un algoritmo glotón: Dijkstra (220-233).
- 14/03 (Día de
π): Análisis de un algoritmo glotón: Dijkstra (220-233). Tarea 5 (para el 26/03).
- 19/03: Análisis de algoritmos de búsqueda con retroceso:
cadenas k-arias (253-274).
- 21/03: Día feriado.
- 26/03: Análisis
de algoritmos de búsqueda con retroceso: permutaciones
(275-290). Tarea 6 (para el 02/04).
- 28/03: Día
feriado.
- 02/04: Tercer examen
parcial: Análisis de algoritmos glotones y de búsqueda
con retroceso (198-290).
- 08/04: 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.
