El desarrollo de sistemas de software es una disciplina relativamente joven que no ha alcanzado el nivel de madurez de otras ingenierías. Como consecuencia, los proyectos de desarrollo resultan frecuentemente en procesos inestables e impredecibles. Las Ciencias de la Computación han contribuido con conocimiento teórico, pero ciertas areas necesitan una mayor evolución para poder generar nuevas metodologías de trabajo. Uno de los aspectos más críticos es, dado el conjunto de metodologías existentes, determinar cuál corresponde utilizar para la construcción de un producto específico. Esta decisión involucra elegir, entre otras cosas, cuales son los pasos a seguir y que se espera lograr al finalizar cada una de las distintas etapas. El hecho de definir un proceso de producción de software nos permite repetir los beneficios de un proceso estandarizado. Sin embargo, hay que tener presente que es un proceso que (como toda actividad ingenieril) necesita de técnicas y metodologías precisas y bien definidas, y todavía no se ha logrado caracterizarlas por completo por lo novedoso de la disciplina. Este trabajo, en primer término, analiza y compara metodologías de desarrollo de sistemas e investiga las distintas areas de las Ciencias de la Computación sobre las cuales se fundamentan. La utilización de una metodología para el desarrollo de sistemas es la base para poder realizar la planificación y el control de proyectos. Asociados a estas tareas se encuentran los procesos de medición que se aplican tanto al producto como a los pasos para su construcción. Para cada una de las metodologías aplicadas, el trabajo profundiza sobre las métricas específicas existentes. / The software systems development is a relatively young discipline, and has not reached the same level of maturity of other engineering disciplines. As a consequence, the development projects result in unstable and unpredictable processes. Computer Sciences have contributed with theoretical knowledge, but certain areas need a grater evolution to generate new work methodologies. One of the more critical aspects is, given the set of existing development methodologies, to determine which of them to use to construct a specific product. This decision involves the choice, among other things, of what are the steps to follow and what is the expected result at the end of each step. The fact of defining a software production process makes possible to repeat the benefits of a standardized process. However, it is necessary to take into account that it is a process that (as every engineering activity) needs precise and well defined techniques and methodologies, and they are not completely characterized because of the discipline novelty. At a first stage, this work analyzes and compares systems development methodologies and investigates the different Computer Sciences areas on which they are foundated. The use of a systems development methodology is the base to carry out the projects planning and control. Associated with these tasks, there are measurement processes that apply to product as well as to the steps for their construction. For each of the applied methodologies, this work goes into existing specific metrics in depth.

El objetivo general de esta tesis fue desarrollar técnicas meta-heurísticas híbridas para el tratamiento de problemas NP-Hard relacionados con el problema de la red de tránsito (Transit Network Problem: TNP). Estas técnicas están orientadas, en particular, a las dos etapas más importantes del TNP: el diseño y la planificación (Transit Network Design and Scheduling Problem: TNDSP) de la red. El objetivo principal fue proveer una herramienta automatizada para la creación tanto de las rutas de las líneas de la red de tránsito como de la frecuencia de los móviles. Como resultado colateral de esta tesis se logró además subsanar una deficiencia de los trabajos existentes sobre TNP: su incapacidad para obtener resultados que reflejen la dinámica de las variables que dependen de los tiempos consumidos por el usuario en su espera, acceso y viaje dentro de la red. Esta tesis analiza dichas falencias y presenta como solución la posibilidad de incorporar un elemento dinámico dentro de la resolución del TNDSP. De este modo, se han podido obtener resultados realistas tanto desde el punto de vista del operador del servicio como así también del cliente. En base a nuestras investigaciones, se obtuvo un algoritmo híbrido evolutivo dinámico multi-objetivo de dos etapas que tiene en cuenta tanto al operador como a los clientes de la red. La primera es una etapa de inicialización de distancias y rutas entre paradas a través de un novedoso procedimiento GRASP (Greedy Randomized Adaptive Search Procedure). La segunda es una etapa que implementa un nuevo algoritmo evolutivo que contiene un procedimiento de simulación para el cálculo de la función de aptitud (fitness) de los individuos. Finalmente, se estudiaron algunas ciudades hipotéticas estableciendo la mejor configuración de parámetros para las fases del algoritmo híbrido y se analizó un caso real utilizado en la literatura para comparar nuestra metodología con los procedimientos más conocidos sobre el tema, mostrando resultados altamente satisfactorios. / The general purpose of this thesis was to develop meta-heuristic hybrid techniques for the treatment of NP-hard problems related to the Transit Network Problem (TNP). These techniques are particularly oriented to the most important TNP stages: the design and planning of the network (Transit Network Design and Scheduling Problem: TNDSP). The main goal was to provide a tool for the creation of both the routes for the transit network lines and the mobile frequency. Also, the work performed in this thesis contributes to eliminate a deficiency in the existing work about TNP: the inability to yield results that reflect the dynamics of the variables that depend on the time taken by the users while they are waiting, accessing and tripping within the network. This thesis analyses this dearth and proposes as a solution the possibility of incorporating a dynamic element to the manner of solving the TNDSP. In this way, realistic results could be obtained from the viewpoint of both the service operator and the client as well. On the basis of our research, a hybrid dynamic two-stage evolutionary algorithm was obtained. In the network, it takes into account both the operator and the clients as well. The first stage is an initialization of the distances and routes between stops through a GRASP (Greedy Randomized Adaptive Search Procedure). The second stage implements an evolutionary algorithm that contains a simulation procedure for the calculation of the individuals fitness. Finally, some hypothetical cities were studied by establishing the best parameter configuration for the phases of the hybrid algorithm. A real case, which is classic in the literature, was analyzed in order to compare our method against the well-known approaches used to solve these problems. The results of this analysis were highly satisfactory.

