Ingeniero Civil Matemático / Esta memoria tiene como objetivo el análisis de un modelo de transmisión de datos bajo el contexto de network coding. El modelo fue inspirado en un estudio de comunicación en redes inalámbricas. En el escenario a estudiar, se desea enviar información particionada en paquetes, que llegan a un transmisor, a múltiples receptores. Se considera que el tiempo está particionado en períodos de tiempo iguales. Los paquetes, modelados como vectores de un espacio vectorial, llegan al transmisor mediante un proceso de Bernoulli de tasa $\lambda$. El transmisor puede enviar, en cada período, una combinación lineal de paquetes por igual a cada uno de los receptores. Las transmisiones pueden fallar en cada período con probabilidad $1-\mu$ de manera independiente entre cada receptor. Los receptores deben ser capaces de recuperar cada paquete de información original. En el contexto descrito, el principal parámetro de estudio es el retraso de decodificación de un paquete, definido como el tiempo esperado que transcurre entre que llega el paquete al transmisor y el instante en que un receptor logra decodificarlo (es decir, ser capaz de calcular una combinación lineal entre las transmisiones que el receptor ha recibido, cuyo resultado sea el paquete en consideración). El caso de interés del análisis del retraso de decodificación, es cuando el factor de carga $\rho = \lambda/\mu$, con $\lambda < \mu$, $\rho \rightarrow 1$. En primer lugar, se analiza el caso en que existen dos receptores. El transmisor ocupa un esquema de codificación propuesto en la literatura para calcular las combinaciones lineales de paquetes que se van a enviar. Se demuestra que el tiempo esperado del retraso de decodificación es $O\left( \frac{1}{1-\rho} \right)$, siendo una cota asintóticamente óptima. Se introduce el uso de funcionales de Lyapunov sobre cadenas de Markov, que permiten estudiar y acotar esperanzas que dependen del funcional. Posteriormente, se estudia si es posible para el caso de dos receptores realizar transmisiones, en períodos específicos, que den prioridad al receptor que ha recibido menos paquetes, con el objetivo de acotar el retraso de decodificación de los paquetes que le falta por decodificar a tal receptor. Aquí, se introduce la técnica de coupling de cadenas de Markov en el contexto de network coding. Por último, se avanza en el análisis de un esquema de codificación para el caso de tres receptores propuesto en la literatura. Se generalizan resultados que permiten obtener cotas para el caso de dos receptores utilizando funcionales de Lyapunov, adecuando las hipótesis a las que se tienen en el esquema de codificación en consideración.

Ingeniero Civil en Computación / En este trabajo se propone un nuevo método para la recuperación de documentos eficiente en espacio reducido. En términos generales, en recuperación de documentos se busca responder eficientemente a consultas sobre una colección de documentos con aquellos documentos cuyo contenido satisface algún criterio especificado en las consultas. Para acelerar las consultas los documentos son indexados con alguna estructura de datos. Las soluciones tradicionales para estos problemas basadas en índices invertidos no son adecuadas para dominios en los cuales los patrones de consulta son arbitrarios. Por ello, para colecciones cuyo contenido son, por ejemplo, secuencias de ADN, secuencias de proteínas, datos multimedia o algunos lenguajes naturales estas soluciones no son aplicables. Los índices de texto completo ofrecen una alternativa. Estos permiten indexar patrones generales pero incurren en un excesivo costo en espacio. Muthukrishnan diseñó una solución que utiliza este tipo de índices junto con otras estructuras para resolver listado de documentos. Su algoritmo es óptimo en tiempo pero consume más de veinte veces el espacio que ocupa la colección de documentos de entrada. Sadakane desarrolló una variante del algoritmo de Muthukrishnan. Para reducir el espacio introduce algunas modificaciones y diseña estructuras compactas que reemplazan las utilizadas por Muthukrishnan. Además extiende el algoritmo para resolver consultas de listado de documentos jerarquizadas. El espacio ocupado por el algoritmo de Sadakane para consultas jerarquizadas resulta excesivo para muchas aplicaciones prácticas. Aquí se proponen nuevas estructuras compactas para abordar este problema. Los resultados experimentales muestran que la nueva estrategia resuelve el problema de listado de documentos con sus frecuencias en un espacio menor y con la misma eficiencia que la solución original de Sadakane.

No description available.

No description available.

