Resumo: As árvores binárias são estruturas de dados utilizadas tradicionalmente para a realização de pesquisa de forma eficiente sobre um conjunto de dados. Uma árvore pode atingir grandes dimensões, bem como ser utilizada para armazenar dados em memória secundária ou distribuídos pelos nodos de uma rede de computadores. Nestes casos, é necessário definir uma estratégia eficiente para o acesso aos dados da árvore, que são organizados em páginas. Uma página é utilizada para a transferência de dados em blocos da memória secundária para a primária, além do acesso remoto em redes de computadores, por intermédio de pacotes que possuem tamanho máximo pré-fíxado. Este trabalho apresenta um algoritmo para a paginação de árvores binárias de pesquisa aplicável quando o conjunto de informações é estático, as freqüências de acesso não são conhecidas e o armazenamento é remoto ou secundário. O algoritmo visa reduzir o tempo de pesquisa aos dados armazenados na árvore binária em termos do número de páginas visitadas e do aumento da taxa de preenchimento das páginas utilizadas. Uma versão alternativa do algoritmo que visa reduzir a distância internodal nas páginas é apresentada. Observou-se que o algoritmo proposto constrói a paginação ótima quando possível, isto é, quando a árvore é completa e o número de nodos é múltiplo do tamanho da página. Além disso, propõe-se uma política eficiente para o preenchimento das páginas de uma árvore binária degenerada tendo por base a aplicação de empacotamento unidimensional na franja da árvore. A complexidade computacional do algoritmo, que depende do empacotamento unidimensional a ser utilizado, é discutida e apresentada. O algoritmo foi implementado e resultados experimentais quanto ao número de páginas visitadas e à taxa de preenchimento das páginas utilizadas, comparativos com a paginação seqüencial, valores ótimos teóricos e as árvores B, são descritos e analisados. Comparando o algoritmo proposto com as árvores B, enquanto o número de paginas visitadas por pesquisa é similar em ambas as abordagens, a taxa de preenchimento das páginas produzida pelo algoritmo proposto é mais de 30% superior à taxa obtida pelas árvores B.

Freitas, L. I. B. A conjectura de Tuza sobre triângulos em grafos. 2014. 83 f. Dissertação (Mestrado Ciência da Computação) - Instituto de Computação, Universidade Estadual de Campinas, Campinas, 2014. / Submitted by Juliana Almeida (julianaufc@gmail.com) on 2014-10-30T18:26:55Z No. of bitstreams: 1 2014_dis_libfreitas.pdf: 1836193 bytes, checksum: 8a654f1e68aa87973b4560f5c194508f (MD5) / Approved for entry into archive by Juliana Almeida(julianaufc@gmail.com) on 2014-10-30T18:28:27Z (GMT) No. of bitstreams: 1 2014_dis_libfreitas.pdf: 1836193 bytes, checksum: 8a654f1e68aa87973b4560f5c194508f (MD5) / Made available in DSpace on 2014-10-30T18:28:27Z (GMT). No. of bitstreams: 1 2014_dis_libfreitas.pdf: 1836193 bytes, checksum: 8a654f1e68aa87973b4560f5c194508f (MD5) Previous issue date: 2014 / In this thesis we study the conjecture of Tuza, which relates covering of triangles (by edges) with packing of edge-disjoint triangles in graphs. In 1981, Tuza conjectured that for any graph, the maximum number of edge-disjoint triangles is at most twice the size of a minimum cover of triangles by edges. The general case of the conjecture remains open. However, several attempts to prove it appeared in the literature, which contain results for several classes of graphs. In this thesis, we present the main known results for the conjecture of Tuza. Currently, there are several versions of Tuza’s conjecture. Nevertheless, we emphasize that our focus is on conjecture applied to simple graphs. We also present a conjecture that, if verified, implies the validity of the conjecture of Tuza. We also show that if G is a mininum counterexample to the conjecture of Tuza, then G is 4-connected. We can deduce from this result that the conjecture of Tuza is valid for graphs with no K5 minor. / Neste trabalho estudamos a conjectura de Tuza, que relaciona cobertura mínima de triângulos por arestas com empacotamento máximo de triângulos aresta-disjuntos em grafos. Em 1981, Tuza conjecturou que para todo grafo, o número máximo de triângulos aresta-disjuntos é no máximo duas vezes o tamanho de uma cobertura mínima de triângulos por arestas. O caso geral da conjectura continua aberta. Contudo, diversas tentativas de prová-la surgiram na literatura, obtendo resultados para várias classes de grafos. Nesta dissertação¸ nós apresentamos os principais resultados obtidos da conjectura de Tuza. Atualmente, existem várias versões da conjectura. Contudo, ressaltamos que nosso foco está na conjectura aplicada a grafos simples. Apresentamos também uma conjectura que se verificada, implica na veracidade da conjectura de Tuza. Demonstramos ainda que se G é um contraexemplo mínimo para a conjectura de Tuza, então G é 4-conexo. Deduzimos desse resultado que a conjectura de Tuza é válida para grafos sem minor do K5.

