Ingeniero Civil en Computación / Las redes de comunicación anónima posibilitan nuevas formas de interacción entre las personas. En particular, la libre expresión de ideas contrarias a la opinión popular o la de la autoridad ha permitido, en ciertos casos, el inicio de procesos de cambio en las sociedades. Sin embargo, el anonimato puede ser abusado, lo cual lleva al cuestionamiento de la utilidad del mismo y a la tentación de no implementar estos sistemas. En este contexto, la posibilidad de filtrar de manera segura mensajes según un criterio público permite resolver este problema, al permitir implementar sistemas de comunicación anónima donde es posible filtrar (descartar) mensajes que no calzan con una política pública predefinida. Por ejemplo, el sistema de comunicación anónima pudiera establecer la restricción de que sólo mensajes "certificados" (firmados) por entidades confiables pueden ser comunicados. Un posible escenario de uso de tal sistema sería el caso en que usuarios pueden "comprar" el acceso al sistema de comunicación anónima, vía una autorización de su autoridad certificadora local. Una solución para este escenario se complica debido a la naturaleza distribuida de las implementaciones de canales de comunicación anónima - cada participante del sistema debe poder verificar si está procesando mensajes certificados o no. En la presente memoria se trabajó en la definición e instanciación de un sistema de comunicación anónima (en particular, una red de mezcla basada en reencriptación) que permitiese el filtrado de mensajes según una propiedad claramente definida. Para ello, primero se realizó un estudio de herramientas comúnmente aplicadas para obtener propiedades criptográficamente verificables, firmado y anonimato. Habiendo identificado un conjunto de herramientas útiles, el trabajo se focalizó en el aspecto definicional. Se logró construir una definición basada en conceptos criptográficos estándares. Luego, utilizando herramientas criptográficas analizadas, se construyó una instanciación de esta definición, utilizándose técnicas criptográficas formales y rigurosas para demostrar la seguridad del esquema. La solución desarrollada no sólo logra resolver el problema planteado, sino que provee una base sobre la cual pueden realizarse múltiples mejoras y extensiones futuras.

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.

Ingeniera Civil / Actualmente se vive una situación de estrechez hídrica prolongada en la mayor parte del territorio nacional, donde se observa que desde la VI región hacia el norte, la demanda de agua dulce supera la oferta. Una de las principales fuentes de agua dulce la constituyen aquellas provenientes del derretimiento de nieves, por lo cual el modelar su derretimiento a escalas temporales finas, es decir, escalas temporales menores a la mensual, con el objeto de gestionar y utilizar el recurso hídrico de forma óptima, resulta de gran importancia. La presente memoria consiste en la elaboración de distintas redes neuronales artificiales con el objetivo de pronosticar caudales de deshielo a tres escalas temporales, las cuales son la escala diaria, semanal y quincenal, para la cuenca Mapocho en los Almendros. Adicionalmente, se evalúan y analizan los efectos de incluir datos hidrometeorológicos provenientes de la estación en Valle Nevado, tales como humedad del aire, temperatura y precipitación, en las redes neuronales. La metodología consta de cinco partes, en primera instancia se estudian las redes neuronales artificiales (RNA) mediante revisión bibliográfica, luego se realiza un análisis teórico del fenómeno en estudio con el objetivo de definir las variables significativas y poder formular las RNA para el pronóstico de caudales de deshielo a los distintos niveles temporales y seleccionar la RNA óptima para cada nivel. Finalmente se realiza la inclusión de los datos hidrometeorológicos de la estación Valle Nevado en los modelos RNA, concluyendo con un análisis de resultados, en el cual se simulan las RNA óptimas para la temporada de deshielo 2013 2014. Los resultados indican que se obtuvieron RNA con coeficientes de correlación de Pearson R2 mayores a 0.99 en el caso de las escalas temporales diaria y quincenal y mayores a 0.98 en el caso de la escala temporal semanal. Al simular las RNA óptimas para la temporada de deshielo 2013-2014, se obtuvieron caudales con errores absolutos promedio de 0.18 m3/s (5.6 %) para la escala temporal diaria, 0.39 m3/s (11.6%) para la escala temporal semanal y 0.38 m3/s (11.5%) para la escala temporal quincenal. Respecto a los parámetros de entrada, se concluye que aquellos más significativos, son los relacionados al caudal y la temperatura máxima, lo cual se observa tanto para las RNAs entrenadas con datos de la estación Mapocho en Los Almendros como de la estación Valle Nevado. Por último, debido a la escasa disponibilidad de datos y a la baja calidad de los mismos, los resultados obtenidos a partir de las RNAs entrenadas con datos de la estación Valle Nevado, no permiten decir con certeza si la inclusión de datos provenientes de una estación ubicada a 3.000 m.s.n.m. implican una mejora en los pronósticos de caudales de deshielo.

