El problema de la búsqueda aproximada en texto consiste en buscar las ocurrencias de un patrón en un texto, permitiendo que las ocurrencias no sean necesariamente copias exactas del patrón, sino que sean su cientemente próximas de acuerdo a alguna métrica particular. El problema tiene gran importancia en áreas como recuperación de la información, biología computacional y bases de datos de texto. El algoritmo de Chang y Marr (1994) es un algoritmo teóricamente óptimo en la complejidad de tiempo promedio para este problema. Posteriormente, Fredriksson y Navarro (2004) diseñan un algoritmo teóricamente óptimo que además es competitivo en la práctica. Esto hace pensar que el desarrollo de algoritmos exactos para este problema está llegando a su límite. El objetivo de este trabajo es enfrentar el problema de búsqueda utilizando una formulación débil que tiene potenciales aplicaciones prácticas y admite soluciones más e cientes que aquellas que se obtienen con algoritmos exactos, a cambio de posibles errores en la respuesta. Denominamos nuestra formulación búsqueda aproximada permitiendo errores. La principal contribución de este trabajo es la introducción y de nición formal del problema de búsqueda aproximada permitiendo errores para el caso en-línea, es decir, cuando se asume que no hay tiempo o espacio su ciente como para preprocesar el texto. Se presentan algoritmos para esta formulación, apoyados por análisis teóricos y experimentales que permiten entender su competitividad con respecto a algoritmos exactos para búsqueda aproximada. Los algoritmos propuestos son probabilísticos, permitiendo perder ocurrencias con cierta probabilidad y disminuyendo el tiempo de ejecución a cambio. Por ejemplo, sobre lenguaje natural estos algoritmos pueden recuperar el 95 % de las ocurrencias ocupando sólo el 15 % del tiempo utilizado por algoritmos exactos similares. El trabajo se complementa con algunas extensiones de las ideas desarrolladas para el caso en línea a otros problemas relacionados. En particular, se estudia cómo adaptar las ideas planteadas al problema de búsqueda aproximada múltiple, donde varios patrones se buscan sobre un mismo texto y a la búsqueda fuera de línea, en la cual se permite preprocesar el texto. Ambas extensiones muestran la robustez de los conceptos introducidos en este trabajo.

En la secuencia de la cadena de valor de la fibra de alpaca,la medición es realizada por observación basada en el conocimiento tradicional. La valorización depende en muchos casos de la experiencia empírica, lo cual dificulta entender la riqueza intrínseca del hato.Dando como consecuencia vellonespoco sostenibles en el tiempo.La contribución principal, pretende comprender el potencial de las alpacas, no sólo por el diámetro de la fibra, sino por sus otras características, estandarizando criteriosa través de los estereotipos. Este trabajo está sustentado sobre publicaciones relacionadas a las características de la fibra en sus diferentes dimensiones, proponiendo una solución que permita asignar un valor característico en los individuos, que resulte equiparable entre su morfología y genética. Diseñando un modelo de redes neuronales artificiales y reglas de asociación, quehizo posible transformar la percepción de los expertos en un valor característico definida por una escala de calificación. Se realizaron diferentes ensayos experimentales en Cusco, Puno y Huancayo. Aplicando la prueba de Friedman, como método de comparación entre tres tratamientos. Se utilizó el estadístico (H0, α<0.05), como parámetro de decisión. Finalmente, el artefactorespondió en forma similar a los otros tratamientos, manteniendo el estándar de la NTP 231.300:2004 y elOFDA-100. Con cierto grado de madurez, este artefacto puede convertirse en referente nacional y ayudar a la toma de decisiones en estrategias de mejoramiento de la especie. -- Palabras clave: Redes Neuronales Artificiales, Reglas de asociación, Fibra Fina, OFDA / -- In the sequence of the value chain the alpaca fiber, the measurement it’s made by observation and supported on classic knowledge. The quality depends in many cases of empirical experience, difficult to understand the herd intrinsic richness. Giving due fleece unsustainable in the time. The main contribution aims understand his alpaca potential. Don’t only for fiber diameter, but for his other characteristics been to standard criteria through of the sterotypes. This job to be supported of publish relational with fiber characteristics in his dimensions different, proposing a solve how allow to assign a characteristic value individuals, resulting comparable between his genetic and morphologic. Designing a model artificial neural network and rules of association, it made possible to transform the perception of the experts on characteristics value defined for a scale of qualify. Were different tests experimental in Cusco, Puno and Huancayo, applying the test of Friedmann, as method of comparison between three treatments. So used the statistical (H0, α<0.05), as parameter of decision. Finally, the artifact responded in form similar from others treatments, keeping the standard NTP 231.300:2004 y el OFDA-100.With true grade of maduraty, this artifact can become in a national framework and to help to making decision in strategies of improvement of the species. -- Keywords: Artificial Neural Network, Rules Association, Fine Fiber, OFDA. / Tesis

Tesis para optar al grado de Magíster en Finanzas

