Memoria para optar al título de Ingeniero Civil Industrial / Memoria para optar al título de Ingeniero Civil en Computación / El análisis neuroescritural (o grafológico) corresponde al proceso de estudio mediante el cual un perito en la materia detecta una serie de características de un texto manuscrito y las interpreta para inferir características de la personalidad del autor del mismo. El presente trabajo busca automatizar el proceso de un análisis neuroescritural para disminuir el tiempo que se requiere para llevarlo a cabo. Más concretamente, el objetivo general de este proyecto es: detectar automáticamente patrones grafológicos a partir de imágenes de texto manuscrito, mediante un sistema computacional usando técnicas de procesamiento de imágenes. Para abordar este desafío, se propone una primera etapa de estudio de la situación actual y de análisis de los requisitos que debe satisfacer el sistema. Posteriormente, se realiza un diseño del mismo basado en tres componentes principales: un sistema de backend para realizar el procesamiento de imágenes; una plataforma web de interacción con el backend, para ejecutar el análisis e incluir información adicional; y otro sistema web para proveer acceso a clientes que soliciten la realización de un análisis. A continuación, se construye un conjunto de algoritmos capaces de detectar características grafológicas y se implementan de acuerdo al diseño propuesto utilizando la biblioteca OpenCV en el backend. Mientras que para el frontend se utiliza un framework de desarrollo web siguiendo el paradigma MVC. Como resultado de esta fase, se logra construir un sistema funcional en sus tres componentes y se procede a evaluarlo de acuerdo a la calidad de las detecciones realizadas. Con muestras analizadas manualmente por un experto, se evalúa la calidad de la detección automática de 15 patrones distintos, obteniéndose, para cada algoritmo, clasificaciones acertadas en al menos un 86 % de los casos analizados. Sin embargo, debido a sesgos detec- tados en los datos de las muestras analizadas, se requerirá obtener más datos para asegurar la efectividad de todos los algoritmos propuestos en cualquier escenario. Por último, se puede concluir que el sistema genera una precisa clasificación agregada a nivel de competencias, coincidiendo totalmente con el análisis realizado por el experto neuroescritural en 14 de los 15 casos de evaluación.

Ingeniero Civil en Computación / El presente trabajo tiene como objetivo desarrollar un algoritmo para enfrentar la resolución de múltiples escenarios de una licitación combinatorial El trabajo se concretó con la implementación de un aplicación que apoya la decisión de determinar las ofertas ganadoras para una licitación de servicios de alimentación de la Junta Nacional de Auxilio Escolar y Becas (JUNAEB). Esta licitación tiene un costo aproximado a los 400 millones de dólares y bajo los términos de la compra, el país se divide en unidades territoriales (UT). Los participantes pueden presentar ofertas por grupos de una o más UT, entregando precios por adjudicarse el conjunto completo. Este diseño permite incorporar economías de escala y ventajas logísticas obteniéndose mejores precios, pero le entrega un carácter combinatorial al proceso, debiendo seleccionarse las ofertas ganadoras entre decenas de miles de ofertas presentadas. El problema de encontrar las ofertas ganadoras se abordó a través de la construcción de un modelo de programación lineal entera mixta. Para resolverlo, se construyó un software que generara instancias del modelo y utilizando las librerías del solver comercial IBM CPLEX se determinan las ofertas ganadoras, presentándose los resultados al usuario. Sin embargo, en la decisión no sólo se deben consideran los costos de las ofertas sino que también deben incorporarse otros criterios: opciones del servicio comprado, límites de concentración de mercado, consideración del desempeño técnico de las empresas oferentes, entre otros. Por lo tanto, la decisión de compra es multi-criterio dependiendo de los diferentes conjuntos de parámetros u opciones consideradas (escenario). Estas combinaciones de criterios se abordaron generando cientos de problemas, que se pueden resolver en forma paralela en diferentes computadores para luego reunir los resultados, presentarlos al usuario para que los compare y pueda tomar la decisión final de adjudicación. El diseño del modelo, la secuencia de resolución, así como el uso de técnicas de incorporación de cortes y uso de soluciones iniciales permite resolver todos los problemas en menos de dos días. La solución tecnológica desarrollada ha permitido determinar las ofertas ganadoras de licitaciones que ya suman más de 2 mil millones de dólares. También, ha permitido ahorrar recursos que se utilizan en mejorar la calidad de las prestaciones entregadas y proveer una mayor cantidad de servicios de alimentación a los establecimientos educacionales.

