O problema do isomorfismo de grafos possui aplicações em diversas áreas da ciência. Tal problema não possui uma solução eficiente para o seu caso geral. No presente trabalho, apresentamos os conceitos básicos em teoria de grupos, teoria dos grafos e mecânica quântica. Apresentamos o problema do subgrupo oculto e uma conhecida redução polinomial do problema do isomorfismo de grafos no seu caso geral para o problema do subgrupo oculto sobre o grupo simétrico. Utilizamos um método que reduz o problema do isomorfismo de grafos para o problema de interseção de grupos. Este método utiliza resultados da computação quântica e da teoria dos grupos solúveis, nos permitindo obter uma solução eficiente através de um algoritmo quântico para o problema do isomorfismo de grafos para uma classe particular de grafos. / The graph isomorphism problem has applications in several areas of science. This problem has not an efficient solution to its general case. In this work, we present the basic concepts of group theory, graph theory and quantum mechanics. We introduce the hidden subgroup problem and a known polynomial reduction of the graph isomorphism problem in its general case to the hidden subgroup problem on the symmetric group. We use a method that reduces the graph isomorphism problem to the group intersection problem. This method combines results from quantum computing and solvable group theory providing a efficient solution through a quantum algorithm to the graph isomorphism problem for the particular class of graphs.

Esta dissertação apresenta os algoritmos BicriterionAnt, MACS e MONACO, disponíveis na literatura, baseados em colônia de formigas, para resolução do Problema do Caixeiro Viajante Multiobjetivo (PCVMO). São apresentadas as características do problema e de cada algoritmo utilizado. Estes algoritmos foram testados em seis instâncias bi-objetivo do PCVMO. Foram implementadas algumas alterações na estrutura original dos algoritmos na tentativa de produzir resultados melhores do que os algoritmos originais. Para a avaliação dos resultados e medição da qualidade das soluções, foram utilizadas métricas de desempenho que auxiliam na identificação dos melhores conjuntos de soluções não-dominadas. / This dissertation presents the BicriterionAnt, MACS and MONACO Ant Colony algorithms, available in literature, to solve the Multi-Objective Traveling Salesman Problem (MOTSP). The characteristics of the problem and of each algorithm used are presented. Those algorithms were tested in six bi-objective instances of MOTSP. Changes in the original algorithms were implemented to try to produce better results than the original ones. To validate the results and to measure the quality of the solutions, metrics of performance were used which help to identify the best non-dominated solution sets.

O Pirarucu (Arapaima gigas ) tem sido dos mais importante recursos econômicos entre todas as espécies de peixe da Amazônia Brasileira por mais de três séculos. A introdução de tecnologias modernas de exploração trouxe graves ameaças à preservação desta espécie. Estratégias de manejos adequados devem ser urgentemente introduzidas, a fim de evitar extinção. O objetivo deste trabalho é apresentar um modelo matemático para a dinâmica populacional do pirarucu considerando peculiaridades da espécie e as diferentes taxas de pesca de modo a fornecer subsídios para a sua conservação. A fim de diferenciar seus respectivos papéis na reprodução, a população está dividida em dois grupos: machos e fêmeas. Os parâmetros assumidos no presente trabalho são parcialmente derivados de dados de campo limitados, mas seguros da Reserva de Desenvolvimento Sustentável de Mamirauá na região Amazônica Brasileira . Alguns outros parâmetros são estimados a partir de considerações biológicas. / Pirarucu ( Arapaima gigas) has been one of the most important economic resources among all the fish species of the Brazilian Amazon for more than three centuries. The introduction of modern technologies of exploitation brought serious threats to the preservation of this species. Adequate management strategies have to be urgently introduced in order to prevent extinction. The aim of this work is to present a mathematical model for the pirarucu population dynamics considering the species peculiarities and the different fishing rates to supply subsides for its conservation. In order to differentiate its respective role in breeding, the population is divided into two groups: female and male. The parameters introduced in this paper are derived from limited but reliable field data collected at the Mamirauá Sustainable Development Reserve (MSDR) in the Brazilian Amazonian Region. Complementary parameters are estimated from biological considerations and commonsense.

