Search

Submitted by António Freitas (amsf@uma.pt) on 2018-10-10T10:35:52Z No. of bitstreams: 1 MestradoVitorJesus.pdf: 1861005 bytes, checksum: 99f90ba600e01a52fdd3e2cf831db176 (MD5) Made available in DSpace on 2018-10-10T10:35:52Z (GMT). No. of bitstreams: 1 MestradoVitorJesus.pdf: 1861005 bytes, checksum: 99f90ba600e01a52fdd3e2cf831db176 (MD5) Previous issue date: 2018-05-03

O problema de Turán, assim como seu derivado, o problema de Zarankiewicz, pertencem à área de teoria extremal de grafos, e são problemas em aberto. Na década de 90, houve o passo inicial ao que alguns autores chamam de teoria espectral extremal, que ocorre ao solucionar problemas extremais com o auxílio da teoria espectral de grafos. Motivados por tal expansão, apresentamos algumas cotas retiradas da literatura associadas ao problema de Zarankiewicz e às matrizes de adjacência, Laplaciana e Laplaciana sem sinal, juntamente com o passo a passo de suas demonstrações. Visamos fortalecer nosso “background” para uma futura interpretação do problema de Zarankiewicz associado à matriz Laplaciana normalizada, que se encontra em aberto. Por fim, apresentamos comentários e limitantes superiores ao número de arestas associadas aos resultados indicados acima. Indicamos, também, que trabalhos futuros pretendemos estudar. The Turán problem, as well as its derivative, the Zarankiewicz problem, belong to the extremal graph theory and are open problems. In the 90’s started what some authors call the spectral extremal graph theory, which occurs by solving extremal problems with the aid of the spectral graph theory. Motivated by such expansion, we present some bounds, taken from the literature, associated with the Zarankiewicz problem and the adjacency, Laplacian, and signless Laplacian matrices, along with step-by-step demonstrations of each. Our aim is to strengthen our background for a future interpretation of the Zarankiewicz problem associated with the normalized Laplacian matrix, which also remains open. Finally, we comment on the results and present upper bounds for the number of edge associated with the results above. We also indicate what should be addressed by future studies.

Universidade Presbiteriana Mackenzie Cellular automata are totally discrete systems that act locally in a simple and deterministic way, but whose resulting global behavior can be extremely complex. The set of possible global configurations in one finite time step for a CA can be described by a regular language, which in turn can be represented by a finite automaton, more precisely the so-called process graph, in which all states are initial and final. Here, we study the temporal evolution complexity of the elementary cellular automata (i.e., one-dimensional, binary, with radius 1), and related previous works are revisited and discussed, indicating problems and their consequences. We also start up a novel approach for the problem, substituting the process graph based representation that describes the configuration at each time step by adjacency matrices derived from them. In fact, we extend the classical adjacency matrix notation, as they cannot fully represent process graphs. With this new notation, we show that it is possible to obtain the algorithm to generate a process graph for an arbitrary finite time step for each of the rules at study. In conclusion, although advancing the limit graph problem, it still remains open, and we provide suggestions for further research. Autômatos celulares são sistemas totalmente discretos que agem localmente de forma simples e determinística, mas cujo comportamento global resultante pode ser extremamente complexo. O conjunto de possíveis configurações globais em um passo de tempo t finito para um autômato celular pode ser descrito por uma linguagem regular, a qual por sua vez pode ser representada por meio de um autômato finito, mais precisamente, pelo chamado grafo de processo, em que todos os estados são iniciais e finais. Estuda-se aqui a complexidade da evolução temporal dos autômatos celulares elementares (i.e., unidimensionais, binários, de raio 1), e trabalhos anteriores são revisitados e discutidos, no quais apontam-se problemas e suas consequências. Também inicia-se uma nova abordagem para o problema, substituindo a representação dos grafos de processo que descrevem a configuração a cada passo de tempo por matrizes de adjacência deles derivadas. De fato, estende-se a notação clássica de matriz de adjacência, já que ela se mostra insuficiente para descrever completamente os grafos de processo em questão. Com essa nova notação, mostra-se que é possível obter o algoritmo que gere o grafo de processo de tempo t para cada uma das regras estudadas. Conclui-se que, embora houve avanços para o problema do grafo limite, este ainda permanece aberto, e sugestões para continuação da pesquisa são dadas.

Submitted by Boris Flegr (boris@uerj.br) on 2021-01-07T14:40:04Z No. of bitstreams: 1 Dissertacao Sabrina de Oliveira Figueira texto completo.pdf: 1639119 bytes, checksum: 17de8cb705c3c133dd486d796c272dd0 (MD5) Made available in DSpace on 2021-01-07T14:40:04Z (GMT). No. of bitstreams: 1 Dissertacao Sabrina de Oliveira Figueira texto completo.pdf: 1639119 bytes, checksum: 17de8cb705c3c133dd486d796c272dd0 (MD5) Previous issue date: 2010-08-26 This study presents the results of the work about simulations of networks of complex connections. They were simulate regular networks, middlemen and aleatory with the number of nodes and of connections varying between 103 and 5x104 and between 2x104 and 105, respectively, and with probability varying from 0 to 1 with step of 0.1, with the focus in the Spectral Theory. Using the language C and the software Matlab, the networks are represented by its adjacency matrix, with the objective of observing the behavior of its eigenvalues through histograms. The purpose is the characterization of complex networks. It s observed that the eigenvalues distribution follows the Wigner s semicircular law. Neste estudo são apresentados os resultados do trabalho sobre simulações de redes de conexões complexas. Foram simuladas redes regulares, intermediárias e aleatórias com o número de nós e de conexões variando entre 103 e 5x103 e entre 2x104 e 105, respectivamente, e com probabilidade variando de 0 a 1 com passo de 0.1, com o enfoque na Teoria Espectral. Utilizando a linguagem C e o software Matlab, as redes são representadas pela sua matriz adjacência, com o objetivo de observar-se o comportamento de seus autovalores através de histogramas. A finalidade é a caracterização de redes complexas. Observa-se que a distribuição dos autovalores segue a lei semicircular de Wigner.

This paper presents an approach to image analysis using the techniques of Complex Networks for obtaining similarities between images. Initially, the features are extracted from the edge of images, which will be understood computationally as arrays. Through these matrices are generated adjacency matrices, which will be used to check the connections of the vertices (pixels) of images. Extracted from the adjacency matrix will be performed to extract the degree of the vertices to a threshold T and the extraction of the average degree of the vertices. In the extraction of the degree of the vertices each threshold is applied in the calculation and returns an array that will be analyzed with other matrices extracted by checking the likelihood of isomorphism.

Cografos representam uma classe de grafos que pode ser de nida e caracterizada de diversas maneiras. A estrutura de relacionamento entre seus vértices, permite que um cografo possa ser construído de forma recursiva a partir de um único vértice. Neste trabalho estudamos algumas caracterizações clássicas de cografos, dentre as quais abordamos: livre de P4, formas recursivas utilizando união, complemento e junção, diâmetro de todo subgrafo induzido 2, vértices irmãos, propriedade CK(clique Kernel), e formas recusivas utilizando duplicação e coduplica ção de vértices. A principal contribuição foi relacionar algumas das diferentes formas de caracterizações de um cografo com a de nição de grafo complementar redutível. Apresentamos algumas formas de representar cografos, que podem ser encontradas em diversos trabalhos, como forma normalizada, coárvore e matriz de adjacência. Estudamos um algoritmo que auxilia na localização de autovalores em cografos, como contribuição apresentamos os detalhes teóricos sobre seu funcionamento através da Lei na Inércia de Sylvester, e da obtenção de matrizes congruentes à matriz A+xI, onde A é a matriz de adjacência de um cografo, x é um número real e I é a matriz identidade de mesma ordem de A. Com este algoritmo, estudamos alguns resultados clássicos sobre o espectro de um cografo, que são: a multiplicidade dos autovalores 1 e 0, e que um cografo não possui autovalores no intervalo (1; 0). Além disso, apresentaremos algumas aplicações para obter famílias de cografos com a mesma energia de grafos completos Kn. Cographs are a class of graphs that can be de ned and characterized in several ways. The structure given in terms of vertices enable a cograph to be built by recursive form from a single vertice. In this work, we study some classical characterizations of cographs, among which: P4 - free, recursive form with union, complement and join, diameter of all induced subgraph connected 2, siblings vertices, property CK(cliqueKernel), and recursive form by duplication and coduplication of vertices. As main contribution, we establish a relationship between some characterizations of cographs, which is a complement reducible graph. We also show some ways to make a mathematical representation that can be found in various works, as normalized form, cotree and adjacency matrix. We study an algorithm that can help us to nd eigenvalues in cographs, as an additional contribution we provide the theoretical details about its operation through the Sylvester Law of Inertia and how to get congruent matrices from A+xI, where A is the adjacency matrix of a cograph, x is a real number and I is a identity matrix with the same order of A. Using the algorithm, we study some classical results about spectral set of a cograph, as the multiplicity of eigenvalues 1 and 0, and the statement of no cographs have eigenvalues in (1; 0). In addition, we show some applications to nd cograph families with the same energy of complete graphs Kn.

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.

