Orientador: Fabricio Aparecido Breve / Banca: Denis Henrique Pinheiro Salvadeo / Banca: Diego Raphael Amancio / Resumo: O Aprendizado de Máquina é uma área que vem crescendo nos últimos anos e é um dos destaques dentro do campo de Inteligência Artificial. Atualmente, uma das subáreas mais estudadas é o Aprendizado Semi-Supervisionado, principalmente pela sua característica de ter um menor custo na rotulação de dados de exemplo. A categoria de modelos baseados em grafos é a mais ativa nesta subárea, fazendo uso de estruturas de redes complexas. O algoritmo de competição e cooperação entre partículas é uma das técnicas deste domínio. O algoritmo provê acurácia de classificação compatível com a de algoritmos do estado da arte, e oferece um custo computacional inferior à maioria dos métodos da mesma categoria. Neste trabalho é apresentado um estudo sobre Aprendizado Semi-Supervisionado, com ênfase em modelos baseados em grafos e, em particular, no Algoritmo de Competição e Cooperação entre Partículas (PCC). O objetivo deste trabalho é propor um novo algoritmo de competição e cooperação entre partículas baseado neste modelo, com mudanças na caminhada pelo grafo, com informações de dominância sendo mantidas nas arestas ao invés dos nós; as quais possam melhorar a acurácia de classificação ou ainda o tempo de execução em alguns cenários. É proposta também uma metodologia de avaliação da rede obtida com o modelo de competição e cooperação entre partículas, para se identificar a melhor métrica de distância a ser aplicada em cada caso. Nos experimentos apresentados neste trabalho, pode ser visto que... / Abstract: Machine Learning is an increasing area over the last few years and it is one of the highlights in Artificial Intelligence area. Nowadays, one of the most studied areas is Semi-supervised learning, mainly due to its characteristic of lower cost in labeling sample data. The most active category in this subarea is that of graph-based models, using complex networks concepts. The Particle Competition and Cooperation in Networks algorithm (PCC) is one of the techniques in this field. The algorithm provides accuracy compatible with state of the art algorithms, and it presents a lower computational cost when compared to most techniques in the same category. In this project, it is presented a research about semi-supervised learning, with focus on graphbased models and, in special, the Particle Competition and Cooperation in Networks algorithm. The objective of this study is to base proposals of new particle competition and cooperation algorithms based on this model, with new dynamics on the graph walking, keeping dominance information on the edges instead of the nodes; which may improve the accuracy classification or yet the runtime in some situations. It is also proposed a method of evaluation of the network built with the Particle Competition and Cooperation model, in order to infer the best distance metric to be used in each case. In the experiments presented in this work, it can be seen that the proposed algorithm presented better accuracy when compared to the PCC for some datasets, while the proposed distance metrics evaluation achieved a high precision level in most cases / Mestre

