La actividad se desarrolló en dependencias de la Facultad de Matemáticas del Campus San Joaquín.
Agustin Caracci se convirtió el pasado viernes 16 de agosto en el primer estudiante del Magíster en Ingeniería Matemática y Computacional en realizar su defensa de tesis. El alumno cumplió este paso con distinción máxima gracias a su trabajo titulado "Randomized Binary and Tree Search under Pressure", el cual tuvo como guía al académico José Verschae y como co-guía al docente Cristóbal Rojas, ambos del IMC.
Abstract:
We study a generalized binary search problem on the line and general trees. On the line (e.g., a sorted array), binary search finds a target node in O(log n) queries in the worst case, where n is the number of nodes. In situations with limited budget or time, we might only be able to perform a few queries, possibly sub-logarithmic many. In this case, it is impossible to guarantee that the target will be found regardless of its position. Our main result is the construction of a randomized strategy that maximizes the minimum (over the target position) probability of finding the target. Such a strategy provides a natural solution where there is no apriori (stochastic) information of the target's position. As with regular binary search, we can find and run the strategy in O(log n) time (and using only O(log n) random bits). Our construction is obtained by reinterpreting the problem as a two-player (\textit{seeker} and \textit{hider}) zero-sum game and exploiting an underlying number theoretical structure.
Furthermore, we generalize the setting to study a search game on trees. In this case, a query returns the edge's endpoint closest to the target. Again, when the number of queries is bounded by some given k, we quantify a \emph{the-less-queries-the-better} approach by defining a seeker's profit p depending on the number of queries needed to locate the hider. For the linear programming formulation of the corresponding zero-sum game, we show that computing the best response for the hider (i.e., the separation problem of the underlying dual LP) can be done in time O (n222k), where n is the size of the tree. This result allows to compute a Nash equilibrium in polynomial time whenever k=O(log n). In contrast, computing the best response for the hider is NP-hard.
Agustín Caracci durante la defensa de su tesis.
Cabe destacar que este programa de reciente creación busca que los estudiantes incorporen los fundamentos computacionales, teóricos y prácticos que les permitan desarrollar e implementar diversas herramientas. “Hay una necesidad general de gente que tenga un nivel de conocimiento un poco más profundo que simplemente manejar estas herramientas, para así poder proponer versiones que sean novedosas y que se adapten a los requerimientos específicos del problema que se desea resolver. Eso implica entonces seguir un programa de estudio que esté orientado, precisamente, a que los estudiantes desarrollen esa profundidad. Este magíster tiene un carácter de investigación y en eso se diferencia de otros magísteres que apuntan más bien a conocer una diversidad de herramientas”, explica Cristóbal Rojas, profesor asociado del IMC y jefe del comité de postgrado.
Con la Ingeniería Matemática y Computacional es posible establecer puentes entre distintas disciplinas, y crear métodos más robustos para soluciones a problemas complejos, en vinculación con la sociedad y la industria.
Algunos desafíos del área:
• Desarrollo de métodos más eficientes para el manejo y análisis de datos.
• Diseño de herramientas de aprendizaje estadístico para soluciones con métodos automáticos.
• Desarrollo de métodos de modelación matemática y simulación computacional robustos, para resolver problemas demandantes y de gran escala.
• Diseño de técnicas de optimización y control de vanguardia que ayuden a tomar decisiones eficaces en escenarios complejos.
El magíster -que dura cuatro semestres y se desarrolla en una modalidad diurna presencial- presenta características únicas que lo diferencian de programas ofrecidos por otras instituciones. “Ante el déficit de gente bien capacitada en esta área en el mundo en general, las universidades más importantes, como el MIT o Harvard, han generado programas específicos en esta área. Pero en Latinoamérica no hay. La mayoría de los programas de la región están más bien enfocados en la profundización de una sola área, ya sea la parte matemática, la estadística, o la computacional. En ese sentido nuestro magíster se diferencia al buscar abarcar todas esas áreas de manera transversal, para que los egresados tengan esa flexibilidad a la hora de trabajar”, indica Rojas.
Al postular, los candidatos ya deben haber contactado a alguno de los profesores del magíster -entre los que hay expertos en astrofísica, gestión de operaciones, teoría de bases de datos y computación científica, entre otras áreas- y tener un respaldo de uno de esos académicos para llevar adelante un tema que sea de su interés. “La progresión de cursos del magíster está organizada de forma de ir apoyando el desarrollo de la investigación. Ya en el primer semestre los estudiantes tienen un curso de seminario de investigación, donde exploran qué significa hacer un trabajo de este tipo e inmediatamente a partir del segundo semestre empiezan el proceso de identificar los problemas asociados a su propia investigación y de plantear una hoja de ruta para abordarlos”, explicó Rojas.
Perfil de estudiantes
Para poder participar del Magíster en Ingeniería Matemática y Computacional, se requiere contar con el grado académico de Licenciado en Ingeniería, Matemática, Estadística, Ciencia de Datos o afines, otorgado por una universidad reconocida por el Estado de Chile o, en el caso de instituciones extranjeras, por el Estado del país correspondiente. Además, se debe aprobar el proceso de selección, que cuenta con cuatro etapas: envío de antecedentes, evaluación de antecedentes, notificación formal del resultado y postulación a becas si correspondiese al caso.
En cuanto al campo ocupacional del Magíster, los graduados(as) del Magíster en Ingeniería Matemática y Computacional podrán desempeñarse en distintos ámbitos de investigación científica y aplicada.
Algunos ejemplos:
• Sector público: Rutas de transporte, gestión de atenciones y turnos médicos, ciencias políticas, evaluación de propuestas en concursos a financiamiento.
• Sector privado y consultorías: Herramientas de inversión, automatización de toma de decisiones, sistemas de seguridad en aerolíneas.
• Centros de investigación científica: Física y astronomía, diagnósticos médicos, desarrollo de prótesis, automatización del descubrimiento científico.
Para mayores consultas, los interesados en este programa pueden escribir al correo Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo. o visitar el siguiente enlace: Postgrado IMC.