Orientador : Prof. Dr. Julio Eduardo Arce Coorientador : Prof. Dr. Arinei Carlos Lindbeck da Silva Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Agrárias, Programa de Pós-Graduação em Engenharia Florestal. Defesa: Curitiba, 27/03/2015 Inclui referências : f. 50-51 Área de concentração : Manejo florestal Resumo: O planejamento da colheita florestal está entre as etapas mais importantes do empreendimento florestal devido principalmente ao seu alto custo. Planejar espacialmente a colheita está se tornando cada vez mais comum, pois os problemas que eram considerados muito restritivos computacionalmente no início da aplicação da pesquisa operacional no setor florestal tiveram suas formulações reorganizadas de maneira a facilitar a resolução, isso sem mencionar que os recursos computacionais e os programas otimizadores (solvers) existentes estão cada vez mais capazes de solucionar problemas maiores e mais complexos. Representar as vizinhanças entre unidades de manejo na forma de restrições tem sido uma tarefa desafiadora, pois cada conjunto de unidades de manejo tem uma conformação diferenciada e para que todas as combinações possíveis entre as unidades fiquem explícitas é necessário um esforço computacional a mais que o esforço de apenas resolver o modelo matemático, em outras palavras, gerar o modelo matemático também é uma tarefa que merece atenção. Neste trabalho foi utilizado um grupo de talhões (unidades de manejo) com apenas 26 unidades e posteriormente foi aplicada a mesma metodologia em uma área comercial com cerca de 10 mil hectares plantados com o gênero Pinus. As formulações e algoritmos já existentes para este tipo de problema foram utilizados com sucesso e graças à facilidade que linguagens computacionais matemáticas proporcionam foi possível criar uma rotina que consegue formular as restrições para qualquer floresta, desde que seja fornecida uma matriz de adjacência das unidades de manejo. Adicionalmente também é apresentado um procedimento para automatizar a criação da matriz de adjacência usando uma rotina dentro de um programa de Sistemas de Informações Geográficas (SIG). Os conjuntos de unidades de manejo testados tiveram um decréscimo no Valor Presente Líquido à medida que foram acrescentadas as restrições de áreas máxima e/ou mínima contínuas, assim como um maior tempo necessário para que o solver conseguisse encontrar a solução ótima. Palavras-chave: Adjacência de Talhões; Otimização do Planejamento Florestal; Modelo de Restrição por Área; Blocos de Colheita. Abstract: The forest harvesting planning is among the most important stages of forest activity because its high costs. Planning spatially the harvest is becoming increasingly common, as problems that were considered too restrictive computationally early in the application of operations research in the forestry sector had their formulations reorganized in order to facilitate the resolution, not to mention that the current computational resources and existing solvers programs are progressively more able to face larger and more complex problems. Represent the neighborhoods between management units in the form of restrictions has been a challenging task, as each set of management units has a different spatial conformation and, in order to achieve all possible combinations among them, an extra computational effort is needed apart than just the effort to solve the problem, in other words, to generate the problem is also a task that deserves attention. In this study it was first used a group of stands (management units) with only 26 units and the same methodology was extended to a commercial area with around 10 thousand hectares planted with Pinus. The formulations and algorithms existent for this type of problem have been successfully used and thanks to the aid provided by mathematical computer languages it was possible to create a script that can make restrictions to any forest, as long as an adjacency matrix of the management units is provided. Additionally, it is also presented a procedure to automate the creation of the adjacency matrix using a routine within a Geographic Information Systems program (GIS). The sets of management units tested had a decrease in Net Present Value as the restrictions of maximum and/or minimum continuous area were added, and a longer time was required for the solver to find the optimal solution. Keywords: Stands Adjacency, Forestry Planning Optimization, Area Restriction Model, Harvest Clusters.

A teoria espectral de grafos visa descobrir propriedades de um grafo G por meio da análise do espectro de uma matriz associada ao grafo. Neste trabalho, estudamos a matriz de adjacência A, a matriz laplaciana L, a matriz laplaciana normalizada L e a matriz laplaciana sem sinal Q e para essas matrizes apresentamos resultados de entrelaçamento de autovalores associados com as operações de deleção de uma aresta e de deleção de um vértice. Além disso, mostramos resultados de entrelaçamento de autovalores associados com a operação de contração de dois vértices para a matriz de adjacência A e para matriz laplaciana normalizada L. Como contribuição original construímos resultados de entrelaçamento de autovalores associados com a operação de subdivisão de uma aresta para as matrizes A, L, L e Q, e associados com a operação de contração de vértices para L e Q. The spectral graph theory aims to discover properties of a graph G through the analysis of the spectrum of a matrix associated with the graph. In this work, we study the adjacency matrix A, the standard Laplacian matrix L, the normalized Laplacian matrix L and the signless Laplacian matrix Q and for these matrices we present eigenvalues interlacing results associated with the operations of deleting an edge and deleting a vertex. Moreover, we show eigenvalues interlacing results associated with the vertex contraction operation for the adjacency matrix A and the normalized laplacian matrix L. As original contribution, we prove some results about eigenvalues interlacing associated with the operation of subdivision of an edge for the matrices A, L, L and Q, and associated with the vertex contraction operation for L and Q.

No primeiro artigo, introduzimos um modelo denominado "Probabilistic Context Neighborbood" para um lattice de duas dimensões como uma extensão do modelo de árvore de contexto probabilística em um espaço unidimensional , preservando algumas de suas propriedades interessantes. Este modelo tem uma estrutura de vizinhança variável com uma geometria fixa, mas de raio variável. Desta forma calculamos a cardinalidade do conjunto de vizinhos e utilizamos o Pseudo-Likelihood Bayesian Criterion (PIC) para selecionar um modelo adequado para cada amostra. Representamos, ainda a estrutura de dependência da vizinhança como uma arvoré, objetivando facilitar o entendimento da complexidade do modelo. Em seguida, propusemos um algoritmo para estimar o modelo que explora a estrutura de árvore esparsa, com o intuito de melhorar a eficiência computacional. Por fim, apresentamos uma extensão do modelo anterior, o Non-Homogeneous Probabilistic Context Neighorhood model", permitindo uma mudança espacialmente probabilística na vizinhança de contexto à medida que nos movemos no lattice. No segundo artigo, propusemos uma abordagem Bayesiana para a problemática da escolha da matriz de vizinhança no mapeamento de doenças. Utilizamos o modelo proposto por Besag et al. (1991), no qual dos efeitos aleatórios segue o modelo "Conditional Autoregressive" (CAR), no qual se utiliza a matriz de adjacência como vizinhança. Observamos, contudo, que a matriz de adjacência é inadequada para cenários nos quais a estrutura espacial é insuficiente para a obtenção de boas estimativas dos riscos relativos, tal como ocorre em estudos criminológicos e epidemiológicos que apresentam evidências sobre elevadas taxas de incidência em grandes centros, independentemente das taxas apresentadas pelas cidades vizinhas. Além das classes a priori, propusemos dois estimadores a posteriori para a estrutura de vizinhança. Foram apresentados vários exemplos, simulações e aplicações do nosso método, cujos resultados foram mais satisfatórios que os apresentados pelo modelo CAR. Por fim, no último artigo, propusemos um sistema de vigilância para monitorar prospectivamente a emergência de clusters espaço-temporais em dados de doenças. O objetivo, nesse caso, é detectar um cluster que venha a emergir, mantendo a taxa de falsos alarmes em um nível controlado. Trata-se de um sistema de fácil compreensão e de fácil implementação, com imensa aplicabilidade pelos órgãos oficiais de saúde pública, refletindo uma modificação de proposta anteriormente feita por Rogerson (2001), que exminou um cenário de vigilância retrospectiva, olhando para o tempo mais antigo no passado que a mudança poderia ter ocorrido. Modificamos o método, de forma a levar em conta os casos prospectivos, e avaliamos o nosso sistema de vigilância em vários cenários de clusters emergentes, verificando os pressupostos de distribuição e avaliação de desempenho e impacto de diferentes tempos de emergências, formas, extensão e intensidade. In the first paper, we introduce the Probabilistic Context Neighborhood model for two dimensional lattices as an extension of the Probabilistic Context Tree model in one dimensional space preserving some of its interesting properties. This model has a variable neighborhood structure with a fixed geometry but varying radius. In this way we are able to compute the cardinality of the set of neighborhoods and use the Pseudo-Likelihood Bayesian Criterion to select an appropriate model given the data. We represent the dependence neighborhood structure as a tree making easier to understand the model complexity. We provide an algorithm to estimate the model that explores the sparse tree structure to improve computational efficiency. We also present an extension of the previous model, the Non-Homogeneous Probabilistic Context Neighborhood model, which allows a spatially changing Probabilistic Context Neighborhood as we move on the lattice. In the second paper, we proposed a Bayesian approach to the problem of choosing the neighborhood matrix in disease mapping. We use the model proposed by Besag et al. (1991), whose random effects follow the Autoregressive Conditional (CAR), using the adjacency matrix as neighborhood. However, the adjacency matrix is inadequate for scenarios in which the spatial structure is insufficient to obtain a precise estimative of the relative risks, as occurs in criminological and epidemiological studies that show high incidence rates in large towns, regardless the rates presented by neighboring cities. In addition to the a priori classes, we proposed two a posteriori estimators for the neighborhood structure. Finally, we presented several examples, simulations and applications of our method, which reached more satisfactory results than the CAR model. In the last paper, we propose a surveillance system to prospectively monitor the emergence of space-time clusters in point pattern of disease events. Its aim is to detect a cluster as soon as possible after its emergence and it is also desired to keep the rate of false alarms at a controlled level. It is an easily understood and easily implemented system, requiring very little input from the user. This makes it a promising candidate to practical use by public health official agencies. Our method is a modification from a previous proposal made by Rogerson, who examined a retrospective surveillance scenario, looking for the earliest time in the past that change could have been deemed to occur. We modify his method to take into account the prospective case. We evaluated our surveillance system in several scenarios, including without and with emerging clusters, checking distributional assumptions and assessing performance impacts of different emergence times, shapes, extent and intensity of the emerging clusters.

