Exploramos o seguinte problema: dadas duas sequências X e Y sobre um alfabeto finito, encontre uma subsequência comum máxima de X e Y sem símbolos repetidos. Estudamos a estrutura deste problema, particularmente do ponto de vista de grafos e de combinatória poliédrica. Desenvolvemos algoritmos de aproximação e heurísticas para este problema. O enfoque deste trabalho está na construção de um algoritmo baseado na técnica branch-and-cut, aproveitando-nos de um algoritmo de separação eficiente e de heurísticas e técnicas para encontrarmos uma solução ótima mais cedo. Também estudamos um problema mais fácil no qual este problema é baseado: dadas duas sequências X e Y sobre um alfabeto finito, encontre uma subsequência comum máxima de X e Y. Exploramos este problema do ponto de vista de combinatória poliédrica e descrevemos vários algoritmos conhecidos para resolvê-lo. / We explore the following problem: given two sequences X and Y over a finite alphabet, find a longest common subsequence of X and Y without repeated symbols. We study the structure of this problem, particularly from the point of view of graphs and polyhedral combinatorics. We develop approximation algorithms and heuristics for this problem. The focus of this work is in the construction of an algorithm based on the branch-and-cut technique, taking advantage of an efficient separation algorithm and of heuristics and techniques to find an optimal solution earlier. We also study an easier problem on which this problem is based: given two sequences X and Y over a finite alphabet, find a longest common subsequence of X and Y. We explore this problem from the point of view of polyhedral combinatorics and describe several known algorithms to solve it.

Submitted by (ana.araujo@ufrpe.br) on 2016-08-10T13:00:13Z No. of bitstreams: 1 Rejane dos Santos Brito.pdf: 1642561 bytes, checksum: 084711a62c79f703133a032643c8d19f (MD5) / Made available in DSpace on 2016-08-10T13:00:13Z (GMT). No. of bitstreams: 1 Rejane dos Santos Brito.pdf: 1642561 bytes, checksum: 084711a62c79f703133a032643c8d19f (MD5) Previous issue date: 2009-03-20 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / We make a review about Edgeworth, Lugannani-Rice, Daniels and Cordeiro-Ferrari asymptotic approximations. We use the Cordeiro-Ferrari asymptotic approximation to approximate the gamma distribution G(m;f ) by the exponential distribution with mean a. In a further application, based on the statistical proposed by them, we approximate the t-Student distribution with n degrees of freedom using the normal standard distribution. Moreover, we realize a study about the functionalities of the beta generalized distributions. We obtain moments of the generalized beta distributions using the Lauricella and Kampé de Fériet generalized functions. Beyond this, we propose a new generalized beta distribution called beta power. Finally, we realize some applications in regression models by logistic regression and further more using discriminant analysis. / Inicialmente, realiza-se uma revisão literária sobre as expansões assintóticas de Daniels, Edgeworth, Lugannani-Rice e Cordeiro-Ferrari. Mediante uso da expansão de Cordeiro- Ferrari, torna-se possível realizar um estudo correspondente a aproximação da distribuição gama G(m;f ) em função da distribuição exponencial com média a. E, ainda, numa outra aplicação, faz-se a aproximação da distribuição t-Student com n graus de liberdade em função da distribuição normal padrão. Além disso, apresenta-se um estudo correspondente às funcionalidades das distribuições beta generalizadas e, ainda, a obtenção dos momentos das distribuições beta generalizadas mediante as funções de Lauricella e generalizada de Kampé de Fériet. Propõe-se, ainda, a generalização da distribuição power como sendo uma nova distribuição beta generalizada. Por fim, realizam-se algumas aplicações em modelos de regressão, mediante regressão logística, bem como em modelos de análise discriminante.