Ingeniero Civil en Computación / Existen aplicaciones en donde una triangulación de buena calidad es esencial, entendiéndose por calidad que el ángulo mínimo de cada triángulo esté acotado inferiormente. El método de elementos finitos corresponde a una de las aplicaciones más importantes. Los algoritmos de refinamiento de triangulaciones eliminan aquellos triángulos que poseen algún ángulo interior menor a un umbral deseado, mediante la inserción de nuevos puntos en la triangulación original. Un subconjunto de estos algoritmos, que reciben el nombre de algoritmos de refinamiento Delaunay, toman como punto de partida una triangulación de Delaunay restringida de los datos de entrada, y mediante inserciones Delaunay de los nuevos vértices mantienen la condición de Delaunay tras cada inserción. Estos algoritmos son los más utilizados para obtener triangulaciones de calidad. En esta memoria se desarrolló un nuevo software de comparación de algoritmos de refinamiento llamado Compare2DMesh, el cual permite: hacer comparaciones experimentales rigurosas de los diferentes algoritmos de refinamiento Delaunay, manejar cualquier tamaño de mallas y geometrías complejas, visualizar cada inserción de un nuevo vértice mientras la triangulación está siendo refinada, refinar sin visualización del progreso, y configurar y ejecutar variaciones de los algoritmos. Este software usó como base un prototipo llamado MeshSuite. Para validar el desempeño de Compare2DMesh se realizaron experimentos de comparación entre los algoritmos implementados, y también se comparó con otros software de refinamiento. Se concluyó que Compare2DMesh supera considerablemente el rendimiento del prototipo del que fue originado, y que procesa mallas grandes en tiempos razonables, lo que permite que Compare2DMesh pueda ser utilizado para los fines de probar, comparar y afinar algoritmos.

Ingeniero Civil en Computación / En este trabajo se discute un sistema experimental para resolver ecuaciones diferenciales parciales (EDP) elípticas o parabólicas sobre dominios en 2-D mediante el método de elementos finitos (MEF). La herramienta combina algoritmos de refinamiento y desrefinamiento de triangulaciones conformes sobre dominios generales con bordes curvos en las fronteras e interfaces de medios; el MEF, usando elementos lineales; una estructura de datos adecuada; el uso de estimadores del error cometido en la resolución numérica; una interfaz gráfica sobre XWindows y un lenguaje declarativo para la definición de los problemas. La herramienta fue desarrollada en forma modular, para permitir la incorporación de nuevas opciones, como elementos de grado mayor en el uso del MEF, y utiliza librerías externas, como son, Sparse y SuperLU para la resolución de los sistemas de ecuaciones poco densos, pdraw para visualización de resultados en 3D y GLADE para construcción de la interfaz gráfica; todas estas herramientas corresponden a software de código abierto. La herramienta tiene un uso potencial en una amplia gama de aplicaciones, por ejemplo en cálculo estructural, y mecánica de fluidos y permite al usuario manejar en forma flexible la adaptabilidad, pudiendo definir o modificar a través de la interfaz gráfica, las triangulaciones, nodos, conexiones, moléculas, condiciones de borde y lados curvos. Esta interfaz, también permite al usuario definir o modificar tanto el problema que se desea resolver, como las regiones en las que el usuario desea dirigir ya sea el refinamiento como el desrefinamiento de la triangulación. Los estimadores de error utilizados permiten crear indicadores que dirigen el refinamiento y desrefinamiento en forma adaptativa, para mejorar la solución con la menor interacción del usuario. Con ello solo se debe definir una triangulación inicial conforme que representa una malla gruesa y luego por medio de los mecanismos de refinamiento explícito o los procesos adaptativo, obtener una triangulación que provea de una malla mas fina, que permitirá obtener una solución de mejor calidad. Se ilustra el uso del sistema con problemas de prueba, de solución conocida; se muestra la imagen de la malla inicial del dominio y de algunas iteraciones, la malla y solución asociada. Se concluye que esta herramienta constituye un software general, flexible y sencillo de usar para resolver problemas de EDP sobre dominios en 2-D generales.