Conselho Nacional de Desenvolvimento Científico e Tecnológico The occurrence of problems related to the scattering and tangling phenomenon, such as the difficulty to do system maintenance, increasingly frequent. One way to solve this problem is related to the crosscutting concerns identification. To maximize its benefits, the identification must be performed from early stages of development process, but some works have reported that this has not been done in most of cases, making the system development susceptible to the errors incidence and prone to the refactoring later. This situation affects directly to the quality and cost of the system. PL-AOVgraph is a goal-oriented requirements modeling language which offers support to the relationships representation among requirements and provides separation of crosscutting concerns by crosscutting relationships representation. Therefore, this work presents a semi-automatic method to crosscutting concern identification in requirements specifications written in PL-AOVgraph. An adjacency matrix is used to identify the contributions relationships among the elements. The crosscutting concern identification is based in fan-out analysis of contribution relationships from the informations of adjacency matrix. When identified, the crosscutting relationships are created. And also, this method is implemented as a new module of ReqSys-MDD tool A ocorrência de problemas relacionados aos fenômenos de espalhamento e entrelaçamento, tal como a dificuldade de manutenção do sistema, é cada vez mais frequente. Uma tentativa de resolver este problema está relacionada à identificação de interesses transversais. Para maximizar seus benefícios, a identificação deve ser realizada desde as etapas iniciais do processo de desenvolvimento, porém alguns trabalhos relatam que isto não tem sido feito na maioria dos casos, tornando o desenvolvimento do sistema suscetível à ocorrência de erros e propensos à refatorações em fases posteriores. Esta situação afeta diretamente à qualidade e o custo do sistema. PL-AOVgraph é uma linguagem de modelagem de requisitos orientada a metas que oferece suporte para representação dos relacionamentos entre requisitos e provê separação de interesses transversais através da representação de relacionamentos transversais. Diante disso, esse trabalho apresenta um método semi-automático para identificação de interesses transversais em especificações de requisitos escritas em PL-AOVgraph. Uma matriz de adjacência é utilizada para a identificação dos relacionamentos de contribuição entre os elementos. A identificação de interesses transversais é baseada na análise fan-out dos relacionamentos de contribuição a partir das informações da matriz de adjacência. Quando identificados, os relacionamentos transversais são criados. Esse método está implementado como um novo módulo da ferramenta ReqSys-MDD

Nesta tese de doutorado estudamos uma classe de grafos denominada threshold. Iniciamos apresentando algumas caracterizações dos grafos threshold e definindo-os de uma forma apropriada para o nosso propósito. Mais especificamente, estudamos o espectro dos grafos threshold. Para isso apresentamos alguns resultados previamente conhecidos, como por exemplo, em relação à matriz de adjacência, uma redução para o cálculo do polinômio característico e a multiplicidade dos autovalores não principais. Desenvolvemos um algoritmo que constrói uma matriz diagonal D congruente a A + xI , onde A é a matriz de adjacência de um grafo threshold, x é um número real e I é a matriz identidade. Como aplicação, determinamos quantos autovalores de um grafo threshold G pertencem a um intervalo real (a, b]. A implementação do nosso algoritmo depende apenas da sequência binária de um grafo threshold e sua complexidade é de ordem O(n). Tal algoritmo é facilmente adaptado para a matriz distância Θ de um grafo threshold G. Nesta tese apresentamos aplicações desse algoritmo, como a simplicidade dos autovalores principais, a minimalidade do menor autovalor de um threshold, exibindo uma fórmula para esse menor autovalor, uma ordenação dos grafos threshold via índice, e uma classe infinita de grafos threshold com espectro integral. Além disso, apresentamos um novo algoritmo para o cálculo do polinômio característico de um grafo threshold G. In this thesis we study the class of threshold graphs. We begin showing some characterizations of threshold graphs defining them in a convenient way for our purposes. More specifically, we study the spectrum of threshold graphs. To this end, we show some previously known results about the adjacency matrix, such as the reduction for computing the characteristic polynomial and the multiplicity of non main eigenvalues. We developed an algorithm that constructs a diagonal matrix D con- gruent to A + xI , where A represents the adjacency matrix of a threshold graph and x is a real number. As an application, we determine how many eigenvalues of a threshold graph lie in an interval (a, b]. The algorithm implementation depends only on the binary sequence of the threshold graph, and its complexity is of order O(n). This algorithm is easily adapted for the distance matrix Θ of a threshold graph G. We finish this dissertation showing some applications of this algorithm. We show that the main eigenvalues are simple. We also determine the class of threshold graphs which have the minimum eigenvalue among threshold graphs of order n, and a formula for this eigenvalue is given. We identify an infinite class of threshold graphs with integral spectra. And finally we obtain a simple algorithm to compute the characteristic polynomial of a threshold graph G.

Submitted by Boris Flegr (boris@uerj.br) on 2021-01-07T14:37:08Z No. of bitstreams: 1 TeseNiltonAlvesJunior.pdf: 2642043 bytes, checksum: 64629d5e3558a310da84df6d88c7765d (MD5) Made available in DSpace on 2021-01-07T14:37:08Z (GMT). No. of bitstreams: 1 TeseNiltonAlvesJunior.pdf: 2642043 bytes, checksum: 64629d5e3558a310da84df6d88c7765d (MD5) Previous issue date: 2007-03-29 Connection networks are observed in many areas of human knowledge. The characterization and topological studies of these networks may be performed through distribution of connectivity degrees, rank properties, shortest path length between nodes, adjacency matrix etc, typical concepts from Complex networks, a filed of study of Statistical Physics domain. In this thesis we characterize the Internet connections evolution from 1998 to 2007. The Internet may be seen under several levels of reach and complexity considering different basic units. A wide vision is to consider the Internet basic element as an Autonomous System - AS, which is defined as a cluster of LANs or routers submitted to the same policy of usage, connectivity and technically administrated by the same network management group. The complex network considered in this work is composed by Autonomous Systems (vertices) and the established tra connection (edges) between them obtained from the BGP routing table. Many interesting property of this networks is analyzed, e.g. degree distribution (the rank and outdegree exponents) from 1998 to 2007 and the shortest path length (L), obtained by a proposed computational method (Friburgo algorithm) among each pair of ASs represented in the adjacency matrix. Finally, we present the behavior of the power law function and the shortest path length of the Internet for each year. Simulations of the connections network were carried out by a proposed model developed from continuous growth premises, possibilities of new and rearranging connections. This model was based on the concept of potential preferable connection showing a stable exponential factor that reproduces the true shortest path parameter over the decade. Neste trabalho, foram utilizadas técnicas e conceitos tipicamente encontrados em estudos de Redes Complexas, uma sub-área da Física Estatística, para caracterizar a Internet e sua evolução em uma década, de 1998 a 2007. Foi considerada como unidade básica de análise, a estrutura Sistema Autônomo. Nesta caracterização, foram utilizadas várias ferramentas computacionais desenvolvidas em linguagem C/C++, que permitiram classificar, simular e modelar propriedades dinâmicas. Dentre estas propriedades podemos destacar o coeficiente de conectividade, fundamental para os estudos topológicos, e o parâmetro menor caminho médio, ambos baseados nas propriedades da matriz adjacência. Os dados experimentais foram inicialmente obtidos nos roteadores de borda da RedeRio de Computadores - FAPERJ e posteriormente, os dados relativos ao intervalo de estudo, foram retirados da base de dados disponibilizada pela Universidade de Oregon. Foi proposto um modelo de crescimento de uma rede complexa baseado nas premissas de crescimento contínuo e conexão preferencial não linear com suporte aos mecanismos de rearranjo e novas conexões entre nós já existentes. Este modelo se mostrou bastante adequado no estudo das propriedades consideradas. Foi desenvolvido um método para cálculo do menor caminho médio que apresentou performance superior àqueles normalmente utilizados pela comunidade acadêmica. O comportamento da topologia sob o ponto de vista da distribuição de probabilidades de conexão e do ranque de conectividade, apresentaram comportamento linear constante no período estudado com coeficientes médios iguais a -2,0 e -0,93, respectivamente. O parâmetro menor caminho médio global da Internet permaneceu praticamente inalterado e igual a 4, 2 ao longo da década estudada.