Plantilla para elaborar Trabajo de investigación de Ciencias de la Computación para la obtención del grado de bachiller en Ciencias de la Computación en el Programa Académico de Ciencias de la computación. Facultad de Ingeniería. Universidad Peruana de Ciencias Aplicadas.

El Gobierno Electrónico es considerado una herramienta para lograr mejor gobernabilidad debido a que promueve y facilita la participación ciudadana, la prestación de servicios de manera más efectiva y un modo de operación más eficiente. El potencial de gobierno electrónico es dependiente, en gran medida, de un fuerte liderazgo. El liderazgo es uno de los factores más importantes, no sólo para el desarrollo del gobierno electrónico sino también para la aplicación de las Tecnologías de la Información y las Comunicaciones (TICs) en cualquier contexto. Por este motivo, el modelo de CIO (Chief Information Officer), originado en el sector privado como respuesta a la necesidad de administrar los asuntos relacionados con tecnología, ha sido el mecanismo adoptado por varios gobiernos durante los últimos años para resolver y liderar las iniciativas de gobierno electrónico. Los países más avanzados en materia de gobierno electrónico han definido la figura de GCIO (Government CIO) con el objetivo de controlar y mejorar el uso de las TICs dentro de la administración pública (AP) y la tendencia refleja que, durante los próximos años, un número importante de países formalizará la posición de GCIO. Sin embargo, la implementación de un sistema que sea eficiente y mantenible en el tiempo puede demandar un gran esfuerzo, con plazos largos y costos altos, especialmente para los países menos desarrollados. Por este motivo, es importante poder aprender de la experiencia de los países más desarrollados en el tema para poder replicar las iniciativas exitosas y evitar cometer los mismos errores. Esta tesis presenta los conceptos y los fundamentos del CIO de gobierno con el propósito de poder contribuir – especialmente con los países que están comenzando o aún no han comenzado con la implementación de un modelo de coordinación y liderazgo de tecnología – en establecer y sostener un sistema de GCIO. El sistema considera todos los aspectos del entorno que pueden afectar la implementación del modelo, incluyendo factores tecnológicos, culturales, sociales, institucionales, políticos, regulatorios, económicos, financieros, operativos, internacionales, etc. Además, incluye propuestas de procesos y metodologías para guiar el desarrollo de algunas de las actividades clave identificadas por el sistema y las experiencias de su utilización en situaciones reales de gobiernos con características muy distintas como son el gobierno nacional de Colombia en Sudamérica y la Región Administrativa Especial de Macao, en Asia. Las principales contribuciones de la tesis son: (1) la definición rigurosa y formal del dominio del GCIO que sirve no sólo para definir un vocabulario común y que puede ser utilizada como marco unificador para resolver problemas sino también para permitir que se comparta, se intercambie y se reutilice el conocimiento existente en el tema, (2) un relevamiento extensivo de las experiencias en la implementación de la figura de GCIO en algunos de los países más avanzados en materia de gobierno electrónico, (3) un marco de trabajo para guiar la implementación de un modelo de GCIO que sea eficiente y mantenible en el tiempo, y (4) una metodología para la evaluación del estado de preparación – y su posterior evolución – de una AP para la implementación de un sistema de GCIO.

