Submitted by Johnny Rodrigues (johnnyrodrigues@ufcg.edu.br) on 2018-10-01T14:15:29Z No. of bitstreams: 1 ELLOÁ BARRETO GUEDES COSTA - TESE PPGCC 2013..pdf: 53314941 bytes, checksum: 3758326a173b3852e098b78e3e03a1fc (MD5) / Made available in DSpace on 2018-10-01T14:15:29Z (GMT). No. of bitstreams: 1 ELLOÁ BARRETO GUEDES COSTA - TESE PPGCC 2013..pdf: 53314941 bytes, checksum: 3758326a173b3852e098b78e3e03a1fc (MD5) Previous issue date: 2013-11-13 / CNPq / A Teoria da Informação Quântica é uma área de pesquisa a qual considera o estudo dos limites máximos possíveis para o processamento e transmissão da informação, considerando que esta última encontra-se representada de acordo com as leis da Mecânica Quântica. Uma das maneiras de contribuir com esta área de pesquisa é no desenvolvimento de contrapartidas quânticas para os conceitos da Teoria da Informação Clássica. Graças a esta abordagem é que foi proposta a Teoria da Informação Quântica Erro-Zero, a qual considera o uso e as condições para que canais quânticos ruidosos possam transmitir informação clássica sem erros de decodificação. Apesar da proposição desta teoria e dos progressos recentes, foi identificado que o conhecimento das potencialidades, limitações e aplicações desta teoria ainda é incipiente. Na tentativa de minimizar este problema, esta tese apresenta dois novos conceitos ligados à Teoria da Informação Quântica Erro-Zero: (i) a capacidade quântica de sigilo erro-zero; e a (ii) informação acessível erro-zero de fontes quânticas. Em relação à primeira contribuição, tem-se o estabelecimento das condições necessárias para enviar informação por canais quânticos ruidosos sem que haja erros de decodificação e com sigilo absoluto, identificando uma nova capacidade de canais quânticos, estabelecendo a relação desta capacidade com a Teoria dos Grafos e identificando as situações em que esta possui caracterização de letra isolada. A segunda contribuição trata da proposição de uma medida de informação sobre fontes quânticas, a qual mensura o potencial de decodificar, sem erros, estados quânticos emitidos por estas fontes. Obter esta medida é um problema análogo ao de calcular a capacidade erro-zero de canais clássicos equivalentes e não há medida equivalente na Teoria da Informação Erro-Zero Clássica. Os conceitos propostos colaboram para o desenvolvimento da Teoria da Informação Quântica Erro-Zero em termos teóricos e práticos, uma vez que é possível considerar implementações de ambas contribuições com tecnologia existente atualmente. Além disto, intersecções da Teoria da Informação Quântica Erro-Zero junto à Criptografia, Teoria dos Grafos e Ciência da Computação são identificadas. O estabelecimento de tais contribuições colabora diretamente para a resolução de um dos desafios da Teoria da Informação Quântica, o qual trata da determinação de limites para a classe de tarefas de processamento de informação que são possíveis considerando a utilização da Mecânica Quântica. / Quantum Information Theory is a research area that investigates the limits of information processing and transmission considering the laws of Quantum Mechanics. The translation of concepts from Classical Information Theory is a widely known approach to contribute to Quantum Information Theory. Thanks to that, the Quantum Zero-Error Information Theory was proposed. This theory investigates the use and the conditions for classical information exchange through noisy quantum channels without decoding errors. Despite the recent developments, it wasidentified that the knowledge about its potentialities, limitations and applications is still incipient. In the attempt to minimize this problem, this thesis presents two new concepts related to the Quantum Zero-Error Information Theory: (i) the quantum zero-error secrecy capacity; and the (ii) zero-error quantum accessible information. Regarding the first contribution, there is the establishment of the required conditions to send information through quantum channels without decoding errors and with perfect secrecy. This proposal identifies a new capacity of quantum channels, enlightens its relation with Graph Theory, and shows the situations where this capacity has single-letter characterization. Regarding the second contribution, there is the proposal of a quantum information measurement which quantifies the error-free decoding ability of a quantum source. Obtaining such measurement is a problem equivalent to the one of determining the zero-erro capacity of an equivalent classical channel and for which there is no counterpart in Classical Zero-Error Information Theory. The concepts proposed collaborate to Quantum Zero-Error Information Theory in theoretical and practical ways, since it is possible to implement both of them using current technology. Moreover, intersections with Cryptography, Graph Theory and Computer Science were identified. These concepts contribute straightforwardly to the resolution of a challenge of Quantum Information Theory which is the determination of the limits for the tasks of information processing that can be accomplished considering the use of Quantum Mechanics.

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. / 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.