Neste trabalho estudamos o espectro de grafos, que é o conjunto de autovalores da sua matriz de adjacência. Apresentamos uma teoria baseada na função geradora do número de passeios de um grafo para obter o polinômio característico de algumas classes de grafos. Também desenvolvemos um novo método para o cálculo do polinômio característico de árvores que utiliza um algoritmo geométrico -- também por nós apresentado-- para o determinante de matrizes da forma A+a.I, onde A é a matriz de adjacências e a. é um número real arbitrário. O custo computacional desse algoritmo é O(n2 ), que é menor do que os algoritmos previamente conhecidos. Finalmente apresentamos alguns resultados que visam determinar a estrutura de um grafo a partir de suas propriedades espectrais. In this dissertation, we study the spectra of graphs, which is the set o f the eigenvalues ofits adjacency matrix. We present a theory, based on the generating function o f the number o f walks, in order to obtain the characteristic polynomial o f certa in classes of graphs. We also develop a new method to compute the characteristic polynomial of a tree's adjacency matrix that hinges on a geometric algorithm --- also introduced in this work ---to obtain the determinant of matrices A+a l, where Ais the adjacency matrix and a an arbitrary real number. The computational cost of this algorithm is O(n2 ) , which is lower than any previously known algorithm. Finally, we present results that try to determine the structure o f a graph from its spectral properties.

Neste trabalho, apresentaremos nosso estudo acerca de grafos coespectrais. Mostraremos construções de famílias de grafos coespectrais já conhecidas na literatura e também construções desenvolvidas durante nossa pesquisa envolvendo grafos thresholds e produto cartesiano. Iremos compartilhar com o leitor o processo histórico que envolve questionamentos acerca de grafos coespecrais. Por fim, apresentaremos nossa maior contribuição: sugerimos usar o espectro complementar de um grafo como alternativa para a representação espectral. O espectro complementar não se trata de associar uma nova matriz a um grafo, mas sim de utilizar a já conhecida matriz de adjacências de uma forma diferente. Nesse viés, realizamos experimentos com famílias de grafos já conhecidas como as árvores, por exemplo. O espectro complementar, juntamente com os conceitos de raio espectral e entrelaçamento de grafos deram o suporte e embasamento para nosso estudo. Por fim, estudamos o conceito de matróide e tentamos vincular com nosso problema de coespectralidade de grafos. Encontramos uma aplicação de um conhecido resultado de Teoria de Matróides na Teoria Espectral de Grafos, mais especificamente, na determinação de grafos. In this work, we present our study around cospectral graphs. We display constructions of cospectral graphs already known in the literature, and also some constructions developed in our own research, which involve threshold graphs and cartesian product. Also, we share with the reader the historic process of raising questions about cospectral graphs. Finally, we then present our greatest contribution: we suggest use the complementary spectrum of a graph as an alternative to spectral representation. The complementary spectrum is not about associating a new matrix to a graph, instead it is about utilizing the already known adjacency matrix in a different way. In this bias, we experiment with families of graphs that are well known, such as the trees, for example. The complementary spectrum, along with the concepts of spectral radius and graph interlacing, gave us the support and foundation to our study. In the end, we study the concept of matroids and try to tie it with our problem of graph cospectrality. We find an application of a known result of the Matroid Theory on the Spectral Graph Theory, specifically, on graph determination.

Dissertação de Mestrado em Treino Desportivo para Crianças e Jovens apresentada à Faculdade de Ciências do Desporto e Educação Física Objetivo: Este estudo teve dois objetivos primordiais: um primeiro, que consistiu na análise do processo ofensivo do AS Monaco, na condição de visitado, nos jogos para a Ligue 1 na época desportiva 2016/17, através da análise de networks; e, um segundo, que consistiu na apresentação dos nossos resultados ao treinador Leonardo Jardim e ao analista e observador Miguel Moita, por forma a indagar acerca da sua perspetiva de análise relativamente aos procedimentos mais eficazes do processo ofensivo da sua equipa.Metodologia: Foram analisados dezasseis jogos do AS Monaco no Stade Louis II para a Ligue 1 na época desportiva 2016/17. A análise dos jogos foi efetuada através de uma matriz de adjacência presente numa folha de Excel pré-configurada, o que nos possibilitou realizar também uma análise notacional de cada jogo. Após termos realizado essa análise e já termos disponíveis todos os dados necessários, utilizámos o software SocNetV 2.4 para a criação das weighted networks que utilizamos em todo o estudo de forma a compreender quais os jogadores que tinham uma maior influência e uma maior participação durante o processo ofensivo do AS Monaco. Este recurso gráfico facilitou a apresentação dos resultados aos treinadores entrevistados.Resultados: Os resultados demonstraram a existência de regularidades no Processo ofensivo da equipa analisada. Ademais, permitiram constatar que existe uma grande diferença entre um jogador influente numa weighted network e um jogador decisivo no terreno de jogo. Comprovou-se ainda que Fabinho, foi o jogador mais participativo no processo ofensivo do AS Monaco nos jogos realizados para a Ligue 1 na condição de visitado. Conclusões: Conclui-se que o AS Monaco na época em que foi analisado na condição de visitado para a Ligue 1, era uma equipa que privilegiava o ataque pelos corredores laterais com os defesas laterais a dar profundidade ao ataque monegasco, enquanto os médios alas aproveitavam muito bem o espaço interior para criar desequilibrar a defensiva adversária. Aim: This study had two main objectives. At first, the analysis of the offensive procedure of AS Monaco at home games for the Ligue 1 on the 2016/17 season through networks analysis. The second one consisted on the presentation of our results to the football manager Leonardo Jardim and to the analist and observer Miguel Moita so we could obtain a relationship between quantitative and qualitative studies.Methodology: We analyzed sixteen games from AS Monaco at the Stade Louis II for Ligue 1 on 2016/17 season. At first, we travelled to AS Monaco’s training center to ask for permition to take all the AS Monaco recordings from 2016/17 season on home games into a hard drive. Up next, we analyzed the games using an adjacency matrix already pre-configured in a Excel sheet. Those data allowed us to accomplish also a notational analysis. After all data was collected, we used the SocNetV 2.4 software to generate the weighed networks that we used during our whole study. Is was an important tool to comprehend which player had the most influence on the AS Monaco offensive procedure. This graphic resource enhansed the results presentation to the interviewed football managers.Results: The results evidenced that there is a big difference between an influent player on a weighted network and the most crucial player on the field. The same results proved that Fabinho was the most influent player at the AS Monaco offensive procedure on the home games for Ligue 1.Conclusions: We can conclude that on this season that we analysed, AS Monaco was a team who privileged the wide attack, using both side corridors, with the depth being assured by the full backs while the wingers utilized a lot the inner space of the field in order to unbalance the opposite defense.

Uma crescente e importante dúvida na Teoria Espectral de Grafos é como saber quando dois grafos são determinados pelo espectro (DS), em particular, da matriz de adjacência, e se quase todos os grafos são DS. Este trabalho retrata o alguns resultados que temos até o momento dos grafos que são determinados pelo seu espectro, isto é, quando um espectro está associado a apenas um grafo, mostrando quais métodos foram utilizados e quais autores foram os responsáveis pelo estudo. Também abordaremos algumas afirmações acerca de grafos DS realizadas por alguns matemáticos que, ao longo dos anos, foram descobertas serem falsas. Apresentamos também um estudo sucinto sobre as invariantes espectrais de um grafo, que são utilizados em todas as presentes demonstrações de grafos que são determinados pelo espectro. A growing and important question on Spectral Graph Theory is how to know when two graphs are determined by the spectrum (DS) of a matrix, particularly, their adjacency matrix, and if mostly all graphs are DS. This work portraits what we have so far about the graphs that are determine by their spectrum, meaning when a spectrum is associated with only one graph, showing which methods were used and which authors were responsible for the study. We also approach a few affirmations about DS graphs made by some mathematicians that over the years were discovered to be false. We present a succinct study about a graph’s spectral invariable elements, which are used in every shown demonstration on graphs determined by the spectrum.

Submitted by Boris Flegr (boris@uerj.br) on 2021-01-05T17:54:43Z No. of bitstreams: 1 merged.pdf: 1921202 bytes, checksum: c740b14485594fed8782b12ae980530e (MD5) Made available in DSpace on 2021-01-05T17:54:43Z (GMT). No. of bitstreams: 1 merged.pdf: 1921202 bytes, checksum: c740b14485594fed8782b12ae980530e (MD5) Previous issue date: 2017-03-10 This thesis comprises two major contributions. It summarizes the literature about four important probabilistic data structures: Bloom filters, Count-Min sketch, MinHash, and HyperLogLog, discussing their definition, variants, error bounds, and practical applications, while providing new experimental data about them. Also, it discusses the application of probabilistic data structures to the graph representation problem. Two new probabilistic representations are introduced here: one that uses Bloom filters and can represent general graphs with the same complexity as the adjacency matrix (but outperforms it for sparse graphs), the other that uses MinHash and can represent trees with lower complexity than the optimal deterministic implicit representation Esta dissertação apresenta duas principais contribuições. É feito um resumo da literatura sobre quatro estruturas de dados probabilísticas importantes: Bloom filters, CountMin sketch, MinHash e HyperLogLog. São discutidas suas definições, variantes, limites de erro e aplicações práticas. Novos dados experimentais sobre essas estruturas foram produzidos para este trabalho. Além disso, é discutida aqui a aplicação de estruturas de dados probabilísticas para o problema de representação de grafos. Duas novas representações probabilísticas são introduzidas aqui: uma que usa filtros de Bloom e pode representar grafos gerais com a mesma complexidade da matriz de adjacência (sendo até melhor para grafos esparsos), e outra que usa MinHash e pode representar árvores com complexidade menor que a representação determinística ótima