La idea central de esta tesis consiste en aprovechar las técnicas metaheurísticas para resolver problemas reales asociados al transporte. Por ende, en esta investigación hemos incluido el desarrollo de algoritmos metaheurísticos, su diseño, aplicación y testeo del software. Los problemas de transporte se caracterizan por su difícil tratamiento, con respecto a su modelado. En particular, en Argentina, la calidad del servicio de transporte público ha sido considerada históricamente como inadecuada, encontrándose típicamente asociada a un reclamo continuo por parte de la sociedad. Por lo tanto, la principal línea de investigación aquí tratada se relaciona con el transporte público de pasajeros, particularmente concentrándose en las localizaciones de las paradas de colectivos y en el establecimiento de las rutas que servirán para prestar un mejor servicio, minimizando los costos globales. Como última parte de nuestras investigaciones, creamos una hiperheurística eficiente basada en el análisis de desempeño de distintas metaheurísticas, cuyos algoritmos individuales desarrollamos y testeamos en primera instancia. Se consideraron las siguientes metaheurísticas: Algoritmos Genéticos, Recocido Simulado y Optimización por Colonia de Hormigas. Como resultado hemos obtenido una técnica hiperheurística que resuelve exitosamente el problema de localización y ruteo para el transporte público. El algoritmo propuesto selecciona y aplica la metaheurística apropiada para cada momento, a fin de obtener un proceso de búsqueda exitoso. Comparaciones con procedimientos bien establecidos reflejan el impacto de un procedimiento hiperheurístico sobre la optimización completa. Las principales contribuciones de esta tesis se pueden resumir como sigue: * Nuevas propuestas para el tratamiento de un problema que aqueja a gran parte de la población mundial como lo es el transporte público. * Aplicación exitosa del enfoque en problemas de transporte no relacionado a las personas, tal como la localización de cañerías. * Técnicas que reducen el número de evaluaciones improductivas mediante la implementación de una memoria interna. * Novedosa selección de vecinos que acelera el proceso de búsqueda. * La capacidad de enlazar nuestra propuesta con software externo. * Estrategia paralela que ofrece notables mejoras en cuanto al tiempo de cómputo a la vez que optimiza los recursos disponibles / The thesis statement concerns taking advantage of metaheuristic techniques as a means to solve realistic problems associated to transport. Then, in this research we have included the development of metaheuristic algorithms, their design, application and software testing. Transport problems are characterized by their difficult treatment, as regards their modeling. In particular, in Argentina, the quality of public transport service has historically been deemed inadequate, being typically marked by continual social demands. Therefore, the main points that this research covered is related to public transport of passengers, particularly concentrating on bus-stop locations and bus-route design so as to offer a better service while minimizing global costs. As the last part of our research work, an efficient hyper-heuristics was created on the basis of the performance analysis of various meta-heuristics, whose individual algorithms were firstly developed and tested. The following meta-heuristics were considered: Genetic Algorithms, Simulated Annealing and Ant Colony Optimization. As a result, we have obtained a hyperheuristic technique that succeeds in solving the location and routing problem for the public transport. The proposed algorithm chooses and applies the most adequate metaheuristic at any time instance, in order to obtain a successful search process. The comparisons with the well-established procedures reflect the impact of a hyperheuristic procedure on the optimization as a whole. The main contributions of this thesis can be summarized as follows: * New proposals for the treatment of a problem that concerns a wide amount of the world population, like the public transport. * Successful application of this approach to transport problems unrelated to persons, like pipeline routing. * Techniques that reduce the number of unproductive evaluations by means of an internal memory implementation. * Novel neighbour choice that speeds up the search process. * The capacity to link our proposal with external software. * Parallel strategy that offers noteworthy improvements as regards computing times, while optimizing the available resources