Ingeniero Civil Matemático / La computación distribuida, rama de las ciencias de la computación, se focaliza en estu- diar sistemas distribuidos, tales como internet, redes sociales o protocolos de mensajería. La información se encuentra distribuida entre las distintas entidades que conforman el sistema y el objetivo último es resolver algún problema global. Para ello las distintas entidades se comunican mediante los canales de la red hasta que encuentran la solución. Esta memoria comienza estudiando el problema de la degenerancia de un grafo en los modelos de computación distribuida UCAST y BCAST, donde la degenerancia de un grafo G se define como el máximo grado mínimo de un subgrafo F de G. Los modelos distribuidos UCAST y BCAST corresponden a redes completas de n individuos, los cuales se comunican de manera síncrona por los canales de la red en rondas. En el primer caso, cada individuo por ronda puede enviar diferentes mensajes por cada uno de sus canales. En el segundo caso, cada individuo por ronda envía a través de sus canales el mismo mensaje. En general, se suele decir que BCAST es una restricción de UCAST. Primero, se construye un protocolo aleatorio en el modelo UCAST que calcula una (1 + ε)- aproximación de la degenerancia en O(log n) rondas con mensajes de largo O(log n). En el modelo BCAST se demuestra que el problema de calcular la degenerancia es difícil en 1 ronda. Más específicamente, se demuestra que todo protocolo aleatorio de 1 ronda que calcule exactamente la degenerancia debe enviar un mensaje de largo Ω(n). En el mismo modelo, se construye un protocolo aleatorio de 2 rondas con mensajes de largo O(log 2 n) que calcula una (1 + ε)-aproximación de la degenerancia para grafos α-densos. Finalmente, se construye un protocolo determinista que calcula una (2 + ε)-aproximación de la degenerancia en O(log n) rondas con mensajes de largo O(log n). Como segunda parte de este trabajo, y motivado por el protocolo en BCAST que calcula una (2 + ε)-aproximación de la degenerancia, se estudia la siguiente dinámica sobre grafos: Durante cada iteración, eliminar todos los vértices que tengan grado a lo más el grado prome- dio del grafo +1. Se conjetura que para todo grafo G de n vértices la dinámica toma O(log n) iteraciones en vaciar el grafo. Se aborda el problema estudiando clases de grafos tales como: bosques, grafos planares, grafos con degenerancia acotada y grafos unión disjunta de cliques. Finalmente, se estudian diversos problemas en el modelo BCAST. Se comienza estudiando el problema de calcular el conjunto independiente maximal con un vértice fijo. Se prueba que el problema es difícil en 1 ronda y luego se contruye un protocolo que en O(log n) rondas, usando mensaje de largo O(log n), calcula el conjunto independiente. Se estudia también el problema de calcular el número cromático de un grafo. Se prueba que el problema resulta difícil en 1 ronda. Concluyendo el capítulo, se estudian los problemas de encontrar conjuntos dominantes de tamaño k y conjuntos -dominantes de tamaño k, en ambos casos se demuestra que los problemas son difíciles en 1 ronda. / Este trabajo ha sido parcialmente financiado por Proyecto Fondecyt 1130061

