Nesta dissertação de mestrado estudamoscódigos Reed-Solomon. Começamos fazendo uma revisão sobre extensões de corpos finitos, focando na maneira de representar e operar com os seus elementos, e também sobre teoria de códigos, explorando os códigoslineares e os códigos cíclicos. Apresentamos as duas construções dos códigos de Reed-Solomon, a original, com a imagem de uma função polinomial, e a descoberta por Gorenstein e Zierler, como o ideal gerado por um polinômio gerador. Terminamos mostrando um algoritmo devido a Gao que mostra como decodificar palavras código de Reed-Solomon codificadas de maneira não sistemática. / In this dissertation we study Reed-Solomon codes. We begin with a review about extensions of finite fields, focusing on the way to represent and operate with its elements, and also about the theory os codes, exploting a few propertiesof linear codes and codes cyclic. We present two constructions of Reed-Solomon codes, the original, as the image os a polynomial function, and the discovery by Gorenstein and Zierler, as the ideal generated by a polynomial generator. Finished showing an algorithm due to Gao that shows how to decode Reed-Solomon code words coded in a nonsystematic way.

A abordagem Bayesiana na inferência estatística tem sido muito utilizada como uma alternativa aos métodos clássicos. Neste trabalho, apresentamos uma abordagem Bayesiana para a estimação dos parâmetros dos modelos autoregressivos de médias móveis de ordens p e g, denotados por ARMA(p, q) e do modelo autoregressivo fracionariamente integrado de médias móveis, denotado por ARFIMA(p, d, q). Para o último modelo, a abordagem Bayesiana é realizada assumindo p = g = 0. Considerando o modelo AR(p), que é um caso particular do modelo ARMA(p, g) onde g = O, um estimador é proposto através da abordagem Bayesiana. A eficiência do estimador é verificada através de simulações de Monte Cario e os resultados são comparados com o método clássico da máxima verossimilhança. No caso do modelo ARFIMA(0, d, 0), um estudo teórico é realizado através de uma abordagem Bayesiana. Para estimar os parâmetros desse modelo, é utilizada a sua representação autoregressiva. Alguns algoritmos computacionais Bayesianos são apresentados nesse trabalho já que desempenham um papel importante na inferência Bayesiana. Alguns desses algoritmos, como o amostrador de Gibbs e o Metropolis-Hastings, foram utilizados na construção dos estimadores para os parâmetros dos modelos ARMA e ARFIMA. / The Bayesian approach in statistical inference has been widely used as an alternative to traditional methods. In this work, we present a Bayesian approach for estimating the parameters of the autoregressive moving average processes of orderp and q, denoted by ARMA(p, g) and of the autoregressive fractionally integrated moving average process, denoted by ARFIMA(p, d, g). For the later model, the Bayesian approach is performed assuming p = g = 0. Whereas AR(p), which is a particular case of the ARMA(p, g) model when g = O, an estimator is proposed via the Bayesian approach. The efficiency of the estimator is verified by Monte Cario simulations and the results are compared with the classical maximum likelihood estimator. In the case of ARFIMA(0, d, 0) process, a theoretical study is performed by the Bayesian approach. For estimating the parameters of that process we consider its infiriite autoregressive representation. Some Bayesian computational algorithms are presented in this work since they play an important role in Bayesian inferences. Some of these algorithms, such as Gibbs sampler and Metropolis-Hastings algorithm, were used in building the estimators for the parameters of ARMA and ARFIMA models.