Tese (doutorado) - Universidade Federal de Santa Catarina, Centro Tecnológico, Programa de Pós-Graduação em Engenharia Mecânica, Florianópolis, 2010 / Made available in DSpace on 2012-10-24T22:44:03Z (GMT). No. of bitstreams: 1 281094.pdf: 2556693 bytes, checksum: 3357c5d3f7a1cfe0bddeec63b21572c0 (MD5) / A fase de projeto conceitual demecanismos emanipuladores paralelos, i.e. estruturas cinematicas, destina-se ao desenvolvimento da concepçao da cadeia cinematica. As etapas fundamentais para o desenvolvimento da concepao da cadeia cinematica sao sintese e analise. A sintese corresponde à enumeraçao de concepcoes e a analise corresponde `a seleçao das concepçoes mais promissoras considerando os requisitos de projeto. O objetivo deste trabalho é aplicar ferramentas da teoria de grupos e teoria de grafos para a enumeraçao e para a analise de estruturas cinematicas. A enumeraçao sera desenvolvida de forma sistematica em tres niveis: enumeraçao de cadeias cinematicas, enumeraçao de mecanismos e enumeraçao de manipuladores paralelos. A aplicaçao de ferramentas da teoria de grafos e grupos permite desenvolver novos metodos para enumeraçao e, consequentemente, obter novos resultados. A analise sera simplificada considerando um novo metodo que avalia as simetrias das cadeias cinematicas. Uma cadeia cinematica é representada de forma univoca atraves de um grafo. A representaçao atraves do grafo permite a manipulaçao computacional do problema de enumeraçao de cadeias cinematicas. A aplicaçao de ferramentas integradas da teoria de grafos e teoria de grupos permite identificar as simetrias das cadeias cinematicas atraves do grupo de automorfismos do grafo e, assim, é possivel identificar quais são as possiveis escolhas de base para novos mecanismos e avaliar quais sao as possiveis escolhas de base e efetuador final para manipuladores paralelos. O primeiro nivel da sintese corresponde à enumeraçao de cadeias cinematicas com determinada mobilidade, numero de elos, numero de juntas que operam num determinado sistema de helicoides. O segundo nivel da sintese corresponde a enumeraçao de mecanismos. Um mecanismo é uma cadeia cinematica com um elo escolhido para ser a base. Assim, a enumeraçao de mecanismos consiste em determinar todas as possiveis escolhas de bases para uma determinada cadeia cinematica. O principal conceito empregado neste nivel é o de simetria de grafos não coloridos e orbitas do grupo de automorfismos. O terceiro nivel da sintese corresponde `a enumeraçao de manipuladores paralelos. Um manipulador paralelo é uma cadeia cinematica com um elo escolhido para ser a base e outro para ser o efetuador final. Em outras palavras, um manipulador paralelo é um mecanismo com um elo escolhido para ser o efetuador final. Assim, a enumeraçao de manipuladores paralelos consiste em determinar todas as possiveis escolhas de efetuador final para um determinado mecanismo. O principal conceito empregado neste nivel é a simetria de grafos coloridos e orbitas do grupo de automorfismos de grafos coloridos. Na etapa de analise das concepcoes enumeradas serao abordadas propriedades bem estabelecidas na literatura: mobilidade, variedade, conectividade, grau de controle, redundancia e simetria. Mobilidade e variedade sao propriedades globais das estruturas cinematicas. Conectividade, grau de controle e redundancia sao propriedades locais, i.e. entre dois elos da estrutura cinematica e sao dadas por matrizes n×n, onde n é o número de elos da cadeia. A simetria pode ser considerada uma propriedade global e/ou local da estrutura cinem´atica. A aplicaçao de ferramentas integradas da teoria de grafos e teoria de grupos permite demonstrar que as propriedades locais sao invariantes pela acao do grupo de automorfismos do grafo, i.e. elas sao propriedades simetricas. Desta forma, a representaçao matricial é reduzida de n×n para o×n, onde o é o numero de orbitas do grupo de automorfismos do grafo aassociado à estrutura cinematica. Essa abordagem permite simplificar a analise de estruturas cinematicas apenas considerando as simetrias das cadeia associadas.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-graduação em Engenharia Mecânica / Made available in DSpace on 2012-10-23T23:10:37Z (GMT). No. of bitstreams: 1 248436.pdf: 960786 bytes, checksum: ea91ab2ec7da01bf13ed0f739309d988 (MD5) / O objetivo principal deste trabalho é apresentar novas abordagens para a síntese estrutural de cadeias cinemáticas, que é uma fase fundamental para o projeto de mecanismos, utilizando ferramentas da teoria de grafos e da teoria de grupos. A síntese estrutural de cadeias cinemáticas consiste na geração de uma lista completa de cadeias cinemáticas sem cadeia isomórficas e degeneradas que satisfazem a equação da mobilidade. Nesta fase do projeto de mecanismos as dimensões dos elos não são consideradas e uma cadeia cinemática pode ser representada de forma unívoca por um grafo cujos vértices correspondem aos elos da cadeia e as arestas correspondem às juntas. Com isso, a síntese estrutural de cadeias cinemáticas consiste na geração de uma lista completa de grafos que satisfazem a equação da mobilidade. Uma revisão dos principais métodos de síntese estrutural de cadeias cinemáticas é apresentada e os principais problemas desses métodos são identificados. Existem duas espécies de problemas: geração de cadeias isomórficas e degeneradas as quais devem sempre ser evitadas por um método ideal de síntese estrutural; e a geração de cadeias com fracionamento as quais devem ser consideradas opcionais. Em vista disto, dois métodos de geração de cadeias sem fracionamento e um de cadeias com fracionamento são aprimorados e um novo método de geração exclusiva de cadeias com fracionamento é proposto. Novos resultados são obtidos para cadeias que operam em vários sistemas de helicóides. Os resultados serão apresentados em tabelas, e para o caso plano, as diferenças nos resultados encontrados na literatura serão analisados. A síntese estrutural de mecanismos consiste na enumeração das possíveis inversões cinemáticas que uma cadeia cinemática pode originar. Para esta fase foi utilizada uma nova abordagem com ferramentas da teoria de grupos. Pela primeira vez na literatura de mecanismos foi introduzido o conceito de órbitas do grupo de automorfismos do grafo, o qual representa a cadeia cinemática, para representar as inversões cinemáticas. Novos resultados são obtidos para mecanismos que operam em vários sistemas de helicóides e apresentados em tabelas.