We have modeled some magnetic systems, which consists of a number of sublattices, in the mean field approximation. This is possible in crystalline systems formed by two or more magnetic ions coupled by specific interactions such as the crystal field, exchange, among others. The main idea is to solve the microscopic Hamiltonian that models a given magnetic system in order to obtain their magnetic equation of state: M (H, T). For this, we use the appropriate arrangements to different magnetic (ferro-, ferri- and antiferro- magnetic) scheme sublattices. From the solutions of the Hamiltonian (eigenvalues and eigenvectors), physical quantities of interest were determined. In principle we consider systems with localized magnetism due to 3d and 4f electrons with the participation of non-magnetic ligands including 3d-4f systems with the presence of crystal field. In this dissertation we use the model of two-and three sublattices in order to obtain the equation of state for the following systems: RKKY exchange in RNi2B2C, superexchange in (Y3-zRz)(T1xFe1-x)(T2yFe3-y)O12, LixFe3- xO4 and (NixMn1-x)1.5[Cr(CN)6]. In these formulas, R represents a rare earth ion, T1 and T2 represent non-magnetic ions. Some representative cases are presented to illustrate the different equations of state and behavior of sublattices, metamagnetism, temperature compensation, etc. The extension to other similar systems can be direct or need to incorporate additional phenomenological parameters. / Consideramos neste estudo sistemas magnéticos modeláveis mediante sub- redes na aproximação do campo médio. Isto é possível em sistemas cristalinos formados por dois ou mais íons magnéticos acoplados por interações específicas como as do campo cristalino, troca, entre outros. A ideia central é resolver o hamiltoniano microscópico que modela um determinado sistema magnético de maneira a se obter sua equação de estado magnética: M(H,T). Para isto usamos o esquema de sub- redes adequado a diferentes arranjos magnéticos (ferro-, ferri- e antiferro- magnéticos). Com as soluções do hamiltoniano (autovalores e autovetores), grandezas físicas de interesse foram determinadas. Em princípio, consideramos sistemas com magnetismo localizado devido a elétrons 3d e 4f com participação de ligandos não magnéticos incluindo sistemas 3d-4f com presença de campo cristalino. Neste trabalho de dissertação empregamos o modelo de duas e três sub- redes para obter as equações de estado nos seguintes sistemas: troca tipo RKKY em RNi2B2C, supertroca em (Y3-zRz)(T1xFe1-x)(T2yFe3-y)O12, LixFe3-xO4 e (NixMn1- x)1.5[Cr(CN)6]. Nestas fórmulas, R representa um íon de terra rara, T1 e T2 representam íons não magnéticos. Alguns casos representativos são apresentados para exemplificar as diferentes equações de estado e comportamento das sub- redes, metamagnetismo, temperatura de compensação etc. Em princípio, a extensão para outros sistemas semelhantes, usando os modelos apresentados aqui, pode ser direta ou precisar incorporar parâmetros fenomenológicos adicionais.

