Submitted by Reginaldo Soares de Freitas (reginaldo.freitas@ufv.br) on 2016-04-26T17:01:30Z No. of bitstreams: 1 texto completo.pdf: 6402016 bytes, checksum: 2ad43c5bb42a77cb19379857a960b47d (MD5) / Made available in DSpace on 2016-04-26T17:01:30Z (GMT). No. of bitstreams: 1 texto completo.pdf: 6402016 bytes, checksum: 2ad43c5bb42a77cb19379857a960b47d (MD5) Previous issue date: 2015-12-08 / Fundação de Amparo à Pesquisa do Estado de Minas Gerais / O Problema do Caixeiro Viajante Preto e Branco (PCV-PB) é uma generalização do Problema do Caixeiro Viajante (PCV), definido sobre um grafo onde os vértices são classificados como pretos ou brancos. Assim como o clássico PCV, o objetivo do PCV-PB é encontrar um ciclo hamiltoniano de custo mínimo, entretanto, duas restrições adicionais são consideradas. Enquanto que a restrição de cardinalidade restringe o número de vértices brancos entre dois vértices pretos consecutivos, a restrição de comprimento restringe a distância máxima entre os mesmos. Apli- cações do PCV-PB podem ser observadas no escalonamento de aeronaves e em configurações de redes de telecomunicações. A proposta deste estudo é analisar diferentes estratégias heurísticas aplicadas para o PCV-PB. Heurísticas construtivas da literatura foram aperfeiçoadas e uma nova estratégia para a construção da solução foi apresentada. Neste contexto foi utilizado métodos como Lin kernighan e Inserção Específica de Brancos. Além disso, foram propostas abordagens heurísticas baseadas nas metaheurísticas GRASP, VND, ILS e SA. Diversos experimentos computacionais foram realizados para comparar a eficácia das abordagens. Os resultados garantem a aplicabilidade dos algoritmos propostos para o problema. / The Black and White Traveling Salesman Problem (TSP-BW) is a generalization of the Travelling Salesman Problem (TSP), set on a graph where the vertices are classified as black or white. As in the classical PCV, a solution of the TSP-BW is a Hamiltonian cycle of minimal cost. However, two additional constraints are considered. While the cardinality constraint limits the number of white vertices between two consecutive black vertices, the length constraint restricts the maximum distance therebetween. Applications of TSP-BW can be observed in aircraft scheduling and telecommunications network settings. The purpose of this study is to analyze different heuristic strategies applied to TSP-BW. Literature constructive heuristics have been improved and a new strategy for building the solution was presented. In this context it used methods such as Lin Kernighan and Inserção Específica de Brancos. Also, it has been proposed heuristic approaches based on metaheuristics GRASP, VND, ILS and SA. Several computational experiments were performed to compare effectiveness of approa- ches. The results ensure the applicability of the proposed algorithms to the problem.

