Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Esta dissertação levanta uma análise comparativa dos processos políticos que antecederam a construção de duas pontes transnacionais nas Américas: a ponte sobre o Rio Tacutu, que liga as cidades de Lethem (Região 9, Guyana) e Bonfim (Roraima, Brasil); e a ponte sobre o Rio Hondo, que liga as cidades de Santa Elena (Corozal, Belize) e Subteniente López (Quintana Roo, México). Enquanto isso, o estudo inserese no corpo mais amplo de pesquisas que analisam o processo de integração das Américas através do uso de infraestrutura física. Além disso, a pesquisa aborda a maneira em que poderes emergentes usam infraestrutura para propósito de projeção de poder regional nos seus entornos geopolíticos, particularmente, em relação aos seus vizinhos contíguos menores. Esta análise realiza-se no contexto histórico do reconhecimento da necessidade de fomentar integração entre os países do sul global e de países de tradições coloniais diferentes; e mais ainda, visa alcançar essa meta com o uso da infraestrutura física. Metodologicamente, é um estudo interpretativo quantitativo das fontes bibliográficas e discursos executivos, utilizando o método comparativo para deduzir modos de interação entre dois poderes emergentes latinoamericanos e dois países relativamente pequenos e isolados do Caribe anglófono. Pode-se concluir que as duas pontes foram construídas e inauguradas dentro de projetos mais amplos para integração regional, promovidos pelo México e Brasil, para as regiões imediatas de influência geopolítica, facilitado por fortes vínculos bilaterais históricos no campo de segurança de território; e completado pela transição contemporânea dos países caribenhos na busca para novos parceiros internacionais, frente à perda de viabilidade de vínculos tradicionais. / This dissertation carries out a comparative analysis of the political processes leading up the construction of two transnational bridges in the Americas; these are the Takutu River Bridge linking Lethem, Region 9, Guyana and Bonfim, Roraima, Brazil; and the Hondo River Bridge linking Santa Elena, Cozoral, Belize and Subteniente López, Quintana Roo, Mexico. In so doing, the study is inserted in a wider body of researches that analyse the process of integration in the Americas through the use of physical infrastructure. The research further highlights how emerging powers use infrastructure as a means of regional power projection in their geopolitical spaces, particularly as it pertains to smaller contiguous neighbours. This analysis takes place in the historical context of countries of the global south and of different colonial traditions, recognising the need to foster integration, and achieve advancement in this regard through infrastructure. Methodologically, it is an interpretive qualitative study of bibliographical sources and executive speeches, using the comparative method to deduce modes of interaction between two emerging Latin American powers and two relatively small and isolated continental countries of the Anglophone Caribbean. It may be concluded that the two bridges were successfully constructed and inaugurated as part of wider projects for regional integration fostered by Mexico and Brazil for their regions of immediate geopolitical influence, and aided by historically strong bilateral relations in the area of territorial integrity and further, the contemporary transitioning in the search by Caribbean countries for new international partners as old linkages become less viable.

