1151040 Análisis y Diseño de Algoritmos
Trimestre 2026 Invierno
Profesor: Dr. Francisco Javier Zaragoza Martínez.
Inicio y fin del curso:
lunes 19 de enero a miércoles 1 de abril de 2026.
Grupo: CSI81 (lunes,
miércoles y viernes de 16:00 a 17:30).
Asesorías: de 9:30 a 17:30
en el G211 o por correo electrónico a través de cuentas
institucionales.
Lugar: E312.
Cupo: 32.
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 global
Habrá al menos once tareas semanales (valor máximo de 100 puntos
cada una) y tres exámenes en clase (presenciales, valor máximo de
400 puntos cada uno). Todas estas evaluaciones serán escritas o
programas
que sean de tu propia autoría y titularidad y que se enviarán a omegaUp.
Para acreditar el curso se requieren al menos:
- 700 puntos en la tareas y 700 puntos en los exámenes para
obtener S,
- 800 puntos en la tareas y 800 puntos en los exámenes para
obtener B y
- 900 puntos en la tareas y 900 puntos en los exámenes para
obtener MB.
Consideraré la entrega de cualquier evaluación (ya sea programa o
no) que no sea de tu propia autoría y titularidad 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. No uses herramientas de inteligencia
artificial.
Recuerda 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, el presentar como propios
trabajos u obra intelectual que sean de la autoría o titularidad de
otra persona y el engañar a una persona o aprovecharse del error en
que ésta se encuentra para obtener ilícitamente un bien o para
alcanzar un beneficio indebido (Artículo 8). Se impondrá desde
amonestación escrita hasta expulsión de la universidad (Artículos
16, 17 y 18) según sea el caso.
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: 5 de enero a 16 de enero
- 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 Eduardo Suárez (yesc@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 2026 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: 19 de enero a 23 de enero
Esta semana iniciaremos el Tema 1: Análisis de correctitud y
complejidad.
- 19 de enero: Presentación del curso. Inducción matemática.
- 21 de enero: Inducción matemática. Correctitud de algoritmos
recursivos.
- 23 de enero: No hubo clase por causas de fuerza mayor.
- 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 19 de enero a las 16:00 al
26 de enero a las 16:00.
Semana 2: 26 de enero a 30 de enero
Esta semana terminaremos el Tema 1: Análisis de correctitud y
complejidad e iniciaremos el Tema 2: Recursividad y ecuaciones de
recurrencia.
- 26 de enero: Correctitud de algoritmos recursivos e
iterativos.
- 28 de enero: Correctitud de algoritmos recursivos e
iterativos.
- 30 de enero: Complejidad de algoritmos iterativos y
recursivos.
- Material de consulta (en inglés): Ecuaciones
de recurrencia.
- Tarea 2 (Tema 2, 100 puntos): Del 26 de enero a las 16:00 al 2
de febrero a las 16:00.
Semana 3: 2 de febrero a 6 de febrero
Esta semana terminaremos el Tema 2: Recursividad y ecuaciones de
recurrencia.
- 2 de febrero: Complejidad de algoritmos recursivos:
sustitución repetida.
- 4 de febrero: Notación asintótica (ómicron, omega, theta).
- 6 de febrero: Teorema general de ecuaciones de recurrencia.
- Tarea 3 (Tema 2, 100 puntos): Del 2 de febrero a las 16:00 al
9 de febrero a las 16:00.
Semana 4: 9 de febrero a 13 de febrero
Esta semana iniciaremos el Tema 3: Algoritmos de divide y
vencerás.
- 9 de febrero: Mínimo y máximo simultáneos. Cálculo de
potencias. Búsqueda binaria.
- 11 de febrero: Números de Fibonacci. Torres de Hanoi.
- 13 de febrero: Ordenamiento por mezcla. Cota inferior de
ordenamiento.
- Tarea 4 (Tema 3, 100 puntos): Del 9 de febrero a las 16:00 al
16 de febrero a las 16:00.
Semana 5: 16 de febrero a 20 de febrero
Esta semana continuaremos el Tema 3: Algoritmos de divide y
vencerás.
- 16 de febrero: Primer examen presencial (Temas 1 y 2).
- 18 de febrero: Quicksort y k-selección.
- 20 de febrero: Multiplicación de enteros y de matrices.
- Tarea 5 (Tema 3, 100 puntos): Del 16 de febrero a las 16:00 al
23 de febrero a las 16:00.
Semana 6: 23 de febrero a 27 de febrero
Esta semana terminaremos el Tema 3: Algoritmos de divide y
vencerás.
- 23 de febrero: Generación de cadenas binarias.
- 25 de febrero: Suma exacta. Particiones de enteros.
- 27 de febrero: Generación de permutaciones. Problema de las
reinas.
- Tarea 6 (Tema 3, 100 puntos): Del 23 de febrero a las 16:00 al
2 de marzo a las 16:00.
Semana 7: 2 de marzo a 6 de marzo
Esta semana cubriremos el Tema 4: Algoritmos de búsqueda con
retroceso.
- 2 de marzo: Recorrido del caballo. Problema del agente
viajero.
- 4 de marzo: Día feriado.
- 6 de marzo: Recursión y memoración.
- Material de consulta (en inglés): Permutaciones.
- Tarea 7 (Tema 4, 100 puntos): Del 2 de marzo a las 16:00 al 9
de marzo a las 16:00.
Semana 8: 9 de marzo a 13 de marzo
Esta semana iniciaremos el Tema 5: Algoritmos de programación
dinámica.
- 9 de marzo: Segundo examen presencial (Temas 3 y 4).
- 11 de marzo: Suma exacta.
- 13 de marzo: Problema del cambio. Problema de la mochila.
- Tarea 8 (Tema 4, 100 puntos): Del 9 de marzo a las 16:00 al 16
de marzo a las 16:00.
Semana 9: 16 de marzo a 20 de marzo
Esta semana terminaremos el Tema 5: Algoritmos de programación
dinámica.
- 16 de marzo: Subsecuencia creciente más larga. Subsecuencia
común más larga.
- 18 de marzo: Producto encadenado de matrices.
- 20 de marzo: Búsqueda en amplitud con cadenas binarias.
- Tarea 9 (Tema 5, 100 puntos): Del 16 de marzo a las 16:00 al
23 de marzo a las 16:00.
Semana 10: 23 de marzo a 27 de marzo
Esta semana cubriremos el Tema 6: Algoritmos de búsqueda local y
cubriremos el Tema 7: Algoritmos glotones.
- 23 de marzo: Búsqueda en amplitud con permutaciones.
- 25 de marzo: Planificación de intervalos.
- 27 de marzo: Planificación minimizando la tardanza máxima.
- Tarea 10 (Tema 5, 100 puntos): Del 23 de marzo a las 16:00 al
30 de marzo a las 16:00.
Semana 11: 30 de marzo a 3 de abril
Esta semana cubriremos el Tema 8: Problemas NP completos.
- 30 de marzo: Clases de complejidad P, NP y NP completo.
Reducciones e intratabilidad.
- 1 de abril: Tercer examen presencial (Temas 6, 7 y 8)
- 3 de abril: Día feriado.
- Tarea 11 (Tema 6, 100 puntos): Del 30 de marzo a las 16:00 al
6 de abril a las 16:00.
- Material de consulta (en inglés): Reducciones.
Intratabilidad.
Leer
este artículo.
Entrega de actas y evaluación de recuperación: 6 de abril a 24
de abril
Estos días ocurrirán las evaluaciones de recuperación.
- 9 a 15 de abril: Entrega de actas de evaluación global.
- 20 de abril: Inscripción a evaluación de recuperación.
- 22 a 24 de abril: Evaluación de recuperación.
- 22 a 24 de abril: 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.