Submitted by Fabio Sobreira Campos da Costa (fabio.sobreira@ufpe.br) on 2016-06-21T15:14:55Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Vitor_de_Andrade_Coutinho-dissertacao_ppgee.pdf: 3622975 bytes, checksum: 01a22e0302dfc1890d745c6b1bffe327 (MD5) / Made available in DSpace on 2016-06-21T15:14:56Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Vitor_de_Andrade_Coutinho-dissertacao_ppgee.pdf: 3622975 bytes, checksum: 01a22e0302dfc1890d745c6b1bffe327 (MD5) Previous issue date: 2015-02-23 / CNPq / O presente trabalho aborda o desenvolvimento de aproximações para a transformada dis- reta do osseno (DCT) utilizando a abordagem pruning. Devido à propriedade da ompa ta- ção de energia, a DCT é empregada em diversas apli ações de ompressão de dados. Embora algoritmos rápidos permitam omputar a DCT e ientemente, operações de multipli ação são inevitáveis. Devido a res ente demanda por métodos de baixo onsumo energéti o, novos algoritmos de usto omputa ional reduzido são ne essários. Neste ontexto, aproximações para a DCT foram propostas nos últimos anos. Tais aproximações permitem algoritmos livres de multipli ação, sem a ne essidade de operações de ponto utuante, mantendo o desempe- nho de ompressão omparável ao forne ido por métodos baseados na DCT. Uma abordagem adi ional para reduzir o usto omputa ional da DCT é a utilização de pruning. Tal té ni a onsiste em não onsiderar oe ientes dos vetores de entrada e/ou saída que apresentam menor relevân ia em termos de energia on entrada. No aso da DCT, esses oe ientes são os termos de mais alta frequên ia do vetor transformado. A apli ação de pruning a aproxima- ções para a DCT é uma área pou o explorada. O objetivo deste trabalho é apli ar a té ni a a diferentes métodos aproximados para a DCT. As transformações resultantes foram apli adas no ontexto de ompressão de imagem e vídeo e os resultados mostraram desempenho ompa- rável ao de métodos exatos a um usto omputa ional bastante reduzido. Uma generalização do on eito é apresentada, assim omo uma análise da omplexidade aritméti a. / This work introdu es approximate dis rete osine transforms (DCT) based on the pruning approa h. Due to the energy ompa tion property, the DCT is employed in several data ompression appli ations. Although fast algorithms allow an e ient DCT omputation, multipli ation operations are inevitable. Due to the in reasing demand for energy e ient methods, new algorithms with redu ed omputational ost are required. In this ontext, DCT approximations have been proposed re ently. Su h approximations allow multipli ation free algorithms whi h an avoid oating point operations, while maintaining a ompetitive performan e. A further approa h to redu e the omputational ost of the DCT is pruning. The te hnique onsists of dis arding input and/or output ve tors oe ients whi h are regarded as less signi ant. In the ase of the DCT, su h oe ients are output oe ients asso iated to higher frequen y terms. Pruned DCT approximations is a relatively unexplored eld of resear h. The obje tive of this work is the ombination of approximations and pruning to derive extremely low- omplexity DCT approximations. The resulting methods were applied in the image and vídeo ompression s enario and results showed omparative performan e with exa t methods at a mu h lower omputational omplexity. A qualitative and quantitative omparison with a omprehensive list of existing methods is presented. A generalization of the pruning on ept is presented.

