Orientador : Prof. Dr. Luiz Eduardo Soares de Oliveira / Co-orientador : Prof. Dr. Paulo Rodrigo Cavalin / Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 21/112014 / Inclui referências / Resumo: Classifica¸c˜ao de texturas 'e um problema na 'area de Reconhecimento de Padr˜oes com uma ampla gama de aplica¸c˜oes. Esse problema 'e geralmente tratado com o uso de descritores de texturas e modelos de reconhecimento de padr˜oes, tais como M'aquinas de Vetores de Suporte (SVM) e Regra dos K vizinhos mais pr'oximos (KNN). O m'etodo cl'assico para endere¸car o problema depende do conhecimento de especialistas no dom'ýnio para a cria¸c˜ao de extratores de caracter'ýsticas relevantes (discriminantes), criando-se v'arios descritores de textura, cada um voltado para diferentes cen'arios (por exemplo, descritores de textura que s˜ao invariantes 'a rota¸c˜ao, ou invariantes ao borramento da imagem). Uma estrat'egia diferente para o problema 'e utilizar algoritmos para aprender os descritores de textura, ao inv'es de constru'ý-los manualmente. Esse 'e um dos objetivos centrais de modelos de Arquitetura Profunda – modelos compostos por m'ultiplas camadas, que tem recebido grande aten¸c˜ao nos 'ultimos anos. Um desses m'etodos, chamado de Rede Neural Convolucional, tem sido utilizado para atingir o estado da arte em v'arios problemas de vis˜ao computacional como, por exemplo, no problema de reconhecimento de objetos. Entretanto, esses m'etodos ainda n˜ao s˜ao amplamente explorados para o problema de classifica¸c˜ao de texturas. A presente disserta¸c˜ao preenche essa lacuna, propondo um m'etodo para treinar Redes Neurais Convolucionais para problemas de classifica¸c˜ao de textura, lidando com os desafios e tomando em considera¸c˜ao as caracter'ýsticas particulares desse tipo de problema. O m'etodo proposto foi testado em seis bases de dados de texturas, cada uma apresentando um desafio diferente, e resultados pr'oximos ao estado da arte foram observados para a maioria das bases, obtendo-se resultados superiores em duas das seis bases de dados. Por fim, 'e apresentado um m'etodo para transferˆencia de conhecimento entre diferentes problemas de classifica¸c˜ao de texturas, usando Redes Neurais Convolucionais. Os experimentos conduzidos demonstraram que essa t'ecnica pode melhorar o desempenho dos classificadores em problemas de textura com bases de dados pequenas, utilizando o conhecimento aprendido em um problema similar, que possua uma grande base de dados. Palavras chave: Reconhecimento de padr˜oes; Classifica¸c˜ao de Texturas; Redes Neurais Convolucionais / Abstract: Texture classification is a Pattern Recognition problem with a wide range of applications. This task is commonly addressed using texture descriptors designed by domain experts, and standard pattern recognition models, such as Support Vector Machines (SVM) and K-Nearest Neighbors (KNN). The classical method to address the problem relies on expert knowledge to build relevant (discriminative) feature extractors. Experts are required to create multiple texture descriptors targeting different scenarios (e.g. features that are invariant to image rotation, or invariant to blur). A different approach for this problem is to learn the feature extractors instead of using human knowledge to build them. This is a core idea behind Deep Learning, a set of models composed by multiple layers that are receiving increased attention in recent years. One of these methods, Convolutional Neural Networks, has been used to set the state-of-the-art in many computer vision tasks, such as object recognition, but are not yet widely explored for the task of texture classification. The present work address this gap, by proposing a method to train Convolutional Neural Networks for texture classification tasks, facing the challenges of texture recognition and taking advantage of particular characteristics of textures. We tested our method on six texture datasets, each one posing different challenges, and achieved results close to the state-of-the-art in the majority of the datasets, surpassing the best previous results in two of the six tasks. We also present a method to transfer learning across different texture classification problems using Convolutional Neural Networks. Our experiments demonstrated that this technique can improve the performance on tasks with small datasets, by leveraging knowledge learned from tasks with larger datasets. Keywords: Pattern Recognition; Texture Classification; Convolutional Neural Networks

