Publicación a texto completo no autorizada por el autor / Analiza y evalúa algoritmos de rutas de transporte para optimizar el servicio de mensajería interna en una empresa del sector financiero. Para la mensajería interna, la empresa cuenta con un servicio de motorizados contratados con un proveedor externo el cual ha tenido muchos reclamos los últimos meses, debido a que no se está llegando a los tiempos de entrega acordados y por parte de gerencia está presionando en revisar bien el contrato con el proveedor y los niveles de servicio acordados. Para esto, los conceptos de investigación operativa y los algoritmos de rutas de transporte fueron utilizados para dar solución a este problema y definir el proceso interno cumpliendo de manera eficiente los tiempos de entrega. En primer lugar, se definió la población la cual son todas las rutas de los motorizados realizadas entre el 01 de agosto del 2016 hasta el 31 de julio del 2017 (01 año). Como segundo paso, se determinó la muestra a analizar para lo cual se utilizó la fórmula del tamaño de muestra para una proporción poblacional si se conoce la población. Luego se eligió las rutas de manera aleatoria ayudándonos del Microsoft Excel 2016 para determinar las rutas a analizar. Para obtener el detalle de las rutas seguidas por los motorizados, se solicitó al supervisor del área encargada brinde el detalle histórico de los documentos entregados con las direcciones y horas pactadas. Los análisis de los algoritmos se realizan a través de métodos heurísticos y metaheurísticos para el VRP (Vehicle Routing Problem) para el cual se seleccionan tres métodos y según la evaluación se tendrá el que mejor se adapte a la casuística. / Tesis

El presente trabajo está enfocado en las bases de datos multimedia, área importante de investigación en los últimos años. Por objetos multimedia se entiende contenido como audio, imágenes, objetos 3D, etc. A diferencia de las bases de datos tradicionales, en una base de datos multimedia no se buscan los objetos que cumplan una condición exacta, sino los más parecidos a un objeto conocido de antemano, llamado objeto de consulta. Por esta razón, la búsqueda por similitud es uno de los temas principales de estudio en las bases de datos multimedia. Para reflejar la similitud entre objetos multimedia, en general existen distintos métodos para calcular una distancia entre dos objetos multimedia, los cuales intentan reflejar el parecido entre dichos objetos (a mayor distancia, más disímiles son). Se ha comprobado empíricamente que algunos métodos funcionan mejor que otros ante distintos tipos de objetos de consulta, y que combinar varios de ellos a la vez entrega generalmente mejores resultados que utilizar cada uno en forma separada. Sin embargo, aún no existe una forma clara de decidir la forma de combinarlos en el momento de la consulta, y muchas veces se termina utilizando el mejor método en promedio, lo cual no siempre es la mejor opción. En este trabajo se estudia un método formal para combinar estos métodos, realizando una consulta previa en un conjunto de objetos conocido como conjunto de entrenamiento, que permite estimar en forma dinámica la calidad de cada método ante un objeto de consulta dado. Como primera tarea, se implementó un entorno de trabajo que permite realizar experimentos de manera masiva, incorporar fácilmente distintos tipos de bases de datos y definir los tipos de experimentos a ejecutar. El entorno de trabajo implementado permitió estudiar cómo afecta la selección de un conjunto de entrenamiento en determinar la calidad de un método de transformación de objetos multimedia. De los resultados experimentales obtenidos, se concluye que un conjunto de entrenamiento adecuado es de un tamaño bastante pequeño en relación a la base de datos original, lo que permite estimar la calidad de un método de cálculo de similitud con poco esfuerzo adicional. Adicionalmente, se observó que el cálculo dinámico de esta información permite aproximarse bastante a mejores combinaciones de métodos, las cuales sólo pueden ser obtenidas mediante fuerza bruta. Se muestra también que algunos resultados tienden a ser independientes de la base de datos, mientras que otros son exclusivos de la forma en que ésta haya sido construida, y que en general todos los resultados poseen un buen grado de robustez, lo que permite reproducirlos fácilmente en bases de datos con distintos tipos de información multimedia.

