Orientador: Sueli Irene Rodrigues Costa / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-10T04:41:55Z (GMT). No. of bitstreams: 1 Carlos_TatianaBertoldi_D.pdf: 779190 bytes, checksum: d0ff8f53ff44a5f19c7edb1427cd1a82 (MD5) Previous issue date: 2007 / Resumo: Neste trabalho abordamos a construção de reticulados usando propriedades da teoria dos números algébricos. Enfocamos particularmente a construção, como reticulado ideal, de rotações do reticulado n-dimensional dos inteiros, usando corpos ciclotômicos. Reticulados desta forma tem se mostrado uma eficiente ferramenta para obtenção de bons esquemas de codificação para canais com desvanecimento, pois permitem estimativas da distância produto e diversidade, parâmetros que controlam a probabilidade de erro no envio de informações por estes canais. Apresentamos uma nova construção de tais reticulados no caso em que n é uma potência de 2, através do subcorpo maximal real do n-ésimo corpo ciclotômico. Estabelecemos também condições para que um reticulado ideal seja rotação do reticulado n-dimensional dos inteiros, usando algoritmos de redução de base, LLL (Lenstra-Lenstra- Lovász) e Minkowski. Outros resultados incluem caracterizações geométricas de grafos circulantes e de alguns reticulados construídos algebricamente. / Abstract: In this work we approach lattice constructions using properties of algebraic number theory. One focus is on the construction of ideal lattices via cyclotomic fields. Those lattices have been used as an efficient tool for designing coding strategies for the Rayleigh fading channels since it is possible to estimate the product distance and the diversity, parameters which control the error probability transmission for those channels. A special case, due to "shaping gain", is when those lattices are rotations of the n-dimensional integer lattice. We present a new construction of such lattices when n is a power of 2, via the maximal sub-field of the n-cyclotomic field. We also establish conditions for an ideal lattice to be a Zn-lattice using the Minkowski and the LLL (Lenstra-Lenstra-Lovasz) reductions. Other results include geometric characterizations of circulant graphs and of some algebraic lattices. / Doutorado / Doutor em Matemática

Orientador: Jorge Stolfi [Orientador] / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação. / Made available in DSpace on 2018-08-10T07:43:58Z (GMT). No. of bitstreams: 1 Montagner_ArnaldoJovanini_D.pdf: 2204093 bytes, checksum: 4c9c86ca0312f3b5507e1daa8c6553db (MD5) Previous issue date: 2007 / Resumo: Mapas são subdivisões de espaços topológicos em regiões simples, e triangulações são um tipo específico de mapa em que cada elemento é um simplexo (aresta, triângulo, tetraedro, etc). Neste trabalho, tratamos o problema de representação da topologia de triangulações e mapas de dimensão arbitrária. Estudamos a utilização de uma representação baseada em grafos de arestas coloridas, já utilizada como ferramenta teórica, mas nunca empregada em aplicações práticas. A principal limitação desta representação é a relativa inflexibilidade imposta sobre a manipulação da topologia. Há porém grandes vantagens em sua utilização, como a simplicidade de representação e a generalidade. Este trabalho consiste na especificação teórica de uma estrutura de dados baseada nestes grafos coloridos e de operações topológicas para construção e manipulação da estrutura. A utilização desta estrutura é ilustrada através de algoritmos para resolução de problemas em geometria computacional / Abstract: Maps are subdivisions of topological spaces into simple regions, and triangulations are a specific kind of map wherein each element is a simplex (edge, triangle, tetrahedron, etc). In this work, we analyze the problem of representing the topology of triangulations and maps with arbitrary dimension. We study a representation based on edge-colored graphs, already used as theoretical tool, but never employed in practical applications. The main limitation of this representation is the relative inexibility imposed on the manipulation of topology. There are, though, great advantages in its use, as its simplicity and generality. This work consists in the theoretic specification of a data structure based on these colored graphs and of topological operators to build and manipulate the structure.The use of this structure is illustrated by algorithms for computational geometry problems / Doutorado / Computação Grafica / Mestre em Ciência da Computação