Made available in DSpace on 2017-07-21T19:53:47Z (GMT). No. of bitstreams: 1 Elisangela Meira dos Santos.pdf: 1220706 bytes, checksum: 1387090400d1c0df8cb0bb5c88039b69 (MD5) Previous issue date: 2016-12-15 Coordenação de Aperfeiçoamento de Pessoal de Nível Superior In this work we review the diferent distinct aspects associated with quantum dynamics in graphs. The approach used is that of the Green's functions, dened in the feld of energy. In this technique the Green's functions are obtained through the sum of all possible classical paths connecting the initial and Final points, the style of Feynman path integrals. Local quantum efects are included through the use of quantum amplitudes for reection and transmission are defined in each of the vertices of the graph. We show that in order to get the exact Green function can use the adjacency matrix of the graph, which sets the links between the vertices of the graph. This approach ensures that all paths have been accounted for and has the advantage of providing a rating only for the various families of paths that can be defined in a given graph. An application of the method to study resonances in graphs is also presented. Neste trabalho revisamos os diferentes aspectos distintos associados a dinâmica quântica em grafos. A abordagem utilizada è aquela das funções de Green de únidas no domínio da energia. Nessa técnica as funções de Green são obtidas através da soma de todos os possíveis caminhos clássicos, ao estilo das integrais de caminho de Feynman. Os efeitos quânticos locais são incluídos através da utilização das amplitudes quânticas de reflexão e transmissão de únidas em cada um dos vértices do grafo. Mostramos que para obtermos a função de Green exata podemos utilizar a matriz de adjacência do grafo, a qual define as ligações existentes entre os vértices do grafo. Essa abordagem garante que todos os caminhos foram contabilizados e tem a vantagem de fornecer uma classificação única para as diferentes famílias de caminhos que podem ser de únidas em um dado grafo. Uma aplicação do método para o estudo ressonâncias em grafos é também apresentada.

O objetivo deste trabalho é estudar alguns tópicos da teoria de grafos com o intuito de resolver alguns problemas. Para complementar, abordamos um leve estudo de matrizes, autovalores e autovetores. O primeiro problema é conhecido como o Problema da Ponte de Königsberg, onde tal, foi considerado o problema que deu origem ao estudo sobre grafos. O Problema das Casas que é uma brincadeira, que nos mostra várias proposições sobre grafos planares e bipartidos. Alguns modelos que podemos relacionar grafos, tais como veremos no problema dos canibais e no jogo de xadrez. Por fim, trabalharemos com aplicações na matriz de adjacência como no problema do Condomínio de Chácaras e no Número de Caminhos Possíveis em um Grafo, onde trabalharemos com figuras geométricas, resolvendo aparentemente um problema de contagem, utilizando autovalores e grafos. Como suporte metodológico será abordado Álgebra Linear. This work aims to study some topics of graph theory in order to solve some problems. In order to complement, we approached a light study of matrices, eigenvalues and eigenvectors. The first problem is known as Königsberg Bridge Problem, where this was considered the problem that gave rise to the study on graphs. The House Problem is a joke, which shows us several propositions about planar and bipartite graphs. Some models we can relate graphs, such as we can observe in the problem of cannibals and in the game of chess. Finally, we will work with applications in the adjacency matrix as in the Problem of the Condominium of Farms and in the Number of Possible Paths in a graph, where we will work with geometric figures, apparently resolving a counting problem using eigenvalues and graph. As a methodological support will be approached Linear Algebra. Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES

A Teoria Espectral de Grafos tem como objetivo descobrir propriedades de um grafo G através da análise do espectro de uma matriz associada ao grafo. Nesta dissertação estudamos a matriz de adjacência A(G), a matriz laplaciana L(G) e a matriz laplaciana sem sinal Q(G). Para cada uma dessas matrizes estudamos o comportamento dos autovalores no que diz respeito `a integralidade. Mais especificamente, estudamos os grafos integrais, os grafos Q-integrais e os grafos L-integrais, que são os grafos que têm espectro inteiro em relação `as matrizes A(G), Q(G) e L(G), respectivamente. Estudamos a variação espectral inteira via adição de aresta para a matriz laplaciana. Vimos que se os autovalores da matriz laplaciana variam de maneira inteira, então um dos autovalores aumenta em duas unidades ou dois dos autovalores aumentam em uma unidade cada um. Esses dois tipos de variações são conhecidas como variação espectral inteira em um lugar e dois lugares [26, 33], respectivamente. Essas duas variações foram cruciais para estabelecermos uma estratégia para construção de grafos L-integrais por adição de arestas. Além disso, estudamos os grafos construtivelmente laplaciano integrais [28], que são um subconjunto dos grafos L-integrais. Caracterizamos este subconjunto através dos subgrafos induzidos e mostramos uma técnica alternativa para calcular o seu espectro. Estudamos também algumas famílias com infinitos grafos integrais e grafos Q-integrais construídos através do join de grafos regulares [12, 15, 24]. The spectral graph theory aims to discover properties of a graph G by analyzing the spectrum of a matrix associated to the graph. In this thesis, we study the adjacency matrix A(G), Laplacian matrix L(G) and the signless Laplacian matrix Q(G). For each of these matrices we study the behavior of eigenvalues with respect to integrality. More specifically, we study integral graphs, Q-integral graphs and L-integral graphs, which are graphs that have integral spectrum with regard to the matrices A(G), Q(G) and L(G), respectively. We study the spectral integral variation for the Laplacian matrix under the addition of an edge. We have seen that if the eigenvalues of the Laplacian matrix change by integer quantities, then one of the eigenvalues increases by two units or two of the eigenvalues increase by one unit each. These two types of variation are known as spectral integral variation in one place and two places [26, 33], respectively. These two variations were crucial to establish a strategy for building L-integral graphs by adding edges. Moreover, we studied the class of constructably Laplacian integral graphs, that are a subset of L-integral graphs. We characterize this subset through vertex-induced subgraphs and show an alternative technique for calculating their spectrum. We also study some families with infinite integral graphs and Q-integral graphs built through the join of regular graphs [12, 15, 24].

Neste trabalho abordaremos a an alise espectral de grafos por dois estudos: técnicas de probabilidade quântica e por polinômios ortogonais com valores em matrizes. No Capítulo 1, consideraremos a matriz de adjacência do grafo tal como um operador linear e sua decomposição quântica permitir a uma an alise espectral que produzir a um teorema do limite central para tal grafo. No Capítulo 2, consideraremos uma medida com valores em matrizes induzida por polinômios ortogonais com valores em matrizes. Sob certas condições, e possível exibir explicitamente uma expressão de tal medida. Algumas aplicações em teoria dos grafos são dadas quando nos restringimos as matrizes estoc asticas e com valores em 0-1. Do nosso conhecimento, os cálculos e exemplos obtidos nas seçõoes 0.3.2, 0.3.3, 2.4 e 2.5 são novos. In this work we focus on the spectral analysis of graphs via two studies: quantum probabilistic techniques and by orthogonal matrix-valued polynomials. In Chapter 1 we consider the adjacency matrix of a graph as a linear operator, and its quantum decomposition will allow a spectral analysis that will produce a central limit theorem for such graph. In Chapter 2, we consider a matrix-valued measure induced by orthogonal matrix-valued polynomials. Under certain conditions, it is possible to display an explicit expression for such measure. Some applications to combinatorics and graph theory are given when we restrict to the stochastic and 0-1 matrices. Up to our knowledge, the calculations and examples obtained in sections 0.3.2, 0.3.3, 2.4 and 2.5 are new.

A identificação de formas apresenta inúmeras aplicações na área de visão computacional, pois representa uma poderosa ferramenta para analisar as características de um objeto. Dentre as aplicações, podemos citar como exemplos a interação entre humanos e robôs, com a identificação de ações e comandos, e a análise de comportamento para vigilância com a biometria não invasiva. Em nosso trabalho nós desenvolvemos um novo descritor de formas 2D baseado na utilização de redes complexas e teoria espectral de grafos. O contorno da forma de um objeto é representado por uma rede complexa, onde cada ponto pertencente a forma será representado por um vértice da rede. Utilizando uma dinâmica gerada artificialmente na rede complexa, podemos definir uma série de matrizes de adjacência que refletem a dinâmica estrutural da forma do objeto. Cada matriz tem seu espectro calculado, e os principais autovalores são utilizados na construção de um vetor de características. Esse vetor, após aplicar as operações de módulo e normalização, torna-se nossa assinatura espectral de forma. Os principais autovalores de um grafo estão relacionados com propriedades topológicas do mesmo, o que permite sua utilização na descrição da forma de um objeto. Para validar nosso método, nós realizamos testes quanto ao seu comportamento frente a transformações de rotação e escala e estudamos seu comportamento quanto à contaminação das formas por ruído Gaussiano e quanto ao efeito de oclusões parciais. Utilizamos diversas bases de dados comumente utilizadas na literatura de análise de formas para averiguar a eficiência de nosso método em tarefas de recuperação de informação. Concluímos o trabalho com a análise qualitativa do comportamento de nosso método frente a diferentes curvas e estudando uma aplicação na análise de sequências de caminhada. Os resultados obtidos em comparação aos outros métodos mostram que nossa assinatura espectral de forma apresenta bom resultados na precisão de recuperação de informação, boa tolerância a contaminação das formas por ruído e oclusões parciais, e capacidade de distinguir ações humanas e identificar os ciclos de uma sequência de caminhada. The shape is a powerful feature to characterize an object and the shape analysis has several applications in computer vision area. We can cite the interaction between human and robots, surveillance, non-invasive biometry and human actions identifications among other applications. In our work we have developed a new 2d shape descriptor based on complex network and spectral graph theory. The contour shape of an object is represented by a complex network, where each point belonging shape is represented by a vertex of the network. A set of adjacencies matrices is generated using an artificial dynamics in the complex network. We calculate the spectrum of each adjacency matrix and the most important eigenvalues are used in a feature vector. This vector, after applying module and normalization operations, becomes our spectral shape signature. The principal eigenvalues of a graph are related to its topological properties. This allows us use eigenvalues to describe the shape of an object. We have used shape benchmarks to measure the information retrieve precision of our method. Besides that, we have analyzed the response of the spectral shape signature under noise, rotation and occlusions situations. A qualitative study of the method behavior has been done using curves and a walk sequence. The achieved comparative results to other methods found in the literature show that our spectral shape signature presents good results in information retrieval tasks, good tolerance under noise and partial occlusions situation. We present that our method is able to distinguish human actions and identify the cycles of a walk sequence.