Submitted by Izabel Franco (izabel-franco@ufscar.br) on 2016-10-11T17:36:54Z No. of bitstreams: 1 DissVAK.pdf: 4608619 bytes, checksum: 3022034b9035e4e8caf1195902d24581 (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-10-21T13:03:21Z (GMT) No. of bitstreams: 1 DissVAK.pdf: 4608619 bytes, checksum: 3022034b9035e4e8caf1195902d24581 (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-10-21T13:03:27Z (GMT) No. of bitstreams: 1 DissVAK.pdf: 4608619 bytes, checksum: 3022034b9035e4e8caf1195902d24581 (MD5) / Made available in DSpace on 2016-10-21T13:03:34Z (GMT). No. of bitstreams: 1 DissVAK.pdf: 4608619 bytes, checksum: 3022034b9035e4e8caf1195902d24581 (MD5) Previous issue date: 2016-08-12 / Não recebi financiamento / Cluster analysis is the organization of a collection of patterns into clusters based on similarity which is determined by using properties of data. Clustering techniques can be useful in a variety of knowledge domains such as biotechnology, computer vision, document retrieval and many others. An interesting area of biology involves the concept of microRNAs (miRNAs) that are approximately 22 nucleotide-long non-coding RNA molecules that play important roles in gene regulation. Clustering miRNA sequences can help to understand and explore sequences belonging to the same cluster that has similar biological functions. This research work investigates and explores seven unsupervised clustering algorithms based on graphs that can be divided into three categories: algorithm based on region of influence, algorithm based on minimum spanning tree and spectral algorithm. To assess the contribution of the proposed algorithms, data from miRNA families stored in the online miRBase database were used in the conducted experiments. The results of these experiments were presented, analysed and evaluated using clustering validation indexes as well as visual analysis. / A análise de agrupamento é uma organização de coleção de padrões em grupos, baseando-se na similaridade das propriedades pertencentes aos dados. A técnica de agrupamento pode ser utilizado em muitas áreas de conhecimento como biotecnologia, visão computacional, recuperação de documentos, entre outras. Uma área interessante da biologia envolve o conceito de microRNAs (miRNAs), que são moléculas não-codificadas de RNA com aproximadamente 22 nucleotídeos e que desempenham um papel importante na regulação dos genes. O agrupamento de sequências de miRNA podem ajudar em sua exploração e entendimento, pois as sequências que pertencem ao mesmo grupo possuem uma função biológica similar. Esse trabalho explora e investiga sete algoritmos de agrupamentos não-supervisionados baseados em grafos que podem ser divididos em três categorias: algoritmos baseados em região de influência, algoritmos baseados em árvore spanning minimal e algoritmo espectral. Para avaliar a contribuição dos algoritmos propostos, os experimentos conduzidos utilizaram os dados das famílias de miRNAs disponíveis no banco de dados denominado miRBase. Os resultados dos experimentos foram apresentados, analisados e avaliados usando índices de validação de agrupamento e análise visual.

Os sistemas de transporte público (STP) são entidades complexas formados por vários subsistemas (administração, gerenciamento de frota, manutenção de veículos, segurança, bilhetagem, engenharia de tráfego, urbanismo, recursos humanos, entre outros). Os STP oferecem diversas rotas de veículos coletivos para atender os usuários do serviço mas o planejamento das rotas é uma das áreas que exigem atenção e são de difícil avaliação de desempenho. Estas rotas formam malhas que podem ser abstraídas como grafos, em vários tipos de representações, como por exemplo as paradas associadas aos nós e uma rota (ou linha) de veículos associada a uma sequência de conexões ou arestas que interligam estes pontos. Da representação do STP como grafos, é possível extrair informações importantes a partir de métricas como dimensões, centralidades, pesos, entre outras, e classificar o STP em algum modelo já estudado. A partir do modelo estabelecido, melhorias no sistema podem ser propostas e uma posterior re-análise dos resultados das novas medidas no modelo pode justificar ou não uma possível implementação destas propostas no sistema real. Neste trabalho um sistema de transporte público foi analisado como rede complexa, especificamente o STP de Curitiba, no estado do Paraná, Brasil. Demonstrou-se que este sistema, em representação espaço-L, possui características de rede complexa do tipo scale free. Tal sistema possuía onze categorias de rotas de ônibus, sendo que as principais categorias foram analisadas como rede complexa para avaliar sua influência nas métricas do sistema como um todo. Adicionalmente, combinando as métricas de redes complexas com o método k-means de agrupamento nesse STP, foram identificadas regiões geográficas da cidade que possuem as maiores e menores características de conectividade para os habitantes de Curitiba, sinalizando possíveis degradações de atendimento do sistema de transporte. O estudo revelou que, em Curitiba, a região central é a melhor servida, enquanto que algumas regiões periféricas no sudeste e nordeste da cidade são pouco favorecidas de transporte público. / Public transportation systems (PTS) are complex entities composed by many different subsystems (administration, vehicles management and maintenance, security, taxing, trafic engineering, urbanism, human resources and others). PTS offers various routes using public sharing vehicules to serve users, and the route planning is one of the issues that demand attention and has hard performance assessment. This routes form meshes in many types of representation, e. g., vehicle stops as nodes and a route as a sequence of links that connect their nodes. From PTS representation as graphs, it is possible to extract valuable informations from metrics as dimensions, centralities, weight and others, and to classify this PTS within some model already studied. Towards established models, system enhancements can be proposed and posterior re- analysis of such improved systems can justify or not their implementation in the real system. At this work a public transport system was analysed as Complex Network, specifically Curitiba’s PTS, (Paraná, Brazil). Here it was demonstrated that this system, represented in l-space, has network characteristics of scale-free networks. This system has eleven bus routes categories, in which main categories were analysed as complex networks to assess their influence on whole system metrics. Additionally, combining both complex network metrics and k-means method on this PTS, geographic areas of the city showing best and worst connectivity characteristics for the inhabitants of Curitiba were identified, which allows detecting potential transportation system weakness. This study revealed that Curitiba’s central region is best served, and some periphericals areas at southeast and northeast have low public transportation service.

ANP / Este trabalho propõe o uso de Mapas Cognitivos Fuzzy Dinâmicos (DFCM, do inglês Dynamic Fuzzy Cognitive Maps), uma evolução dos Mapas Cognitivos Fuzzy (FCM), para o desenvolvimento de sistemas autônomos para tomada de decisões. O FCM representa o conhecimento de forma simbólica, através de conceitos e relações causais dispostas em um grafo. Na sua versão clássica, os FCMs são usados no desenvolvimento de modelos estáticos, sendo inapropriados para o desenvolvimento de modelos temporais ou dinâmicos devido à ocorrência simultânea de todas as causalidades em uma estrutura fixa dos grafos, i.e., os conceitos e suas relações causais são invariantes no tempo. O DFCM utiliza o mesmo formalismo matemático do FCM através de grafos, acrescentando funcionalidades, como por exemplo, a capacidade de auto adaptação através de algoritmos de aprendizagem de máquina e a possibilidade de inclusão de novos tipos de conceitos e relações causais ao modelo FCM clássico. A partir dessas inclusões, é possível construir modelos DFCM para tomada de decisões dinâmicas, as quais são necessárias no desenvolvimento de ferramentas inteligentes em áreas de conhecimento correlatas à engenharia, de modo especifico a construção de modelos aplicados em Robótica Autônoma. Em especial, para as áreas de Robótica de Enxame e Vida artificial, como abordados nesta pesquisa. O sistema autônomo desenvolvido neste trabalho aborda problemas com diferentes objetivos (como desviar de obstáculos, coletar alvos ou alimentos, explorar o ambiente), hierarquizando as ações necessárias para atingi-los, através do uso de uma arquitetura para o planejamento, inspirada no modelo clássico de Subsunção de Brooks, e uma máquina de estados para o gerenciamento das ações. Conceitos de aprendizagem de máquina, em especial Aprendizagem por Reforço, são empregadas no DFCM para a adaptação dinâmica das relações de casualidade, possibilitando o controlador a lidar com eventos não modelados a priori. A validação do controlador DFCM proposto é realizada por meio de experimentos simulados através de aplicações nas áreas supracitadas. / This dissertation proposes the use of Dynamic Fuzzy Cognitive Maps (DFCM), an evolution of Fuzzy Cognitive Maps (FCM), for the development of autonomous system to decision-taking. The FCM represents knowledge in a symbolic way, through concepts and causal relationships disposed in a graph. In its standard form, the FCMs are limited to the development of static models, in other words, classical FCMs are inappropriate for development of temporal or dynamic models due to the simultaneous occurrence of all causalities in a permanent structure, i.e., the concepts and the causal relationships are time-invariant. The DFCM uses the same mathematical formalism of the FCM, adding features to its predecessor, such as self-adaptation by means of machine learning algorithms and the possibility of inclusion of new types of concepts and causal relationships into the classical FCM model. From these inclusions, it is possible to develop DFCM models for dynamic decision-making problems, which are needed to the development of intelligent tools in engineering and other correlated areas, specifically, the construction of autonomous systems applied in Autonomous Robotic. In particular, to the areas of Swarm Robotics and Artificial Life, as approached in this research. The developed autonomous system deals with multi-objective problems (such as deviate from obstacle, collect target or feed, explore the environment), hierarchizing the actions needed to reach them, through the use of an architecture for planning, inspired by the Brook’s classical Subsumption model, and a state machine for the management of the actions. Learning machine algorithms, in particular Reinforcement Learning, are implemented in the DFCM to dynamically tune the causalities, enabling the controller to handle not modelled event a priori. The proposed DFCM model is validated by means of simulated experiments applied in the aforementioned areas.

Os sistemas de transporte público (STP) são entidades complexas formados por vários subsistemas (administração, gerenciamento de frota, manutenção de veículos, segurança, bilhetagem, engenharia de tráfego, urbanismo, recursos humanos, entre outros). Os STP oferecem diversas rotas de veículos coletivos para atender os usuários do serviço mas o planejamento das rotas é uma das áreas que exigem atenção e são de difícil avaliação de desempenho. Estas rotas formam malhas que podem ser abstraídas como grafos, em vários tipos de representações, como por exemplo as paradas associadas aos nós e uma rota (ou linha) de veículos associada a uma sequência de conexões ou arestas que interligam estes pontos. Da representação do STP como grafos, é possível extrair informações importantes a partir de métricas como dimensões, centralidades, pesos, entre outras, e classificar o STP em algum modelo já estudado. A partir do modelo estabelecido, melhorias no sistema podem ser propostas e uma posterior re-análise dos resultados das novas medidas no modelo pode justificar ou não uma possível implementação destas propostas no sistema real. Neste trabalho um sistema de transporte público foi analisado como rede complexa, especificamente o STP de Curitiba, no estado do Paraná, Brasil. Demonstrou-se que este sistema, em representação espaço-L, possui características de rede complexa do tipo scale free. Tal sistema possuía onze categorias de rotas de ônibus, sendo que as principais categorias foram analisadas como rede complexa para avaliar sua influência nas métricas do sistema como um todo. Adicionalmente, combinando as métricas de redes complexas com o método k-means de agrupamento nesse STP, foram identificadas regiões geográficas da cidade que possuem as maiores e menores características de conectividade para os habitantes de Curitiba, sinalizando possíveis degradações de atendimento do sistema de transporte. O estudo revelou que, em Curitiba, a região central é a melhor servida, enquanto que algumas regiões periféricas no sudeste e nordeste da cidade são pouco favorecidas de transporte público. / Public transportation systems (PTS) are complex entities composed by many different subsystems (administration, vehicles management and maintenance, security, taxing, trafic engineering, urbanism, human resources and others). PTS offers various routes using public sharing vehicules to serve users, and the route planning is one of the issues that demand attention and has hard performance assessment. This routes form meshes in many types of representation, e. g., vehicle stops as nodes and a route as a sequence of links that connect their nodes. From PTS representation as graphs, it is possible to extract valuable informations from metrics as dimensions, centralities, weight and others, and to classify this PTS within some model already studied. Towards established models, system enhancements can be proposed and posterior re- analysis of such improved systems can justify or not their implementation in the real system. At this work a public transport system was analysed as Complex Network, specifically Curitiba’s PTS, (Paraná, Brazil). Here it was demonstrated that this system, represented in l-space, has network characteristics of scale-free networks. This system has eleven bus routes categories, in which main categories were analysed as complex networks to assess their influence on whole system metrics. Additionally, combining both complex network metrics and k-means method on this PTS, geographic areas of the city showing best and worst connectivity characteristics for the inhabitants of Curitiba were identified, which allows detecting potential transportation system weakness. This study revealed that Curitiba’s central region is best served, and some periphericals areas at southeast and northeast have low public transportation service.

ANP / Este trabalho propõe o uso de Mapas Cognitivos Fuzzy Dinâmicos (DFCM, do inglês Dynamic Fuzzy Cognitive Maps), uma evolução dos Mapas Cognitivos Fuzzy (FCM), para o desenvolvimento de sistemas autônomos para tomada de decisões. O FCM representa o conhecimento de forma simbólica, através de conceitos e relações causais dispostas em um grafo. Na sua versão clássica, os FCMs são usados no desenvolvimento de modelos estáticos, sendo inapropriados para o desenvolvimento de modelos temporais ou dinâmicos devido à ocorrência simultânea de todas as causalidades em uma estrutura fixa dos grafos, i.e., os conceitos e suas relações causais são invariantes no tempo. O DFCM utiliza o mesmo formalismo matemático do FCM através de grafos, acrescentando funcionalidades, como por exemplo, a capacidade de auto adaptação através de algoritmos de aprendizagem de máquina e a possibilidade de inclusão de novos tipos de conceitos e relações causais ao modelo FCM clássico. A partir dessas inclusões, é possível construir modelos DFCM para tomada de decisões dinâmicas, as quais são necessárias no desenvolvimento de ferramentas inteligentes em áreas de conhecimento correlatas à engenharia, de modo especifico a construção de modelos aplicados em Robótica Autônoma. Em especial, para as áreas de Robótica de Enxame e Vida artificial, como abordados nesta pesquisa. O sistema autônomo desenvolvido neste trabalho aborda problemas com diferentes objetivos (como desviar de obstáculos, coletar alvos ou alimentos, explorar o ambiente), hierarquizando as ações necessárias para atingi-los, através do uso de uma arquitetura para o planejamento, inspirada no modelo clássico de Subsunção de Brooks, e uma máquina de estados para o gerenciamento das ações. Conceitos de aprendizagem de máquina, em especial Aprendizagem por Reforço, são empregadas no DFCM para a adaptação dinâmica das relações de casualidade, possibilitando o controlador a lidar com eventos não modelados a priori. A validação do controlador DFCM proposto é realizada por meio de experimentos simulados através de aplicações nas áreas supracitadas. / This dissertation proposes the use of Dynamic Fuzzy Cognitive Maps (DFCM), an evolution of Fuzzy Cognitive Maps (FCM), for the development of autonomous system to decision-taking. The FCM represents knowledge in a symbolic way, through concepts and causal relationships disposed in a graph. In its standard form, the FCMs are limited to the development of static models, in other words, classical FCMs are inappropriate for development of temporal or dynamic models due to the simultaneous occurrence of all causalities in a permanent structure, i.e., the concepts and the causal relationships are time-invariant. The DFCM uses the same mathematical formalism of the FCM, adding features to its predecessor, such as self-adaptation by means of machine learning algorithms and the possibility of inclusion of new types of concepts and causal relationships into the classical FCM model. From these inclusions, it is possible to develop DFCM models for dynamic decision-making problems, which are needed to the development of intelligent tools in engineering and other correlated areas, specifically, the construction of autonomous systems applied in Autonomous Robotic. In particular, to the areas of Swarm Robotics and Artificial Life, as approached in this research. The developed autonomous system deals with multi-objective problems (such as deviate from obstacle, collect target or feed, explore the environment), hierarchizing the actions needed to reach them, through the use of an architecture for planning, inspired by the Brook’s classical Subsumption model, and a state machine for the management of the actions. Learning machine algorithms, in particular Reinforcement Learning, are implemented in the DFCM to dynamically tune the causalities, enabling the controller to handle not modelled event a priori. The proposed DFCM model is validated by means of simulated experiments applied in the aforementioned areas.

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. / 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.

Made available in DSpace on 2016-08-17T14:52:43Z (GMT). No. of bitstreams: 1 Milson Monteiro.pdf: 1924077 bytes, checksum: 78f931b493f756dec0edee7a465e1099 (MD5) Previous issue date: 2002-06-07 / Conselho Nacional de Desenvolvimento Científico e Tecnológico / This works concern software development (graphical user interface) that makes possible to analyze the interconnection in a LAN (Local Area Network) using CORBA (Common Object Request Broker Architecture) on distributed and heterogeneous environment among several outlying machines. This works presents paradigms of graphs theory: shortest paths problems (Dijkstra-Ford-Moore-Belman), maximum flow problems (Edmonds-Karp) and minimum cost flow problems (Busacker-Gowen) to formalize the interface development. We discoursed on the graphs theory and networks flows that are essentials to guarantee theoretical insight. / O objeto de estudo deste trabalho é o desenvolvimento de um software (interface gráfica do usuário) que possibilita analisar a interconexão de uma LAN (Local Area Network) usando CORBA (Common Object Request Broker Architecture) em ambientes distribuídos e heterogêneos entre diversas máquinas periféricas. Este trabalho apresenta os paradigmas da teoria de grafos: menor caminho (Dijkstra, Ford-Moore-Belman), fluxo máximo (Edmonds-Karp) e fluxo de custo mínimo (Busacker-Gowen) para formalizar o desenvolvimento da interface. Discorremos sobre a teoria de grafos e fluxos em redes que são relevantes para garantir o embasamento teórico.