Made available in DSpace on 2014-06-12T18:31:43Z (GMT). No. of bitstreams: 2 arquivo8519_1.pdf: 1184960 bytes, checksum: bacaee589325d0137cd7cd316fb23a67 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2003 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / O trabalho aqui apresentado consiste no estudo e plicação da teoria relacionada com conjuntos co-geradores de uma matróide, desenvolvida por Alfred Lehman e Jack Edmonds, num jogo chamado Bridge-it. Para tanto, exibimos um algoritmo que encontra, dada uma matróide, um subconjunto maximal de seus elementos, A0, o qual pode ser particionado em k subconjuntos independentes co-geradores, disjuntos, e geradores de A0. Este conjunto A0 está fortemente relacionado com as estratégias dos jogadores

[pt] Redes veiculares (VANETs — Vehicle Ad Hoc NETworks) constituem um caso especial de redes ad hoc em que os nós são veículos equipados com uma interface de comunicação sem fio. Esses veículos podem se mover a velocidades elevadas, e a transmissão de dados em cenários urbanos pode ser facilmente bloqueada por prédios ou outros obstáculos. Tais fatores contribuem para tornar a comunicação inter-veicular intermitente, e dificultar o roteamento de pacotes. Um dos principais desafios dos protocolos de roteamento em VANETs é evitar as ruas onde o volume de tráfego esteja baixo, uma vez que a escassez de veículos nessas ruas tende a impossibilitar a propagação de pacotes através delas. Por esse motivo, a informação sobre o volume de tráfego em cada rua é fundamental para se determinar a melhor rota entre dois veículos. Especificamente em cenários urbanos, a mudança de estado dos semáforos provoca uma flutuação do tráfego de veículos ao longo do tempo. Em vista disso, esta tese propõe o TLAR (Traffic Light Aided Routing), um novo algoritmo de roteamento para VANETs que explora a variação de estado dos semáforos para inferir quais ruas oferecerão uma maior probabilidade de sucesso de propagação de pacotes. Resultados de simulação mostram que o algoritmo apresenta um bom desempenho comparado ao de propostas existentes. / [en] VANETs (Vehicle Ad Hoc NETworks) are a special case of mobile ad hoc networks where vehicles are equiped with wireless communication interfaces. These vehicles may move at high speeds and data transmission in urban scenarios may easily be blocked by buildings and other sort of obstacles. Such factors contribute to make inter-vehicle communication intermitent and packet routing more difficult. One of the main challenges faced by routing protocols is avoiding low-traffic streets, where the lack of vehicles tend to make packet forwarding impossible. For this reason, traffic information on each street is essential for the computation of the best route between any given two vehicles. Specifically in urban scenarios, traffic light transitions cause significant fluctuations on traffic flow over time. Given this fact, this thesis proposes TLAR (Traffic Light Aided Routing), a new routing algorithm for VANETs that exploits traffic light transition timings in order to determine which streets will offer the greatest probabilities for successful packet forwarding. Simulation results indicate a good performance of this algorithm compared to existing approaches.

