O problema biobjetivo da árvore geradora quadrática em adjacência de arestas

The Quadratic Minimum Spanning Tree Problem (QMST) is a version of the Minimum Spanning Tree Problem in which, besides the traditional linear costs, there is a quadratic structure of costs. This quadratic structure models interaction effects between pairs of edges. Linear and quadratic costs are added up to constitute the total cost of the spanning tree, which must be minimized. When these interactions are restricted to adjacent edges, the problem is named Adjacent Only Quadratic Minimum Spanning Tree (AQMST). AQMST and QMST are NP-hard problems that model several problems of transport and distribution networks design. In general, AQMST arises as a more suitable model for real problems. Although, in literature, linear and quadratic costs are added, in real applications, they may be conflicting. In this case, it may be interesting to consider these costs separately. In this sense, Multiobjective Optimization provides a more realistic model for QMST and AQMST. A review of the state-of-the-art, so far, was not able to find papers regarding these problems under a biobjective point of view. Thus, the objective of this Thesis is the development of exact and heuristic algorithms for the Biobjective Adjacent Only Quadratic Spanning Tree Problem (bi-AQST). In order to do so, as theoretical foundation, other NP-hard problems directly related to bi-AQST are discussed: the QMST and AQMST problems. Bracktracking and branch-and-bound exact algorithms are proposed to the target problem of this investigation. The heuristic algorithms developed are: Pareto Local Search, Tabu Search with ejection chain, Transgenetic Algorithm, NSGA-II and a hybridization of the two last-mentioned proposals called NSTA. The proposed algorithms are compared to each other through performance analysis regarding computational experiments with instances adapted from the QMST literature. With regard to exact algorithms, the analysis considers, in particular, the execution time. In case of the heuristic algorithms, besides execution time, the quality of the generated approximation sets is evaluated. Quality indicators are used to assess such information. Appropriate statistical tools are used to measure the performance of exact and heuristic algorithms. Considering the set of instances adopted as well as the criteria of execution time and quality of the generated approximation set, the experiments showed that the Tabu Search with ejection chain approach obtained the best results and the transgenetic algorithm ranked second. The PLS algorithm obtained good quality solutions, but at a very high computational time compared to the other (meta)heuristics, getting the third place. NSTA and NSGA-II algorithms got the last positions

JCML - Java Card Modeling Language: Definição e Implementação

Formal methods should be used to specify and verify on-card software in Java Card applications. Furthermore, Java Card programming style requires runtime verification of all input conditions for all on-card methods, where the main goal is to preserve the data in the card. Design by contract, and in particular, the JML language, are an option for this kind of development and verification, as runtime verification is part of the Design by contract method implemented by JML. However, JML and its currently available tools for runtime verification were not designed with Java Card limitations in mind and are not Java Card compliant. In this thesis, we analyze how much of this situation is really intrinsic of Java Card limitations and how much is just a matter of a complete re-design of JML and its tools. We propose the requirements for a new language which is Java Card compliant and indicate the lines on which a compiler for this language should be built. JCML strips from JML non-Java Card aspects such as concurrency and unsupported types. This would not be enough, however, without a great effort in optimization of the verification code generated by its compiler, as this verification code must run on the card. The JCML compiler, although being much more restricted than the one for JML, is able to generate Java Card compliant verification code for some lightweight specifications. As conclusion, we present a Java Card compliant variant of JML, JCML (Java Card Modeling Language), with a preliminary version of its compiler

Computabilidade no espaço dos intervalos reais: um modelo BSS intervalar

