[Todos CMAT] Fwd: [Todos_imerl] Curso - Algoritmos de Aproximación

[Gonzalo Tornaria]

Reenvío por si es de interés para algún estudiante (de licenciatura).
Le consulté a Pablo que me confirma que el curso puede ser adecuado
para un curso opcional de la Lic. en Matemática.

Aclaro que no hay ninguna gestión hecha con la comisión de carrera de
matemática. En caso que alguien esté interesado sugiero que (a) se
contacte con Pablo (lo copio en este mensaje); y (b) se contacte con
la comisión de carrera de matemática para consultar la posibilidad de
validar estos créditos para la licenciatura, y cómo formalizar la
inscripción.

Saludos,
Gonzalo

---------- Forwarded message ---------
From: Pablo Romero <promero en fing.edu.uy>
Date: Thu, Aug 10, 2023 at 12:54 PM
Subject: [Todos_imerl] Curso - Algoritmos de Aproximación
To: todosimerl <todos_imerl en fing.edu.uy>


Buenas Compañera/os,
                                         Dejo en posdata una
invitación al curso del asunto.

Las clases toman lugar los lunes y jueves de 18:00 a 19:30 en el salón
Beige (725, séptimo piso de la Facultad de Ingeniería).

Si bien ya hemos tenido una clase (empezamos el lunes 7/8), las
inscripciones siguen abiertas.

El sitio EVA del curso se encuentra aquí:
https://eva.fing.edu.uy/course/view.php?id=914

El curso se aprueba mediante participación en clase, resolución de una
lista de ejercicios y una charla de un tema complementario del curso
de libre elección (donde los tribunales son rotativos e integrados por
estudiantes).

Cordiales saludos,
Pablo.

PD: ¡¡Les doy la bienvenida al curso de Algoritmos de Aproximación en
su edición de 2023!!

Este curso es una invitación a explorar el mundo de la optimización,
clasificando problemas según si admiten una solución exacta y
eficiente, una noción de aproximabilidad, o ninguna de las anteriores.

Existe una mujer muy longeva y empoderada que se ha nutrido de
conversaciones con Petersen, Konig, Kuhn y Edmonds, y nadie como ella
es capaz de organizar el mundo de forma exacta y eficiente mediante
asignaciones o correspondencias.
Ella se llama Teoría de Emparejamientos.

Otra teoría muy potente se llama Programación Lineal, que ha mantenido
conversaciones hace más de 90 años con Kantorovich y una intensa
maduración entre 1946 y 1947 mediante intercambios con Dantzig. Esta
teoría se enorgullece de ser una generalización del Álgebra Lineal.

Algunos problemas se resistieron a las técnicas desarrolladas por las
poderosas teorías anteriores. Turing, Cook y Karp han concebido una
manera de clasificar esos intrincados problemas, dando nacimiento a
inicios de la década del 70' a la Teoría de la Complejidad.

Los Algoritmos de aproximación son nietos de las tres teorías
anteriores. Por un lado, la Teoría de Emparejamientos es su musa
inspiradora.
Konig, Dilworth, Fulkerson, Edmonds, Lovasz y luego otras
personalidades, mediante diversas consultas realizadas a la teoría de
la Programación Lineal, notaron que existe una suerte de "dualidad"
entre emparejamientos y cubrimientos, describiendo esos objetos en
términos de grafos. Sus avances por suerte quedaron registrados en
Actas (Dilworth lo hizo en Annals of Mathematics) y en libros (Konig
escribió el primer libro en la historia de la Teoría de Grafos y
Lovasz rinde un homenaje a la Teoría de Emparejamientos junto con
Plummer en un rico y profundo libro de referencia). Dichos algoritmos
de aproximación permiten clasificar de modo más fino a aquellos
problemas "difíciles", o "aparentemente intratables", de la Teoría de
la Complejidad.

En este curso vamos a ver una introducción a los algoritmos de
aproximación. La iniciativa de este curso nace a raíz de un bonito
curso titulado "Approximation Algorithms" por un contribuyente en el
área, el Profesor Maurice Queyranne. Ese curso fue ofrecido en nuestra
Casa de Estudios, la Facultad de Ingeniería, por el año 2009.  Tal fue
mi admiración por ese curso, que luego en 2016 se ha ofrecido este
curso por quien escribe. Ahora en 2023, y nuevamente siendo
principiante en el tema, me propongo ofrecer un espacio para
comprender juntos algunos Algoritmos de Aproximación.

A modo de convite se acaban de subir unas diapositivas relativas a las
primeras 4 clases. En la primera clase vamos a conocernos y a repasar
la teoría de grafos, que es el lenguaje sobre el cual se describen
diversos problemas de optimización combinatoria. En la segunda clase
estudiaremos el Teorema de Konig y mencionaremos algunos teoremas
minimax equivalentes. En el libro de Lovasz se expone una prueba
basada en teoría de grafos; de hecho el mismo Konig ha escrito el
primer libro en la historia de la teoría de grafos, y su teorema que
versa  sobre emparejamientos y cubrimientos es una pieza más de dicha
teoría. En el curso veremos una demostración del Teorema de Konig
basada en la Teoría de Programación Lineal (concretamente, en el
teorema fuerte de discrepancia 0 y las propiedades de matrices
totalmente unimodulares, que eran ya conocidas por Poincaré).

En la tercera clase veremos el concepto de algoritmo de aproximación.
Antes, veremos el significado de problema de optimización combinatoria
y vamos a familiarizarnos con los 5 problemas que estudiaremos en el
curso desde el punto de vista de estructuras combinatorias (luego
volveremos a estudiar estos 5 problemas junto con otros mediante un
esquema dual-primal que se deduce a partir de la programación lineal).
También veremos nociones de complejidad computacional, la
reducibilidad de Karp para probar que un problema de decisión es
NP-difícil y el concepto de reducción que preserva el factor de
aproximación (dos reducciones de naturaleza diferente, pero ambas
permiten clasificar problemas).

En la cuarta clase veremos los primeros algoritmos de aproximación del
curso aplicables al problema del cubrimiento de vértices de mínimo
cardinal (el algoritmo que veremos se inspira fuertemente en el
Teorema de Konig, que es un pilar de la teoría de emparejamientos para
grafos bipartitos) y al problema de cubrimiento de conjuntos, que es
una generalización del problema anterior. Vamos a construir un
algoritmo de factor armónico para el cubrimiento de conjuntos.

En las semanas que siguen voy a ir subiendo nuevas diapositivas y
lecturas complementarias. Próximamente voy a subir ejercicios para un
mejor seguimiento de los contenidos del curso. Durante las clases se
van a dar sugerencias para la resolución de dichos ejercicios.

¡¡Que disfruten mucho de este curso!!
Cordialmente,
Pablo.
_______________________________________________
Todos_imerl mailing list
Todos_imerl en fing.edu.uy
https://www.fing.edu.uy/mailman/listinfo/todos_imerl