Orientador: André Santanchè / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-24T12:38:30Z (GMT). No. of bitstreams: 1 Miranda_EduardodePaula_M.pdf: 3021722 bytes, checksum: 93a67943f673753c003a021060a55b6c (MD5) Previous issue date: 2013 / Resumo: Um grande número de estudos em biologia, incluindo os que envolvem a reconstrução de árvores filogenéticas, resultam na produção de uma enorme quantidade de dados -- por exemplo, descrições fenotípicas , matrizes de dados morfológicos , árvores filogenéticas, etc. Biólogos enfrentam cada vez mais o desafio e a oportunidade de efetivamente descobrir conhecimento a partir do cruzamento e comparação de vários conjuntos de dados, nem sempre conectados e integrados. Neste trabalho, estamos interessados em um contexto específico da biologia em que biólogos aplicam ferramentas computacionais para construir e compartilhar descrições digitais dos seres vivos. Nós propomos um processo que parte de fontes de dados fragmentadas, que nós mapeamos para grafos, em direção a uma plena integração das descrições através de ontologias. Os bancos de dados de grafos intermediam o processo de evolução. Eles são menos dependentes de esquema e, uma vez que ontologias também são grafos, o processo de mapeamento do grafo inicial para uma ontologia torna-se uma sequência de transformações no grafo. Nossa motivação parte da ideia de que a conversão de descrições fenotípicas em uma rede de relações e a busca de conexões entre elementos relacionados irá aumentar a capacidade de resolver problemas mais complexos suportados por computadores. Este trabalho detalha os princípios de concepção por trás do nosso processo e duas implementações práticas como prova de conceito / Abstract: A large number of studies in biology, including those involving phylogenetic trees reconstruction, result in the production of a huge amount of data -- e.g., phenotype descriptions, morphological data matrices, phylogenetic trees, etc. Biologists increasingly face a challenge and opportunity of effectively discovering useful knowledge crossing and comparing several pieces of information, not always linked and integrated. In this work, we are interested in a specific biology context, in which biologists apply computational tools to build and share digital descriptions of living beings. We propose a process that departs from fragmentary data sources, which we map to graphs, towards a full integration of descriptions through ontologies. Graph databases mediate this evolvement process. They are less schema dependent and, since an ontology is also a graph, the mapping process from the initial graph towards an ontology becomes a sequence of graph transformations. Our motivation stems from the idea that transforming phenotypical descriptions in a network of relationships and looking for links among related elements will enhance the ability of solving more complex problems supported by machines. This work details the design principles behind our process and two practical implementations as proof of concept / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

El 54% de la población mundial vive ya en torno a núcleos de población que llamamos ciudades, por lo que su estudio nos enseña la forma en que piensa y se desarrolla el propio ser humano. Un análisis de las relaciones espaciales que se producen en entornos urbanos reales requieren un procesamiento de dichas relaciones en paralelo. Con el fin de representar y analizar estas relaciones espaciales complejas, los especialistas en urbanismo han empezado a utilizar modelos basados en redes complejas. Las redes emergen como un nuevo modelo más acorde con el problema de la complejidad organizada que es una ciudad. Otro aspecto esencial unido a las ciudades es que se han convertido en unas entidades productoras y creadoras de datos, tanto físicos como virtuales. Un estudio serio de la ciudad significa, por tanto, un estudio de los datos que en ella se generan o se encuentran. Dentro de la moderna teoría de redes, un concepto fundamental y muy estudiado en la bibliografía en las últimas décadas es el de la centralidad de la red. La centralidad consiste en determinar cuantitativamente la importancia de cada nodo dentro de la red, dependiendo del criterio que se adopte en cuanto a lo que consideramos por “importante”. Existen unas medidas clásicas de centralidad en redes complejas, como son la centralidad de grado, de cercanía, de intermediación y basadas en el vector propio. Todas estas medidas solo tienen en cuenta la topología de la red para determinar un valor y una clasificación de los nodos en orden de importancia. Cuando aplicamos estas centralidades a las redes urbanas nos encontramos con el problema de la densidad de grado uniforme que tienen estas redes, lo que hace que no sean adecuadas para la realidad que representan las ciudades. En esta memoria, se han implementado un conjunto de medidas de centralidad para redes urbanas, con la principal característica que tienen en cuenta no solo la topología de la red sino la influencia de la cuantía de los datos presentes en la misma. De esta forma, cuando estudiamos la centralidad de una red urbana, tenemos en cuenta de forma determinante qué datos analizamos y su influencia en la red. Más concretamente, se han implementado tres medidas de centralidad basadas en el concepto de PageRank, introducido por Page y Brin en el conocido buscador Google, que clasifican los nodos de una red urbana en orden de importancia, tanto atendiendo a su conectividad como a los datos asociados a cada nodo. Se ha implementado una medida de centralidad basada en la clásica medida current-flow betweenness, un tipo concreto de medida de intermediación que estudia la distribución de flujos por una red. Por último, se ha implementado una medida de centralidad para redes urbanas basad en el concepto de centralidad basada en el vector propio, donde la idea básica es que un nodo es importante si sus conexiones o vecinos son importantes. Al final de la memoria se establece una pequeña comparativa entre las medidas basadas en el vector PageRank y vector propio, ya que todas se basan en el cálculo de un vector propio del valor propio dominante de una cierta matriz que resume tanto la conectividad de la red como sus datos.

