[pt] Há muitas aplicações de realidade virtual que requerem navegação em ambientes 3D. Em geral, esta facilidade é oferecida permitindo que o usuário controle todos os seis graus de liberdade da câmera virtual. No entanto, dessa forma é difícil, mesmo para usuários experientes, chegar a áreas de interesse com movimentos suaves e livres de colisão. Torna-se necessário prover uma navegação assistida, onde o usuário guia a câmera mais facilmente, sem restringir sua exploração do ambiente. Além disso, é interessante prover uma navegação totalmente automática, onde o usuário seleciona um alvo e o sistema calcula um caminho suave e livre de colisões através do ambiente. Este trabalho propõe uma solução específica para navegação em modelos usados para simulação numérica de reservatórios naturais de petróleo, baseada em grafos de guia probabilísticos. Utilizados comumente em aplicações de robótica, grafos de guia probabilísticos visam capturar, através de uma amostragem aleatória, a conectividade das áreas livres da cena, sendo construídos em pré-processamento e consultados em tempo de execução. Este trabalho propõe um algoritmo de construção de grafo de guia específico para reservatórios e duas técnicas para utilizar o grafo obtido como base para prover navegação automática e navegação assistida. / [en] There are many virtual reality applications that require navigation on 3D environments. Usually, this feature is offered by allowing the user to control all the six degrees of freedom of the virtual camera. However, it is difficult in this way, even for experienced users, to reach areas of interest with smooth and collision-free paths. It becomes necessary to provide an assisted navigation, in which the user guides the camera more easily, without restricting the environment exploration. Moreover, it is interesting to provide a fully automatic navigation, in which the user selects a target and the system computes a smooth, collision-free path throughout the environment. This work proposes a specific solution for navigation on models used in numerical simulations of black oil reservoirs, based on probabilistic roadmaps. Commonly used in robotics applications, probabilistic roadmaps tend to capture, by random sampling, the conectivity of the free space of the scene, being constructed in a pre-processing stage and queried in execution time. This work proposes a roadmap construction algorithm specific to reservoirs and two techniques to use the obtained roadmap as the basis to provide assisted and automatic navigation.

O tema central deste trabalho é o estudo de problemas sobre caminhos mais longos em grafos, de pontos de vista tanto estrutural como algorítmico. A primeira parte tem como foco o estudo de problemas motivados pela seguinte questão levantada por T. Gallai em 1966: é verdade que em todo grafo conexo existe um vértice comum a todos os seus caminhos mais longos? Hoje, já se conhecem diversos grafos conexos cuja intersecção de todos os seus caminhos mais longos é vazia. Entretanto, existem classes de grafos para as quais a resposta à pergunta de Gallai é afirmativa. Nessa linha, apresentamos alguns resultados da literatura e duas novas classes que obtivemos: os grafos exoplanares e as 2-árvores. Motivado por esse problema, nos anos 80, T. Zamfirescu formulou a seguinte pergunta que permanece em aberto: é verdade que em todo grafo conexo existe um vértice comum a quaisquer três de seus caminhos mais longos? Apresentamos, além de alguns resultados conhecidos, uma prova de que a resposta é afirmativa para grafos em que todo bloco não trivial é hamiltoniano. Notamos que esse último resultado e o acima mencionado para grafos exoplanares generalizam um teorema de M. Axenovich (2009) que afirma que quaisquer três caminhos mais longos em um grafo exoplanar têm um vértice em comum. Finalmente, mencionamos alguns outros resultados da literatura relacionados com o tema. Na segunda parte, investigamos o problema de encontrar um caminho mais longo em um grafo. Este problema é NP-difícil para grafos arbitrários. Isto motiva investigações em duas linhas a respeito da busca de tais caminhos. Pode-se procurar classes especiais de grafos para as quais existem algoritmos polinomiais, ou pode-se abrir mão da busca de um caminho mais longo, e projetar um algoritmo eficiente que encontra um caminho cujo comprimento esteja próximo do comprimento de um mais longo. Nesse trabalho estudamos ambas as abordagens e apresentamos alguns resultados da literatura. / The central theme of this thesis is the study of problems related to longest paths in graphs, both from a structural and an algorithmic point of view. The first part focuses on the study of problems motivated by the following question raised by T. Gallai in 1966: is it true that every connected graph has a vertex common to all its longest paths? Today, many connected graphs in which all longest paths have empty intersection are known. However, there are classes of graphs for which Gallais question has a positive answer. In this direction, we present some results from the literature, as well as two new classes we obtained: outerplanar graphs and 2-trees. Motivated by this problem, T. Zamfirescu, in the 80s, proposed the following question which remains open: is it true that every connected graph has a vertex common to any three of its longest paths? We present, in addition to some known results, a proof that the answer to this question is positive for graphs in which all non-trivial blocks are Hamiltonian. We note that this result and the one mentioned above for outerplanar graphs generalize a theorem of M. Axenovich (2009) that states that any three longest paths in an outerplanar graph have a common vertex. Finally, we mention some other related results from the literature. In the second part, we investigate the problem of finding a longest path in a graph. This problem is NP-hard for arbitrary graphs. This motivates investigations in two directions with respect to the search for such paths. We can look for special classes of graphs for which the problem is polynomially solvable, or we can relinquish the search for a longest path and design an efficient algorithm that finds a path whose length is close to that of a longest path. In this thesis we study both approaches and present some results from the literature.