Históricamente, la autentificación de mensajes se ha manejado a través de firmas digitales basadas en certificados, usualmente emitidos por una entidad neutral a la comunicación y de confianza de todas las partes. Sin embargo, esta solución no siempre es posible de implementar, debido a factores como los costos, el tiempo limitado de vigencia de los certificados, la necesidad de depositar la confianza en un tercero, y por último el poder, usualmente limitado, de procesamiento de las máquinas. Además los certificados usualmente son muy pesados, y deben adjuntarse a cada mensaje enviado para mostrar su autenticidad, lo cual dificulta su implementación en dispositivos con poca capacidad de almacenamiento. La Criptografía basada en identidad (o Identity Based Cryptography, IBC) es una alternativa al escenario presentado en sistemas que desean autentificar mensajes, pero no quieren (o no pueden) depender de certificados. Esto se logra usando la identidad de la persona (o del dispositivo) como semilla para la generación de claves por parte de un servidor maestro dentro del mismo sistema. De esta forma, las firmas son mucho más ligeras que los certificados, agilizando las comunicaciones. Además, como las identidades son públicas, cualquier miembro de la red puede verificar la autenticidad de un mensaje sin necesidad de hacer consultas online al ente central. Por otro lado, las lecturas biométricas son la forma más usada de comprobar la identidad de una persona, ya sea a través de las huellas digitales, reconocimiento facial, lectura de iris o incluso análisis de forma de las orejas. Esto debido a que los rasgos mencionados son únicos para la persona, e incluso los dispositivos actuales permiten reconocer rasgos latentes, es decir que no poseen señales biológicas, de "vivos" y así prevenir el uso de guantes, máscaras, etc. El tema de esta tesis es desarrollar una alternativa de sistema de seguridad para dispositivos de procesamiento limitado. El sistema utiliza firma de mensajes basada en identidad, pero usando las huellas digitales tanto para enlazar un usuario específico a un dispositivo, como para la protección de los datos privados del usuario. El sistema debe poder extenderse para poder incorporar encriptación basada en identidad también. La primera parte de este trabajo consiste en un estudio de las componentes a usar, tanto de hardware como de software, incluyendo los conceptos básicos necesarios para su diseño y operación, así como los estándares que siguen. La segunda parte corresponde a un estudio y descripción detallada de las componentes del proyecto y de la implementación realizada, para terminar con posibles extensiones. El sistema se probará en dispositivos BUG, un tipo de hardware usado en el diseño y fabricación de prototipos modulares.

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.

No description available.

No description available.

No description available.

No description available.

Doctor en Ciencias, Mención Computación / Los autoíndices comprimidos para texto ofrecen una funcionalidad similar a la de los índices clásicos, ocupan espacio proporcional al tamaño del texto comprimido, y además lo reemplazan, pues son capaces de reproducir cualquier subcadena del texto. Aunque un índice comprimido es más lento que su versión clásica, puede funcionar en memoria principal en casos en que un índice tradicional tendría que recurrir a la memoria secundaria, que es órdenes de magnitud más lenta. Por otra parte, los autoíndices comprimidos para texto actuales sufren de varias deficiencias, como la falta de practicidad, la lentitud para localizar un patrón y para extraer un texto, y la falta de mecanismos de construcción eficientes en espacio, de versiones en memoria secundaria o de capacidades para actualizar el índice. Esta tesis aporta soluciones para todos estos problemas. Nuestra primera contribución es una estructura de datos para arreglos de bits, sencilla y eficiente, que permite consultas de rank y select, y que se ha hecho muy popular por su practicidad. También se creó el sitio Pizza&Chili, que contiene una colección de textos y de índices comprimidos, y se realizó un estudio práctico que compara los índices más prometedores. Cabe destacar que este sitio se ha convertido en una referencia habitual en la comunidad. Se desarrolló un nuevo índice comprimido para texto, basado en regularidades del arreglo de sufijos, el cual permite localizar ocurrencias rápidamente, y aún es más pequeño que los índices clásicos. Esta estructura se basa en Re-Pair, un compresor que posee propiedades de localidad que no tienen los índices comprimidos clásicos. Se desarrolló un codificador estadístico de secuencias, que permite el acceso directo a cualquier parte de la secuencia y logra una compresión de alto orden. Esta es una herramienta clave para lograr velocidad y localidad en la extracción de texto en un índice comprimido. Aprovechando esta localidad en la localización y en la extracción, se presentó un nuevo índice para memoria secundaria cuyo tiempo de acceso mejora gracias a la compresión, en lugar de empeorar como es lo normal en otros autoíndices. Este índice ofrece un compromiso muy competitivo entre espacio y tiempo. / Esta tesis ha recibido el apoyo de Mecesup, Proyecto UCH 0109, Chile; del Núcleo Milenio Centro de Investigación de la Web, Proyecto P04-067F, Mideplan, Chile; de Yahoo! Research Latin America, y del Instituto Milenio de Dinámica Celular y Biotecnología, Proyecto P05-001-F, Mideplan, Chile