ALENCAR, João Marcelo Uchôa de. Reconfiguração elástica de componentes paralelos em nuvens de serviços de Computação de Alto Desempenho. 2017. 134 f. Tese (Doutorado em Ciência da Computação)-Universidade Federal do Ceará, Fortaleza, 2017. / Submitted by Jonatas Martins (jonatasmartins@lia.ufc.br) on 2017-09-20T19:48:38Z No. of bitstreams: 1 2017_tese_jmualencar.pdf: 2927371 bytes, checksum: 31dbca226eba1a11536c49993d0056f5 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2017-09-21T12:29:09Z (GMT) No. of bitstreams: 1 2017_tese_jmualencar.pdf: 2927371 bytes, checksum: 31dbca226eba1a11536c49993d0056f5 (MD5) / Made available in DSpace on 2017-09-21T12:29:09Z (GMT). No. of bitstreams: 1 2017_tese_jmualencar.pdf: 2927371 bytes, checksum: 31dbca226eba1a11536c49993d0056f5 (MD5) Previous issue date: 2017 / Researchers willing to run scientific applications have a vast choice of computing infrastructures such as supercomputers and clouds. Since these infrastructures are of shared nature, it is usual to face variability in the state of resources during the execution of a parallel program. End users and developers should have the capability to adapt and control execution to ensure compliance with quality of service requirements. In the particular case of clouds, the reconfiguration is enabled by the concept of elasticity. In this Thesis, we present an architecture for a framework that allows the stakeholders to define policies and mechanisms of control at runtime for the elasticity of components of parallel systems, changing the set of allocated resources. We use the HPC Shelf cloud of components as the execution environment. This cyberinfrastructure presents a contextual contract system that allows the proper description and allocation of components and virtual platforms, defining the optimized match according to the characteristics of the parallel programs and the resources available on the platforms. Contextual contracts also allow the definition of quality of service contracts according to researchers' priorities and requirements. The resulting HPC Shelf environment with elastic reconfiguration control expands the options for the stakeholders, ensuring that the runtime respects the component service quality contract in the face of incomplete information and fluctuations in the environment. / Os pesquisadores que desejam executar aplicações científicas possuem uma vasta opção de infraestruturas computacionais como supercomputadores e nuvens. Essas infraestruturas são de natureza compartilhada, é norma existirem mudanças no estado dos recursos durante a execução de um programa paralelo. É importante que os usuários finais e os desenvolvedores tenham meios de adaptar e controlar a execução para garantir o cumprimento de requisitos de qualidade de serviço. No caso específico das nuvens, a reconfiguração é habilitada pelo conceito de elasticidade. Nesta Tese, apresentamos uma arquitetura para um arcabouço que permita aos atores envolvidos definir políticas e mecanismos de controle em tempo de execução para a elasticidade de componentes de sistemas paralelos, alterando o conjunto de recursos alocados. Utilizamos como ambiente de execução a nuvem de componentes HPC Shelf. Esse ambiente apresenta um sistema de contratos contextuais que permite a descrição e alocação adequada de componentes e plataformas virtuais, definindo a combinação otimizada de acordo com as características dos programas paralelos e os recursos disponíveis nas plataformas. Os contratos contextuais também permitem a definição de contratos de qualidade de serviço de acordo com prioridades e requisitos dos pesquisadores. Dessa forma, o ambiente resultante da HPC Shelf com controle de reconfiguração elástica amplia as opções dos atores envolvidos, garantindo que o contrato de qualidade de serviços dos componentes seja respeitado diante de informações incompletas e de mudanças no ambiente.

O objetivo principal deste trabalho é apresentar uma. descrição detalhada sobre as diversas abordagens do Problema do Caixeiro Viajante, a complexidade na sua resolução e as aplicações nas diversas áreas do conhecimento. O Problema do Caixeiro Viajante é um dos mais conhecidos e estudados problemas da Teoria dos Grafos e sua importância é tanta teórica quanto prática. O resultado teórico mais importante que apresentamos neste trabalho é a prova de que o PCV é -P-Completo, usando (e provando) o Teorema de Cook, como ponto de partida e a Máquina de Turing como o modelo computacional para as provas da complexidade dos problemas envolvidos. O PCV é equivalente ao problema de encontrar um circuito Hamiltoniano de peso mínimo em um grafo ponderado. Uma das questões principais envolvidas neste problema, e na verdade uma das principais indagações da Ciência da Comput ação, é saber se existe um algoritmo eficiente de tempo polinomial para calcular tal circuito, ou se tal algoritmo não existe, caracterizando-o, assim, como um problema impossível de ser resolvido. Quando não se pode encontrar uma solução eficiente para um dado problema e também não pode ser demonstrado que tal solução existe, deve-se usar técnicas que permitam construir um algoritmo que forneça soluções aproximadas. Neste trabalho, apresentamos um algoritmo de tempo polinomial que nos fornece soluções aproximadas para o PCV. / The main objective of this work is to present a detailed description on the various approaches to the Traveling Salesperson Problem (TSP), the complexity of its solution and its applications to the various knowledge area.s. The Traveling Salesperson Problem is one of the most known and studied problems in graph theory and its importance is theoretical as well as practical. The theory result more important who we will introduce in this work is the proof of the TSP is NP-complete, using (and proving) of Cook's Theorem like point of departure and the Turing Machine like the model computational for the tests of complexity of problems involved. The TSP is equivalent to the problem of finding a Hamiltonian circuit of minimal weight in a weighted graph. One of the main questions involved in this problem, and actually one of the main questions of the whole Computing Science, is to know if there exists an polynomial-time efficient algorithm to compute such a circuit, or if such an algorithm can not exist, then characterizing it as an impossible problem. When one can not find an efficient solution for a given problem and also can not show that such a solution exists, we must use techniques that aid us to construct an algorithm providing approximate solutions. In this work, we will present a polynomial-time algorithm that gives approximate solutions for the solution of the Traveling Salesperson Problem.