Técnicas baseadas em física têm chamado a atenção da comunidade de computação gráfica, em especial para animação de fluidos (gás ou líquidos). As técnicas tradicionais para animação de fluidos são metodologias top-down baseadas em malhas 2D/3D, tais como Diferenças Finitas e Elementos Finitos, em conjunto com equações de fluidos Navier-Stokes. Entretanto, tais métodos têm um custo computacional alto. Uma alternativa é o uso de técnicas baseadas em Autômatos Celulares do tipo Lattice Gas (LGCA) e o Método de Lattice Boltzmann (LBM). A idéia básica desses métodos consiste em obter a dinâmica macroscópica de um fluido a partir do comportamento coletivo de diversas partículas microscópicas. Em geral, tais metodologias bottom-up são eficientes do ponto de vista computacional. Neste trabalho, são estudados os aspectos teóricos e práticos da animação computacional de fluidos bidimensionais para computação gráfica, usando um método LGCA chamado FHP, e um método LBM chamado D2Q9. É proposto um modelo de fluido 3D baseado nos modelos bidimensionais FHP e D2Q9, bem como em métodos de interpolação. Em seguida, são apresentadas duas aplicações para animação de fluidos através dos métodos mencionados, uma para execução em tempo real e outra para execução off-line. Nos resultados dos experimentos computacionais são enfatizados a simplicidade e o potencial dos modelos propostos quando combinados com técnicas eficientes de rendering. / Physically-based techniques for the animation of fluids (gas or liquids) have taken the attention of the computer graphics community. The traditional fluid animation methods rely on a top down viewpoint that uses 2D/3D mesh based approaches motivated by the Eulerian methods of Finite Element (FE) and Finite Difference (FD), in conjunction with Navier-Stokes equations of fluids. Alternatively, lattice methods comprised by the Lattice Gas Cellular Automata (LGCA) and Lattice Boltzmann (LBM) can be used. The basic idea behind these methods is that the macroscopic dynamics of a fluid is the result of the collective behavior of many microscopic particles. Such bottom-up approaches need low computational resources for both the memory allocation and the computation itself. In this work, we consider animation of fluids for computer graphics applications, using a LGCA method called FHP, and a LBM method called D2Q9, both bidimensional models. We propose 3D fluid animation techniques based on the FHP and D2Q9 as well as interpolation methods. Then, we present two animating frameworks based on the mentioned lattice methods, one for a real time implementation and the other for an off-line implementation. In the experimental results we emphasize the simplicity and power of the presented models when combined with efficient techniques for rendering and compare their efficiency.

Neste trabalho, modela-se a ocorrência de contaminação de um aquífero hipotético por derramamento de substância tóxica e analisa-se a solução de descontaminação baseada na retirada do contaminante através de bombeamento feito por poços de extração. O projeto do sistema de remediação envolve a escolha do número de poços a serem instalados, suas localizações e vazões de modo a maximizar a quantidade de poluente extraída e ao mesmo tempo minimizar o custo total do sistema. A busca da solução ótima é feita de forma automática, através de um sistema paralelo de otimização por simulação numérica, composto por três subsistemas: (a) simulador numérico - resolve numericamente o modelo matemático do aquífero contaminado; (b) otimizador automático - implementa o método dos algoritmos genéticos para busca das localizações e vazões ótimas dos poços de extração; (c)sistema computacional distribuído - gerencia a distribuição e a execução paralela das simulações numéricas. Foram feitos experimentos em vários ambientes computacionais: homogêneo, heterogêneo, em grande escala, usando máquinas não dedicadas, interligadas por rede local e ambiente de grade, e seus resultados demonstram a aplicabilidade da metodologia. / In this dissertation, a hypothetical aquifer that has been contaminated by the dumping of toxic substances is modeled. The remediation strategy considered is based on withdrawal, which requires the removal of contaminated groundwater from the aquifer by pumping. The design of such a system involves the choice of the number of extracting wells to be installed, their locations and pumping rates,with the goal of maximizing the amount of contaminant extracted, while minimizing the cost of the system. To find the optimal solution, a numerical simulation optimization parallel system is used, which is composed by three subsystems: (a) numerical simulator - numerically solves the mathematical model ofthe contaminated aquifer; (b) optimizer - implements the genetic algorithm method to search for optimal locations and pumping rates for the extracting wells; (c)distributed computing system - manages the distribuition and parallel execution of the numerical simulations. Experiments were done in many different computational environments: homogeneous, heterogeneous, in large scale, using non dedicated computers, connected via local network, and computational grids, and their results demonstrate the methodologys applicability.