Este trabalho descreve a área de processamento matricial, mostrando os principais compromissos existentes na obtenção de arquiteturas paralelas a partir de algoritmos, para que haja um ganho real na avaliação destes. São feitas, ainda, considerações sobre ferramentas de programação para arquiteturas paralelas. Os principais compromissos que influenciam as arquiteturas SIMD, objeto de estudo deste trabalho, são abordados analisando-se uma áera de aplicação de arquiteturas SIMD: tratamento de imagens. Como uma caso prático de estudo e exemplo destes compromissos, é proposta uma arquitetura SIMD para um processador matricial empregando um chip matricial disponível comercialmente - o GAPP (Geometric Arithmetic Parallel Processor). É proposto, ainda, um ambiente para o desenvolvimento de programas nesta arquitetura. Este ambiente é baseado na utilização da lingaugem GAL (GAPP Algorithm Language), criada especificamente para elaboração de programas para o GAPP. / This work describes the array processing area, discussing the main tradeoffs in the design of parallel architecture from algorithms. The algorithm to architecture transformation is called a mapping problem. Some considerations about progamming tools for parallel architectures are also made. The relationship between algorithms and architectures is covered by studying a specific case for SIMD architectures: digital image processing. A SIMD architecture proposal, using a commercially available chip array - GAPP (Geometric Arithmetic Parallel Processor) is made. This architecture is used on a practical case to study and analyze those tradeoffs. An environment for program development for this architecture is also proposed. This environment is based on the use of GAL language (GAPP Algorithm Language), which was created specificaly for GAPP program development.

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.

Las empresas de hoy se ven en la necesidad de analizar su información para la correcta y oportuna toma de decisiones, la cual ayuda a encaminarla hacia los objetivos planteados. En el caso del grupo empresarial Leoncito con respecto a su toma de decisiones en su proceso de ventas se pudo identificar que para obtener información solicitada existía una demora de hasta 2 días, se desconocía el comportamiento de sus ventas en el tiempo, no contaban con reportes que permitan monitorear metas establecidas, no analizaban sus ventas desde diferentes perspectivas de negocio. Y además no se explotaban los datos históricos de la empresa. La presente tesis se desarrolló para apoyar la toma de decisiones en el proceso de ventas del grupo empresarial Leoncito mediante la implementación de un sistema de inteligencia de negocios utilizando algoritmo de serie temporal. Se utilizó la metodología Ralph Kimball y se usaron las herramientas Microsoft. El resultado que se obtuvo fue un sistema que logró disminuir el tiempo promedio que tomaba la obtención de información sobre ventas, generó reportes los cuales brindaron información analítica desde diferentes perspectivas, además se hicieron proyecciones para sus ventas; para las cuales se empleó el algoritmo de serie temporal. / Tesis

Dissertação (mestrado)—Universidade de Brasília, Faculdade de Tecnologia, Departamento de Engenharia Elétrica, 2014. / Submitted by Larissa Stefane Vieira Rodrigues (larissarodrigues@bce.unb.br) on 2014-11-28T18:54:24Z No. of bitstreams: 1 2014_DiogoAndrade.pdf: 6416367 bytes, checksum: abaa3ef1a99fc484bd009e4049175ff7 (MD5) / Approved for entry into archive by Raquel Viana(raquelviana@bce.unb.br) on 2014-12-01T17:30:23Z (GMT) No. of bitstreams: 1 2014_DiogoAndrade.pdf: 6416367 bytes, checksum: abaa3ef1a99fc484bd009e4049175ff7 (MD5) / Made available in DSpace on 2014-12-01T17:30:24Z (GMT). No. of bitstreams: 1 2014_DiogoAndrade.pdf: 6416367 bytes, checksum: abaa3ef1a99fc484bd009e4049175ff7 (MD5) / Neste trabalho, foi desenvolvido um algoritmo de síntese de circuitos translineares, útil para converter polinômios multivariável adimensionais, incluindo equações diferenciais lineares e não-lineares, em um ou mais polinômios translineares implementáveis em circuitos translineares. Circuitos translineares podem ser utilizados para realizar processamento de sinais inteiramente no domínio analógico e em modo-corrente, dispensando conversão analógica-digital, permitindo o desenvolvimento de circuitos de baixíssimo consumo de energia e de baixíssima tensão de alimentação. Este algoritmo e outro encontrado na literatura são implementados em uma ferramenta computacional, e são comparados em termos de eficácia e eficiência. O algoritmo desenvolvido neste trabalho mostrou-se mais eficiente e mais eficaz que o outro em alguns casos. O algoritmo também foi validado ao ser aplicado em polinômios utilizados em circuitos translineares publicados, e as realizações utilizadas nestes trabalhos foram encontradas pelo algoritmo. A ferramenta computacional foi implementada utilizando linguagem de programação “C”, e não depende de pacotes de software proprietários. Seu código fonte foi disponibilizado gratuitamente sob a licença geral pública “GNU v.3”. _________________________________________________________________________________ ABSTRACT / In this work, a Translinear circuit synthesis algorithm, useful to convert a generic dimensionless multivariate polynomial, including linear and non-linear differential equations, into one or more translinear polynomials that can be realized onto a Translinear Circuit was developed. Translinear circuits allow current-mode signal processing entirely into the analog domain, dispensing analog-to-digital conversion, resulting in ultralow power and ultra low-voltage signal processing circuits. This algorithm and another one found in the literature are implemented into a computer tool, and they are both compared regarding their efficiency and effectiveness. The developed algorithm was shown to be more effective and more efficient than the other in some cases. The algorithm was also validated by being applied to polynomials used in published Translinear circuits implementations, and the circuit realizations found in those works were also found by this algorithm. The computer tool was implemented using “C” programming language, and it is not dependent on any proprietary software package. Its source code is freely available under the GNU General Public License v.3.