Orientador : Prof. Dr. Eduardo Todt / Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 16/09/2014 / Inclui referências / Resumo: Os algoritmos de detecção de bordas necessitam de um poder muito alto de processamento, devido 'a quantidade de convoluções, problema agravado no caso de aplicações que exigem processamento de video em tempo real, como em rob'otica m'ovel. Uma maneira de melhorar o desempenho 'e implementar o algoritmo diretamente em hardware. Esta dissertação descreve um projeto de uma implementação do algoritmo de detecção de bordas Canny, realizada com a linguagem de descrição VHDL e com a linguagem de programação C++, em uma plataforma híbrida. A suavização, o cálculo do gradiente, a supressão de não máximos e o threshold duplo estão implementados em um computador de mesa do tipo PC (Personal Computer ) e a segunda etapa da histerese est'a implementada em um FPGA (Field Programmable Gate Array), modelo Virtex 6, da Xilinx. A arquitetura da parte implementada no FPGA 'e em pipeline e paralela. Palavras-chave: Canny; FPGA; Hardware Reconfigur'avel; VHDL; Processamento de Imagens; Detec¸c˜ao de Bordas; Arquitetura Paralela; Arquitetura H'ýbrida; pipeline. / Abstract: The edge detection algorithms require a very high power processing due the number of convolutions, an issue in real-time video applications like mobile robotics. One way to improve performance is to implement the algorithm directly in hardware. This paper describes and demonstrates the results of an implementation of the edge detection Canny algorithm performed with VHDL and the C++ programming language in a hybrid platform i.e.; Noise reduction, gradient intensity finding, non-maxima supression and double thresholding are implemented on a Desktop Personal Computer and the second part of hysteresis is implemented in a Xilinx Virtex 6 FPGA (Field Programmable Gate Array). The architecture designed on FPGA is a pipeline and parallel type. Keywords: Canny; FPGA; Reconfigurable Hardware; VHDL; Image Processing; Edge Detection; Parallel Architecture; Hybrid architecture; pipeline.

Orientador: Marcelo Messias / Banca: Marcos Tadeu de Oliveira Pimenta / Banca: Márcio Ricardo Alves Gouveia / Resumo: O presente trabalho apresenta e prova um resultado sobre a existência e unicidade de um ponto-fixo para contrações locais sem assumir que a família de coeficientes seja uniformemente limitada por um número estritamente menor que a unidade, bem como sem restringir a cardinalidade desta família. Mais importante, mostra como este resultado de ponto-fixo pode ser aplicado a fim de estudar a existência e unicidade de soluções para equações recursivas que aparecem em economia dinâmica / Abstract: This work presents and proves a result on the existence and uniqueness of a fixed point for local contractions without assuming that the family of coefficients is uniformly bounded for a number stricrly less unit, and without restricting the cardinality of this family. More importantly, it shows how this fixed-point result can be applied to study the existence and uniqueness of solutions to recursive equations that arise in dynamic economy / Mestre

Submitted by Maria Medeiros (maria.dilva1@ufcg.edu.br) on 2018-05-18T13:02:28Z No. of bitstreams: 1 BRUNO FÁBIO DE FARIAS PAIVA - DISSERTAÇÃO (PPGCC) 2016.pdf: 1168178 bytes, checksum: 6c0e24a4b1cecec06d1e8c0f8bdad27c (MD5) / Made available in DSpace on 2018-05-18T13:02:28Z (GMT). No. of bitstreams: 1 BRUNO FÁBIO DE FARIAS PAIVA - DISSERTAÇÃO (PPGCC) 2016.pdf: 1168178 bytes, checksum: 6c0e24a4b1cecec06d1e8c0f8bdad27c (MD5) Previous issue date: 2016 / CNPq / A computação pervasiva é um paradigma em que o computador se torna onipresente e invisível para o usuário, com capacidade de obter informações acerca do ambiente ao redor e utilizá-las para controlar, configurar e ajustar aplicações dinamicamente. Os sistemas pervasivos se caracterizam pelo uso de sensores disponíveis no ambiente, cujos dados são processados para prover serviços personalizados para os usuários. Atualmente, o principal gerador de dados de sensores é o dispositivo portátil pessoal, como smartphone e tablet, pois são dispositivos que possuem diversos sensores embutidos. Do ponto de vista de desenvolvimento de software, tem-se um grande esforço na aquisição, tratamento e processamento dos dados de sensores, principalmente considerando diferentes plataformas, modelos de dispositivos e fabricantes. Neste trabalho, propõe-se uma abordagem baseada em componentes para o desenvolvimento de aplicações pervasivas baseadas em contexto de ambiente, ou seja, que utilizam sensores como base de dados para prover serviços para o usuário. A abordagem foi validada utilizando um experimento de desenvolvimento de aplicações para a plataforma Android. Os resultados indicam redução no tempo de desenvolvimento e no número de linhas de código geradas ao utilizar a abordagem proposta. / The pervasive computing is a paradigm which the computer becomes ubiquitous and invisible to the user with the ability to get information about the surrounding environment and use them to control, configure and tune applications dynamically. Pervasive systems are characterized by the use of sensors, which capture data from the environment, and then processes, to provide personalized services to users. In certain environments, the main sensor data generator is the personal portable device, which has several built-in sensors, such as smartphones and tablets. From a software development perspective there is a great effort in acquisition, treatment and data processing, especially considering different platforms, device model and device manufacturers. In this work, we propose a component-based approach to develop pervasive applications based on the environmental context by providing services which uses sensor data. The validation of our approach was an experiment which developers used the Android platform. Results show a reduction in the development time and the number of lines generated using this approach.