Os processos de negócio desempenham um papel muito importante na indústria, principalmente pela evolução das tecnologias da informação. As plataformas de computação em nuvem, por exemplo, com a alocação de recursos computacionais sob demanda, possibilitam a execução de processos altamente requisitados. Para tanto, é necessário definir o ambiente de execução dos processos de tal modo que os recursos sejam utilizados de forma ótima e seja garantida a correta funcionalidade do processo. Nesse contexto, diferentes métodos já foram propostos para modelar os processos de negócio e analisar suas propriedades quantitativas e qualitativas. Há, contudo, vários desafios que podem restringir a aplicação desses métodos, especialmente para processos com alta demanda (como os workflows de numerosas instâncias) e que dependem de recursos limitados. A análise de desempenho de workflows de numerosas instâncias via modelagem analítica é o objeto de estudo deste trabalho. Geralmente, para a realização desse tipo de análise usa-se modelos matemáticos baseados em técnicas Markovianas (sistemas estocásticos), que sofrem do problema da explosão do espaço de estados. Entretanto, a Teoria do Campo Médio indica que o comportamento de um sistema estocástico, sob certas condições, pode ser aproximado por o de um sistema determinístico, evitando a explosão do espaço de estados. Neste trabalho usamos tal estratégia e, com base na definição formal de aproximação determinística e suas condições de existência, elaboramos um método para representar os workflows, e seus recursos, como equações diferenciais ordinárias, que descrevem um sistema determinístico. Uma vez definida a aproximação determinística, realizamos a análise de desempenho no modelo determinístico, verificando que os resultados obtidos são uma boa aproximação para a solução estocástica. / Business processes play a very important role in the industry, especially by the evolution of information technologies. Cloud computing platforms, for example, with the allocation of on-demand computing resources enable the execution of highly requested processes. Therefore, it is necessary to define the execution environment of the processes in such a way that the resources are used optimally and the correct functionality of the process is guaranteed. In this context, different methods have already been proposed to model business processes and analyze their quantitative and qualitative properties. There are, however, a number of challenges that may restrict the application of these methods, especially for high-demanded processes (such as workflows of numerous instances) and that rely on resources that are limited. The analysis of the performance of workflows of numerous instances through analytical modeling is the object of study of this work. Generally, for the accomplishment of this type of analysis, mathematical models based on Markovian techniques (stochastic systems) are used, which suffer the problem of the state space explosion. However, the Mean Field Theory, indicates that the behavior of a stochastic system, under certain conditions, can be approximated by that of a deterministic system, avoiding the explosion of the state space. In this work we use such a strategy, based on the formal definition of deterministic approximation and its conditions of existence, we elaborate a method to represent the workflows, and their resources, as ordinary differential equations, which describe a deterministic system. Once the deterministic approximation has been defined, we perform the performance analysis in the deterministic model, verifying that the obtained results are a good approximation for the stochastic solution.

O foco central desta tese é o desenvolvimento de algoritmos para o problema de recoloração convexa de caminhos. Neste problema, é dado um caminho cujos vértices estão coloridos arbitrariamente, e o objetivo é recolorir o menor número possível de vértices de modo a obter uma coloração convexa. Dizemos que uma coloração de um grafo é convexa se, para cada cor, o subgrafo induzido pelos vértices dessa cor é conexo. Sabe-se que este problema é NP-difícil. Associamos a este problema um poliedro, e estudamos sua estrutura facial, com vistas ao desenvolvimento de um algoritmo. Mostramos várias inequações válidas para este poliedro, e provamos que várias delas definem facetas. Apresentamos um algoritmo de programação dinâmica que resolve em tempo polinomial o problema da separação para uma classe grande de inequações que definem facetas. Implementamos um algoritmo branch-and-cut baseado nesses resultados, e realizamos testes computacionais com instâncias geradas aleatoriamente. Apresentamos adicionalmente uma heurística baseada numa formulação linear que obtivemos. Estudamos também um caso especial deste problema, no qual as instâncias consistem em caminhos coloridos, onde cada cor ocorre no máximo duas vezes. Apresentamos um algoritmo de 3/2-aproximação para este caso, que é também NP-difícil. Para o caso geral, é conhecido na literatura um algoritmo de 2-aproximação. / The focus of this thesis is the design of algorithms for the convex recoloring problem on paths. In this problem, the instance consists of a path whose vertices are arbitrarily colored, and the objective is to recolor the least number of vertices so as to obtain a convex coloring.Acoloring of a graph is convex if, for each color, the subgraph induced by the vertices of this color is connected. This problem is known to be NP-hard. We associate a polyhedron to this problem and investigate its facial structure. We show various classes of valid inequalities for this polyhedron and prove that many of them define facets.We present a polynomial-time dynamic programming algorithm that solves, in polynomial time, the separation problem for a large class of facet-defining inequalities.We report on the computational experiments with a branch-and-cut algorithm that we propose for the problem. Additionally, we present a heuristic that is based on a linear formulation for the problem. We also study a special case of this problem, restricted to instances consisting of colored paths in which each color occurs at most twice. For this case, which is also NP-hard, we present a 3/2-approximation algorithm. For the general case, it is known a 2-approximation algorithm.

