Departamento de Ingeniería Matemática

Optimización Combinatorial

Código: MA47A

• Equipo docente (nombres, oficinas, etc.)
• Estudiantes
• Horario y salas de clases
• Nota final y criterio de aprobación
• Fechas relevantes
• Tareas, controles y pautas
• Material de interés
• Optimización combinatorial y la WWW

Equipo docente

Estudiantes

Horario y salas de clases

Nota final y criterio de aprobación

La nota final esta basada en las notas de tres (3) controles y la nota del examen. La nota final se calcula de la siguiente manera:

Aquellos para los cuales NF sea mayor o igual a 3.95 aprueban el curso (con nota final NF). Aquellos que no estando en el caso anterior tengan NF mayor o igual a 3.65 y que hayan aprobado un examen especial aprueban el curso (con nota final 4.0).

Es posible que algunos controles lleven asociadas una tarea computacional que influirá en la nota de estos.

Fechas relevantes

• Inicio de clases: Lunes 10 de Marzo
• Vacaciones mitad de semestre: 19-24 de Mayo
• Feriados: 18 de Abril
• Control 1: 26 de Abril
• Control 2: 17 de Mayo
• Control 3: 21 de Junio
• Exámen 3: 8 de Julio
• Último día de clases: Sábado 28 de Junio

Tareas, controles, y pautas

• Control 1: Enunciado, Pauta.
• Control 2: Enunciado, Pauta.
• Control 3: Enunciado, Pauta.
• Examen: Enunciado, Pauta.

• Tarea 1: Implementar algún algoritmo para el problema del árbol generador de peso mínimo.
  • Se puede elegir cualquier lenguaje, pero el código debe compilar y ejecutar en alguna de las máquinas del DIM.
  • No se deben utilizar librerias especiales (i.e., el algoritmo debe ser implementado desde cero).
    
  • La fecha de entrega es antes del comienzo del Control 1 (26 de Abril). Se deducirá 1.0 puntos por día de retraso.
  • La entrega es vía email al auxiliar,  haciendollegar ccódigofuente, instrucciones para compilar y/o ejecutar el programa y la máquina del DIM donde se verificó funciona este funciona.
  • El programa debe funcionar para grafos de hasta 2000 nodos.
  • La estructura del grafo debe ser leída de un archivo de nombre grafo.txt. Ejemplos auto-explicativos del formato en que se especifica el grafo pueden verse en: Grafo 1 (6 nodos), Grafo 2 (6 nodos), Grafo 3 (10 nodos), Grafo 4 (250 nodes), Grafo 5 (1000 nodos), Grafo 6 (2000 nodos) -- los nodos siempre estarán identificados por números enteros, los pesos podrán ser negativos y el grafo especificado siempre será conexo.
  • El programa debe entregar como resultado el valor del árbol generador de peso mínimo.
  Un programa que funcione correctamente tendrá una nota mínima de 4.0. El resto de la nota se asignará de acuerdo a la rapidez del programa en determinar el valor del árbol generador de peso mínimo sobre varios grafos. Dichos grafos estarán divididos en grupos de similar tamaño. Sobre cada grupo de números se determinará un ranking de los programas que funcionen correctamente. La sumatoria de estos rankings corresponderá al ranking final. La nota se asignará de acuerdo a este ranking (por interpolación lineal de las notas entre 4.0 y 7.0).

  La nota de la tarea incidirá en la nota del control de la siguiente forma: se tomará la peor nota del control, se le sumará la nota obtenida en la tarea y se le restará 4.0 puntos (si el valor resultante es mayor que 7.0 o menor que 1.0 se colocará 7.0 o 1.0 respectivamente).

Material de interés

Apuntes

• Notación Asintótica

Pseudo-código

• Búsqueda horizontal -- BFS.
• Búsqueda en profundidad -- DFS.
• Implementación de Prim -- Prim, Max_Heapify, Build_Heap, Extract_Max, Increase_Key.

Controles Año 2000

• Control 1: Enunciado, Pauta,
• Control 2: Enunciado, Pauta,
• Control 3: Enunciado, Pauta,
• Examen: Enunciado, Pauta,

Optimización combinatorial y la WWW

• A compendium of NP optimization problems
• Mathematics --- un buen punto de partida para encontrar información relacionada con matemáticas.
• Personas:
• Alexander Schrijver, página personal.
• Michael Goemans, página personal.
• Demos:
  • Kruskal
  • Prim -- Heap insert & delete, Build heap
  • Dijkstra
  • Floyd-Warshall
  • Ford-Fulkerson
• Organizaciones:
• Institute for Operations Research and Management Sciences (INFORMS)
• Mathematical Programming Society (MPS)
• Centros:
• Combinatorics and Opitmization, U. of Waterloo.
• Operations Research Center, MIT.
• Matrix Reference Manual
• A compendium of NP optimization problems