Spelling suggestions: "subject:"teoria dde grafos"" "subject:"teoria dee grafos""
201 |
Extensões induzidas de altura mínima de um conjunto parcialmente ordenadoLima, Ítalo Siqueira January 2007 (has links)
LIMA, Ítalo Siqueira. Extensões induzidas de altura mínima de um conjunto parcialmente ordenado. 2007. 78 f : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza-CE, 2007. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-07-01T19:49:21Z
No. of bitstreams: 1
2007_dis_islima.pdf: 567978 bytes, checksum: 3ba284ffabfddf975efc4b51ef98ffe6 (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-07-01T19:49:52Z (GMT) No. of bitstreams: 1
2007_dis_islima.pdf: 567978 bytes, checksum: 3ba284ffabfddf975efc4b51ef98ffe6 (MD5) / Made available in DSpace on 2016-07-01T19:49:52Z (GMT). No. of bitstreams: 1
2007_dis_islima.pdf: 567978 bytes, checksum: 3ba284ffabfddf975efc4b51ef98ffe6 (MD5)
Previous issue date: 2007
|
202 |
Resolução de problemas relacionados à teoria de Grafos no Ensino FundamentalMesquita, Daniel da Rosa January 2015 (has links)
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.
|
203 |
Grafos no ensino médio: uma inserção possívelMalta, Gláucia Helena Sarmento January 2008 (has links)
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.
|
204 |
Estudo de casos de complexidade de colorações gulosa de vértices e de arestas / Case studies of complexity of greedy colorings of vertices and edgesOliveira, Ana Karolinna Maia de January 2011 (has links)
OLIVEIRA, Ana Karolinna Maia de. Estudo de casos de complexidade de colorações gulosa de vértices e de arestas. 2011. 58 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza-CE, 2011. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-05-24T19:36:17Z
No. of bitstreams: 1
2011_dis_akmoliveira.pdf: 520341 bytes, checksum: b0c0d48f19d7c3e376c2c79c3a815b08 (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-05-24T19:36:55Z (GMT) No. of bitstreams: 1
2011_dis_akmoliveira.pdf: 520341 bytes, checksum: b0c0d48f19d7c3e376c2c79c3a815b08 (MD5) / Made available in DSpace on 2016-05-24T19:36:55Z (GMT). No. of bitstreams: 1
2011_dis_akmoliveira.pdf: 520341 bytes, checksum: b0c0d48f19d7c3e376c2c79c3a815b08 (MD5)
Previous issue date: 2011 / The vertices and edges colorings problems, which consists in determine the smallest number of colors needed to color the vertices and edges of a graph, respectively, so that adjacent vertices and adjacent edges, respectively, have distinct colors, are computationally hard problems and recurring subject of research in graph theory due to numerous practical problems they model. In this work, we study the worst performance of greedy algorithms for coloring vertices and edges. The greedy algorithm has the following general principle: to receive, one by one, the vertices (respect. edges) of the graph to be colored by assigning always the smallest possible color to the vertex (resp. edge) to be colored. We note that so greedy coloring the edges of a graph is equivalent to greedily coloring its line graph, this being the greatest interest in research on greedy edges coloring. The worst performance of the Algorithms is measured by the greatest number of colors they can use. In the case of greedy vertex coloring, this is the number of Grundy or greedy chromatic number of the graph. For the edge coloring, this is the greedy chromatic index or Grundy index of the graph. It is known that determining the Grundy number of any graph is NP-hard. The complexity of determining the Grundy index of any graph was however an open problem. In this dissertation, we prove two complexity results. We prove that the Grundy number of a (q,q−4)-graph can be determined in polynomial time. This class contains strictly the class of cografos P4-sparse for which the same result had been established. This result generalizes so those results. The presented algorithm uses the primeval decomposition of graphs, determining the parameter in linear time. About greedy edge coloring, we prove that the problem of determining the Grundy index is NP-complete for general graphs and polynomial for catepillar graphs, implying that the Grundy number is polynomial for graphs of line of caterpillars. More specifically, we prove that the Grundy index of a caterpillar is D or D+1 and present a polynomial algorithm to determine it exactly. / Os problemas de colorac¸ ˜ao de v´ertices e de arestas, que consistem em determinar o menor n´umero de cores necess´arias para colorir os v´ertices e arestas de um grafo, respectivamente, de forma que v´ertices adjacentes e arestas adjacentes, respectivamente, possuem cores distintas, s˜ao problemas computacionalmente dif´ıceis e s˜ao objeto de pesquisa recorrente em teoria do grafos em virtude de in´umeros problemas pr´aticos que eles modelam. No presente trabalho, estudamos o pior desempenho dos algoritmos gulosos de colorac¸ ˜ao de v´ertices e de arestas. O algoritmo guloso tem o seguinte princ´ıpio geral: receber, um a um, os v´ertices (respect. as arestas) do grafo a ser colorido, atribuindo sempre a menor cor poss´ıvel ao v´ertice (resp. aresta) a ser colorido. Observamos que colorir de forma gulosa as arestas de um grafo equivale a colorir de forma gulosa o seu grafo linha, tendo sido este o maior interesse na pesquisa em colorac¸ ˜ao gulosa de arestas. O pior desempenho dos algoritmos ´e medido pelo maior n´umero de cores que eles podem utilizar. No caso da colorac¸ ˜ao gulosa de v´ertices, esse ´e o n´umero de Grundy ou n´umero crom´atico guloso do grafo. No caso da colorac¸ ˜ao de arestas, esse ´e o ´ındice crom´atico guloso ou ´ındice de Grundy do grafo. Sabe-se que determinar o n´umero de Grundy de um grafo qualquer ´e NP-dif´ıcil. A complexidade de determinar o ´ındice de Grundy de um grafo qualquer era entretanto um problema em aberto. Na presente dissertac¸ ˜ao, provamos dois resultados de complexidade. Provamos que o n´umero de Grundy de um grafo (q,q−4) pode ser determinado em tempo polinomial. Essa classe cont´em estritamente a classe dos cografos e P4-esparsos para os quais o mesmo resultado havia sido estabelecido. Esse resultado generaliza portanto aqueles resultados. O algoritmo apresentado usa a decomposic¸˜ao primeval desses grafos, determinando o parˆametro em tempo linear. No que se refere `a colorac¸ ˜ao de arestas, provamos que o problema de determinar o ´ındice de Grundy ´e NP-completo para grafos em geral e polinomial para grafos caterpillar, implicando que o n´umero de Grundy ´e polinomial para os grafos linha desses. Mais especificamente provamos que o ´ındice de Grundy dos caterpillar ´e D ou D+1 e apresentamos um algoritmo polinomial para determin´a-lo exatamente.
|
205 |
Caracterização de grafos de genealogia acadêmica por meio de métricas topológicasRossi, Luciano January 2015 (has links)
Orientador: Prof. Dr. Jesús Pascual Mena-Chalco / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Ciência da Computação, 2015. / A busca pela origem de indivíduos apresenta-se como uma tentativa recorrente em obter respostas que expliquem o presente, com base no passado e permitam traçar os caminhos do futuro. A origem de um indivíduo esta ligada à algum tipo de relacionamento que possibilite identicar outro que o precedeu. Este modelo de estruturação de grupos sociais é objeto de estudo da genealogia. A genealogia acadêmica utiliza os relacionamentos de orientação entre professores (orientadores) e alunos (orientados) para criar a estrutura social que, comumente, é representada por um grafo de genealogia. O grafo descreve seus vértices como orientadores e orientados e suas arestas direcionadas descrevem as orientações acadêmicas existentes entre eles.
Nesta dissertação de mestrado busca-se caracterizar os vértices de um grafo de genealogia considerando somente seus relacionamentos de orientação acadêmica. A caracterização dos vértices é realizada por meio do desenvolvimento e/ou adaptação de um conjunto de métricas topológicas. O conjunto é composto por 22 métricas, sendo 13 de composição descendente ((i) largura, (ii) número de folhas, (iii) profundidade, (iv) fecundidade, (v) fecundidade ponderada, (vi) maior largura, (vii) índice h genealógico, (viii) impacto, (ix) distância média, (x) média dos menores caminhos, (xi) pagerank inverso, (xii) pagerank inverso ponderado e (xiii) balanceamento pela fecundidade), 8 de composição ascendente ((xiv) fecundidade inversa, (xv) fecundidade média do território inverso, (xvi) fecundidade ponderada média do território inverso, (xvii) número de origens, (xviii) largura inversa, (xix) profundidade inversa, (xx) pagerank e (xxi) pagerank ponderado) e 1 de composição mista ((xxii) balanceamento global ). Acreditamos que todas as métricas propostas possam servir de insumo para analisar computacionalmente qualquer grafo de genealogia.
Em particular, as métricas propostas foram calculadas para o conjunto de doutores em matemática cadastrados na plataforma do Mathematics Genealogy Project (MGP), que em Abril de 2014 contava com mais de 178 mil registros de 185 países, e permitiu realizar análises para: (i) observar características especícas dos vértices do grafo, (ii) estudar o efeito da abrangência das métricas (janela) na caracterização dos vértices e (iii) classicar os vértices em função dos conjuntos de valores de suas métricas. / The search for the origin of individuals is presented as a recurrent attempt to get answers to explain the present, based on the past and to retrace the paths of the future. The origin of a subject is linked to some kind of relationship that allows identify others that preceded it. The academic genealogy uses the orientation relationships between professors (advisors) and students (advisees) to create a social structure that, commonly, is represented by a genealogy graph. The graph describes its vertices as advisors/advisees and the directed edges describe their existing academic guidelines between them.
In this master thesis we present a characterization of a genealogy graph considering only their academic guindance relationships. The characterization of the vertices is performed through the development and / or adaptation of a set of topological metrics. The set consists of 22 metrics. The first 13 descending composition metrics are related with: (i) width, (ii) leaf number, (iii) depth, (iv) fecundity, (v) weighted fecundity, (vi) max width, (vii) genealogical h-index, (viii) impact, (ix) average distance (x) average of the shortest paths, (xi) reverse pagerank, (xii) reverse pagerank weighted and (xiii) balanced fecundity. Eight ascending composition metrics related with: (xiv) reverse fecundity, (xv) fecundity of the reverse territory, (xvi) weighted average fecundity of the reverse territory, (xvii) number of origins, (xviii) reverse width, (xix) reverse depth, (xx) pagerank and (xxi) weighted pagerank. Finally, one mixed composition metrics called (xxii) overall balance. We believe that all proposed metrics can serve as input to analyze genealogy graphs. The proposed metrics were calculated for all PhDs in mathematics registered on Mathematics Genealogy Project (MGP), which in April 2014 had more than 178,000 records from 185 countries, and allowed to perform analysis in order: (i) to observe specic characteristics of the graph vertices, (ii) to study the eect of coverage metrics (i.e, window size) in the characterization of vertices and, (iii) to classify the vertices according to the sets of values of their metrics.
|
206 |
Explorando abordagens de aprendizado sequencial para floresta de caminhos ótimosNakamura, Rodrigo Yuji Mizobe [UNESP] 25 February 2014 (has links) (PDF)
Made available in DSpace on 2015-04-09T12:28:25Z (GMT). No. of bitstreams: 0
Previous issue date: 2014-02-25Bitstream added on 2015-04-09T12:47:36Z : No. of bitstreams: 1
000813449.pdf: 748488 bytes, checksum: d9474f03d8434bb9f3d905323e3bf032 (MD5) / Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) / A modelagem do problema de classificação como um problema de busca em um grafo fornece uma estrutura elegante, rica em algoritmos eficientes e comprovadamente corretos. A abordagem Floresta de Caminhos Ótimos reduz o problema de classificação para o cálculo de uma floresta de cami- nhos ótimos relativa a uma função de conectividade, a qual atribui um valor a qualquer caminho no grafo. Considerando o valor máximo entre todos os caminhos possíveis com término em cada vértice, o caminho ideal é trivial para alguns vértices, chamados raízes, e para os vértices restantes, a minimi- zação da função de conectividade atribui a cada vértice um caminho de custo mínimo a partir de sua raiz mais fortemente conectada. Não obstante, para a classificação de novos conjuntos de dados, assume-se que cada amostra compõe um vértice pertecente ao grafo e calcula-se a afinidade deste vértice às árvores geradoras mínimas respectivas a cada classe. Este procedimento não utiliza a estrutura inerente da aplicação que pode ser fundamental para uma melhor precisão dos resultados. Dentro desse contexto, este trabalho avalia a contribuição de técnicas de modelagem contextual como os campos aleatórios Markovianos e as abordagens de empilhamento de classificado- res. A modelagem do campo aleatório sumariza o comportamento global do sistema através de suas interações locais. Os métodos baseados em empilha- mento de classificadores interpretam as interações entre as amostras como uma análise no espaço escala, capturando as interações de longa distância de forma eficiente através da definição das regiões de vizinhança em múltiplas escalas. Resultados obtidos para a classificação de estruturas anatômicas do cérebro em imagens de ressonância magnética e de coberturas do solo em imagens multi-espectrais de sensoriamento remoto monstram que a inclusão da informação contextual é de fato capaz de melhorar ... / The interpretation of classification problem as a graph search provides a rich framework with correct and efficient algorithms. The Optimum-Path Fo- rest classifier can reduce classification to the the computation of an optimum- path forest according to a connectivity function, which assigns a value to any path in the graph. Considering the maximum value among all possible paths with terminus at each node, the optimum path is trivial for some nodes, cal- led roots, and the remaining nodes will have an optimum path coming from their most strongly connected root, partitioning the graph into an optimum- path forest (disjoint sets of optimum-path trees). Notwithstanding, to clas- sify out-of-sample, we assume that each sample in the new dataset composes one node in the graph and we compute their most strongly connected root within all spanning trees. As one can see, this procedure do not take advan- tage of the problem structure information, which can be fundamental for a better precision of the results. In this context, the purpose of this work is to evaluate the contribution of contextual modelling techniques, such as Mar- kov random fields and stacked classifiers. The first approach, called Markov random fields, sumarizes the system overall behavior through its local inte- ractions. The second approach, based on combination of classifiers, model the interaction between samples in the space scale, which provides effici- ent implementations of long interaction by defining neighborly relations in multiple scales. The results for brain tissue segmentation of magnetic reso- nance images and land-cover classification of multi-spectral satellite images show that the contextual information can improve the effectiveness of the Optimum-Path Forest classifier
|
207 |
Explorando abordagens de múltiplos rótulos por floresta de caminhos ótimosPereira, Luís Augusto Martins [UNESP] 25 February 2013 (has links) (PDF)
Made available in DSpace on 2015-04-09T12:28:25Z (GMT). No. of bitstreams: 0
Previous issue date: 2013-02-25Bitstream added on 2015-04-09T12:47:36Z : No. of bitstreams: 1
000811257.pdf: 6065923 bytes, checksum: 2f62e4d931cb75542832b3627b24b710 (MD5) / Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) / Em problemas convencionais de reconhecimento de padrões, dado um conjunto de classes, cada instância do problema e associada a uma e somente uma classe. No entanto, alguns problemas reais de classificaço apresentam instâncias que podem ser associadas a mais de uma classe simultaneamente, esses problemas são denotados como classificação com múltiplos rótulos. Entre problemas dessa natureza, podemos destacar categorização de filmes e músicas, classificação de documentos, análise funcional de genes etc. Contudo, os problemas de classificação com múltiplos rótulos não são diretamente tratáveis por técnicas convencionais, o que justifica o interesse da comunidade de reconhecimento de padrões nesses tipos de problemas. Embora muitos métodos tenham sido propostos na literatura, há ainda muito a ser explorado, principalmente no uso de novos algoritmos convencionais de aprendizado de máquinas adaptados ou não aos problemas com múltiplos rótulos. O classificador supervisionado Floresta de Caminhos Otimos (Optimum- Path Forest - OPF) e um algoritmo determinístico aplicado a problemas convencionais de classificação, no entanto, ainda não foi investigado em problemas com múltiplos rótulos. Nesse contexto, investigamos neste trabalho a aplicação de classificadores baseados em OPF em problemas de múltiplos rótulos. Analisamos duas versões do classificador OPF: (i) a tradicional baseada em grafo completo e (ii) a versão baseada no grafo k-vizinhos mais próximos (OPFkNN). Para manipulação das bases com múltiplos rótulos, utilizamos dois métodos de transformação de problemas, o Binary Relevance e Label Powerset. Propusemos também algumas modificações nas fases de treinamento e classificação do OPFkNN com o objetivo de melhor os resultados desse classificador combinado a métodos de transformação de problemas. Os experimentos realizados em sete bases de dados públicas mostraram que as modifica ções ... / In conventional problems of pattern recognition, given a set of classes, each instance of the problem is associated with one and only one class. However, some real classification problems have instances that can be associated with more than one class at the same time, these problems are denoted as classification with multilabel. Among such problems, we highlight movies and music categorization, document classification, functional gene analysis etc. Nevertheless, the classification problems with multilabel are not directly treatable by conventional techniques, which explains the interest of pattern recognition community in these types of problems. Although many methods have been proposed in the literature, there is still much to be explored, especially in the use of novel conventional machine learning algorithms adapted or not to problems with multlabels. The Optimum-Path Forest (OPF) classifier is a supervised and deterministic algorithm applied to conventional classification problems, however, it has been not investigated in problems with multilabel. In this context, we investigated in this work the application of OPF-based classifiers on multilabel problems. We analyzed two versions of OPF-based classi ers: (i) the traditional one based on complete graph and (ii) the one based on k-nearest neighbors graph (OPFkNN). For manipulation of multilabel datasets, we used two transformation methods, the Binary Relevance and Label Powerset. We also proposed some changes in the training and classification phases of OPFkNN aiming to achieve better results when combined it with transformation methods. Experiments performed in seven public datasets showed that changes in OPFkNN improve outcomes. Comparison with the J48 classifier, ... / FAPESP: 2011/14094-1
|
208 |
Representação na forma normal disjuntiva para a flexibilidade de seqüência na manufaturaRohde, Leonardo Rosa January 2002 (has links)
A crescente demanda por produtos de melhor qualidade, diferenciados e com custos competitivos tem forçado as manufaturas a se tornarem flexíveis, capacitando-as a responder às mudanças impostas pelo mercado. A flexibilidade permite que as empresas alcancem a customização desejada através da capacitação do sistema de responder e atuar em tempo real, mesmo em um ambiente de incertezas. Para atuar em tempo real, os sistemas de manufatura precisam de representações eficientes dos planos de produção. Muitas vezes, a atuação em tempo real torna-se inviável devido ao crescimento exponencial no número de planos de produção para cada máquina ou operação adicionada ao sistema. Uma possível solução para este problema é uso de representações adequadas para o espaço de estados. A escolha de uma representação adequada para o espaço de estados influencia na capacidade de reposta em tempo real, pois determina o desempenho computacional do sistema através da utilidade e eficiência dos algoritmos desenvolvidos, tornando possível explorar problemas clássicos de flexibilidade, tais como, seqüenciamento, otimização, etc. Entretanto, a geração de uma representação que trabalhe com o espaço de estados completo de uma manufatura é considerada um problema não polinomial (NP). Esta particularidade dificulta o desenvolvimento de algoritmos que trabalhem com uma manufatura flexível. Assim, a geração de uma representação, que trabalhe com pouca memória computacional e permita o desenvolvimento de heurísticas eficientes, é um importante desafio para uma avaliação efetiva da flexibilidade. Este trabalho objetiva o desenvolvimento de uma representação para o espaço de estados de uma manufatura com flexibilidade de seqüência. Na construção desta representação são aplicadas técnicas de modelagem baseadas na teoria dos grafos e nos princípios de álgebra booleana. Inicialmente, os grafos são utilizados para representar todas as seqüências de operações de uma manufatura, posteriormente estas seqüências são convertidas em formas normais disjuntivas (FND). Por fim, é apresentada uma possível aplicação da representação na FND em modelos de programação linear.
|
209 |
Grafos no ensino médio: uma inserção possívelMalta, Gláucia Helena Sarmento January 2008 (has links)
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.
|
210 |
Uma abordagem de múltiplos aspectos para alinhamento de ontologias baseado em Cluster Ensembles Bayesianos. / A multi-aspect approach for ontology matching based on Bayesian Cluster Ensembles.André Ippolito 22 May 2017 (has links)
Ontologias são especificações formais e explícitas usadas para descrever entidades de um domínio e seus relacionamentos. Estatísticas recentes do projeto Linked Open Data (LOD) indicam a existência de milhares de ontologias heterogêneas publicadas na nuvem do LOD, impondo um desafio para a integração de ontologias. Um passo fundamental na integração é o emparelhamento, processo que obtém elementos correspondentes entre ontologias heterogêneas. Visando superar o desafio de efetuar o emparelhamento em larga escala, desenvolveu-se uma estratégia baseada em clusterização das ontologias, a qual particiona as ontologias em subontologias, clusteriza as subontologias e restringe o processo de emparelhamento aos elementos de um mesmo cluster. Porém, observa-se que as soluções do estado da arte necessitam explorar mais os múltiplos aspectos que as subontologias possuem. As clusterizações de cada aspecto podem ser combinadas, por meio de um consenso. Cluster Ensembles é uma técnica que permite obter esse consenso. Além disso, estudos comparativos indicaram que o uso de Cluster Ensembles Bayesianos (CEB) resulta em uma clusterização de maior acurácia do que a obtida por outras técnicas de Cluster Ensembles. Um dos principais objetivos deste trabalho foi desenvolver uma nova metodologia de emparelhamento de ontologias baseada em clusterização consensual de múltiplos aspectos de comunidades, de forma a estruturar um arcabouço metodológico, por meio do qual diferentes técnicas e aspectos podem ser incorporados e testados. De acordo com a metodologia desenvolvida neste trabalho, inicialmente aplicaram-se técnicas de Detecção de Comunidades para particionar as ontologias. Em seguida, consideraram-se os seguintes aspectos das comunidades obtidas: terminológico, estrutural e extensional. Fez-se, separadamente, a clusterização das comunidades segundo cada aspecto e aplicaram-se diferentes técnicas de clusterização consensual para obter um consenso entre as clusterizações de cada aspecto: CEB, técnicas baseadas em similaridades e técnicas baseadas em métodos diretos. Para os diferentes consensos, o processo de emparelhamento foi feito apenas entre elementos das ontologias que pertencessem a um mesmo cluster consensual. As soluções consensuais destacaram-se nos estudos de caso efetuados quanto à precisão e cobertura dos alinhamentos, enquanto a solução baseada no aspecto terminológico destacou-se quanto ao valor de F-measure. A principal contribuição deste trabalho relaciona-se à metodologia desenvolvida, que constitui um arcabouço metodológico, por meio do qual diferentes aspectos e técnicas podem ser incorporados e testados quanto ao seu desempenho de clusterização e de alinhamento de ontologias. / Ontologies are formal and explicit specifications used to describe entities of a domain and its relationships. Recent statistics of the Linked Open Data (LOD) project indicate the existence of thousands of heterogeneous ontologies in the LOD cloud, posing a challenge to ontology integration. A fundamental step in integration is matching, a process that finds correspondent elements between heterogeneous ontologies. Aiming to overcome the challenge of large-scale ontology matching, researchers developed a strategy based on clustering, which divides ontologies into subontologies, clusters subontologies and restricts the matching process to elements of the same cluster. However, state-of-the-art solutions need to explore more the multiple aspects that subontologies have. Clustering solutions of each aspect can be combined, by means of a consensus. Cluster Ensembles is a technique that allows obtaining this consensus. Besides, comparative studies indicated that Bayesian Cluster Ensembles has higher clustering accuracy than other Cluster Ensembles techniques. One of the main goals of this work was to develop a new methodology for ontology matching based on consensus clustering of multiple aspects of communities, structuring a methodological framework that enables the use and tests of different techniques and aspects. According to the methodology adopted in this work, initially, Community Detection techniques were applied to partition the ontologies. In the sequence, the following aspects of the communities were considered: terminological, structural and extensional. Clustering according to each aspect was performed separately and different consensus clustering techniques were applied to obtain a consensus among clustering solutions of each aspect: Bayesian Cluster Ensembles, techniques based on similarities and techniques based on direct methods. For the different consensuses, matching was done only between elements of the two ontologies that belonged to the same consensual cluster. For the case studies applied in this work, the consensual solutions were a standout in precision and recall, while the terminological-based solution was a standout in F-measure. The main contribution of this work is related to the developed methodology, which constitutes a methodological framework, through which different aspects and techniques can be incorporated and tested concerning their ontology clustering and alignment performance.
|
Page generated in 0.0757 seconds