Optimización combinatoria

Esta es la página de una clase de maestría con clave MECBS 5104 de FIME dado en la primavera del año 2008 en la UANL por la Dra. Elisa Schaeffer.

Esta versiín del curso está enfocada en los temas de tesis de los tesistas de la doctora, por lo cual otros estudiantes que quieren inscribirse deben consultar con ella y con sus asesores de tesis antes de inscribirse.

El prerequisito de la materia es Optimización de flujo en redes (MECAS 5002) y conocimiento general de programación. Hay tres horas de clase semanalmente: los lunes y los miércoles a las 9:30-11:00 horas (los asuetos están definidos en el calendario académico de la UANL) en el salón 5-205. Se otorga seis (6) créditos a los que aprueben la materia.

Objetivo

Enseñar al estudiante los fundamentos y las metodologías para resolver problemas de optimización discreta donde el número de posibles soluciones es finito pero de tamaño gigantesco (exponencial), tal como ocurre en diversas aplicaciones en la práctica. Se cubren resultados clásicos de esta rama asícomo también tratamientos más recientes como meta-heurísticas y versiones probabilistas de los algoritmos.

Temario

  1. Conceptos introductorios de optimización combinatoria
    • Introducción a optimización combinatoria 21.01.
  2. Complejidad computacional
  3. Teoría de apareamiento
    • Problemas combinatorios; acoplamientos en grafos bipartitos 30.01.
    • Acoplamientos/apareamientos generales; conjunto independiente 06.02.
    • Proyecto de Vanesa: acoplamientos 07.05.
  4. Árboles de expansión y matroides
  5. Diseño y análisis de algoritmos
    • Estructuras de datos
      • Listas y árboles 20.02.
      • Montículos binómicos 25.02.
    • Técinas para algoritmos eficientes
    • Técincas avanzadas
      • Ramificar-acotar, Algoritmos de aproximación 12.03.
      • Computación aleatorizada 02.04.
      • Metaheurísticos
        • Algoritmos genéticos 07.04
        • Implementación de metaheurísticos 09.04.
      • Proyecto de David: métodos MCMC 19.05.

Tareas y otros pendientes

FechaTarea/pendiente
21.01.Leer Capítulos 1 y 2 del material en PDF - habrá miniexamen
06.02.Entrega de la tarea sobre cómo generar las permutaciones de n elementos distintos; hacer un ejemplo con n = 4
11.02Los que no asistieron, deben estudiar los algoritmos Prim y Kruskal, saber demostrar que funcionan y detallar su complejidad computacional
18.02.Entrega de la tarea sobre matroides (la demostración de que lo de bosques es un matroide - ver diapositivas)
25.02.Entrega de la tarea alternativa: implementar DFS con una pila y BFS con una cola, leyendo el grafo de un archivo e imprimiento el orden de visitas
08.03.Entrega de la tarea de distancia de edición - implementar o explicar
14.04.Sesión de preguntas sobre las tareas
16.04.Fecha lámite de entrega de tareas; revisión en clase

Calificación

Ponderación
Proyecto Tareas Primer examen parcial Segundo examen parcial Examen final
30 20 15 15 20

Resultados

Tareas

Los alumnos se identifica por los dos últimos dígitos de su número de matrícula.

Tareas extras de proyectos

Primer examen parcial (05.03. PDF)

Los alumnos se identifica por los dos últimos dígitos de su número de matrícula (NM). Las tres columnas finales muestran la suma de los puntos, el porcentaje y la cantidad de puntos de calificación final otorgada. La última fila contiene los máximos posibles.

La letra negrita indica los problemas donde el alumno hizo bien, los itálicos los problemas donde hizo mal. En los tres primeros, todos hicieron bastante bien, pero en los otros el rendimiento ya era variado.

NM1234 5678 Suma%CF
5332 211 20212 376
5732 25 36- 6277712
64221 3132- 14406
74222 13 64 6267411
77212 41 612 19548
Max3226 4666 3510015

Segundo examen parcial (30.04.)

Traer una laptop. Sesión de preguntas 28.04.

Los alumnos se identifica por los dos últimos dígitos de su número de matrícula (NM). Las tres columnas finales muestran la suma de los puntos, el porcentaje y la cantidad de puntos de calificación final otorgada. La última fila contiene los máximos posibles.

La letra negrita indica los problemas donde el alumno hizo bien, los itálicos los problemas donde hizo mal. En los tres primeros, todos hicieron bastante bien, pero en los otros el rendimiento ya era variado.

NM123 Suma%CF
53 668 20579
57 71010 277712
64 588 21609
74 899 267411
77 107825 7111
Max101015 3510015

Examen final (28.05.)

Sin materiales. Sesión de calificación por la tarde el 29 de mayo. Son 19 puntos por respuesta y un punto por una asignación razonable de prioridades. Se otorgó un punto adicional por la participación en la sesión de calificación y un punto extra por haber tratado el tema de matroides.

Calificación final (acumulada)

NM Examenes Tareas Proyecto Extra Suma
P1P2F T1T2T3
53 6912 677 271185
57 121219 674 2614100
64 6918 477 2723100
74 111118 477 27590
77 81117 637 25885
Max151520 677 30-100

Material

El material de apoyo del sobre el diseño y análisis de algoritmos está disponible en PDF. Para leer el documento en yalma, en vez de copiarlo, es mejor crear un enlace simbólico para siempre ver la versión actual. Esto se logra por la instrucción

ln -s /u/faculty/elisa/public_html/teaching/aa/pdf/aa.pdf aa.pdf

después de que basta con ejecutar

/opt/Acrobat5/bin/acroread aa.pdf

para abrirlo en Acrobat Reader.

Libros

El mundo está lleno de libros relacionados. Los siguientes libros de texto, que son favoritos personales de la profesora, sirven como material de estudio, aunque asistencia en las clases o estudio de las diapositivas cubrirá los temas esenciales también.

Notas y tutoriales

Enlaces útiles

Utilización de documentos de formato PDF

Para acceder las diapositivas, ejercicios y otros materiales en formato PDF, se necesita Acrobat Reader (descarga gratuita) u otra herramienta similar (en sistemas linux/unix, use el comando acroread o xpdf). Para crear documentos en formato PDF, en Windows se puede instalar una impresora virtual como Primo PDF y en linux imprimir a un archivo en PostScript y utilizar el comando ps2pdf para la conversión.

Actualizado por última vez el 27 de septiembre del 2010.
URL: http://elisa.dyndns-web.com/~elisa/opt/comb/