Ce travail présente un modèle d'information, conçu de manière à permettre l'évaluation des produits, basé sur l'approche de la Conception pour la fabrication. Le modéle proposé concerne la représentation des piéces mécaniques , et il doit être utilisé en parallèle avec un système de Conception assisté par ordinateur, L'adequation du modèle d'information, ainsi que l'application de certains sujets spécifiques de la Conception pour la fabrication sont abordées.Un schéma de modèle d'information des produits et de la fabrication, basé sur la Technologie a base de caractéristiques a été developpé. Le modèle géométrique de pièces est basé sur l'approche des Bases de caractéristiques de forme et sur la méthode de Synthèse d'élements wolumetriques. Les sujets liés à la Conception pour la fabrication- nottement la Technologie de groupe, le Choix des procedés de fabrication des piéces et l'application des consignes de fabrication- ont eté mis en ocuvre, à partir des téchniques de la Modelisation de la connaissence. Les procédés liés à la sélection des procédes ont été utilises, afin d'aider les projecteurs à obtenir une définition approché du procedé de fabrication de lá pièce, avant de l'active de planification du processus. Le modéle d'information est sencé d1être capable de génére une base suffisante pour établir une analyse liée a la Planification des processus. Il est important de remarquer que ce travail fait partie d'un effort de mis en ocuvre de L'ingeniere concourante, ainsi que de son approximantion des domanines du projet et de la fabrication. Cet objectif est atendu par le biais d'utilisation d'un outil d'informatque adequat à l'aide des projecteurs dans la tâche de l'évalution du projet des pièces (par rapport aux besoins de fabrication). / Este trabalho introduz um modelo de representação da informação concebido para permirtir a avalição de produto baseado nas abordagens providas pelo Projecto Orientado à Fabricação. Esse modelo concentra-se no domínio das peças mecânicas e é suposto que venha a operar conjuntamente com um sistema de desenho assistido por computador. Tanto a adequação do modelo de representação da informação, quanto a aplicação de tópicos específicos em Projecto Orientado à Fabricação são discutidas. Um esquema de representação da informação sobre o produto e a fabricação baseado na Tecnologia de Características foi desenvolvido. O modelo geométrico da peça é baseado na abordagem da utilização de bases de formas características e no método de síntese de volumes elementares. Um protótipo de modelo de representação da informação foi implementado baseado no paradigma de programação orientada a objectos. A adequação do modelo de representação da informação é examinada considerando-se a necessidade de viabilizar a análise das peças mecânicas baseada no Projecto Orientado à Fabricação. Os tópicos ralacionados com o Projecto Orientado à Fabricação- nomeadamente a Tecnologia de Grupo, a slecção de processos de fabricação das peças e a aplicação de recomendações para a fabricação- foram implementadas, utilizando-se técnicas de engenharia de conhecimento. Os procedimentos relacionados com a selecção de processos foram incluídos para auxiliar os prejectíticas a obterem uma definição aproximada do processo de fabricação da peça precedendo a actividade de planeamento do processo. Espera-se que este modelo de representação da informação também seja capaz de prover uma base razoavel para o estabelecimento da análise relcionada com o planeamento de processos. Observa-se que este trabalho insere-se no esforço de implementação da engenharia concorrente através da tentativa de aproximar as áreas de projecto e fabricação. Este objectivo é alcançado pela utilização de uma ferramenta computacional adequada para assistência aos projectistas na tarefa de avalição do pejecto da peça (face aos requisisto de fabricação). / This work introduces an information model conceived to enable product evaluation based on the design for manufacture approach. It concentrates on the mechanical parts domain and it is supposed to operate coupled wiht a computer-aided drafting system. Both the information model adequacy and the application of specific desing for manufacture topics are discussed. A product and manufacturing information representation scheme based on the Features Technology was developed. The geometric part model is based on the desing by features approach and the synthesis of volumetric elements method. It was implemented an information model protoype based on the object-oriented programming paradigm. The information model adequacy is examined considering the need for enabling mechanical part analysis based on the design for manufacture.The desing for manufacture related topics- namely concerning Group Technology, part manufacturin process selection and manufacturin rules application- were impelmented using knowledge engineering tecniques. The process selection procedure was included to help designers obtaining a coarse definition on part manufacturing process preceding the process palnning activity. This information model is also expected to provide a regular basis for the process planning reasoning. It must be noticed this work is embedded in the concurrent enginerring implementation effort by attempting to bridge the gap between desing and manufacture. This obective is achieved by using and adequate software tool which assist designers in the part design evaluation task (inface of manufaturing requiremenst).

