1151040 - Análisis y Diseño de Algoritmos

Institución: Universidad Autónoma Metropolitana, Azcapotzalco.
Instructor: Rodrigo Alexander Castro Campos.
Trimestre: 2024-I.

Grupo: CSI01.
Horario: Lunes, miércoles y viernes de 7:00 a 8:30.
Salón: E309.

Contenido oficial del curso:
  • 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.
Calificación:

Habrán ocho tareas con un valor de 10 puntos cada una y cuatro exámenes con un valor de 5 puntos cada uno. Las tareas y exámenes consistirán en escribir programas para la plataforma omegaUp que resuelvan al 100% el problema de programación indicado para la evaluación. Sus datos de registro deberán enviarse mediante este formulario antes de la entrega de la primera tarea. No se calificarán programas de ninguna otra forma. Cada tarea estará disponible con al menos una semana de anticipación con respecto a la fecha de entrega. Los exámenes se realizarán de manera presencial en horario de clase y tendrán una duración de 75 minutos. El examen comenzará 10 minutos después de iniciada la sesión de clase y se requiere asistencia puntual al mismo. La fecha de cada examen se anunciará con al menos una clase de anticipación. No habrá evaluación terminal. El curso se impartirá en los lenguajes C y C++.

Es requisito para aprobar el curso obtener al menos 12 puntos provenientes de exámenes. Cumpliendo eso, la calificación final se obtiene de la suma de los puntajes asignados a las evaluaciones. La escala de calificación en acta es:
  • Al menos 60 puntos para acreditar con S.
  • Al menos 73 puntos para acreditar con B.
  • Al menos 87 puntos para acreditar con MB.

Cuando exista más de una versión para una tarea, basta con que resuelvan una de ellas; no se otorgarán puntos adicionales por resolver varias versiones. De manera similar, cuando exista más de una versión para un examen, su calificación vendrá de la versión que resuelvan y que otorgue más puntos; no se otorgarán puntos adicionales por resolver varias versiones.

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 y se impondrá desde amonestación escrita hasta suspensión por dos trimestres. Adicionalmente, los alumnos que incurran en esta falta no tendrán derecho a aprobar el curso.

Pueden consultar esta lista de problemas de "Programación Estructurada" para que practiquen.
Pueden consultar esta lista de problemas de "Algoritmos y Estructuras de Datos" para que practiquen.
Pueden consultar esta lista de problemas de "Análisis y Diseño de Algoritmos" para que practiquen.

Calendario: El calendario es tentativo y podrá cambiar. Pueden consultar programas de ejemplo de los temas del curso.

  • 06/03: Presentación del curso. Introducción a omegaUp 1, 2. Prueba diagnóstica.
  • 08/03: Algoritmos recursivos e inducción matemática.
  • 11/03: Correctitud de algoritmos recursivos.
  • 13/03: Correctitud de algoritmos iterativos.
  • 15/03: Complejidad de algoritmos iterativos.
  • 18/03: Complejidad de algoritmos recursivos. Tarea 1 para el 27/03. Envíos aceptados.
  • 20/03: Solución de ecuaciones de recurrencia.
  • 22/03: Notación asintótica O, Ω y Θ.
  • 25/03: El teorema maestro para ecuaciones de recurrencia.
  • 27/03: El paradigma de divide y vencerás.
  • 29/03: Día de descanso obligatorio.
  • 01/04: Primer examen parcial. Envíos aceptados.
  • 03/04: Algoritmos de divide y vencerás.
  • 05/04: Algoritmos de divide y vencerás. Tarea 2 para el 15/04. Envíos aceptados.
  • 08/04: Subproblemas repetidos en divide y vencerás.
  • 10/04: Recursión con memorización y su implementación. Tarea 3 para el 22/04. Envíos aceptados.
  • 12/04: El paradigma de programación dinámica.
  • 15/04: Segundo examen parcial. Envíos aceptados.
  • 17/04: Algoritmos de programación dinámica.
  • 19/04: Recuperación de soluciones en programación dinámica.
  • 22/04: Optimización de memoria en programación dinámica. Tarea 4 para el 06/05. Envíos aceptados.
  • 24/04: El paradigma de búsqueda con retroceso.
  • 26/04: Algoritmos de búsqueda con retroceso. Tarea 5 para el 17/05.
  • 29/04: Tercer examen parcial. Envíos aceptados.
  • 01/05: Día de descanso obligatorio.
  • 03/05: Algoritmos de búsqueda con retroceso. El espacio de búsqueda de un problema.
  • 06/05: Búsqueda en amplitud.
  • 08/05: Búsqueda en amplitud. Tarea 6 para el 20/05.
  • 10/05: Día de descanso obligatorio.
  • 13/05: Algoritmos glotones.
  • 15/05: Día de descanso obligatorio.
  • 17/05: Cuarto examen parcial.
  • 20/05: Algoritmos glotones.
  • 22/05: Problemas indecidibles.
  • 24/05: Clases de complejidad.
Entornos de programación que pueden usar localmente:
Entornos de programación que pueden usar en línea:
Bibliografía:
  • Castro Campos. Notas de curso (se irán actualizando conforme avance el trimestre).
  • Baase, Van Gelder. Algoritmos computacionales: Introducción al análisis y diseño. Addison Wesley.
  • Dasgupta, Papadimitriou, Vazirani. Algorithms. Mc Graw Hill.
  • Erickson, Algorithms. Disponible en https://jeffe.cs.illinois.edu/teaching/algorithms/
  • Kernighan, Ritchie. El lenguaje de programación C. Pearson.
  • Kleinberg, Tardos. Algorithm Design. Addison Wesley.
  • Knuth. The Art of Computer Programming: Vol. 3 Sorting and Searching. Addison Wesley.
  • Parberry. Problems on Algorithms. Prentice Hall. Disponible en http://ianparberry.com/books/free/
  • Roberts. Thinking Recursively. Wiley.
  • Sedgewick. Algoritmos en C++. Pearson.