Submitted by Nathália Faria da Silva (nathaliafsilva.ufv@gmail.com) on 2017-10-04T12:42:42Z No. of bitstreams: 1 texto completo.pdf: 13995495 bytes, checksum: 71c34a30f49b54385642ee42cdb41d72 (MD5) / Made available in DSpace on 2017-10-04T12:42:42Z (GMT). No. of bitstreams: 1 texto completo.pdf: 13995495 bytes, checksum: 71c34a30f49b54385642ee42cdb41d72 (MD5) Previous issue date: 2017-02-22 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / A Teoria dos Grafos está associada a situações que podem ser descritas por meio de diagramas representados por um conjunto de pontos (vértices) e linhas que ligam alguns pares destes pontos (arestas). Seu inı́cio remonta a visita de Leonhard Euler à cidade de Königsberg, em 1736, quando foi apresentado a ele um desafio que intrigava os moradores da cidade. Eles se perguntavam se era possı́vel sair de casa, passar em cada ponte, apenas uma vez, e retornar ao ponto inicial. O diagrama montado por Euler para representar o mapa das sete pontes da cidade é um esquema de grafo. O desenvolvimento e a consolidação da Teoria dos Grafos proporcionou significativas contribuições para a Fı́sica, Quı́mica, Biologia e Ciência da Computação. Os algoritmos associados a problemas de caminho mı́nimo, coloração e busca de árvore geradora mı́nima são amplamente utilizados na prática de linguagem de programação. Nessa pesquisa, o problema de caminho mı́nimo e a busca da árvore geradora mı́nima são usados para o trabalho de algoritmos envolvendo grafos com alunos do Ensino Médio em uma escola de Belo Horizonte. Uma sequência didática com três aulas foi aplicada, sendo a primeira aula sobre a introdução à teoria dos grafos, a segunda aula sobre algoritmos e grafos e a terceira aula com a implementação desses algoritmos usando a linguagem de programação C. Os algoritmos utilizados foram Dijkstra, Prim, Kruskal e Floyd. Resultados apontam para a possibilidade de inclusão da Teoria dos Grafos no Ensino Médio tendo em vista as interações com Análise Combinatória, Probabilidade e Poliedros. O estudo de grafos por meio de algoritmos e sua aplicação em linguagem de programação é uma nova abordagem a ser considerada para o Ensino Médio. / The Theory of Graphs is associated with situations that can be described by means of diagrams represented by a set of points (vertices) and lines that connect some pairs of these points (edges). Its beginning dates back to Leonhard Euler’s visit to the town of Königsberg in 1736, when he was presented with a challenge that intrigued the city’s residents. They wondered if it was possible to get out of the house, pass on each bridge only once, and return to the starting point. The diagram assembled by Euler represent the map of the city’s seven bridges is a graph diagram. The development and consolidation of Graph Theory provided significant contributions to Physics, Chemistry, Biology and Computer Science. The algorithms associated with minimum path, coloring, and minimum generation tree search algorithms are widely used in programming language practice. In this research, the minimum path problem and the minimum generation tree search are used to work with algorithms involving graphs with high school students in a school in Belo Horizonte. A didactic sequence with three sections was applied, being the first class on the introduction to the graph theory, the second class on algorithms and graphs and the third class with the implementation of these algorithms using the C programming language. The algorithms used were Dijkstra, Prim, Kruskal and Floyd. Results point to the possibility of including the Theory of Graphs in High School in view of the interactions with Combinatorial Analysis, Probability and Polyhedra. The study of graphs through algorithms and their application in programming language is a new approach to be considered for High School.