[pt] O objetivo deste trabalho é o de estudar propriedades geométricas de curvas poligonais genéricas. Inicialmente abordamos resultados clássicos para curvas quanto à sua curvatura total no caso discreto e discutimos aqueles pertinentes a nós poligonais. Também é feito o estudo do Grafo de Maxwel para poligonais. No caso, temos uma interessante relação entre a natureza do grafo quanto ao seu número de componentes e à condição de a poligonal ser ou não convexa. / [en] The aim of this work is to study geometrical properties of generic polygonal lines. We begin with some classical results for curves with respect to total curvature, in the discrete case, and discuss results related to polygonal knots. Maxwell graphs are also considered for polygonal lines: We study the relation between the number of components of the graph and the convexity of the polygonal line.

No description available.

[pt] A montagem de fragmentos de sequências biológicas é um problema fundamental na bioinformática. Na montagem de tipo De Novo, onde não existe um genoma de referência, é usada a estrutura de dados do grafo de Bruijn para auxiliar com o processamento computacional. Em particular, é necessário considerar um conjunto grande de k-mers, substrings das sequências biológicas. No entanto, a construção deste grafo tem grande custo computacional, especialmente muito consumo de memoria principal, tornando-se inviável no caso da montagem de grandes conjuntos de k-mers. Há soluções na literatura que utilizam o modelo de memória externa para conseguir executar o procedimento. Porém, todas envolvem alta redundância nos cálculos envolvendo os k-mers, aumentando consideravelmente o número de operações de E/S. Esta tese propõe uma nova abordagem para a construção do grafo de Bruijn que torna desnecessária a geração de todos os k-mer. A solução permite uma redução dos requisitos computacionais e a viabilidade da execução, o que é confirmado com os resultados experimentais. / [en] Fragment assembly is a current fundamental problem in bioinformatics. In the absence of a reference genome sequence that could guide the whole process, a de Bruijn Graph data structure has been considered to improve the computational processing. Notably, we need to count on a broad set of k-mers, biological sequences substrings. However, the construction of de Bruijn Graphs has a high computational cost, primarily due to main memory consumption. Some approaches use external memory processing to achieve feasibility. These solutions generate all k-mers with high redundancy, increasing the number of managed data and, consequently, the number of I/O operations. This thesis proposes a new approach for de Bruijn Graph construction that does not need to generate all k-mers. The solution enables to reduce computational requirements and execution feasibility, which is confirmed with the experimental results.