The type IV secretion system can be classified as a large family of macromolecule transporters divided in three recognized sub-families involved in different bacterial functions. The major sub-family of T4SS is the conjugation system, which allows transfer of genetic material as a nucleoprotein via cell contact among bacteria. Analogously to bacterial conjugation, the T4SS can transfer genetic material from bacteria to eukaryotic cells; such is the case of T-DNA transfer of Agrobacterium tumefaciens to host plant cells. The system of effector proteins transport constitutes the second sub-family, being indispensable for infection processes of several mammalian and plants pathogens. The third sub-family corresponds to the DNA uptake/release system involved in genetic transformation competence, independently of cell contact, as it was described to the systems VirB/D4 from Campylobacter jejuni and ComB form Helicobacter pylori. Several essential features of T4SS are well known, but the knowledge in support of an uncomplicated classification or proper protein annotation of system subunits remains confusing, which in same cases can avoid making inferences about evolution of the system in bacterial species. The purpose of this work was to organize, classify and integrate the knowledge about T4SS through building a database devoted to this bacterial secretion system. The T4SS database was created using the SGBD MySQL and Perl programming language and with a web interface (HTML/CGI) that gives access to the database. Currently, this database hold genomic data from 43 bacteria and 10 plasmids acquired from the GenBank NCBI, these organisms comprise groups from Actionobacteria to Gram-negative Proteobacteria including symbiotic and pathogenic bacteria. By applying Bidirectional Best-Hits method was possible to get a core set of 75 clusters with 974 proteins involved in the T4SS. Also, during this procedure BlastP, Muscle e ClustalW algorithms were applied. The database was manually annotated supported by cross references built-in the T4SS annotation pages, such as the UniProtKB/Swiss-Prot, COG, InterPro and TCDB as well as by the methods for signal peptide and transmembrane regions prediction. All T4SS protein records scattered into 75 ortholog clusters were organized into five different classes of type IV secretion system proteins: (i) Type IVA Mpf/T4CP; (ii) Type IVA Dtr; (iii) F-type plasmid; (iv) IncP-1-type plasmid; (v) Type IVB Icm/Dot. All 974 proteins were annotated into 68 well-known families, which can be involved in conjugation, effector translocator, DNA uptake/release or even can be bifunctional proteins. Also, by using the Maximum Likelihood method were built 70 unrooted phylogenetic trees that represents just 70 clusters instead of 75, this is due to five clusters had only two protein sequences, five unrooted phylogenetic trees were built for each group of first hierarchical classification, one unrooted phylogenetic trees including proteins from archetype systems of all groups, one unrooted phylogenetic trees from 16S sequence of each organism and one rooted tree including a sequence from a Gram-positive bacteria as an external group. The phylogenetic analyses show that some proteins of T4SS are more divergent than others, which indicate that for a particular function few sequence mutations were needed, but other proteins required many sequence mutations to get another functions. Thus, these results proved that proteins belong to the same cluster show different functions: conjugation, DNA uptake/release or effector translocator. Consequently, it was possible verify that similar functions were grouped together within phylogenetic tree, which allowed to annotate a probable function of some uncharacterized proteins, that is possibly due to the sequence similarity may reveal a similar evolution to get the same function. Thus, the phylogenetic trees allowed confirming the protein annotation as well as inferring whether uncharacterized proteins would encompass a known function. The T4SS database will be an open access, given to the users searching and submission sequence tools, which will permit to get insights about classification and phylogeny of T4SS sequence of interest. T4SS Database is accessible at the URL http://www.t4ss.lncc.br. / O T4SS pode ser classificado como uma família de transportadores de macromoléculas envolvidos em diferentes funções bacterianas. A maior subfamília do T4SS é a do sistema de conjugação, o qual permite a transferência de material genético entre bactérias. Analogamente à conjugação, o sistema pode transferir material genético entre bactérias e eucariotos, tal como a transferência de T-DNA de Agrobacterium tumefaciens. O sistema de transporte de proteínas efetoras constitui uma segunda subfamília do T4SS, sendo indispensável nos processos de infecção de vários patógenos de mamíferos e plantas. A última subfamília corresponde ao sistema DNA-uptake/release" que funciona independente de contato com uma célula alvo, representado pelos sistemas VirB/D4 de Campylobacter jejuni e ComB de Helicobacter pylori. Muitas características básicas do T4SS são bem conhecidas, entretanto o conhecimento para a classificação simples e intuitiva ou a anotação apropriada das proteínas ainda não está claro, impedindo em alguns casos estabelecer correlações evolutivas deste sistema em bactérias. O objetivo deste trabalho foi o de organizar, classificar e integrar o conhecimento do T4SS através da construção de um banco de dados especializado para este sistema secretório bacteriano. O banco de dados T4SS foi criado utilizando o SGBD MySQL e a linguagem de programação Perl e com uma interface web (HTML/CGI) que fornece acesso ao banco. Este banco consta atualmente com 43 genomas bacterianos e 10 plasmídeos obtidos do GenBank NCBI, estes organismos vão desde Actinobactérias até Proteobactérias Gram-negativas, incluindo simbiontes e patogênicos. Foi utilizada a metodologia do Bidirectional Best-Hits", com a qual foi possível obter um conjunto mínimo de 75 clusters" com 974 proteínas envolvidas no T4SS. Também, durante este procedimento foram utilizados os algoritmos BlastP, Muscle e ClustalW. O banco foi anotado manualmente utilizando referências cruzadas incluídas nas páginas de anotação do T4SS, tais como UniProtKB/Swiss-Prot, COG, InterPro e TCDB e métodos para predição de regiões de peptídeos sinal e transmembrana. As análises do banco T4SS permitiram criar uma classificação hierárquica e funcional para as proteínas do T4SS, consistindo em cinco grupos: (i) Type IVA Mpf/T4CP; (ii) Type IVA Dtr; (iii) F-type plasmid; (iv) IncP-1-type plasmid; (v) Type IVB Icm/Dot). As 974 proteínas foram anotadas em 68 famílias conhecidas, as quais podem estar envolvidas em conjugação, transferência de T-DNA, transferência de proteínas efetoras, DNA-uptake/release" ou bem serem proteínas bifuncionais. Também, através do método de máxima verossimilhança foram geradas 70 árvores filogenéticas não enraizadas (NR) representando apenas 70 clusters, já que cinco clusters apresentaram apenas duas seqüências de proteínas, cinco árvores filogenéticas NR foram criadas para cada grupo da primeira categoria hierárquica, uma árvore NR com representantes de todos os grupos, uma árvore NR gerada a partir das seqüências 16S de cada organismo e uma árvore de um cluster incluindo uma seqüência de bactéria Gram-positiva como grupo externo. As análises filogenéticas mostram que determinadas proteínas do sistema são mais divergentes que outras, indicando que para uma determinada função poucas mutações de seqüências foram necessárias, já outras proteínas precisaram de maiores mutações para adquirir outras funções. Por isso, verifica-se que proteínas de um mesmo cluster apresentam diferentes funções: conjugação, DNA-uptake/release", traslocadores de proteínas efetoras. Conseqüentemente, foi possível verificar que funções semelhantes se agruparam juntas nas árvores filogenéticas, permitindo anotar uma função provável das proteínas ainda não caracterizadas (unknown"), isto possivelmente devido a que em virtude de sua semelhança de seqüências, possivelmente evoluíram para realizar a mesma função. Assim, as arvores possuíram a finalidade de confirmar a anotação e contribuíram permitindo inferir se os unknown" ou probable" podem ser de uma determinada classificação funcional. O banco T4SS será de uso público, oferecendo ao usuário ferramentas de buscas e submissão de seqüências, as quais permitirão inferir respostas sobre a classificação e filogenia da seqüência T4SS de interesse. O banco de dados T4SS pode ser acessado na URL: http://www.t4ss.lncc.br.