IVO, Rafael Fernandes. Uma nova estratégia para renderizar descontinuidades e superfícies intersectantes em modelos baseados em splats. 2011. 87 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2011. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-12T15:39:16Z No. of bitstreams: 1 2011_dis_rfivo.pdf: 18188495 bytes, checksum: 8bba2f9c682856ab4b475566ec0afe9a (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-21T14:07:35Z (GMT) No. of bitstreams: 1 2011_dis_rfivo.pdf: 18188495 bytes, checksum: 8bba2f9c682856ab4b475566ec0afe9a (MD5) / Made available in DSpace on 2016-07-21T14:07:35Z (GMT). No. of bitstreams: 1 2011_dis_rfivo.pdf: 18188495 bytes, checksum: 8bba2f9c682856ab4b475566ec0afe9a (MD5) Previous issue date: 2011 / Splats based models have gained increasing attention due to its potential for rendering complex geometric models efficiently and with high quality. The absence connectivity information of these models allows complex modeling operations, as Boolean operations, and fractures in physics simulations. However, these operations often generate models with edges and corners that can not be represented correctly with a finite number of splats without a treatment to be done. In this work, a neighborhood graph uses an estimate which ensures the connection of all these splats on opposite sides a discontinuity and that need to be clipped against each other. After using a method for detecting discontinuities in the generated graph, the neighbors participating in the a splat clipping, clip partners are determined to cut out and sorted splat so as to adapt it to the curve of discontinuity. Another problem encountered in rendering models based on reconstruction of splats is intersecting surfaces. Close intersections of surfaces, the surfaces are mixed, resulting in artifacts. to treat these cases, a segmentation algorithm performs separation of the various surfaces present in the model, identifying the splats that form and hold them to be combined into areas near the intersections of surfaces in the surface reconstruction phase space image. / Modelos baseados em splats têm ganhado crescente atenção devido a seu potencial para renderizações de modelos geométricos complexos de forma eficiente e com alta qualidade. A ausência de informações de conectividade desses modelos permite operações de modelagem complexas, como operações booleanas, e fraturas em simulações físicas. Entretanto, essas operações geralmente geram modelos com arestas e cantos que não podem ser representados corretamente com um número finito de splats sem que um tratamento seja feito. Neste trabalho, um grafo de vizinhança utiliza uma estimativa que garante a conexão de todos os splats presentes em lados opostos de uma descontinuidade e que precisam ser recortados uns contra os outros. Após utilizar um método de detecção de descontinuidades no grafo gerado, os vizinhos que participam do recorte de um splat, os clip partners, são determinados e classificados para que recortem o splat de forma a adaptá-lo à curva da descontinuidade. Outro problema encontrado na renderização de modelos baseados em splats é reconstrução de superfícies intersectantes. Nas proximidades de interseções de superfícies, as superfícies são misturadas, resultando em artefatos. Para tratar esses casos, um algoritmo de segmentação realiza a separação das diversas superfícies presentes no modelo, identificando os splats que as formam e impedindo que eles sejam combinados em áreas próximas de interseções de superfícies na etapa de reconstrução da superfície em espaço de imagem.

Submitted by Reginaldo Soares de Freitas (reginaldo.freitas@ufv.br) on 2016-08-30T11:54:54Z No. of bitstreams: 1 texto completo.pdf: 17704467 bytes, checksum: 3fff70ad8c6dec633832a9b489d49f79 (MD5) / Made available in DSpace on 2016-08-30T11:54:54Z (GMT). No. of bitstreams: 1 texto completo.pdf: 17704467 bytes, checksum: 3fff70ad8c6dec633832a9b489d49f79 (MD5) Previous issue date: 2015-12-04 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / A proposta aqui apresentada pretende estudar, do ponto de vista global, aplicações de 3-variedades fechadas no R3 , com grafos associados ao conjunto singular destas aplicações que servem como invariantes topológicos na classificação destas e também como ferramenta para a construção de aplicações. / The proposal presented here wants to study, from a global point of view, applications of 3-manifolds closed in R3 associating graphs the single set of these applications that serves as topological invariant in the classification of these as well as a tool for building applications. / O autor não apresentou título em inglês.

Neste trabalho, apresentamos um algoritmo que determina o número de autovalores de uma matriz simétrica qualquer que representa uma árvore, num dado intervalo real. Várias aplicações são obtidas em relação à distribuição dos autovalores da matriz laplaciana perturbada, uma matriz de representação de grafos que inclui, como casos particulares, a matriz de adjacências, a matriz laplaciana combinatória, a matriz laplaciana sem sinal e a matriz laplaciana normalizada, amplamente estudadas em Teoria Espectral de Grafos. Além disso, desenvolvemos também um algoritmo de localização de autovalores da matriz de adjacências de um grafo unicíclico. Este procedimento permite obter propriedades espectrais de grafos unicíclicos denominados centopeias unicíclicas. / In this work, we present an algorithm that computes the number of eigenvalues of any symmetric matrix that represents a tree, in a given real interval. Several applications are obtained about the distribution of the eigenvalues of the perturbed Laplacian matrix, which is a matrix representation of graphs that includes, as special cases, the adjacency matrix, the combinatorial Laplacian matrix, the signless Laplacian matrix and the normalized Laplacian matrix, widely studied in Spectral Graph Theory. In addition, we also develop an algorithm that locates the eigenvalues of the adjacency matrix of a unicyclic graph. This procedure allows us to obtain spectral properties of unicyclic caterpillars.

OPERTI, Felipe Gioachino. Interpolation strategy based on Dynamic Time Warping. 2015. 53 f. Dissertação (Mestrado em Física) - Programa de Pós-Graduação em Física, Departamento de Física, Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2015. / Submitted by Edvander Pires (edvanderpires@gmail.com) on 2015-04-14T22:11:14Z No. of bitstreams: 1 2015_dis_fgoperti.pdf: 5361657 bytes, checksum: b47dae9c4d72accf5fe2c50b89abaae4 (MD5) / Approved for entry into archive by Edvander Pires(edvanderpires@gmail.com) on 2015-04-16T18:35:49Z (GMT) No. of bitstreams: 1 2015_dis_fgoperti.pdf: 5361657 bytes, checksum: b47dae9c4d72accf5fe2c50b89abaae4 (MD5) / Made available in DSpace on 2015-04-16T18:35:49Z (GMT). No. of bitstreams: 1 2015_dis_fgoperti.pdf: 5361657 bytes, checksum: b47dae9c4d72accf5fe2c50b89abaae4 (MD5) Previous issue date: 2015 / In oil industry, it is essential to have the knowledge of the stratified rocks’ lithology and, as consequence, where are placed the oil and the natural gases reserves, in order to efficiently drill the soil, without a major expense. In this context, the analysis of seismological data is highly relevant for the extraction of such hydrocarbons, producing predictions of profiles through reflection of mechanical waves in the soil. The image of the seismic mapping produced by wave refraction and reflection into the soil can be analysed to find geological formations of interest. In 1978, H. Sakoe et al. defined a model called Dynamic Time Warping (DTW)[23] for the local detection of similarity between two time series. We apply the Dynamic Time Warping Interpolation (DTWI) strategy to interpolate and simulate a seismic landscape formed by 129 depth-dependent sequences of length 201 using different values of known sequences m, where m = 2, 3, 5, 9, 17, 33, 65. For comparison, we done the same operation of interpolation using a Standard Linear Interpolation (SLI). Results show that the DTWI strategy works better than the SLI when m = 3, 5, 9, 17, or rather when distance between the known series has the same order size of the soil layers.

Orientador: Prof. Dr. Letícia Rodrigues Bueno / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Ciência da Computação, 2015. / Given a graph G, the hamiltonian cycle problem consists in determining if there is a cycle containing all vertices of G exactly once. This problem is known to be NP-Complete, therefore a recent trend is to searching for long cycles in order to determine the cycle with the largest possible number of vertices. Another trend is searching for related structures. In this aspect, being prism-hamiltonian has been an interesting relaxation of being hamiltonian. The prism over a graph G consists of two copies of G with an edge joining the corresponding vertices. A graph G is prism-hamiltonian if the prism over G contains a hamiltonian cycle. In this work, we study a conjecture which claims that every 4-connected 4-regular graph is prism-hamiltonian. We prove the conjecture for claw-free graphs. In fact, for a subclass of claw-free 4-connected 4-regular graphs, we prove a stronger result: its hamiltonicity; therefore, corroborating to another conjecture from 1993 which states that claw-free 4-connected 4-regular graphs are hamiltonian. Given a graph G, let G1 = GK2 and Gq = Gq..1K2, for q > 1. For every connected graph G, we prove that Gq is hamiltonian for q dlog2 (G)e, where (G) is the maximum degree of G.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-Graduação em Engenharia de Produção. / Made available in DSpace on 2012-10-21T11:16:53Z (GMT). No. of bitstreams: 1 214048.pdf: 2531808 bytes, checksum: b4579a715576cd7603a6b3238f14bd5e (MD5) / O conhecimento tem se configurado como um recurso estratégico nas organizações. Para elas, gerar, codificar, gerir e disseminar o conhecimento organizacional tornaram-se tarefas essenciais. Logo, é necessário o desenvolvimento de novas técnicas, metodologias e formas de extração de conhecimento a partir de fontes de informação que descrevem um domínio de aplicação. Nesse contexto, o objetivo do presente trabalho é propor um método que permita traduzir fontes de informação em um formato padrão de representação de relacionamentos entre elementos do domínio do problema, de forma a viabilizar a extração de conhecimento por meio da aplicação de Link Analysis e Teoria dos Grafos. Além disso, são apresentadas duas aplicações desse modelo na Plataforma Lattes de CT&I.