Neste trabalho, são apresentados aspectos analíticos computacionais em funções matriciais , enfatizando-se os métodos de Aproximação de Runckel-Pittelkow , dos Aproximantes de Padé e de Decomposição Matricial. É estudada também, a sensibilidade das funções matriciais , isto é, o comportamento das funções matriciais frente perturbações da matriz . Como importante aplicação das fórmulas de Runckel & Pittelkow são obtidas expressões para a solução dinâmica de uma equação diferencial matricial . Além disso, com base nestas fórmulas, é apresentado um programa computacional para computar exponenciais matriciais .

Fenômenos como a rápida propagação de epiderriias em escala mundial têm chamado a atenção 'para a importância da estrutura da rede de contatos, através da qual os membros de uma comunidade interagem entre. si. O efeito da topologia das redes de contatos sociais na dinâmica de epidemias tem sido .estudado recentemente de maneira geral em redes paradigmáticas (inundo pequeno, livre de escala, etc), mostrando efeitos que dão outra dimensão aos resultadps típicos de campo médio, ou seja, ausência de limiar de epidemia e limiar de epidemia dependente da topologia. Motivados por estes resultados, analisamos e implementamos: modelos teóricos 'e computacionais de propagação de epidemias. Em termos de contribuição,' primeiramente, apresentamos uma solução algébrica para o modelo SIR. na aproximação de campo médio. Em seguida; desenvolvemos um modelo de rede de interação. dinâmica a qual se desenvolve uma epidemia. *Entre os resultados, achamós que o tempo característico de formação da rede frente ao ternpo da doença influencia na dinâmica da epi demia. Por fim, utilizando dá dinâmica da doença, comparamos uma rede real de, contatos amorosos com as redes paradigmáticas. Concluímos, que estrutura estática real comporta-se como uma rede aleatória e que a inserçãO da formação dinâmica das interações atenua os efeitos da epidemia. / Phenomena such as the rapid spread of epidermes on a global scale have drawn attention to the importante of the structure of the network, through which members of a cornmunity interact. The effect of 'the network topology of social contacts the dyriamics of ,epidemics has been studied recently in general network models (small world, scale free, etc), showing effects that give another dimension to the results of typical mean field, or absence of epidemic threshold and epidemic threshold depends on the topology. Motivated by these results; we analyze and implement theoretical and computational fflodels for the sprea,d of epidermes. In terms of contribution, first, we present an algebraic solution for the SIR model in the mean field approximátion. Further, we develop a network model for the dynarnic interaction between individuais in which develops an epidemic. Among the results, we found that the characteristic time of formation of the network against the time of disease infiuences the dynamics of the epidemic. Finally, using the dynamics of the disease, we cornpáred a real network of loving contacts with the network model. We conclude that real static structure behaves like a random network and that the insertion of the formation dynamies of interactions attenuates the effects of the epidernic..