Orientador : Marcelo Firer / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-07-27T17:53:18Z (GMT). No. of bitstreams: 1 Faria_MercioBotelho_M.pdf: 14611582 bytes, checksum: 61aa064159bcc7d73d18470e00be77ed (MD5) Previous issue date: 2000 / Resumo: Começamos o texto com uma breve apresentação de conceitos essenciais ao desenvolvimento do trabalho: uma introdução à geometria hiperbólica (capítulo 1) e grupos fuchsianos (capítulo 2), grupos discretos de isometrias do plano hiperbólico. Introduzimos a seguir, em sua forma genérica, o problema de empacotamento de esferas (capítulo 3). Apresentamos alguns resultados importantes para o caso euclidiano e a seguir, introduzimos as definições necessárias para o estudo do problema de empacotamento em espaços hiperbólicos. Neste caso, fazemos também uma apresentação de diversos resultados importantes, cobrindo parte relevante da literatura atual sobre o tema. No capítulo 4, desenvolvemos duas questões referentes a empacotamentos no plano hiperbólico (bi-dimensional). A primeira delas é o estudo da densidade local de ladrilhamentos (p,q) do plano. Provamos que a o limite da densidade local quando p e q tendem a ¥ existe e é igual a 2/p, portanto menor que o melhor limitante conhecido, a densidade simplicial d2=3/p. Este resultado conduz naturalmente à questão de determinar se, ao menos nos casos de empacotamentos associados a reticulados, a densidade local maximal é atingida em domínios de Dirichlet regulares. Para estudar esta questão, perturbamos um polígono regular de 4g lados, domínio de Dirichlet de um grupo isomorfo ao grupo fundamental de uma superfície compacta de genus g e estudamos o comportamento local da função densidade. Para isto, precisamos definir uma projeção adequada no espaço de teichmuller Tg, definida a partir de uma pseudo-homotetia do espaço hiperbólico. Analisamos então as derivadas parciais da constante de pseudo-homotetia como função da perturbação obtendo que, ao menos para uma perturbação restrita a um semi espaço fechado, a função densidade atinge um máximo local no polígono regular. Além disto, obtemos indícios que este é de fato um ponto de máximo. / Abstract: Not informed. / Mestrado / Mestre em Matemática

