Trimestres anteriores‎ > ‎2020-I‎ > ‎

‎1151040 - Análisis y Diseño de Algoritmos‎

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

Grupo: CSI01.
Horario: Lunes, miércoles y viernes de 8:30 a 10:00.
Salón: Página de Facebook (clases en stream) / G-208.

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 una. 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 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 en horario de clase y tendrán una duración máxima de 45 minutos. La fecha de cada examen se anunciará con al menos una semana 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.

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.

Calendario: El siguiente calendario es tentativo y podrá cambiar a lo largo del curso.

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.

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.

Introducción a omegaUp (video de uso) 1, 2. Prueba diagnóstica.
Pueden consultar esta lista de problemas de programación para que practiquen.
  • 11/05: Presentación del curso. Algoritmos recursivos.
  • 13/05: Correctitud de algoritmos recursivos.
  • 15/05: Día de descanso obligatorio.
  • 16/05: [sábado] Ejercicios de práctica (subsección 2.1 de las notas). Las soluciones están en el anexo de las notas
  • 18/05: Correctitud de algoritmos iterativos.
  • 20/05: Complejidad de algoritmos iterativos y recursivos.
  • 22/05: Solución de ecuaciones de recurrencia. Tarea 1 para el 01/06. Envíos aceptados.
  • 23/05 : [sábado] Ejercicios de práctica (subsecciones 3.1, 4.1 y 5.1 de las notas).
  • 25/05: Notación asintótica O, Ω y Θ. Ejercicio previo al primer examen parcial.
  • 27/05: El teorema maestro para ecuaciones de recurrencia.
  • 29/05: Divide y vencerás como una aplicación de recursión. Ejercicio previo al primer examen parcial.
  • 30/05 : [sábado] Ejercicios de práctica (subsecciones 6.1 y 7.1 de las notas y los problemas de práctica en omegaUp agregados a la subsección 5.1).
  • 01/06: Algoritmos de divide y vencerás. Primer examen parcial. Envíos aceptados.
  • 03/06: Algoritmos de divide y vencerás. Problemas 1, 2. Tarea 2a, 2b para el 10/06. Envíos aceptados.
  • 05/06: El árbol de toma de decisiones y búsqueda con retroceso.
  • 06/06 : [sábado] Ejercicios de práctica (subsección 8.1 de las notas) .
  • 08/06: Algoritmos de búsqueda con retroceso. Problema 1, 2.
  • 10/06: Algoritmos de búsqueda con retroceso. Problema 1, 2. Tarea 3a, 3b para el 19/06. Envíos aceptados.
  • 12/06: Subproblemas repetidos en divide y vencerás. Problema 1.
  • 13/06 : [sábado] Ejercicios de práctica (subsección 10.1 de las notas).
  • 15/06: Algoritmos de recursión con memorización. Segundo examen parcial. Envíos aceptados.
  • 17/06: Características de programación dinámica. Problema 1. Tarea 4 para el 24/06. Envíos aceptados.
  • 19/06: Eliminación de la recursión con programación dinámica.
  • 20/06 : [sábado] Ejercicios de práctica (subsección 12.1 de las notas).
  • 22/06: Recuperación de soluciones en programación dinámica. Problema 1.
  • 24/06: Algoritmos de programación dinámica. Tercer examen parcial. Envíos aceptados. Tarea 5 para el 06/07. Envíos aceptados.
  • 26/06: El espacio de búsqueda de un problema. Problema 1.
  • 27/06 : [sábado] Ejercicios de práctica (subsección 13.1 de las notas).
  • 29/06: Búsqueda en amplitud en el espacio de búsqueda. Problema 1, 2.
  • 01/07: Búsqueda en prioridad en el espacio de búsqueda. Problema 1. Tarea 6a, 6b para el 13/07. Envíos aceptados.
  • 03/07: Optimización y algoritmos glotones. Problema 1, 2, 3.
  • 04/07 : [sábado] Ejercicios de práctica (subsección 14.1 de las notas).
  • 06/07: Correctitud de algoritmos glotones. Tarea 7 para el 15/07. Envíos aceptados. Cuarto examen parcial. Envíos aceptados.
  • 08/07: Problemas indecidibles y clases de complejidad. Tarea 8 para el 15/07. Envíos aceptados.
  • 10/07: Problemas NP-Completos y reducciones.
  • 11/07 : [sábado] Ejercicios de práctica (subsección 15.1 de las notas).
  • 15/07: Examen de reposición.
  • Calificaciones finales.
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.