En muchas aplicaciones de búsqueda de información se necesita una estructura eficiente que pueda almacenar y leer datos concurrentemente bajo el supuesto de que la distribución del acceso a dichos datos no es uniforme. Ejemplos son las memorias caché para aplicaciones Web o las mismas bases de datos. Existen soluciones para esto y cada una con un rendimiento diferente bajo ciertos entornos. Sin embargo, estas soluciones suelen estar basadas en un mismo tipo de árboles de búsqueda, los autobalanceados, por lo que tienen ciertas limitaciones en términos de concurrencia. En el presente trabajo se desarrollará una nueva estructura concurrente y escalable, la cual se basará en el árbol no autobalanceado de Van Emde Boas [1], y se realizarán experimentos para determinar su rendimiento en comparación con el de otras estructuras comúnmente usadas. Finalmente, se determinar´a bajo qué circunstancias es útil. Esta estructura la llamaremos UHTree (Unicursal Hexagram Tree). / Tesis

En este proyecto de fin de carrera se ha escogido abarcar el tema de Turismo Literario, resaltando principalmente la integración de una herramienta que ha existido durante años, el libro, con las nuevas tecnologías de Reconocimiento de Entidades Mencionadas (REM). Se propone implementar un método de extracción de lugares que se encargue de procesar las obras literarias con la finalidad de identificar los nombres de los lugares mencionados en dichos textos; para que éstos, finalmente, sean validados en el mundo real con el apoyo de una librería de información geográfica. Con el método implementado se va a obtener información, la cual puede ser utilizada para la construcción de herramientas que permitan difundir y aprovechar el Turismo Literario. Esta clase de turismo busca difundir los lugares reales que son mencionados en las obras literarias Estos escenarios pueden ser parques, restaurantes, pasajes, avenidas, entre otros lugares. / Tesis

El objetivo general del trabajo realizado fue desarrollar un sistema genérico de seguridad y privacidad de datos, que pudiera ser aplicable a un amplio espectro de aplicaciones colaborativas móviles. Se logró desarrollar un sistema de control de acceso a archivos basado en roles, usando herramientas de criptografía, tomando en cuenta los objetivos de seguridad, así como las características y restricciones propias de los sistemas colaborativos móviles. El sistema es capaz de mantener la privacidad, integridad y autenticación de los documentos (en realidad de cualquier archivo) usando un sistema de permisos de escritura y lectura. La privacidad de los documentos se asegura haciendo uso de la criptografía simétrica; la integridad y autenticación se obtiene mediante el uso de códigos de autenticación de mensajes basados en hash. Como resultado final se obtuvo una interfaz de servicios que puede ser reutilizada por distintas aplicaciones móviles, así como una aplicación gráfica que permite que los usuarios de un sistema colaborativo protejan y compartan sus archivos. El sistema funciona sobre PDA’s y Notebooks, con un desempeño adecuado para los usuarios y acorde a la capacidad de los dispositivos empleados.