Dissertação (mestrado)—Universidade de Brasília, Faculdade de Tecnologia, 2014. / Submitted by Albânia Cézar de Melo (albania@bce.unb.br) on 2014-12-02T15:12:17Z No. of bitstreams: 1 2014_RobertoLemosColletti.pdf: 2319887 bytes, checksum: 6fb627e93dd1f7a9ef065cd99de3de6d (MD5) / Approved for entry into archive by Guimaraes Jacqueline(jacqueline.guimaraes@bce.unb.br) on 2014-12-03T15:03:59Z (GMT) No. of bitstreams: 1 2014_RobertoLemosColletti.pdf: 2319887 bytes, checksum: 6fb627e93dd1f7a9ef065cd99de3de6d (MD5) / Made available in DSpace on 2014-12-03T15:03:59Z (GMT). No. of bitstreams: 1 2014_RobertoLemosColletti.pdf: 2319887 bytes, checksum: 6fb627e93dd1f7a9ef065cd99de3de6d (MD5) / Nesse trabalho, é proposto um modelo analítico para a avaliação do tempo de vida de enlaces (ou LLT, do inglês link lifetime) para o modelo de mobilidade Random Waypoint (RWP), em redes móveis ad hoc. A partir do método do jacobiano para otenção da função densidade de probabilidade (ou pdf, do inglês probability density function) de funções de variáveis aleatórias, as pdfs do tempo de vida do enlace e do tempo de vida residual são desenvolvidas para qualquer escolha de velocidades no RWP. Os resultados obtidos são comparados com simulações de enlaces feitas usando o RWP e o Uniform Mobility Model (UMM). Além disso, com uma relação conhecida da teoria de processos de renovação, encontra-se a estatística completa do tempo de vida residual (Residual Link Lifetimes ou RLL) correspondente. Ainda, investigam-se alguns cenários de fronteira onde a simulação não se comporta como o modelo, de nindo-se seu escopo de aplicação. Por m, por meio das simulações, mostra-se que o modelo analítico desenvolvido para o RWP pode ser empregado também para descrever o tempo de vida de enlaces no UMM. ________________________________________________________________________________________ ABSTRACT / In this work, we propose an analytical model to evaluate the link lifetime (LLT) for the Random Waypoint (RWP) mobility model. By employing the jacobian method used to obtain the probability density function (pdf) of functions of random variables, we derive the pdfs of link lifetime (LLT) and residual link lifetime (RLL) under any choice of speeds for the RWP model. Results are compared with simulations performed using both RWP and Uniform Mobility Model (UMM). Further on, employing the theory of renewal processes, we derive the corresponding statistics of residual link lifetime. Some limiting scenarios that are shown not to agree with the model are investigated, thus, de ning its scope. Lastly, it is shown that the model can be employed to describe link lifetime under UMM.

Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2011. / Submitted by Albânia Cézar de Melo (albania@bce.unb.br) on 2012-10-22T12:42:15Z No. of bitstreams: 1 2011_HumphreyCorreaFonseca.pdf: 24779734 bytes, checksum: b5fa28e9a4144784cac443891d0ef50a (MD5) / Approved for entry into archive by Guimaraes Jacqueline(jacqueline.guimaraes@bce.unb.br) on 2012-10-25T10:19:46Z (GMT) No. of bitstreams: 1 2011_HumphreyCorreaFonseca.pdf: 24779734 bytes, checksum: b5fa28e9a4144784cac443891d0ef50a (MD5) / Made available in DSpace on 2012-10-25T10:19:46Z (GMT). No. of bitstreams: 1 2011_HumphreyCorreaFonseca.pdf: 24779734 bytes, checksum: b5fa28e9a4144784cac443891d0ef50a (MD5) / Sistemas orientados a contexto têm apresentado um crescente interesse na comuni- dade de computação, uma vez que necessitam uma melhor integração do usuário com o ambiente onde ele se insere. No entanto, a primeira tarefa durante a de nição de uma aplicação sensível ao contexto é a localização do usuário, a qual deve ser feita de forma dinâmica e inteligente. O problema de localização se mostra mais complexo quando se verifi ca a existência de diversos dispositivos móveis, transmitindo simultaneamente sinais na mesma radiofreqüência, que podem ser usados para determinar posição do usuário através de dispositivos eletrônicos, com padrões diferentes, como o Bluetooth (IEEE 802.15.1), Zigbee (IEEE 802.15.4) e Wi-Fi (IEEE 802.11). Diante do exposto, esse trabalho aborda o problema de localização de usuários em ambientes fechados, através do uso de diferentes protocolos com abordagem de rede neural e sistemas multiagente tendo aplicado aspectos de qualidade de serviço. ______________________________________________________________________________ ABSTRACT / Context-oriented systems have received greather interest in the computing commu- nity, since they need a better user integration with the environment. However, the rst task when de ning a context sensitive application is the user location, which must be done dynamically and intelligently. The location problem appears more complex when it checks for various electronic devices, transmitting signals simultaneously on the same radio frequency, which can be used to determine position of an electronic device, but in deferent patterns, such as Bluetooth (IEEE 802.15.1), ZigBee (IEEE 802.15.4) and Wi-Fi (IEEE 802.11). Given the above, this work addresses the problem of locating users indoors, through the use of diferent protocols with neural network approach with multi-agent systems and applied aspects of quality of service.

