Análisis de Algoritmos y Estructuras de Datos
Semestre 2007-1, UNAM
Agosto a Diciembre, 2006
Página principal del curso
Ayudante: Jorge Figueroa
<jfigueroac@uxmcc2.iimas.unam.mx>
Curso impartido a alumnos de la Maestría
en Ciencia e Ingeniería de la Computación como
Estructuras de Datos y Teoría de Algoritmos.
Lugar: Aula 202, edificio anexo del IIMAS.
Horario: Martes y Jueves, de 9 a 10:00 hrs. Clases de
ejercisios: lunes 11:30 - 12:30
Contenido de esta página
Durante el curso se dejarán tareas y consistirán en
ejercicios relacionados con los temas tratados en clase. Cada tarea
tendrá que ser resuelta en un plazo fijo. La fecha de
entrega es estricta.
Profesor:
Ayudante:
- Jorge Figueroa
Oficina:
email: jfigueroac@uxmcc2.iimas.unam.mx
Las tareas estarán disponibles conforme se vayan dejando
durante el curso. La fecha de
entrega es estricta.
- Tarea
1: 26 de agosto 2006, entrega 5 de septiembre 2006
- Introducción al análisis de correctez y
complejidad de algoritmos.
- Tarea-Proyecto
2: 5 de septiembre 2006, entrega 26 de septiembre 2006
- Apareamientos estables, complejidad y algoritmos aleatorios.
- Tarea
3: 3 de octubre 2006, entrega 10 de octubre 2006
- Tarea 4: 19 de octubre 2006, entrega 31
de octubre 2006
- 1er Examen Parcial, fecha: ??
- Examen final, fecha: ??
Clases. Libro de texto: Algorithm Design de
Kleinberg y Tardos.
- Primer día de clases, agosto 15, 2006
- martes agosto 15: presentación del curso en powerpoint -
el mundo de los problemas computables y no computables
- jueves agosto 17: complejidad (peor, promedio y mejor caso),
notación asintótica
- martes agosto 22: notación asintótica (2nda parte)
- jueves agosto 24: presentación del curso en powerpoint -
el mundo de los problemas computables, la pregunta P vs. NP y
algorítmica
- martes agosto 29: apareamientos estables
- jueves agosto 31: apareamientos estables (presentaciones de
alumnos)
- martes septiembre 5: análisis de correctez y complejidad
de la búsqueda secuencial, impartida por Ayudante; stoy en MSRI Workshop
on Computational Applications of Algebraic Topology (entregar Tarea
1)
- jueves septiembre 7: análisis de correctez y complejidad
de la búsqueda binaria, impartida por Ayudante; estoy en MSRI Workshop
on Computational Applications of Algebraic Topology
- martes septiembre 12: Cinco problemas representativos (1.2 del
libro de Kleinberg-Tardos)
- jueves septiembre 14: Discusión Tarea 2
- martes septiembre 19: introducción a la teoría de
gráficas,
impartida por ayudante; estoy en DISC
2006
- jueves septiembre 21: circuitos eulerianos, impartida por
ayudante; estoy en DISC 2006
- martes septiembre 26: Gráficas, inducción.
Entrega Tarea-Proyecto 2.
- jueves septiembre 28: Algoritmo de Euler
- martes Octubre 3: BFS. Tarea 3.
- jueves Octubre 5: Algoritmos Greedy: calendarización
- martes Octubre 10: calendarización. Entregar Tarea 3.
- jueves Octubre 12: calendarización
- martes Octubre 17: caching. Tarea 4
- jueves Octubre 19: no hay clase por curso en el IIMAS obligatorio
- martes Octubre 24: Algoritmo de Dijkstra
- jueves Octubre 26: Colas de prioridad
- martes Octubre 31: Árboles generadores mínimos
- jueves Noviembre 2: asueto
Autor original: Miguel Angel Rodríguez
Última modificación: agosto 14, 2005