Neste trabalho apresentamos um novo algoritmo quântico eficiente para o Problema do Subgrupo Oculto (PSO) sobre uma classe especial de grupos metacíclicos, Z_p times Z_q^s, com q | (p-1) e p/q= poli(log p), onde p, q são números primos ímpares distintos e s um inteiro positivo qualquer. Em um contexto mais geral, sem impor uma relação entre p e q obtemos um algoritmo quântico com complexidade de tempo 2^{O(sqrt{log p})}. Em qualquer caso, esses resultados são melhores que qualquer algoritmo clássico para o mesmo fim, cuja complexidade é Omega(sqrt{p}). Apresentamos também, algoritmos quânticos para o PSO sobre grupos não abelianos de ordem 2^{n+1} que possuem subgrupos cíclicos de índice 2 e para certos produtos semidiretos de grupos Z_N^m times Z_p, com m, N inteiros positivos e N fatorado de forma especial. / We present a new polynomial-time quantum algorithm that solves the hidden subgroup problem (HSP) for a special class of metacyclic groups, namely Z_{p} times _{q^s}, with q mid (p-1) and p/q= up{poly}(log p), where p, q are any odd prime numbers and s is any positive integer. This solution generalizes previous algorithms presented in the literature. In a more general setting, without imposing a relation between p and q, we obtain a quantum algorithm with time and query complexity 2^{O(sqrt{log p})}. In any case, those results improve the classical algorithm, which needs {Omega}(sqrt{p}) queries. We also present quantum algorithms for the HSP over non-abelian groups of order 2^{n+1} which have a cyclic subgroup of index 2 and for some semidirect product _N^m times _p, where N has a special prime factorization.

