Orientador: Celia Picinin de Mello / Tese (doutorado) - Universidade Estadual de Campinas , Instituto de Computação / Made available in DSpace on 2018-08-06T12:11:33Z (GMT). No. of bitstreams: 1 Campos_ChristianeNeme_D.pdf: 1048367 bytes, checksum: e8270db6704873ddaf2043927ca93e99 (MD5) Previous issue date: 2006 / Doutorado / Teoria dos Grafos / Doutor em Ciência da Computação

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / The present dissertation aims to introduce the basic concepts of graph theory to explore the concept of planarity and present a beautiful theorem connected to this theme. Graph theory is a very effective tool for solving problems involving several areas of knowledge. Some of these problems are related to planarity of graphs. Thus, this work presents Kuratowski’s theorem, with the beauty of its demonstration, which provides a necessary and sufficient condition for a graph to be planar, observing if it contains a specific type of subgraph related to complete and split graphs. / A presente dissertaçãoo tem como objetivo introduzir os conceitos básicos da teoria dos grafos para explorar o conceito de planaridade e apresentar um belo teorema ligado a esse tema. A teoria dos grafos é uma ferramenta muito eficaz na resolução de problemas que envolvem diversas áreas de conhecimento. Alguns destes problemas estão relacionados `a planaridade de grafos. Dessa forma, este trabalho apresenta o teorema de Kuratowski, com a beleza de sua demonstra¸c˜ao, que fornece uma condição necessária e suficiente para um grafo ser planar, observando se o mesmo contém um tipo específico de subgrafo relacionado a grafos completos e bipartidos. / São Cristóvão, SE

Bartsch (BARTSCH, 1993) introduziu uma teoria de índice cohomológico, conhecida como o length, para G-espaços, no qual G é um grupo de Lie compacto. Apresentamos o cálculo do length de G-espaços os quais são esferas de cohomologia e G = (Z2)k, (Zp)k ou (S1)k, k &ge; 1. Como consequências, obtemos um teorema de Borsuk-Ulam neste contexto e damos condições suficientes para a existência de aplicações G-equivariantes entre uma esfera de cohomologia e uma esfera de representação quando G = (Zp)<sup<k. Também, uma versão Bourgin-Yang do teorema de Borsuk-Ulam é apresentada. Como segunda parte desta tese, uma nova definição do grafo de Reeb R( f) de uma função suave f : MR com pontos críticos isolados, como um subcomplexo de M é dada. Para isto, um complexo 1-dimensional &Gamma; (f ) mergulhado em M e equivalente por homotopia a R( f ) é construído. Como consequência, mostramos que para toda função f sobre uma variedade com grupo fundamental finito, o grafo de Reeb de f é uma árvore. Se &pi;1(M) é um grupo abeliano, ou mais geralmente, um grupo amenable1, então R( f ) conterá no máximo um laço. Finalmente, é provado que o número de laços do grafo de Reeb de toda função sobre uma superfície Mg é estimado superiormente por g, o genus de Mg. Os resultados desta segunda parte estão publicados em (KALUBA; MARZANTOWICZ; SILVA, 2015). / Bartsch (BARTSCH, 1993) introduced a numerical cohomological index theory, known as the length, for G-spaces, where G is a compact Lie group. We present the length of G-spaces which are cohomology spheres and G = (Z2)k, (Zp)k or (S1)k, k &ge; 1. As consequences, we obtain a Borsuk-Ulam theorem in this context and we give a sucient condition for the existence of G-maps between a cohomological sphere and a representation sphere when G = (Zp)k. Also, a Bourgin-Yang version of the Borsuk-Ulam theorem is presented. As a second part of this thesis, a new definition of the Reeb graph R( f ) of a smooth function f : M &rarr; R with isolated critical points as a subcomplex of M is given. For that, a 1-dimensional complex &Gamma; ( f ) embedded into M and homotopy equivalent to R( f ) is constructed. As consequence it is shown that for every function f on a manifold with finite fundamental group, the Reeb graph of f is a tree. If &pi; 1 (M) is an abelian group, or more generally, an amenable group2, then R( f ) contais at most one loop. Finally, it is proved that the number of loops of the Reeb graph of every function on a surface Mg is estimated from above by g, the genus of Mg. The results of this second part is published in (KALUBA; MARZANTOWICZ; SILVA, 2015).

Nesta tese apresentamos uma metodologia de mapeamento capaz de gerar representações em termos de grafos para sistemas biológicos de conectividade complexa. Tais sistemas são inicialmente armazenados na forma de imagens digitais e em seguida submetidos a um pré-processamento com objetivo de padronizar as imagens. As imagens pré-processadas são então utilizadas para gerar modelos tridimensionais dos sistemas de interesse. Um algoritmo de propagação de rótulos é utilizado para extrair os esqueletos dos modelos volumétricos e estes esqueletos são por fim, representados por um grafo, composto por vértices e arestas. Os vértices e arestas desse grafo armazenam propriedades do sistema original, como posição, comprimento e diâmetro, bem como as características topológicas de tais sistemas. Finalmente, os grafos resultantes são estudados através da teoria das redes complexas, dentro de um contexto específico para cada sistema. Nossos procedimentos foram aplicados com sucesso a diferentes sistemas biológicos, como artérias caríotidas, árvores arteriais, estruturas mitocondriais e poros em amostras de solo. / In the present work, we developed a mapping methodology able to build a graph representation for biological branched systems. Initially, such systems are stored as digital images and then they undergo a pre-processing in order to standardize the images. The pre-processed imagens are used to build tridimensional models of the interested systems. A label-propagation algorithm is used to extract the skeleton from the volumetric models and these skeletons are then represented by a graph, composed by nodes and edges. The nodes and edges of these graphs store properties of the original system, such as spatial position, lengths and diameter, as well as the topological features of such systems. Finally, the graphs are studied by using the complex networks theory within a specific context for each system. Our procedures were apllied sucefully to different biological systems, such as carotid artery, arterial trees, mitocondrial structure and pores in soil samples.

O problema de corte consiste no corte de objetos maiores para produção de peças menores, de modo que uma certa função objetivo seja otimizada, por exemplo, a perda seja minimizada. O problema de empacotamento pode também ser visto como um problema de corte, onde as peças menores são arranjadas dentro dos objetos. Uma abordagem em grafo E/OU para a resolução de problemas de corte e empacotamento foi proposta inicialmente por Morabito (1989) para problemas de corte bidimensionais e, mais tarde, estendida para problemas tridimensionais (Morabito, 1992). Nesta abordagem foi utilizada uma técnica de busca híbrida, onde se combinou a busca em profundidade primeiro com limite de profundidade e a busca hill-climbing, utilizando-se heurísticas baseadas nos limitantes superiores e inferiores. Experiências computacionais mostraram a viabilidade de uso na prática desta abordagem. Mais tarde, Arenales (1993) generalizou esta a abordagem em grafo E/OU mostrando como diferentes problemas de corte poderiam ser resolvidos, independentemente da dimensão, formas dos objetos e itens, baseado em simples hipóteses, sem realizar, entretanto, estudos computacionais. O presente trabalho tem por objetivo estender a abordagem em grafo E/OU para tratar outros casos não analisados pelos trabalhos anteriores, tais como situações envolvendo diferentes processos de corte, bem como a implementação computacional de métodos baseados na abordagem em grafo E/OU, mostrando, assim, a versatilidade da abordagem para tratar diversas situações práticas de problemas de corte e sua viabilidade computacional. / The cutting problem consists of cutting larger objects in order to produce smaller pieces, in such a way as to optimizing a given objective function, for example, minimizing the waste. The packing problem can also be seen as a cutting problem, where the position that each smaller piece is arranged inside of the objects can be seen as the place it was cut from. An AND/OR-graph approach to solve cutting and packing problems was initially proposed by Morabito (1989) for two-dimensional cutting problem and, later, extended to threedimensional problems (Morabito, 1992). That approach uses a hybrid search, which combines depth-first search under depth bound and hill-climbing strategy. Heuristics were devised based on upper and lower bounds. Computational experiences demonstrated its practical feasibility. The AND/OR-graph approach was later generalized by Arenales (1993) based on simple hypothesis. He showed that different cutting problems Gould be solved using the AND/ORgraph approach, independently of the dimension and shapes. The main objective of this thesis is the practical extension of the AND/OR-graph approach to handle other cases not considered by previous works. It was considered different cutting processes, as well as the analysis of computational implementation, showing how can it be adapted to many classes of practical cutting and packing problems.

O teste de software é considerado uma atividade importante para a revelação de falhas. Apesar desta vantagem, tem sido pouco explorado no âmbito de aplicações de Realidade Virtual (RV). Dentre as lacunas existentes, a definição e automatização de critérios de teste de software para esse domínio foi identificada, uma vez que esses sistemas possuem características próprias que requerem definição ou adaptação de técnicas de teste, fazendo com que aplicações nesse domínio constituam sistemas de alta complexidade. Diante disso, o objetivo desta tese é apresentar uma abordagem denominada Virtual Reality-Requirements Specification and Testing (VR-ReST) que visa apoiar a especificação de requisitos de aplicações de RV com base na descrição de casos de uso e conceitos do domínio de RV e Grafo de Cena (GC), derivar requisitos de teste e gerar dados de teste a partir dos requisitos especificados. Além disso, é apresentado um apoio ferramental chamado de Virtual Requirements Specification and Testing (ViReST), que permite automatizá-las. A abordagem é composta por três módulos: (i) especificação dos requisitos por meio do auxílio de um modelo denominado Virtual Requirements Specification (ViReS); (ii) mapeamento dos requisitos por meio de uma linguagem semi-formal chamada Behavior Language Requirement Specification (BeLaRS) para garantir uma especificação padronizada; e (iii) geração automática dos requisitos de teste e dos dados de teste. Foi realizado um estudo de caso para avaliar a conformidade e a usabilidade da BeLaRS em auxiliar a especificação de requisitos de uma aplicação de RV. Além disso, também foi realizado um experimento para avaliar a eficácia da abordagem VR-ReST por meio da ferramenta ViReST. Usando teste de mutação neste último experimento, a abordagem VR-ReST alcançou um escore de mutação médio de 15,49% maior que o teste aleatório. Portanto, os resultados mostraram que a abordagem, bem como o apoio ferramental, podem auxiliar o projetista durante a atividade de especificação de requisitos e o testador na geração dos testes para aplicações de RV. / Software testing is considered an important activity towards fault revealing. Despite this advantage, it has been few explored within the scope of Virtual Reality (VR) applications. Among the existing gaps, the definition and automation of software testing criteria for this domain were identified, since these systems have their own characteristics that require definition or adaptation of testing techniques, making applications in this domain constitute highly complex systems. Therefore, a Virtual Reality-Requirements Specification and Testing (VR-ReST) approach is presented to perform the functional test of VR applications using Scene Graph (SG) concepts and a support tool called Virtual Requirements Specification And Testing (ViReST), which allows you to automate them. The approach is composed of three modules: (i) the first consists in specifying the requirements by means of a model called Virtual Requirements Specification (ViReS); (ii) the second involves mapping the requirements through a semi-formal language called Behavior Language Requirement Specification (BeLaRS) to ensure a standardized specification; and (iii) the third is the automatic generation of test requirements and test data. A case study was conducted to evaluate the compliance and usability of BeLaRS in assisting the requirements specification of an RV application. Also, an experiment was also carried out to evaluate the effectiveness of the VR-ReST approach using the ViReST tool. Using mutation testing in this latter experiment, the VR-ResT approach achieved a mean mutation score of 15.49% higher than the random testing. Therefore, the results showed that the approach, as well as tooling support, can assist the designer during the requirement specification activity and the tester in generating the tests for RV applications.

[pt] A otimização do desempenho dos modelos de aprendizado de máquina supervisionados representa um desafio constante, especialmente em contextos com conjuntos de dados de alta dimensionalidade ou com numerosos atributos correlacionados. Neste estudo, é proposto um método para o enriquecimento de conjuntos de dados tabulares, fundamentado na utilização de estatísticas provenientes de um grafo construído a partir da similaridade entre as instâncias presentes neste conjunto de dados, buscando capturar correlações estruturais entre esses dados. As instâncias assumem o papel de vértices no grafo, enquanto as conexões entre elas refletem sua similaridade. O conjunto de características originais (FO) é enriquecido com as estatísticas extraídas do grafo (FG) na busca pela melhora do poder preditivo dos modelos de aprendizado de máquina. O método foi avaliado em dez conjuntos de dados públicos de distintas áreas de conhecimento, em dois cenários distintos, sobre sete modelos de aprendizado de máquina, comparando a predição sobre o conjunto de dados inicial (FO) com o conjunto de dados enriquecido com as estatísticas extraídas do seu grafo (FO+FG). Os resultados revelaram melhorias significativas na métrica de acurácia, com um aprimoramento médio de aproximadamente 4,9 por cento. Além de sua flexibilidade para integração com outras técnicas de enriquecimento existentes, o método se apresenta como uma alternativa eficaz, sobretudo em situações em que os conjuntos de dados originais carecem das características necessárias para as abordagens tradicionais de enriquecimento com a utilização de grafo. / [en] The optimization of supervised machine learning models performancerepresents a constant challenge, especially in contexts with high-dimensionaldatasets or numerous correlated attributes. In this study, we propose a methodfor enriching tabular datasets, based on the use of statistics derived from agraph constructed from the similarity between instances in the dataset, aimingto capture structural correlations among the data. Instances take on the role ofvertices in the graph, while connections between them reflect their similarity.The original feature set (FO) is enriched with statistics extracted from thegraph (FG) to enhance the predictive power of machine learning models. Themethod was evaluated on ten public datasets from different domains, in twodistinct scenarios, across seven machine learning models, comparing predictionon the initial dataset (FO) with the dataset enriched with statistics extractedfrom its graph (FO+FG). The results revealed significant improvements inaccuracy metrics, with an average enhancement of approximately 4.9 percent. Inaddition to its flexibility for integration with existing enrichment techniques,the method presents itself as a effective alternative, particularly in situationswhere original datasets lack the necessary characteristics for traditional graph-based enrichment approaches.

[pt] Neste trabalho descreve-se um procedimento para o desenvolvimento de modelos reduzidos de sistemas mecânicos lineares baseado na técnica dos Grafos de Ligação. A partir da análise da estrutura topológica dos principais modelos mecânicos descritos por esta técnica estabeleceu- se uma nova formulação que possibilita a obtenção de variadas formas de representação matemática e definiu-se um grafo genérico, formado por hipercampos armazenadores e dissipadores de energia, onde se encontram as matrizes que caracterizam a dinâmica do sistema. Sobre o grafo genérico, com algumas restrições, foi aplicada uma metodologia de normalização e desacoplamento dos campos armazenadores, com base nos seus modos locais, o que permitiu a criação de um grafo particionado, acoplado através do campo dissipador. A análise dos coeficientes do campo de acoplamento leva ao grafo de Ligação Reduzido do sistema. Comprova-se a validade do procedimento através de exemplos de fácil compreensão. / [en] It is described in this work a Bond Graph based procedure to the development of linear mechanical systems reduced order models. From the analysis of the topological structure of the main mechanical models represented by this technique it was established a new formulation that permits to obtain several mathematical representation forms and it was defined a generic graph, formed by energy storage and dissipative hiperfields, where the matrices that characterizes the system dynamics are included. On the generic graph, with some constraints, it was applied a methodology for the normalization and decoupling of the energy storage fields, based on its local modes, that permits to develop a partioned graph, couplec through the dissipative field. The analysis of the coupling field coefficients permits to define the system Reduced Bond Graph. The procedure was comproved by easy comprehensive examples.

[pt] O crescente uso de veículos aéreos não tripulados (VANTs) em diversos setores da sociedade é fruto de avanços da tecnologia. Por sua vez, a ampliação de aplicações de VANTs traz consigo a necessidade de aumento de robustez destes sistemas, especialmente em ambientes compartilhados com o ser humano. A presente dissertação aborda o desenvolvimento de uma plataforma para testes de veículos multicópteros, com o objetivo de contribuir para o processo de desenvolvimento e implementação de drones, permitindo sua movimentação em torno dos seus graus de liberdade de rotação e realizando medições de atitude e força geradas pelo sistema, sem colocar o veículo ou seu operador em risco. Todos os dados adquiridos pela plataforma são transmitidos para um computador, onde foi desenvolvida uma interface virtual para sua visualização em tempo real, além de permitir armazenamento para pós-processamento e análises futuras. Também apresenta-se e discute-se o desenvolvimento do simulador de trajetórias proposto, que mostra o deslocamento do veículo em função da sequência de comandos fornecida, com base nos dados adquiridos pela plataforma. No intuito de se propiciar um melhor entendimento do funcionamento do sistema aqui desenvolvido, é apresentado um estudo detalhado dos subsistemas que compõem um multicóptero, bem como do processo de modelagem dinâmica de um veículo quadricóptero, por meio da técnica de grafos de ligação. A modelagem do veículo é complementada com a identificação de parâmetros fundamentais para a implementação do modelo, sendo discutidos métodos para identificação de parâmetros inerciais do veículo e parâmetros dinâmicos do sistema motopropulsor. / [en] The growing use of unmanned aerial vehicles (UAVs) in various sectors of society is a result of advances in technology. In turn, the expansion of UAV applications brings with it the need to increase the robustness of these systems, especially in environments shared with humans. and comes together with the need for increased robustness due to its use in shared environments with humans. This dissertation approaches the development of a platform for testing multicopter vehicles aiming at assisting the process of developing and implementing drones, allowing movements around their rotational degrees of freedom and making measurements of attitude and forces generated by the system, without putting the vehicle or its operator at risk. All data acquired by the platform is transmitted to a computer, where a virtual interface was developed to provide real time visualization, in addition to allowing data storage for post-processing and future analysis. The development of the proposed trajectory simulator is also presented and discussed, that shows the displacement of the vehicle as a function of the sequence of commands provided, based on the acquired data. Aiming at allowing a better understanding of the functioning of the developed system, a detailed study of the subsystems that compose a multicopter is presented, as well as the process of dynamic modeling of a quadcopter vehicle, by using bond graph technique. The modeling of the vehicle is complemented with the identification of fundamental parameters for the model implementation, such as methods for the identification of inertial parameters of the vehicle and dynamics of the powertrain system.

[pt] A interpretação manual de um horizonte sísmico é um processo muito custoso em termos de tempo de trabalho do intérprete, o que incentiva a pesquisa de métodos automáticos, ou semi automáticos, de rastreamento. Dentre as propostas existentes baseadas em correlação, uma limitação conhecida é o uso de abordagens locais para definir as amostras pertencentes ao horizonte rastreado. Esse tipo de abordagem possui bom desempenho em dados onde não há a presença de falhas sísmicas, porém, nas regiões de baixa coerência, característica das regiões ruidosas ou de falhas, ao tomar uma decisão local o rastreador fica suscetível à propagação de erro. O objetivo deste trabalho é avaliar o uso de algoritmos de menor caminho em grafos para a solução do problema de rastreamento de horizontes sísmicos, afim de propor um método de caráter global que seja robusto a diferentes feições sísmicas. / [en] The manual interpretation of a seismic horizon is a time consuming process, which drives the research for automatic or semi automatic tracking methods. Among the known propositions that use correlation, there is a common limitation: the usage of local approaches to determine which samples belong to the horizon. This kind of approach performs well in data where there are no seismi faults. However, by using only local information, it is prone to error propagation in low coherency areas, which usualy corresponds to fault regions. The goal of this work is to evaluate the performance of shortest path algorithms as a solution for the horizont tracking problem. It intends to propose a global method that is robust to different seismic features.