Uma decomposição de um grafo G é um conjunto D = {H_1,... , H_k } de subgrafos de G dois-a-dois aresta-disjuntos que cobre o conjunto das arestas de G. Se H_i é isomorfo a um grafo fixo H, para 1<=i<=k, então dizemos que D é uma H-decomposição de G. Neste trabalho, estudamos o caso em que H é um caminho de comprimento fixo. Para isso, primeiramente decompomos o grafo dado em trilhas, e depois fazemos uso de um lema de desemaranhamento, que nos permite transformar essa decomposição em trilhas numa decomposição somente em caminhos. Com isso, obtemos resultados para três conjecturas sobre H-decomposição de grafos no caso em que H=P_\\ell é o caminho de comprimento \\ell. Dois desses resultados resolvem versões fracas das Conjecturas de Kouider e Lonc (1999) e de Favaron, Genest e Kouider (2010), ambas para grafos regulares. Provamos que, para todo inteiro positivo \\ell, (i) existe um inteiro positivo m_0 tal que se G é um grafo 2m\\ell-regular com m>=m_0, então G admite uma P_\\ell-decomposição; (ii) se \\ell é ímpar, existe um inteiro positivo m_0 tal que se G é um grafo m\\ell-regular com m>=m_0, e G contém um m-fator, então G admite uma P_\\ell-decomposição. O terceiro resultado diz respeito a grafos altamente aresta- conexos: existe um inteiro positivo k_\\ell tal que se G é um grafo k_\\ell-aresta-conexo cujo número de arestas é divisível por \\ell, então G admite uma P_\\ell-decomposição. Esse resultado prova que a Decomposition Conjecture de Barát e Thomassen (2006), formulada para árvores, é verdadeira para caminhos. / A decomposition of a graph G is a set D = {H_1,...,H_k} of pairwise edge-disjoint subgraphs of G that cover the set of edges of G. If H_i is isomorphic to a fixed graph H, for 1<=i<=k, then we say that D is an H-decomposition of G. In this work, we study the case where H is a path of fixed length. For that, we first decompose the given graph into trails, and then we use a disentangling lemma, that allows us to transform this decomposition into one consisting only of paths. With this approach, we tackle three conjectures on H-decomposition of graphs and obtain results for the case H=P_\\ell is the path of length \\ell. Two of these results solve weakenings of a conjecture of Kouider and Lonc (1999) and a conjecture of Favaron, Genest and Kouider (2010), both for regular graphs. We prove that, for every positive integer \\ell, (i) there is a positive integer m_0 such that, if G is a 2m\\ell-regular graph with m>=m_0, then G admits a P_\\ell-decomposition; (ii) if \\ell is odd, there is a positive integer m_0 such that, if G is an m\\ell-regular graph with m>=m_0 containing an m-factor, then G admits a P_\\ell-decomposition. The third result concerns highly edge-connected graphs: there is a positive integer k_\\ell such that if G is a k_\\ell-edge-connected graph whose number of edges is divisible by \\ell, then G admits a P_\\ell-decomposition. This result verifies for paths the Decomposition Conjecture of Barát and Thomassen (2006), on trees.