Dissertação (mestrado)—Universidade de Brasília, Faculdade de Tecnologia, Departamento de Engenharia Elétrica, 2012. / Submitted by Alaíde Gonçalves dos Santos (alaide@unb.br) on 2013-03-13T11:31:05Z No. of bitstreams: 1 2012_GersonLuizHaus.pdf: 957180 bytes, checksum: f9c596d9013a74353fb90cf2ae82584d (MD5) / Approved for entry into archive by Guimaraes Jacqueline(jacqueline.guimaraes@bce.unb.br) on 2013-03-26T11:30:30Z (GMT) No. of bitstreams: 1 2012_GersonLuizHaus.pdf: 957180 bytes, checksum: f9c596d9013a74353fb90cf2ae82584d (MD5) / Made available in DSpace on 2013-03-26T11:30:30Z (GMT). No. of bitstreams: 1 2012_GersonLuizHaus.pdf: 957180 bytes, checksum: f9c596d9013a74353fb90cf2ae82584d (MD5) / O trabalho descrito nesta dissertação objetiva identificação de tráfego de rede proveniente de interceptação telemática judicialmente autorizada utilizando WEKA (Waikato Environment for Knowledge Analysis).Propõe-se o desenvolvimento de um método de identificação do tráfego de rede gerado pelo aplicativo P2P (peer-to-peer) BitTorrent. Com a identificação do fluxo de rede do BitTorrent podem ser obtidas informações periciais importantes tais como: provas de materialidade, delimitação geográfica dos locais para onde foram transferidos arquivos, entre outras informações. A proposta deste trabalho emprega o conjunto de ferramentas WEKA, com o uso do algoritmo J.48 (baseado no C4.5) e SVM (Support Vector Machine), para classificar o fluxo de dados que utilizou criptografia. Como resultado experimental, foram detectados até 97,03% do tráfego criptografado. Os resultados experimentais alcançados demonstram a viabilidade da utilização do WEKA para a identificação de tráfego do BitTorrent. _______________________________________________________________________________________ ABSTRACT / The work described in this thesis aims at identifying network traffic from interception telematics judicially authorized using WEKA (Waikato Environment for Knowledge Analysis). It is proposed the development of a method for the identification of network traffic generated by P2P (peer-to-peer) application BitTorrent. With the identification of the BitTorrent network flow information can be obtained important expert such as: proofs of materiality, geographical boundaries of sites for which they have been transferred files, among other information. The proposal of this work employs the WEKA toolset, using J.48 (based on C4.5) and SVM (Support Vector Machine)algorithms, to sort the data flow that uses encryption. As a result, 97.03% of the encrypted traffic were detectThe experimental results achieved demonstrate the feasibility of using WEKA for identifying BitTorrent traffic.

Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2012. / Submitted by Alaíde Gonçalves dos Santos (alaide@unb.br) on 2013-04-26T15:53:16Z No. of bitstreams: 1 2012_FabioHenriquedaSilva.pdf: 552243 bytes, checksum: e64f674891aeafd428d4d66fd0fe9706 (MD5) / Approved for entry into archive by Guimaraes Jacqueline(jacqueline.guimaraes@bce.unb.br) on 2013-07-29T13:03:08Z (GMT) No. of bitstreams: 1 2012_FabioHenriquedaSilva.pdf: 552243 bytes, checksum: e64f674891aeafd428d4d66fd0fe9706 (MD5) / Made available in DSpace on 2013-07-29T13:03:08Z (GMT). No. of bitstreams: 1 2012_FabioHenriquedaSilva.pdf: 552243 bytes, checksum: e64f674891aeafd428d4d66fd0fe9706 (MD5) / Os cálculos de Substituições Explícitas (CSEs) são variações do cálculo λ que especificam de maneira concreta a operação de substituição, definida de maneira implícita no cálculo λ. Estes cálculos estendem a linguagem do cálculo λ de maneira a atomizar os passos envolvidos numa aplicação concreta da operação de substituição. Este trabalho abordará a propriedade de expansibilidade em alguns CSEs que podemos dizer que seja uma investigação do passado de um termo. Esta propriedade é interessante quando este passado nos revela um termo puro, ou seja, um termo pertencente à linguagem do cálculo λ Para isso fez-se necessário estudar várias outras propriedades, como a simulação da regra β do cálculo λ, a correção da regra (B) no λ? -cálculo e, a propriedade de Projeção do λ?-cálculo e do λσ-cálculo. O objetivo é estudar o problema de expansão no lambda sigma-cálculo, e para isso observamos os resultados de Ariel Arbiser no lambda upsilon-cálculo, em que o Teorema de Scott foi uma ferramenta crucial. _______________________________________________________________________________________ ABSTRACT / Calculi of Explicit Substitutions (CSEs) are variants of the λ calculus which specify concretely the substitution operation, defined implicitly in the λ calculus. These calculi extend the language of λ calculus in order to atomize the steps involved in the practical application of replacement operation. This work will discuss the expansion property in some CSEs, that it is an investigation of the past of a term. This property is interesting when it discloses a past term pure, i.e. a term belonging to the language of λ calculus. For this it was necessary to study several other properties, such as the simulation of rule β of λ calculus, the correction of the rule (B) in λ?-calculus and the property projection of λ?-calculus and the λσ-calculus. The goal is to study the expansion problem in the λσ-calculus and verify the aplication of the results of Ariel Arbiser in the λ?-calculi, in which the Scott Theorem was a crucial tool.