TEIXEIRA, D. N. Uma técnica de decomposição a priori para geração paralela de malhas bidimensionais. 2014. 95 f. Dissertação (Mestrado em Ciência da Computação) - Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2014. / Submitted by Daniel Eduardo Alencar da Silva (dealencar.silva@gmail.com) on 2015-01-23T18:25:13Z No. of bitstreams: 1 2014_dis_dnteixeira.pdf: 17919971 bytes, checksum: 092ad12b33cf64a31552e6a839a5a5bc (MD5) / Approved for entry into archive by Rocilda Sales(rocilda@ufc.br) on 2015-09-23T16:26:52Z (GMT) No. of bitstreams: 1 2014_dis_dnteixeira.pdf: 17919971 bytes, checksum: 092ad12b33cf64a31552e6a839a5a5bc (MD5) / Made available in DSpace on 2015-09-23T16:26:52Z (GMT). No. of bitstreams: 1 2014_dis_dnteixeira.pdf: 17919971 bytes, checksum: 092ad12b33cf64a31552e6a839a5a5bc (MD5) Previous issue date: 2014 / This work describes a technique of two-dimensional domain decomposition for parallel mesh generation. This technique works for both distributed and shared memory and has the freedom to use any data structure that manages rectangular regions parallel to the axes to decompose the domain given as input, such as a quaternary tree (quadtree) or a binary space decomposition (bsp), for example. Any process of mesh generation that respects the prerequisites established can be used in the subdomains created, for instance, Delaunay or Advancing Front, among others. This technique is called a priori because the mesh on the interface of the subdomains is generated prior to the their internal meshes. The load estimation for each sub-domain in this work is performed with the aid of a refined quadtree, whose level of refinement guides the creation of edges that are defined from the bounderies of only inner cells. This way of estimate load produces results that accurately represent the number of elements to be generated in each subdomain. That contributes to a good partitioning of the domain, making the mesh generation in parallel be significantly faster than the serial generation. Furthermore, the quality of the generated mesh in parallel is qualitatively equivalent to that generated serially within acceptable limits. / Este trabalho descreve uma técnica de decomposição de domínios bidimensionais para geração em paralelo de malhas. Esta técnica funciona tanto para memória distribuída quanto compartilhada, além de permitir que se utilize qualquer estrutura de dados que gere regiões quadrangulares paralelas aos eixos para decompor o domínio dado como entrada. Pode se utilizar por exemplo, uma árvore quaternária (quadtree) ou uma partição binária do espaço (bsp). Além disso, qualquer processo de geração de malha que respeite os pré-requisitos estabelecidos pode ser empregado nos subdomínios criados, como as técnicas de Delaunay ou Avanço de Fronteira, dentre outras. A técnica proposta é dita a priori porque a malha de interface entre os subdomínios é gerada antes das suas malhas internas. A estimativa de carga de processamento associada a cada subdomínio é feita nesse trabalho com a ajuda de uma quadtree refinada, cujo nível de refinamento orienta a criação das arestas que são definidas a partir da discretização das fronteiras das células internas. Essa maneira de estimar carga produz resultados que representam, com boa precisão, o número de elementos a serem gerados em cada subdomínio. Isso contribui para um bom particionamento do domínio, fazendo com que a geração de malha em paralelo seja significativamente mais rápida do que a geração serial. Além disso, a qualidade da malha gerada em paralelo é qualitativamente equivalente àquela gerada serialmente, dentro de limites aceitáveis.

