1151040 - Análisis y Diseño de Algoritmos
Trimestre 21-I

Instructor: Dr. Marco Antonio Heredia Velasco

Grupo: CSI01 (Horario asignado: Lunes, Miércoles y Viernes 10:00 - 11:30)

Modalidad: No Presencial            Sesiones en tiempo real: Información abajo.

Contenido y estrategia.

Esta página web contiene información importante para el grupo CSI01 de la UEA de Análisis y Diseño de Algoritmos. Se intentará cubrir el contenido oficial del curso, aunque no necesariamente en el orden establecido:

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

Se podrá hacer uso de los siguientes lenguajes de alto nivel: C, C++, Java, Python, Ruby, C#, Pascal, Haskell o Lua; aunque en clase se asumirá que se cuenta con conocimientos básicos de C y C++.

Dada la modalidad no presencial del curso (siguiendo el PEER de la UAM) se intentará seguir la estrategia de aprendizaje de Aula invertida; donde el profesor facilita a los estudiantes materiales de estudio para ser revisados fuera de clase, y las sesiones en tiempo real (clases) son utilizadas para reafirmar y profundizar conocimientos.

Instrucciones y Evaluación.

Las Instrucciones para primer contacto pueden descargarse en PDF aquí y aparecieron de forma resumida en el sitio de contingencia de la UAM Azcapotzalco. La forma de Evaluación, detalles sobre la lista de correo y postura hacia el plagio pueden ser consultados en esas mismas instrucciones. Usaremos exclusivamente el correo institucional.

De acuerdo al Reglamento de Alumnos de la UAM, es falta 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 reprobarán el curso.

Sesiones en tiempo real.

Las sesiones en vivo (tiempo real) se programarán dentro del horario asignado, utilizando Google Meet. El horario exacto de cada sesión y el enlace (código de reunión) serán informados a través de la lista de correo.

Las reglas para estas sesiones son: Sólo podrán ingresar los alumnos inscritos en cada grupo accediendo desde su cuenta institucional. Se debe mantener apagado el micrófono y cámara (excepto en las sesiones de examen). Usar el botón Levantar la mano y el chat de Meet para pedir la palabra, participar o hacer preguntas. Se debe haber revisado los materiales de estudio antes de la sesión correspondiente. Sólo el profesor tiene derecho a grabar la sesión.

Sobre  y Classroom.

En este curso utilizaremos la plataforma para la entrega y aplicación de algunas actividades de programación. OmegaUp es un juez en línea a donde podemos enviar nuestro código para intentar resolver alguno de los cientos de problemas de programación disponibles, a la vez que recibimos retroalimentación en cuestión de segundos. Si seguiste las Instrucciones del curso, ahora ya tienes cuenta en dicha plataforma y llenaste tus datos de perfil correctos. En las sesiones del curso ampliaremos la forma de uso de dicha plataforma.

Otro recurso que utilizaremos es una clase en Google Classroom. Principalmente haremos uso de esta clase para la entrega de Tareas que tengan que ser escaneádas. Para estos momentos, ya debiste recibir un correo de invitación a la misma y debiste presionar el botón "Unirse" dentro de ese correo. Recuerda que sólo podrás tener acceso a dicha clase a través de tu cuenta institucional.

Calendario.

El calendario se irá liberando conforme avanza el trimestre. Los materiales de estudio se denominan primarios si los debes revisar antes de la sesión en vivo correspondiente. Los materiales secundarios son opcionales y sirven como complemento a un tema.

Semana 1:  29 y 31 de marzo.

• Presentación del curso.

• Algoritmos y análisis de Complejidad.    Primario: Diapositivas        Secundario: Video.

Semana 2:  5, 7 y 9 de abril.

• Notación Asintótica O grande.    Primario: Video (ver hasta minuto 8:47) y diapositivas de semana anterior.
• Recordando la Recursión.    Primario: Video y Video.

