V Escuela de Invierno en Matemáticas Discretas

Fecha : 1-3 Agosto 2014

Lugar: Hostería el Copihue, Olmué.

 

Coordinador: José Zamora, U. Andrés Bello (email josezamora (a) unab.cl).

Cursos

En la primera parte de la clase se definirá el concepto de arreglos perfectos y se mostrará su relación con otros objetos combinatoriales.
Se continuará con aspectos enumerativos, para terminar analizando elementos algorítmicos y de complejidad.

  • Jeremy Barbay : “ Más alla del peor caso: Desde “Merge sort” hasta “Convex Hull”“.
El análisis tradicional de algoritmos ” el peor caso” sobre instancias de tamaño fijo es, por definición, pesimista. A medida que el volumen de datos tratados crece, el gap entre el rendimiento del mejor algoritmo “en el peor caso” y el mejor algoritmo “en la practica” crece, lo que reduce el interés de una análisis teórico.En esta charla/curso, veremos algunos ejemplos simples de análisis mas finos sobre el algoritmo “MergeSort”, revisando temas como el cálculo de códigos libres de prefijos de Huffman. Además, estudiaremos como aplicar esta análisis a problemas similares, como el cálculo de Coberturas Convexas (“Convex Hull”) y de triangulaciones de Delaunay en dos dimensiones.
Principios como la definicion de log(n), recursividad y  complejidad en el peor caso se asumen conocidos.
Algunos recuerdos acerca de “Mergesort” y “Huffman” ayudaran a entender el curso, sin ser necesarios. Conocimientos sobre coberturas convexas y triangulaciones de Delaunay NO son necesarias.

  • José Verschae : “Relajaciones semidefinidas positivas y formulaciones extendidas para algoritmos de aproximación”.

Un algoritmo de aproximación es un algoritmo que da una solución con una garantía de calidad para sus soluciones. Una técnica importante para el diseño de este tipo de algoritmos es la de formular el problema con variables enteras y después relajar la integralidad. Así se obtiene una relajación que se puede resolver en tiempo polinomial, cuya solución se puede redondear para obtener una solución entera factible con costo acotado. En este mini-curso nos enfocaremos en el diseño de algoritmos basados en relajaciones no-lineales, en particular semidefinidas positivas. Partiremos mostrando el resultado clásico de Goemans y Williamson para Max-Cut. Luego nos enfocaremos en técnicas más recientes que dan una manera sistemática de obtener relajaciones mejoradas, en particular hablaremos de técnicas tipo lift-and-project y de la jerarquía de Lasserre.

Programa:

Viernes 01:

  • 15:00             – Salida de Santiago
  • 18:00- 19:00 – Video.
  • 19:00- 20:30 – Discusión

Sábado 02:

  • 09:30 – 11:00 – Curso 1.
  • 11:15 – 12:45 – Trabajo Alumnos
  • 12:45 – 13:30 – Presentaciones.
  • 15:00 – 16:00 – Curso 2.
  • 16:00 – 17:00 – Trabajo Alumnos
  • 17:00 – 17:30 – Presentaciones.
  • 17:30 – 18:15 – Curso 2.

Domingo 03:

  • 09:30 – 11:00 – Curso 3.
  • 11:15 – 12:45 – Trabajo Alumnos.
  • 12:45 – 13:30 – Presentaciones.
  • 15:00             – Regreso a Santiago.


Postulaciones

La Escuela está dirigida a estudiantes de pregrado y postgrado que se interesen en algoritmos, teoría de grafos, combinatoria y la teoría de juegos. Las sesiones estarán orientadas principalmente a estudiantes de pregrado.

Los interesados en participar deben postular llenando el siguiente formulario.
Se recibirán postulaciones hasta el  18 de Julio. Los alumnos aceptados dispondrán de la ayuda financiera suficiente para cubrir el transporte, la estadía (en pieza compartida) y comidas.

Esta es la quinta versión de la escuela. Versiones anteriores.