Orientador: Orlando Lee / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-25T17:05:58Z (GMT). No. of bitstreams: 1 Freitas_LucasIsmailyBezerra_M.pdf: 2067916 bytes, checksum: 77f11deab9d862fe9a10de2df94b447c (MD5) Previous issue date: 2014 / Resumo: Neste trabalho estudamos a conjectura de Tuza, que relaciona cobertura mínima de triângulos por arestas com empacotamento máximo de triângulos aresta-disjuntos em grafos. Em 1981, Tuza conjecturou que para todo grafo, o número máximo de triângulos aresta-disjuntos é no máximo duas vezes o tamanho de uma cobertura mínima de triângulos por arestas. O caso geral da conjectura continua aberta. Contudo, diversas tentativas de prová-la surgiram na literatura, obtendo resultados para várias classes de grafos. Nesta dissertação, nós apresentamos os principais resultados obtidos da conjectura de Tuza. Atualmente, existem várias versões da conjectura. Contudo, ressaltamos que nosso foco está na conjectura aplicada a grafos simples. Apresentamos também uma conjectura que se verificada, implica na veracidade da conjectura de Tuza. Demonstramos ainda que se G é um contra-exemplo mínimo para a conjectura de Tuza, então G é 4-conexo. Deduzimos desse resultado que a conjectura de Tuza é válida para grafos sem minor do K_5 / Abstract: In this thesis we study the conjecture of Tuza, which relates covering of triangles (by edges) with packing of edge-disjoint triangles in graphs. In 1981, Tuza conjectured that for any graph, the maximum number of edge-disjoint triangles is at most twice the size of a minimum cover of triangles by edges. The general case of the conjecture remains open. However, several attempts to prove it appeared in the literature, which contain results for several classes of graphs. In this thesis, we present the main known results for the conjecture of Tuza. Currently, there are several versions of Tuza's conjecture. Nevertheless, we emphasize that our focus is on conjecture applied to simple graphs. We also present a conjecture that, if verified, implies the validity of the conjecture of Tuza. We also show that if G is a mininum counterexample to the conjecture of Tuza, then G is 4-connected. We can deduce from this result that the conjecture of Tuza is valid for graphs with no K_5 minor / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientador : Marcelo Firer / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-04T02:48:30Z (GMT). No. of bitstreams: 1 Faria_MercioBotelho_D.pdf: 4443274 bytes, checksum: 86dda25654f7eb724f654b696016fcf1 (MD5) Previous issue date: 2005 / Resumo: Este trabalho busca elementos para se determinar a densidade de empacotamento de esferas definida por reticulados no plano hiperbólico.Consideramos o espaço de teichmuller Tu de todas as superfícies orientadas com-pactas e fechadas de gênero 9 2: 2, as quais tem o plano hiperbólico como recobrimento universal riemanniano. É conhecido o sistema de coordenadas Fricke em Tu que associa a cada superfície um domínio fundamental de Voronoi-Dirichlet dado por um polígono convexo com 4g arestas. Sabemos que, fixado o gênero, a densidade cresce com o número de arestas do domínio de Voronoi-Dirichlet escolhido, de modo que é natural a busca por polígonos com um número máximo de arestas associado ao gênero dado, que é sempre limitado por 12g - 6.Neste trabalho, determinamos as coordenadas Fricke em Tu que associa a cada su-perfície um domínio de Voronoi-Dirichlet com 4g + 2 e 12g - 6 arestas. Além disso, determinamos e implementamos algoritmos para a determinação dos círculos inscrito e circunscrito de um polígono (em superfícies de curvatura constante). Estes algorit-mos, em sua generalidade tem complexidade O (n4) mas, restringindo os polígonos a vizinhanças abertas de um polígono dado, possui complexidade O (n), situação ótima.A determinação dos domínios de Voronoi-Dirichlet e dos círculos inscritos permitem definir a densidade de empacotamento diretamente nos espaços de teichmuller através de um sistema de equações polinomiais / Abstract: This work searches elements to determine the packing density of spheres defined by lattices in the hyperbolic plane. We consider the teichmüller space Tg of all closed compacts oriented surfaces of genus 9 ~ 2, which has the hyperbolic plane as universal covering rienmannian surface. It is known that the system of Fricke coordinates in Tg associates each surface to a fundamental of Voronoi-Dirichlet domain, given by convex polygon with 49 edges. We know that, with fixed genus, the density increases with the number of edges of the chosen Voronoi-Dirichlet domain. Thus it is naturallooking for polygons with a maximum number of edges associated to a given genus, which is always limited by 129 - 6.In this work, we determine Fricke coordinates in Tg which associates each surface to a Voronoi-Dirichlet domain with 49 + 2 and 129 - 6 edges. Furthermore, we determine and we program the algorithms for determination of the inscribed and circumscribed circles of a polygon (in surfaces of constant curvature). These algorithms, have com-plexity O (n4) , but when restricted to open neighbourhoods of a given polygon, have complexity O (n), best situation.The determination of the Voronoi-Dirichlet domain from the inscribed circles per-mits to define the packing of density directly on teichmüller spaces through a polyno-mials of system equations / Doutorado / Matematica / Doutor em Matemática