O trabalho que se descreve consiste na implementação do programa FullProf para refinamento estrutural. Trata-se de um programa baseado no método Rietveld, disponível na internet. Uma vez adaptado às instalações locais, o programa foi submetido a uma série de ensaios para avaliação de seu comportamento frente a possíveis artefatos experimentais e computacionais, bem como frente à estratégia de refinamento. Constatou-se que o programa é muito sensível à estratégia de refinamento, podendo-se perder em mínimos locais; os parâmetros de rede e as posições atômicas informados inicialmente podem apresentar erro máximo de cerca de 1 % e 20 %, respectivamente, dependendo da amostra; erros na interpretação do refinamento podem resultar de equívocos de apreciação dos fatores de qualidade de ajuste, uma vez que são susceptíveis a alguns tipos de artefatos experimentais e computacionais; a sensibilidade frente à correta definição do grupo espacial é grande e erros nesta definição acarretam em divergência no processo de refinamento; os parâmetros de assimetria são importantes para o ajuste de picos difratados a baixos ângulos; o uso do parâmetro refinável que descreve o deslocamento experimental da origem da escala 2q, é imprescindível. Finalmente o programa foi usado para refinamento estrutural de amostras do tipo FexCo1-xTa2O6; determinação de cristalinidade relativa em polipropilenos isotáticos e identificação de fases em ligas submetidas a tratamentos de superfície. / The work described in the present Dissertation consists of the program FullProf implementation. It is a program for structural refinement, based on the Rietveld method, available in the internet. Once adapted to the local facilities, the program was submitted to a series of evaluation essays of its behaviour against possible experimental and computational artefacts and refinement strategy as well. It was verified that the program is very sensitive to the refinement strategy, occasionally going to be trapped in local minima; the initial cell parameters and atomic positions can present, respectively, maximum deviation of about 1% and 20%, depending on the sample; mistakes on the refinement interpretation can result from equivocated appreciation of the agreement factors, since they are susceptible to some kind of experimental and computational artefacts; the sensibility facing the correct definition of the space group is high and mistakes in this definition usually result in refinement divergence; the asymmetry parameters are important for the fitting of diffracted peaks in low angles; the use of the zero- 2q parameter, related to the experimental shift of the 2q-scale origin, is indispensable. Finally, the program was used for structural refinement of samples of the type FexCo1-xTa2O6; determination of relative crystalline fraction in isotactic polypropylene and phase identification in alloys submitted to surface treatments.

Este trabalho propõe uma metodologia onde usamos experimentos numéricos para determinar os parâmetros de um modelo neural mais simples e, a partir deste modelo assim ajustado, tentamos estudar suas propriedades dinâmicas com a intenção de achar leis mais gerais que possam ser aplicadas a modelos mais complexos. Para este fim, os experimentos que medem a resistência, a corrente de reobase do neurônio e o decaimento do potencial de SAG se apresentam como bons candidatos para ajustar os parâmetros do modelo a dados experimentais, onde a consistência desse ajuste pode ser testada usando tanto o experimento de ressonância do potencial da membrana, como a frequência de oscilações subliminares induzidas por ruído, comparando os resultados obtidos com resultados experimentais. / This work proposes a methodology where we use numerical experiments to determine the parameters of a simple neural model, and from this model thus adjusted, try to study its dynamic properties with the intention of nding the most general laws that can be applied to more complex models. To this end, experiments measuring resistance, rheobase current and the SAG potential decay are good candidates to adjust the parameters of the model to experimental data, where the consistency of the adjustment can be tested using both the experiment of resonance membrane potential and the frequency of subthreshold oscillations induced by noise, by comparing the results with experimental results.