Magíster en Gestión de Operaciones / Este proyecto, formó parte del plan de mitigación de clientes morosos implementado por una empresa de telecomunicaciones en el año 2009, dónde una de las líneas de acción estaba enfocada en disminuir la morosidad de los nuevos clientes en su primera factura. Se propuso un modelo que clasifique a los nuevos clientes en pagadores y no pagadores, permitiendo con ello, reorientar recursos y realizar acciones preventivas de morosidad de manera más focalizada y efectiva, las cuales estaban siendo hasta ese momento aplicadas al universo total de nuevos clientes. El éxito de este proyecto requería el compromiso del área de cobranzas, usuaria del modelo, por esto, la elección del modelo consideró aspectos tanto teóricos como prácticos. La simpleza y la fácil ejecución del modelo, idealmente programable, eran variables deseables y decidoras del éxito de éste. Se ejecutó basado en Clasificación Bayesiana por su forma simple de utilizar y presentar una confiabilidad aceptable [17]. Los métodos de inducción bayesiana han demostrado ser una clase de algoritmos tan competitivos como los métodos árboles de decisión y redes neuronales [29], que permiten implementar algoritmos en Wolfram Mathematica 6.0 cuyas sentencias de programación son muy similares al lenguaje C++, permitiendo su programación posterior. El modelo se confeccionó con 42.087 clientes, contratantes entre el 15 de julio y el 15 de octubre del 2009, de estos, 40.087 formaron la base de aprendizaje para calibrar y realizar los cálculos de probabilidades, y 2.000 como base de testing. Los clientes a clasificar en pagadores y no pagadores correspondieron a 9.328, quienes ingresaron a la empresa entre el 16 de Octubre y el 15 de Noviembre del 2009. En base a establecer una probabilidad a priori, se plantea en valores estimados de corte probabilístico basado en la experiencia o un método de clasificación [19], por una probabilidad de corte de 0,4 para clasificar a un cliente pagador por la necesidad que enfrenta la empresa de mejorar el % de clientes morosos en su primera boleta y a la vez reducir los costos actuales involucrados en la cobranza. El modelo clasificó a 2.910 clientes como no pagadores, 2.179 de ellos efectivamente no cancelaron su boleta al vencimiento (75%). Este resultado es compatible con el esperado en el análisis teórico, debido a la eficiencia de los estimadores estimados, como también, el tamaño de los set de datos empleados que en forma teórica respalda los resultados obtenidos con un 80% de confiabilidad. Como trabajo futuro, resulta interesante evaluar el aporte del modelo en la reducción real del porcentaje de clientes morosos al permitir reorientar recursos y focalizarse en ciertos clientes, como a su vez, actualizar la base de aprendizaje de tal forma ir considerando la actualidad al modelo.

Magíster en Gestión de Operaciones / El objetivo principal de este trabajo es proporcionar un algoritmo que resuelve instancias de gran tamaño para problemas de juegos de seguridad de Stackelberg con un énfasis en reducir el número de recursos necesarios requeridos para calcular dicha solución. Para ello se utilizan los principios de generación de columnas para desarrollar un algoritmo que procede mediante la resolución de un problema más pequeño (menor número de restricciones). Entonces, de forma iterativa, añadimos restricciones hasta que el problema llega a las condiciones de parada definidas. Básicamente, partimos de un problema secundario del original con dos jugadores que juegan a la seguridad y cuentan con un espacio de estrategia limitado, ya que este considera sólo un número limitado de restricciones. Iterativamente, verificamos si algún jugador le gustaría cambiar su estrategia con el fin de incrementar sus utilidades, añadimos la estrategia candidata y resolvemos una vez más. Esto sugiere un método de descomposición que es capaz de estimar el conjunto mínimo de restricciones a tener en cuenta con el fin de encontrar también la solución óptima para el problema global. En el transcurso de nuestros estudios identificamos que el proceso de iteración no siempre encuentra la solución óptima para el problema global. Luego, proporcionamos un análisis y caracterización de la estructura de las funciones de utilidad para ambos jugadores con el fín comprender más la dinámica de los jugadores e identificar las situaciones en las que la solución óptima global efectivamente es encontrada. Más tarde, se presenta una implementación que incluye datos del mundo real a través de una red en el centro de Santiago, Chile. Las recompensas se calcularon teniendo en cuenta el promedio histórico robado en cada lugar y un valor estimado de la falta de voluntad de ir a la cárcel para efectos de los asaltantes. Finalmente, comparamos nuestro algoritmo con los demás ya la literatura en escenarios similares. Mostramos que nuestros métodos nos permiten ofrecer de manera eficiente soluciones razonables para los problemas de seguridad en tamaño del mundo real. Además comparamos nuestros resultados con los resultados utilizando la metodología estándar de resolución de problemas lineales y mostramos que se pueden reducir ampliamente la necesidad de recursos computacionales y en algunos casos, el tiempo de ejecución para llegar a la solución.

