115117 Análisis de Algoritmos
Trimestre 2006 Otoño
Instructor: Dr. Francisco
Javier Zaragoza Martínez.
Inicio y fin del curso: Lunes
18 de septiembre a miércoles 6 de diciembre.
Grupo: CCT01 (Martes y jueves
de
11:30 a 13:00).
Asesorías: Por definirse
en la
oficina H-264.
Salón: F-104.
Laboratorio: Base de datos
"Edgar F. Codd" (H-253 a H-258).
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.
La calificación será como sigue: Las tareas
valdrán un total de 25 puntos, los tres exámenes un total
de 75 puntos y habrá la posibilidad de reponer las tareas o uno
de los exámenes con un proyecto (a elección del
estudiante de entre los problemas del libro de Parberry y en acuerdo
con el profesor). No
habrá examen global. 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.
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 las notas de
Parberry.
- 19/09: Inicio del curso.
- 21/09: No hubo clase (estuve en un congreso).
- 26/09: [Introducción] e [Inducción
matemática].
- 28/09: [Correctitud de algoritmos].
- 03/10: [Análisis de algoritmos 1].
- 05/10: Tarea 1 (para el 10/10).
- 10/10: [Análisis de algoritmos 2].
- 12/10: Día feriado.
- 17/10: [Análisis de algoritmos 3].
- 19/10: [Divide y vencerás 1].
- 20/10: Primer examen
parcial
(para entregar el 24 de octubre).
- 24/10: [Divide y vencerás 2].
- 26/10: [Divide y vencerás 3].
- 28/10: Tarea 2 (para el 07/11)
- 31/10: [Programación dinámica 1 y 2].
- 02/11: Día feriado.
- 07/11: [Programación dinámica 3].
- 09/11: [Programación dinámica 4].
- 13/11: Segundo examen
parcial (para entregar el 16 de noviembre).
- 14/11: [Algoritmos glotones 1 y 2].
- 16/11: [Algoritmos glotones 3].
- 17/11: Tarea 3 (para el 28/11).
- 21/11: [Búsqueda con retroceso 1 y 2].
- 23/11: [Búsqueda con retroceso 3].
- 28/11: [Búsqueda con retroceso 4].
- 30/11: [Problemas NP completos 1].
- 01/12: Tarea 4 (para el 05/12).
- 04/12: Tercer examen
parcial (para entregar el 11 de
diciembre sin prórroga posible).
- 05/12: [Problemas NP completos 2].
- 11/12: Revisión de proyecto. (Luis: 504, 505 y 506,
Salathiel: 417+análisis)
- 12/12: No habrá global, pero está
programado para este día a las 10:00. Entrega del acta a las
13:00.
- 10/01: Examen de recuperación de 10:00 a 13:00.
Bibliografía