1151040 Análisis y Diseño de Algoritmos
Trimestre 2014 Invierno
Instructor: Dr. Francisco Javier
Zaragoza Martínez.
Inicio y fin del curso:
lunes 6 de enero a jueves 20 de marzo de 2014.
Grupo: CSI01 (lunes,
miércoles y viernes de 10:00 a 11:30).
Asesorías: lunes a viernes
de 9:00 a 10:00 en la oficina H-264.
Salón: E309.
Cupo: 50.
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.
- Análisis de correctitud y complejidad.
- Recursividad y ecuaciones de recurrencia.
- Algoritmos de divide y vencerás.
- Algoritmos de búsqueda con retroceso.
- Algoritmos de programación dinámica.
- Algoritmos de búsqueda local.
- Algoritmos glotones.
- Problemas NP completos.
Evaluación
Habrá cuatro exámenes y al menos diez tareas. Cada examen valdrá 15
puntos y cada tarea valdrá 4 puntos. Sí habrá examen global. Se
requiere obtener
- al menos 30 puntos en los exámenes, 20 puntos en las tareas y
un total de al menos 60 puntos para acreditar con S,
- al menos 35 puntos en los exámenes, 25 puntos en las tareas y
un total de al menos 73 puntos para acreditar con B y
- al menos 40 puntos en los exámenes, 30 puntos en las tareas y
un total de al menos 87 puntos para acreditar con MB.
Las tareas se deberán entregar como se indique en clase y deberán estar escritas en C o C++.
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 evaluaciones que
muestro abajo es tentativo e irá apareciendo paulatinamente. Las
transparencias para los primeros temas están aquí.
Los materiales para los otros temas están acá.
06/01:
Inicio del curso. Presentación del curso y de las reglas de
evaluación. Introducción e inducción matemática.
08/01:
Correctitud de algoritmos recursivos. Tarea 1
(para el 13/01).
10/01:
Correctitud de algoritmos iterativos.
13/01: Notación O y complejidad de
algoritmos. Tarea 2 (para el 17/01).
15/01: Recursividad y ecuaciones de recurrencia.
17/01: Primer
examen parcial.
20/01:
Teorema general de ecuaciones de recurrencia. Manual para conectarse a callix.
22/01:
Algoritmos de divide y vencerás (mínimo y máximo simultáneos). Tarea 3 (para el 27/01).
24/01:
Algoritmos de divide y vencerás (Fibonacci y multiplicación de
enteros).
27/01: Algoritmos de divide y
vencerás (ordenamiento por mezcla y quicksort). Tarea
4 (para el 03/02).
29/01: Algoritmos de divide y
vencerás (suma de subconjuntos).
31/01: Segundo
examen parcial.
03/02:
Algoritmos de búsqueda con retroceso (suma de subconjuntos). Tarea 5 (para el 10/02).
05/02:
Día feriado.
07/02:
Algoritmos de búsqueda con retroceso (recorrido del caballo).
10/02: Algoritmos de búsqueda con
retroceso (problema de las reinas).
12/12: Algoritmos de programación
dinámica (recursión y memoización). Tarea 6
(para el 17/02).
14/02: Algoritmos de programación
dinámica (suma de subconjuntos).
17/02:
Algoritmos de programación dinámica (problema de la mochila). Tarea 7 (para el 24/02).
19/02:
Algoritmos de programación dinámica (subsecuencia creciente más
larga).
21/02:
Algoritmos de programación dinámica (subsecuencia común más
larga).
24/02: Tercer
examen parcial.
26/02: Algoritmos de búsqueda local
(salto de caballo).
28/02: Algoritmos de búsqueda local
(juego de 16). Tarea 8 (para el 07/03).
03/03:
Algoritmos glotones (planificación de tareas en una máquina).
05/03:
Algoritmos glotones (planificación de todas las tareas en varias
máquinas). Tarea 9 (para el 14/03).
07/03:
Problemas NP completos (las clases P y NP).
10/03: Problemas NP completos
(satisfacibilidad). Tarea 10 (para el
17/03).
12/03: Estaré en un congreso.
14/03: Estaré en un congreso.
17/03:
Cuarto examen parcial.
19/03:
Fin del curso.
21/03:
Día feriado.
24/03: Examen global (10:00 a 13:00
en el E309).
28/03: 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.
- Kernighan y Ritchie. El lenguaje de programación C. Pearson.
- Kleinberg
y Tardos.
Algorithm Design.
Addison Wesley.
- Knuth.
The
Art of Computer Programming: Vol. 3 Sorting and Searching.
Addison Wesley.
- Parberry. Problems on
Algorithms. Prentice Hall.
- Roberts.
Thinking Recursively. Wiley.
- Sedgewick.
Algoritmos en C++. Pearson.