Esta pesquisa apresenta a construção de um modelo conceitual para a sustentabilidade do Rio Pinheiros na capital de São Paulo através da aplicação de um método de mapeamento e análise de variáveis em sistemas sócio-ecológicos. O método se baseia na Teoria Geral dos Sistemas e na Stakeholder Analysis e visa identificar variáveis relevantes por meio de uma abordagem hierárquica e transdisciplinar. Nesse sentido, especialistas de diversas áreas do conhecimento foram consultados para que as variáveis fossem identificadas e, ainda, a elas se atribuíssem níveis de importância. Além disso, uma matriz de adjacência foi elaborada a fim de identificar as conexões entre as variáveis. Duas hipóteses foram testadas. A primeira - referente à distribuição não aleatória dos pontos de importância atribuídos pelos diversos especialistas - foi corroborada. A segunda - que postulava a sobreposição das variáveis mais importantes e mais conectadas em um conjunto formado pelos quartis dos valores mais altos de importância e conectância - foi refutada. A verificação da primeira hipótese foi feita com o teste não paramétrico do sinal e distribuições binomiais. A verificação da segunda hipótese se deu com o cálculo da porcentagem de maioria simples. A partir dos resultados obtidos, construiu-se o modelo conceitual da sustentabilidade do Rio Pinheiros com a ajuda de um software de modelagem de redes complexas e hierárquicas. This research presents the construction of a conceptual model for the sustainability of the Pinheiros River in São Paulo City through the application of a method of mapping and analysis of variables in socio-ecological systems. The method is based both on the General Theory of Systems and on the Stakeholder Analysis and aims at the identification of relevant variables through a hierarchical and transdisciplinary approach. In this sense, specialists from different fields of expertise were consulted in order to identify the variables and to assign them importance levels. An adjacency matrix was developed so that connections amidst the variables could be identified. Two hypotheses were tested. The first - concerning the nonfortuitous distribution of the importance points assigned by the several specialists - was corroborated. The second - which postulated the superposition of the more important and more connected variables in a group formed by the quartile of the more important variables - was refuted. The first hypothesis was verified with the support of the non-parametric signal and binomial distribution test. The second hypothesis was verified through the simple majority calculation. Based on the results and with the help of a software able to model hierarchical and complex networks, a conceptual model of sustainability for the Pinheiros River was built.

Made available in DSpace on 2017-07-21T19:26:05Z (GMT). No. of bitstreams: 1 Rafael Ribaski Borges.pdf: 2504879 bytes, checksum: b87dbb16266c955866bfc47eef34de30 (MD5) Previous issue date: 2013-03-05 Coordenação de Aperfeiçoamento de Pessoal de Nível Superior The extreme value theory is a branch of statistics and probability. It deals with the asymptotic distributions of extreme values (maximum or minimum) temporal series. The events which takes the average values removed are classified as extreme events. Examples include natural disasters such as goods, earthquakes or an event that causes a strong impact on society. Considering the scenario of complex networks, some examples of extreme events are congestion in networks of roads, power outages in power transmission networks and web servers congested. Thus, understanding the mechanisms that occur in such events is of great interest, because the prediction of these occurrences can minimize its efects, or even avoid them. Thus, the objectives of this study were: 1) to describe the asymptotic behavior of exceedances of a threshold specified by the generalized extreme value distribution, 2) extend the study to the probability of extreme events in complex networks with random topology, small world and scale free. This work was carried out by simulations of random walk pattern and shorter paths. The results shows that for the nodes, also called vertices or sites with low connectivity (lesser degree) in the networks analyzed, the distribution of excesses is not of exponential type. This implies that this distribution is bounded above. The results for the nodes with higher degree were similar, but only for the scale-free network this behavior does not occur. This is due to the fact that the number of exceedances observed in this case is signicantly smaller than the other. It was checked analytically and numerically simulated by random walk pattern, the probability of extreme event is larger and the average time between them is smaller for nodes with lower degree when compared with nodes with higher degree. The spectrum of eigenvalues of the adjacency matrix of the network, which describes the links between nodes, provides conditions for a good agreement between the analytical results and the simulations. For simulations of random walk for shorter paths it was found that nodes with lower betweenness centralities are more likely to have extreme events. A teoria de valores extremos é um ramo da estatística e probabilidade. Ela trata das distribuições assintóticas de valores extremos (máximos ou mínimos) de séries temporais. Os eventos que assumem valores afastados da média são classificados como eventos extremos. Alguns exemplos são desastres naturais, tais como enchentes, terremotos ou um evento que cause um forte impacto na sociedade. Considerando o cenário de redes complexas, alguns exemplos de eventos extremos são congestionamentos em redes de rodovias, quedas de energia em redes de transmissão e servidores de internet congestionados. Assim, a compreensão dos mecanismos que regem tais eventos é de grande interesse, pois com a previsão de ocorrências destes pode-se minimizar seus efeitos ou até mesmo evitá-los. Com isso, os objetivos deste trabalho foram: 1) descrever o comportamento assintótico das excedências de um valor limite especicado por meio da distribuição de valores extremos generalizada; 2) estender o estudo para a probabilidade de eventos extremos em redes complexas com topologia aleatória, mundo pequeno e escala livre. Este trabalho foi realizado por meio de simulações de caminhada aleatória padrão e por menores caminhos. Os resultados obtidos mostram que para os nós, também denominados vértices ou sítios, com menor conectividade (menor grau) nas redes analisadas, a distribuição dos excessos não é do tipo exponencial. Isto implica que esta distribuição é limitada superiormente. Os resultados para os nós com maior grau foram semelhantes, porém, somente para a rede de escala livre este comportamento não ocorre. Isto se deve ao fato de que o número de excedências observadas neste caso são menores do que nos demais. Foi vericado analiticamente e numericamente por meio de simulações de caminhada aleatória padrão, que a probabilidade de evento extremo é maior e que o tempo médio entre eles é menor para os nós com grau menor, quando comparados com nós com grau maior. O espectro de autovalores da matriz adjacência da rede, a qual descreve as ligações entre os nós, fornece condições para uma boa concordância entre os resultados analíticos e das simulações.Para simulações de caminhada aleatória por menores caminhos verificou-se que os nós com menores centralidades de intermediação são mais propensos a ter eventos extremos.

Universidade Federal de Sao Carlos The Wireless Sensor Networks (WSNs) and Mobile Wireless Sensor Networks (MWSNs) are being increasingly used by different applications, such as monitoring of animals, monitoring of vital signs, environmental monitoring, surveillance and protection of critical infrastructure, leaking gas, among many others. Some of these applications are already making use of mobile sensor nodes, such as underwater monitoring, precision agriculture, among many others. Due to restricted resources of sensor nodes, especially in relation to energy consumption, the development for solutions based on WSN and MWSN becomes limited. The use of mobile sensor nodes, which typically has more computational resources, power and communication, can help to reduce the energy consumption of fixed nodes, increasing the lifetime of the network. Networks that use mobile sensor nodes (fixed and mobile) with different types of hardware are called Wireless Sensor Networks Heterogeneous Mobile. This paper presents the RAHMoN (Routing Algorithm for Heterogeneous Mobile Networks), which makes use of data aggregation technique to reduce the traffic transmissions on the network, hierarchy of nodes (clustering), and use of sensor nodes (fixed and mobile) that collaborate to deliver data to a sink node at high speed. In RAHMoN, the network is configured using the techniques of inundation (flooding) and inundation reverse (reverse flooding) to collect the fixed position of sensor nodes and form an adjacency matrix. This matrix helps to build routes for data delivery to the sink and is stored in the mobile sensor nodes. Results show that our solution can guarantee a high packages delivery rate, low latency and reduce the delay of packet delivery. The solution was compared with the WHISPER, present in the literature and also focused on the delivery of data to sink node at high speed. As Redes de sensores sem Fio (RSSFs) e Redes de Sensores Sem Fio Móveis (RSSFMs) estão sendo cada vez mais utilizadas por diferentes aplicações, tais como: monitoramento de animais, monitoramento de sinais vitais, monitoramento ambiental, vigilância e proteção de infraestruturas críticas, vazamento de gás, dentre inúmeras outras. Algumas dessas aplicações já fazem uso de nós sensores móveis. Devido aos recursos restritos dos nós sensores, principalmente em relação ao consumo energético, o desenvolvimento de soluções baseadas em RSSF e RSSFM torna-se limitado. O uso de nós sensores móveis, que tipicamente têm mais recursos computacionais, de energia e de comunicação, pode ajudar a reduzir o consumo de energia dos nós fixos, aumentando o tempo de vida da rede. Redes que utilizam nós sensores (fixos e móveis) com diferentes tipos de hardware são denominadas Redes de Sensores Sem Fio Móvel Heterogênea. Neste trabalho é apresentado o RAHMoN (Routing Algorithm for Heterogeneous Mobile Networks), que faz uso da técnica de agregação de dados para reduzir o tráfego de transmissões na rede, da hierarquização de nós (clustering), da utilização de nós sensores (fixos e móveis) e de um sink em alta velocidade. No RAHMoN, a rede é configurada utilizando flooding e flooding reverse para coletar a posição dos nós sensores fixos e formar uma matriz de adjacência. Essa matriz auxilia na construção de rotas durante a entrega dos dados para o sink e será armazenada nos nós sensores móveis. Resultados de avaliação mostram que a nossa solução consegue garantir uma alta taxa de entrega de pacotes, diminuir a latência e reduzir o atraso de entrega dos pacotes. A solução foi comparada com o WHISPER, presente na literatura e também voltado à entrega de dados para o nó sink em alta velocidade.