A fragmentação de habitats em muitos casos limita o potencial de dispersão das espécies. Por esta razão, muitas iniciativas visando à conservação de espécies em paisagens fragmentadas envolvem o delineamento de corredores ecológicos entre manchas de hábitat. Neste trabalho, foi modelado um sistema de corredores entre manchas de mata remanescentes no mosaico urbano-rural de uma grande cidade no sul do Brasil (Porto Alegre, RS), tendo como organismo focal o primata Alouatta clamitans (bugio-ruivo) que está ameaçado de extinção. Nossos objetivos específicos são (a) demonstrar a importância dá conectividade para a presença das populações de bugio-ruivo nos fragmentos florestais em Porto Alegre; (b) detectar os fragmentos mais importantes para manter a conectividade funcional potencial da espécie; (c) desenhar um sistema de corredores potenciais, considerando a capacidade de dispersão do bugio-ruivo em diferentes tipos de manchas de paisagem e (d) propor um método para avaliação da qualidade de corredores, levando em consideração a variação do atrito à dispersão ao longo do traçado dos corredores e a existência de pontos críticos de vulnerabilidade ao longo dos corredores. A vulnerabilidade foi avaliada em função da paisagem vizinha a cada corredor, entendendo-se como vulnerabilidade a probabilidade de futura modificação ou interrupção do corredor devido a mudanças na paisagem vizinha. Foi verificada a existência da relação da conectividade funcional com a presença da espécie nos fragmentos florestais através do índice Integral index of connectivity - IIC. Através da porcentagem de importância do mesmo índice (dIIC) para cada fragmento arbóreo, identificou-se o morro São Pedro como mais importante para a manutenção da conectividade da paisagem. Além do morro São Pedro foram selecionados os fragmentos arbóreos maiores que 10 ha para a modelar corredores utilizando o algoritmo do caminho de menor custo. Utilizou-se dois parâmetros: grau de antropização que avalia o potencial de persistência dos corredores e o atrito que simula a resistência dos habitats ao deslocamento da espécie. Esses parâmetros foram utilizados nas análises de fracionamento para quantificar o número de interrupções no corredor e a qualidade do habitat interno. Os resultados da análise de fracionamento e a extensão foram usados na classificação de qualidade de cada corredor. Foram gerados 136 corredores com extensão entre 4 m e 4128 m, Observou-se que corredores com mais de 1000 m tendem a ser potencialmente mais fracionados. Setenta e três corredores mantiveram-se contínuos segundo o potencial de persistência. A análise da qualidade do habitat revelou que 120 corredores foram fracionados. A área total de habitat efetivo (classe arbórea/arbustiva) para o deslocamento foi reduzida em 41%. A análise de qualidade global revelou que 32% dos corredores são bons, 51% são medianos e 16,2% são ruins. O potencial de persistência revelou-se um método promissor de avaliar o potencial de alteração que o entorno tem em relação ao corredor. A análise de qualidade de habitat mostrou-se eficiente para identificar os corredores lineares de hábitat ou íntegros. O método pode auxiliar na tomada de decisão do custo-beneficio para investir em gestão e manejo de corredores lineares multi-habitat. / Habitat fragmentation limits possibility of species dispersai. Many initiatives aim at species conservation in fragmented landscapes involve the delineation of ecological corridors among habitat patches. Here, we modeled a corridor system among remnant forest fragments in the urban-rural mosaic of a large city in southern Brazil (Porto Alegre, RS), using the endangered primate Alouatta clamitans (brown-howler-monkey) as a focal species. Our specific aims were (a) to demonstrate the importance of connectivity for the presence of the brown-howler monkey in forest fragments; (b) to identify the most important fragments for maintenance of potential functional connectivity for the species; (c) to draw a potential corridor system, considering the species dispersai capacity in different habitat patches; and (d) to propose a new method of corridor quality evaluation, considering friction variation to disperse along corridors and the existence of vulnerable criticai points for the persistence of corridors. Vulnerability was evaluated in terms of neighboring landscape of each corridor (context), being defined as the probability of future corridor modification or interruption due to changes in the neighboring landscape. We examined the existence of a positive relation between functional connectivity and the species presence in forest fragments using the Probability of Connectivity index (dIPC). We identified the São Pedro hill as the most important area for the maintenance of landscape connectivity based on the dIPC. In addition to São Pedro hill, we selected the forest fragmentes larger than 10 hectares to model corridors using the least-cost distance algorithm. To assess vulnerability, we used two parameters: the antropization degree, which is a proxy for potential of corridor persistence, and the friction degree, which is a proxy for habitat resistance to the species dispersal. These parameters were used to examine the fractioning of corridors, that is, to quantify the number of actual or potential interruptions in corridor trajectory and its inner habitat quality. The results of the fractioning analyses and the corridor extension were used as attributes for ranking ali corridors in terms of quality. We generated 136 corridors with an extension between 4 m and 4128 m. Corridors with more than 1000 m tended to be potentially more fractioned, while seventy three corridors were kept uninterrupted according to persistence potential. Habitat quality analysis revealed that 120 corridors were fractioned. Total area of effective habitat (arboreal/shrubby class) to movements was reduced in 41%. The global quality analysis revealed that 32% of corridors are good, 51% are median and 16.2% are bad. Persistence potential appears to be a promising method to evaluate the potential for antropogenic modification imposed on corridors by their surrounding landscape. This method cari help in cost-benefit decision making for management of multi-habitat linear corridors.

