Orientador: Roberto de Alencar Lotufo / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e Computação / Made available in DSpace on 2018-08-03T16:19:35Z (GMT). No. of bitstreams: 1 Zampirolli_FranciscodeAssis_D.pdf: 1636054 bytes, checksum: 4a735d10a69d449de502f78d4b02f2e8 (MD5) Previous issue date: 2003 / Doutorado

El objetivo del presente trabajo de título es estudiar el algoritmo para búsqueda de patrones en texto debido a Boyer-Moore-Horspool (BMH) bajo un enfoque de texto sometido a una ligera perturbación independiente carácter a carácter, de manera de determinar la esperanza del desempeño del algoritmo sometido a dicha perturbación. El algoritmo BMH es una simplificación de Horspool al algoritmo que había sido propuesto anteriormente por Boyer y Moore (BM). En el mismo trabajo original de Horspool, él hace notar que su versión, en cuanto a tiempo de ejecución y comparaciones entre texto y patrón, aunque más sencilla y con peor desempeño de peor caso, tiene un desempeño comparable y a veces incluso superior al del algoritmo BM. Si bien diversos trabajos han hecho un buen análisis del algoritmo BMH especialmente en el caso promedio, no es claro que un análisis promedio sea una buena respuesta a la pregunta de por qué un algoritmo funciona bien en la práctica aunque su desempeño de peor caso sea deficiente. Basados en el enfoque de análisis suavizado propuesto originalmente por Spielman y Teng pero adaptado para problemas de naturaleza discreta y más específicamente para texto, proponemos una perturbación bajo la cual analizar el desempeño esperado del algoritmo BMH cuando la entrada es sometida a una perturbación lo suficientemente pequeña como para no eliminar la influencia que la entrada ejerce sobre el desempeño del algoritmo. Para ello, en primer lugar, diseñamos herramientas que permiten encontrar una familia de constantes, indexada por parámetros del algoritmo, que acotan el peor desempeño en cada caso. También diseñamos un procedimiento para calcular dichas constantes para patrones y alfabetos pequeños. Luego encontramos una familia de constantes análoga a la anterior para acotar el desempeño esperado, bajo perturbación de texto, del algoritmo, y demostramos resultados que aseguran que dicho desempeño perturbado, bajo condiciones razonables, es mejor que el desempeño de peor caso asintóticamente con el tamaño del texto. Finalmente, mostramos alguna evidencia empírica que sugiere que dentro del espacio de entradas la mayoría lleva a un comportamiento sustancialmente mejor al del peor caso. Las herramientas desarrolladas durante el trabajo y el enfoque aplicado podrían, en un trabajo futuro, justificar la diferencia entre el desempeño teórico y el observado en la práctica para BMH.

En el siguiente trabajo se presentan dos tratamientos a los problemas suscitados en el análisis de datos con presencia de datos perdidos: El Algoritmo EM basado en la Estimación por Máxima Verosimilitud y la Imputación Múltiple para datos faltantes, ambos métodos presentan ciertas ventajas frente a los métodos de imputación simple que ocasionan la obtención de estimadores distorsionados y sesgados. El algoritmo EM y la Imputación Múltiple se aplican a un conjunto de datos obtenido por simulación, causándole la pérdida de algunos valores con el objetivo de realizar posteriores comparaciones de las estimaciones obtenidas en casos con el conjunto de datos con y sin información faltante.

Se presenta una variante del método de punto interior (MAE) para resolver un programa matemático lineal. Describe el método de escalado afín, relevando su aspecto geométrico y presentando aplicaciones. Compara la eficiencia de este método con la del método simplex. / Tesis