Ingeniero Civil en Computación / El estudio cuantitativo de estructuras microscópicas 3D requiere de herramientas computacionales, tanto para realizar mediciones como para su visualización, dada su complejidad y gran volumen. Una de las herramientas para medir y visualizar estas estructuras es el skeleton. Un skeleton es la representacion simplificada de la estructura en forma de grafo, compuesta por nodos y segmentos. Si bien existen múltiples algoritmos para su generación, estos buscan generalmente mantener propiedades topológicas y geométricas del objeto de estudio. Actualmente se cuenta con la implementación de un algoritmo de generación de skeletons [2], basado en el algoritmo propuesto por Au et al [3]. Esta implementación, si bien entrega resultados satisfactorios, presenta tiempos de cálculo muy extensos. Dado lo anterior, es que esta memoriam tiene como objetivo analizar y optimizar el tiempo de ejecución de esta implementación. En este trabajo se realizaron optimizaciones seriales y la paralelización del cálculo. La optimización serial incluyó: (1) implementación del algoritmo con una nueva estructura de datos: Halfedge, (2) optimización en la actualización de costos de arcos, (3) optimización en el uso de la cola de costos y (4) optimización de estructuras de datos. La paralelización fue realizada sobre una de las etapas más demandantes del algoritmo usando la unidad de procesamiento gráfico (GPU). Para validar las optimizaciones y paralelización, se realizaron pruebas de la correctitud y speed-up alcanzado en: (1) modelos 3D creados simples, (2) modelos sintéticos de estructuras biológicas y (3) modelos de estructuras biológicas obtenidas de imágenes de microscopía. Con las optimizaciones y paralelización implementados, se logró una mejora sustancial en el tiempo, pasando de días a minutos o incluso segundos. Además, se verificó que estas mejoras mantienen los skeletons resultantes bien definidos, vale decir, mantienen las propiedades que deben cumplir.

Magíster en Gestión de Operaciones / Ingeniero Civil Industrial / Los sitios de redes sociales virtuales han tenido un enorme crecimiento en la última década. Su principal objetivo es facilitar la creación de vínculos entre personas que, por ejemplo, comparten intereses, actividades, conocimientos, o conexiones en la vida real. La interacción entre los usuarios genera una comunidad en la red social. Existen varios tipos de comunidades, se distinguen las comunidades de interés y práctica. Una comunidad de interés es un grupo de personas interesadas en compartir y discutir un tema de interés particular. En cambio, en una comunidad de práctica las personas comparten una preocupación o pasión por algo que ellos hacen y aprenden cómo hacerlo mejor. Si las interacciones se realizan por internet, se les llama comunidades virtuales (VCoP/VCoI por sus siglas en inglés). Es común que los miembros compartan solo con algunos usuarios formando así subcomunidades, pudiendo pertenecer a más de una. Identificar estas subestructuras es necesario, pues allí se generan las interacciones para la creación y desarrollo del conocimiento de la comunidad. Se han diseñado muchos algoritmos para detectar subcomunidades. Sin embargo, la mayoría de ellos detecta subcomunidades disjuntas y además, no consideran el contenido generado por los miembros de la comunidad. El objetivo principal de este trabajo es diseñar, desarrollar y evaluar un algoritmo para detectar subcomunidades traslapadas mediante el uso de análisis de redes sociales (SNA) y Text Mining. Para ello se utiliza la metodología SNA-KDD propuesta por Ríos et al. [79] que combina Knowledge Discovery in Databases (KDD) y SNA. Ésta fue aplicada sobre dos comunidades virtuales, Plexilandia (VCoP) y The Dark Web Portal (VCoI). En la etapa de KDD se efectuó el preprocesamiento de los posts de los usuarios, para luego aplicar Latent Dirichlet Allocation (LDA), que permite describir cada post en términos de tópicos. En la etapa SNA se construyeron redes filtradas con la información obtenida en la etapa anterior. A continuación se utilizaron dos algoritmos desarrollados en esta tesis, SLTA y TPA, para encontrar subcomunidades traslapadas. Los resultados muestran que SLTA logra un desempeño, en promedio, un 5% superior que el mejor algoritmo existente cuando es aplicado sobre una VCoP. Además, se encontró que la calidad de la estructura de sub-comunidades detectadas aumenta, en promedio, un 64% cuando el filtro semántico es aumentado. Con respecto a TPA, este algoritmo logra, en promedio, una medida de modularidad de 0.33 mientras que el mejor algoritmo existente 0.043 cuando es aplicado sobre una VCoI. Además la aplicación conjunta de nuestros algoritmos parece mostrar una forma de determinar el tipo de comunidad que se está analizando. Sin embargo, esto debe ser comprobado analizando más comunidades virtuales.