O objetivo desta dissertação é apresentar uma pesquisa e investigação que validam uma proposta de sequência didática que utiliza a perspectiva metodológica da Resolução de Problemas para ensinar conceitos relacionados à Teoria de Grafos na escola básica, mais especificamente, no Ensino Fundamental. Para tanto, a metodologia de pesquisa escolhida foi o Estudo de Caso, de acordo com Fiorentini e Lorenzato (2006), Ventura (2007) e Gil (1995). O referencial teórico é baseado nos trabalhos do GTERP1, de Onuchic e Allevato (1999) e (2004), Polya (2006), Pozo (1998), Santos (2002) e De Maio (2009), bem como os PCNs2 e outros artigos/livros relacionados à Teoria de Grafos e à Resolução de Problemas. Apresentaremos uma prática realizada com cinco grupos de uma turma do sétimo ano do Ensino Fundamental, em uma escola particular de Porto Alegre, no ano de 2014. Concluímos que a escolha desse tópico da Matemática aliado à perspectiva metodológica da Resolução de Problemas contribui para o desenvolvimento intelectual e matemático, bem como para a formação de um indivíduo mais autônomo e crítico. / The aim of this dissertation is to show a research and investigation that validate a didactic propose of sequence that use the methodological perspective of Problem Solving to teach concepts related to Graph Theory in primary school, more specifically, in Elementary School. For this, the research methodology chosen was Case Study according to Fiorentini and Lorenzato (2006), Ventura (2007) and Gil (1995). The theoretical approach is based on the work of GETERP, Onuchic and Allevato (1999) and (2004), Polya (2006), Pozo (1998), Santos (2002) and De Maio (2009), as well as the National Curriculum Parameters (PCNs), books and articles dealing with Graph Theory and the Problem Solving. We will introduce a practice carried out with five groups of a class of seventh year of primary school, in a private school of Porto Alegre, in 2014. We conclude that the choice of this topic of mathematics combined with methodological perspective of Problem Solving contribute to the intellectual and mathematician development, as well as the formation of a more autonomous and critical individual.