Dado un conjunto de requerimientos lineales y un número ilimitado de barras de metal (u otro material) de tamaño estándar, con dimensión mayor a la de los requerimientos. El Problema de Cortes consiste en realizar cortes sobre las barras de tamaño estándar, de tal manera que se obtengan todos los requerimientos con el menor número de barras de tamaño estándar y el menor desperdicio posible. El problema es NP-Difícil, y presenta diversas aplicaciones en los diversos sectores de la industria, tales como la maderera, metal, plástico, etc. La presente Tesis, muestra un Procedimiento de Búsqueda Aleatoria, Adaptativa y Golosa (GRASP), para la resolución del problema de cortes. Experimentos numéricos realizados del algoritmo propuesto sobre 100 problemas-test, reportan una eficiencia, promedio del 95.4% para un parámetro de relajación de 0.5 y 2000 iteraciones. El software implementado consta de 4 módulos importantes: ingreso de datos necesarios para la realización de los cortes, Algoritmos Golosos FFD (First Fit Decreasing) y BFD (Best Fit Decreasing), GRASP y Reportes. / Given a group of lineal requirements and a limitless number of metal bars (or another material) of standard size, with more dimension to that of the requirements. The Cutting Stock Problem consists on carrying out courts on the bars of standard size, in such a way that all the requirements are obtained with the smallest number of bars of standard size and the minor waste possible. The problem is NP-hard, and it presents several applications in the different sectors of the industry, such as the lumberman, metal, plastic, etc. The present Thesis shows a Procedure of Random Search, Adaptive and Greedy to solve the Cutting Stock Problem. Carried out numeric experiments of the algorithm proposed on 100 problem-tests, they report efficiency, average of 95.4% for a parameter of relaxation of 0.5 and 2000 iterations. The implemented software consists of 4 important modules: entrance of necessary data for the realization of the cuts, Greedy Algorithms FFD (First Fit Decreasing) and BFD (Best Fit Decreasing), GRASP and Reports.

Los problemas de corte de piezas se presentan en diversos sectores productivos y han sido ampliamente estudiados en la literatura. En algunos casos, son problemas simples de especificar; pero en todos los casos son extremadamente difíciles de resolver; aquí se considera un caso de esa familia de problemas denominado el problema de corte de piezas irregulares. El objetivo principal de este trabajo es implementar un algoritmo que permita resolver el problema de corte de piezas irregulares el cual consiste básicamente en minimizar el número de superficies que alojen a una determinada cantidad de piezas irregulares en demanda, posicionar las piezas en las respectivas superficies, permitien- do minimizar la perdida de material. La solución a este problema se entrega a través de un programa computacional basado en la metaheurística GRASP y la Simulación Dinámica, donde el algoritmo implementado selecciona las piezas irregulares a posicionar en cada superficie, para luego aplicarles parámetros físicos necesarios para la simulación dinámica. Una vez que las piezas se compacten dentro de cada contenedor se tiene la configuración final, donde se analiza el desperdicio resultante. Se midió el rendimiento del algoritmo basándose en un conjunto de instancias de prueba; los experimentos numéricos sobre 10 instancias numéricas muestran un bajo costo computacional y un grado de eficiencia respecto a la calidad de la solución en 100 %.

State Estimation is responsible for constructing a complete and reliable database, which will be used by other functions in an Energy Management System. Data redundancy is crucial for the success of state Estimation. With an adequate redundancy, State Estimation can detect, identify and suppress bad data. Besides, the quality/reliability of the estimated quantities is not affected in case of a temporary loss of measurements. Redundancy level is evaluated considering the number, type and location of meters in the network. Metering systems with a high redundancy level are always desirable. As it is related to the investments on metering and communication equipments, many times redundancy level is reduced due to financial constraints. On the other hand, during power systems operation, topology changes or data acquisition system malfunctions may also reduce the data redundancy for State Estimation. Even critical levels may be reached, where loss of observability is imminent and bad data processing routines do not work properly. This work describes the development of a computational tool for the design and evaluation of metering systems. The developed tool aims to help the designer on the analyses of different metering plans, taking into account the need to establish adequate trade-offs between the expected performance of the State Estimation function employs and the associated investments costs. / El proceso de Estimación de Estado comprende aplicativos responsables por la construcción de una base de datos completa y confiable que es utilizada por funciones avanzadas en un Sistema de Gerenciamiento de Energía. La redundancia de datos es fundamental para el suceso de la Estimación de Estado. Con un nivel adecuado de redundancia, el proceso de Estimación de Estado puede lidiar con el problema de detección, identificación y eliminación de errores groseros, además de permitir que la perdida temporaria de medidas no afecte a la calida/confiabilidad de las estimativas producidas. La redundancia es evaluada considerándose el número, tipo y distribución topológica de los puntos de medición en una red eléctrica. Siempre se requieren sistemas de medición altamente redundantes. Una vez que la cantidad de datos está directamente relacionada a la inversión de una empresa eléctrica en equipos de medición y transmisión de informaciones, muchas veces la redundancia sufre cortes presupuestales en la revisión de asignación de fondos. Por otro lado, durante la operación del sistema, cambios en la configuración de la red o un funcionamiento temporalmente inadecuado del sistema de adquisición de datos, reducen el nivel de redundancia para la Estimación de Estado. De esta manera, se pueden alcanzar niveles críticos, caracterizando situaciones de pérdida de observabilidad y consecuentemente un desempeño inadecuado de rutinas de procesamiento de errores groseros. Este trabajo describe el desarrollo de un sistema informático para el planeamiento y evaluación de sistemas de medición destinados a la función de Estimación de Estado. Este sistema busca facilitar el análisis de diversas alternativas de interés de un proyectista, muchas veces con la necesidad de conciliación de aspectos conflictivos como la atención al requisito de desempeño de la Estimación de Estados en relación a los costos asociados.

