115841 Análisis y Diseño de Algoritmos
Trimestre 2010 Invierno
Instructor: Dr. Francisco
Javier Zaragoza Martínez.
Inicio y fin del curso: lunes
11 de enero a viernes 26 de marzo de 2010.
Grupo: CMC01 (lunes,
miércoles y viernes de 16:00
a
17:30).
Asesorías: lunes,
miércoles y viernes de 10:00 a 11:30 en la
oficina H-264.
Salón: MCC.
Cupo: 25 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.
- Introducción al análisis de algoritmos.
- Recursión.
- Algoritmos de exploración.
- Árboles generadores mínimos.
- Distancia.
- Flujo de redes.
Evaluación
Habrá 10 tareas teóricas y de programación en C o
C++.
Cada tarea valdrá 10 puntos. Se
requiere obtener
- al menos 60 puntos para acreditar con S,
- al menos 73 puntos para acreditar con B y
- al menos 87 puntos para acreditar con MB.
Las tareas teóricas se deberán entregar en PDF (hecho en LaTeX, OpenOffice o algún otro
procesador de texto) por correo electrónico a la cuenta franz en correo.azc.uam.mx y los
programas se deberán entregar en gcc,
g++ o gcj a
la cuenta ada 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 evaluaciones que
muestro abajo es tentativo e irá
apareciendo paulatinamente. Usaremos el libro
de Dasgupta, Papadimitriou y Vazirani y el libro de Parberry
(ambos se pueden descargar legalmente de las páginas de los
autores). Los números de sección se refieren a la
versión publicada del
libro de Dasgupta. Los números de ejercicio se refieren a la
versión preliminar
del libro de Dasgupta.
- 11/01: Inicio del
curso. Establecimiento de las reglas de evaluación.
- 13/01: Secciones
0.1, 0.2 y 0.3.
- 15/01:
Sección
1.1. Tarea 1 (para el 22/01): ejercicios 0.1(a, b, f, h, m, n, o)
y 0.2(a, b, c). Programa 1 (para el 04/02).
- 18/01: Sección 1.2.
- 20/01: No habrá clase, pero estaré media hora en
el salón de clase para atender dudas sobre la tarea.
- 22/01: Sección 1.3. Tarea 2 (para el 29/01): ejercicios
1.1, 1.2, 1.6, 1.9, 1.11, 1.12, 1.13, 1.16, 1.17 y 1.18. Programa 2 (para el 08/02).
- 25/01:
Secciones 1.4 y 1.5.
- 27/01:
Secciones 2.1 y 2.2.
- 29/01:
Sección 2.3. Tarea 3 (para el 08/02): ejercicios 1.20, 1.21,
1.22, 1.25, 1.27, 1.38(a), 2.1, 2.4, 2.5(a, b). Programa
3 (para el 12/02).
- 01/02: Sección 2.4.
- 03/02: Sección 2.5 [clase
cancelada por causas de fuerza mayor, el tema es sencillo y lo deben
estudiar por su cuenta]. Tarea 4 (para el 12/02): ejercicios
2.5(c, d, e, j, k), 2.13(a, b, c), 2.14, 2.26. Programa
4 (para el
16/02).
- 05/02: Día
feriado.
- 08/02:
Sección 3.1.
- 10/02: Clase
cancelada por causas de fuerza mayor.
- 12/02: Clase
cancelada por causas de fuerza mayor.
- 15/02 y 16/02: Visita de
los evaluadores de CACEI para la acreditación de
Ingeniería en Computación.
- 15/02: Clase
cancelada por causas de fuerza mayor.
- 17/02: Sección 3.2.
- 19/02: Sección 3.3.
- 22/02: Secciones
4.1 y 4.2. Tarea 5 (para el 01/03): ejercicios 3.1, 3.2, 3.3(a, b, c,
d), 3.5, 3.8(a, b, c) y programa 5.
- 24/02: Secciones
4.3 y 4.4.
- 26/02:
Sección 4.5. Tarea 6 (para el 12/03): ejercicios 4.1(a, b), 4.3,
4.5 (2x), 4.8, 4.11 (2x), 4.12 (2x), donde 2x significa que ese
problema vale doble.
- 01/03: Estaré en un congreso.
- 03/03: Estaré en un congreso.
- 05/03: Estaré en un congreso.
- 08/03:
Sección 5.1.
- 10/03:
Sección
5.2.
- 12/03: Secciones
6.1 y 6.2.
- 15/03: Secciones 6.3 y 6.4. Tarea 7 (para el 19/03): ejercicios
5.1(a, b), 5.2(a, b), 5.6, 5.13, 6.1, 6.2, 6.3, 6.4(a).
- 17/03: Sección 7.2.
- 19/03: Sección 7.3. Tarea 8 (para el 26/03): ejercicios
7.10, 7.17(a, b, c, d, e), 7.19, 7.21, 7.23, 7.30.
- 22/03:
Sección 8.1.
- 24/03: Clase
cancelada por causas de fuerza mayor. Estaré en mi oficina para
aclaración de dudas.
- 26/03: Clase
cancelada por causas de fuerza mayor. Estaré en mi oficina para
aclaración de dudas.
Bibliografía
- Baase y Van Gelder. Algoritmos
computacionales: Introducción
al análisis y diseño. Addison Wesley.
- Bentley. Programming
Pearls. Addison Wesley.
- Berlioux y Bizard. Algorithms. Wiley.
- Cormen, Leiserson, Rivest y Stein. Introduction
to
Algorithms. Mc Graw Hill. [Libro de texto.]
- Dasgupta, Papadimitriou, Vazirani. Algorithms.
Mc Graw Hill.
- Even. Graph
Algorithms. Computer Science Press.
- Folk,
Zoellick y Riccardi. File Structures:
An Object-oriented Approach with
C++. Addison Wesley.
- Gregorio et
al. Ejercicios de
programación creativos y recreativos en C++. Prentice Hall.
- Kleinberg
y Tardos. Algorithm Design.
Addison Wesley.
- Kreher y Stinson. Combinatorial
Algorithms: Generation, Enumeration, and Search. CRC
Press.
- Parberry. Problems on Algorithms.
Prentice Hall.
- Peña
Mari. Diseño de programas, formalismo y abstracción.
Prentice Hall.
- Roberts.
Thinking Recursively. Wiley.
- Rohl. Recursion
via Pascal. Cambridge.
- Sedgewick.
Algoritmos en C++. Pearson.
- Sedgewick y Flajolet. An Introduction
to the Analysis of Algorithms. Addison Wesley.
- Skiena. The
Algorithm Design Manual. Telos.
- Skiena
y Revilla. Programming
Challenges. Springer Verlag.
- Wilf. Algorithms and
Complexity. A K Peters Ltd.