Doctor en Ciencias, Mención Computación / La generación y refinamiento de mallas son temas de gran interés en aplicaciones tales como simulación de fenómenos físicos mediante el uso de los métodos de elementos finitos, en aplicaciones CAD, modelado geométrico y mallas geométricas. Una malla es un conjunto de elementos geométricos (polígonos o poliedros) que no se superponen, los cuales están conectados por medio de vértices, aristas y caras, que se usan para aproximar dominios geométricos. Los algoritmos de refinamiento producen mallas cada vez más finas para discretizar dominios complejos, representar objetos con topologías arbitrarias y también superficies con formas complejas. En esta tesis se estudió la paralelización de algoritmos de refinamiento basados en el concepto de Lepp para sistemas multicore (multinúcleo) y sistemas distribuidos. Se consideraron dos problemas: (1) refinamiento de mallas de buena calidad: aquí dada una malla de entrada de buena calidad, ésta es iterativa y localmente refinada (de acuerdo a un requerimiento externo a la aplicación) para producir una malla final de calidad análoga a la inicial; (2) refinamiento de triangulaciones Delaunay de mala calidad, donde dada una triangulación Delaunay de entrada de mala calidad (con una geometría dada), deseamos producir una triangulación Delaunay de buena calidad y de tamaño óptimo. Algoritmos basados en el concepto de Lepp son algoritmos refinamiento por la arista más larga mejorados donde el refinamiento de cualquier triángulo t tiene asociado un Lepp(t). En el contexto de los sistemas multicore se desarrollaron algoritmos Lepp-bisección multicore eficientes y escalables para el refinamiento de mallas de 2 y 3 dimensiones. También se desarrolló un algoritmo Lepp-Delaunay multicore para la generación de mallas Delaunay de buena calidad. En el contexto de los sistemas de memoria distribuida se desarrolló un algoritmo Lepp-bisección distribuido para el refinamiento de mallas de 2 dimensiones donde la malla inicial es subdividida dentro de un conjunto de submallas (o subparticiones), las cuales son distribuidas entre los procesadores. También se desarrolló una estrategia eficiente para garantizar que se obtiene una malla final válida (conforme) en las interfaces de submallas vecinas. Se realizaron evaluaciones empíricas de los algoritmos paralelos sobre arquitecturas multicore y sistemas de memoria distribuida que muestran que los algoritmos paralelos tienen buen desempeño.

Dados los avances en la tecnología, la astronomía es capaz de recolectar del orden de terabytes de datos por noche. El análisis manual de ésta es prácticamente imposible, por lo que es constante la necesidad de nuevos y mejores algoritmos para realizar análisis automático. Por otro lado, la computación paralela provee herramientas para realizar análisis de datos masivos, las que incrementan la capacidad total de procesamiento y disminuyen el tiempo requerido. Existe un software para la búsqueda de cúmulos de galaxias, el cual funciona de forma secuencial. Hacer que este software funcione en forma paralela sería de gran utilidad, dada la cantidad de datos que existen y existirán para analizar. El objetivo de esta memoria es diseñar e implementar una solución computacional que permita efectuar la detección de cúmulos de galaxias en forma paralela. La paralelización del algoritmo se hizo sobre el framework Hadoop, utilizando la herramienta Streaming con el lenguaje Python para el desarrollo del software. Se construyó una aplicación que divide los datos de entrada de forma inteligente, ejecuta el algoritmo de detección de cúmulos de galaxias en varias máquinas de forma paralela, y re ensambla los resultados parciales obtenidos. Se estudiaron estrategias para el particionamiento de los datos, utilizando celdas con distintas geometrías. También se estudiaron e implementaron estrategias para el re ensamblado de los resultados. En base a conocimientos astronómicos y experimentación se determinó la utilidad, dado el contexto, de cada estrategia, y los valores límites para sus parámetros. Los resultados son los siguientes: (1) un software paralelo para la detección de cúmulos de galaxias; (2) al correr el programa paralelo con dos particiones, el tiempo de ejecución se reduce a la mitad; (3) el software secuencial de detección de cúmulos se observa altamente dependiente de las particiones utilizadas, encontrándose para una partición de 2 celdas sólo un 11% de los cúmulos que se detectaban en la versión secuencial. Como trabajo futuro se propone: (1) modificar el software secuencial de búsqueda de cúmulos de galaxias para que detecte cúmulos sin miembros repetidos; (2) ejecutar este software en un clúster de computadores o con cloud computing, para medir las mejoras en tiempo; (3) la ejecución de este software con sets de datos más grandes, para medir la escalabilidad de éste; (4) crear una partición ad-hoc al set de datos.