Magíster en Ciencias, Mención Computación / La recuperación de documentos consiste en, dada una colección de documentos y un patrón de consulta, obtener los documentos más relevantes para la consulta. Cuando los documentos están disponibles con anterioridad a las consultas, es posible construir un índice que permita, al momento de realizar las consultas, obtener documentos relevantes en tiempo razonable. Contar con índices que resuelvan un problema como éste es fundamental en áreas como recuperación de la información, minería de datos y bioinformática, entre otros. Cuando el texto que se indexa es lenguaje natural, la solución paradigmática corresponde al índice invertido. Sin embargo, los problemas de recuperación de documentos emergen también en escenarios en que el texto y los patrones de consulta pueden ser secuencias generales de caracteres, como lenguajes orientales, bases de datos multimedia, secuencias genómicas, etc. En estos escenarios los índices invertidos clásicos no se aplican con el mismo éxito. Si bien existen soluciones que requieren espacio lineal en este escenario de texto general, el espacio que utilizan es un problema importante: estas soluciones pueden utilizar más de 20 veces el espacio de la colección. Esta tesis presenta nuevos algoritmos y estructuras de datos para resolver algunos pro- blemas fundamentales para recuperación de documentos en colecciones de texto general, en espacio reducido. Más específicamente, se ofrecen nuevas soluciones al problema de document listing con frecuencias, y recuperación de los top-k documentos. Como subproducto, se de- sarrolló un nuevo esquema de compresión para bitmaps repetitivos que puede ser de interés por sí mismo. También se presentan implementaciones de las nuevas propuestas, y de trabajos relaciona- dos. Estudiamos nuestros algoritmos desde un punto de vista práctico y los comparamos con el estado del arte. Nuestros experimentos muestran que nuestras soluciones para document listing reducen el espacio de la mejor solución existente en un 40%, con un impacto mínimo en los tiempos de consulta. Para recuperación de los top-k documentos, también se redujo el espacio de la mejor solución existente en un 40% en la práctica, manteniendo los tiempos de consulta. Así mismo, mejoramos el tiempo de esta solución hasta en un factor de 100, a expensas de usar un bit extra por carácter. Nuestras soluciones son capaces de retornar los top-10 a top-100 documentos en el orden de milisegundos. Nuestras nuevas soluciones dominan la mayor parte del mapa espacio-tiempo, apuntando a ser el estándar contra el cual comparar la investigación futura.

No description available.

Uno de los procesos del diseño de circuitos integrados digitales es la preparación de la información de las máscaras, o MDP por sus siglas en inglés (Mask Data Preparation). La preparación de máscaras recibe el diseño de un circuito y lo convierte en una secuencia de instrucciones que son leídas por una máquina generadora de máscaras. Este proceso es realizado por una serie de algoritmos, ordenados en forma de pipeline, donde la salida de uno es la entrada del siguiente. Uno de los primeros algoritmos ejecutado es el llamado Windfrac, encargado de particionar, o fracturar, polígonos complejos en conjuntos de rectángulos y trapecios horizontales (cuyos lados paralelos son horizontales). Esta fractura inicial tiene gran importancia ya que, al reducir los distintos posibles polígonos de entrada a sólo rectángulos y trapecios horizontales, los algoritmos ejecutados después pueden ser simplificados e incluso tomar menos tiempo. En esta memoria se estudia y documenta el funcionamiento del algoritmo Windfrac, y se reimplementa de una forma más legible y mantenible. El estudio del algoritmo, el cual fue el tema central y lo que más tiempo ocupó, contempla la revisión de ciertos conceptos geométricos y de geometría computacional necesarios para la total comprensión de éste. Debido a que sólo existe un paper que explica un algoritmo parecido, toda la información acerca de cómo funciona Windfrac debió ser deducido a partir del código fuente mismo, cuya implementación era muy difícil de leer. El funcionamiento fue descifrado, principalmente, utilizando casos de prueba y depuradores para ir viendo, paso a paso, lo que el algoritmo hacía dado un polígono. Una vez entendido el funcionamiento completo de Windfrac se reimplementó teniendo en cuenta legibilidad, mantenibilidad y ciertos detalles para mejorar la calidad de los resultados. La legibilidad y mantenibilidad se lograron con una implementación modular, es decir, utilizando estructuras de datos más especializadas y separando funcionalidades en archivos y funciones. La mejora de la calidad se logró escribiendo código para manejar esos casos particulares. Finalmente, se realiza una discusión acerca del tema en estudio y sobre posibles mejoras que pueden ser llevadas a cabo en el futuro, las cuales podrían tener un gran impacto en el desempeño de la aplicación completa. Y, se concluye que el algoritmo fue satisfactoriamente comprendido y que su reimplementación soluciona los problemas de la implementación antigua.