Dissertação (mestrado)—Universidade de Brasília, Departamento de Engenharia Elétrica, 2011. / Submitted by Jaqueline Ferreira de Souza (jaquefs.braz@gmail.com) on 2012-06-15T13:50:39Z No. of bitstreams: 1 2012_LuisFilipedaCruzNassif.pdf: 2383961 bytes, checksum: da0b72387006c228c284836d695f4629 (MD5) / Approved for entry into archive by Jaqueline Ferreira de Souza(jaquefs.braz@gmail.com) on 2012-06-15T13:50:55Z (GMT) No. of bitstreams: 1 2012_LuisFilipedaCruzNassif.pdf: 2383961 bytes, checksum: da0b72387006c228c284836d695f4629 (MD5) / Made available in DSpace on 2012-06-15T13:50:55Z (GMT). No. of bitstreams: 1 2012_LuisFilipedaCruzNassif.pdf: 2383961 bytes, checksum: da0b72387006c228c284836d695f4629 (MD5) / Em análises periciais de computadores, usualmente são examinados centenas de milhares de arquivos. Grande parte dos dados desses arquivos é constituída por texto não estruturado, cuja análise por parte dos peritos é difícil de ser realizada. Nesse contexto, o uso de métodos automatizados de análise baseados na mineração de textos é de grande interesse. Particularmente, algoritmos de agrupamento podem facilitar a descoberta de conhecimentos novos e úteis nos textos sob análise. Este trabalho apresenta uma abordagem para aplicar agrupamento de documentos em análises periciais de computadores apreendidos durante investigações policiais. Para ilustrar tal abordagem, foi realizado um estudo comparativo de seis algoritmos de agrupamento de dados (K-means, K-medoids, Single Link, Complete Link, Average Link e CSPA) aplicados a cinco bases de dados textuais provenientes de investigações reais. Foram realizados experimentos utilizando-se diferentes combinações de parâmetros, totalizando dezoito instanciações diferentes dos algoritmos. Adicionalmente, dois índices de validade relativos (Silhueta e sua versão simplificada) foram utilizados para estimar automaticamente o número de grupos. Estudos relacionados encontrados na literatura se mostram significativamente mais limitados do que o estudo aqui apresentado, especialmente ao se considerar a variedade de algoritmos utilizados e a estimativa automática do número de grupos. Nesse contexto, o presente estudo poderá servir como ponto de partida para aqueles interessados em desenvolver pesquisas neste domínio de aplicação específico. Além disso, os experimentos realizados mostram que os algoritmos hierárquicos Average Link e Complete Link proporcionaram os melhores resultados. Os algoritmos particionais K-means e K-medoids, quando adequadamente inicializados, apresentaram resultados similares àqueles obtidos pelos algoritmos hierárquicos. Este estudo também apresenta e discute diversos resultados práticos mais específicos que podem ser úteis para pesquisadores e praticantes de análises forenses computacionais. ______________________________________________________________________________ ABSTRACT / In computer forensic analysis, hundreds of thousands of files are usually analyzed. Most of the data available in these files consists of unstructured text that are hard to be analyzed by human beings. In this context, the use of automated techniques, based on text mining, is of great relevance. In particular, clustering algorithms can help to find new, useful, and potentially actionable knowledge from text files. This work presents an approach that applies document clustering algorithms to forensic analysis of computers seized in police investigations. It was carried out a comparative study of six clustering algorithms – Kmeans, K-medoids, Single Link, Complete Link, Average Link and CSPA – when applied to five textual databases derived from real cases. A variety of experiments, using different combinations of parameter values, have been performed by running 18 different instantiations of the algorithms under study. In addition, two relative validity indexes for automatically estimating the number of groups – the Silhouette index and its simplified version – have been empirically assessed. To the best of our knowledge, studies of this nature, especially considering a variety of different clustering algorithms and the automatic estimation of the number of clusters, have not been reported in the literature about computer forensics. This study can thus serve as a starting point for researchers interested in developing further research in this particular application domain. In brief, the experiments performed on five real-world datasets show that the hierarchical algorithms known as Average Link and Complete Link provided the best performances. The partitional algorithms K-means and K-medoids, when appropriately initialized, have shown similar performances to those hierarchical algorithms. This study also presents and discusses several practical results for both researchers and practitioners of computer forensic analysis

Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, Programa de Pós-Graduação em Informática, 2013. / Submitted by Albânia Cézar de Melo (albania@bce.unb.br) on 2013-04-24T13:40:56Z No. of bitstreams: 1 2013_FernandoMachadoMendonca.pdf: 1941126 bytes, checksum: 14c4673df9cda4875e23e0c924101558 (MD5) / Approved for entry into archive by Guimaraes Jacqueline(jacqueline.guimaraes@bce.unb.br) on 2013-04-26T14:02:39Z (GMT) No. of bitstreams: 1 2013_FernandoMachadoMendonca.pdf: 1941126 bytes, checksum: 14c4673df9cda4875e23e0c924101558 (MD5) / Made available in DSpace on 2013-04-26T14:02:39Z (GMT). No. of bitstreams: 1 2013_FernandoMachadoMendonca.pdf: 1941126 bytes, checksum: 14c4673df9cda4875e23e0c924101558 (MD5) / Quando uma nova sequência biológica é descoberta, suas características funcionais e estruturais devem ser estabelecidas. Para isso, a sequência é comparada com outras sequências, procurando por similaridades. A comparação de sequências é, então, uma das operações básicas em Bioinformática. O algoritmo mais preciso para executar compara- ções é o proposto por Smith-Waterman (SW), que é baseado em programação dinâmica e possui complexidade quadrática de tempo e espaço. Essa complexidade pode facilmente levar a um alto tempo de execução e uso de memória. Técnicas de processamento paralelo podem ser utilizadas para produzir resultados em menos tempo. Existem muitas versões paralelas do algoritmo SW na literatura que se executam em multicores, GPUs, FPGAs e CellBEs. Mesmo que existam algumas abordagens que executem o algoritmo SW em plataformas híbridas compostas por GPUs e multicores, elas alocam trabalho de forma xa, baseada no desempenho teórico das unidades de processamento ou nos resultados obtidos por benchmarks. Essa dissertação de Mestrado propõe e avalia uma estratégia otimizada e exível para executar o algoritmo SW em plataformas híbridas compostas por GPUs e multicores com extensões SIMD. A nossa estratégia fornece múltiplas polí- ticas de alocação de tarefas e o usuário pode escolher a que é mais apropriada para o seu problema. Propomos também um mecanismo de re-trabalho que trata situações que ocorrem quando nodos mais lentos recebem as últimas e maiores tarefas. Os resultados obtidos comparando sequências de busca com cinco diferentes bancos de dados genômicos em uma plataforma composta por 4 GPUs e 2 multicores mostram que a nossa aborda- gem é capaz de reduzir o tempo de execução em plataformas híbridas, quando comparada com soluções que utilizam apenas GPUs. Mostramos também que o nosso mecanismo de re-trabalho pode melhorar signi cativamente o desempenho na plataforma utilizada. ______________________________________________________________________________ ABSTRACT / Once a new biological sequence is discovered, its functional and structural characteris- tics must be established. In order to do that, the newly discovered sequence is compared against other sequences, looking for similarities. Sequence comparison is, therefore, one of the most basic operations in Bioinformatics. The most accurate algorithm to execute pairwise comparisons is the one proposed by Smith-Waterman (SW), which is based on dynamic programming, with quadratic time and space complexity. This can easily lead to very high execution times and huge memory requirements. Parallel processing can be used to produce results faster, reducing signi cantly the time needed to obtain results with the SW algorithm. There are many parallel versions of SW in the literature, which run in multicores, GPUs, Field-Programmable Gate Arrays (FPGAs) and CellBEs. Even though there are some versions of SW that run on hybrid platforms composed of GPUs and multicores, they assign work in a xed way, based on the theoretical performance of the processing units or in the results obtained by some benchmarks. This MsC Disser-tation proposes and evaluates a exible and optimized strategy to run Smith-Waterman applications in hybrid platforms composed of GPUs and multicores with SIMD extensions. Our strategy provides multiple task allocation policies and the user can choose the one which is more appropriate to his/her problem. We also propose a workload adjustment mechanism that tackles situations that arise when slow nodes receive the last tasks. The results obtained comparing query sequences to 5 public genomic databases in a platform composed of 4 GPUs and 2 multicores show that we are able to reduce the execution time with hybrid platforms, when compared to the GPU-only solution. We also show that our workload adjustment technique can provide signi cant performance gains in our target platform.

