Análisis de Algoritmos y Estructuras de Datos

Semestre 2006-1, UNAM

Agosto a Diciembre, 2005

Página principal del curso

Profesor: Sergio Rajsbaum

Ayudante: David Flores <colegadavid@gmail.com>

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 304, nuevo edificio del IIMAS.

Horario: Martes y Jueves, de 13 a 14:30 hrs.

Contenido de esta página

• Forma de trabajo
• Contacto con Profesores y Ayudantes
• Tareas
• Exámenes
• Clases
  

Forma de trabajo

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.

Contacto con el Profesor y el Ayudante

Profesor:

• Sergio Rajsbaum
  Instituto de Matemáticas, Cubículo 107
  email: rajsbaum@matem.unam.mx

Ayudante:

• David Flores
  Oficina:
  email: colegadavid@gmail.com

Tareas

Las tareas estarán disponibles conforme se vayan dejando durante el curso. La fecha de entrega es estricta.

• Tarea 1: 23 de agosto 2005, entrega 30 de agosto 2005
  
• Introducción al análisis de correctez y complejidad de algoritmos.
• Tarea 2: 6 de septiembre 2005, entrega 14 de septiembre 2005
• Divide-y-vencerás, notación asintótica, recursividad
• Tarea 3:  15 de septiembre 2005, entrega 27 de septiembre 2005
• Invariantes y análisis de complejidad, notación asintótica, Euler
• Tarea 4: 29 de septiembre 2005, entrega 6 de octubre 2005
• BFS, caminos más cortos
• Tarea 5: 11 de octubre 2005, entrega 20 de octubre 2005
• caminos más cortos
• Tarea 6: 27 de octubre 2005, entrega 8 de noviembre 2005
• Heaps Binomiales y complejidad amortizada. Hipercómputo
• Tarea 7: 15 de noviembre 2005, entrega 24 de noviembre 2005
• Programación dinámica
• Tarea 8: 24 de noviembre 2005, entrega 6 de diciembre 2005
• Heaps de Fibonacci, AGM, DFS
  

Exámenes

• 1er Examen Parcial, fecha: ??
• Examen final, fecha: ??
  

Clases

• Primer día de clases, agosto 16, 2005
• martes agosto 16: presentación del curso en powerpoint
• jueves agosto 18: búsqueda secuencial, invariantes para probar correctez; complejidad (peor, promedio y mejor caso)
• martes agosto 23: búsqueda binaria, más complejidad, correctez e invariantes; O(log n) vs O(n), entrega Tarea 1
• jueves agosto 25: ordenamiento por inserción O(n^2); más complejidad, correctez e invariantes; definiciones de notación asintótica
• martes agosto 30: los alumnos pasaron a exponer sus soluciones al problema 1 y 3 de la Tarea 1: primero el de decidir el orden lexicográfico de dos cadenas, y luego el de ordenar las tortillas.
• jueves septiembre 1: Divide-y-vencerás. Merge Sort y solución a ecuaciones recursivas.
• martes septiembre 6: introducción a gráficas, representación de gráficas en la computadora, algoritmo de Euler. Entrega Tarea 2. Devolución de Tarea 1 calificada.