La evaluación de yacimientos mineros tiene por objetivo estimar, con el menor error posible, la calidad y cantidad de un recurso mineral, que tiene potencial de ser explotado. Una de las principales herramientas utilizadas es la Geoestadística, la cual pone énfasis en el contexto geológico y la relación espacial entre los datos a estudiar. Los métodos de estimación tradicionales, llamados Kriging, calculan el mejor estimador lineal insesgado de una variable en base a los valores de datos vecinos. Para representar de mejor manera la variabilidad espacial de los datos, se recurre a la Simulación Convencional, que consiste en añadir un factor aleatorio a Kriging para obtener una distribución de escenarios, que sirven como medida de la respuesta ante la incerteza. El inconveniente de esta técnica es que no permite correlacionar diversos puntos al mismo tiempo, sólo se pueden correlacionar dos puntos a la vez (se basa en la covarianza de 2 puntos). Este hecho representa una potencial pérdida de información en la construcción del modelo que se utilizará para realizar estimaciones o simulaciones. Al correlacionar dos puntos a la vez, se induce una suavización sobre las estimaciones, lo cual puede entregar resultados sobreestimados o subestimados. Para solucionar el problema anterior, se propone utilizar métodos que contemplan estadísticas de múltiples puntos, representadas por patrones. Se espera que la utilización de patrones junto a un método de simulación no convencional llamado Recocido Simulado (Simulated Annealing) puedan tener un mejor desempeño al evaluar un proceso que la simulación convencional. Los principales problemas del método propuesto son el tiempo de cálculo del Recocido Simulado y el manejo de patrones grandes. Se optó por resolver el primero de ellos y dejar abierta la puerta para posibles trabajos a futuro en la optimización de las estructuras de datos para el manejo de patrones grandes. El tiempo de cálculo del Recocido Simulado aumenta exponencialmente al incrementar el tamaño de los patrones a estudiar. Para solucionar esto, se realizó una implementación utilizando múltiples procesos, configurados según una técnica llamada Computación Especulativa, la cual permite realizar varios pasos de la simulación a la vez. Se estudió el speedup teórico de la paralelización y se realizaron pruebas numéricas, las cuales entregaron resultados satisfactorios en tiempo y en calidad de la imagen simulada.

En Computación Gráfica uno de los conceptos más importantes es el \emph{Rendering}, definido como el proceso que a partir de los datos de una escena tridimensional genera una imagen en una ventana de visualización en 2 dimensiones. El rendering siempre se ha enfocado en generar imágenes fotorrealistas, aunque para diversas aplicaciones y escenarios se desea una imagen abstracta y/o estilizada. El proceso que puede generar ese tipo de imágenes es llamado Rendering No Fotorrealista, o NPR por sus siglas en inglés (Non Photorealistic Rendering). El NPR integra conceptos de Computación Gráfica y de Geometría Diferencial, y puede aplicarse en visualización científica e ilustración técnica, con el fin de destacar áreas o contornos de los objetos que son de interés para el observador; en la producción de imágenes que imiten medios tradicionales como la pintura o la acuarela; y en la generación de imágenes que imiten dibujos animados, entre otras áreas. En esta memoria se diseña e implementa un marco de trabajo (framework en inglés) para Computación Gráfica que permite desarrollar técnicas NPR y de rendering tradicional. El diseño del marco de trabajo contempla el estudio de los puntos comunes de diferentes técnicas de NPR y de las áreas asociadas, y, siguiendo el paradigma de la Orientación a Objetos, define distintas componentes internas que pueden ser extendidas para implementar técnicas de NPR y de rendering tradicional. La implementación se realiza en el lenguaje de programación C++ utilizando bibliotecas de código abierto o compatibles con código abierto: se utilizan la biblioteca gráfica OpenGL y el lenguaje Cg para comunicarse con los procesadores de la tarjeta de vídeo (GPU). El marco de trabajo incluye técnicas ya implementadas: para el rendering tradicional se implementaron graficadores de Gouraud y de Phong, mientras que para las técnicas NPR se implementaron graficadores de dibujado animado (Cel-Shading) y de modelos de tonos (Gooch Shading). Se implementaron extractores de líneas de interés (Siluetas y Contornos Sugestivos), así como una clase abstracta que permite definir nuevos tipos de líneas a extraer. La demostración de estas implementaciones se realiza mediante una aplicación de prueba que permite cargar modelos tridimensionales estáticos y animados; los resultados obtenidos se muestran mediante imágenes de los modelos tridimensionales cargados en la aplicación de prueba. Finalmente se realiza una discusión sobre el trabajo futuro, sobre las posibles líneas de investigación a seguir en estudios de post-grado y sobre el uso del marco de trabajo para implementar técnicas de rendering no NPR. Se concluye que el marco de trabajo se puede utilizar para el desarrollo de técnicas NPR y de rendering tradicional, que su desempeño es adecuado para el rendering en tiempo real para escenas tridimensionales de tamaño medio y que puede ser utilizado en aplicaciones reales.