Memoria para optar al título de Ingeniero Civil Electricista / El objetivo general de esta memoria es presentar una solución para detectar intentos de plagio de dominios de internet, mejorando los resultados entregados por un sistema pre existente. El trabajo fue realizado para una empresa que se encarga de registrar y proteger dominios de internet para firmas comerciales, con el problema de que el sistema utilizado en la protección entregaba cantidades excesivas de falsas alarmas. Este sistema resulta poco práctico en términos económicos, debido al costo que representa el descarte manual de este gran número de falsas alarmas. Se presentó una solución basada en el modelamiento del problema y aplicación de algoritmos clasificadores en trenables. El trabajo incluyó fases de modelamiento o traducción del problema, diseño, implementación, construcción de set de datos para entrenar y validar los algoritmos, y pruebas con datos reales para comparar los resultados de la solución propuesta con el sistema que se pretendía superar. El resultado es una solución que reduce la cantidad de alarmas reportadas diariamente a cerca de un tercio (y las falsas alarmas al 15%) de las obtenidas con el sistema antiguo y que no incrementa la cantidad de alarmas real es no reportadas. Se concluye que el objetivo perseguido se cumplió de modo exitoso, superando ampliamente los resultados del sistema antiguo y entregando a la empresa una alternativa más eficaz y rentable.

Ingeniero Civil en Computación / Ingeniero Civil Eléctrico / Uno de los desafíos importantes para la Robótica, es la capacidad del robot de manipular objetos de su entorno, ya sea para transportarlos u operarlos de alguna manera. Si bien esta capacidad está prácticamente resuelta en ambientes controlados, es un problema abierto en el caso de robots autónomos y ambientes no controlados, dado que la forma de los objetos, sus características físicas y las cualidades del efector del robot no están acotadas. Como segundo requisito, se busca además que las soluciones sean robustas y funcionen en tiempo real para aumentar las aplicaciones reales de la robótica. Una de las partes centrales de un algoritmo que permita manipular objetos es la detección de puntos de agarre. Esto corresponde a calcular los puntos del objeto por donde un robot debe tomarlo para que este no se caiga. Existen varios algoritmos que intentan dar solución a esta problemática pero solo funcionan para ciertas familias de objetos y en muchos casos toma demasiado tiempo realizar el cálculo. En esta memoria se implementó un algoritmo de manipulación de objetos basado en un método del estado del arte. El algoritmo permite manipular objetos en tiempos razonables y no esta restringido a una familia específica de objetos, aunque los objetos manipulables requieren de cierta simetría axial. El algoritmo se implementó en C++ en un robot PR2, un robot especialmente diseñado para investigación, usando Robot Operating System (ROS) como framework de desarrollo, lo que permitirá que este algoritmo sea usado fácilmente por otros equipos de investigación y robots en diferentes partes del mundo. El algoritmo implementado consta de una etapa de filtrado y segmentación de una nube de puntos, la determinación de los puntos de agarre, muestreo de poses de agarre, descarte de éstas por diferentes criterios, la asignación de puntaje a los agarres y finalmente la ejecución del mejor agarre seleccionado. Los experimentos muestran que el algoritmo permite tomar objetos en simulación y en un robot PR2 real.

En la actualidad, los sistemas de bases de datos son considerados como un componente fundamental para casi cualquier organización, ya que estos sistemas permiten acceder a información puntual de forma segura y rápida, lo cual es clave para una correcta toma de decisiones y una adecuada atención a los usuarios. Sin embargo, debido al rápido desarrollo de las tecnologías de información, cada vez más sistemas de información generan enormes cantidades de datos y necesitan lidiar con estos de forma eficiente y, dado que las bases de datos relacionales juegan un rol vital en muchos sistemas de información, el rendimiento de estos mismos sistemas depende directamente del rendimiento del sistema de base de datos. En ese sentido, se considera crítico aplicar diversos métodos para optimizar el rendimiento del sistema de base de datos. Uno de estos métodos es la asignación de tablas, el cual consiste en distribuir de manera adecuada a las tablas de una base de datos en los dispositivos de almacenamiento disponibles. Dicho método es útil porque permite mejorar el rendimiento del sistema de base de datos y aprovechar de mejor manera los recursos de hardware disponibles. Sin embargo, muchas veces esta tarea se realiza considerando sólo algunas variables o factores al momento de tomar una decisión. Asimismo, existe una ausencia en el empleo de esta técnica por parte de muchos sistemas modernos. Esto, sumado al hecho de que la asignación suele realizarse de manera manual y también a que los estudios presentes en el estado del arte utilizan, en su gran mayoría, soluciones basadas en heurísticas o cálculos simples, las cuales pueden no brindar buenos resultados, conducen a que se realice una deficiente asignación de tablas a unidades de almacenamiento. Esta situación provoca un bajo rendimiento del sistema de base de datos, un deficiente funcionamiento de la entrada y salida de disco y que las tareas de administración sean más propensas a errores. Ante esta situación, se torna necesario el uso de métodos que automaticen y optimicen esta tarea, en ese sentido, el presente trabajo de tesis propone el diseño y la implementación de un algoritmo memético que permita optimizar la asignación de tablas a unidades de almacenamiento de bases de datos relacionales.