Doctor en Sistemas de Ingeniería / Hoy en día, la planificación de la capacidad y la administración de las actividades son dos problemas centrales para cualquier directivo en una universidad. Si bien los objetivos de la planificación de la capacidad difieren de los objetivos que se persiguen con la programación de actividades, éstos están ligeramente relacionados. En el corto plazo, una mala programación de las actividades genera múltiples problemas operativos, como por ejemplo: la existencia de conflictos horarios entre cursos que deben ser inscritos por un mismo grupo de estudiantes o la asignación de una sala de clase con capacidad inferior a la requerida, es natural pensar que estas descoordinaciones provocarán un descontento general, tanto en los estudiantes y profesores, como en los directivos de estas unidades académicas. En el largo plazo, si la planificación de la capacidad está muy por debajo de los requerimientos de las mallas curriculares, disminuirá considerablemente la calidad del servicio, no habrá espacio disponible para programar ciertos cursos, ni tampoco profesores idóneos para dictar sus sesiones. Mientras que si planificamos la capacidad por sobre la demanda de requerimientos, ocasionará un aumento considerable en los costos de inversión y costos de operación. Este trabajo de tesis tiene como objetivo principal dar direcciones para la mejor utilización de los recursos en las universidades y la planificación de éstos en el tiempo. Para el corto plazo se presentan modelos de optimización basados en patrones que permiten resolver el problema de programación de horarios y asignación de salas de clase en universidades. Los modelos de optimización basados en patrones facilitan la utilización de paquetes comerciales que permiten resolverlos. Mientras que para el largo plazo, se presenta un enfoque de solución que determina la planificación de la capacidad para hacer frente a cambios en las matrículas. Este enfoque de solución propuesto se basa en la resolución de un modelo de optimización que utiliza como información de entrada el pronóstico de dos modelos predictivos. El primer modelo determina el número de estudiantes que ingresarán a primer año durante el período de planificación mediante un modelo de series de tiempo, mientras que el segundo modelo determina el número de estudiantes que se inscribirán en cada curso y período simulando el paso de los estudiantes dentro de una malla curricular. Todos los enfoques de solución presentados en esta tesis fueron adaptados para ser aplicados en tres instituciones académicas. En general, al aplicar estos enfoques fue posible obtener mejoras significativas respecto de los enfoques de solución manuales, como por ejemplo: reducción de costos operativos, eliminación de conflictos horarios, un mejor uso de los recursos actuales y la planificación del crecimiento de éstos en el largo plazo.

El proyecto consiste en el diseño y la construcción de un robot Gusano que sea capaz de desplazarse en línea recta sin el uso de patas ni ruedas. El robot Gusano imitará el movimiento zigzagueante de estos seres invertebrados basándose en modelos matemáticos que serán explicados en ésta tesis. Asimismo, de forma alternativa, el robot Gusano desarrollará un desplazamiento adoptando la forma de una rueda para poder recorrer a mayores velocidades sobre superficies planas. Sobre las dimensiones del robot Gusano, ésta tendrá cuarenta y cinco centímetros (45 cm.) de longitud y constará de ocho (08) eslabones. De estos ochos eslabones, seis serán eslabones totalmente modulares y los otros dos eslabones establecerán la cabeza y cola del robot. El material que se empleará será el más idóneo para la presente aplicación. Para lograr las secuencias de movimientos del robot Gusano, se analizará la locomoción natural de dichos invertebrados. Se desarrollarán modelos matemáticos que reproduzcan dichos movimientos de manera eficiente y, posteriormente, estos serán probados mediante programas por computadora. Finalmente, las secuencias con mejores resultados de desplazamiento serán grabadas en una memoria que llevará el robot para su desplazamiento autónomo. Para que el robot Gusano pueda desplazarse de manera autónoma, este poseerá una tarjeta electrónica que se encargará principalmente de controlar los motores del robot. Dicha tarjeta constará principalmente de un microcontrolador, una memoria EEPROM para almacenar las secuencias de movimiento y un módulo inalámbrico para lograr el comando inalámbrico del robot. El microcontrolador controlará siete (07) motores, los cuales se encargarán de generar los movimientos para cada articulación. El programa del microcontrolador tendrá la capacidad de controlar hasta dieciséis (16) motores para futuras ampliaciones y aprovechar su diseño modular. Asimismo, las secuencias de movimientos del robot serán guardadas de forma permanente en una memoria tipo EEPROM. El microcontrolador se encargará de leer las secuencias de movimiento desde la memoria y, con ella, generar las señales de control para los motores. Gracias al módulo de comunicación inalámbrica, el robot podrá ser controlado a distancia. El microcontrolador se encargará de obedecer las instrucciones recibidas desde el mando. En lo concerniente al mando, se diseñará una tarjeta electrónica que poseerá un módulo inalámbrico y será gobernada desde una computadora a través su interfaz serial RS232. A dicha computadora se conectará una consola de videojuegos con interface USB y, con la ayuda de un programa desarrollado en esta tesis, el robot será comandado de una manera más sencilla.