Magíster en Ingeniería de Negocios con Tecnología de Información / El presente trabajo afina el modelo de negocio en la gestión de compras de la empresa distribuidora de electricidad Chilectra S.A., a través del análisis y rediseño del proceso Administración Relación de Proveedores , sustentado en el patrón de negocios Macro 1 dvs Administración y Ventas de Stock, complementado por la metodología de colaborativa en la gestión de la cadena de aprovisionamiento Collaborative Planning, Forecasting, and Replenishment . A través de esta metodología se resolvieron problemáticas en la gestión de abastecimiento, con la disminución de la incertidumbre en la determinación de la demanda y optimización de las compras de materiales recurrentes, lo que permitió ahorros en los costos de inventario en un 10,56 %.El desarrollo de este proyecto sustenta un proceso sistemático de compartir información y conocimiento con los proveedores estratégicos, además de la implementación de pronósticos de demanda se describen las oportunidades de mejora de problemas antes mencionados. En la evaluación económica se cuantifican los ahorros producto de los beneficios y se calcula el VPN del proyecto, obteniéndose un valor de $460MM para una tasa de descuento de 10,43% que se calculó a través de método de CAPM. La simulación y prototipo proporcionaron la base para la cuantificación de beneficios al comparar la realidad versus el modelo para un periodo de 5 meses. El trabajo de Tesis también propone un marco de referencia para soluciones tecnológicas para cualquier tipo de empresas en la gestión de aprovisionamiento. Para ello se generalizó la experiencia a través de un proceso de decisión de compra en función de pronósticos de la demanda, mostrando así la aplicabilidad del modelo a otros dominios de negocios. Además, para la implementación de este proyecto se consideró el ámbito asociado a la gestión del cambio, el cual facilita la flexibilidad y adaptación de las personas para llevar a cabo nuevos retos como la ejecución de este proyecto, todo esto a través de un plan de gestión del cambio con enfoque en los procesos, de modo de asegurar el éxito del mismo.

Magíster en Ciencias de la Ingeniería, Mención Matemáticas Aplicadas. Ingeniero Civil Matemático / En 1992 M. Boshernitzan [6] presenta una condición suficiente para que los subshifts minimales sean únicamente ergódicos. Usando el concepto de factores simbólicos extendemos esta condición a sistemas minimales de Cantor. Decimos que un sistema minimal de Cantor satisface la condición de Boshernitzan si todos sus factores simbólicos satisfacen la condición de Boshernitzan. Esta extensión resulta natural en cuanto todo sistema minimal de Cantor es topologicamente conjugado al límite inverso de ciertas secuencias factorizantes de factores símbolicos. Demostramos que la condición de Boshernitzan implica única ergodicidad para sistemas minimales de Cantor. También mostramos que esta condición puede ser verificada analizando cualquier representación de Bratteli-Vershik de un sistema minimal de Cantor dado. Luego tiene sentido buscar condiciones sobre los diagramas de Bratteli asociados a un sistema minimal de Cantor que sean necesarias y/o suficientes para que tal sistema satisfaga la condición de Boshernitzan. Presentamos varias de estas condiciones. Las más generales están relacionadas con el comportamiento asintótico de los vectores de altura y los vectores de medida de las representaciones de Bratteli-Vershik. Estas condiciones son luego reduci- das, sacrificando un poco de generalidad, a condiciones concernientes a la repetición de un bloque de matrices positivas dado en una cantidad infinita de niveles de los diagramas. En todos los casos se considera una hipótesis de estandarización sobre el orden de los diagramas. Se explora el alcance y las limitaciones de los criterios presentados a través del estudio de ejemplos específicos. Se observa que la combinatoria de los sistemas influye de gran manera en el cumplimiento de la condición de Boshernitzan. In 1992 M. Boshernitzan [6] provided a sufficient condition for minimal subshifts to be uniquely ergodic. By using the concept of symbolic factors we extend this condition to Cantor minimal systems. We say a Cantor minimal systems satisfies Boshernitzan s condition if all of its symbolic factors satisfy Boshernitzan s condition. This extension seems natural given the fact that every Cantor minimal system is topologically conjugate to the inverse limit of certain factoring sequences of symbolic factors. We prove that Boshernitzan s condition implies unique ergodicity for Cantor minimal systems. We also show that this con- dition can be verified by analyzing any particular Bratteli-Vershik representation of a given a Cantor minimal system. It then makes sense to look for diagram related necessary and/or sufficient condition for Cantor minimal systems to satisfy Boshernitzan s condition. We pro- vide several of these conditions. The more general ones relate to the asymptotic behaviour of the height vectors and measure vectors of the Bratteli Vershik representations. These con- ditions are then reduced, sacrificing some generality, to conditions concerning the repetition of a given block of positive matrices at inifinitely many levels of the diagrams. In all cases a standardization hypothesis on the order of the diagrams is made. We explore the scope and limitations of the criteria provided by studying specific examples. The combinatorics of the systems is seen to greatly influence the achievement of Boshernitzan s condition.

No description available.

No description available.