Associadas a um grafo G, temos a matriz de adjacência A(G) e a matriz laplaciana L(G). Este trabalho descreve algumas propriedades dessas matrizes e de seus autovalores em relação a características estruturais do grafo. Veremos que, em geral, somente o espectro de G, isto é, conjunto de autovalores de A(G), não é capaz de revelar todas as informações a respeito do grafo. Apresentaremos também uma nova cota superior para a soma dos k maiores autovalores laplacianos de uma árvore com n vértices, para k {1, . . . , ng}. Esse limite nos permitirá demonstrar que, dentre todas as árvores de n vértices, a árvore com energia laplaciana máxima é a estrela Sn, o que foi conjecturado por Radenkovi¢ e Gutman [18]. Associated with a graph G, we have the adjacency matrix A(G) and the Laplacian matrix L(G). This work relates properties of these matrices and their eigenvalues to structural characteristics of the graph. We will see that, in general, the spectrum of G, namely the set of eigenvalues of A(G), does not reveal all the information about the graph. We will also present a new upper bound on the sum of the k largest Laplacian eigenvalues of a tree with n vertices, where k {1, . . . , ng}. This result is used to establish that the n-vertex star Sn has the highest Laplacian energy over all n-vertex trees, which answers a rmatively to a question raised by Radenkovi¢ and Gutman [18].

Dissertação (mestrado) - Universidade de Brasília, Instituto de Física, 2010. Nesta dissertação, nós discutimos o Sistema de Transporte Urbano do Distrito Federal utilizando a teoria de redes complexas, a partir da definição de três redes: rede-P, rede-L e rede-B. Na rede-P, os pontos de parada de ônibus representam os nós e as arestas são representadas pela existência de linhas de ônibus que passam em dois pontos. Na rede-L, as linhas de ônibus representam os nós. Se duas linhas passam por, pelo menos, um ponto de parada em comum, então existe aresta nesse par de linhas de ônibus. A rede-B é uma rede bipartida, nesse caso, tanto os pontos de parada como as linhas de ônibus representam os nós da rede, onde as arestas ligam somente os nós de tipos diferentes. Geramos as matrizes de adjacências AP, AL, MP e ML, essas duas últimas representam grafos de multiplicidade de arestas (redes ponderadas) dos dois primeiros e a matriz de incidência B representa a rede-B bipartida. Construímos a matriz-T, matriz de transbordo, para análise do número de transbordos necessários numa situação em que não exista conexão direta entre dois nós. Obtivemos resultados de rede de mundos pequenos para a rede- P não ponderada, por meio da análise do coeficiente de aglomeração e do número de transbordos. Como resultados da análise do grau do nó, encontramos a distribuição do grau do nó das redes ponderadas e calculamos sua entropia, observamos que a rede-B apresenta uma curva do tipo lei de potência para a distribuição do grau do nó. Além disso, concluímos que a rede-P apresenta características de rede de mundos pequenos. _______________________________________________________________________________________ ABSTRACT In this work, we studied Distrito Federal's Urban transport System using complex network theory, from the definition of three networks: the P-network, the L-network and the B- network. On the P-network, every bus stop is represented by one node and the edge represents the existence of a bus route between two bus stops. On the L-network, bus routes are represented by a node. If two bus routes pass on at least one common bus stop, there is a edge between this pair of routes. The network-B is a bipartite network, in this case, both the bus stops as bus routes represent nodes network, where edges only connect nodes of difierent type. Adjacency matrix AP, AL, MP and ML are generated, the last two ones representing graphs with multiedge (weighed network) from the first two ones and the incident matrix B to represent the mixed B-network. Also is build the T network, the bus transfer bus stop for analysis of the absence of direct connection between bus stops. Results for a small-world network on the unweighted P-network were obtained by means of clustering coeficient analysis and number of transfer bus stops. We found degree distribution for the weighed networks and calculated it's entropy, observed that B-network shows a power law curve for the degree distribution. Also, we conclude that the P-network shows small-world network features.

Conselho Nacional de Desenvolvimento Científico e Tecnológico In this work, a performance analysis of transmission schemes employing turbo trellis coded modulation. In general, the performance analysis of such schemes is guided by evaluating the error probability of these schemes. The exact evaluation of this probability is very complex and inefficient from the computational point of view, a widely used alternative is the use of union bound of error probability, because of its easy implementation and computational produce bounds that converge quickly. Since it is the union bound, it should use to expurge some elements of distance spectrum to obtain a tight bound. The main contribution of this work is that the listing proposal is carried out from the puncturing at the level of symbol rather than bit-level as in most works of literature. The main reason for using the symbol level puncturing lies in the fact that the enummerating function of the turbo scheme is obtained directly from complex sequences of signals through the trellis and not indirectly from the binary sequences that require further binary to complex mapping, as proposed by previous works. Thus, algorithms can be applied through matrix from the adjacency matrix, which is obtained by calculating the distances of the complex sequences of the trellis. This work also presents two matrix algorithms for state reduction and the evaluation of the transfer function of this. The results presented in comparisons of the bounds obtained using the proposed technique with some turbo codes of the literature corroborate the proposition of this paper that the expurgated bounds obtained are quite tight and matrix algorithms are easily implemented in any programming software language Neste trabalho é feita uma análise de desempenho de esquemas de transmissão empregando modulação codificada turbo em treliça. Em geral, a análise de desempenho de tais esquemas é guiada pelo cálculo da probabilidade de erro destes esquemas. O cálculo exato desta probabilidade é muito complexo e ineficiente sob o ponto de vista computacional, uma alternativa muito utilizada é o emprego de limitante da união da probabilidade de erro, por ser de fácil implementação computacional e produzir limitantes que convergem rapidamente. Por se tratar do limitante da união, este deve utilizar de expurgo de alguns elementos do espectro de distâncias do código para a obtenção de um limitante apertado. A principal contribuição deste trabalho é que a enumeração proposta é realizada a partir da perfuração a nível de símbolo e não a nível de bit como na maioria dos trabalhos da literatura. O principal motivo do uso da perfuração a nível de símbolo reside no fato que a função enumeradora do esquema turbo é obtida diretamente das seqüências complexas de sinais através da treliça e não de forma indireta a partir da seqüências binárias que exigem posterior mapeando binário para complexo, como proposto por trabalhos anteriores. Assim, podem ser aplicados algoritmos completamente matriciais a partir da matriz adjacência, que é obtida a partir do cálculo das distâncias das seqüências complexas da treliça e não das seqüências binárias. Neste trabalho também são apresentados dois algoritmos matriciais de redução de estados do codificador bem como do cálculo da função de transferência deste. Os resultados apresentados em forma de comparações dos limitantes obtidos utilizando a técnica proposta com alguns códigos turbo da literatura corroboram com a proposição deste trabalho que os limitantes expurgados obtidos são apertados e os algoritmos completamente matriciais são facilmente implementados em qualquer software de programação simbólica

