115117 Análisis de Algoritmos
Trimestre 2011 Invierno
Instructor: Dr. Francisco
Javier Zaragoza Martínez.
Inicio y fin del curso: lunes
17 de enero a viernes 1 de abril de 2011.
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: 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 total de seis)
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 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 (nueva versión).
- 18/01: Inicio del
curso. Introducción e inducción matemática (1-18).
- 20/01: Correctitud
de algoritmos recursivos e iterativos (19-39).
- 25/01: Notación O y tipos de análisis
(40-60).
- 27/01: Análisis de un algoritmo no recursivo: ordenamiento
por montículo
(61-77).
- 01/02:
Derivación y solución de relaciones de
recurrencia
(78-88).
- 03/02: Teorema general (89-98).
- 08/02: Análisis de algoritmos de divide y vencerás
(99-123). Tarea 1 (para el 15/02).
- 10/02: Primer examen
parcial: Introducción al análisis de algoritmos
(1-98).
- 15/02:
Análisis de un algoritmo de divide y
vencerás: quicksort (124-138).
- 17/02: Clase
cancelada por causas de fuerza mayor. Revisen el tema del algoritmo de
selección por su cuenta.
- 22/02:
Análisis de algoritmos de programación
dinámica (153-165). Tarea 2 (para el
03/03).
- 24/02:
Análisis de un algoritmo de
programación
dinámica: producto encadenado de matrices (166-174). Tarea 3 (para el 10/03).
- 01/03: Algoritmos
de Floyd y Warshall (189-197).
- 03/03: Segundo examen
parcial: Análisis de algoritmos de divide y
vencerás y de programación dinámica
(99-197).
- 08/03: Análisis de un algoritmo glotón:
almacenamiento óptimo en
cintas (198-206).
- 10/03: Análisis de un algoritmo glotón:
problema
continuo de la mochila (207-219).
- 15/03:
Análisis de un algoritmo glotón: Dijkstra
(220-233).
- 17/03:
Análisis de un algoritmo glotón: problema de
unión y búsqueda (234-241). Tarea 4
(para el 29/03).
- 22/03: Análisis de un algoritmo glotón:
árboles abarcadores de costo mínimo (242-252).
- 24/03: Análisis de algoritmos de búsqueda con
retroceso: cadenas k-arias y aplicaciones (253-274).
- 29/03:
Análisis de algoritmos de búsqueda con
retroceso: permutaciones y aplicaciones (275-290).
- 31/03: Tercer examen
parcial: Análisis de algoritmos glotones y de
búsqueda con retroceso (175-290).
- 05/04: No
habrá más tareas ni exámenes.
- 07/04: Estas son
las calificaciones que pondré en el
acta.
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.