Los dispositivos móviles son utilizados con más frecuencia por la sociedad, en los últimos años ha habido un crecimiento en la venta de estos equipos y por consiguiente en las aplicaciones que brindan. Un tipo importante de estas aplicaciones, son las educativas a través de las cuales se le brindan mayores oportunidades de desarrollo y crecimiento a la sociedad en este contexto. Estas aplicaciones se han desarrollado enfocadas en diversas áreas y para todo tipo de usuarios, desde niños hasta adultos. Por lo tanto su usabilidad se convierte en un factor clave para su adopción. El objetivo de este trabajo es identificar cuáles son las técnicas de usabilidad que se utilizan en las aplicaciones educativas móviles por área y nivel educativo, y que tipos de perfiles de usuario realizan estas evaluaciones. Para ello se realizó un mapeo sistemático, en el cual se identificó un total de 1503 artículos, de los cuales se seleccionaron 174 para su revisión. Los resultados muestran que la prueba de usuarios es la técnica de evaluación de usabilidad más utilizada en las aplicaciones educativas móviles; de igual manera las aplicaciones de idiomas y tecnologías de la información y comunicación, han sido en las que más se han aplicado estas técnicas y el público universitario (pregrado y postgrado) es en el que la mayor cantidad de aplicaciones educativas móviles se han evaluado; siendo los alumnos los que realizan en su mayoría estas evaluaciones. Estos resultados pueden orientar a expertos y desarrolladores de software de aplicaciones educativas móviles, al seleccionar las técnicas de evaluación de usabilidad y los perfiles de usuario adecuados, de acuerdo al área y nivel educativo al que está dirigida la aplicación; con lo cual les permitirá crear aplicaciones con mayor facilidad de uso en base a las necesidades de los usuarios. / Trabajo de investigación

When many users consult service desks simultaneously, these typically saturate. This causes the customer attention is delayed more than usual. The service is perceived as lousy from the point of view of the customer. Increase the amount of human agents is a costly process for organizations. In addition, the amount of sta turnover in this type of service is very high, which means make frequent training. All this has motivated the design of a knowledge-based system that automatically assists both customers and human agents at the service desk. Web technology was used to enable clients to communicate with a software agent via chat. Techniques of Natural Language Processing were used in order the software agent understands the customer requests. The domain knowledge used by the software agent to understand customer requests has been codi ed in an ontology. A rule-based expert system was designed to perform the diagnostic task. This paper presents a knowledge-based system allowing client to communicate with the service desk through a chat system using free text. A software agent automatically executes the customer request. The agent software attempts to reach a conclusion using expert system and ontology. If achieved success, returns the response to the customer, otherwise the request is redirected to a human agent. Evaluations conducted with users have shown an improvement in the attention of service desks when the software developed is used. On the other hand, since the most frequent requests are handled automatically, the workload of human agents decreases considerably. The software has also been used to train new human agents which facilitates and reduces the cost of training. / Tesis