O Tungstato de Zircônio (ZrW2O8) é um material que exibe Expansão Térmica Negativa (ETN), isotrópica em um amplo intervalo de temperatura (0,3 a 1050 K). Apesar de amplamente estudado, existem controvérsias acerca dos mecanismos microscópicos responsáveis por este comportamento. A fase cúbica deste composto, denominada a-ZrW2O8, já foi motivo de estudo através de simulações computacionais utilizando Potenciais Interatômicos (PI) e Dinâmica de Rede na Aproximação Quasi-Harmônica (DRQH). Nos dois PI distintos propostos na literatura conseguiu-se reproduzir a ETN da a-ZrW2O8, mas não a dependência com a temperatura do tensor de elasticidade. É partindo desta observação que este trabalho pretende avaliar o desempenho de PI existentes e de novos PI em simulações computacionais visando a descrição da dependência com a temperatura do tensor de elasticidade da a-ZrW2O8 entre 0 e 300 K. Utilizaram-se dados experimentais, tais como posições atômicas, parâmetros de rede e o tensor de elasticidade da a-ZrW2O8 em temperaturas entre 0 e 300 K e, em outra série de cálculos, a hipersuperfície de energia ab initio no limite atérmico para obter os parâmetros dos PI. Diferentes estratégias foram empregadas na busca pelos parâmetros dos PI incluindo minimização em linha, Newton-Raphson/BFGS e Algoritmo Genético (AG). Concluiu-se que não é possível descrever as propriedades estruturais e elásticas da a-ZrW2O8 em função da temperatura com PI simples e que esta incapacidade não está relacionada a qualquer limitação da DRQH ou dos parâmetros dos PI, mas à forma analítica dos PI empregados. Isto sugere que se deve ter cautela na interpretação de resultados obtidos com estes potencias já disponíveis na literatura. Como alternativas para a solução deste problema, pode-se considerar o uso de redes neurais para a representação da hipersuperfície de energia ab initio, o uso de PI mais sofisticados que levam em consideração a vizinhança atômica (bond order potentials) e, também, cálculo ab initio a T > 0, este último a um custo computacional muito mais elevado. / Zirconium tungstate (ZrW2O8) is a material that exhibits negative thermal expansion (NTE), over a wide temperature range (0.3 at 1050 K). Although thoroughly studied, controversies still remain concerning the microscopic mechanisms responsible for this behavior. The cubic phase of this compound, denominated a-ZrW2O8, was already the subject of study through computer simulations using interatomic potentials (IP) and lattice dynamics in quasiharmonic approximation (LDQH). In two different IPs proposed in the literature succeeded in reproducing the a-ZrW2O8 NTE, but not the dependence with temperature of the elasticity tensor. Starting from this observation, this work intends to evaluate of existent IPs and same proposed new IPs in computer simulations aiming the calculation of the tensor of elasticity for a-ZrW2O8 between 0 and 300 K. Experimental data (such as atomic positions, lattice parameters and the tensor of elasticity of a-ZrW2O8 at 0 and 300 K) and, in another series of calculations, the ab initio energy hypersurface in the athermic limit, were used to obtain the parameters of the IPs. Different strategies were used in the search for the parameters of IP, including line minimization, Newton-Raphson/BFGS and genetic algorithm (GA). At the end of an exhaustive search we were led to conclude that it is not possible to describe the structure and elastic properties of a-ZrW2O8 as a function of temperature with simple IPs and that this incapacity is not related the any limitation of LDQH or of the parameters of the IPs, but instead to the analytical form of the tested IPs. This suggests that same results obtained with IPs already available in the literature may be unreliable. As alternatives for the solution of this problem, it can be considered the use of a neural network for the representation of the ab initio energy hypersurface, the use of more sophisticated IPs than take into account the atomic neighborhood (bond order potentials) and even (with a computational cost much higher) ab initio calculations at T > 0.

Submitted by (lucia.rodrigues@ufrpe.br) on 2017-03-28T15:03:54Z No. of bitstreams: 1 Danilo Albuquerque de Campos.pdf: 453917 bytes, checksum: 1b07ec11128857b2e96af37543e335fe (MD5) / Made available in DSpace on 2017-03-28T15:03:55Z (GMT). No. of bitstreams: 1 Danilo Albuquerque de Campos.pdf: 453917 bytes, checksum: 1b07ec11128857b2e96af37543e335fe (MD5) Previous issue date: 2014-08-22 / In this work we are interested in showing three algorithms rational approximation of square roots by methods unknown or underutilized by teachers of elementary and secondary education. We begin by defining numerical sequence and convergence of sequences, will discuss the need to expand the concept of rational number and demonstrate the irrationality of the diagonal of a square. Prove an important theorem known in the literature as Dirichlet’s theorem and finally elencaremos three methods of approximating the square roots of natural non-perfect square numbers, very simple to be worked on in the classroom that are rational algorithm aproximção of Hiero of Alexandria, Theon’s Ladder and the Pell-Fermat equation, sende latter discursão fundamental to who will perform on the relationship of the three methods presented. / Neste trabalho estamos interessados em mostrar três algoritmos de aproximação racional de raízes quadradas por métodos pouco utilizados ou desconhecidos pelos professores do ensino fundamental e médio. Iniciaremos definindo sequência numérica e convergência de sequências, discutiremos sobre a necessidade de ampliação do conceito de número racional e demonstraremos a irracionalidade da diagonal de um quadrado. Provaremos um importante Teorema conhecido na literatura como o Teorema de Dirichlet, e por fim elencaremos três métodos de aproximação de raízes quadradas de números naturais não quadrados perfeitos, muito simples de serem trabalhados em sala de aula que são: O algoritmo de aproximação racional de Hierão de Alexandria, A escada de Theon e a Equação de Pell-Fermat, sendo este último fundamental para discussão que iremos realizar sobre a relação dos três métodos apresentados.