São Paulo, metrópole global e do terciário avançado, tem conhecido, sobretudo nas últimas três décadas, a efetivação de operações urbanas em praticamente todas as regiões da cidade. Na escala municipal, a região compreendida pelos distritos do Butantã, Rio Pequeno, Morumbi e Vila Sônia torna-se objeto da composição desse instrumento urbanístico, a partir da chamada Operação Urbana Consorciada Vila Sônia (OUCVS). As reestruturações e modificações postas nos variados projetos da OUCVS estão francamente relacionadas ao lugar que a região ocupa na metrópole, cuja forma e conteúdo são herdeiros dos caminhos e fronteiras pregressos (reafirmando formas pregressas da propriedade), tanto em relação aos fluxos viários quanto às possibilidades econômicas do contemporâneo mercado imobiliário e seu crescente interesse por certas áreas consideradas estratégicas no município de São Paulo. Discernindo tal estratégia do espaço, trata-se também em considerar a reprodução das relações sociais de produção, assentando-se a espacialidade desse fenômeno nas tessituras do quotidiano; este, em sua materialidade, conduz ao necessário tratamento, neste trabalho, das camadas e classes sociais, bem como suas complexas tramas de relações. Assim, admitindo o desnível constante entre a(o) política(o) e a economia política, operados no corpo da reprodução das relações sociais de produção, sugerimos a consideração da política média como o devir dessa forma social, cujo fundamento se ancora em reiterativa alienação, mistificação, reificação e fetichização. Reconhecendo tais fundamentos, poder-se-ia abrir vias no intento da urgente superação do discurso, do pensamento e das práticas ancoradas ao Estado e a essa economia. / São Paulo, global metropolis and including the advanced tertiary sector, has known, especially in the last three decades, the realization of urban operations in virtually all regions of the city. At the municipal level, the region comprising the districts of Butantã, Rio Pequeno, Morumbi and Vila Sônia becomes the object for the composition of this urban instrument, from the called Operação Urbana Consorciada Vila Sônia (OUCVS). The restructurings and changes which are put in varied projects for the OUCVS are frankly related to the place occupied by the region in the metropolis, whose form and content are the heirs of the paths and borders of its previous history (reaffirming stunted forms of ownership); that is both in relation to road flows as the economic possibilities of contemporary housing market and its growing interest in certain areas considered strategic in São Paulo. Discerning such a strategy space, it is also to consider the reproduction of social relations of production, bottoming spatiality of this phenomenon in everyday tessitura, who, in its materiality, leading to necessary treatment, in this work, for the layers and social classes as well as their complex webs of relationships. Thus, assuming the constant gap between the political and the political economy, both operated in the body of the reproduction of social relations of production, we suggest consider the middle politics as the average social becoming in this way, whose foundation is anchored in reiterative alienation, mystification, reification and fetishization. Recognizing such foundations, we should pave the way with the intent of the urgent overcoming of the speech, thought and practices anchored to this State and economy.

Orientadora: Gordana Manic / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Ciência da Computação, 2013

Orientador: Gustavo Sousa Pavani / Dissertação (mestrado) - Universidade Federal do ABC. Programa de Pós-Graduação em Ciências da Computação, 2013

A tecnologia de virtualização de redes é um novo paradigma de redes que permite a múltiplas redes virtuais (VNs) compartilharem de uma forma eficiente e eficaz a mesma rede de infraestrutura denominada rede de substrato (SN). A implementação e o desenvolvimento de novos protocolos, testes de novas soluções e arquiteturas para a Internet atual e do futuro podem ser tratadas por meio da virtualização de redes. Com a virtualização de redes surge um desafio denominado problema VNE. O problema de virtualização de redes embutidas (VNE) consiste em realizar o mapeamento dos nós virtuais e o mapeamento dos enlaces virtuais sobre uma rede de substrato (SN). O problema é conhecido como NP-Hard e a sua solução é realizada por meio de algoritmos heurísticos e aproximados que realizam o mapeamento de nós e enlaces virtuais em dois estágios de forma independente ou coordenada. A presente tese tem o objetivo de resolver o mapeamento dos enlaces virtuais do problema VNE com a utilização da álgebra de caminhos. A solução apresentada fornece o melhor desempenho quando comparada com as demais soluções de virtualização de redes encontradas na literatura. Os resultados obtidos nas simulações para o problema VNE foram avaliados e analisados com a utilização do algoritmo desenvolvido nesta tese denominado Path Algebra for Virtual Link Mapping (PAViLiM), que utiliza a álgebra de caminhos para realizar o mapeamento de enlaces virtuais para caminhos na rede de substrato. A álgebra de caminhos é poderosa e flexível. Tal flexibilidade permite que ocorra uma exploração detalhada do espaço de soluções e a identificação do melhor critério e política que devem ser utilizados para a virtualização de redes. / The network virtualization technology is a new paradigm of network that allows multiple virtual networks (VNs) share in an efficient and effective way the same network infrastructure called substrate network (SN). The implementation and the development of new protocols, testing of new solutions and architectures for current and future Internet can be addressed through network virtualization. With the network virtualization arises a challenge called VNE problem. The problem of virtual network embedded (VNE) is to conduct the mapping of the virtual nodes and mapping of the virtual links over a substrate network (SN).The problem is known as NP-Hard and its solution is accomplished by means of approximate and heuristic algorithms that perform the mapping of virtual nodes and links in two stages independently or coordinated. This thesis aims to solve the mapping of virtual links for VNE problem using the paths algebra. The solution presented provides the best performance when compared with other networks virtualization solutions from the literature. The results of simulation for the VNE problem were evaluated and analyzed using the algorithm developed in this thesis called Path Algebra for Virtual Link Mapping (PAViLiM), which uses the paths algebra to perform the mapping of virtual links to paths in substrate network. The paths algebra is powerful and flexible. This flexibility allows the occurrence of a detailed exploration for identifying the best solutions and political criteria to be used for network virtualization.