Esta tese aborda o problema de entender videos digitais algoritmicamente aplicado ao design de sistemas de Interação Homem-Computador (HCI do Inglês: Human-Computer Interaction) baseados na postura e movimento da mão. Tais sistemas são frequentemente referidos como um tipo de Interface Perceptual com o usuário (PUI do Inglês: Perceptual User Interface), que é uma interface que habilita o computador a detectar e reconhecer ações dos usuários de forma ativa. Acredita-se que PUI é um paradigma que irá suplementar o padrão atual, as Interfaces Gráficas com o Usuário (GUI do Inglês: Graphical User Interfaces), que são baseadas em mouses e teclados para entrada do usuário. A principal motivação da pesquisa feita em HCI por gestos manuais é habilitar as pessoas a interagir de uma forma mais natural com dispositivos computacionais, por exemplo, ao permitir que usuários manipulem programas, arquivos e pastas de computador de uma forma similar ao manuseio de objetos físicos familiares. Neste trabalho é proposto um ferramental para rastreamento da mão --posição e rotação no plano-- assim como para reconhecimento de postura da mão a partir dos contornos da mão. Uma nova abordagem de processamento de pixels baseada em aprendizagem de máquina forma o bloco fundamental para um método level set de extração de contornos, tão bem como para um módulo de mensuração do rastreador, que é formulado como um problema de filtragem em espaço de estados onde a dinâmica do sistema é modelada com sistemas lineares com saltos markovianos. Baixas taxas de erro de classificação de postura são alcançadas com o uso de um descritor de formas baseados em medidas invariantes de momentos bidimensionais.