Dissertação (mestrado)—Universidade de Brasília, Departamento de Ciência da Computação, 2013. / Submitted by Albânia Cézar de Melo (albania@bce.unb.br) on 2013-07-15T16:43:11Z No. of bitstreams: 1 2013_JoseLuisSonccoAlvarez.pdf: 1018122 bytes, checksum: 9dd7f3ffe2e2bdb1cb9b764e37a8d6a1 (MD5) / Approved for entry into archive by Guimaraes Jacqueline(jacqueline.guimaraes@bce.unb.br) on 2013-08-02T13:47:05Z (GMT) No. of bitstreams: 1 2013_JoseLuisSonccoAlvarez.pdf: 1018122 bytes, checksum: 9dd7f3ffe2e2bdb1cb9b764e37a8d6a1 (MD5) / Made available in DSpace on 2013-08-02T13:47:05Z (GMT). No. of bitstreams: 1 2013_JoseLuisSonccoAlvarez.pdf: 1018122 bytes, checksum: 9dd7f3ffe2e2bdb1cb9b764e37a8d6a1 (MD5) / Ordenação de permutações por reversões é um dos problemas mais desafiantes relacionados com a análise da distância evolutiva entre organis- mos, cujos resultados podem ser usados na construção de árvores filogenéticas baseadas nesta distância. No caso de permutações com sinal, o problema pode ser resolvido em tempo linear, porém, no caso de permutações sem sinal o problema é mais complexo, já que foi demonstrado ser NP-difícil e com uma questão ainda em aberto: se é ou não NP completo; este foi o motivo pelo qual foram propostos diversos algoritmos de aproximação e de computação evolucionária. Neste trabalho, é proposto um algoritmo genético(AG) padrão para resolver o problema de ordenação de permutações sem sinal. Este enfoque está baseado no método proposto por Auyeung e Abraham, que usa soluções exatas para o caso de permutações com sinal, para resolver a versão do problema com permutações sem sinal. Adicionalmente, foi proposto um algoritmo genético melhorado (hibrido), que usa uma heurística de eliminação de pontos de quebra em gerações iniciais. Diversos experimentos foram feitos tomando como entrada permutações gera- das aleatoriamente, escolhendo um elemento aleatório sobre um conjunto de números, ou aplicando reversões aleatórias sobre uma permutação ordenada. Ademais, foram usadas permutações de Gollan as quais sabemos que podem ser ordenadas usando n — 1 reversões, onde n é o comprimento da permutação. Desde que muitos enfoques de AG's usaram mecanismos de controle impreci- sos para validar a precisão das suas respostas, foi necessário um grande esforço para desenvolver uma algoritmo de aproximação confiável. Dando origem a um desenvolvimento teórico baseado no algoritmo de raio de aproximação 1.5 proposto por Christie, e sua posterior implementação. Os experimentos mostraram que ambos AG fornecem respostas que são melhores do que aquelas fornecidas por métodos relacionados prévios, tanto como os que são fornecidos pelo algoritmo de raio de aproximação 1.5 corrigido. ______________________________________________________________________________ ABSTRACT / Sorting permutations by reversals is one of the most challenging problems related to the analysis of the evolutionary distance between organisms, whose results can be used in the construction of phylogenetic trees bases on this distance. In the case of signed permutations, the problem can be solved in linear time, however in the case of unsigned permutations the problem is more complex, since it was shown to be NP-hard and it is unknown whether it is NP-complete or not; this fact motivated the proposal of several approximation, and evolutionary computing algorithms. In this work, we propose genetic algorithms (GA) to solve the problem of sorting unsigned permutations. Initially, we propose a standard GA approach based on the method proposed by Auyeung and Abraham, which uses exact polynomial solutions for the case of signed permutations, for solving the problem with unsigned permutations. Further, we propose an improved genetic algorithm, which uses the heuristic of elimination of break points in early generations and then the standard approach. Several experiments were made using as inputs permutations generated randomly by choosing a random element over a set of numbers, and by applying random reversals over an sorted permutation. Also, was used Gollan permutations that it's well-known that can be sorted by n 1 reversals, where n is the length of the permutation. Since previous GA approaches have used imprecise control mechanisms for checking the accuracy of their answers, a great deal of e ort was necessary in order to develop a reliable approximate algorithm. This gave rise to a theoretical development based on the well-known Christie's 1.5 ratio approximation algorithm and its further implementation. Experiments showed that both AG approaches compute answers that are better than the ones computed by previous approaches as well as than the ones computed with the adjusted correct 1.5 approximation algorithm.