Nos últimos anos, a área de robôs aéreos vêm se tornando cada vez mais importantes no dia-a-dia, em diversos usos, em que se pode destacar: segurança pública e particular, agricultura de precisão, registro fotográfico de eventos, serviços de entregas e apoio a diversas outras áreas, como monitoramento ambiental.Para que tais robôs aéreos possam cumprir suas mais variadas tarefas, faz-se necessária uma etapa de planejamento de movimento, que consiste em encontrar um caminho factível entre a postura atual e uma postura final (também chamada de postura alvo ou meta) do robô aéreo. Neste trabalho, a tarefa de planejamento de movimento é abordada para o caso tridimensional em ambientes dinâmicos, nos quais não se assume que todos os obstáculos permanecerão fixos ao longo do trajeto. Derivado da Teoria de Campos Potenciais Harmônicos, os Campos Potenciais Modificados (CPM) permitem a distorção do campo potencial favorecendo uma direção específica de chegada a postura meta. Tais CPM resultam em um planejador de movimentos para ambientes dinâmicos e multidimensionais, em especial, o caso tridimensional. / In recent years, aerial robots have become increasingly important in day-to-day situations, in several uses, in which we can highlight: public and private security, precision agriculture, photographic record of events, delivery and support to several other areas, such as environmental monitoring. In order for aerial robots perform their broad range of tasks, a motion planning step is necessary. Motion planning consists in finding a feasible path between the current posture and a final posture (also called target posture or goal) of a robot. In this work, the task of motion planning is approached in three-dimensional and dynamic environments, in which it is not assumed that all the obstacles will remain fixed along the trajectory. Derived from Harmonic Potential Field Theory, Modified Potential Fields (MPF) allows a controlled distortion of the potential field, as an example, towards a specific direction of arrival to the target posture. Such MPF results in a motion planner for dynamic and multidimensional environments, especially the three-dimensional case.

Orientador: Luís Roberto Almeida Gabriel Filho / Coorientador: Luiz Fernando Sommaggio Coletta / Coorientador: Camila Pires Cremasco Gabriel / Resumo: O presente trabalho buscou identificar padrões na produção de cana de por meio da utilização de Inteligência Artificial. Para tanto, foi realizada coleta de informações de fontes secundárias, com dados estatísticos fornecidos por órgãos públicos sobre a área cultivada e a produção de cana de açúcar, índices como pluviométricos e de temperatura e o tipo de solo dos municípios do estado de São Paulo, no ano de 2017, por meio de pesquisa documental. Com a utilização dos métodos Floresta dos Caminhos Ótimos (OPF), K-means e Fuzzy C-means (FCM) buscou-se identificar clusters, ou padrões, que representem essas características produtivas. Além disso, o trabalho testou a utilização do algoritmo OPF como ferramenta de apoio à decisão no setor agroindustrial e fez a comparação do método com os agrupadores de padrões K-means e FCM. Após o processamento dos dados foi possível identificar padrões na produção de cana de açúcar pelos três algoritmos, sendo que o OPF proporcionou resultados muito parecidos com o K-means e FCM, confirmando a eficiência do método. Além disso, foi possível identificar, no ano de 2017, um padrão de produção com municípios com alta produtividade, grandes áreas destinadas a produção de cana de açúcar e produção da cultura, com temperatura média alta e índices pluviométricos baixos. Os municípios que possuem pequenas áreas com plantação de cana de açúcar possuem uma variabilidade muito grande em resultados de produtividade. O padrão de município com baixa produtivi... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: The present work sought to identify patterns in sugarcane production through the use of Artificial Intelligence. For this purpose, information was collected from secondary sources, with statistical data provided by public agencies on cultivated area and sugarcane production, rainfall and temperature indices, and the soil type of the municipalities of the State of São Paulo, in the year 2017, through documentary research. Using Optimum-Path Forest (OPF), K-means and Fuzzy C-means (FCM) methods, the aim was to identify clusters, or patterns, that represent these productive characteristics. In addition, the work tested the use of OPF algorithm as a decision support tool in the agribusiness sector and compared the method with the K-means and FCM standards groupers. After data processing, it was possible to identify patterns in sugarcane production by the three algorithms, and OPF provided results very similar to K-means and FCM, confirming the efficiency of the method. In addition, it was possible to identify, in the year 2017, a production pattern of municipalities with high productivity, large areas destined to the production of sugar cane and crop production, with high average temperature and low rainfall. Municipalities that have small areas with sugar cane plantation have a very large variability in productivity results. The municipal pattern with low productivity is accompanied by very low average temperature, very high rainfall rates and soils of the type Cambisols, Neosols and Spodosols. The soil type pattern that provided the highest productivity for the municipalities was the Oxisol. / Mestre