El objetivo de la presente investigación es mejorar la asignación de ternas arbitrales para los encuentros del Torneo Descentralizado del Fútbol Peruano mediante la implementación de un modelo matemático de Programación Lineal Entera Mixta. En el marco teórico se describen investigaciones similares realizadas para resolver problemas relacionas al fútbol haciendo uso de herramientas matemáticas. Además, se explica la importancia y aplicación de la Programación Deportiva en el fútbol. Por último, se exponen los conceptos de Investigación Operativa que son usados en la presente investigación. En el diagnóstico del problema se detalla el contexto en el cual se encuentra el problema objeto de estudio. Además, en la definición de los requerimientos se expone la información básica para la elaboración del modelo como condiciones iniciales, información de equipos participantes, ternas arbitrales y categoría de los mismos. Para el desarrollo del modelo se definen las entradas y salidas, así como los supuestos a considerar. También se definen las partes que conforman el modelo como variables, restricciones y función objetivo. Luego, en la resolución del modelo se definen los parámetros, se presenta el modelo aplicado al fútbol peruano que será resuelto, y los resultados del mismo. Asimismo, en la validación del modelo se realizan diferentes análisis donde se exponen las mejoras de la asignación propuesta frente la actual, como disminución de costos en 2%; mejor distribución de los ingresos, cantidad de partidos, coincidencias por equipo y distancia a recorrer por cada terna disminuyendo la desviación en 82%, 83%, 46% y 68% respectivamente; además, se presenta una matriz de asignaciones propuestas, en donde se demuestra el cumplimiento de diferentes restricciones. Finalmente, se detallan las conclusiones y recomendaciones de la presente investigación. / Tesis

Memoria para optar al título de periodista / El siguiente reportaje consta de tres capítulos. El primero hace un repaso por el mapa actual de la televisión chilena, incluyendo lo relacionado a las horas y pautas de consumo de las audiencias infantiles, a la valoración que se hace a los contenidos que se transmiten, y el rol que tiene la televisión en los hogares, sin obviar por su puesto al 8 rol que cumple el CNTV. Mientras que en el segundo capítulo, muestra el panorama de las productoras audiovisuales infantiles en Chile, abarcando tanto sus logros como los problemas que deben afrontar para subsistir en el país, además, se hace hincapié en cómo eran los programas infantiles tiempo atrás. Ya en el último capítulo, se muestra como han ido avanzando los canales infantiles en el resto de Latinoamérica, y como han hecho uso de la televisión digital para alcanzar sus metas en función de la infancia, junto a eso, se ahonda en la crisis que ha arrastrado TVN el último tiempo, y los planes que se contemplan tanto para salvarlo como para mejorar la calidad del servicio que brinda al país.

Magíster en Ciencias de la Ingeniería, Mención Matemáticas Aplicadas / En este trabajo se estudia una versión en línea del problema de Cubrimiento de Máquinas Paralelas. En este problema buscamos asignar trabajos a una cierta cantidad de máquinas idénticas, maximizando la carga de la máquina menos cargada. En el problema en linea los trabajos son revelados uno a uno sucesivamente, y ante la llegada de cada trabajo el programador debe decidir a qué máquina asignar el trabajo. A diferencia del modelo clásico, donde las decisiones son irrevocables, se considera un modelo dinámico introducido por Sanders et al. \cite{SSS09}. En este modelo, ante la llegada de un trabajo nuevo, algunos trabajos anteriores pueden ser reasignados. Sin embargo la carga total de trabajos migrados debe ser a lo más proporcional al tamaño del trabajo entrante. La constante de proporcionalidad se denomina \emph{factor de migración} del algoritmo, y mide la robustez de las soluciones construidas. En primer lugar se estudian algoritmos de búsqueda local, ya que gran parte de estos algoritmos pueden ser adaptados de manera sencilla al contexto en línea con migración. Se demuestra que para la vecindad de \emph{Saltos} e \emph{Intercambios}, el factor de aproximación de una solución localmente óptima yace en el intervalo $[1.691, 1.723]$. Además, usando técnicas de sensibilidad para programación entera, se da una vecindad para la cual las soluciones localmente óptimas son $(1+\e)$-aproximadas y pueden ser halladas en una cantidad polinomial de iteraciones, obteniéndose un PTAS basado exclusivamente en búsqueda local. Posteriormente se analizan y diseñan algoritmos para el problema en línea con migración. El primer resultado es una mejora en la cota inferior del factor de competitividad alcanzable con migración constante de $\frac{20}{19}$ obtenida por Skutella y Verschae \cite{SV10} a $\frac{17}{16}$. Luego, utilizando un procedimiento de redondeo para la instancia distinto al usado en trabajos anteriores, denominado redondeo a múltiplos, se diseña una versión en línea de optimalidad local respecto a saltos con factor de migración $O\left(\frac{1}{\e}\log\frac{1}{\e}\right)$. Modificando esta propiedad levemente, se obtiene un algoritmo $\left(\frac{3}{2} + \e\right)$-competitivo usando factor de migración $O\left(\frac{1}{\e}\log\frac{1}{\e}\right)$. Finalmente, explotando la simetría otorgada por el redondeo a múltiplos, se diseña una versión en línea de $\LPT$, que es una $(\frac{4}{3}+\e)$-aproximación para el problema de Cubrimiento de Máquinas, con factor de migración $O\left(\frac{1}{\e^3}\log\frac{1}{\e}\right)$. Usando la intuición generada por esta simetría junto a las técnicas de programación entera y \emph{configuraciones} de máquinas, se obtiene un nuevo programa entero para el problema que es más simple y abre las puertas a obtener un PTAS para el problema de Minimización de Makespan en línea cuyo factor de migración tenga dependencia polinomial en $\frac{1}{\e}$, lo que aún es un problema abierto.

