21 |
Consultas de segmentos em janelas: algoritmos e estruturas de dados / Windowing queries: algorithms and data structures.Franco, Alvaro Junio Pereira 06 July 2009 (has links)
Neste trabalho estudamos problemas relacionados com a busca de pontos e segmentos em janelas retangulares com os lados paralelos aos eixos. É dado um conjunto de segmentos (ou pontos) no plano. Em uma primeira fase estes segmentos são organizados em estruturas de dados de tal forma a tornar buscas por aqueles que estão contidos em janelas retangulares mais eficiente. Na segunda fase são dadas as janelas de maneira online. Várias destas estruturas de dados são baseadas em árvores balanceadas, tais como, árvore limite, árvore de busca com prioridade, árvore de intervalos e árvore de segmentos. Na dissertação mostramos detalhadamente estas estruturas de dados e os algoritmos para resolver este problema para conjuntos de pontos (versão unidimensional do problema) e para segmentos no plano, tanto horizontais e verticais como com qualquer orientação (sem cruzamentos). Os algoritmos são analisados de forma rigorosa quanto ao seu uso de espaço e de tempo. Implementamos também os vários algoritmos estudados, construindo uma biblioteca destas estruturas de dados. Apresentamos, finalmente os resultados de experimentos computacionais com instâncias do problema. / In this work we study problems about point and segment query in rectangular windows whose edges are parallel to the axis. Given a set of segments (or points) in the plane. In a first phase these segments are organized in data structures such that queries for segments in windows are done more efficiently. In the second phase windows are given online. The data structures are balanced trees as range tree, priority search tree, interval tree and segment tree. In this master\'s thesis we show in details data structures and algorithms for solving windowing queries to sets of points (unidimensional version of the problem) and of segments in the plane, as horizontal and vertical as any orientation (without crossings). The algorithms are analysed rigorously regarding their space and time used. We implement the algorithms studied, building a library of these data structures. Finally, we present, the results of computational experiments with instances of the problem.
|
22 |
Uma proposta para a predi??o computacional da estrutura terci?ria de polipept?deosCardoso, Marcos Borba 12 July 2007 (has links)
Made available in DSpace on 2015-04-14T14:50:25Z (GMT). No. of bitstreams: 1
396435.pdf: 5923930 bytes, checksum: 9836e0a21f7fba5b0893387a40431ee7 (MD5)
Previous issue date: 2007-07-12 / Nos ?ltimos anos, um dos grandes desafios da Ci?ncia da Computa??o perante a Bioinform?tica ? o desenvolvimento de algoritmos, os quais, em um tempo h?bil, consigam gerar as estruturas terci?rias de prote?nas a partir da seq??ncia linear de seus amino?cidos. Embora existam alguns m?todos que consigam gerar estruturas quando se possui outra prote?na com um alto grau de similaridade, quando n?o se possui o mesmo, os m?todos at? ent?o desenvolvidos n?o consigam realizar esta predi??o de forma n?o onerosa computacionalmente. Este trabalho apresenta um algoritmo recursivo capaz de predizer a topologia de polipept?deos, utilizando apenas os ?ngulos da cadeia principal de prote?nas com estruturas tridimensionais (3D) j? conhecidas. O mesmo se mostra eficaz quando aplicado ? mini-prote?na Trp-Cage (c?digo PDB 1L2Y) que possui apenas 20 amino?cidos, tendo uma estrutura predita de RMSD igual 3,7 ?; no entanto, para uma prote?na de 34 amino?cidos Mini-Prote?na Estabilizada por Pontes Dissulfeto (c?digo PDB 1ZDD) o mesmo se mostra ineficiente, gerando a melhor prote?na com o RMSD igual a 7,2 ?, devido ao fato de n?o ter sido percorrido todo o espa?o conformacional esperado para a mesma. Os resultados e as suas conseq??ncias s?o discutidos no trabalho.
|
23 |
[en] SCALABLE TOPOLOGICAL DATA{STRUCTURES FOR 2 AND 3 MANIFOLDS / [pt] ESTRUTURAS DE DADOS TOPOLÓGICAS ESCALONÁVEIS PARA VARIEDADES DE DIMENSÃO 2 E 3MARCOS DE OLIVEIRA LAGE FERREIRA 24 April 2006 (has links)
[pt] Pesquisas na área de estrutura de dados são fundamentais
para aumentar a generalidade e eficiência computacional da
representacão de modelos geometricos. Neste trabalho,
apresentamos duas estruturas de dados topológicas
escalonáveis, uma para superfícies triânguladas, chamada
CHE (Compact Half--Edge), e outra para malhas de
tetraedros, chamada CHF (Compact Half--Face). Tais
estruturas são compostas de diferentes níveis, que nos
possibilitam alterar a quantidade de dados armazenados com
objetivo de melhorar sua eficiência computacional. O uso
de APIs baseadas no conceito de objeto, e de haran»ca de
classes, possibilitam uma interface única para cada função
em todos os níveis das estruturas. A CHE e a CHF requerem
pouca memória e são simples de implementar já que
substituem o uso de ponteiros pelo de contêineres
genéricos e regras aritméticas. / [en] Research in data structure area are essential to increase
the generality and
computational effciency of geometric models`
representation. In this work,
we present two new scalable topological data structures,
one for triangulated
surfaces, called CHE (Compact Half { Edge ), and the
another for tetrahedral
meshes, called CHF (Compact Half { Face ). Such structures
are composed of
different levels, that enable us to modify the amount of
data stored with the
objective to improve its computational effciency. The use
of APIs based in
the object concept and class inheritance, makes possible
an unique interface
for each function at any level. CHE and CHF requires very
few memory and
are simple to implement since they substitute the use of
pointers by generic
containeres and arithmetical rules.
|
24 |
Uso combinado de editor de metadados e árvore hiperbólica para auxílio na recuperação de dados em infraestruturas de dados espaciais: caso de estudo da IDE-CEMIG / Use of thesaurus for help on the data retrieval in spatial data infrastructure: SDI-Cemig study caseMontanari, Marcos Vinícius 28 March 2016 (has links)
Submitted by Reginaldo Soares de Freitas (reginaldo.freitas@ufv.br) on 2016-09-08T16:55:43Z
No. of bitstreams: 1
texto completo.pdf: 1747269 bytes, checksum: bc200b3c7c7bced3b56c994dd82ac3eb (MD5) / Made available in DSpace on 2016-09-08T16:55:43Z (GMT). No. of bitstreams: 1
texto completo.pdf: 1747269 bytes, checksum: bc200b3c7c7bced3b56c994dd82ac3eb (MD5)
Previous issue date: 2016-03-28 / Fundação de Amparo à Pesquisa do Estado de Minas Gerais / O conjunto de informações utilizado para documentar e organizar dados, com o objetivo de minimizar sua redundância e facilitar sua manutenção e obtenção, é denominado metadado. Um mesmo dado acaba sendo, muitas vezes, produzido por diversos produtores de forma isolada. Para tentar evitar a duplicidade de ações e o desperdício de recursos na obtenção de dados espaciais, o governo brasileiro criou a Infraestrutura Nacional de Dados Espaciais (INDE). A INDE tem como objetivo catalogar, integrar e harmonizar os dados geoespaciais produzidos e mantidos pelas diversas instituições governamentais, visando facilitar sua localização, exploração e acesso por qualquer usuário ligado à Internet. Para definir o conjunto estruturado de elementos básicos que retratam as características dos produtos geoespaciais brasileiros, garantindo sua identificação, avaliação e utilização consistente, a Comissão Nacional de Cartografia (CONCAR) criou o Perfil de Metadados Geoespaciais do Brasil (Perfil MGB). Para pesquisar informações dentro de uma Infraestrutura de Dados Espaciais (IDE) é necessário fazer a busca utilizando uma ou mais das seguintes alternativas: palavras-chave; coordenadas espaciais; classificação temática ou período de tempo. Entretanto, muitos usuários podem apresentar dificuldades na busca de dados geoespaciais através de termos específicos, por não terem conhecimento sobre o assunto ou quais critérios deverão ser utilizados na pesquisa. Este trabalho propõe a utilização de uma árvore hiperbólica de termos para a indexação dos metadados, facilitando sua recuperação. Após a indexação, o usuário pode navegar pelos nós da árvore e realizar buscas pelos metadados relacionados com os termos pesquisados. Para ajudar na elaboração de metadados utilizando o perfil MGB foi desenvolvido o edpMGB, que consiste em um editor de metadados classificado como um software livre e está disponibilizado na Web seguindo o modelo de Software como Serviço (SaaS). Este editor foi desenvolvido no SIG corporativo Companhia Energética de Minas Gerais. Os metadados criados por esse editor podem ser validados e indexados aos nós de uma árvore hiperbólica criada para o setor elétrico. / The Information set used to document and organize data, with the objective of minimize its redundancy and obtainment, is called metadata. Different producers can produce a same data many times in an isolated way. To avoid the duplication of efforts and waste of resources, the Brazilian government has created the National Spatial Data Infrastructure (Infraestrutura Nacional de Dados Espaciais - INDE). The INDE aims to catalogue, integrating and harmonizing geospatial data produced and hold by several government institutions, aiming to facilitate its location, exploration and access by any user from Internet. To define the structured set of basic elements that portrays the characteristics of the Brazilian geospatial products, the National Commission of Cartography (Comissão Nacional de Cartografia - CONCAR) has created the Geospatial Metadata Profile of the Brazil (Perfil de Metadados Geoespaciais do Brasil MGB Profile). To search information in a Spatial Data Infrastructure (SDI), it is necessary to search using one or more the following alternatives: keywords, spatial coordinates, thematic classification or periods of time. However, the untrained users may show difficulties in search geospatial data through specific terms, because the user may not have knowledge about the subjects and which criteria will be used in the search. This work proposes the use of a hyperbolic tree of terms to index metadata, helping its retrieval. After the indexing, the user . To help in the metadata creation using the MGB Profile, was developed the edpMGB, which consists a metadata editor, classified as a software open-source, and it is available in the Internet following the model Software as a Service (SaaS). The edpMGB was developed in the research and developm objective is the implantation of a corporate SDI for the Companhia Energética de Minas Gerais (Cemig). The metadata create by the editor can be validated and indexed to the hyperbolic tr nodes, created by the electric system.
|
25 |
Consultas de segmentos em janelas: algoritmos e estruturas de dados / Windowing queries: algorithms and data structures.Alvaro Junio Pereira Franco 06 July 2009 (has links)
Neste trabalho estudamos problemas relacionados com a busca de pontos e segmentos em janelas retangulares com os lados paralelos aos eixos. É dado um conjunto de segmentos (ou pontos) no plano. Em uma primeira fase estes segmentos são organizados em estruturas de dados de tal forma a tornar buscas por aqueles que estão contidos em janelas retangulares mais eficiente. Na segunda fase são dadas as janelas de maneira online. Várias destas estruturas de dados são baseadas em árvores balanceadas, tais como, árvore limite, árvore de busca com prioridade, árvore de intervalos e árvore de segmentos. Na dissertação mostramos detalhadamente estas estruturas de dados e os algoritmos para resolver este problema para conjuntos de pontos (versão unidimensional do problema) e para segmentos no plano, tanto horizontais e verticais como com qualquer orientação (sem cruzamentos). Os algoritmos são analisados de forma rigorosa quanto ao seu uso de espaço e de tempo. Implementamos também os vários algoritmos estudados, construindo uma biblioteca destas estruturas de dados. Apresentamos, finalmente os resultados de experimentos computacionais com instâncias do problema. / In this work we study problems about point and segment query in rectangular windows whose edges are parallel to the axis. Given a set of segments (or points) in the plane. In a first phase these segments are organized in data structures such that queries for segments in windows are done more efficiently. In the second phase windows are given online. The data structures are balanced trees as range tree, priority search tree, interval tree and segment tree. In this master\'s thesis we show in details data structures and algorithms for solving windowing queries to sets of points (unidimensional version of the problem) and of segments in the plane, as horizontal and vertical as any orientation (without crossings). The algorithms are analysed rigorously regarding their space and time used. We implement the algorithms studied, building a library of these data structures. Finally, we present, the results of computational experiments with instances of the problem.
|
26 |
[en] DATA STRUCTURES FOR TIME SERIES / [pt] ESTRUTURAS DE DADOS PARA SERIES TEMPORAISCAIO DIAS VALENTIM 24 April 2013 (has links)
[pt] Séries temporais são ferramentas importantes para análise de eventos que ocorrem em diferentes domínios do conhecimento humano, como medicina, física, meteorologia e finanças. Uma tarefa comum na análise de séries temporais é a busca por eventos pouco frequentes que refletem fatos de interesse sobre o domínio de origem da série. Neste trabalho, buscamos desenvolver técnicas para detecção de eventos raros em séries temporais. Formalmente, uma série temporal A igual a (a1, a2,..., an) é uma sequência de valores reais indexados por números inteiros de 1 a n. Dados dois números, um inteiro t e um real d, dizemos que um par de índices i e j formam um evento-(t, d) em A se, e somente se, 0 menor que j - i menor ou igual a t e aj - ai maior ou igual a d. Nesse caso, i é o início do evento e j o fim. Os parâmetros t e d servem para controlar, respectivamente, a janela de tempo em que o evento pode ocorrer e a
magnitude da variação na série. Assim, nos concentramos em dois tipos de perguntas relacionadas aos eventos-(t, d), são elas: - Quais são os eventos-(t, d) em uma série A? - Quais são os índices da série A que participam como inícios de ao menos um evento-(t, d)? Ao longo desse trabalho estudamos, do ponto de vista prático e teórico, diversas estruturas de dados e algoritmos para responder às duas perguntas
listadas. / [en] Time series are important tools for the anaylsis of events that occur in different fields of human knowledge such as medicine, physics, meteorology and finance. A common task in analysing time series is to try to find events that happen infrequently as these events usually reflect facts of interest about the domain of the series. In this study, we develop techniques for the detection of rare events in time series. Technically, a time series A equal to (a1, a2,..., an) is a sequence of real values indexed by integer numbers from 1 to n. Given an integer t and a real number d, we say that a pair of time indexes i and j is a (t, d)-event in A, if and only if 0 less than j - i less than or equal to t and aj - ai greater than or equal to d. In this case, i is said to be the beginning of the event and j is its end. The parameters t and d control, respectively, the time window in which the event can occur and magnitude of the variation in the series. Thus, we focus on two types of queries related to the (t, d)-events, which are: - What are the (t, d)-events in a series A? - What are the indexes in the series A which are the beginning of at least one (t, d)-event? Throughout this study we discuss, from both theoretical and practical points of view, several data structures and algorithms to answer the two queries mentioned above.
|
27 |
A data structure for spanning tree optimization problems / Uma estrutura de dados para problemas de otimização de árvores geradorasBarbosa, Marco Aurélio Lopes 17 June 2019 (has links)
Spanning tree optimization problems are related to many practical applications. Several of these problems are NP-Hard, which limits the utility of exact methods and can require alternative approaches, like metaheuristics. A common issue for many metaheuristics is the data structure used to represent and manipulate the solutions. A data structure with efficient operations can expand the usefulness of a method by allowing larger instances to be solved in a reasonable amount of time. We propose the 2LETT data structure and uses it to represent spanning trees in two metaheuristics: mutation-based evolutionary algorithms and local search algorithms. The main operation of 2LETT is the exchange of one edge in the represented tree by another one, and it has O(√n) time, where n is the number of vertices in the tree. We conducent qualitative and quantitative evaluations for 2LETT and other structures in the literature. For the main operation of edge exchange in evolutionary algorithms, the computational experiments show that 2LETT has the best performance for trees with more than 10,000 vertices. For local search algorithms, 2LETT is the best option to deal with large trees with large diameters. / Os problemas de otimização de árvores geradoras estão relacionados a muitas aplicações práticas. Vários desses problemas são NP-difícies, o que limita a utilidade de métodos exatos e pode exigir abordagens alternativas, como metaheurísticas. Um questão relevante para muitas metaheurísticas é a estrutura de dados usada para representar e manipular as soluções. Uma estrutura de dados com operações eficientes pode aumentar a utilidade de um método, permitindo que instâncias maiores sejam resolvidas em um período de tempo razoável. Propomos a estrutura de dados 2LETT e a usamos para representar árvores geradoras em duas metaheurísticas: algoritmos evolutivos baseados em mutações e algoritmos de busca local. A operação principal da 2LETT é a troca de uma aresta na árvore representada por outra aresta. Esta operação tem tempo de O(√n), onde n é o número de vértices na árvore. Conduzimos avaliações qualitativas e quantitativas para 2LETT e outras estruturas na literatura. Para a principal operação de troca de arestas em algoritmos evolutivos, os experimentos computacionais mostram que a 2LETT possui o melhor desempenho para árvores com mais de 10.000 vértices. Para algoritmos de busca local, o 2LETT é a melhor opção para lidar com árvores grandes com grandes diâmetros.
|
28 |
Árvores de Ukkonen: caracterização combinatória e aplicações / Ukkonen\'s tree: combinatorial characterization and applicationsSacomoto, Gustavo Akio Tominaga 08 February 2011 (has links)
A árvore de sufixos é uma estrutura dados, que representa em espaço linear todos os fatores de uma palavra, com diversos exemplos de aplicações práticas. Neste trabalho, definimos uma estrutura mais geral: a árvore de Ukkonen. Provamos para ela diversas propriedades combinatórias, dentre quais, a minimalidade em um sentido preciso. Acreditamos que a apresentação aqui oferecida, além de mais geral que as árvores de sufixo, tem a vantagem de oferecer uma descrição explícita da topologia da árvore, de seus vértices, arestas e rótulos, o que não vimos em nenhum outro trabalho. Como aplicações, apresentamos também a árvore esparsa de sufixos (que armazena apenas um subconjunto dos sufixos) e a árvore de k-fatores (que armazena apenas os segmentos de comprimento k, ao invés dos sufixos) definidas como casos particulares das árvores de Ukkonen. Propomos para as árvores esparsas um novo algoritmo de construção com tempo O(n) e espaço O(m), onde n é tamanho da palavra e m é número de sufixos. Para as árvores de k-fatores, propomos um novo algoritmo online com tempo e espaço O(n), onde n é o tamanho da palavra. / The suffix tree is a data structure that represents, in linear space, all factors of a given word, with several examples of practical applications. In this work, we define a more general structure: the Ukkonen\'s tree. We prove many properties for it, among them, its minimality in a precise sense. We believe that this presentation, besides being more general than the suffix trees, has the advantage of offering an explicit description of the tree topology, its vertices, edges and labels, which was not seen in any other work. As applications, we also presents the sparse suffix tree (which stores only a subset of the suffixes) and the k-factor tree (which stores only the substrings of length k, instead of the suffixes), both defined as Ukkonen\'s tree special cases. We propose a new construction algorithm for the sparse suffix trees with time O(n) and space O(m), where n is the size of the word and m is the number of suffixes. For the k-factor trees, we propose a new online algorithm with time and space O(n), where n is the size of the word.
|
29 |
[en] BOOLEAN OPERATIONS WITH COMPOUND SOLIDS REPRESENTED BY BOUNDARY / [pt] OPERAÇÕES BOOLEANAS COM SÓLIDOS COMPOSTOS REPRESENTADOS POR FRONTEIRAMARCOS CHATAIGNIER DE ARRUDA 13 July 2005 (has links)
[pt] Num modelador de sólidos, uma das ferramentas mais
poderosas para a
criação de objetos tridimensionais de qualquer nível de
complexidade geométrica
é a aplicação das operações booleanas. Elas são formas
intuitivas e populares
de combinar sólidos, baseadas nas operações aplicadas a
conjuntos. Os tipos
principais de operações booleanas comumente aplicadas a
sólidos são: união,
interseção e diferença. Havendo interesse prático, para
garantir que os objetos
resultantes possuam a mesma dimensão dos objetos originais,
sem partes soltas
ou pendentes, o processo de regularização é aplicado.
Regularizar significa
restringir o resultado de tal forma que apenas volumes
preenchíveis possam
existir. Na prática, a regularização é realizada
classificando-se os elementos
topológicos e eliminando-se estruturas de dimensão
inferior. A proposta deste
trabalho é o desenvolvimento de um algoritmo genérico que
permita a aplicação
do conjunto de operações booleanas em um ambiente de
modelagem
geométrica aplicada à análise por elementos finitos e que
agregue as seguintes
funcionalidades: trabalhar com um número indefinido de
entidades topológicas
(conceito de Grupo), trabalhar com objetos de dimensões
diferentes, trabalhar
com objetos non-manifold, trabalhar com objetos não
necessariamente poliedrais
ou planos e garantir a eficiência, robustez e
aplicabilidade em qualquer ambiente
de modelagem baseado em representação B-Rep. Neste
contexto, apresenta-se
a implementação do algoritmo num modelador geométrico pré-
existente,
denominado MG, seguindo o conceito de programação orientada
a objetos e
mantendo a interface com o usuário simples e eficiente. / [en] In a solid modeler, one of the most powerful tools to
create threedimensional
objects with any level of geometric complexity is the
application of
the Boolean set operations. They are intuitive and popular
ways to combine
solids, based on the operations applied to sets. The main
types of Boolean
operations commonly applied to solids are: union,
intersection and difference. If
there is practical interest, in order to assure that the
resulting objects have the
same dimension of the original objects, without loose or
dangling parts, the
regularization process is applied. To regularize means to
restrict the result in a
way that only filling volumes are allowed. In practice, the
regularization is
performed classifying the topological elements and removing
the lower
dimensional structures. The objective of this work is the
development of a generic
algorithm that allows the application of the Boolean set
operations in a geometric
modeling environment applied to finite element analysis,
which aggregates the
following functionalities: working with an undefined number
of topological entities
(Group concept), working with objects of different
dimensions, working with nonmanifold
objects, working with objects not necessarily plane or
polyhedrical and
assuring the efficiency, robustness and applicability in
any modeling environment
based on B-Rep representation. In this context, the
implementation of the
algorithm in a pre-existing geometric modeler named MG is
presented, using the
concept of object oriented programming and keeping the user
interface simple
and efficient.
|
30 |
[en] SHELL MODELING WITH PARAMETRIC INTERSECTION / [pt] MODELAGEM DE CASCAS COM INTERSEÇÕES PARAMÉTRICASLUIZ CRISTOVAO GOMES COELHO 26 July 2002 (has links)
[pt] Apresenta-se uma metodologia para modelagem de cascas para elementos finitos definidas em
superfícies paramétricas. A metodologia consiste na criação de curvas e geração de malhas sobre
os retalhos paramétricos constru´ıdos com base nestas curvas, que também são usadas para a conexão
de malhas adjacentes. O modelo final é uma representação de todas as malhas combinadas
em uma única estrutura de dados.
As ferramentas básicas para geração de tais malhas são uma interface para modelagem de
curvas espaciais e os algoritmos geom´etricos para construcão de mapeamentos nos domínios
elementares. O problema central em modelagens compostas é o tratamento dado às malhas
em superfícies que se interceptam. Um algoritmo capaz de modelar com precisão as curvas
de interseção e de ajustar as duas malhas para as novas restrições geradas é apresentado neste trabalho.
O algoritmo é parte de um programa completo para modelagem interativa de cascas, que
tem sido usado no projeto de grandes sistemas flutuantes para explotação de petróleo em águas
profundas. O uso de uma variante da estrutura de dados DCEL, que usa árvores de ordenação
espacial para armazenar as entidades topol´ogicas ao invés de listas ou vetores, permite que malhas bastante refinadas sejam reconstru´ıdas em tempo compatível com o trabalho interativo. Estas
árvores aceleram os cálculos de interseção necessários à determinação dos pontos de interpolação
das curvas de trimming, permitindo tamb´em a reconstrução das malhas usando-se apenas consultas
locais. / [en] We present a methodology for modeling finite-element
meshes defined on parametric surface
patches. The idea is to build curves and generate meshes
over the parametric patches built with
these curves, which also connect adjacent meshes. The
final model is a representation of all
meshes combined into a single data structure.
The basic tools to generate such meshes are the user
interface to model space curves and
the geometric algorithms to construct the elementary
domain mappings. The main problem in
composite modeling is how to handle mesh surfaces that
intersect each other. We present an
algorithm that models the intersection curves precisely
and adjusts both meshes to the newly
formed borders. The algorithm is part of an interactive
shell modeling program, which has been
used in the design of large offshore oil structures. We
avoid unacceptable interaction delays by
using a variant of the DCEL data structure that stores
topological entities in spatial indexing trees
instead of linked lists. These trees speed up the
intersection computations required to determine
points of the trimming curves, and also allows mesh
reconstruction using only local queries.
|
Page generated in 0.0461 seconds