Magíster en Tecnologías de la Información / En todas las instituciones de educación, el proceso de creación de un horario académico es un desafío que se debe sortear semestre a semestre. Este proceso no es simple, ya que está sujeto a restricciones físicas, reglamentarias y legales entre otras. El objetivo de esta investigación es ofrecer una alternativa de solución para el problema de la asignación de horarios y salas en INACAP, una de las instituciones de educación de mayor envergadura en cuanto a cantidad de alumnos y a infraestructura. En este trabajo se revisan algunos de los métodos más utilizados para resolver estos problemas de tipo timetabling, un problema considerado de tipo NP-completo, entre los cuales se encuentra la programación lineal y los algoritmos genéticos. Los algoritmos genéticos, como varios otros métodos, se basan en procesos que se encuentran presentes en la naturaleza. Son técnicas de optimización que emulan de cierta forma los conceptos de la evolución como la supervivencia y la reproducción postulados por Charles Darwin. En este documento se muestra el diseño y la implementación de un algoritmo genético que logra resolver el problema planteado en tiempos muy razonables y con una muy buena calidad de las soluciones reflejada en el bajo porcentaje de choques horarios. Se concluye que los algoritmos genéticos son una alternativa muy rápida y confiable para los problemas de optimización.

Busca encontrar modelos utilizando el método de los k−vecinos más próximos con el propósito de clasificar las 31 Cortes Superiores de Justicia del País y poder realizar predicciones para futuras Cortes Superiores de Justicia. Verifica la validez del modelo de clasificación y predicción de las Cortes Superiores de Justicia basado en el método de los k-vecinos más próximos. Verifica la precisión del modelo de k-vecinos más próximo cuando se tiene muestras pequeñas de entrenamiento y reserva. Experimenta los modelos que identifica y evalúa las 31 Cortes Superiores de Justicia, respecto de los predictores en forma a priori. Encuentra un modelo de agrupamiento jerárquico basado en encadenamiento simple para asociar las Cortes Superiores de Justicia del País en conglomerados. / Tesis

Estendemos o trabalho de Vincent Rijmen e Joan Daemen na estratégia de trilha larga, uma metodologia de projeto para primitivas criptográficas simétricas eficientes e demonstravelmente resistentes às técnicas de criptanálise diferencial e linear. Preocupamo-nos principalmente com a melhoria na eficiência de primitivas projetadas de acordo com a estratégia de trilha larga. Investigamos duas linhas distintas de pesquisa: a aplicabilidade da técnica de bitslicing à implementação em software de primitivas baseadas na estratégia de trilha larga; e o projeto de S-boxes estruturadas com implementação eficiente em hardware e bitslicing, e especificamente, o uso de S-boxes invariantes por rotação, que exibem propriedades vantajosas para implementação. Também implementamos e otimizamos algumas primitivas criptográficas em plataformas de software selecionadas, para substanciar e aprimorar as afirmações de eficiência da estratégia de trilha larga. Ademais, aplicamos nosso conhecimento e técnicas propostas ao projeto de novas primitivas criptográficas altamente eficientes, em particular a função de hash MAELSTROM-0 e a cifra de bloco legada FUTURE. / We extend the work of Vincent Rijmen and Joan Daemen on the Wide Trail strategy, a design methodology for symmetric-key cryptographic primitives which are efficient and provably secure against differential and linear cryptanalysis. We concern ourselves mainly with improving the efficiency of primitives designed according to the Wide Trail strategy. To that end, we investigate two distinct lines of research: the applicability of the bitslicing technique to the software implementation of primitives based on the Wide Trail strategy; and the design of structured S-boxes with efficient implementation in hardware and bitslicing, and specifically, the use of rotation-symmetric S-boxes, which exhibit advantageous implementation properties. We also perform general implementation and optimization work on selected software platforms, to further realize the claims of efficiency of the Wide Trail strategy. Additionally, we apply our expertise and proposed techniques to the design of new highly-efficient cryptographic primitives, in particular the hash function MAELSTROM-0 and the legacy-level block cipher FUTURE.