Magíster en Ciencias, Mención Computación / Ingeniero Civil en Computación / En el campo de los sistemas distribuidos, lograr la coordinación entre diversas unidades de cómputo y sub-sistemas es una tarea compleja, pues cada unidad de computo se comporta distinta a las demás, de forma concurrente y de manera descentralizada. Con el fin de expresar como diversas unidades de computo se comunican unas con otras, se utilizan definiciones de protocolos. Session types son una disciplina de tipos que permite lograr la coordinación entre muchos participantes de un sistema distribuido, mediante la definición de un protocolo coreográfico. La disciplina de tipos impone condiciones sobre la coreografía con el fin de asegurar que el sistema distribuido que la implementa se comporta de la forma en la que fue definido y además posee garantías sobre propiedades de la comunicación. Entre las propiedades importantes se encuentran la ausencia de: deadlocks, mensajes huérfanos y recepciones inesperadas de mensajes. La coreografía es expresada como una entidad global, la cual es projectada a distintos tipos, uno para cada participante involucrado en la coreografía. Dichos tipos son usados para un proceso de typecheck que verifica que las implementaciones de las unidades distribuidas, llamadas procesos, se comportaran en la interacción global como se espera. Se muestra que lograr modularidad en session types no es trivial. Para ello, se presenta un caso de estudio en el que el uso de definiciones modulares para session types introduce problemas en el comportamiento global luego de su composición. Comenzando desde el caso de estudio, se explica como se introducen dichos problemas al componer sub-sessiones. Se muestra como los problemas globales pueden ser evitados gracias al uso de un mecanismo de composición que se basa en interacciones de bloqueo entre participantes. En este trabajo se desarrolla una extensión de un sistema de tipos que permite la composición modular de session types (MCST). MCST se basa en condiciones impuestas sobre definiciones modulares de sub-sessiones, además de un sistema de tipos que permite verificar sub-sessiones por separado, y un mecanismo de composición que produce sistemas bien formados. La solución presentada es modular, dado que mantiene sus definiciones separadas con el fin de reusarlas. Las condiciones para verificar correctitud no dependen del contexto en el cual una sub-session es llamada.El mecanismo de composición reusa conceptos de inlining y composición con ciclos de trabajos previos, haciéndolas aplicables en más casos, lo que resulta en un sistema más expresivo. MCST mantiene las garantías de comunicación de session types mencionadas previamente. Ademas, MCST mejora la expresividad de session types, dado que la nueva disciplina de tipos con el mecanismo de composición permite definir coreografías que no son permitidas en el estado del arte de session types.

Magíster en Ciencias, Mención Computación / Aspect-Oriented Programming (AOP) is an advanced technique for modularizing crosscutting concerns such as profiling, security, monitoring, among others. To do this, AOP introduces a new functional unit called aspect. In current aspect-oriented systems, aspects references to the base code. Those references are fragile and give up important software engineering properties such as modular reasoning and independent evolution of aspects and base code. In this thesis, we introduce a novel abstraction called Join Point Interfaces that, by design, supports modular reasoning and independent evolution by decoupling aspects from base code and by providing a modular type-checking algorithm. Join point interfaces can be used both with implicit announcement through pointcuts, and with explicit announcement by using closure join points. Join point interfaces further offer polymorphic dispatch on join points, with an advice-dispatch semantics akin to multi-methods. In this work, we show how our proposal solves a large number of problems observed in previous, related approaches. We have implemented join point interfaces as an open-source extension to AspectJ. An initial study on existing aspect-oriented programs supports our initial design in general, but also highlights some limitations which we then address by introducing parametric polymor- phism and a more permissive quantification mechanism. As a result, join point interfaces are a safe and practical way of decoupling aspects.

