Spelling suggestions: "subject:"árvores""
31 |
Revisão de modelos CTL / CTL Model RevisionOliveira, Paulo de Tarso Guerra 16 December 2010 (has links)
Verificação de modelos é uma das mais eficientes técnicas de verificação automática de sistemas. No entanto, apesar de poder lidar com verificações complexas, as ferramentas de verificação de modelos usualmente não fornecem informação alguma sobre como reparar inconsistências nestes modelos. Nesta dissertação, mostramos que abordagens desenvolvidas para a atualização de modelos CTL inconsistentes não são capazes de lidar com todos os tipos de alterações em modelos. Introduzimos então o conceito de revisão de modelos: uma abordagem baseada em revisão de crenças para o reparo de modelos inconsistentes em um contexto estático. Relacionamos nossa proposta com trabalhos clássicos em revisão de crenças. Definimos um operador de revisão de modelos e mostramos que este obedece postulados de racionalidade clássico de revisão de crenças. Propomos um algoritmo de revisão com base no algoritmo utilizado pela abordagem de atualização de modelos. Discutimos sobre problemas e limites do algoritmo proposto, e mostramos que essa estratégia de adaptação não é uma solução apropriada. / Model checking is one of the most robust techniques in automated system verification. But, although this technique can handle complex verifications, model checking tools usually do not give any information on how to repair inconsistent system models. In this dissertation, we show that approaches developed for CTL model update cannot deal with all kinds of model changes. We introduce the concept of CTL model revision: an approach based on belief revision to handle system inconsistency in a static context. We relate our proposal to classical works on belief revision. We define an operator for model revision and we show that it obeys the classical rationality postulates of belief revision. We propose an algorithm for model revision based on the algorithm used by the model update approach. We discuss problems and limitations of our proposed algorithm and show that this strategy of adaptation is not an appropriate solution.
|
32 |
DBM-tree: método de acesso métrico sensível à densidade local / DBM-tree: metric access method sensitive to local density dataVieira, Marcos Rodrigues 28 May 2004 (has links)
Um espaço métrico é definido por um conjunto de objetos e uma função de distância métrica, que é utilizada para avaliar o nível de similaridade entre estes objetos. Isto permite a elaboração de Métodos de Acesso Métricos (MAMs) capazes de responder consultas por similaridade nesses conjuntos em um tempo reduzido. Em geral, esses MAMs são materializados através de uma estrutura hierárquica chamada de árvore métrica. Normalmente essas árvores são mantidas balanceadas, pois isto tende a manter a altura da árvore mínima, reduzindo o número de acessos a disco necessários para responder às consultas. No entanto, é difícil manter as estruturas balanceadas sem a existência de sobreposição entre os nós que cobrem regiões de alta densidade de objetos. O efeito disto é a degradação do tempo das consultas, pois várias subárvores devem ser analisadas para compor as consultas. Em outras palavras, minimizar a sobreposição entre os nós aumenta a eficiência das árvores métricas. Um meio efetivo para isto é flexibilizar o balanceamento das árvores métricas. Este trabalho apresenta um novo MAM dinâmico, chamado de DBM-tree (Density-Based Metric tree), que permite flexibilizar o balanceamento da estrutura, minimizando o grau de sobreposição entre os nós em regiões densas e, conseqüentemente, aumentando o seu desempenho para responder às consultas. Essa flexibilização é ajustada pelo usuário e é rigidamente controlada pela estrutura. A profundidade da árvore é maior em regiões de alta densidade, procurando um equilíbrio entre o número de acessos a disco para avaliar múltiplas subárvores e para a busca em profundidade em cada subárvore. A DBM-tree possui um algoritmo de otimização chamado de DBM-Slim-Down, que melhora o desempenho das árvores através da reorganização de elementos entre os seus nós. Os experimentos feitos com dados reais e sintéticos mostram que a DBM-tree supera em desempenho os MAMs tradicionais. Ela é, em média, 50% mais rápida que os MAMs tradicionais e reduz o número de acessos a disco e cálculos de distância em até 50%. Depois de executado o algoritmo DBM-Slim-Down, o seu desempenho melhorou em até 30% para as consultas por abrangência e aos vizinhos mais próximos. Ainda, a DBM-tree é escalável considerando tempo total de processamento, número de acessos a disco e de cálculos de distância em relação ao tamanho do conjunto de dados indexado. / A metric space is defined as a set of objects and a metric distance function that is used to measure the similarity between these objects. It allows the development of Metric Access Methods (MAMs) that are able to answer similarity queries in these datasets quickly. Usually these MAMs are materialized through a hierarchical structure called metric trees. These trees are kept balanced because it tends to maintain the height of the tree small, aiming to reduce the number of disk access required to answer queries. However, it is difficult to maintain the tree balanced without overlapping nodes covering a large number of objects, leading to the degradation of query performance. In other words, reducing the overlap among nodes increases the performance of metric trees. A possible solution is to relax the need to keep metric trees balanced. This work presents a new dynamic MAM called DBM-tree (Density-Based Metric tree), which changes the rule that imposes a rigid balancing policy, allowing a small amount of unbalancing in some regions of it. This unbalancing minimizes the degree of overlapping among some high-density nodes and, consequently, increases query answering performance. The amount of relaxation is set by the user and is strongly enforced in the tree. The height of the tree is higher in high-density regions, in order to keep a balance between searching in various subtrees and searching deeply in each subtree. The DBM-tree has an optimization algorithm called DBM-Slim-Down that improves the performance in trees through reorganizing the elements among its nodes. The experiments performed over synthetic and real-world datasets showed that the DBM-tree outperforms the traditional MAMs. The DBM-tree is, in average, 50% faster than traditional MAMs and reduces the number of distance calculations and disk accesses up to 50%. After executing the DBM-Slim-Down algorithm, the performance achieves improvements up to 30% for range and k-nearest neighbor queries. Moreover, the DBM-tree is scalable regarding time, number of disk accesses and distance calculations.
|
33 |
Explorando técnicas para modelagem de dados agregados de óbitos provenientes de acidentes por automóvel / Exploring techniques for modeling of aggregates data from deaths automobile accidentsSantos, Murilo Castanho dos 01 October 2015 (has links)
Esta dissertação se baseia na exploração de técnicas para modelagem de óbitos provenientes de acidentes por automóvel no estado de São Paulo. A análise foi agregada por área, e utilizou a razão de óbitos por população, por área e por fluxo veicular como variáveis dependentes e as variáveis independentes foram características socioeconômicas, área, frota de veículos, IDHM, fluxo veicular anual e distâncias entre microrregiões. Os dados do ano 2000 foram utilizados na calibração e dados de 2010 na validação dos modelos, com a técnica de mineração de dados (algoritmos de Árvore de Decisão - AD: CART - Classification And Regression Tree e CHAID - Chi-squared Automatic Interaction Detection) e Regressão Linear Múltipla (RLM) para fins comparativos com os modelos de AD. A partir dos resultados verifica-se que a RLM foi a técnica que obteve melhores erro médio, erro médio absoluto e coeficiente de correlação, e o algoritmo CART da AD o menor erro médio normalizado. Ao comparar as taxas de óbitos, a relação por área apresentou melhor erro médio e coeficiente de correlação, já a relação por população obteve menor erro médio normalizado e erro médio absoluto. Vale ressaltar que os algoritmos de AD são técnicas adequadas para classificação de áreas segundo faixas de valores de variáveis explicativas e valores médios da variável objeto de estudo. Além disso, tais técnicas são mais flexíveis em relação a alguns pressupostos de modelos de regressão. Dessa forma, a principal contribuição deste trabalho consiste na exploração de tais algoritmos para previsão de acidentes e classificação de regiões. / This dissertation is based on techniques exploration for modeling of deaths from automobile accidents on the state of São Paulo. The analysis was aggregated by area, and used the ratio of deaths per population, by area and by vehicle flow as dependent variables and the independent variables were socioeconomic characteristics, area, vehicle fleet, Municipal Human Development Index (MHDI), annual vehicle flow and distances between micro-regions. The 2000 data were used for calibration and 2010 data to validate the models with data mining technique (decision tree - DT algorithms: CART - Classification And Regression Tree and CHAID - Chi-squared Automatic Interaction Detection) and Multiple Linear Regression (MLR) for comparative purposes with the DT models. From the results it appears that the RLM was the technique that achieved better mean error, mean absolute error and correlation coefficient values, while the CART algorithm presented the lowest value of mean normalized error. When comparing death rates, a relation by area showed better mean error and correlation coefficient values, as the ratio by population had lower mean normalized error and mean absolute error values. It is noteworthy that the DT algorithms are suitable techniques for classification of areas in accordance with explanatory variables of value ranges and average values of the variable object of study. Furthermore, such techniques are more flexible compared to some assumptions regression models. Thus, the main contribution of this study is the exploration of such algorithms for prediction of accidents and regions classification.
|
34 |
Algoritmos para o problema da árvore de Steiner com coleta de prêmios / Algorithms for prize-collecting Steiner tree problemMatsubara, Camila Mari 14 December 2012 (has links)
Neste projeto estudamos algoritmos de aproximação para o problema da árvore de Steiner com coleta de prêmios. Trata-se de uma generalização do problema da árvore de Steiner, onde é dado um grafo com custos positivos nas arestas e penalidades positivas nos vértices. O objetivo é encontrar uma subárvore do grafo que minimize a soma dos custos das arestas mais a soma das penalidades dos vértices que não pertencem à subárvore. Em 2009, os autores Archer, Bateni, Hajiaghayi e Karloff obtiveram pela primeira vez um algoritmo com fator de aproximação estritamente menor do que 2. Além de analisarmos este algoritmo, estudamos também a implementação de algoritmos 2-aproximação para o problema da árvore de Steiner e da árvore de Steiner com coleta de prêmios. / In this project we analyze approximation algorithms for the prize-collecting Steiner tree problem. This is a generalization of the Steiner tree problem, in which it is given a graph with positive costs in edges and positive penalties in vertices. The goal is to find a subtree of the graph that minimizes the sum of costs of edges plus the sum of the penalties of the vertices that don\'t belong to the subtree. In 2009, the authors Archer, Bateni, Hajiaghayi e Karloff described, for the first time an algorithm with approximation factor strictly less than 2. Besides analyzing this algorithm, we also study the implementation of 2-approximation algorithms to the Steiner tree problem and prize-collecting Steiner tree problem.
|
35 |
Modelo para tomada de decisão na escolha de sistema de tratamento de esgoto sanitário / A decision making model for choosing sewage treatment systemsOliveira, Sonia Valle Walter Borges de 10 November 2004 (has links)
A escolha do sistema de tratamento de esgoto sanitário a ser instalado em uma cidade pode tornar-se uma difícil decisão, uma vez que diversas variáveis interferem em seu custo e em sua qualidade ambiental. Este trabalho pretende mostrar a possibilidade de se usar técnicas da análise de decisão para a escolha do sistema de tratamento de esgoto sanitário de forma ecológica e econômica, como árvore de decisão e análise de sensibilidade. Para a avaliação dos sistemas, foi desenvolvido um modelo com oito alternativas, compostas de processos biológicos anaeróbios Reator Anaeróbio de Manta de Lodo e Lagoa Anaeróbia seguidos de aeróbios Lodos Ativados, Lagoa Facultativa, Filtro Biológico Percolador e Lagoa Aerada com Lagoa de Decantação. O modelo elabora o dimensionamento das unidades de tratamento e, a partir desses dados, a estimativa de custo de cada sistema. O custo total de cada alternativa foi composto por itens de implantação, operação e manutenção. O modelo foi avaliado para quatro casos de populações distintas, apresentando variação nas alternativas mais indicadas para cada um. A análise de sensibilidade se mostrou eficaz em identificar as alternativas mais significativas no custo total dos sistemas. Os resultados encontrados indicam, de maneira promissora, que o modelo poderá auxiliar a escolha de sistemas de tratamento, bem como seu pré-dimensionamento, com base em características peculiares à sua localidade. / The selection of the wastewater treatment system to be installed in a city can be a difficult decision, once several variables interfere in its cost and in its environmental quality. This study intends to show the possibility of using techniques of decision analysis to select the wastewater treatment system in an ecological and economical way, as decision tree and sensitivity analysis. For the evaluation of systems, a model was developed with eight alternatives, composed of anaerobic biological process - Upflow Anaerobic Sludge Blanket and Anaerobic Pond - followed by aerobic process Activated-Sludge, Facultative Pond, Trickling Filter and Aerated Lagoon with Sedimentation Basin. The model elaborates the treatment units dimensioning and cost estimation of each system, based on dimensioning data. The total cost of each alternative was composed by construction, operation and maintenance items. The model was evaluated using four cases of different populations, presenting variation in the most suitable alternatives for each one. The sensitivity analysis was shown effective in identifying the most significant alternatives in the total cost of the systems. The results indicate, in a promising way , that the model will be able to help the choice of treatment systems, as well as its pre-dimensioning, based in local peculiar characteristics.
|
36 |
Montagem de novo do transcriptoma de teca (Tectona grandis L. f.) e busca por genes relacionados ao estresse hídrico / De novo assembly of teak (Tectona grandis L. f.) transcriptome and search for water-stress related genesVasconcelos, Tarcisio Sales 22 May 2015 (has links)
A teca é uma árvore de grande importância comercial pelas características de cor e durabilidade de sua madeira. Devido a sua rusticidade e fácil adaptação ao clima, plantios de teca tornam-se cada vez mais atrativos ao redor do mundo. Contudo, esta espécie apresenta escassez de estudos genéticos moleculares a respeito tanto de sua madeira, quanto de sua tolerância às variações ambientais. Uma vez que o transcriptoma pode apresentar grande quantidade de informação a respeito dos genes expressos por um conjunto celular, neste trabalho foi realizado o primeiro transcriptoma de teca, onde foram sequenciadas flores, folhas, raízes e seedlings pela tecnologia Illumina. A montagem do transcriptoma foi realizada com o programa Trinity acima de 100 milhões de reads e gerou mais de 400 mil contigs, os quais tiveram as anotações funcionais adquiridas com o programa Blas2GO. 51% dos contigs foram anotados, mostrando alta similaridade com as espécies Vitis vinifera e Solanum licopersicum; destes, 78% obtiveram anotações funcionais com o Gene Ontology, totalizando 5.165 termos para Processo Biológico, 2.846 termos para Função Molecular e 742 para Componente Celular. A expressão diferencial foi obtida com o programa edgeR a 5% de probabilidade de erro e mostrou que, para 187.315 contigs montados através da fusão de todas as bibliotecas sequenciadas, 18 mostraram expressão diferencial para flor, 14 para folha, 13 para raiz e 29 para seedling. Após a etapa de caracterização do transcriptoma, foi realizado um experimento de estresse por déficit hídrico em casa-de-vegetação, onde plantas de teca foram submetidas a estresse Moderado (40% de água no substrato por 20 dias), estresse Severo (20 a 40% de água por 30 dias) e tratamento controle (substrato saturado). As medições através de analisador de gases por infravermelho (IRGA) mostraram queda na fotossíntese (até 70% a menos do que o controle), na transpiração (até 77%) e na condutância estomática (até 85%) entre os tratamentos; além disto, o conteúdo relativo de água foliar caiu 13% entre o tratamento severo e o controle, e níveis de prolina livre foram até 3,5 vezes mais altos nos tratamentos de estresse. A temperatura foliar aumentou significativamente com o aumento da irradiância de fótons aplicada. A busca por genes relacionados ao estresse por déficit hídrico na biblioteca de transcritos de Raiz retornou 1.145 sequências, e destas, 4 foram caracterizadas: TgTPS (trealose 6-fosfato sintase), TgPIP (aquaporina, proteína intrínseca de membrana plasmática), TgDREB2 (proteína de ligação a elemento responsivo a desidratação) e TgAREB (proteína de ligação a elemento responsivo a ácido abscísico). Apenas TgTPS, TgPIP e TgDREB2 mostraram alto grau de conservação entre as espécies, podendo ser corretamente amplificadas via PCR e validadas por sequenciamento. Assim, com o banco de dados de transcritos obtido pelo RNA-seq, foi possível identificar genes candidatos ao estudo de características vegetativas e reprodutivas de teca, contribuindo para entender os mecanismos moleculares desta espécie florestal. / Teak is a tree of great commercial importance by the characteristics of color and durability of its wood. Due to its hardiness and easy adaptation to climate, teak plantations become increasingly attractive around the world. However, this species has a lack of molecular genetic studies on both of its wood, as their tolerance to environmental variations. Once the transcriptome can provide lots of information about the genes expressed by a cell group, this work represents the first transcriptome teak, which were sequenced flowers, leaves, roots and seedlings by Illumina technology. The transcriptome assembly was performed with Trinity program above 100 million reads and generated more than 400,000 contigs, which have acquired the functional annotations with Blas2GO program. 51% of the contigs were annotaded, showing high similarity to Vitis vinifera and Solanum licopersicum; of these, 78% had functional annotations with the Gene Ontology, totaling 5,165 terms for Biological Process, 2846 terms for Molecular Function and 742 for Cell Component. The differential expression was obtained with the edgeR program at 5% probability of error and showed that for 187,315 contigs assembled by merging all sequenced libraries, 18 showed differential expression to flower, 14 to leaf, 13 to root and 29 for seedling. After this step of characterization of the transcriptome, we performed a stress experiment by water deficit at greenhouse, where teak plants were subjected to Moderate stress (40% of water in the substrate for 20 days), Severe stress (20 to 40% water for 30 days) and control treatment (saturated substrate). Measurements by infrared gas analyzer (IRGA) showed a decrease in photosynthesis (up to 70% less than the control), transpiration (up 77%) and stomatal conductance (up 85%) between treatments; furthermore, leaf relative water content dropped 13% between the treatment control and severe, and free proline levels were up to 3.5 fold greater in stress treatments. The leaf temperature increased significantly with increasing irradiance of photons applied. The search for genes related to stress by water deficit in the root transcripts library returned 1,145 sequences, and these, 4 were characterized: TgTPS (trehalose 6-phosphate synthase), TgPIP (aquaporin, protein intrinsic of plasma membrane), TgDREB2 (dehydration responsive element binding protein) and TgAREB (abscisic acid responsive element binding protein). Only TgTPS, TgPIP and TgDREB2 showed a high degree of conservation between species, and can be properly amplified by PCR and validated by sequencing. Thus, with the database of transcripts obtained by RNA-seq, candidate genes were identified for the study of vegetative and reproductive characteristics teak, helping to understand the molecular mechanisms of this forest species.
|
37 |
Avaliação do processo de adensamento de resíduos de poda de árvore visando ao aproveitamento energético: o caso do campus da USP na capital / Assessment of densification process of tree pruning waste aimed at energy use: the case of Campus of USP in CapitalSilva, Dafne Pereira da 23 September 2016 (has links)
Os resíduos sólidos urbanos (RSU) são particularmente difíceis de gerenciar por se tratar de um resíduo muito heterogêneo em sua composição (resíduos domésticos, de construção civil, de poda de árvore, entre outros). Com isso torna-se necessário o conhecimento das atuais tecnologias de tratamento de resíduos, para que busquem soluções ambientalmente adequadas, economicamente viáveis, socialmente justas e politicamente aceitáveis. Com base nessa premissa e com a necessidade de se estudar novas fontes renováveis de energia na busca por combustíveis alternativos aos combustíveis fósseis, a utilização de resíduos de poda de árvore como fonte energética apresenta aspectos benéficos ao país, desde que viável econômica e tecnicamente. Assim este trabalho analisa a atual situação da destinação dos resíduos de poda de árvore, e apresenta algumas alternativas para seu aproveitamento energético e não energético. Sendo o objetivo principal desta dissertação avaliar o potencial de utilização dos resíduos de poda de árvore para o seu aproveitamento energético por meio dos processos de adensamento de biomassa (peletização e briquetagem), utilizando como base o caso do campus da Universidade de São Paulo na capital. Nos ensaios de peletização foi possível obter pellets com densidade energética elevada, entre 6 GJ/m3 e 8 GJ/m3, o que corresponde a uma densidade energética de 6 a 9 vezes maior que a da poda de árvore in natura. Os briquetes apresentaram uma densidade energética entre 5 GJ/m3 a 6 GJ/m3, ou seja, uma densidade energética de 5 a 6 vezes maior que da poda de árvore in natura. Entretanto os valores obtidos de durabilidade mecânica dos briquetes foram considerados insatisfatórios nas condições estudadas, ao contrário dos pellets, que apresentaram elevados valores. Neste estudo o processo de peletização se mostrou mais viável tecnicamente do que o de briquetagem, visto que os pellets de resíduo de poda de árvore garantiram uma densidade energética elevada e boa resistência mecânica. / Municipal solid wastes (MSW) are particularly difficult to manage because it is a very heterogeneous waste in its composition (household waste, construction, tree pruning, etc). It becomes more than necessary knowledge of current waste treatment technologies, to seek environmentally adequate solutions, economically viable, socially fair and politically acceptable. Based on these assumptions and the need to study new renewable energy sources in the search for alternative fuels to replace fossil fuels, the use of tree pruning waste as an energy source have beneficial aspects to the country, since economic viable and technically. So this paper analyzes the current situation of final disposal of tree pruning waste, and presents some alternatives for its energy and non-energy use. Since the main objective of this work is to evaluate the potential use of tree pruning waste for their energy application through biomass densification processes (pelletizing and briquetting), based on the case of the campus of the University of São Paulo in capital. In the pelleting tests it was possible to obtain pellets with high energy density between 6 GJ/m3 and 8 GJ/m3, which corresponds to an energy density of 6 to 9 times greater than that of tree pruning in nature. The briquettes had an energy density of between 5 GJ/m3 6 GJ/m3, in other words a power density of 5 to 6 times that of tree pruning in nature. However the values obtained from mechanical durability of briquettes were found to be unsatisfactory under the conditions studied, unlike pellets, they showed high values. In this study, the pelleting process is technically more feasible than briquetting. Since the tree pruning waste pellets ensured a high energy density and good mechanical strength.
|
38 |
Grafos e hipergrafos com cintura e número cromático grandes / Graphs and hypergraphs with high girth and high chromatic numberMaesaka, Giulia Satiko 08 June 2018 (has links)
A demonstração feita por Erdos da existência de grafos com cintura e número cromático grandes é uma das primeiras aplicações do método probabilístico. Essa demonstração fornece um limite para o número de vértices de um grafo desse tipo, que é exponencial na cintura quando o número cromático é fixado. O foco deste texto, no entanto, são as construções determinísticas de grafos com cintura e número cromático grandes e os números de vértices dos grafos obtidos. As construções elementares conhecidas fornecem apenas grafos com um número Ackermanniano de vértices. O texto começa com uma breve repetição das demonstrações probabilísticas da existência de grafos e hipergrafos com cintura e número cromático grandes. Depois, a busca por construções determinísticas é motivada apresentando-se algumas construções para o caso particular de grafos livres de triângulo e com número cromático grande. São construídos os grafos de Tutte, Zykov, Mycielski e Kneser, os grafos de shift e os de planos projetivos finitos. Os números de vértices dessas construções são computados e comparados. De fato, a construção a partir de planos projetivos finitos tem um número polinomial de vértices. A parte principal do texto são as construções de grafos e hipergrafos com cintura e número cromático grandes. A primeira construção apresentada foi feita por Kriz. Ela foi a primeira construção para grafos com cintura e número cromático grandes que não envolvia hipergrafos. A segunda construção apresentada foi feita por Nesetril e Rödl. Essa construção antecede a de Kriz. Ela utiliza a amalgamação entre grafos e hipergrafos para obter um hipergrafo uniforme com cintura e número cromático grandes. A terceira e última construção apresentada foi encontrada por Alon, Kostochka, Reiniger, West e Zhu. Essa construção consegue obter hipergrafos uniformes com cintura e número cromático grandes diretamente a partir de um grafo, que é uma certa árvore aumentada. Em particular, essa construção obtém grafos com cintura e número cromático grandes sem envolver hipergrafos. Os números de vértices dos hipergrafos obtidos por essas construções são computados e comparados. / The proof by Erdos of the existence of graphs with high girth and high chromatic number is one of the first applications of the probabilistic method. This proof gives a bound on the number of vertices of such graphs, which is exponential on the girth if the chromatic number is fixed. The focus of this text is however on the deterministic construction of graphs with high girth and high chromatic number and on the number of vertices of the obtained graphs. The elementary known constructions can only give us graphs with an Ackermannian number of vertices. We begin by briefly repeating the probabilistic proofs of the existence of graphs and hypergraphs with high girth and high chromatic number. Then we motivate the search for deterministic constructions of such graphs by showing some constructions for the special case of triangle-free graphs with high chromatic number. We construct Tutte, Zykov, Mycielski and Kneser graphs, the shift graphs and graphs built from finite projective planes. We count and compare the number of vertices of the graphs obtained by each of these constructions. In fact, the construction based on finite projective planes gives us graphs with a polynomial number of vertices. The main part of the text consists of constructions of graphs and hypergraphs with high girth and high chromatic number. The first construction we present is due to Kriz. This was the first construction to give graphs with high girth and high chromatic number without using hypergraphs. The second construction we present is due to Nesetril and Rödl. This construction precedes the one by Kriz. It uses amalgamations between graphs and hypergraphs to obtain uniform hypergraphs with high girth and high chromatic number. The third and last construction we show was found by Alon, Kostochka, Reiniger, West and Zhu. This construction manages to build uniform hypergraphs with high girth and high chromatic number directly from a single graph, which is an augmented-tree. In particular, it constructs graphs with high girth and high chromatic number without using hypergraphs. We count and compare the number of vertices of the hypergraphs obtained by these constructions.
|
39 |
Determinantes do acesso ao crédito rural: um estudo a partir do levantamento das unidades produtivas agropecuárias (LUPA) do Estado de São Paulo / Determinats of acces to rural credit: a study based on a survey of agricultural production units (LUPA, in Portuguese) of the State of São PauloEusébio, Gabriela dos Santos 22 February 2011 (has links)
Este trabalho busca compreender e mensurar as características dos produtores rurais que ampliam a probabilidade para que o mesmo tenha acesso ao crédito rural. Utilizando os dados do Levantamento das Unidades Produtivas Agropecuárias (LUPA) do Estado de São Paulo (2006/2007), que abrange todas as UPAs pertencentes aos 645 municípios do estado, foi possível detalhar as características observáveis dos produtores e das propriedades que acessaram o crédito rural em 2007. Para tanto, foi utilizado o método de Árvores de Classificação e Regressão. As estimações realizadas para todas as UPAs de estado de São Paulo mostraram que a diferença de tamanho das unidades produtivas é o principal determinante para o acesso ao crédito. Quando se analisa o acesso ao crédito para unidades produtivas de pequena, média e grande extensão, algumas variáveis apresentam maior impacto no acesso ao crédito. Para as unidades de pequena extensão (até dez hectares), a diversificação de cultura, entre cultura temporária e perene, aumenta a probabilidade dos produtores acessarem o crédito. Para propriedades de média extensão (até quinhentos hectares), a presença de vínculos institucionais, seja cooperativa, sindicato ou associação, e melhorias em gestão (uso de computador, acesso á assistência técnica oficial), além da diversificação de cultura, elevam as probabilidades de acesso ao crédito. A análise mostra também que para unidades produtivas de grande extensão as variáveis que impactam a probabilidade de acesso ao crédito rural estão relacionadas a participação em instituições (cooperado e associado), além de variáveis relacionadas à melhoria de gestão, independentemente do tipo de cultura cultivada pela UPA. / This paper aims to understand and measure the characteristics of farmers which enhance their likelihood of having access to rural credit. Using data from the Survey of Agricultural Production Units (LUPA, in portuguese) of São Paulo (2006/2007), which covers all 645 Agricultural Production Units belonging to municipalities in the state was possible to detail the observable characteristics and properties of the producers who have accessed rural credit in 2007. For this, we used the Classification and Regression Trees method. The estimates performed for all UPAs (in Portuguese) in the state of São Paulo showed that the difference in size of production units is the main determinant to access credit. When analyzing the access to credit for production units of small, medium and large extent, some variables have greater impact on access to credit. For units of small extent (up to ten hectares) the culture diversification between temporary and perennial crop, increases the likelihood of farmers to access credit. For production units of medium length (up to five hundred acres), the presence of institutional links, such as cooperative, union or association, and improvements in management (computer use, technical support officer access), and crop diversification, increase the likelihood of access to credit. The analysis also shows that for production units with large extent the variables that have more impact in the probability of access to rural credit are related to participation in institutions (cooperative and associate), and variables related to improvement management, regardless of the type of crop cultivated by UPA.
|
40 |
Contagem incremental de padrões locais em árvores de componentes para cálculo de atributos / Incremental counting of local patterns in component tree for attribute calculationSilva, Dênnis José da 26 October 2017 (has links)
Árvore de componentes é uma representação completa de imagens que utiliza componentes conexos dos conjuntos de níveis de uma imagem e a relação de inclusão entre esses componentes. Essas informações possibilitam diversas aplicações em processamento de imagens e visão computacional, e.g. filtros conexos, segmentação, extração de características entre outras. Aplicações que utilizam árvore de componentes geralmente computam atributos que descrevem os componentes conexos representados pelos nós da árvore. Entre esses atributos estão a área, o perímetro e o número de Euler, que podem ser utilizados diretamente ou indiretamente (para o cálculo de outros atributos). Os \"bit-quads\" são padrões de tamanho 2x2 binários que são agrupados em determinados conjuntos e contados em imagens binárias. Embora o uso de \"bit-quads\" resulte em um método rápido para calcular atributos em imagens binárias, o mesmo não ocorre para o cálculo de atributos dos nós de uma árvore de componentes, porque os padrões contados em um nó podem se repetir nos conjuntos de níveis da imagem e serem contados mais de uma vez. A literatura recente propõe uma adaptação dos bit-quads para o cálculo incremental e eficiente do número de buracos na árvore de componentes. Essa adaptação utiliza o fato de cada nó da árvore de componentes representar um único componente conexo e uma das definições do número de Euler para o cálculo do número de buracos. Embora essa adaptação possa calcular o número de Euler, os outros atributos (área e perímetro) não podem ser computados. Neste trabalho é apresentada uma extensão dessa adaptação de bit-quads que permite a contagem de todos os agrupamentos de bit-quads de maneira incremental e eficiente na árvore de componentes. De forma que o método proposto possa calcular todos os atributos que podem ser obtidos pelos bit-quads (além do número de buracos) em imagens binárias na árvore de componentes de maneira incremental. / Component tree is a full image representation which uses the connected components of the level sets of the image and these connected components\' inclusion relationship. This information can be used in various image processing and computational vision applications, e.g. connected filters, segmentation, feature extraction, among others. In general, applications which use component trees compute attributes that describe the connected components represented by the tree nodes. Attributes such as area, perimeter and Euler number, can be used directly or indirectly (when they are used to compute other attributes) to describe the component tree nodes in various applications. The bit-quads are binary patterns of size 2x2 that are grouped in determined sets and counted in binary images to compute area, perimeter (also their continuous approximation) and Euler number. Even though the bit-quads usage can yield an efficient method to compute binary image attributes, they cannot be used efficiently to compute attributes for all component tree nodes, since some bit-quads can be counted more than once over the level sets. An adaptation of the bit-quads has been proposed to compute efficiently and incrementally the number of holes for all component tree nodes. This adaptation uses the fact that each component tree node represents a unique connected component and one of Euler number definitions to compute the number of holes. Even though this adaptation can compute Euler number, it cannot compute other attributes derived from the bit-quads (area and perimeter). In this work, an extension of this adaptation is proposed to efficiently and incrementally count all bit-quads sets in a component tree. Moreover, it yields a method to compute all attributes which can be computed by the bit-quads in binary images in the component tree using an incremental strategy.
|
Page generated in 0.3446 seconds