No autorizado por el autor para ser publicada a texto completo / La cantidad de datos disponibles crece de forma dramática cada día. Esto trae consigo la necesidad de poder manejar éstos datos de forma adecuada, de manera de poder acceder a estos de forma eficiente y al mismo tiempo ahorrar espacio de almacenamiento. En particular, para manejar grandes cantidades de texto una herramienta clave son los índices de texto, y en el contexto de este trabajo los índices comprimidos, los cuales no sólo responden consultas de forma rápida sino que también almacenan sus datos y el texto en forma eficiente. El objetivo general del presente trabajo fue desarrollar un índice comprimido basado en listas de ocurrencias de los q-gramas del texto y comprimir este último. Se desea comparar la eficacia de este índice con los auto-índices ya desarrollados en el sitio Pizza&Chili (http://pizzachili.dcc.uchile.cl). Un índice invertido de q-gramas permite encontrar patrones en un texto. Para tal efecto las consultas se dividen en dos etapas. En la primera etapa se seleccionan las regiones del texto (llamadas bloques) donde ocurren todos los q-gramas del patrón y por lo tanto éste podría encontrarse. En la segunda etapa se verifica si efectivamente el patrón se encuentra en los bloques que fueron seleccionados. Además es necesario almacenar el texto de forma independiente. En la implementación realizada se mantiene el texto dividido en bloques comprimidos, los cuales se almacenan en memoria secundaria. Esto permite utilizar menos espacio y acceder a los bloques individualmente. Se implementaron diversos algoritmos para comprimir el índice y realizar consultas. Además se diseñaron y ejecutaron experimentos para medir el rendimiento de las distintas variantes obtenidas al combinar los diferentes algoritmos. En base a los resultados obtenidos se seleccionaron los algoritmos que presentaron mejor rendimiento tanto en velocidad como en niveles de compresión alcanzados. De la misma forma se implementaron y midieron experimentalmente alternativas para comprimir y buscar en el texto. Finalmente se comparó el rendimiento de las variantes seleccionadas del índice frente a los índices competitivos presentes en el sitio Pizza&Chili. Los resultados indican que el índice tiene un rendimiento competitivo para búsquedas de patrones pequeños.

Ingeniero Civil en Computación / El árbol de sufijos es una de las estructuras más importantes que se han creado para el manejo de cadenas de caracteres. Esta estructura permite encontrar eficientemente las ocurrencias de un patrón, en tiempo proporcional al largo del patrón. Adicionalmente soporta operaciones para resolver problemas complejos sobre una secuencia. Esta estructura tiene muchas aplicaciones en variadas áreas de la investigación , destacándose en la bioinformática, donde los recientes avances tecnológicos han permitido recolectar grandes colecciones de secuencias de ADN. La implementación clásica se vuelve impracticable para grandes volúmenes de información dado que ocupan demasiado espacio, que siempre muchas veces mayor que el texto mismo. Luego, no pueden ser almacenados en memoria principal, lo que en la práctica significa un aumento importante del tiempo de respuesta. Este problema es la principal motivación por la cual se buscan nuevas representaciones comprimidas de esta estructura, dando lugar a los árboles de sufijos comprimidos. Estos contienen la misma información que los árboles de sufijos pero ocupan un espacio considerablemente menor. Existen variadas propuestas teóricas para representar un árbol de sufijos comprimido, que ofrecen espacios y tiempos diferentes. En la práctica, dos estructuras destacan por sobre las demás. La primera fue propuesta por Sadakane e implementada por Välimäki et al. Esta estructura soporta la mayoría de las operaciones de navegación en tiempo constante, pero en la práctica requiere entre 25 y 35 bits por símbolo. La segunda fue propuesta por Fischer et al. e implementada por Cánovas, incorporando variantes y nuevas ideas para todas las estructuras que componen el árbol de sufijos comprimido propuesto por ellos. Una de estas variantes resulta ser superior a la implementación de Sadakane tanto en espacio como en tiempo, utilizando alrededor de 8 a 12 bits por símbolo. Dado que secuencias de ADN relacionadas son altamente similares, por ejemplo dos genomas humanos son muy parecidos, las colecciones pueden ser tratadas como un gran texto que contiene cadenas altamente similares. En este trabajo se propone e implementa una nueva variante del árbol de sufijos comprimido de Fischer et al, optimizada para textos altamente repetitivos. Se reemplazan y/o modifican cada una de las estructuras que componen el árbol por nuevas que presentan mayor compresión en textos repetitivos. El resultado más importante consiste en crear una nueva estructura inspirada en una técnica de compresión basada en gramáticas, aplicable al árbol de sufijos comprimido, que con poco espacio extra acelera considerablemente las operaciones sobre el árbol. Finalmente, la variante se compara experimentalmente sobre textos altamente repetitivos y resulta ser superior a la implementación de Cánovas, tanto en tiempo como en espacio, ocupando entre 3 a 6 bits por símbolo. / Este trabajo ha sido parcialmente financiado por el Instituto Milenio de Dinámica Celular y Biotecnología (ICDB) y el proyecto Fondecyt 1-080019