Análisis y Diseño de Algoritmos

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

Profesor: Dr. Francisco Javier Zaragoza Martínez.
Inicio y fin del curso: lunes 6 de febrero de 2023 a viernes 16 de junio de 2023.
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.

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.

Evaluación

Habrá al menos diez tareas semanales (valor máximo de 100 puntos cada una, sí habrá puntos parciales) y cuatro exámenes en clase (valor máximo de 3 puntos cada uno, no habrá puntos parciales). La mayoría de estas evaluaciones serán programas en C, C++ o Java que se enviarán a omegaUp. Para acreditar el curso se requieren al menos:

700 puntos en la tareas y 6 puntos en los exámenes para obtener S,
800 puntos en la tareas y 8 puntos en los exámenes para obtener B y
900 puntos en la tareas y 10 puntos en los exámenes para obtener MB.

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: 23 de enero a 3 de febrero

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).
Usaremos exclusivamente el correo institucional. Si no tienes el tuyo, actívalo con la Coordinación de Servicios de Cómputo (CSC).
Usaremos la plataforma 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.
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 2023 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: 6 de febrero a 10 de febrero

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

6 de febrero: Presentación del curso. Inducción matemática.
8 de febrero: Correctitud de algoritmos recursivos e iterativos.
10 de febrero: Complejidad de algoritmos iterativos y recursivos.
Material de consulta (en español): Actúa ahora.
Material de consulta (en inglés): Recursión. Análisis de algoritmos. Uso de energía de los lenguajes.
Tarea 1 (Tema 1, 100 puntos): Del 5 de febrero a las 16:00 al 11 de febrero a las 16:00.

Semana 2: 13 de febrero a 17 de febrero

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

13 de febrero: Complejidad de algoritmos recursivos: sustitución repetida.
15 de febrero: Notación asintótica (ómicron, omega, theta).
17 de febrero: Teorema general de ecuaciones de recurrencia.
Material de consulta (en inglés): Ecuaciones de recurrencia.
Tarea 2 (Tema 2, 100 puntos): Del 12 de febrero a las 16:00 al 18 de febrero a las 16:00.

Semana 3: 20 de febrero a 24 de febrero

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

20 de febrero: Mínimo y máximo simultáneos. Cálculo de potencias. Búsqueda binaria.
22 de febrero: Números de Fibonacci. Torres de Hanoi.
24 de febrero: Examen 1 (Temas 1 y 2).
Tarea 3 (Tema 2, 100 puntos): Del 19 de febrero a las 16:00 al 25 de febrero a las 16:00.

Semana 4: 27 de febrero a 3 de marzo

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

27 de febrero: Ordenamiento por mezcla. Cota inferior de ordenamiento.
1 de marzo: Quicksort y k-selección.
3 de marzo: Multiplicación de enteros y de matrices.
Tarea 4 (Tema 3, 100 puntos): Del 26 de febrero a las 16:00 al 4 de marzo a las 16:00.

Semana 5: 6 de marzo a 10 de marzo

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

6 de marzo: Generación de cadenas binarias.
8 de marzo: Suma exacta. Particiones de enteros.
10 de marzo: Inicia el paro en la UAM.
Tarea 5 (Tema 3, 100 puntos): Del 5 de marzo a las 16:00 al 12 de marzo a las 16:00.

Debido al paro de la UAM, tomaremos las siguientes medidas:

Como ya vieron, la tarea que tenía originalmente su fecha de entrega para el 11 de marzo cambió para tener fecha de entrega el 12 de marzo.
La tarea que inició el 12 de marzo y que tenía fecha de entrega para el 18 de marzo tendrá fecha de entrega el 16 de mayo.
No iniciarán más tareas mientras no se levante el paro.
Una vez que se levante el paro, agendaré un nuevo calendario para las tareas restantes.
De la misma manera, una vez que se levante el paro, agendaré un nuevo calendario para los exámenes restantes.

Mientras tanto, yo me encuentro disponible por correo electrónico para cualquier duda que pueda surgir.

Semana 6: 8 de mayo a 12 de mayo.

Esta semana repasaremos algunos temas con sesiones en línea (por Meet de 16:00 a 17:00).

8 de mayo: Repaso de recursión.
10 de mayo: Día feriado.
12 de mayo: Repaso de divide y vencerás.
Tarea 6 (Tema 3, 100 puntos): Del 12 de marzo a las 16:00 al 16 de mayo a las 16:00.

Semana 7: 15 de mayo a 19 de mayo

Esta semana cubriremos el Tema 4: Algoritmos de búsqueda con retroceso.

15 de mayo: Día feriado.
17 de mayo: Generación de permutaciones. Recorrido del caballo.
19 de mayo: Problema de las reinas. Problema del agente viajero.
Material de consulta (en inglés): Permutaciones.
Tarea 7 (Tema 4, 100 puntos): Del 14 de mayo a las 16:00 al 22 de mayo a las 16:00.

Semana 8: 22 de mayo a 26 de mayo

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

22 de mayo: Recursión y memoración.
24 de mayo: Suma exacta. Problema del cambio.
26 de mayo: Examen 2 (Temas 3 y 4).
Tarea 8 (Tema 5, 100 puntos): Del 22 de mayo a las 16:00 al 28 de mayo a las 16:00.

Semana 9: 29 de mayo a 2 de junio

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

29 de mayo: Subsecuencia creciente más larga.
31 de mayo: Subsecuencia común más larga.
2 de junio: Problema de la mochila. Producto encadenado de matrices.
Tarea 9 (Tema 5, 100 puntos): Del 28 de mayo a las 16:00 al 3 de junio a las 16:00.

Semana 10: 5 de junio a 9 de junio

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

5 de junio: Búsqueda en amplitud con cadenas binarias.
7 de junio: Búsqueda en amplitud con permutaciones.
9 de junio: Ejemplos de algoritmos glotones.
Tarea 10 (Tema 6, 100 puntos): Del 4 de junio a las 16:00 al 10 de junio a las 16:00.

Semana 11: 12 de junio a 16 de junio

Esta semana cubriremos el Tema 7: Algoritmos glotones.

12 de junio: Planificación de intervalos.
14 de junio: Planificación minimizando la tardanza máxima.
16 de junio: Examen 3 (Temas 5, 6 y 7).
Material de consulta (en inglés): Reducciones. Intratabilidad.
Tarea 11 (Tema 7, 100 puntos): Del 11 de junio a las 16:00 al 17 de junio a las 16:00.
Tarea 12 (Tema 8, 100 puntos): Tema 8: Problemas NP completos. Leer este artículo.

Entrega de actas y evaluación de recuperación: 19 de junio a 3 de julio

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

19 a 23 de junio: Entrega de actas de evaluación global.
26 de junio: Inscripción a evaluación de recuperación.
28 a 30 de junio: Evaluación de recuperación.
29 de junio a 3 de julio: Entrega de actas de evaluación de recuperación.

Bibliografía

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

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