Neste trabalho, procurei construir um ajuste fenomenológico que descrevesse o comportamento das oscilações acústicas de bárions (BAO) no espectro de potência da temperatura de brilho da linha de 21cm do átomo de hidrogênio neutro, na aproximação de Limber. O ajuste obtido demonstrou ser capaz de descrever o comportamento oscilatório do BAO nas faixas de redshift analisados, que foram de 0.127 à 0.479. Quando combinado com dados de supernova, restrições nos parâmetros cosmológicos tiveram resultados mais precisos. Contudo, restrições incluindo a medida do valor local da constante de Hubble piora os dados, devido a grandes divergências nos valores da constante de Hubble. / In this work, I searched for a phenomenological fit that describes the behavior of the baryon acoustic oscillation (BAO) in the angular power spectrum of brightness temperature of the 21cm line from the neutral hydrogen atom, under Limbers approximation. The fit obtained has shown to be capable of describe the oscillatory behaviour of the BAO in the redshift bands analyzed, that lies in the range from 0.127 to 0.479. When combined with supernova data, the constraints in the cosmological parameters produced more precise results. However, constraints including measuring the local value of the Hubble. constant worsen the data, due to great divergences in the values of the Hubble constant.

Orientador: Sergio Antonio Tozoni / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica / Made available in DSpace on 2018-08-25T19:58:00Z (GMT). No. of bitstreams: 1 Stabile_RegisLeandroBraguim_D.pdf: 1552111 bytes, checksum: af2b74d1076ee2c6dd825049748fd3fd (MD5) Previous issue date: 2014 / Resumo: As teorias de n-larguras e de entropia foram introduzidas por Kolmogorov na década de 1930. Desde então, muitos trabalhos têm visado obter estimativas assintóticas para n-larguras e números de entropia de diferentes classes de conjuntos. Neste trabalho, investigamos n-larguras e números de entropia de operadores multiplicadores definidos sobre o toro d-dimensional. Na primeira parte, estabelecemos estimativas inferiores e superiores para n-larguras e números de entropia de operadores multiplicadores gerais. Na segunda parte, aplicamos estes resultados para operadores multiplicadores específicos, associados a conjuntos de funções finitamente e infinitamente diferenciáveis sobre o toro. Em particular, demonstramos que as estimativas obtidas são exatas em termos de ordem em diversas situações / Abstract: The theories of n-widths and entropy were introduced by Kolmogorov in the 1930s. Since then, many works aims to find estimates for n-widths and entropy numbers of different classes of sets. In this work, we investigate n-widths and entropy numbers of multiplier operators defined on the d-dimensional torus. In the first part, upper and lower bounds are established for n-widths and entropy numbers of general multiplier operators. In the second part, we apply these results to specific multiplier operators, associated with sets of finitely and infinitely differentiable functions on the torus. In particular, we prove that, the estimates obtained are order sharp in various situations / Doutorado / Matematica / Doutor em Matemática

Orientador: Eduardo Candido Xavier / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-24T00:15:42Z (GMT). No. of bitstreams: 1 Silveira_JeffersonLuizMoisesda_D.pdf: 2236708 bytes, checksum: 8e569408c2f068347058e36031689c3a (MD5) Previous issue date: 2013 / Resumo: Neste trabalho estamos interessados em problemas de empacotamento e roteamento. Assumindo a hipótese de que P ? NP, sabemos que não existem algoritmos eficientes para resolver tais problemas. Além de algoritmos exatos, duas das abordagens para resolver tais problemas são Algoritmos Aproximados e Heurísticas. Nesta tese mostramos algoritmos baseados nestas três abordagens para ambos os problemas, de empacotamento e roteamento. Os dois primeiros problemas atacados foram generalizações de problemas clássicos de empacotamento: O problema da mochila bidimensional e o problema de empacotamento em faixas. Estes foram generalizados adicionando restrições na forma de carregamento e descarregamento dos itens no recipiente (restrições estas, que aparecem no contexto de problemas de roteamento). O terceiro problema é uma combinação de problemas de empacotamento e roteamento. Neste caso, atacamos uma generalização do clássico Pickup and Delivery Problem. Propomos os primeiros resultados de aproximação para algumas versões dos problemas de empacotamento supracitados. Além disto, apresentamos algumas abordagens práticas para o terceiro problema. As heurísticas foram avaliadas através de experimentos computacionais comparando os seus resultados com algoritmos exatos / Abstract: In this work we are interested in packing and routing problems. Assuming P ? NP, we have that there are no efficient algorithms to deal with such problems. Besides exact algorithms, two approaches to solve such problems are Approximation Algorithms and Heuristics. In this thesis we show algorithms using these three approaches for both packing and routing problems. The first two addressed problems are generalizations of classical packing problems: The Two Dimensional Knapsack problem and the Strip Packing problem. These problems were generalized by adding constraints on the way the items can be inserted/removed into/from the bin (These constraints appear in the context of routing problems). The third problem is combination of packing and routing problems. It is a generalization of the classical Pickup and Delivery problem. We propose the first approximation results for some packing problems. Besides that, we present some practical algorithms for the third problem. The heuristics were assessed through computational experiments by comparing their results with exact algorithms / Doutorado / Ciência da Computação / Doutor em Ciência da Computação

