Tese (doutorado) - Universidade Federal de Santa Catarina, Centro Tecnológico, Programa de Pós-Graduação em Engenharia Elétrica, Florianópolis, 2016. / Made available in DSpace on 2017-05-02T04:12:13Z (GMT). No. of bitstreams: 1 345510.pdf: 8179542 bytes, checksum: c7d616d9dbca1730bc9064d7782ee7f2 (MD5) Previous issue date: 2016 / Este trabalho de pesquisa trata da modelagem estocástica de dois algoritmos adaptativos bem conhecidos na literatura, a saber: o algoritmo FxLMS (filtered x least mean square) e o algoritmo NLMS (normalized least mean square). Particularmente, para o algoritmo FxLMS são desenvolvidos dois modelos estocásticos, ambos considerando aplicações de controle e/ou equalização ativa de ruído periódico, porém em diferentes estruturas (monocanal e multicanal). Baseado nas expressões de modelo obtidas, diversos aspectos do comportamento do algoritmo FxLMS são discutidos, evidenciando o impacto dos parâmetros do algoritmo sobre seu desempenho. Para o algoritmo NLMS, são propostos dois modelos estocásticos, ambos considerando a aplicação de identificação de sistemas tanto com sinal de entrada branco gaussiano quanto correlacionado gaussiano. Especificamente, o primeiro modelo do algoritmo NLMS é derivado assumindo que o filtro adaptativo e a planta a ser estimada podem possuir ordens diferentes (tal suposição, que é condizente com cenários práticos, não é usualmente tratada na literatura devido às dificuldades matemáticas surgidas no desenvolvimento da modelagem estocástica). O segundo modelo do algoritmo NLMS considera uma formulação matemática mais geral (quando comparada a outros trabalhos da literatura) para representar a planta a ser identificada, possibilitando a representação de diversos tipos de sistemas variantes no tempo; originando, assim, um modelo estocástico capaz de predizer o comportamento do algoritmo NLMS em uma ampla gama de cenários de operação. Resultados de simulação são apresentados, ratificando a precisão dos modelos estocásticos propostos, tanto na fase transitória quanto em regime permanente.<br> / Abstract : This research work focuses on the stochastic modeling of two well-known adaptive algorithms from the literature, namely: the filtered x least mean square (FxLMS) algorithm and the normalized least mean square (NLMS) algorithm. In particular, for the FxLMS algorithm two stochastic models are developed, both considering applications of active noise control and equalization of periodic noise, but in different structures (single channel and multichannel). Based on the obtained expressions, several aspects of the FxLMS algorithm behavior are discussed, highligting the impact of some parameters on the algorithm performance. For the NLMS algorithm, two stochastic models are proposed, both considering the application of system identification with white Gaussian and correlated Gaussian input signals. Specifically, the first model of the NLMS algorithm is developed assuming that the adaptive filter and the system to be identified can have different orders (such a supposition, which is consistent with practical scenarios, is not usually considered in the literature due to the mathematical difficulties ariasing in the development of the stochastic model). The second model of the NLMS algorithm considers a more general mathematical formulation (compared with other works from the open literature) to represent the system to be identified, allowing to represent several types of time varying systems; resulting in a stochastic model able to predict the NLMS algorithm behavior in several scenarios. Simulation results are presented, confirming the accuracy of the proposed stochastic models for both transient and steady state phases.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico, Programa de Pós-Graduação em Engenharia Elétrica, Florianópolis, 2016. / Made available in DSpace on 2017-05-02T04:12:34Z (GMT). No. of bitstreams: 1 345228.pdf: 2456245 bytes, checksum: 8a93eaf6ebf886bec3c4c85de820db74 (MD5) Previous issue date: 2016 / O constante aumento da complexidade de sistemas embarcados requer um processo de verificação capaz de acompanhar esse crescimento e ser capaz de assegurar o correto funcionamento do sistema projetado, especialmente se tratando de aplicações críticas que lidem com vidas humanas ou com grandes investimentos. Esta responsabilidade por parte das companhias que desenvolvem tais sistemas faz com que a verificação se torne a parte mais importante no projeto de um sistema, consumindo a maior parte dos seus recursos, tanto em questão de tempo quanto financeiramente. A verificação realizada através de simulações requer a participação de um engenheiro de verificação analisando os resultados e com base nestes, modificando parâmetros para gerar novos testes. Neste trabalho é apresentada uma abordagem para uso de Algoritmos Genéticos no processo de verificação, de forma a automatizar a geração de novos vetores de teste. Esta abordagem analisa os resultados com base nas métricas de verificação definidas durante a fase de planejamento do projeto, e com estas informações gera novos testes que contribuam para a validação do sistema, adaptando-se ao funcionamento do sistema e aos resultados de cada nova iteração do processo de verificação.<br> / Abstract : The growing increase in embedded systems complexity requires a verification process to be able to follow this trend while capable of assuring the correctness of the designed system, especially on critical applications that deal with human lives, or big financial investments. This responsibility incurred by these system's developers makes verification the most important step in designing an embedded system, considering both development time and money. Simulation-based verification requires an engineer's work by analyzing results and creating new test vectors relevant to the process. In this work an approach for automating test vector generation through Genetic Algorithms is presented. This approach analyzes test results based on predefined verification metrics and, with this information creates new tests that aim on advancing the verification process to reach a better system validation, adapting itself to the design and its results at each step of the process.