The tourism is one of the great activities that they collaborate with the world development, growing in a compared way the sections as informatization and telecommunications and it is one of the activities that more employments and profits generate in the world. Studies accomplished on the municipal district of Santiago and area, involving historical, cultural, educational, tourist and social aspects, they verified the possibility to create routes, trails and kindred stops that the characteristics and potentialities of the municipal district were disclosed and at the same time it rescued its history. Knowing that the rural tourism is an activity in growth in the whole world and source of generation of income, the City halls of the municipal districts of Santiago, São Miguel das Missões, Capão do Cipó e Bossoroca are developing the Project Tourist " Roads of Santiago from Brazil " and the present work seeks to develop a methodology using the geoprocessing techniques - SIG and GPS, applied to the rural tourism, to elaborate a rural tourist route prioritizing the historical colonization of the involved municipal districts as well as the valorization of the natural way, where he/she/it looks for to approach the tourist of the contact with the nature. The application of these geoprocessing techniques, Systems and Geographical Information and System of Global Positioning, as support tools in the elaboration of the tourist route demonstrated to be a necessary and effective tool, because it represents gain of time and economy for the implantation of the project. The pilgrim, making use of a GPS, it will travel the road, using the maps here developed and he will have in hands the whole necessary tool for its orientation. The application of these geoprocessing techniques is recommended in works that demand a speed and precision of data, facilitating the taking of decisions, as well as aiding in the implantation of new projects. / O turismo é uma das grandes atividades que colaboram com o desenvolvimento mundial, crescendo de forma equiparada a setores como informatização e telecomunicações sendo que é uma das atividades que mais empregos e lucros gera no mundo. Estudos realizados sobre o município de Santiago e região, envolvendo aspectos históricos, culturais, educacionais, turísticos e sociais, verificaram a possibilidade de se criar roteiros, trilhas e paradas afim de que as características e potencialidades do município fossem divulgadas e ao mesmo tempo resgatasse a sua história. Sabendo que o turismo rural é uma atividade em crescimento no mundo todo e fonte de geração de renda, as Prefeituras dos municípios de Santiago, São Miguel das Missões, Capão do Cipó e Bossoroca estão desenvolvendo o Projeto Turístico Caminhos de Santiago do Brasil . O presente trabalho possui como objetivo desenvolver uma metodologia utilizando as técnicas de geoprocessamento - SIG e GPS, aplicados ao turismo rural, para elaborar um roteiro turístico rural priorizando a colonização histórica dos municípios envolvidos, bem como a valorização do meio natural, onde se busca aproximar o turista do contato com a natureza. A aplicação destas técnicas de geoprocessamento, Sistemas e Informações Geográficas e Sistema de Posicionamento Global, como ferramentas de apoio na elaboração do roteiro turístico demonstrou ser uma ferramenta necessária e eficaz, pois representa ganho de tempo e economia para a implantação do projeto. O peregrino, fazendo uso de um GPS, irá percorrer o caminho, utilizando os mapas aqui desenvolvidos e terá em mãos toda a ferramenta necessária para sua orientação. Recomenda-se a aplicação destas técnicas de geoprocessamento em trabalhos que exijam uma rapidez e precisão de dados, facilitando a tomada de decisões, bem como auxiliando na implantação de novos projetos.