Na aproximação de potencial local (L\\downarrow1) a transformação de grupo de renormalização para o modelo O(N) de Heisenberg hierárquico é descrita por uma equação a derivadas parciais (EDP). Neste trabalho investigamos, na criticalidade (sistema à temperatura inversa crítica), a somabilidade da série de potências em 1/N que formalmente satisfaz essa EDP. / In the local potential approximation (L\\downarrow1) the renormalization group transformation for the hierarchical O(N) Heisenberg model is described by a partial differential equation (PDE). In this work we investigate, at criticality (system at inverse critical temperature), the summability of the formal power series in 1/N which formally satisfies that PDE.

Dado um grupo G, a definição dos grupos de cohomologia com coeficientes em um ZG-módulo M podem ser dadas usando as técnicas usuais da Álgebra Homológica, que garantem a existência de resoluções projetivas P de Z como um ZG-módulo trivial, a equivalência entre resoluções distintas etc. Podemos também construir o produto cup em cohomologia, cuja definição depende de uma aproximação da diagonal para a resolução projetiva P. Entretanto, o cálculo explicito de tais resoluções e dos grupos de cohomologia pode ser bastante difícil na prática, e ainda mais difícil a obtenção de uma aproximação da diagonal. Nesta tese, obteremos resoluções livres e aproximações da diagonal para os grupos fundamentais das superfícies que são espaços K(G,1) e também para o grupo fundamental de fibrados do toro com base S^1, bem como a estrutura de anel de cohomologia de tais grupos. Ainda, para certos grupos virtualmente cíclicos G, obteremos o anel de cohomologia calculando diretamente uma resolução livre e uma aproximação da diagonal, ou então usando a sequência espectral de Lyndon-Hochschild-Serre. A motivação para o estudo da primeira família de grupos vem do fato de representarem variedades de dimensão 2 e 3, e da segunda família por ser constituída de grupos que atuam em esferas de homotopia. / Given a group G, a definition for its cohomology groups with coefficients in a given ZG-module M can be given using the standard techniques of Homological Algebra, that ensure the existence of projective resolutions P of Z as a trivial ZG-module, the equivalence between two such resolutions etc . We can also construct the cup product, whose definition depends on a diagonal approximation for a given projective resolution P. However, the explicit computation of such resolutions and of the cohomology groups may be very hard in practice, and even worse may be the task of constructing a diagonal approximation. In this thesis, we obtain free resolutions and diagonal approximations for the fundamental groups of surfaces that are K(G,1) spaces and for the fundamental group of the torus bundle with the circle as the base space, as well as the structure of the cohomology ring of these groups. Also, for some virtually cyclic groups, we obtain the cohomology ring by an explicit computation of a free resolution and a diagonal approximation, or by the Lyndon-Hochschild-Serre spectral sequence. The motivation for the study of the first family of groups comes from the fact that such groups represent manifolds of dimension 2 and 3, and the groups of the second family act on homotopy spheres.

