Orientador: Cid Carvalho de Souza / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-15T11:41:44Z (GMT). No. of bitstreams: 1 Hoshino_EdnaAyako_D.pdf: 1434503 bytes, checksum: c1b32d8a6dc810d6d7ff6100d1a77c79 (MD5) Previous issue date: 2009 / Resumo: Nesta tese,dois problemas de otimização combinatória em grafos são modelados por programação linear inteira e resolvidos através de técnicas de geração de colunas. Os dois casos correspondem a generalizações de problemas clássicos em grafos e que ocorrem em muitas situações práticas. O primeiro, chamado problema dos anéis-estrelas capacitados, é uma generalização do problema de roteamento de veículos e modela situações reais encontradas nas áreas de logística de distribuição e de transporte. O segundo, conhecido por problema da coloração particionada, generaliza o problema da coloração de vértices em grafos e ocorre em aplicações no projeto de redes ópticas. As formulações de programação linear inteira desenvolvidas neste trabalho para modelar ambos os problemas estão relacionadas 'a técnica da decomposição de Dantzig-Wolfe e usam uma quantidade exponencialmente grande de variáveis de decisão . Nestas formulações, cada uma das variáveis representa uma estrutura específica do problema sendo estudado. No problema dos anéis-estrelas capacitados, cada variável está associada a um anel-estrela e, no problema da coloração particionada, a um conjunto independente. As relaxações lineares destes tipos de modelos, em geral, apresentam limitantes duais mais apertados que outros modelos compactos, isto é, definidos para um número polinomial de variáveis. Nesta tese, nós avaliamos estas novas formulações, comparando-as com outros modelos conhecidos para os problemas estudados. Além disso, nos dois casos, projetamos e implementamos algoritmos exatos do tipo branch-and-price e/ou branch-and-cut-and-price capazes de computar os modelos propostos. Experimentos computacionais foram realizados com estes algoritmos que confirmaram a adequação das técnicas aqui empregadas. Tanto para o problema dos anéis-estrelas capacitados quanto para o problema da coloração particionada, os resultados alcançados por nós foram comparados com aqueles reportados na literatura e mostraram que os algoritmos baseados em geração de colunas tiveram desempenho melhor que os algoritmos propostos anteriormente / Abstract: In this thesis, two combinatorial optimization problems are modeled by integer linear programming and solved using the column generation technique. Both cases correspond to generalizations of classical problems in graphs that occur in many practical situations. The first, called capacitated ring-star problem is a generalization of the vehicle routing problem and models real situations found in logistics and transportation. The second, known as the partition coloring problem, generalizes the vertex coloring problem in graphs and arises in design of fiber optics networks. The integer linear programming formulations developed in this work to model both problems are related to the Dantzing-Wolfe decomposition and use exponential number of decision variables. In these formulations, each decision variable represents a specific structure of the problem under study. For the capacitated ring-star problem, each variable is assigned to a ring-star and, for the partition coloring problem, to an independent set. The linear relaxation of this kind of model in general leads to tighter dual bounds than the ones obtained from compact models, i.e., defined over a polynomial number of variables. In this thesis, we evaluated both new formulations, comparing them to other known models for the respective problems. Moreover, in both cases, we designed and implemented exact branch-and-price and/or branch-and-cut-and-price algorithms that are able to solve the proposed models. Computational experiments were performed with these algorithms and showed that the used techniques were adequate. Both for the capacitated ring-star problem and for the partition coloring problem, we compared our results with those reported in the literature and showed that the algorithms based on column generation outperformed the previous ones / Doutorado / Otimização Combinatoria / Doutor em Ciência da Computação