Dissertação (mestrado)—Universidade de Brasília, Faculdade de Tecnologia, Departamento de Engenharia Elétrica, 2008. / Submitted by Luana Patrícia de Oliveira Porto (luana_porto_23@hotmail.com) on 2010-03-11T17:16:29Z No. of bitstreams: 1 2008_MaximiraCarlotaCorrea.pdf: 1987262 bytes, checksum: 74c24d8124f981e6b103a304b3a8a60e (MD5) / Approved for entry into archive by Lucila Saraiva(lucilasaraiva1@gmail.com) on 2010-04-06T20:27:38Z (GMT) No. of bitstreams: 1 2008_MaximiraCarlotaCorrea.pdf: 1987262 bytes, checksum: 74c24d8124f981e6b103a304b3a8a60e (MD5) / Made available in DSpace on 2010-04-06T20:27:38Z (GMT). No. of bitstreams: 1 2008_MaximiraCarlotaCorrea.pdf: 1987262 bytes, checksum: 74c24d8124f981e6b103a304b3a8a60e (MD5) Previous issue date: 2008-08 / Nos últimos anos observou-se um aumento considerável no uso de redes de comunicação de dados. Quanto mais pessoas fazem uso das redes de computadores e quanto maior o número de serviços que estão sendo prestados nestas redes, mais é necessário garantir que a rede esteja disponível para o uso de seus clientes. Este trabalho visa propor um método para avaliação e cálculo da disponibilidade em redes IP, de forma que as prestadoras de serviço de comunicação de dados disponham de uma ferramenta segura de análise da variação da disponibilidade da rede quando a mesma sofre alterações e/ou falhas. Este trabalho foi dedicado às redes IP e seu foco será o calculo da disponibilidade entre dois pontos A e B quaisquer.A revisão bibliográfica, além de contextualizar o assunto de redes de computadores, irá focar na teoria da decomposição de espaço de estados. Depois será descrito o algoritmo proposto e sua implementação em linguagem Perl. Então serão apresentados os testes realizados nos trechos selecionados das redes em estudo.Na conclusão deste trabalho foi validado o método proposto para o cálculo de disponibilidade em redes IP. __________________________________________________________________________________________ ABSTRACT / In recent years there was a considerable growth in computer networks applications. The more people use computer networks and the greatest the number of services these networks provide the greatest the necessity to make sure the network is available for its clients to use. This work comes to provide the means to evaluate e calculate the availability of IP networks in order to offer the communication service provides a secure tool for the analysis of the network availability variation when the network is altered or fail. This work will be dedicated to the analysis of IP networks and its scope is the evaluation of the availability between two given points A and B. The bibliography review will contextualize the matter of computer networks, with focus in the Theory of State Space Decomposition. Then the algorithm will be described with its implementation in Perl programming language. Last, the tests performed in selected parts of the network will be presented. At the conclusion of this work the provided method for availability calculus in IP networks is valid was considered valid.

Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2009. / Submitted by Allan Wanick Motta (allan_wanick@hotmail.com) on 2010-07-16T19:38:07Z No. of bitstreams: 1 2009_LidiaAraujoMiranda.pdf: 5472186 bytes, checksum: 3bc128515fab954a95e110f39e6c356c (MD5) / Approved for entry into archive by Lucila Saraiva(lucilasaraiva1@gmail.com) on 2010-07-19T14:24:14Z (GMT) No. of bitstreams: 1 2009_LidiaAraujoMiranda.pdf: 5472186 bytes, checksum: 3bc128515fab954a95e110f39e6c356c (MD5) / Made available in DSpace on 2010-07-19T14:24:14Z (GMT). No. of bitstreams: 1 2009_LidiaAraujoMiranda.pdf: 5472186 bytes, checksum: 3bc128515fab954a95e110f39e6c356c (MD5) Previous issue date: 2009 / O Alinhamento Múltiplo de Sequências genéticas (AMS) é executado milhares de vezes ao dia por cientistas, a fim de identificar regiões de semelhança entre três ou mais sequências. Os alinhamentos múltiplos assim obtidos são usados na resolução de problemas complexos, como a determinação do histórico evolutivo das espécies. Por se tratar de um problema NP-completo, geralmente são utilizadas soluções heurísticas para a sua resolução. Dentre soluções adotadas, destaca-se o Algoritmo Genético (AG), que é um método iterativo não-determinístico, baseado nos princípios da Evolução das Espécies de Darwin. Apesar de apresentar soluções boas para o AMS, os algoritmos genéticos demandam um alto poder de processamento, que se traduz em um alto tempo de execução. Por essa razão, algumas estratégias paralelas foram propostas na literatura para acelerar a obtenção de alinhamentos múltiplos com AGs, geralmente utilizando a estratégia da ilha como base de paralelização. A presente dissertação de mestrado propõe e avalia uma estratégia paralela que utiliza Algoritmo Genético para o Alinhamento Múltiplo de Sequências, inspirada no modelo Multi-ilha. De maneira diferente das abordagens para AMS existentes na literatura, a estratégia proposta utiliza 3 Super Ilhas, onde cada Super Ilha implementa um modelo tradicional de ilhas. Os resultados obtidos com bases reais de proteínas mostram que a estratégia proposta é capaz de encontrar alinhamentos múltiplos de melhor qualidade em menor tempo, quando comparada com a estratégia de ilha tradicional. _______________________________________________________________________________ ABSTRACT / The Multiple Sequence Alignment (MSA) between genetic sequences is exhaustively done by scientists trying to identify matching regions within three or more sequences. The resulting multiple alignments are used in complex problems like the one of establishing genetic relationships between biological sequences. The MSA has been shown to be an NP-complete problem, therefore heuristic solutions are usually used to solve it. One of the solutions that has shown good results for MSA is the Genetic Algorithm (GA), a non deterministic iterative method, based on Charles Darwin's theory of evolution. Though presenting good results, the GA demands high amount of computing power, taking usually a lot of time to be executed. To speed up the sequential algorithms execution, parallel algorithms were proposed in the literature, most of them using the island strategy of parallelization. This masters dissertation proposes and evaluates a parallel strategy that uses Genetic Algorithms to the Multiple Sequence Alignment based on the Multi-island parallelization strategy. Di erently from other MSA strategies, the proposed strategy creates three Super Islands and each one executes a GA parallelized by the island strategy. The results were obtained with real protein banks and revealed that the proposed strategy is capable of nding better multiple alignments in a smaller amount of time, when compared to the conventional island strategy.