1151040 - Análisis y Diseño de Algoritmos

• 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.

Habrá 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 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 el lenguaje C++.

Es requisito para aprobar el curso obtener al menos 12 puntos provenientes de exámenes. Cumpliendo eso, la calificación en acta se obtiene como sigue tras sumar los puntos provenientes de las tareas y de los exámenes:

• Al menos 60 puntos para acreditar con S.
• Al menos 73 puntos para acreditar con B.
• Al menos 87 puntos para acreditar con MB.

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. Los alumnos que incurran en esta falta, o que envíen programas cuya escritura haya sido asistida mediante herramientas de inteligencia artificial generativa, no tendrán derecho a aprobar el curso.

• 10/02: Presentación del curso. Introducción a omegaUp.
• 12/02: Algoritmos recursivos e inducción matemática.
• 14/02: Correctitud de algoritmos recursivos.
• 17/02: Correctitud de algoritmos iterativos.
• 19/02: Complejidad de algoritmos iterativos.
• 21/02: Complejidad de algoritmos recursivos. Tarea 1 para el 05/03. Envíos aceptados.
• 24/02: Solución de ecuaciones de recurrencia.
• 26/02: Notación asintótica O, Ω y Θ.
• 28/02: El teorema maestro para ecuaciones de recurrencia.
• 03/03: Examen 1. Calificaciones.
• 05/03: El paradigma de divide y vencerás.
• 07/03: Algoritmos de divide y vencerás. Tarea 2 para el 19/03. Envíos aceptados.
• 10/03: Algoritmos de divide y vencerás.
• 12/03: Subproblemas repetidos en divide y vencerás.
• 14/03: Recursión con memorización y su implementación. Tarea 3 para el 24/03. Envíos aceptados.
• 17/03: El paradigma de programación dinámica.
• 19/03: Examen 2. Calificaciones.
• 21/03: Día de descanso obligatorio.
• 24/03: Algoritmos de programación dinámica.
• 26/03: Algoritmos de programación dinámica.
• 28/03: Recuperación de soluciones y optimización de memoria. Tarea 4 para el 11/04. Envíos aceptados.
• 31/03: Generación recursiva de cadenas.
• 02/04: Examen 3. Calificaciones.
• 04/04: El paradigma de búsqueda con retroceso.
• 07/04: Algoritmos de búsqueda con retroceso.
• 09/04: Algoritmos de búsqueda con retroceso. Tarea 5 para entrega el 08/05. Envíos aceptados.
• 11/04: El espacio de búsqueda de un problema.
• 14/04: Búsqueda en amplitud.
• 16/04: Búsqueda en amplitud. Tarea 6 para entrega el 08/05. Envíos aceptados.
• 18/04: Día de descanso obligatorio.
• 21/04: Examen 4. Calificaciones.
• El calendario se reprogramó por al paro. Cambio en los criterios de evaluación derivado del paro estudiantil.
• 07/05: Algoritmos glotones. Tarea 7 opcional para entrega el 15/05. Envíos aceptados.
• Video: Clases de complejidad NP-Completo y NP-Duro. Tarea 8 para entrega el 08/05. Envíos aceptados.
• Calificaciones finales.

• CodeBlocks (Windows, Linux): http://www.codeblocks.org/downloads/26.
  • Si tienen algún problema usando la versión más reciente, pueden probar la versión 17.12.
  • En Windows se sugiere descargar el instalador que incluye el compilador MinGW (enlace directo a la version 20.3), (enlace directo a la version 17.12).
• Xcode (macOS):https://developer.apple.com/xcode/ide/.

• Entorno de programación para la clase en vivo: https://racc.mx/ide
• OnlineGDB: https://www.onlinegdb.com
• Repl.it: https://repl.it/languages/cpp

• Castro Campos. Notas de curso.
• 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.

• The Many Faces of Set Cover: https://jeremykun.com/2015/05/04/the-many-faces-of-set-cover/.