50 aniversario de la UAM


1151040 Análisis y Diseño de Algoritmos
Trimestre 2024 Invierno

Profesor: Dr. Francisco Javier Zaragoza Martínez.
Inicio y fin del curso: martes 5 de marzo a viernes 24 de mayo de 2024.
Grupo: CSI81 (lunes, miércoles y viernes de 16:00 a 17:30).
Asesorías: por correo electrónico a través de cuentas institucionales.
Lugar: G206.
Cupo: 36.

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.
  1. Análisis de correctitud y complejidad.
  2. Recursividad y ecuaciones de recurrencia.
  3. Algoritmos de divide y vencerás.
  4. Algoritmos de búsqueda con retroceso.
  5. Algoritmos de programación dinámica.
  6. Algoritmos de búsqueda local.
  7. Algoritmos glotones.
  8. Problemas NP completos.

Evaluación global

Habrá al menos once tareas semanales (valor máximo de 100 puntos cada una) y cuatro exámenes en clase (presenciales, valor máximo de 300 puntos cada uno). Todas estas evaluaciones serán programas en C que se enviarán a omegaUp. Para acreditar el curso se requieren al menos:
Consideraré cualquier copia o plagio de cualquier evaluación (ya sea programa o no) de forma automática como NA para todos los involucrados. Reportaré los casos que se presenten a las autoridades correspondientes. No copies. No pases la tarea. No plagies.

Recuerden que, de acuerdo al Reglamento del Alumnado de la UAM, es falta del alumnado 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 que muestro abajo es tentativo e irá apareciendo paulatinamente. Allí colocaré el material de estudio y de consulta. Mientras tanto, unas transparencias para los primeros temas están aquí y unos materiales para los otros temas están acá.

Preparativos: 12 de febrero a 4 de marzo

  1. Asegúrate de tener disponible una computadora con internet en la que puedas editar, compilar y ejecutar programas en C. Si tienes alguna distribución de Linux es probable que ya tengas gcc y algún editor de texto instalado. Otra posibilidad es instalar Code::Blocks. En Windows instala la versión 17.12 para 32 bits o la 20.03 para 32 o 64 bits (tutorial) o bien instala Dev-C++. Para Mac OS X la versión más reciente de Code::Blocks es la 13.12 o instala Xcode. En Android instala Coding C y en iOS instala Mobile C. Como último recurso, existen compiladores de C en línea (repl.it, tio.run y onlinegdb).
  2. Usaremos exclusivamente el correo institucional. Si no tienes el tuyo, actívalo con la Coordinación de Servicios de Cómputo (CSC).
  3. Usaremos la plataforma omegaUp de forma extensiva. Crea una cuenta usando tu correo institucional, tu usuario deberá ser tu nombre y los cuatro últimos dígitos de tu matrícula (ejemplo: FranciscoZaragoza1234). En tu perfil debes anotar tu nombre completo y como escuela UAM Azcapotzalco. Mira el tutorial de omegaUp.
  4. Envía un correo a mi ayudante Samuel Hernández (rshs@azc.uam.mx) desde tu correo institucional con esta información: tu nombre completo, tu número de matrícula, tu carrera y tu usuario de omegaUp. Una vez que le envíes este correo, él te registrará en el curso ADA 2024 Invierno de omegaUp.

Si tienes alguna duda acerca de estos preparativos, envía un correo a mi ayudante desde tu correo institucional. No lo dejes para el último momento.

Semana 1: 4 de marzo a 8 de marzo

Esta semana iniciaremos el Tema 1: Análisis de correctitud y complejidad.

Semana 2: 11 de marzo a 15 de marzo

Esta semana terminaremos el Tema 1: Análisis de correctitud y complejidad e iniciaremos el Tema 2: Recursividad y ecuaciones de recurrencia.

Semana 3: 18 de marzo a 22 de marzo

Esta semana terminaremos el Tema 2: Recursividad y ecuaciones de recurrencia.

Semana 4: 25 de marzo a 29 de marzo

Esta semana iniciaremos el Tema 3: Algoritmos de divide y vencerás.

Semana 5: 1 de abril a 5 de abril

Esta semana continuaremos el Tema 3: Algoritmos de divide y vencerás.

Semana 6: 8 de abril a 12 de abril

Esta semana terminaremos el Tema 3: Algoritmos de divide y vencerás.

Semana 7: 15 de abril a 19 de abril

Esta semana cubriremos el Tema 4: Algoritmos de búsqueda con retroceso e iniciaremos el Tema 5: Algoritmos de programación dinámica.

Semana 8: 22 de abril a 26 de abril

Esta semana continuaremos el Tema 5: Algoritmos de programación dinámica.

Semana 9: 29 de abril a 3 de mayo

Esta semana terminaremos el Tema 5: Algoritmos de programación dinámica.

Semana 10: 6 de mayo a 10 de mayo

Esta semana cubriremos el Tema 6: Algoritmos de búsqueda local.

Semana 11: 13 de mayo a 17 de mayo

Esta semana cubriremos el Tema 7: Algoritmos glotones.

Semana 11bis: 20 de mayo a 24 de mayo

Esta semana cubriremos el Tema 8: Problemas NP completos.

Entrega de actas y evaluación de recuperación: 27 de mayo a 8 de julio

Estos días ocurrirán las evaluaciones de recuperación.

Bibliografía

  1. Baase y Van Gelder. Algoritmos computacionales: Introducción al análisis y diseño. Addison Wesley.
  2. Castro Campos. Análisis y diseño de algoritmos. UAM Azcapotzalco.
  3. Dasgupta, Papadimitriou, Vazirani. Algorithms. Mc Graw Hill.
  4. Erickson. Algorithms. UIUC.
  5. Kleinberg y Tardos. Algorithm Design. Addison Wesley.
  6. Knuth. The Art of Computer Programming: Vol. 3 Sorting and Searching. Addison Wesley.
  7. Parberry. Problems on Algorithms. Prentice Hall.
  8. Roberts. Thinking Recursively. Wiley.
  9. Sedgewick y Flajolet. An Introduction to the Analysis of Algorithms. Addison Wesley.
  10. Sedgewick y Wayne. Algorithms. Addison Wesley.