Conselho Nacional de Desenvolvimento Científico e Tecnológico / Experimental data show that the dissolved impurities of the Mn presents a magnetic moment when substitute the Ni atom in pseudoquaternary borocarbide Y (Ni(1−x)Mx)2B2C, this is not observed if the impurities are Fe and Co. In this work we do a theoretical study of the superconducting order parameter variation and a possible formation of impurities magnetic moment to T < Tc. We have used the LAPW method, based in Density Functional Theory, to calculate the density of state of pure compound. To describe the superconductor system it was used the attractive Hubbard model. To describe the effects of the disorder induced by the dissolved impurities was used the coherent potential approximation. Using the Nambu s formalism to represent the Hamiltonian and the Green s functions of the effective medium (g) and of the perturbed system (G), we calculate the magnetic moment of the impurities from the diagonal terms and the variation of the order parameter from the off-diagonal one. The calculated date to magnetic moment show a qualitative agreement with the experimental results to Mn impurities. To the Fe and Co cases no magnetic moment was observed, in agreement with the experimental results too. The calculated order parameter shows a decrease with concentration to the Mn and Fe atoms. We investigate, through of the a calculation first principles (LAPW), the possible formation of the magnetic moment in this compound to concentration of 25 and 12.5%. The obtained results show that to concentration of 25%, both the impurities, Mn and Fe, presents a magnetic moment. The magnetization on the Co site was small when compared with the above cases. In this way we conclude that the Co atom not present a magnetic moment in this system. / Medidas experimentais mostram que impurezas de Mn formam momento magnético quando substituem o Ni no borocarbeto pseudoquaternário Y (Ni(1−x)Mx)2B2C, enquanto que as impurezas de Fe e de Co não exibem tal comportamento. Neste trabalho foi feito um estudo teórico da variação do parâmetro de ordem supercondutor e da possível formação de momento magnético nos sítios dessas impurezas para T < Tc. Para isso, utilizamos o m´etodo LAPW, baseado na Teoria do Funcional da Densidade, para calcular a densidade de estados do composto puro. Para descrever o sistema supercondutor foi utilizado o modelo de Hubbard atrativo. Os efeitos de desordem induzidos pela adição de impurezas de metais de transição M no material, foram tratados dentro da aproximação do potencial coerente. Usando o formalismo de Nambu para representar o hamiltoniano e as funções de Green associadas aos propagadores do sistema efetivo (g) e do sistema perturbado (G), calculamos o momento magn´etico das impurezas através dos termos diagonais e as variações do parâmetro de ordem efetivo a partir do termo fora da diagonal. Os resultados obtidos comprovam o que é observado experimentalmente, ou seja, o Mn forma momento magn´etico que aumenta com a concentração, enquanto que nas impurezas de Fe e Co nenhuma magnetização foi observada. Além disso, o parâmetro de ordem diminui com a concentração de Mn e Fe. Além desse estudo, também investigamos, através de um cálculo de primeiros princípios (LAPW), a possível formação de momento magnético neste composto para concentrações de 25 e 12.5%. Os resultados obtidos mostraram que para x = 25%, tanto as impurezas de Mn quanto as de Fe, apresentaram um momento magnético. A magnetização no síıtio do Co foi bastante pequena comparada com as duas anteriores e dessa forma pode-se concluir que esta impureza não forma momento quando diluída neste sistema.