Conselho Nacional de Desenvolvimento Científico e Tecnológico We present a nestedness index that measures the nestedness pattern of bipartite networks, a problem that arises in theoretical ecology. Our measure is derived using the sum of distances of the occupied elements in the adjacency matrix of the network. This index quantifies directly the deviation of a given matrix from the nested pattern. In the most simple case the distance of the matrix element ai,j is di,j = i+j, the Manhattan distance. A generic distance is obtained as di,j = (i¬ + j¬)1/¬. The nestedness índex is defined by = 1 − where is the temperature of the matrix. We construct the temperature index using two benchmarks: the distance of the complete nested matrix that corresponds to zero temperature and the distance of the average random matrix that is defined as temperature one. We discuss an important feature of the problem: matrix occupancy. We address this question using a metric index ¬ that adjusts for matrix occupancy Apresentamos um índice de aninhamento que mede o padrão de aninhamento de redes bipartidas, um problema que surge em ecologia teórica. Nossa medida é construída através da soma das distâncias dos elementos ocupados na matriz de adjacência da rede. Este índice quantifica diretamente o desvio de uma dada matriz em relação a um padrão aninhado. No caso mais simples a distância do elemento ai,j da matriz é di,j = i + j, a distância de Manhattan. Uma distância genérica é obtida através de di,j = (i¬ + j¬)1/¬. O índice de aninhamento é definido por = 1 − , onde é a temperatura da matriz. Construímos o índice de temperatura utilizando dois padrões de referência: a distância da matriz completamente aninhada, que corresponde `a temperatura zero, e a distância da matriz aleatória média, definida de modo que sua temperatura seja um. Discutimos uma importante característica do problema, a ocupação da matriz. Abordamos esta questão introduzindo o índice métrico ¬ que permite o ajuste de matrizes com diferentes ocupações

Made available in DSpace on 2016-03-22T17:26:09Z (GMT). No. of bitstreams: 1 Vanessa_Souza_da_Fonseca.pdf: 1687661 bytes, checksum: 6dbf2a6dc47f997aa3e8aa0c8f37aced (MD5) Previous issue date: 2008-08-07 This research describes the main contributions of the VirD-GM (Virtual Distributed Geometric Machine Model) for the model of parallelism and distribution of the Project D-GM (Distributed Geometric Machine Project). In order to provide the abstractions of the GM model (Geometric Machine) on a platform to support the implementation distributed and / or parallel computations, the middleware EXEHDA (Execution Environment for High Distributed Applications) is considered as the execution environment. The work enabled to create and manage an environment of parallel and directed programming, and promote the implementation, in this environment, of applications developed in the visual environment VPE-GM (Visual Programming Environment for the Geometric Machine Model). These applications are, by nature, parallel and restricted to the study of parallel algorithms for Scientific Computation. The work focuses on the design and construction of the software architecture of the VirD-GM, which is responsible for managing parallel computations obtained by the application of process constructors defined by the GM model. In this context, this research does not only disposes the construction of the structural vision of the project D-GM but also consolidates its integration with the functional vision. It is characterized by an extension of the visual environment VPEGM, which is responsible for the environment development and code generation for the Project D-GM. Among the main contributions, one may consider: (i) formalization of the concepts of concurrency and conflict intermittent with the notions of communication and synchronization of processes, directly related to the space-time structure of the GM model; (ii) modeling and implementation of the loading, management and control structures of the VirD-GM; (iii) implementation and customization of services provided by the EXEHDA; (iv) construction of the levels of applications, support of execution environment and basic systems; (v) data flow control and manipulation of adjacency matrix related to concurrent computations, including the implementation of barriers of synchronization. The prototyping of VirD-GM and avaliaton achieved through the development of test applications have implemented the viability of theoretical-practical approach proposed in Project D-GM Este trabalho descreve as principais contribuic¸ oes da VirD-GM (Virtual Distributed Geometric Machine Model) para o modelo de distribuic¸ ao e paralelismo do Projeto D-GM (Distributed Geometric Machine Project). Para disponibilizar as abstrac¸ oes do modelo GM (Geometric Machine) em uma plataforma com suporte `a execuc¸ ao distribu ´ıda e/ou concorrente, considera-se o middleware EXEHDA ( Execution Environment for High Distributed Applications) como ambiente de suporte `a execuc¸ ao. O trabalho possibilitou criar e gerenciar um ambiente de programac¸ ao paralela e distribu´ıda, bem como promover a execuc¸ ao, sob este ambiente, das aplicac¸ oes desenvolvidas no ambiente visual VPE-GM (Visual Programming Environment for the Geometric Machine Model). Estas aplicac¸ oes s ao, por natureza, paralelas e direcionadas ao estudo de algoritmos paralelos para a Computac¸ ao Cient´ıfica. O trabalho est´a centrado na concepc¸ ao e construc¸ ao da arquitetura de software da VirD-GM, respons´avel pelo gerenciamento das computac¸ oes paralelas obtidas pela aplicac¸ ao de construtores de processos definidos no modelo GM. Neste contexto, esta dissertac¸ ao n ao s´o viabilizou construc¸ ao da vis ao estrutural do projeto D-GM como tamb´em consolidou sua integrac¸ ao com a vis ao funcional, caracterizada pela extens ao do ambiente VPE-GM, respons´avel pelo ambiente de desenvolvimento e gerac¸ ao de c´odigo para o Projeto D-GM. Dentre as principais contribuic¸ oes, destacam-se: (i) formalizac¸ ao das noc¸ oes de concorr encia e conflito intermitentes com as noc¸ oes de comunicac¸ ao e sincronizac¸ ao de processos, diretamente relacionadas com a estrutura espac¸o-temporal do modelo GM; (ii) definic¸ ao compreendendo a modelagem e implementac¸ ao dos m´odulos de carregamento, gerenciamento e controle da VirD-GM; (iii) estudo, aplicac¸ ao e customizac¸ ao dos servic¸os disponibilizados pelo middleware EXEHDA; (iv) implementac¸ ao das camadas de aplicac¸ ao, de suporte ao ambiente de execuc¸ ao e de sistemas b´asicos; (v) controle do fluxo de dados e manipulac¸ ao das depend encias entre as computac¸ oes concorrentes pelo uso de matrizes de adjac encias, incluindo a implementac¸ ao de barreiras de sincronizac¸ ao, garantindo a correta execuc¸ ao. A prototipac¸ ao da VirD-GM e a avaliac¸ ao obtida com o desenvolvimento de aplicac¸ oes de teste demonstraram a viabilidade da abordagem te´orica-pr´atica proposta no Projeto D-GM

Submitted by Deyse Queiroz (deysequeirozz@hotmail.com) on 2019-03-01T12:18:01Z No. of bitstreams: 1 EDMAR CANDEIA GURJÃO - TESE PPGEE 2003..pdf: 3230411 bytes, checksum: bffb204ecf1947b171c5f8a369249adc (MD5) Made available in DSpace on 2019-03-01T12:18:01Z (GMT). No. of bitstreams: 1 EDMAR CANDEIA GURJÃO - TESE PPGEE 2003..pdf: 3230411 bytes, checksum: bffb204ecf1947b171c5f8a369249adc (MD5) Previous issue date: 2003-06 A Teoria da Informação tem grande sucesso quando aplicada a sistemas ponto-a-ponto, porém muitos problemas permanecem em aberto nos sistems multi-ponto (sistemas de comunicação em rede), como por exemplo a determinação da região de capacidade (conjunto de taxas máximas simultâneas para um conjunto de transmissores) de certos canais. A transmissão da informação de uma fonte para um destino consiste na geração de eventos físicos no lado da fonte e na observação de eventos físicos no lado do destino, para sistemas em rede. tais eventos não podem ser totalmente ordenados. A ausência de ordenação entre eventos foi estudada no âmbito da ciência da computação por Carl A. Petri que introduziu precisamente a noção de "concorrência" entre eventos. Assim é natural esperar que os problemas para o cálculo de capacidade de redes de comunicação possam estar relacionados com os problemas da modelagem de sistemas concorrentes, sendo esta relação a principal motivação desta tese. As redes de Petri são uma ferramenta bastante poderosa para a modelagem desses sistemas capturando os conceitos de estado distribuído, as relações de concorrência e causalidade entre eventos. Nesta tese ínícia-se o uso de redes de Petri para a análise da capacidade de sistemas de comunicação multi-ponto. Neste sentido, é feita uma extensão de uma medida de complexidade definida para as rede de Petri, denominada de compressibilidade. Mostra-se que a compressibilidade de uma rede pode ser calculada a partir de uma matriz de adjacências associada ao seu grafo de cobertura. Também são apresentadas algumas propriedades dessa medida. Usando a compressibilidade, são obtidas algumas conclusões a respeito da representação e do comportamento de sistemas concorrentes. São apresentados exemplos de sistemas não-ruidosos concorrentes que geram símbolos obedecendo restrições semelhantes às restrições de um sistema de gravação magnética. Apresenta-se um método para o cálculo da capacidade desses sistemas por meio da modelagem em redes de Petri e de uma função de rotulação Information theory is a successfully discipline concerning point-to-point systems but many problems in networked communication systems remain open as for example the capacity region of some multi-user channels are unknown. Considering the very basic fact that trasmission of information from a source point to a destination point is due by choosing physical events on the transmitter side in order to cause physical events on the receiver side, it is observed that in case of networked systems in general it is impossible to obtain a total ordering of such that events. In other hand lack of ordering of events in distributed systems was explored by Carl A. Petri that has introduced the precise notion of "concurrency" between events in the circle of the computer science. The today well known Petri nets efficiently model aspects os concurrence and causality between events. In view of comments above i t is natural ask about relationship between problems of capacity of networked communication systems and modelling of concurrent systems. This is the main motivation of this thesis. In this thesis it started the use of Petri nets in the analysis of the capacity of multipoint systems. To this end, a previous defined measure of complexity of Petri nets named compressibility is extended. It is shown that the compressibility of a Petri net can obtained from an adjacency matrix associated with its coverability graph. Some of the properties of this measure are presented. From compressibility definition, some conclusions related to the representation and the behavior of concurrent systems are presented. Examples of concurrent noiseless systems generating sequences of symbols that obey some constraints similar to those found in magnetic recording systems. I t is shown how to calculate the capacity of such that systems by means Petri nets modelling and a handy labeling function that associates physical events to information.