A matemática intervalar é uma teoria matemática originada na década de 60 com o objetivo de responder questões de exatidão e eficiência que surgem na prática da computação científica e na resolução de problemas numéricos. As abordagens clássicas para teoria da computabilidade tratam com problemas discretos (por exemplo, sobre os números naturais, números inteiros, strings sobre um alfabeto finito, grafos, etc.). No entanto, campos da matemática pura e aplicada tratam com problemas envolvendo números reais e números complexos. Isto acontece, por exemplo, em análise numérica, sistemas dinâmicos, geometria computacional e teoria da otimização. Assim, uma abordagem computacional para problemas contínuos é desejável, ou ainda necessária, para tratar formalmente com computações analógicas e computações científicas em geral. Na literatura existem diferentes abordagens para a computabilidade nos números reais, mas, uma importante diferença entre estas abordagens está na maneira como é representado o número real. Existem basicamente duas linhas de estudo da computabilidade no contínuo. Na primeira delas uma aproximação da saída com precisão arbitrária é computada a partir de uma aproximação razoável da entrada [Bra95]. A outra linha de pesquisa para computabilidade real foi desenvolvida por Blum, Shub e Smale [BSS89]. Nesta aproximação, as chamadas máquinas BSS, um número real é visto como uma entidade acabada e as funções computáveis são geradas a partir de uma classe de funções básicas (numa maneira similar às funções parciais recursivas). Nesta dissertação estudaremos o modelo BSS, usado para se caracterizar uma teoria da computabilidade sobre os números reais e estenderemos este para se modelar a computabilidade no espaço dos intervalos reais. Assim, aqui veremos uma aproximação para computabilidade intervalar epistemologicamente diferente da estudada por Bedregal e Acióly [Bed96, BA97a, BA97b], na qual um intervalo real é visto como o limite de intervalos racionais, e a computabilidade de uma função intervalar real depende da computabilidade de uma função sobre os intervalos racionais

Proposta e implementação de uma arquitetura reconfigurável híbrida para aplicações baseadas em fluxo de dados

The increase of applications complexity has demanded hardware even more flexible and able to achieve higher performance. Traditional hardware solutions have not been successful in providing these applications constraints. General purpose processors have inherent flexibility, since they perform several tasks, however, they can not reach high performance when compared to application-specific devices. Moreover, since application-specific devices perform only few tasks, they achieve high performance, although they have less flexibility. Reconfigurable architectures emerged as an alternative to traditional approaches and have become an area of rising interest over the last decades. The purpose of this new paradigm is to modify the device s behavior according to the application. Thus, it is possible to balance flexibility and performance and also to attend the applications constraints. This work presents the design and implementation of a coarse grained hybrid reconfigurable architecture to stream-based applications. The architecture, named RoSA, consists of a reconfigurable logic attached to a processor. Its goal is to exploit the instruction level parallelism from intensive data-flow applications to accelerate the application s execution on the reconfigurable logic. The instruction level parallelism extraction is done at compile time, thus, this work also presents an optimization phase to the RoSA architecture to be included in the GCC compiler. To design the architecture, this work also presents a methodology based on hardware reuse of datapaths, named RoSE. RoSE aims to visualize the reconfigurable units through reusability levels, which provides area saving and datapath simplification. The architecture presented was implemented in hardware description language (VHDL). It was validated through simulations and prototyping. To characterize performance analysis some benchmarks were used and they demonstrated a speedup of 11x on the execution of some applications

Otimização em braquiterapia de alta taxa de dose com algoritmo transgenético

Este trabalho aborda o problema de otimização em braquiterapia de alta taxa de dose no tratamento de pacientes com câncer, com vistas à definição do conjunto de tempos de parada. A técnica de solução adotada foi a Transgenética Computacional apoiada pelo método L-BFGS. O algoritmo desenvolvido foi empregado para gerar soluções não denominadas cujas distribuições de dose fossem capazes de eiminar o câncer e ao mesmo tempo preservar as regiões normais

Uma abordagem através de algoritmos transgenéticos para o problema da configuração do traçado de uma rede de distribuição de gás natural

Este trabalho apresenta um algoritmo transgenético híbrido para a solução de um Problema de Configuração de uma Rede de Distribuição de Gás Natural. O problema da configuração dessas redes requer a definição de um traçado por onde os dutos devem ser colocados para atender aos clientes. É estudada neste trabalho uma maneira de conectar os clientes em uma rede com arquitetura em forma de árvore. O objetivo é minimizar o custo de construção da rede, mesmo que para isso alguns clientes que não proporcionam lucros deixem de ser atendidos. Esse problema pode ser formulado computacionalmente através do Problema de Steiner com Prêmios. Este é um problema de otimização combinatória da classe dos NPÁrduos. Este trabalho apresenta um algoritmo heurístico para a solução do problema. A abordagem utilizada é chamada de Algoritmos Transgenéticos, que se enquadram na categoria dos algoritmos evolucionários. Para a geração de soluções inicias é utilizado um algoritmo primaldual, e pathrelinking é usado como intensificador

Turismo e meio ambiente: uma análise do ecoturismo e sua contribuição sócio-ambiental no distrito matutuine: caso da reserva especial de Maputo Moçambique