Semana 3:  12, 14 y 16 de abril.

• Recordando Búsqueda Secuencial y Búsqueda Binaria.    Primario: Video.
• Recordando Algoritmos de ordenamiento.    Primario: Diapositivas.
• Recordando Algoritmos de ordenamiento: Selection Sort, Bubble Sort e Insertion Sort.    Primario: Video, Video y Video.
• Envíos a  .    Primario: Video.
• Práctica 1: Recursión. Dejada por correo (y Classroom), límite de entrega 21/4.

• Recordando Algoritmos de ordenamiento: Quick Sort.    Primario: Video.        Secundario: Video.
• Recordando Algoritmos de ordenamiento: Merge Sort.    Primario: Video (ver desde minuto 0:23) y Video.
• Recordando Algoritmos de ordenamiento.        Secundario: Sitio para visualizar la ejecución de estos algoritmos (seleccionar algoritmo y luego Sort → Go).

Semana 4:  19, 21 y 23 de abril.

• Introducción al Diseño de Algoritmos.
• Tarea 1: Complejidad y Diseño de Algoritmos. Subida a Classroom, límite de entrega 28/4 29/4.

Semana 5:  26, 28 y 30 de abril.

• Ejercicios de Cálculo de complejidad y Diseño de algoritmos.

• Examen 1 durante la sesión en vivo del 30/4.

Semana 6:  3 y 7 de mayo.

• Revisión del Examen 1 y la Tarea 1.

• Correctitud de un Algoritmo.    Primario: Texto [RoCa].
• Ecuaciones de recurrencia I: Algoritmos recursivos.    Primario: Video ^[2] y Video ^[3].        Secundario: Video ^[4].

Semana 7:  12 y 14 de mayo.

• Ecuaciones de recurrencia II: Solución por Sustitución.    Primario: Texto [RoCa].

• Ecuaciones de recurrencia III: Solución por Árbol de Recurrencia.
• Notación Asintótica O, Ω y Θ.    Primario: Video.        Secundario: Video.

Semana 8:  17, 19 y 21 de mayo.

• Ecuaciones de recurrencia IV: Solución por Teorema Maestro.    Primario: Video ^[5] (desde 3:40 hasta 11:38).        Secundario: Video ^[6].
• Divide y Vencerás.    Primario: Video ^[7].        Secundario: Video ^[8].

• Repaso de Heaps (Montículos).    Primario: Video [CaMa], Video [CaMa] y Video [CaMa].
• Práctica 2: Divide y Vencerás. Dejada por correo (y Classroom), límite de entrega 25/5.

• Heap Sort.    Primario: Video ^[9].
• Complejidad espacial I: Introducción.    Primario: Video ^[10] y Texto ^[11].        Secundario: Texto ^[12].

Semana 9:  24, 26 y 28 de mayo.

• Complejidad espacial II: In-place y Ejemplos.
• Tarea 2: Divide y vencerás, Heap Sort y Complejidad espacial. Subida a Classroom, límite de entrega 31/5 1/6.

• Algoritmos Glotones (Greedy).    Primario: Video ^[13] y Video ^[14].         Secundario: Video ^[15].

• Ejemplos de Algoritmos Glotones.
• Algoritmos de Programación Dinámica.    Primario: Video ^[16] (ver hasta 09:32).         Secundario: Video ^[17] (en inglés).

Semana 10:  31 de mayo, 2 y 4 de junio.

• Examen 2 durante la sesión en vivo del 2/6.
• Práctica 3: Algoritmos Glotones. Dejada por correo (y Classroom), límite de entrega 8/6 10/6.

• Ejemplos de Algoritmos de Programación Dinámica.

Semana 11:  7, 9 y 11 de junio.

• Tarea Optativa: Glotones y Programación Dinámica. Subida a Classroom, límite de entrega 13/6.