Conselho Nacional de Desenvolvimento Científico e Tecnológico / New trends and emerging technologies motivate the design of analog-to-digital converters (ADCs) which must fit in increasingly constrained environments. Within this context, one design metric which is constantly forced towards reduction is the power consumption, leading the designers to come up with improvements in both the architecture and circuit levels. This work aims to push forward the energy efficiency of the successive approximation charge sharing ADC, which is a relatively new and unexplored architecture. Therefore, three complete ADCs are designed throughout this work, each one bringing novelties that help decreasing the power consumption. The techniques devised here include novel manners of dealing with the tracking of the input signal and a circuit to reduce power drained in the pre-charge cycle. Also, three different architectures of digital controller for this ADC topology are designed. Moreover, a novel bootstrapping switch circuit is presented, which provides lower devices-count and a extremely high energy efficiency. / As novas tendências e tecnologias emergentes motivam o projeto de conversores analógico-digitais (ADCs) que precisam suprir especificações cada vez mais restritivas. Nesse contexto, uma métrica de projeto que é constantemente forçada em direção à redução é o consumo de potência, fato esse que leva à concepção de melhorias tanto em nível arquitetural como em nível de circuito elétrico. Este trabalho tem como objetivo elevar a eficiência energética dos ADCs por aproximações sucessivas e compartilhamento de carga, visto que essa é uma arquitetura relativamente nova e inexplorada. Portanto, três ADCs completos são projetados ao longo deste trabalho, e cada um traz inovações que ajudam a reduzir o consumo de potência. As técnicas concebidas aqui incluem maneiras novas de efetuar a captura do sinal de entrada e um circuito para reduzir a potência drenada no ciclo de pré-carga. Além disso, três arquiteturas diferentes de controlador digital para essa topologia de ADC são expostas. Mais, um novo circuito de chave com bootstrapping é apresentado, o qual apresenta um número de dispositivos menor e uma eficiência energética extremamente alta.

Orientador : Fernando Jose Von Zuben / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-04T02:17:19Z (GMT). No. of bitstreams: 1 Lima_ClodoaldoAparecidodeMoraes_D.pdf: 5444612 bytes, checksum: 0172ca4143c2737bf19a3b2076c06b44 (MD5) Previous issue date: 2004 / Resumo: Os algoritmos baseados em métodos de kernel destacam-se entre as diversas técnicas de aprendizado de máquina. Eles foram inicialmente empregados na implementação de máquinas de vetores-suporte (SVMs). A abordagem SVM representa um procedimento de aprendizado não-paramétrico para classificação e regressão de alto desempenho. No entanto, existem aspectos estruturais e paramétricos de projeto que podem conduzir a uma degradação de desempenho. Na ausência de uma metodologia sistemática e de baixo custo para a proposição de modelos computacionais otimamente especificados, os comitês de máquinas se apresentam como alternativas promissoras. Existem versões estáticas de comitês, na forma de ensembles de componentes, e versões dinâmicas, na forma de misturas de especialistas. Neste estudo, os componentes de um ensemble e os especialistas de uma mistura são tomados como SVMs. O objetivo é explorar conjuntamente potencialidades advindas de SVM e comitê de máquinas, adotando uma formulação unificada. Várias extensões e novas configurações de comitês de máquinas são propostas, com análises comparativas que indicam ganho significativo de desempenho frente a outras propostas de aprendizado de máquina comumente adotadas para classificação e regressão / Abstract: Algorithms based on kernel methods are prominent techniques among the available approaches for machine learning. They were initially applied to implement support vector machines (SVMs). The SVM approach represents a nonparametric learning procedure devoted to high performance classification and regression tasks. However, structural and parametric aspects of the design may guide to performance degradation. In the absence of a systematic and low-cost methodology for the proposition of optimally specified computational models, committee machines emerge as promising alternatives. There exist static versions of committees, in the form of ensembles of components, and dynamic versions, in the form of mixtures of experts. In the present investigation, the components of an ensemble and the experts of a mixture are taken as SVMs. The aim is to jointly explore the potentialities of both SVM and committee machine, by means of a unified formulation. Several extensions and new configurations of committee machines are proposed, with comparative analyses that indicate significant gain in performance before other proposals for machine learning commonly adopted for classification and regression / Doutorado / Engenharia de Computação / Doutor em Engenharia Elétrica