Neste trabalho desenvolvemos um algoritmo para a geração de malhas quadtree com o objetivo de utilizá-las na simulação de escoamento de fluidos, onde muitas vezes faz-se necessário o uso de malhas finas. A idéia central da geração das malhas quadtree está baseada na estrutura de árvore quaternária em que cada nodo possui quatro filhos. Assim uma estrutura de árvore está associada a uma malha que pode ter espaçamento uniforme ou refinamento em regiões específicas. Para evitar problemas de discretização, uma malha quadtree deve satisfazer um critério chamado de balanceamento e este é tratado de forma detalhada no desenvolvimento do trabalho. Podemos destacar também outro ponto importantíssimo na implementação de malhas quadtree, que é a busca de vizinhos dos nodos. Além disso apresentamos a discretização dos operadores em diferenças finitas, que é feita a partir do conhecimento dos vizinhos dos quadrantes da malha e de técnicas de interpolação. A ordem do método é verificada a partir de testes com a equação do calor, tanto para malhas uniformes quanto para malhas com níveis de refinamento diferenciados e concluímos, assim, que o método desenvolvido e apresentado é satisfatório. / In this work we developed an algorithm to generate meshes quadtree in order to use them to simulate uid ow, which often makes it necessary to use ne meshes. The central idea of the generation of quadtree meshes is based on the quaternary structure of the tree, where each node has four children, and thus a tree structure is associated with a mesh that can be evenly or locally re ned. To avoid problems of discretization, a quadtree mesh must satisfy a criterion called the balancing and this is addressed in detail in the development of this work. We also highlight another important point in the implementation of quadtree meshes, which is the search for neighboring nodes. Additionally, we present the nite di erences discretization of operators, which uses the knowledge of the mesh quadrant neighboors and interpolation techniques. The order of the method is checked by tests with the heat equation for both uniform meshes and for meshes with di erent levels of re nement and we conclude that method here presented is satisfactory.

O ensino de Física inicia ainda nas séries iniciais do Ensino Fundamental, como parte do conteúdo denominado Ciências. Desta introdução dos primeiros conceitos físicos depende grande parte do ensino de Física subseqüente. Porém, a maioria dos professores das séries iniciais do Ensino Fundamental não tem formação adequada para promover este primeiro contato de estudantes com a Física. Então, foi desenvolvido um programa de qualificação que visa dar instrumentos aos professores para que desempenhem, de uma maneira mais adequada, este princípio de educação em Física. O programa é estruturado em quatro módulos, que contemplam diversos instrumentos e estratégias pedagógicas. Cada módulo começa com aulas de laboratório, seguido de uma interação em sala de aula com textos especialmente produzidos para o projeto. Estes textos abordam história da Ciência, Física do cotidiano e discussão de conceitos físicos. Por fim, cada módulo utiliza recursos multimídia, que vêm sendo produzidos por vários autores para enriquecer o ensino de Física e que estão disponíveis na internet. A aplicação do programa se deu através de um curso de extensão da UFRGS ministrado para um grupo de doze professoras do Colégio São Bento, em Criciúma, SC, e de um minicurso ministrado no II Encontro Estadual de Ensino de Física no Instituto de Física da UFRGS. Os professores do Colégio São Bento aplicaram os conteúdos de Física aos alunos das séries iniciais do Ensino Fundamental através de oficinas intituladas “Física para Crianças” e fizeram adaptações, quando necessárias, para adequar os conteúdos e estratégias aos interesses e características dos estudantes. A avaliação dessa aplicação do projeto foi feita através de entrevistas com os professores e de testes respondidos pelos alunos. / The teaching of physics starts in the initial series of elementary school, as a part of science content. By the introduction of the first physics conceptions will depends a big part of the teaching of subsequent physics. But a lot of teachers of initial series of elementary school don’t have the appropriate knowledge to promote this first contact of the students with the physics. Then was developed a qualification program to focus on instruments to the teachers to perform more adequately this beginning of education in physics. The course is structured in four modules that including several instruments and pedagogic strategies. Each module starts with laboratories class followed by interaction in the class with texts specially produced for the project. These texts approach science history, quotidian physics and discussion of concepts. At the end each module uses multimedia resources which had been produced by various authors to improve the teaching of physics, which are available in the internet. The program occurred with a course of extension at UFRGS and was then ministered by a group of twelve teachers of São Bento School, in Criciúma, SC, and by a minicourse ministered at the II State Meeting of Teaching of Physics in the Physics Institute of UFRGS. The teachers of São Bento School applied the content of physics to the children by workshops entitles “Physics to Children” and made adaptation, when necessary, to adequate the content and strategies to the interests and characteristics of students. The assessment of project application was analyzed by interview with the teachers and by tests applied with students.