• Algoritmos de Búsqueda con retroceso (Backtracking).    Primario: Video ^[18] y Video ^[19].
• Ejemplos de Algoritmos de Búsqueda con retroceso.

• Clases de problemas P y NP.    Primario: Video ^[20] (en inglés, pero puedes activar subtítulos en español) y Video ^[21].         Secundario: Video ^[22].
• Problemas NP-Completos y reducciones polinomiales.    Primario: Video ^[23] (al menos ver desde 7:00 hasta 16:25, aunque se sugiere verlo todo).

Extra:  15 - 17 de junio.

• Calificaciones finales por correo: 15/6.
• Periodo de aclaraciones: 15/6, 16/6 y 17/6 (este día sólo en la mañana).
• Llenado y firma de actas: 17/6 por la tarde.

Bibliografía complementaria.

[RoCa]

Rodrigo Castro. Libre adaptación de las "Notas de curso" de Análisis y Diseño de Algoritmos, 2020. (Mi agradecimiento al autor por su permiso. Aquí la versión original.)

[CaMa]

Canal Cátedra de Matemática en YouTube, de la Universidad Estatal a Distancia de Costa Rica, 2018.

[1]

OmegaUp. "omegaUp Tutorials - 01 Enviar Solución", video en YouTube.

[2]

Javier Cordova. "relaciones de recurrencia", video en YouTube.

[3]

Javier Cordova. "solucion de relaciones de recurrencia", video en YouTube.

[4]

Jorge González Mollá. "Tema 2.4.- Análisis de Algoritmos Recursivos", video en YouTube.

[5]

Carlos Andres Delgado. "Clase 14-5 Matematicas discretas II. Método del maestro", video en YouTube.

[6]

Desconocido. "Métodos de Resolución Recursiva - Teorema Maestro (Simplificado)", video del canal PhilosophicalDrigo en YouTube.

[7]

Desconocido. "Recurrencias Divide y Vencerás - Parte 1", video del canal manugunt en YouTube.

[8]

Martín Buchwald. "01 - 01 División y Conquista (ORIGINAL)", video del canal Algo2Fiuba Curso Buchwald en YouTube.

[9]

Desconocido. "Método de ordenamiento Heapsort", video del canal EDatUncoma en YouTube.

[10]

Luis Argerich y Guillermo Henrion. "Complejidad Espacial", video del canal Fundamentos de Computación en YouTube.

[11]

Desconocido. "What does ‘Space Complexity’ mean?", en el sitio Web GeeksforGeeks.

[12]

Abhishek Ahlawat. "Space Complexity of Algorithms", en el sitio Web Studytonight.

[13]

Gerson Lázaro. "Algoritmos Greedy", video del canal promedia ufps en YouTube.

[14]

Desconocido. "Algoritmos Voraces", video del canal courEZ programacion en YouTube.

[15]

Antonio Feregrino. "Los algoritmos voraces.", video del canal That C# guy en YouTube.

[16]

Crisel Ayala. "Programación dinámica", video del canal promedia ufps en YouTube.

[17]

Andrey Grehov. "02 - What is DP? (Dynamic Programming for Beginners)", video en su canal en YouTube.

[18]

Desconocido. "algoritmos de backtracking", video del canal courEZ programacion en YouTube.

[19]

Javier Leal. "Método de Backtracking", video en su canal en YouTube.

[20]

Desconocido. "P versus NP y la complejidad computacional Zoo", video del canal hackerdashery en YouTube.

[21]

Eduardo Sáenz de Cabezón. "¿Qué es eso del problema P versus NP?", video del canal Derivando en YouTube.

[22]

Fernando Cuartero. "P versus NP. La búsqueda de lo imposible (Fernando Cuartero)", video del canal Hablando de Ciencia Divulgacion en YouTube.

[23]

Alberto Márquez. "Alberto nos cuenta el problema de ¿P=NP?", video del canal Los 3 chanchitos en YouTube.

---

Última modificación: 18/06/2021