[pt] Em cenários de tomada de decisão, quando um agente, humano ou máquina, necessita de mais conhecimento para decidir devido a uma lacuna de conhecimento, surge uma necessidade de informação. Os usuários podem conscientemente tomar a iniciativa de adquirir conhecimento para preencher essa lacuna através de tarefas de buscas por informação. As consultas do usuário podem ser incompletas, imprecisas e ambíguas. Isso ocorre porque parte da informação necessária está implícita ou porque o usuário não compreende totalmente o domínio ou a tarefa que motiva a busca. Esta condição está prevista nas abordagens de busca exploratória. Embora os Grafos de Conhecimento (KG) sejam reconhecidos como fontes de informação com grande potencial para integração de dados e busca exploratória, eles são incompletos por natureza. Além disso, KGs Crowdsourced, ou KGs construídos pela integração de diversas fontes de informação de qualidade variável, precisam de uma Camada de Confiança para serem eficazes no suporte a processos de tomada de decisão. A avaliação da veracidade do conhecimento depende dos contextos das alegações e das tarefas a serem realizadas ou pretendidas (propósito). Esta pesquisa tem como objetivo preparar e consultar KGs para apoiar a exploração ciente de contexto em cenários de tomada de decisão. As contribuições incluem uma arquitetura para sistemas de apoio à decisão, composta por uma Camada de Decisão, uma Camada de Confiança e uma Camada de Conhecimento que opera sob a hipótese de Mundo Aberto Dual. A Camada de Conhecimento é composta por um Grafo de Conhecimento enriquecido de Contexto (CoaKG) e uma Máquina de Consulta baseada em CoaKG. CoaKG estende um KG padrão com mapeamentos de contexto para identificar o contexto explicitamente representado e regras para inferir o contexto implícito. A máquina de Consulta baseada em CoaKG foi projetada como uma abordagem de resposta a consultas que recupera todas as respostas contextualizadas (possíveis). A Wikidata é objeto de uma Prova de Conceito para avaliar a eficácia da Camada de Conhecimento. / [en] In decision-making scenarios, an information need arises when an agent, human, or machine needs more knowledge to decide due to a knowledge gap. Users can consciously take the initiative to acquire knowledge to fill this gap through information search tasks. User queries can be incomplete, inaccurate, and ambiguous. It occurs because part of the information needed is implicit or because the user does not fully understand the domain or the task that motivates the search. This condition is foreseen within the exploratory search approaches. Although Knowledge Graphs (KG) are recognized as information sources with great potential for data integration and exploratory search, they are incomplete by nature. Besides, Crowdsourced KGs, or KGs constructed by integrating several different information sources of varying quality, need a Trust Layer to be effective. The evaluation of knowledge truthfulness depends upon the contexts of claims and tasks being carried out or intended (purpose). This research aims to prepare and query KGs to support context-aware exploration in decision-making scenarios. The contributions include a framework for Context Augmented Knowledge Graphs-based Decision Support Systems composed of a Decision Layer, a Trust Layer, and a Knowledge Layer that operates under a Dual Open World Assumption. The Knowledge Layer comprises a Context Augmented KG (CoaKG) and a CoaKG Query Engine. CoaKG contains contextual mappings to identify explicit context and rules to infer implicit context. CoaKG Query Engine is designed as a query-answering approach that retrieves all contextualized (possible answers) from the CoaKG. Wikidata is the object of a Proof of Concept to evaluate the effectiveness of the Knowledge Layer.

[pt] Este trabalho tem por objetivo a modelagem do comportamento dinâmico do motor de CC shunt, através da metodologia dos grafos de ligação. Primeiro será feito um levantamento de todos os parâmetros mecânicos, elétricos e magnéticos da máquina. O segundo passo será a obtenção de um grafo de ligação do motor e de suas respectivas equações de estado representativas. Através destas equações e dos parâmetros obtidos em laboratório será montado um modelo de simulação computacional pelo Matlab para verificação do comportamento da máquina desde a partida até o regime permanente, comprovando a veracidade do modelo. / [en] This work has the goal of modeling the dynamic behavior of a CC shunt motor, through the methodology of bond graphs. First all the mechanical, eletrical and magnetic parameters of the machine are measured. The second step will be the development of the motor bond graph and of its respective state equations. Using these equations and the measured parameters a Matlab simulation is set up to verify the transient behavior of yhe machine, checking the truthfulness of the model.

[pt] Neste trabalho é desenvolvido um procedimento para a geração por inspeção das equações de estado e funções de transferência associadas a um grafo de ligação por meio de análises literal e numérica. O procedimento consiste na identificação de caminhos causais e a determinação de suas contribuições para as equações. É analisada a formulação matemática e discutida a implementação do procedimento em um código computacional. A aplicação do procedimento é ilustrada com exemplos, descreve-se detalhadamente as rotinas de entrada de dados, variáveis auxiliares, identificação dos caminhos e malhas causais, assim como a forma de apresentação dos resultados. / [en] In this work a procedure for the computer generation by inspection of the state equations and transfer functions, both in literal and numerical form, associated to a bond graph is discussed. The procedure consists of the identification of causal paths and the determination of its contributions for the equations. The mathematical background and the implementation of the procedure in a computational code are, also, presented. The application of the procedure is illustrated with examples; the routines for data entry, causal path and mesh identification and the used variables are described, as well as the form of presentation of the results.