Em Ciência da Computação, os caminhos aleatórios são utilizados em algoritmos randômicos, especialmente em algoritmos de busca, quando desejamos encontrar um estado marcado numa cadeia de Markov. Nesse tipo de algoritmo é interessante estudar o Tempo de Alcance, que está associado a sua complexidade computacional. Nesse contexto, descrevemos a teoria clássica de cadeias de Markov e caminhos aleatórios, assim como o seu análogo quântico. Dessa forma, definimos o Tempo de Alcance sob o escopo das cadeias de Markov quânticas. Além disso, expressões analíticas calculadas para o tempo de Alcance quântico e para a probabilidade de encontrarmos um elemento marcado num grafo completo são apresentadas como os novos resultados dessa dissertação. / In Computer Science, random walks are used in randomized algorithms, specially in search algorithms, where we desire to find a marked state in a Markov chain.In this type of algorithm,it is interesting to study the Hitting Time, which is associated to its computational complexity. In this context, we describe the classical theory of Markov chains and random walks,as well as their quantum analogue.In this way,we define the Hitting Time under the scope of quantum Markov chains. Moreover, analytical expressions calculated for the quantum Hitting Time and for the probability of finding a marked element on the complete graph are presented as the new results of this dissertation.

Este trabalho descreve o desenvolvimento de uma estrutura lógica de software para o controle do CAVE do LNCC e sua utilização na visualização de dados biológicos. Configuramos e adaptamos o framework InstantReality para fazer funcionar todos os componentes singulares do CAVE do LNCC ( uma parede não ortogonal, duas paredes com cinco lados, projetores convencionais, entre outros ) por meio de uma tecnologia emergente, o X3D, usado para distribuir conteúdo 3D multimídia pela Internet. Propomos um processo para o rápido desenvolvimento, recorrendo ou não a uma linguagem de programação, de aplicações para visualização de dados biológicos, tais como: descrição geométrica de parte do sistema cardiovascular humano, de parte de uma larva, visualização de modelos de proteínas e capsídios de vírus. Apresentamos questões importantes na visualização de superfícies complexas, como a importância do modelo de iluminação utilizado e descrevemos a implementação de um modelos de iluminação em GPU. Adicionalmente, justificamos o emprego da Realidade Virtual como ferramenta valiosa para a visualização em bioinformática, e mesmo na biologia. Finalmente, avaliamos a eficiência geral do CAVE e de cada componente,através dos resultados obtidos na visualização de cenários temáticos de interesse biológico. Identificamos possíveis problemas e sugerimos opções para uma melhoria geral do desempenho. / This work describes the development of a software structure that currently controls the CAVE at LNCC, as well as its use for biological data visualization. This work also includes the adaptation and configuration of the InstantReality framework considering all particularities of the CAVE built at LNCC, which amongst other things does not have square walls all around (two walls have a particular shape). In order to accompish this task we make use of the emerging X3D technology. This work also proposes a process for fast development of biological data visualization. Such process has been used to develop a series of sample applications, which included geometric description of parts of the human cardiovascular system as well as other structures such as parts of worms and other creatures, visualization of proteine models and virus envelops both relying or not on some programming language. This work also introduces important aspects of complex surface visualization and describes the implementation of a GPU based ilumination model. Additionally, some justifications are presented regarding the use of Virtual Reality as a tool for bioinformatics visuzalization or biologic applications. Finally, this work evaluates the CAVE prototype, considering each of its components, in the light of the results achieved in the biologic visualization applications developed. Problems are identified and further improvements are proposed.