Las máquinas de búsqueda para la Web utilizan el índice invertido como estructura de datos que permite acelerar las búsquedas en grandes colecciones de texto. Para lograr tiempos de respuesta por consulta menores al medio segundo, tanto el índice como la colección de texto se particionan en dos grupos de máquinas distintos. Cada consulta se envía al primer grupo, las cuales responden con los documentos más relevantes para esa consulta. Desde estos resultados se seleccionan los documentos más relevantes en forma global. Dichos documentos se envían al segundo grupo de máquinas las cuales extraen de la colección de texto el resumen (o snippet) asociado a cada documento en el resultado y construyen la página Web final a ser presentada al usuario como respuesta a su consulta. En este trabajo de memoria se propone un método alternativo de procesamiento de consultas, el cual ocupa un solo grupo de máquinas para realizar ambas operaciones, es decir, en un solo grupo de máquinas se realiza la determinación de los mejores documentos y la construcción de la página Web de respuesta. Para esto se recurre al uso de estrategias de texto comprimido auto-indexado y memoria cache diseñada para mantener las listas invertidas de los términos más frecuentes en las consultas. El texto comprimido auto-indexado se utiliza para generar de manera on-line las listas invertidas y para generar el resumen asociado a cada documento en la respuesta a una consulta. Los resultados experimentales muestran que en el mismo espacio ocupado por el índice invertido estándar es posible ubicar la memoria cache de listas invertidas y el texto comprimido, y alcanzar la misma tasa de respuestas por unidad de tiempo que se logra con el índice invertido. La ventaja está en que en el nuevo esquema no es necesario el uso del segundo grupo de máquinas, y por lo tanto se logra un mejor uso de los recursos de hardware, lo cual es relevante para la operación económica de los grandes centros de datos para máquinas de búsqueda.

No autorizada por el autor para ser publicada a texto completo / El continuo aumento de los volúmenes de información almacenada digitalmente ha fomentado el desarrollo de técnicas para brindar acceso y búsqueda de manera eficiente a los datos. En particular, el manejo de grandes colecciones de imágenes es un problema de gran interés. Un enfoque es tratar las imágenes como secuencias de texto bidimensional. En este contexto, han sido planteadas recientemente dos estructuras de autoindexación para colecciones de imágenes, basadas en extender autoíndices de texto unidimensional. Estas estructuras almacenan la colección en espacio proporcional al requerido para almacenar la colección comprimida, permitiendo a la vez el acceso directo a cualquier parte de la colección y la búsqueda eficiente de patrones en ella. Dos tipos de autoíndices para secuencias de texto son el Arreglo de Sufijos Comprimido y el Índice FM, y en ellos se basan las soluciones para imágenes. Este trabajo se centra en la implementación de esos dos autoíndices para imágenes. Se implementaron distintas variantes para ambas estructuras buscando la mejor manera de adaptarlas a secuencias bidimensionales, y mejorando significativamente varios de los algoritmos originales. Finalmente se diseñaron y ejecutaron experimentos para comparar las distintas variantes de ambos índices, tanto en términos de espacio requerido por las estructuras, como de tiempo en responder las consultas de acceso y búsqueda de patrones. Las estructuras basadas en el Arreglo de Sufijos Comprimido resultaron mejores en cuanto a tiempo, mientras que aquellas basadas en el Índice FM resultaron mejores en términos de espacio requerido, cuando el rango de colores es pequeño. Por ejemplo, con el Arreglo de Sufijos Comprimido somos capaces de almacenar una colección utilizando un 80% del espacio que requeriría la representación plana, pudiendo dar acceso a cualquier subimagen a una velocidad aproximada de 1 megapixel por segundo. Con esta estructura somos capaces de contar las ocurrencias de un patrón a una velocidad aproximada de 0,5 megapixeles por segundo, y podemos localizar la posición de cada ocurrencia en menos de 0,1 milisegundo. Sobre colecciones con un rango de color más pequeño, utilizando el Índice FM podemos alcanzar niveles de compresión del 50 %, pudiendo llegar al 25% si aceptamos pérdida de información. Con esta estructura podemos acceder a cualquier subimagen y realizar la búsqueda de patrones a una velocidad de 0,1 megapixel por segundo.