El uso de elementos finitos para analizar fenómenos físicos modelados por ecuaciones diferenciales parciales requiere de una discretización del dominio, como lo son las triangulaciones en dos dimensiones. En este contexto se distinguen tres problemas: generar una triangulación a partir de un conjunto de vértices y segmentos, refinar una malla y mejorar la calidad de una malla. Los algoritmos que refinan triangulaciones Delaunay en general se basan en seleccionar nuevos puntos y realizar una inserción Delaunay de éstos. Los criterios usados para comparar algoritmos se basan en la cantidad de inserciones que realizan, la cantidad de triángulos generados y el tiempo de ejecución. Sin embargo, es difícil encontrar implementaciones que realicen las comparaciones bajo un mismo ambiente y condiciones. En esta memoria se ha diseñado un marco de experimentación que permite investigar y comparar algoritmos de refinamiento Delaunay dentro de un mismo ambiente. Se propone un proceso de refinamiento genérico y se desarrolla una herramienta que, haciendo uso de patrones de diseño de programación con orientación a objetos, implementa el proceso con la flexibilidad de poder extender la herramienta con nuevos algoritmos de forma simple. Se provee una interfaz gráfica que permite seguir el proceso de refinamiento en una forma clara y didáctica. La herramienta genera resultados comparables con los resultados de Triangle, una herramienta de refinamiento Delaunay rápida y eficiente, pero limitada en su extensibilidad y usabilidad. La extensibilidad de la herramienta se puso a prueba implementando los siguientes criterios de selección de puntos asociados a triángulos de mala calidad: Circuncentro, Off-Center, Lepp - Punto Medio, Lepp - Centroide y Lepp - Bisección (No Delaunay). Se evalúan también técnicas de priorización en el procesamiento de los triángulos de mala calidad. Se experimentó con un algoritmo nuevo, Lepp -Circuncentro, el cual presentó un buen rendimiento con las mallas estudiadas, alcanzando en algunos casos una exigencia de 37º como ángulo interior mínimo. Se estudiaron criterios de priorización en la selección de triángulos de mala calidad, concluyendo que el comportamiento de los algoritmos de tipo Lepp es independiente del uso de técnicas de priorización. En cambio, el algoritmo Off-Center aumenta considerablemente el número de puntos insertados si no se utiliza un orden de procesamiento adecuado.

Ingeniero Civil en Computación / La resolución de diversos problemas en ciencia e ingeniería, requiere el apoyo de soluciones y herramientas computacionales que permitan representar, visualizar y modelar sus objetos de estudio, como superficies, terrenos o células. Una forma de representar estos objetos es mediante el uso de mallas geométricas, sobre las cuales se realizan operaciones y simulaciones para modelar los problemas inherentes a cada disciplina. Uno de los principales problemas asociados a trabajar con mallas geométricas, es el tiempo que demoran en ser procesadas. Con el auge de las tarjetas y procesadores gráficos (GPU), se han investigado nuevas técnicas que permitan usar el poder de computo de estas unidades, para desarrollar e implementar estos algoritmos. Actualmente se cuenta con una librería (llamada Cleap), la cual permite realizar la operación de triangulación de Delaunay en Paralelo usando GPU s de marca Nvidia. A ella, se desea integrar otros algoritmos que trabajen con mallas geométricas, como algoritmos de suavizado y simplificación, además de comparar su rendimiento y calidad con otras implementaciones ya existentes. En este trabajo, se investigó sobre algoritmos de suavizado, triangulación y simplificación de mallas geométricas, y luego se implementaron versiones de los dos primeros, los cuales fueron integrados en Cleap, y se comparó el rendimiento y calidad de sus soluciones. Con respecto al algoritmo de simplificación, solo se llegó hasta la fase de investigación teórica, pero se obtuvo la información y conocimientos necesarios para implementar e integrar una versión de este algoritmo. Los resultados muestran que el uso de la GPU permite reducir considerablemente los tiempos de ejecución, cuando se trabaja con mallas de gran tamaño, en comparación a sus contrapartes secuenciales, y que la calidad de sus resultados es similar o incluso mejor a la de las implementaciones conocidas actualmente. Estos resultados también muestran que no siempre lo que se espera teóricamente, ocurre en la práctica, debido a problemas y fallos que ocurren al realizar cálculos con error asociado, y detalles particulares asociados a una arquitectura o plataforma determinada.

