Departamento de Ingeniería Matemática

Optimización Combinatorial

Código: MA4701

• Equipo docente (nombres, oficinas, etc.)
• Nota final
• Fechas relevantes
• Material de interés
• Optimización combinatorial y la WWW

Equipo docente

Nota final

La nota final esta basada en las notas de dos (2) controles y la nota del examen. La nota final se calcula como el promedio ponderado del examen (50%) y del promedio de los controles (50%).

Fechas relevantes

• Inicio de clases: Martes 11 de Octubre
• Control 1: Sábado 26 de Noviembre
• Control 2: Viernes 06 de Enero

Material de interés

Apuntes

• Definiciones básicas sobre grafos
• Notación Asintótica

Pseudo-código

• Búsqueda horizontal -- BFS.
• Búsqueda en profundidad -- DFS.
• Kruskal y Prim (e implementación de este último usando heaps)
• Caminos de costo mínimos -- Bellman-Ford, Relax, Dijkstra

Controles

Año	Evaluación	Enunciado	Pauta
2000	Control 1	PS	PS
	Control 2	PS	PS
	Control 3	PS	PS
	Examen	PS	PS
2003	Control 1	PDF	PS
	Control 2	PS	PS
	Control 3	PS	PS
	Examen	PS	PS
2006	Control 1	PDF - PS	PDF - PS
	Control 2	PDF - PS	PDF - PS
	Control 3	PDF - PS	PDF - PS
	Examen	PDF - PS	PDF - PS
2011	Control 1	PDF	PDF
	Control 2	PDF	PDF
	Examen	PDF

Optimización combinatorial y la WWW

• 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:
  • Algoritmos en grafos
  • Kruskal
  • Prim -- Heap insert, delete, & extract (o ver applet alternativa), Build heap
  • Dijkstra
  • Floyd-Warshall
  • Matrix chain multiplication
  • 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