Orientador: Eduardo Candido Xavier / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-27T04:49:46Z (GMT). No. of bitstreams: 1 Povoa_MarceloGalvao_M.pdf: 1965830 bytes, checksum: 7509ae1701df384bfdc3d415ecd4eda8 (MD5) Previous issue date: 2015 / Resumo: Sistemas computacionais conhecidos como Data Grids fornecem uma infraestrutura computacional distribuída para processamento e armazenamento de dados, com várias aplicações envolvendo computação em larga escala. Devido ao uso de um grande volume de dados, é necessário não apenas um escalonamento eficiente de tarefas, mas também uma distribuição inteligente de réplicas dos dados para se atingir o melhor desempenho. Esses dois problemas já foram extensivamente estudados de forma independente na literatura, mas estamos concentrados em um formulação integrada em um problema estático, de forma a otimizar uma única função objetivo. Primeiramente, mostramos que este problema não pode admitir um algoritmo aproximado. Porém, considerando uma versão restrita do problema, apresentamos um algoritmo aproximado original com fator de aproximação constante. Também fazemos um estudo de algoritmos aproximados para problemas relacionados disponíveis na literatura. Sob um aspecto mais prático, introduzimos duas heurísticas originais para o problema. A primeira é baseada no agrupamento de máquinas próximas em clusters, enquanto a segunda procura identificar grupos de dados frequentemente acessados em conjunto. Comparamos esses algoritmos com duas abordagens adaptadas da literatura, através de simulações computacionais em um grande conjunto de instâncias baseadas em grids reais. Mostramos que nossa primeira heurística costuma obter melhores soluções que as outras com boa eficiência de tempo, enquanto a segunda heurística é ainda mais rápida e ainda obtém soluções competitivas / Abstract: Computational systems known as Data Grids provide a flexible, distributed computing infrastructure for processing and storage and has many applications in large-scale computing. Due to the use of great amounts of data, not only efficient task scheduling but also thorough file replication are crucial for achieving the best performance. Both these problems have already been studied independently in the literature, but we are interested in a combined formulation as a static problem, in order to minimize a single objective function. First, we show that this problem does not admit an approximation algorithm. However, considering a restricted version of the problem, we provide a constant ratio approximation algorithm. We also conduct a study of approximation algorithms for related problems avaliable in the literature. On a more practical side, we introduce two novel heuristics for the problem. The first is based on grouping neighbor nodes into clusters, while the second tries to identify groups of files frequently accessed together. We compare these algorithms with two adapted approaches from other works in the literature by doing computational simulations using an extensive set of instances based on real grids. We show that our first heuristic often obtains the best solutions with good time efficiency, while the second is even faster and still provides competitive solutions / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Nesta dissertação estudamos --- do ponto de vista algorítmico --- o seguinte problema, conhecido como problema da partição conexa balanceada. Dado um grafo conexo G com pesos atribuídos a seus vértices, e um inteiro q >= 2, encontrar uma partição dos vértices de G em q classes, de forma que cada classe da partição induza um grafo conexo e que, ao considerar as somas dos pesos dos vértices de cada classe, a menor das somas seja o maior possível. Em outras palavras, o objetivo é encontrar q classes cujos pesos sejam tão balanceados quanto possível. Sabe-se que este problema é NP-difícil. Mencionamos alguns resultados sobre complexidade computacional e algoritmos que são conhecidos para este problema. Apresentamos algumas heurísticas que desenvolvemos, todas elas baseadas no uso do algoritmo polinomial para árvores, devido a Perl e Schach, que apresentamos com detalhe. Implementamos quatro heurísticas e um algoritmo de 3/4-aproximação conhecido para o caso q=2. Exibimos os resultados obtidos com os vários testes computacionais conduzidos com instâncias aleatórias, com grafos de diferentes pesos e densidades. Os resultados computacionais indicam que o desempenho dessas heurísticas --- todas elas polinomiais --- é bem satisfatório. No caso especial em que q=2, observamos que a heurística mais onerosa sistematicamente produziu soluções melhores ou iguais às do algoritmo de aproximação / In this dissertation we study algorithmic aspects of the following problem, known as the balanced connected partition. Given a connected graph G with weights defined on its vertices, and an integer q >= 2, find a partition of the vertices of G into q classes such that each class induces a connected graph, and furthermore, when we consider the sum of the weights of the vertices in each class, the smallest sum is as large as possible. In other words, the q classes must have weights that are as balanced as possible. This problem is known to be NP-hard. We mention some computational complexity and algorithmic results that are known for this problem. We present some heuristics that we designed, all of them based on the use of the polynomial algorithm for trees, due to Perl and Schach, which we show in detail. We implemented four heuristics and a 3/4-approximation algorithm that is known for q=2. We run tests on many random instances, of graphs with different weights and densities. The computational results indicate that the performance of these heuristics --- all of polynomial time complexity --- are very satisfactory. For q=2, we observed that the most expensive heuristic produced solutions with values which are systematically better or equal to those produced by the approximation algorithm.