Magíster en Ciencias, Mención Computación / Este trabajo de tesis está dedicado al diseño e implementación de algoritmos aproximados que permiten explorar las mejores soluciones para el problema de Clustering Balanceado, el cual consiste en dividir un conjunto de n puntos en k clusters tal que cada cluster tenga como m ́ınimo ⌊ n ⌋ puntos, k y éstos deben estar lo más cercano posible al centroide de cada cluster. Estudiamos los algoritmos existentes para este problema y nuestro análisis muestra que éstos podrían fallar en entregar un resultado óptimo por la ausencia de la evaluación de los resultados en cada iteración del algoritmo. Entonces, recurrimos al concepto de Particles Swarms, que fue introducido inicialmente para simular el comportamiento social humano y que permite explorar todas las posibles soluciones de manera que se aproximen a la óptima rápidamente. Proponemos cuatro algoritmos basado en Particle Swarm Optimization (PSO): PSO-Hu ́ngaro, PSO-Gale-Shapley, PSO-Aborci ́on-Punto-Cercano y PSO-Convex-Hull, que aprovechan la característica de la generación aleatoria de los centroides por el algoritmo PSO, para asignar los puntos a estos centroides, logrando una solución más aproximada a la óptima. Evaluamos estos cuatro algoritmos con conjuntos de datos distribuidos en forma uniforme y no uniforme. Se encontró que para los conjuntos de datos distribuidos no uniformemente, es impredecible determinar cuál de los cuatro algoritmos propuestos llegaría a tener un mejor resultado de acuerdo al conjunto de métricas (intra-cluster-distancia, índice Davies-Doublin e índice Dunn). Por eso, nos concentramos con profundidad en el comportamiento de ellos para los conjuntos de datos distribuidos en forma uniforme. Durante el proceso de evaluación se descubrió que la formación de los clusters balanceados de los algoritmos PSO-Absorcion-Puntos-Importantes y PSO-Convex-Hull depende fuertemente del orden con que los centroides comienzan a absorber los puntos más cercanos. En cambio, los algoritmos PSO-Hungaro y PSO-Gale-Shapley solamente dependen de los centroides generados y no del orden de los clusters a crear. Se pudo concluir que el algoritmo PSO-Gale-Shapley presenta el rendimiento menos bueno para la creación de clusters balanceados, mientras que el algoritmo PSO-Hungaro presenta el rendimiento más eficiente para lograr el resultado esperado. Éste último está limitado al tamaño de los datos y la forma de distribución. Se descubrió finalmente que, para los conjuntos de datos de tamaños grandes, independiente de la forma de distribución, el algoritmo PSO-Convex-Hull supera a los demás, entregando mejor resultado según las métricas usadas.

Magíster en Ciencias, Mención Computación / Ingeniero Civil Matemático / Una red Booleana es un modelo de redes en el cual, cada nodo o elemento de la red tiene asociado una función Booleana que determina el estado del nodo respectivo, y de esta forma la evolución de la red en el tiempo. Los puntos fijos de una red Booleana, esto es, estados particulares de la red que permanecen constantes en el tiempo, han ganado importancia, por ejemplo, en el contexto de redes de regulación génica, donde los puntos fijos tienen un correlato biológico. Para cada red finita y estado inicial posible, dentro de una cantidad finita de actualizaciones de la red, los estados de la red alcanzarán un punto fijo o un ciclo límite, la cual es una secuencia de estados de la red que se repiten a lo largo del tiempo. Puntos fijos y ciclos límites son denominados atractores de la red. En este trabajo nos concentramos en estudiar ciertos aspectos de los atractores de redes Booleanas, incluyendo aspectos computacionales, caracterizaciones, entre otros, utilizando la noción de "filtro'' de una red. Un filtro es un procedimiento consistente en aplicar de forma iterativa transformaciones a una red, cada una de las cuales simula con dinámica paralela cierto modo de actualización, produciendo una nueva red cuyas propiedades y dinámica pueden ser relacionadas con la red inicial. Se ha mostrado que estos filtros pueden ser muy útiles, dado que filtros asociados a actualizaciones secuenciales pueden entregar información eficientemente sobre los puntos fijos de una red (Goles y Salinas 2010). Nuestro análisis se restringe a redes Booleanas disyuntivas, lo cual permite concentrarse solo en la topología de la red. Nos concentramos además en esquemas de actualización bloque-secuencial, los cuales son una generalización de los esquemas paralelo y secuencial. Los principales resultados de este trabajo establecen cotas polinomiales para la complejidad de tiempo de un filtro, así como condiciones sobre la red y esquema de entrada que aseguran ciertas propiedades en la red de salida, incluyendo la remoción de ciclos límites. Los resultados obtenidos hacen uso de teoría de matrices positivas, y fueron formulados con la ayuda de simulaciones computacionales ejecutadas con una aplicación desarrollada para este fin.