o objetivo principal deste trabalho é apresentar uma proposta de inserção de Teoria de Grafos no Ensino Médio. Para tanto, será feita uma fundamentação de alguns aspectos acerca da Teoria de Grafos e Resolução de Problemas. Apresentaremos uma prática realizada em dois grupos de segundo ano do Ensino Médio, numa escola particular de Porto Alegre, no ano de 2006. A Teoria de Grafos apresenta aspectos pertinentes que merecem espaço no currículo da Escola Básica. Apresentaremos uma seleção de possíveis atividades a serem implementadas numa perspectiva metodológica de Resolução de Problemas. A escolha por tal perspectiva metodológica em Educação Matemática está vinculada à prática de Ensino de Matemática que acreditamos ser capaz de contribuir para a formação de um indivíduo autônomo, criativo e capaz de aprender a aprender. / The main goal of this thesis is to present a proposal for the insertion of Graph Theory in High School. In order to do that, we present some principIes of Graph Theory and review some important writings about Problem Solving methodology. We will give a suggested practice done with two groups in the second year of High School, in a private school of Porto Alegre in 2006. Graph Theory has some aspects that deserve space in the curriculum of the Basic School. We will show a selection of possible activities to be implemented within a methodological perspective of Problem Solving. The choice for this methodological perspective in Mathematics Education is related to a practice in Mathematics Teaching that we believe contributes for a development of a more autonomous and creative person. A person that is and able to learn how to learn.

Orientador: Celia Picinin de Mello / Tese (doutorado) - Universidade Estadual de Campinas , Instituto de Computação / Made available in DSpace on 2018-08-06T12:11:33Z (GMT). No. of bitstreams: 1 Campos_ChristianeNeme_D.pdf: 1048367 bytes, checksum: e8270db6704873ddaf2043927ca93e99 (MD5) Previous issue date: 2006 / Doutorado / Teoria dos Grafos / Doutor em Ciência da Computação

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This work aims to present a basic study of social networks and to show how some elements of this theory can be presented in classroom to illustrate and encourage the study of Graph Theory. To reach our goal, we developed some social network applications in State schools, through activities involving students and teachers as well as relationships between teachers and the educational institutions in which they work, activities which were developed using UCINET software. / Este trabalho tem como objetivo apresentar um estudo básico de redes sociais e mostrar como alguns elementos desta teoria podem ser apresentados em sala de aula para ilustrar e estimular o estudo da Teoria dos Grafos. Por isso, desenvolvemos algumas aplicações de redes sociais em sala de aula e instituições públicas de ensino, por meio de atividades envolvendo alunos e professores, bem como relações entre professores e as respectivas instituições de ensino nas quais trabalham, atividades as quais foram desenvolvidas através do software UCINET.

Orientador: Akebo Yamakami / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-14T08:52:58Z (GMT). No. of bitstreams: 1 Verga_Juliana_M.pdf: 625534 bytes, checksum: 396d5b5c1dafff5b2fbb632e185c4a72 (MD5) Previous issue date: 2009 / Resumo: A teoria dos 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 fluxo multiproduto é um dos que também podem ser modelados por grafos. Este trabalho apresenta uma proposta de solução para o problema de fluxo multiproduto fuzzy. O problema foi modelado através de um grafo, cujos nós representam pontos de oferta e demanda de produtos, os quais trafegam pelos arcos da rede. O algoritmo proposto visa encontrar soluções factiveis e boas para o problema de fluxo multiproduto fuzzy em redes com incertezas nos custos e capacidades, contendo múltiplas origens e múltiplos destinos. As incertezas são modeladas por meio da teoria dos conjuntos fuzzy, que tem sido aplicada com sucesso em problemas com incertezas. / Abstract: The graph theory is commonly used in the area of engineering to solve problems that can be represented in the form of nets. Among several problems, the multicommodity flow problem is one that can be modeled by graphs. This work presents an approach for solving the fuzzy multicommodity flow problem. The problem was modeled through a graph whose nodes represent points of supply and demand of commodities, which pass through arcs of the network. Our algorithm aims to find a set of good feasible solutions for the fuzzy multicommodity flow problem in networks with uncertainties in the costs and capacities, containing multiple origins and multiple destinations. The uncertainties are modeled by means of the fuzzy sets theory, which has been successfully applied to problems with uncertainties. / Mestrado / Automação / Mestre em Engenharia Elétrica

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.