O tema central deste trabalho é o estudo de problemas sobre caminhos mais longos em grafos, de pontos de vista tanto estrutural como algorítmico. A primeira parte tem como foco o estudo de problemas motivados pela seguinte questão levantada por T. Gallai em 1966: é verdade que em todo grafo conexo existe um vértice comum a todos os seus caminhos mais longos? Hoje, já se conhecem diversos grafos conexos cuja intersecção de todos os seus caminhos mais longos é vazia. Entretanto, existem classes de grafos para as quais a resposta à pergunta de Gallai é afirmativa. Nessa linha, apresentamos alguns resultados da literatura e duas novas classes que obtivemos: os grafos exoplanares e as 2-árvores. Motivado por esse problema, nos anos 80, T. Zamfirescu formulou a seguinte pergunta que permanece em aberto: é verdade que em todo grafo conexo existe um vértice comum a quaisquer três de seus caminhos mais longos? Apresentamos, além de alguns resultados conhecidos, uma prova de que a resposta é afirmativa para grafos em que todo bloco não trivial é hamiltoniano. Notamos que esse último resultado e o acima mencionado para grafos exoplanares generalizam um teorema de M. Axenovich (2009) que afirma que quaisquer três caminhos mais longos em um grafo exoplanar têm um vértice em comum. Finalmente, mencionamos alguns outros resultados da literatura relacionados com o tema. Na segunda parte, investigamos o problema de encontrar um caminho mais longo em um grafo. Este problema é NP-difícil para grafos arbitrários. Isto motiva investigações em duas linhas a respeito da busca de tais caminhos. Pode-se procurar classes especiais de grafos para as quais existem algoritmos polinomiais, ou pode-se abrir mão da busca de um caminho mais longo, e projetar um algoritmo eficiente que encontra um caminho cujo comprimento esteja próximo do comprimento de um mais longo. Nesse trabalho estudamos ambas as abordagens e apresentamos alguns resultados da literatura. / The central theme of this thesis is the study of problems related to longest paths in graphs, both from a structural and an algorithmic point of view. The first part focuses on the study of problems motivated by the following question raised by T. Gallai in 1966: is it true that every connected graph has a vertex common to all its longest paths? Today, many connected graphs in which all longest paths have empty intersection are known. However, there are classes of graphs for which Gallais question has a positive answer. In this direction, we present some results from the literature, as well as two new classes we obtained: outerplanar graphs and 2-trees. Motivated by this problem, T. Zamfirescu, in the 80s, proposed the following question which remains open: is it true that every connected graph has a vertex common to any three of its longest paths? We present, in addition to some known results, a proof that the answer to this question is positive for graphs in which all non-trivial blocks are Hamiltonian. We note that this result and the one mentioned above for outerplanar graphs generalize a theorem of M. Axenovich (2009) that states that any three longest paths in an outerplanar graph have a common vertex. Finally, we mention some other related results from the literature. In the second part, we investigate the problem of finding a longest path in a graph. This problem is NP-hard for arbitrary graphs. This motivates investigations in two directions with respect to the search for such paths. We can look for special classes of graphs for which the problem is polynomially solvable, or we can relinquish the search for a longest path and design an efficient algorithm that finds a path whose length is close to that of a longest path. In this thesis we study both approaches and present some results from the literature.