Magíster en Gestión de Operaciones / Ingeniero Civil Matemático / En el presente trabajo se estudia el problema de envasado y embotellado de pedidos en líneas de producción. El problema es de tipo scheduling con características propias. La resolución del problema se aborda desde dos ángulos. El primer enfoque consiste en plantear un problema de programación lineal mixto satisfaciendo las restricciones operacionales del sistema. Los resultados de esta primera estrategia satisfacen los requerimientos técnicos, sin embargo, los altos tiempos computacionales impiden su utilización para casos reales. El segundo enfoque consiste en la utilización de un Algoritmo Glotón Usando Constraint Programming (AGUCP) más una estrategia de mejoramiento de la solución. AGUCP permite encontrar una solución factible al problema planteado en el modelo de programación lineal mixto con una calidad aceptable. En este caso, los tiempos computacionales son excelentes incluso para casos de gran tamaño. Sin embargo existe un porcentaje de entre el 15% y el 20% de los casos estudiados en los cuales el algoritmo no encuentra solución. Se presenta además una mejora a la heurística AGUCP, la cual se denomina AGUCP++ y consiste básicamente en una implementación propia de AGUCP adaptando el modelo para enfocarse directamente en las variables de decisión de modo de insertarse mejor al espíritu del Constraint Programming. La implementación de este algoritmo fue hecha en Python. Las principales mejoras de este nuevo algoritmo son: (i) Se trabaja con una menor cantidad de variables debido al modo de guardar la información. (ii) El algoritmo entrega una solución, a pesar que, haya uno o más trabajos que no pudieron incorporarse. (iii) Se disminuye la cantidad de casos en los cuales no todos los trabajos son agendados a un 5 %. Esto depende esencialmente de cuan exigentes sea el caso de estudio. (iv) Los tiempos computacionales disminuyen en un 70% en comparación con AGUCP Finalmente, se incorpora una técnica de mejoramiento de la solución obtenida a través de AGUCP++, utilizando una estrategia basada en la técnica llamada Local Search. Estas búsquedas locales operan optimizando sobre un número acotado de trabajos -a partir de una solución inicial-, dejando fijos los demás. Esta estrategia permite, en poco tiempo, obtener mejoras sustantivas de la solución. Según los experimentos realizados, el porcentaje de mejora varía entre un 5% y un 28%.

La programación reactiva es un paradigma enfocado en el trabajo con flujos de datos de manera asíncrona. En este webinar veremos cómo Spring Framework implementa la programación reactiva con WebFlux.

En el presente trabajo se estudió y rediseñó una implementación existente del algoritmo Filter-SDP, el cual resuelve problemas de programación semidefinida no lineal de la forma: donde f : Rn → R, h : Rn → Rp y G : Rn → Sm son funciones de clase C2 y Sm denota el espacio lineal de las matrices simétricas de m×m dotado del producto interno A·B = . El algoritmo resuelve en cada iteración una aproximación local representada por un problema de programación semidefinida lineal, y adicionalmente se utiliza un esquema de penalización multi-objetivo, en el cual se minimiza la función objetivo y una función de mérito utilizando un filtro. Se estudió la introducción de cálculo paralelo en partes específicas del algoritmo, con el objetivo de disminuir el tiempo de ejecución. Se reimplementó el algoritmo utilizando el lenguaje C y la librería de cálculo paralelo MPI. Esa nueva implementación se comparó con un desarrollo ya existente, realizado sobre la plataforma MATLAB, y se midió su speedup en los problemas más pesados de una batería de tests escogida. Como apoyo al desarrollo del algoritmo, se diseñaron nuevas fases de restauración sobre la plataforma MATLAB, con el objetivo de mejorar la calidad de las soluciones obtenidas. Se diseñaron 4 nuevos métodos para la fase de restauración del algoritmo, cuyas principales áreas de influencia son la restauración inexacta, el diseño de controladores retroalimentados de salida estática y el posicionamiento de polos. Dentro de los resultados obtenidos, se logró visualizar las ventajas de la nueva implementación con respecto al desarrollo ya existente, así como demostrar el beneficio que se obtiene en el speedup para problemas pesados. También se realizó una comparación entre los métodos diseñados para la fase de restauración, con la cual se llegó a conclusiones que pueden abrir nuevas áreas de investigación y trabajo a futuro. Finalmente, se aprendió a utilizar una herramienta de álgebra lineal que funciona sobre ambientes de cálculo paralelo, ScaLAPACK, y se perfeccionó el proceso de desarrollo de software que ya se tenía sobre este tipo de plataformas.