II Escuela Latinoamericana de Algoritmos

26 al 30 de septiembre de 2016

Escuela Politécnica Nacional, Quito

Entre el 26 y 30 de septiembre del presente año se llevó a cabo en la Escuela Politécnica Nacional la II Escuela Latinoamericana de Algoritmos, organizada conjuntamente por el Núcleo Milenio de Información y Coordinación en Redes de Chile y el Centro de Modelización Matemática - ModeMat. El evento contó con la presencia de cerca de 30 participantes, entre estudiantes avanzados de pregrado, estudiantes de posgrado, profesores e investigadores con interés en las áreas de matemática aplicada, optimización y ciencias de la computación. La Escuela comprendió tres cursos, desarrollados mediante clases magistrales y sesiones de ejercicios.

El Núcleo Milenio de Información y Coordinación en Redes es una iniciativa científica aprobada por el Ministerio de Economía, Fomento y Turismo de Chile que persigue como objetivo la consolidación de un polo de investigación de clase mundial en los campos de Algoritmos, Combinatoria, Teoría de Juegos y Optimización, para hacer frente a problemas prácticos como la modelización y mejoramiento del tráfico en redes viales. En este contexto, el Núcleo ha lanzado la idea de organizar escuelas itinerantes a nivel latinoamericano, para fortalecer el desarrollo de las áreas académicas mencionadas en nuestra región. La primera escuela fue desarrollada con éxito en La Habana, Cuba, en el año 2015.

El Centro de Modelización Matemática en Áreas Clave para el Desarrollo - ModeMat - es un centro multidisciplinario de investigación que tiene por objetivo el desarrollo de nuevas técnicas matemáticas y computacionales, y la construcción de innovadores modelos matemáticos para resolver problemas provenientes de diversas áreas de aplicación. Como un mecanismo para fortalecer el desarrollo de la matemática aplicada y las ciencias de la computación en el Ecuador y la región, el ModeMat participa activamente en la organización de conferencias científicas, talleres, escuelas especializadas, y otros eventos académicos.

Cursos

1- Análisis fino de algoritmos y estructuras de datos

El análisis fino de algoritmos, como contraparte del análisis estándar y pesimista de algoritmos en el caso peor, considera otros parámetros además del tamaño de la entrada para capturar mejor la dificultad de la instancia del problema. Desarrollada en los años 70, esta técnica de análisis ha devenido más relevante ahora que los datos a procesar son de gran volumen, apareciendo brechas considerables entre el rendimiento teórico en el peor caso de los algoritmos y el rendimiento en la práctica. Describiremos una introducción a este técnica, revisando problemas clásicos (e.g. búsqueda en arreglos ordenados, ordenamiento de arreglos, etc.), y explicaremos la relación entre el análisis fino y otras técnicas como la sensitividad al tamaño de la salida y la complejidad parametrizada. Concluiremos con algunos problemas abiertos y prometedores, que un alumno podría considerar como trabajo de investigación.
Profesor: Jérémy Barbay (Departamento de Ciencias de la Computación, Universidad de Chile) Material del curso:
Apuntes (Clase 1)
Apuntes (Clase 2)
Apuntes (Clase 3)
Apuntes (Clase 4)
Tarea 1
Tarea 1 (Solución)
Bibliografía

2- Complejidad de comunicación: algunas aplicaciones

La pregunta central de la teoría de la complejidad es la siguiente: ¿Cuánto recurso computacional se requiere para resolver un problema dado? La naturaleza del recurso determina el tipo de complejidad que se está midiendo. Las medidas más comunes son el tiempo y el espacio. Sin embargo, el recurso que se considerará en este curso es el de comunicación. Aquí, la pregunta específica es la siguiente: ¿Cuánta información deben intercambiar distintas partes de un sistema para poder juntos ejecutar cierta tarea? Los resultados en complejidad comunicacional son traspasables, de modo más o menos directo, a problemas de comunicación. En efecto, las técnicas desarrolladas en este curso permitirán acotar, por ejemplo, el tiempo requerido por una red de procesadores para calcular cierta función cuyo input está distribuido. Sin embargo, también son muy interesantes las aplicaciones de resultados en complejidad comunicacional a problemas en los cuales la comunicación no es explícita. En particular, en este curso se abordará el problema consistente en encontrar, para algunas funciones booleanas, la profundidad mínima de circuitos que las calculan.
Profesor: Ivan Rapaport (Universidad de Chile)
Material del curso:
Diapositivas (Parte 1)
Diapositivas (Parte 2)
Ejercicios (Parte 1)

3- Geometría computacional

La geometría computacional es una ciencia que se ocupa del diseño y estudio de algoritmos empleados en la solución de problemas en informática de carácter geométrico. Esta ciencia tiene sus inicios en los años 70, impulsada principalmente por la computación gráfica y los software de diseño gráfico. También se podría considerar su inicio en la Antigua Grecia con el surgimiento de los primeros avances en geometría, respondiendo a preguntas algorítmicas tales como ¿cómo construir con regla y compás la mediatriz de un segmento? Aplicaciones importantes de la geometría computacional hoy en día incluyen la robótica, los sistemas de cartografía como Google Maps, y el diseño de circuitos electrónicos integrados. En estas charlas haremos una introducción a la geometría computacional y sus aplicaciones, mostrando que es un área de estudio donde se dan la mano las matemáticas y la computación. Particularmente estudiaremos el problema de calcular la envoltura convexa de un conjunto de puntos, y problemas de optimización en grafos de intersección de objetos geométricos.
Profesor: Pablo Pérez-Lantero (Departamento de Matemáticas y Ciencia de la Computación, Universidad de Santiago de Chile)
Material del curso:
Diapositivas (Partes 1-2)
Diapositivas (Parte 3)
Diapositivas (Parte 4)
Diapositivas (Subsecuencia de suma máxima)

Contacto

Luis Miguel Torres
Comité Organizador
luis.torres@epn.edu.ec
Telf.: (+593-2) 297 63 00 ext. 1535