Submitted by Cássia Santos (cassia.bcufg@gmail.com) on 2015-10-27T14:37:06Z No. of bitstreams: 2 Tese - Marcio Antonio Duarte - 2015.pdf: 457015 bytes, checksum: 1f57686628e44a0cebc1fee7aaf0bcfc (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2015-10-29T10:04:41Z (GMT) No. of bitstreams: 2 Tese - Marcio Antonio Duarte - 2015.pdf: 457015 bytes, checksum: 1f57686628e44a0cebc1fee7aaf0bcfc (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2015-10-29T10:04:41Z (GMT). No. of bitstreams: 2 Tese - Marcio Antonio Duarte - 2015.pdf: 457015 bytes, checksum: 1f57686628e44a0cebc1fee7aaf0bcfc (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2015-04-10 / Conselho Nacional de Pesquisa e Desenvolvimento Científico e Tecnológico - CNPq / In this work, we present some related results, especially the properties algoritimics and of complexity of a product of graphs called complementary prism. Answering some questions left open by Haynes, Slater and van der Merwe, we show that the problem of click, independent set and k-dominant set is NP-Complete for complementary prisms in general. Furthermore, we show NP-completeness results regarding the calculation of some parameters of the P3-convexity for the complementary prism graphs in general, as the P3-geodetic number, P3-hull number and P3-Carathéodory number. We show that the calculation of P3-geodetic number is NP-complete for complementary prism graphs in general. As for the P3-hull number, we can show that the same can be efficiently computed in polynomial time. For the P3-Carathéodory number, we show that it is NPcomplete complementary to prisms bipartite graphs, but for trees, this may be calculated in polynomial time and, for class of cografos, calculating the P3-Carathéodory number of complementary prism of these is 3. We also found a relationship between the cardinality Carathéodory set of a graph and a any Carathéodory set of complementary prism. Finally, we established an upper limit calculation the parameters: geodetic number, hull number and Carathéodory number to operations complementary prism of path, cycles and complete graphs considering the convexities P3 and geodesic. / Neste trabalho, apresentamos alguns resultados relacionados, principalmente às propriedades algorítmicas e de complexidade de um produto de grafos chamado prisma complementar. Respondendo algumas questões deixadas em aberto por Haynes, Slater e van der Merwe, mostramos o problema de clique, conjunto independente e conjunto com kdominantes é NP-Completo para prismas complementares em geral. Além disso, mostramos resultados de NP-completude em relação ao cálculo de alguns parâmetros da convexidade P3 para o prisma complementar de grafos em geral, como o número P3, número envoltório P3 e número de Carathéodory. Mostramos que o cálculo do número P3 é NPcompleto para o prisma complementar de grafos em geral. Já para o número envoltório P3, mostramos que o mesmo pode ser calculado de forma eficiente em tempo polinomial. Para o número de Carathéodory, mostramos que é NP-completo para os prismas complementares de grafos bipartidos, mas que para árvores, este pode ser calculado em tempo polinomial e ainda, para classe dos cografos, o cálculo do número de Carathéodory do prisma complementar desses é 3. Encontramos também, uma relação entre a cardinalidade de um conjunto de Carathéodory de um grafo qualquer e um conjunto de Carathéodory do seu prisma complementar. Por fim, estabelecemos um limite superior do cálculo dos parâmetros: número geodésico, número envoltório e número de Carathéodory para operações prisma complementar de grafos caminho, ciclos e completos considerando as convexidades P3 e geodésica.

A crescente demanda por produtos de melhor qualidade, diferenciados e com custos competitivos tem forçado as manufaturas a se tornarem flexíveis, capacitando-as a responder às mudanças impostas pelo mercado. A flexibilidade permite que as empresas alcancem a customização desejada através da capacitação do sistema de responder e atuar em tempo real, mesmo em um ambiente de incertezas. Para atuar em tempo real, os sistemas de manufatura precisam de representações eficientes dos planos de produção. Muitas vezes, a atuação em tempo real torna-se inviável devido ao crescimento exponencial no número de planos de produção para cada máquina ou operação adicionada ao sistema. Uma possível solução para este problema é uso de representações adequadas para o espaço de estados. A escolha de uma representação adequada para o espaço de estados influencia na capacidade de reposta em tempo real, pois determina o desempenho computacional do sistema através da utilidade e eficiência dos algoritmos desenvolvidos, tornando possível explorar problemas clássicos de flexibilidade, tais como, seqüenciamento, otimização, etc. Entretanto, a geração de uma representação que trabalhe com o espaço de estados completo de uma manufatura é considerada um problema não polinomial (NP). Esta particularidade dificulta o desenvolvimento de algoritmos que trabalhem com uma manufatura flexível. Assim, a geração de uma representação, que trabalhe com pouca memória computacional e permita o desenvolvimento de heurísticas eficientes, é um importante desafio para uma avaliação efetiva da flexibilidade. Este trabalho objetiva o desenvolvimento de uma representação para o espaço de estados de uma manufatura com flexibilidade de seqüência. Na construção desta representação são aplicadas técnicas de modelagem baseadas na teoria dos grafos e nos princípios de álgebra booleana. Inicialmente, os grafos são utilizados para representar todas as seqüências de operações de uma manufatura, posteriormente estas seqüências são convertidas em formas normais disjuntivas (FND). Por fim, é apresentada uma possível aplicação da representação na FND em modelos de programação linear.

Neste trabalho estudamos um pouco de Teoria dos Grafos, abordando diversas definições e teoremas interessantes. Apresentamos o Teorema das Quatro Cores, desde o surgimento do problema com Francis Guthrie. Analisamos a demonstração do teorema realizada por Alfred Bray Kempe e sua refutação através do contraexemplo de Percy John Heawood. Analisamos também a demonstração do Teorema das Cinco Cores de Percy John Heawood. Porém, apresentamos a primeira demonstração válida do Teorema das Quatro Cores, como sua particularidade de ter sido feita com o auxílio de um computador. O trabalho é concluído com uma análise sobre os benefícios que o conhecimento de Teoria dos Grafos pode render aos alunos do Ensino Básico, e como professor o pode trabalhar este assunto em sala de aula, inclusive abordando o problema de coloração de mapas. / In this paper we study Graph Theory, addressing various definitions and interesting theorems. We present the Four Color Theorem, since the origin of the problem with Francis Guthrie. We analyze the proof of the theorem presented by Alfred Bray Kempe, and its refutation by Percy John Heawood counter-example. We also analyze the Percy John Heawood demonstration of the Five Color Theorem. Finally, we present the first valid proof of the Four Colors Theorem, with its peculiarity of having been done with the aid of a computer. We conclude with an analysis of the beneficial that the knowledge of Graph Theory can render students of Basic Education, and how a teacher can work this topic in the classroom, including addressing the problem of map coloring.

Orientadores: Akebo Yamakami, Ricardo Coelho Silva / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-25T08:18:04Z (GMT). No. of bitstreams: 1 Verga_Juliana_D.pdf: 1085866 bytes, checksum: 6325aac2b413dfa3fc773ecc3791388c (MD5) Previous issue date: 2014 / Resumo: A teoria de grafos é comumente utilizada na área da engenharia para resolver problemas que podem ser representados na forma de redes. Dentre diversos problemas abordados, o problema de transporte multimodal é um dos que podem ser modelados por grafos. Este trabalho apresenta três algoritmos para redes de transporte multimodal aplicados ao tráfego urbano. O primeiro algoritmo é de carregamento incremental de fluxo e aborda incertezas nos custos e nas capacidades dos arcos utilizando a teoria dos conjuntos fuzzy. Neste caso, o problema foi modelado através de subgrafos, onde cada modo de transporte considerado é representado por um subgrafo e o grafo total é a união de todos os subgrafos. O segundo é um algoritmo de caminho mínimo para grafos coloridos com custos crisp e é baseado no algoritmo clássico de caminho mínimo de Ford-Moore-Bellman. O terceiro algoritmo é de carregamento incremental de fluxo e utiliza o segundo algoritmo para encontrar os caminhos mínimos multimodais. Neste caso os custos e capacidades são crisp e assim como no primeiro algoritmo, os custos dependem do fluxo. A modelagem com relação ao segundo e ao terceiro algoritmo, foi feita utilizando grafos coloridos, onde cada modo de transporte é representado por uma cor / Abstract: The graph theory is commonly used in the area of engineering to solve problems that can be represented in the form of networks. Among several problems, the multimodal transport problem is one that can be modeled by graphs. This work presents three algorithms for multimodal transport networks applied to urban traffic. The first algorithm is of incremental loading flow and deals uncertainties in costs and in capacities of arcs using the fuzzy sets theory. In this case the problem was modeled by subgraphs, where each mode of transport considered is represented by a subgraph and the total graph is the union of all subgraphs. The second, is an algorithm of shortest path for colored graphs with crisp costs and is based in the classical shortest path algorithm of Ford-Moore-Bellman. The third algorithm is of incremental loading flow and uses the second algorithm to find the multimodal shortest paths. In this case the costs and the capacities are crisp and thus in the first algorithm, the costs depend on the flow. The modeling with respect to the second and third algorithm was done using colored graphs, where each transport mode is represented by a color / Doutorado / Automação / Doutora em Engenharia Elétrica

O Problema do Multicorte Dirigido Mínimo é um problema clássico em otimização combinatória. Ele é NP-difícil mesmo para instâncias muito simples. Este trabalho faz uma análise dos algoritmos exatos e de aproximação para resolver o problema. Também implementa alguns desses algoritmos e compara seus desempenhos. / The directed multicut problem is a classical problem in combinatorial optimization. It is NP-hard even for very simple families of instances. This work makes an analysis of the exact and approximation algorithms for the problem. It also implements some of these algorithms and compares their performances.

A capacidade das células para responder corretamente a sinais externos e perceber mudanças no seu microambiente é a base do desenvolvimento, reparação de tecidos e de imunidade, bem como a homeostase do tecido normal. Transdução de sinal é o principal meio pelo qual as células respondem a sinais externos de seu ambiente e coordenam alterações celulares complexas. O estudo das vias de sinalização molecular permite-nos tentar compreender o funcionamento dessas transduções de sinais e, consequentemente, as respostas celulares a estímulos externos. Uma abordagem adequada para tais estudos é o uso de modelos matemáticos para simular a cinética das reações químicas que descrevem uma dada via de sinalização, o que nos permite gerar predições testáveis de processos celulares. Construir modelos cinéticos preditivos de vias de sinalização molecular através de dados de alto rendimento produzidos utilizando técnicas ômicas (i.e., genômica, transcriptômica, (fosfo-)proteômica) constitui um dos atuais desafios enfrentados pelos pesquisadores na área de Biologia Molecular. Recentemente, para lidar com este desafio, o arcabouço de e-Science SigNetSim foi introduzido pelo Grupo de Biologia Computacional e de Bioinformática do Instituto Butantan. Esse arcabouço permite fazer a descrição de vias de sinalização molecular através da descrição da estrutura de um modelo através de um conjunto de reações químicas, que por sua vez é mapeado para um sistema de Equações Diferencias Ordinárias (EDOs), numericamente simuladas e avaliadas. Todavia, modificações na estrutura das vias precisam ser feitas manualmente, o qual restringe severamente o número de estruturas da via que precisam ser testadas, especialmente no caso de modelos grandes. Portanto, diante desse panorama, este trabalho propõe o desenvolvimento de um método para modificar vias de sinalização molecular. Esse método se baseia no uso de bancos de dados de interatomas para fornecer um conjunto de espécies químicas candidatas para serem incluídas na via de sinalização. Um componente integrado ao arcabouço SigNetSim capaz de testar diferentes hipóteses de modificação de vias foi desenvolvido neste projeto utilizando a metodologia de heurística incremental. Para avaliar a eficiência do componente implementado, utilizamos como estudo de caso um modelo de vias sinalização de MAPKs e PI3K/Akt para realizar testes experimentais e analisar os resultados obtidos. / The ability of cells to respond correctly external signals and to perceive changes in their microenvironment is the basis for development, tissue repair and immunity as well as normal tissue homeostasis. Signal transduction is the primary means by which cells respond to external signals from their environment and coordinate complex cellular changes. The study of molecular signaling pathways allows us to understand the operation of each process of cellular signal transduction. The use of mathematical models to simulate the kinetics of chemical reactions that describe a given signaling pathway, allow us to generate testable predictions of the cell processos. To Build Kinetic predictive models to molecular signaling pathways through massive data omics produced using modern techniques, Genomics, transcriptomics, (Phospho) proteomics, is one of the current challenges faced by researchers in the field of molecular biology. Recently, the \\textit SigNetSim e-Science was introduced by the Biological Computacional and Bioinformatical Group from the Butantan Institute to face this challenge. This \\textit makes the description of molecular signaling pathways through a set of chemical reactions, which are mapped into a system of ordinary differential equations, this system will be numerically simulated and evaluated . However, changes in the structure of the pathways need to be updated manually presented in this work, which severely restricts the number of track structures that need to be tested, especially for the large models. Therefore, given this background, we present the method to modify the molecular signaling pathways. This method relies on the use of interactome database to provide a set of chemical species candidates to be included in the signaling pathway. An component integrated to SigNetSim framework able to test different hypotheses of pathways modification was developed in this project using the incremental heuristic methodology. To evaluate the implemented component, we used the MAPKs and PI3K/Akt pathways model as case study, in order to perform experimental tests and to analyze the obtained results.

Os objetivos deste trabalho de mestrado consistem em determinar: (i) como modificar a arquitetura de referência de Internet das Coisas para identificar e priorizar as necessidades dos usuários em um determinado contexto; (ii) como transformar dados sociais subjetivos em uma medida objetiva de impacto social; (iii) como correlacionar informações sociais e dados digitais de forma a medir a satisfação dos usuários com os serviços de Internet das Coisas desenvolvidos; (iv) como validar o sistema total; e (v) se a arquitetura é reconfigurável e pode ser adotada e validada em diferentes casos de uso. O método de desenvolvimento começa de uma extensa investigação bibliográfica sobre projetos, arquiteturas e plataformas de Internet das Coisas desenvolvidas e em desenvolvimento, tecnologia social e teoria de grafos. É proposto um mapa conceitual que serve de base a todo o trabalho. A teoria de grafos fornece um conjunto de métricas que permite identificar as reais necessidades de usuários e comunidades e, então, especificar as aplicações e serviços de Internet das Coisas a serem desenvolvidos. ´E proposta uma função de fitness para avaliar a satisfação de requisitos de uma especificação. A validação do método é feita por meio de um estudo de caso. Para uma cidade hipotética são descritos os serviços educacionais, de saúde e de transporte disponíveis. É identificado o problema de oferecimento de serviços educacionais a comunidades distantes e a necessidade desses serviços se integrarem com as entidades culturais e de saúde. Com isso, ´e especificada a aplicação Aula Móvil. Essa aplicação é completamente descrita por meio dos modelos de domínio, de informação, funcional e de comunicação da arquitetura de referência IoT-A. Para o desenvolvimento do software, é feita uma descrição completa em UML: diagrama de classes e diagramas de sequência. Apesar de se ter adotado um estudo de caso simples, fica demonstrada a viabilidade de se integrar a avaliação de dados estatísticos sociais no ciclo de projeto de aplicações de Internet das Coisas. ´E mostrado também que as aplicações de Internet das Coisas geram impacto social a curto, médio e longo prazos. O método e arquitetura propostos neste trabalho são suficientemente genéricos para serem utilizados em outras aplicações relacionadas a uma cidade e também em outros domínios como os de M2M e da iniciativa Industry 4.0. / The objectives of this master thesis consist in determining: (i) how modify an IoT reference architecture to identify and prioritize end user\'s needs in a given context; (ii) how transform subjective social data in a objective measure of social impact; (iii) how correlate social data and digital data to measure the end users\' satisfaction with the developed IoT services; (iv) how validate the total system; and (v) if the architecture is reconfigurable and can be adopted and validated in di?erent use cases. The development method started with and extensive bibliographic research about IoT projects, architectures and platforms, already developed and under development, social technology and graphs theory. A conceptual map is proposed and is used as a basis for the entire work. The graphs theory provides a set of metrics that allow the identification of end users\' and communities\' needs and, then, to specify the IoT applications and services to be developed. A fitness function is proposed to evaluate the fulfillment of requirements of a specification. The whole method validation is made by means of a case study. To do so, the available educational, health and transport services of a hypothetical city are described. The problem of o?ering educational services to distant communities and the need to integrate such services to the cultural and health entities are identified. As a result, a Mobile Class application is specified. This application is completely described by the domain, informational, functional and communicational models of the IoT-A reference architecture. For the software development, a complete UML description is made: class diagrams and sequence diagrams. In spite of having adopted a simple case study, the feasibility of integrating the social statistical data evaluation in the design cycle of IoT applications is demonstrated. It is also shown that IoT applications generate social impact in the short, medium and large terms. The method and architecture proposed in this work are generic enough to be used in other applications related to a city as is other domains as M2M and from the Industry 4.0 Initiative.

Os efeitos deletérios da perda e fragmentação de habitat são considerados a maior ameaça à manutenção da biodiversidade do planeta. Uma das maneiras de evitar a perda de espécies em paisagens fragmentadas é a restauração ecológica, que propicia tanto o aumento da quantidade quanto a melhoria da qualidade do habitat remanescente. Além de influenciar a persistência de espécies, as condições da paisagem são reconhecidas como importantes para o sucesso das ações de restauração. Entretanto, as diretrizes para incorporação das características da paisagem no planejamento da restauração são ainda ambíguas, não facilitando o processo de tomada de decisão. O presente trabalho teve como objetivo contribuir para o avanço do uso de análises espacialmente explícitas da estrutura da paisagem para o planejamento de ações de restauração. Para isso, foram elaboradas propostas metodológicas embasadas no atual conhecimento da ecologia de paisagens e foram realizadas simulações para comparar os potenciais benefícios para a biodiversidade resultantes de diferentes estratégias para seleção de áreas para restauração. A primeira proposta, apresentada no capítulo 2, utiliza análises de paisagens em múltiplas escalas, baseadas na teoria dos grafos, para estimar a resiliência das paisagens, entendida neste trabalho como a capacidade das paisagens de reverterem extinções locais por processos de migração. Em seguida, as paisagens com condições ideais para restauração são classificadas segundo sua importância como corredores biológicos e gargalos de conectividade. Essa proposta metodológica é aplicada no caso da Mata Atlântica (capítulo 3), a fim de estabelecer diferentes níveis de prioridade para restauração no conjunto deste bioma. No quarto capítulo, é apresentada uma segunda proposta metodológica, também baseada em análises de conectividade com o uso da teoria dos grafos, mas desta vez voltada para a identificação de áreas prioritárias para restauração em escala local. Essa proposta permite ainda a comparação de prioridades entre áreas situadas em paisagens com diferentes condições de cobertura e conectividade de habitat. Por fim, no quinto capítulo, foi realizado um conjunto de simulações de restauração para comparar os efeitos das características da paisagem (e.g. a cobertura e configuração florestal), das espécies (e.g. a capacidade de dispersão) e da estratégia de restauração (e.g. o tamanho das áreas restauradas e a ordem temporal da restauração) no aumento da disponibilidade de habitat em três paisagens reais da Mata Atlântica. Os resultados desta tese permitiram estabelecer prioridades de restauração tanto em escala regional quanto em escala local, reduzindo as áreas a serem visitadas em campo e possibilitando a otimização dos esforços de restauração. Também foi possível concluir que a adoção de estratégias espaciais para a seleção de áreas para restauração deve ser feita considerando tanto as características das espécies quanto as características das paisagens e a forma de implementação da restauração. Na ausência de informações detalhadas sobre a capacidade de dispersão das espécies, abordagens baseadas em múltiplas capacidades de dispersão são recomendadas. O embasamento teórico da ecologia de paisagens e as ferramentas atuais de tratamento e integração de dados espacializados permitem a definição das melhores estratégias de restauração a partir de simulações em computador, reduzindo substancialmente os custos da restauração e aumentando a sua eficácia para a conservação das espécies em paisagens fragmentadas / The deleterious effects of habitat loss and fragmentation are considered the main threats to biodiversity. To avoid species loss due to these deleterious effects, there is an urgent need to conduct restoration actions to increase the quantity and quality of the remaining habitat. Besides influencing species persistence, the landscape structure also influences the results of restoration actions. However, guidelines to adopt a landscape approach during restoration planning are not always consistent, nor easy to apply. The objective of this study was to contribute to advances in the use of spatially explicit landscape analysis during restoration planning. To achieve this goal we developed methodological frameworks based on landscape ecology theory to set priority areas for restoration. We also adopted a simulation approach to analyze the potential benefits of different restoration strategies for biodiversity conservation. The methodological proposal presented in chapter 2 consists in multi-scale landscape analyses, based on graph theory, to estimate landscape resilience. We considered landscape resilience as the capacity to revert local species extinctions through recolonization processes. Then, those landscapes considered ideal targets to restoration actions were classified according to their importance as corridors or bottlenecks for biological flow. In chapter 3, the methodological proposal presented in chapter 2 was applied to the Atlantic Forest Biome to set restoration priorities. Chapter 4 consists in a methodological proposal, also based on graph theory, to set restoration priorities in local scale. This methodological proposal also allows the comparison of local restoration priority between landscapes with different amount and configuration of habitat cover. Finally, in the fith chapter we adopted a simulation approach to analyze the improvement of habitat availability, in three Atlantic Forest landscapes, due to different restoration strategies considering: (i) different species dispersal capabilities, (ii) initial habitat amount in the landscape, (iii) the dynamics of landscapes during restoration implementation, i.e., the changes in habitat availability as new areas were restored, and (iv) size of restored areas. The results of this study allowed us to establish local and regional restoration priorities, thus reducing field visits and optimizing restoration efforts. It was also possible to conclude that spatial strategies to set restoration priorities should be conceived based on species dispersal capacities, landscape structure and also considering the strategies to implement restoration actions. If data on species dispersal characteristics is not available, a multi species approach to set restoration priorities is also recommended. The theoretical background of landscape ecology and the available tools to manage spatial data allow identifying the best restoration strategies, reducing the costs and optimizing the benefits to conserve biodiversity in fragmented landscapes

Made available in DSpace on 2015-03-04T18:57:40Z (GMT). No. of bitstreams: 1 Dissertacao_Klaus.pdf: 1117417 bytes, checksum: fa3282de1497f164dc8fc979216ed0e1 (MD5) Previous issue date: 2012-03-05 / Coordenacao de Aperfeicoamento de Pessoal de Nivel Superior / The last decade or so has witnessed an ever-increasing growth in the study of very large complex networks related to different areas, such as biology, sociology, and the Internet. In this broad context, the concept of centrality offers a measure of the relative importance of nodes within a given complex network and is thus crucially important to network analysis. There are many different definitions of network centrality, which rank the relative importance of nodes using different criteria, depending on the targeted analysis. Among these, the traditional closeness centrality ranks the nodes by how close each node is to all other nodes in the network. In other words, the most central nodes according to a ranking based on closeness centrality are those best positioned for efficient diffusion processes, such as information or goods distribution as well as disease or rumor spreading, and so on. Nevertheless, computing closeness centrality in large complex networks is costly because it is necessary to determine the distance between all pairs of nodes in the network, thus requiring full knowledge of the network's topology. In centrality-based network analysis, the position of each node in the centrality ranking is typically more important than the particular centrality value associated to each node. Here, we present a fully distributed method capable of yielding different kinds of centrality, among them one which node ranking correlates strongly with the closeness centrality ranking, but being much cheaper than the traditional algorithm and not requiring full knowledge of the network's topology. Overall, our method is a simple yet efficient alternative for distributively determining the closeness centrality ranking, enabling a centrality-based analysis of large scale-free complex networks. / Os últimos anos tem mostrado um crescimento contínuo no estudo de redes complexas de grande porte relacionadas com diversas áreas de conhecimento, tais como Biologia, Sociologia, Economia, Internet, entre outras. Nesse contexto, o conceito de centralidade oferece uma medida da importância relativa dos nós que compõem uma rede complexa, sendo portanto de fundamental importância para a análise e estudo destas redes. Existem várias definições diferentes para centralidade em redes segundo a aplicação que pretendem, usando critérios distintos para ordenar a importância dos nós. Entre essas diferentes definições de centralidade, Closeness Centrality é uma das mais tradicionais e afere a importância de cada nó pela sua proximidade com todos os demais nós da rede. Dessa maneira, essa forma de centralidade avalia os nós melhor posicionados para realizar processos de difusão de forma eficiente na rede, sendo portanto de grande valia para análise de redes complexas com aplicações em diversas áreas. Entretanto, o cálculo deste tipo de centralidade apresenta um alto custo computacional, uma vez que é necessário que se calcule a distância entre todos os pares de nós da rede. Isso faz ainda que seja necessário conhecer completamente a topologia da rede para que seja possível calcular as distâncias entre os nós. Em virtude disso, o uso de Closeness Centrality se torna impraticável para redes de grande porte, comumente encontradas em diversas áreas do conhecimento. No entanto, em termos práticos, a ordem dos nós em função de sua centralidade é mais relevante do que os valores de centralidade em si. Assim, este trabalho apresenta um método distribuído que pode ser utilizado para calcular vários tipos de centralidades, entre elas uma cuja ordenação dos nós tem um alto grau de correlação com a ordenação obtida pelo uso de Closeness Centrality. O método proposto funciona de maneira totalmente distribuída, baseando-se em conhecimento local não necessitando do conhecimento completo da topologia da rede, e é computacionalmente menos custoso que o método tradicional. Estas características fazem com que o método proposto seja aplicável a redes complexas scale-free de grande porte, possibilitando uma aproximação eficiente da ordenação de Closeness Centrality a estas redes, como analisado nos resultados da dissertação.