Mozambique holds a potential for tourism development, especially for nature tourism, due to the existence of conservation areas around the country. The Maputo Special Reserve (MES) is considered as one of the most important conservation area and has benefited from investment in order to incruse the development of tourism in the region. Currently the number of visitors to MES has grown substantially with the intention to develop recreational activities related to ecotourism. Now the challenge lies in the way of optimizing opportunities for tourism development in order to achieve economic benefitis reduction the lead to poverty, without degrading the environment. Ecotourism face the demands and environmental discussions has been assumed as an alternative to the tourist market focused on protected areas, as it is believed that this segment is able to reconcile tourism development and simultaneously improve the conservation of the natural environment and still ensure the recovery of local communities and promoting their welfare. This study aims to analyze, from the perception of the local community, social and environmental contribution of ecotourism in Maputo Special Reserve, Mozambique. The research sought to investigate the relationship between ecotourism development in the region and generate benefits for the socio-environmental communities for residents. To achieve the objective, was chosen a critical analysis about the generation of socio-environmental benefits versus ecotourism in which we opted for a qualitative and quantitative approach seeking to establish the degree of agreement and disagreement about the benefits generated by ecotourism through interviews with community members

Recuperação de sinais esparsos. Investigação numérica sobre a quantidade de medidas necessárias para recuperar um sinal esparso

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior

Uma ferramenta didática para ajudar na fixação dos conceitos introdutórios de análise combinatória

Humans, as well as some animals are born gifted with the ability to perceive quantities. The needs that came from the evolution of societies and technological resources make the the optimization of such counting methods necessary. Although necessary and useful, there are a lot of diculties in the teaching of such methods.In order to broaden the range of available tools to teach Combinatorial Analysis, a owchart is presented in this work with the goal of helping the students to x the initial concepts of such subject via pratical exercises

Análise multitemporal dos elementos geoambientais da região da Ponta do Tubarão, área de influência dos campos petrolíferos de Macau e Serra, município de Macau/RN

The study area is inserted in Ponta do Tubarão region, Macau City, setentrional littoral of Rio Grande do Norte State, composed of Tertiary and Quatemary sedimentary rocks and sediments. This region is characterized for the intense action of the coastal processes, causing the morphologic instability in part of the area, beyond the interference of human activities, as the Petroliferous Industrial Polo, salt companies and shrimp farms. This justifies the integration of multidisciplinary and multitemporal detailed scientific studies dealing with the evaluation of the changing behavior of this coastal environment by geoenvironments elements characterization, identifying protected and recuperation areas, mainly those under socioeconomic intervention. The main objective was the coastal monitoring using geoprocessing techniques to prepare thematic maps useful for oil spilling environment risk areas survey. The methodology was based on multitemporal interpretation of remote sensing images and field checking, integrated in a Geographical Information System (GIS). The Geologic, Geomorphologic, Vegetation, Soil and Land Use maps were prepared, and later on they allowed the generation of the Natural Vulnerability and Environmental Vulnerability maps. These maps had been classified in accordance with vulnerability degrees: very low, low, medi um, high and very high. Beyond these maps the GIS allowed the analysis of the shoreline evolution for 10 distinct dates, using Landsat 5 TM and 7 ETM+ and SPOT-HRVIR images. This analysis made possible the attendance of the coastal morphodynamic evolution, where the results had been represented by areasof erosion and accretion (or deposition) of sediments, pointing critical areas under erosive process to the petroliferous industry (Macau and Serra fields). The GIS also provided to prepare the Environmental Sensitivity Maps of Oil Spill (SAO Maps) in operational scale (1: 10.000), according to the norms ofthe Ministério do Meio Ambiente (MMA 2002). The SAO Map in operational scale was based on IKONOS images mosaic where the ESI (Environmental Sensitivity Index) was represented according with two tides phases of theregion. Therewere recognizedfiveESI (3, 4,7,9, 1O) for the low tide; to the high tide the ESI number increased to seven (3, 4, 5, 7, 8, 9, 10). All these information are necessary to the decisions making about oi! spill and its derivatives containment. These techniques application makes possible the optimization and implantation ofnew socioeconomics activities of low environmental impact, indicates areas for better productivity and security exploration, and benefits local communities with fauna and flora preservation. The development of these activities is inserted in the scope of Monitoramento Ambiental de Áreas de Risco a Derrames de Petróleo e Seus Derivados Cooperation Project (Rede 05/01 - PETRORISCO, FINEP/CTPETRO/PETROBRAS) of multidisciplinary and interinstitucional characteristics dealing with subjects involving the environmental monitoring and the petroliferous activity