Dissertação (mestrado) - Pontifícia Universidade Católica do Paraná, Curitiba, 2008 / Bibliografia: f 63-66. / Neste trabalho apresentamos um estudo que visa reduzir o erro na identificação de falsificações em sistemas de verificação de assinaturas off-line através do agrupamento de classificadores (ensembles). Num total, quatro características (Distribuição de Pi / In this work we discuss the use of ensemble of classifiers based on graphometric features to improve the reliability of the classification, hence reducing the false acceptance for signature verification systems. The ensemble was built using a standard gen

Dissertação (mestrado) - Pontifícia Universidade Católica do Paraná, Curitiba, 2005 / Inclui bibliografia / O crescimento exponencial da Web e a conseqüente necessidade de diminuir a sobrecarga dos servidores tornam altamente crítica a tarefa de substituição de objetos em cache. Neste trabalho é apresentada uma nova estratégia de substituição de objetos em cach

Dissertação (mestrado) - Pontifícia Universidade Católica do Paraná, Curitiba, 2011 / Bibliografia: p. 83-89 / Uma das técnicas mais eficientes para manipular o problema de concept drift em tarefas de classificação em ambientes dinâmicos e instáveis é a técnica que utiliza conjunto de classificadores. Na literatura encontram-se várias metodologias para a construçã / One of the most effective techniques for dealing with the problem of concept driftin Classification tasks in dynamic environments is the one that uses sets os classifiers. There are several methodologies described in the scientific literature for the co

Dissertação (mestrado) - Pontifícia Universidade Católica do Paraná, Curitiba, 2004 / Inclui bibliografia / O desenvolvimento constante de técnicas de reconhecimento de padrões, de técnicas de extração de primitivas, implementações de algoritmos genéticos e a utilização de força bruta oferecida pela utilização de redes neurais permitem a resolução de problemas / The pattern recognition techniques, feature extraction techniques, genetic algorithms implementation and brute force offered by neural nets allows to solve classification tasks more complex. These facilities allow the use of more complex features groups.

Submitted by Marco Antônio de Ramos Chagas (mchagas@ufv.br) on 2017-08-22T12:50:56Z No. of bitstreams: 1 texto completo.pdf: 2002096 bytes, checksum: 846f5e7b160234fc5880c038b656d3f6 (MD5) / Made available in DSpace on 2017-08-22T12:50:56Z (GMT). No. of bitstreams: 1 texto completo.pdf: 2002096 bytes, checksum: 846f5e7b160234fc5880c038b656d3f6 (MD5) Previous issue date: 2017-03-07 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Este trabalho aborda o problema de flow shop scheduling não permutacional com trabalhadores heterogêneos (FSNPTH). Sendo este classificado como um problema multicomponente, uma vez que, combina dois problemas no qual o resultado de um afeta o outro. O FSNPTH é composto por dois problemas clássicos de otimização combinatória: alocação de trabalhadores em máquinas e o flow shop scheduling não permutacional (FSNP). O problema consiste em alocar trabalhadores hete- rogêneos em máquinas dispostas em série, na qual a heterogeneidade se dá pelo tempo gasto pelo trabalhador ao operar uma máquina. A alocação dos trabalha- dores definem os tempos de execução das tarefas do problema de FSNP. O objetivo do problema de FSNPTH é minimizar o tempo máximo de conclusão das tarefas, conhecido como makespan. Para resolve-lo, inicialmente é proposto a aplicação do método Proximity Search (PS) para tentar determinar soluções ótimas para o pro- blema utilizando o modelo de programação linear inteira mista 0-1 (PLIM). Esse método consiste em substituir a função objetivo por uma função de proximidade e adicionar uma restrição de corte no modelo. Iterativamente o novo modelo é resolvido e a restrição de corte é atualizada. Isso garante que PS limite o espaço de busca e identifique as soluções ótimas. Foram desenvolvidas três versões do PS denotadas por P S 1 , P S 2 e P S 2RIN S . Dado que o problema pertence à classe NP-Difícil e é considerado de difícil resolução de maneira exata, foram desenvolvi- dos dois algoritmos híbridos, VNS-IG e TS-IG, a fim de obter soluções de forma aproximada de alta qualidade em baixo tempo computacional. Esses algoritmos combinam as meta-heurísticas Variable Neighborhood Search (VNS) e Busca Tabu (TB, do inglês Tabu Search) com o Iterated Greedy (IG). Experimentos computa- cionais e análises estatísticas foram realizados a fim de comparar o desempenho das versões do PS e dos algoritmos propostos. De acordo com os experimentos computacionais, as versões do PS obtiveram melhorias na qualidade da solução obtida e redução no tempo computacional se comparado a resolução do modelo matemático pelo solver IBM ILOG CPLEX. Além disso os experimentos realiza- dos mostram que algoritmos propostos são significativamente superiores ao melhor algoritmo da literatura (Scatter Search) em relação a dois fatores: qualidade das soluções e tempo de execução. / The current work addresses the non-permutation flow shop scheduling problem with heterogeneous workers (Het-FSSP), which is defined as a multicomponent problem, since it combines two problems where the result of one affects the other. Het-FSSP consists of two classical combinatorial optimization problems: machine worker allocation and non-permutation flow shop scheduling (NPFSS). The pro- blem is to allocate heterogeneous workers in machines arranged in series, in which the heterogeneity is due to the time spent by the worker when operating a ma- chine. The allocation of workers defines the periods of execution of the jobs of the NPFSS problem. The goal of the Het-FSSP problem is to minimize the maximum job completion time, which is known as makespan. In order to solve this problem, it is initially proposed to apply the Proximity Search (PS) method to try to de- termine optimal solutions for the problem using mixed integer programing (MIP) model. This method consists of replacing the objective function with a proximity function and adding a cut-off constraint on the model. Then, by iteration, the new model is resolved and the cut restriction is updated. This ensures that PS limits the search space and identifies optimal solutions. Three PS versions denoted by P S 1 , P S 2 and P S 2RIN S have been developed. Since the problem belongs to the NP-Difficult class and is considered to be difficult to solve exactly, two hybrid algorithms, VNS-IG and TS-IG, were developed in order to obtain approximate solutions of high quality in low computational time. These algorithms combine the meta-heuristics Variable Neighborhood Search (VNS) and Tabu Search (TS) with Iterated Greedy (IG). Computational experiments and statistical analyzes were performed in order to compare the performance of PS versions and the proposed algorithms. The computational experiments results suggest that the PS versions acquired improvements in the quality of the solution obtained and also reduced computational time spent compared to the resolution of the mathematical model by the IBM ILOG CPLEX solver. In addition, the experiments performed have shown that the proposed algorithms are significantly superior to the best algorithm found in the literature (Scatter Search) in relation to two factors: solution quality and execution time.

Submitted by Reginaldo Soares de Freitas (reginaldo.freitas@ufv.br) on 2016-04-27T09:48:38Z No. of bitstreams: 1 texto completo.pdf: 1187966 bytes, checksum: 9ba7c5ee8c3eafbfbcf97aa8cf96eae5 (MD5) / Made available in DSpace on 2016-04-27T09:48:38Z (GMT). No. of bitstreams: 1 texto completo.pdf: 1187966 bytes, checksum: 9ba7c5ee8c3eafbfbcf97aa8cf96eae5 (MD5) Previous issue date: 2015-12-10 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Este trabalho aborda o problema de sequenciamento de tarefas em máquinas parale- las não-relacionadas considerando restrições de precedência entre as tarefas e tempos de preparação dependentes da sequência e da máquina. Este problema tem como objetivo minimizar o tempo máximo de conclusão do sequenciamento, conhecido como makespan. Em problemas que consideram restrições de precedência, nenhuma tarefa pode iniciar seu processamento sem que todas as suas tarefas predecessoras tenham sido concluídas. Para resolver este problema foram desenvolvidos três mo- delos de programação linear inteira mista (PLIM), denotados por Modelo 1, Modelo 2 e Modelo 3. Em seguida, sete heurísticas construtivas foram desenvolvidas, deno- tadas por HC1 a HC7, as quais se diferenciam pelas regras de prioridade utilizadas. Neste trabalho também é implementado o método chamado Proximity Search (PS), que tenta determinar soluções ótimas para o problema. O método PS precisa de uma solução inicial e de um modelo base de PLIM. Neste método a função objetivo do modelo é substituída por uma função de proximidade e o conjunto de soluções viáveis é reduzido através da adição de cortes. A ideia é, iterativamente, resolver o modelo com a tentativa de melhorar a solução corrente. Foram desenvolvidas três versões do PS denotadas por P S1, P S2 e P S2RIN S . Neste trabalho também foram desenvolvidos algoritmos baseados em meta-heurísticas a fim de resolver o problema de forma aproximada. Primeiramente, foram desenvolvidas duas buscas locais denotadas por BL1 e BL2 baseadas na estratégia de inserção por vizinhança. Em seguida, foram implementadas duas meta-heurísticas: GRASP (Greedy Ran- domized Adaptive Search) e IG (Iterated Greedy). Experimentos computacionais e análises estatísticas foram realizados a fim de comparar o desempenho dos modelos, das versões do P S e das heurísticas propostas. De acordo com os experimentos, o Modelo 1 apresentou-se mais eficiente na qualidade das soluções obtidas e a heurís- tica HC7 mostrou-se mais eficiente na geração de uma solução razoavelmente boa. Além disso, as versões do PS obtiveram melhorias na qualidade da solução obtida e redução no tempo computacional gasto se comparado ao Modelo 1. Em seguida, o IG obteve desempenho significativamente melhor que o GRASP e o PS em relação à qualidade da solução final e a velocidade com que a solução corrente é melhorada. / In this work we address the scheduling problem in unrelated parallel machine with precedence constraints between the jobs and sequence-dependent and machine- dependent setup times. The objective of this problem is to minimize the maximum completion time of sequence, called makespan. The precedence constraints force a job not to be started before all its predecessors are finished. To solve this problem, we developed three models of mixed integer programming (MIP), denoted by Model 1, Model 2 and Model 3. Next, seven constructive heuristics were developed, deno- ted by HC1 to HC7, which differ in the priority rules. Also in this work, a method called Proximity Search (PS) is implemented, which tries to find optimal solutions to the problem. The method requires an initial solution and a MILP-based model. In this method, the objective function of the model is replaced by a proximity func- tion and the set of feasible solutions is reduced by the addition of cuts. The idea is to iteratively solve the model trying to improve the current solution. We deve- loped three versions of the P S denoted by P S1, P S2 and P S2RIN S . In addition, we developed algorithms based on metaheuristics to solve the problem approxima- tely. First, were developed two local searches denoted by BL1 and BL2 based on the insertion neighborhood. Next, were implemented two metaheuristics: GRASP (Greedy Randomized Adaptive Search) and IG (Iterated Greedy). Computational experiments and statistical analyzes were performed in order to compare the per- formance of models, PS versions and heuristics. According to the experiments, the Model 1 is more efficient in the quality of solutions and the HC7 heuristic is more efficient in generating a reasonably good solution. In addition, the versions of the PS obtained improvements in the quality of the obtained solution and reduction in computational time spent compared to Model 1. Then, the IG obtained significantly better performance than the GRASP and PS in relation to the quality of the final solution and the speed with which the current solution is improved.

Submitted by Marco Antônio de Ramos Chagas (mchagas@ufv.br) on 2016-09-13T12:57:14Z No. of bitstreams: 1 texto completo.pdf: 716367 bytes, checksum: 3555ebb07d86905dcc01ee33b9bc59f9 (MD5) / Made available in DSpace on 2016-09-13T12:57:14Z (GMT). No. of bitstreams: 1 texto completo.pdf: 716367 bytes, checksum: 3555ebb07d86905dcc01ee33b9bc59f9 (MD5) Previous issue date: 2016-02-26 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / A cada dia mais dados são gerados das mais diversas fontes. A extração de conheci- mento das bases de dados torna-se cada vez mais desafiadora, visto que os processos utilizados não são triviais. O agrupamento de dados usa técnicas que são capa- zes de trabalhar com dados pouco conhecidos de forma não supervisionada. Essas técnicas dividem os dados em grupos tentando capturar a estrutura presente nos dados para obter um conhecimento que servirá de ponto inicial para seu estudo. Poucos algoritmos de agrupamentos conseguem trabalhar em um contexto escalá- vel. Um dos algoritmos mais influentes no agrupamento é o k -médias, que possui complexidade linear e duas fases bem distintas, facilmente adaptada para modelos escaláveis. Porém, k -médias possui limitações, como sensibilidade à inicialização e especificação do número de grupos k, que geralmente é desconhecido. O obje- tivo desta pesquisa é estudar e desenvolver algoritmos de agrupamento para este contexto escalável. Especificamente, procura-se trabalhar com meta-heurísticas que proporcionem o agrupamento escalável sem a necessidade de especificação do nú- mero de grupos k. Essa dissertação propõe dois novos algoritmos de agrupamento que encontram um valor para k automaticamente em um modelo escalável chamado MapReduce. Adicionalmente, foi estudado um algoritmo com o mesmo propósito encontrado na literatura. Todos os algoritmos foram desenvolvidos e comparados de duas maneiras: pela sua complexidade assintótica e através de experimentos em bases artificiais e reais. Com base em testes estatísticos, foi possível verificar as principais diferenças entre a performance dos algoritmos. / Everyday more data are generated from several sources. The knowledge extraction from datasets becomes more and more challenging as the applied techniques are not trivial. Data clustering techniques are able to work with little knowledge about the data in a totally unsupervised manner. These techniques divide data into clusters trying to capture the structure of the data to obtain knowledge that will serve as a starting point for further studies. Few clustering algorithms are able to work in a scalable scenario. One of the most influential clustering algorithms is k -means, which has linear asymptotic complexity and two distinct phases, which can be easily adapted for scalable models. However, k -means has limitations such as sensitivity to initialization and previous specification of the numbers of clusters k, which is generally unknown, specially for real world scenarios. The objective of this rese- arch is to study and develop scalable clustering algorithms. Specifically, the use of meta-heuristics for scalable clustering to automatically determine the number of k clusters. This dissertation proposes two new clustering algorithms that are able to automatically find the value k in a scalable programing model called MapRe- duce. Additionally, an state-of-art algorithm from the literature has been studied and compared. All algorithms were developed and compared in two ways: based on their asymptotic complexity and through experiments in artificial and real datasets. Based on statistical tests, is was possible to find the main differences among quality and performance of all compared algorithms.

Existem muitos sistemas de criptografia cuja segurança é baseada na dificuldade em resolver logaritmos discretos. Neste trabalho descrevemos alguns métodos para calcular logaritmos discretos, a saber: Algoritmo Shanks, Algoritmo Pollard, Algoritmo Silver-Pohlig-Hellman e o Algoritmo Index Calculus. Também são relatadas questões de complexidade computacional e os últimos recordes alcançados para resolver logaritmos discretos. / There are many cryptosystems whose security is based on the difficulty of solving the discrete logarithm. In this work, we describe some methods to calculate discrete logarithms: Shanks's Algorithm, Pollard's Algorithm, Silver-PohligHellman's Algorithm and the Index Calculus Algorithm. We also relate computation complexity issues and the last records that have been obtained on the discrete logarithm problem.