1 |
A estrutura complexa das redes sociaisRibeiro, Mauricio Aparecido 26 August 2016 (has links)
Made available in DSpace on 2017-07-21T19:25:54Z (GMT). No. of bitstreams: 1
Mauricio A Ribeiro.pdf: 11596045 bytes, checksum: a3c106c698d0e695c79bdb2053e8bd59 (MD5)
Previous issue date: 2016-08-26 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / In this study, we discuss the presence of social structures in classical literature, in particular the ones by two writers: Homer ("Odyssey") and J.R.R. Tolkien ("The Silmarillion", "The Hobbit"and the trilogy "The Lord of the Rings"), that, somehow, influenced the society in different ways. In this context, based on the pieces of definition of social relations presented
in this work, we analyze the literary social structures that are presented in these books, which have characteristics that are similar to the current online real social structures, like Facebook and Twitter, in which individuals interact in various ways. Therefore, we use graphs theory to study and compare the literary social structures present in that literature and the online real social structures, causing the appearance of connectivity
distributions formed by the social relations among the characters (in the literary social structures) and among individuals (in online real social structures). Such distributions
follow a power law with an exponential cutoff, which differs from connectivity distributions of structures found in the scientific literature. Other properties found in these analyzes are: the ubiquity attribute of the gods that are in the literary social structures (detected through varying the average path length of these structures); the friendship paradox; the transitivity; the assortativity; and the distribution of betweenness centrality. Due to these similarities between the two types of social structures that were studied, we chose to
analyze the vulnerability, the efficiency and the homogeneity of social relations of literary social structures by some attack methodologies, like removing from these structures only a
character, a group of characters or whole communities. / Nesta tese, abordaremos a presença de estruturas sociais em obras clássicas, em particular de dois escritores: Homero (“Odisseia”) e J.R.R. Tolkien (“O Silmarillion”, “O Hobbit” e
a trilogia de “O Senhor dos Anéis”), que, de certa forma, influenciaram a sociedade em diversos níveis. Nesse contexto, com base nas definições de relações sociais apresentadas
neste trabalho, analisamos as estruturas sociais literárias que surgem nessas obras e que possuem características semelhantes às das estruturas sociais reais online) da atualidade, como o Facebook e o Twitter, em que os indivíduos interagem das mais diversas maneiras. Portanto, utilizamos a teoria dos grafos para estudar e comparar as estruturas sociais
literárias presentes em tais obras e as estruturas sociais reais (online), possibilitando o surgimento de distribuições de conectividade formadas pelas relações sociais entre as
personagens (nas estruturas sociais literárias) e entre indivíduos (nas estruturas sociais reais online). Tais distribuições seguem uma lei de potência com truncamento exponencial, o que difere das distribuições de conectividade das estruturas encontradas na literatura científica. Outras propriedades encontradas nessas análises são: o atributo de onipresença das divindades que estão inseridas nas estruturas sociais literárias (detectado através da variação da distância de caminho médio dessas estruturas); o paradoxo da amizade; a transitividade; a assortatividade; e a distribuição de centralidade de intermediação. Devido a tais similaridades entre os dois tipos de estruturas sociais estudadas, optamos por analisar
a vulnerabilidade, a eficiência e a homogeneidade das relações sociais das estruturas sociais literárias mediante algumas metodologias de ataques, como remover dessas estruturas
somente um personagem, um grupo de personagens ou comunidades inteiras.
|
2 |
Geometria discreta e codigos / Discrete geometry and codesStrapasson, João Eloir, 1979- 04 November 2007 (has links)
Orientador: Sueli Irene Rodrigues Costa / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-10T10:56:09Z (GMT). No. of bitstreams: 1
Strapasson_JoaoEloir_D.pdf: 1100322 bytes, checksum: 054aeab4b36f30144155ce6b1668659a (MD5)
Previous issue date: 2007 / Resumo: Este trabalho está dividido em duas partes. A primeira e dedicada ao problema de encontrar o menor vetor não nulo de um reticulado. Este é um problema de alta complexidade computacional e que tem grande interesse tanto para a Teoria dos Códigos, como para diversas outras áreas. Esse mínimo está associado a performance do reticulado em termos da codificação: quanto maior for a razão entre este mínimo e o determinante do reticulado, melhor e a distribuição dos pontos no espaço (alta densidade de empacotamento). Nesta tese demos ênfase ao caso especial dos reticulados obtidos por uma projeção ortogonal do reticulado n-dimensional dos inteiros na direção de seus elementos. Tais reticulados estão associados ao problema de codificação contínua fonte/canal. Mostramos nos casos tri e quadridimensionais em que condições podemos garantir reticulados bons, ou seja, com alta densidade de empacotamento. Neste processo foram também construídos dois novos algoritmos, um para cálculo da base de Minkowski de um reticulado e outro específico para a busca da norma mínima do reticulado-projeção. Na segunda parte trabalhamos com grafos em toros planares que são quocientes de reticulados, os quais são isomorfos a grafos circulantes. Estabelecemos a conexão entre estes códigos esféricos rotulados por grupos cíclicos e códigos perfeitos na métrica de Lee. A partir de tal associação foram também obtidos resultados sobre o gênero 1 e a determinação do dos gênero de uma classe especial de grafos circulantes que tem número arbitrariamente grande de conexões (grau) / Abstract: The research developed here is related and inspired by problems in coding theory. It is presented in two parts. In the first we focus on the search for the minimum nonvanishing vector of a lattice, specially in the case of a projection of the ndimensional integer lattice in the direction of one of its vectors. This is a problem of high computational complexity which is related to the search for efficient joint sourcechannel continuous coding. In the second part we deal with flat torus graphs generated by a quotient of lattices and which are labeled by a a cyclic group of isometries. We show that any circulant graph is isomorphic to one of these graphs and hence associated to a spherical code. Through these isomorphism a complete classification of circulant graphs of genus one and the genus of an arbitrarily high order class of circulant graphs is obtained. / Doutorado / Geometria Topologia / Doutor em Matemática
|
3 |
Algoritmos para problemas de grafos com incertezas / Algorithms for fuzzy graphs problemsHernandes, Fabio 23 February 2007 (has links)
Orientadores: Akebo Yamakami, Marcia Tomie Takahashi / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-08T13:05:12Z (GMT). No. of bitstreams: 1
Hernandes_Fabio_D.pdf: 995506 bytes, checksum: c4a27a827d2ca5ec109571ba03e4e094 (MD5)
Previous issue date: 2007 / Resumo: A teoria de grafos é uma importante área da programação matemática, tendo um importante papel em áreas tais como engenharia e pesquisa operacional. Em particular, ela fornece ferramentas para tratar problemas de redes (tais como: alocação, caminho mÃnimo, fluxo máximo, etc.), que têm aplicações em diversas subáreas da engenharia (por exemplo: telecomunicações, transporte, manufatura, etc.). Estas aplicações podem, entretanto, possuir incertezas em seus parâmetros ou em sua estrutura. Baseado nisto, este trabalho trata de algumas importantes aplicações de problemas em grafos com incertezas em seus parâmetros ou estruturas e propõe algoritmos para encontrar suas soluções. As aplicações estudadas são: problemas de caminho mÃnimo, problemas de fluxo máximo, problemas de fluxo de custo mÃnimo e problemas de coloração de grafos. As incertezas são modeladas por meio da teoria dos conjuntos fuzzy, que tem sido aplicada com sucesso em problemas com incertezas e imprecisões / Abstract: The graph theory is an important area of mathematical programming, it has an important role in fields such as engineering and operational research. In particular, it provides the tools to tackle network problems (e.g. allocation, shortest path, maximum flow, etc), which have applications in several sub areas of engineering (e.g. telecommunications, transportation, manufacturing, etc). These applications can, however, possess uncertainties in their parameters or in their structure. Based on that, this work addresses some important applications of graph problems with uncertainties in their structure or parameters and proposes algorithms to find the solution to them. The applications studied are: shortest path problems, maximum flow problems, minimum cost flow problems and graph coloring problems. The uncertainties are modeled by means of the fuzzy sets theory, which has been successfully applied to problems with uncertainties and vagueness / Doutorado / Automação / Doutor em Engenharia Elétrica
|
4 |
Integração de dados estatísticos sociais no desenvolvimento de uma possível arquitetura para a internet das coisas. / Social data integration on a possible architecture development for internet of things.Riaño Riaño, Diana Patricia 13 September 2016 (has links)
Os objetivos deste trabalho de mestrado consistem em determinar: (i) como modificar a arquitetura de referência de Internet das Coisas para identificar e priorizar as necessidades dos usuários em um determinado contexto; (ii) como transformar dados sociais subjetivos em uma medida objetiva de impacto social; (iii) como correlacionar informações sociais e dados digitais de forma a medir a satisfação dos usuários com os serviços de Internet das Coisas desenvolvidos; (iv) como validar o sistema total; e (v) se a arquitetura é reconfigurável e pode ser adotada e validada em diferentes casos de uso. O método de desenvolvimento começa de uma extensa investigação bibliográfica sobre projetos, arquiteturas e plataformas de Internet das Coisas desenvolvidas e em desenvolvimento, tecnologia social e teoria de grafos. É proposto um mapa conceitual que serve de base a todo o trabalho. A teoria de grafos fornece um conjunto de métricas que permite identificar as reais necessidades de usuários e comunidades e, então, especificar as aplicações e serviços de Internet das Coisas a serem desenvolvidos. ´E proposta uma função de fitness para avaliar a satisfação de requisitos de uma especificação. A validação do método é feita por meio de um estudo de caso. Para uma cidade hipotética são descritos os serviços educacionais, de saúde e de transporte disponíveis. É identificado o problema de oferecimento de serviços educacionais a comunidades distantes e a necessidade desses serviços se integrarem com as entidades culturais e de saúde. Com isso, ´e especificada a aplicação Aula Móvil. Essa aplicação é completamente descrita por meio dos modelos de domínio, de informação, funcional e de comunicação da arquitetura de referência IoT-A. Para o desenvolvimento do software, é feita uma descrição completa em UML: diagrama de classes e diagramas de sequência. Apesar de se ter adotado um estudo de caso simples, fica demonstrada a viabilidade de se integrar a avaliação de dados estatísticos sociais no ciclo de projeto de aplicações de Internet das Coisas. ´E mostrado também que as aplicações de Internet das Coisas geram impacto social a curto, médio e longo prazos. O método e arquitetura propostos neste trabalho são suficientemente genéricos para serem utilizados em outras aplicações relacionadas a uma cidade e também em outros domínios como os de M2M e da iniciativa Industry 4.0. / The objectives of this master thesis consist in determining: (i) how modify an IoT reference architecture to identify and prioritize end user\'s needs in a given context; (ii) how transform subjective social data in a objective measure of social impact; (iii) how correlate social data and digital data to measure the end users\' satisfaction with the developed IoT services; (iv) how validate the total system; and (v) if the architecture is reconfigurable and can be adopted and validated in di?erent use cases. The development method started with and extensive bibliographic research about IoT projects, architectures and platforms, already developed and under development, social technology and graphs theory. A conceptual map is proposed and is used as a basis for the entire work. The graphs theory provides a set of metrics that allow the identification of end users\' and communities\' needs and, then, to specify the IoT applications and services to be developed. A fitness function is proposed to evaluate the fulfillment of requirements of a specification. The whole method validation is made by means of a case study. To do so, the available educational, health and transport services of a hypothetical city are described. The problem of o?ering educational services to distant communities and the need to integrate such services to the cultural and health entities are identified. As a result, a Mobile Class application is specified. This application is completely described by the domain, informational, functional and communicational models of the IoT-A reference architecture. For the software development, a complete UML description is made: class diagrams and sequence diagrams. In spite of having adopted a simple case study, the feasibility of integrating the social statistical data evaluation in the design cycle of IoT applications is demonstrated. It is also shown that IoT applications generate social impact in the short, medium and large terms. The method and architecture proposed in this work are generic enough to be used in other applications related to a city as is other domains as M2M and from the Industry 4.0 Initiative.
|
5 |
Multiaspect graphs / Grafo Multi-aspectosWehmuth, Klaus 22 June 2016 (has links)
Submitted by Maria Cristina (library@lncc.br) on 2017-04-06T18:25:05Z
No. of bitstreams: 1
Klaus_Thesis.pdf: 4909850 bytes, checksum: cd68a30c3bae22dc6ea75b6cb4dc6368 (MD5) / Approved for entry into archive by Maria Cristina (library@lncc.br) on 2017-04-06T18:25:18Z (GMT) No. of bitstreams: 1
Klaus_Thesis.pdf: 4909850 bytes, checksum: cd68a30c3bae22dc6ea75b6cb4dc6368 (MD5) / Made available in DSpace on 2017-04-06T18:25:28Z (GMT). No. of bitstreams: 1
Klaus_Thesis.pdf: 4909850 bytes, checksum: cd68a30c3bae22dc6ea75b6cb4dc6368 (MD5)
Previous issue date: 2016-06-22 / Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) / Different graph generalizations have been recently used in an ad hoc manner to represent time-varying complex networks, i.e. networks in which vertices and edges may vary in time. Similar constructions have also been used to represent multilayer networks, i.e. systems formed by distinct interdependent layers where each layer can be seen as a complex network. In this thesis, we introduce the concept of MultiAspect Graph (MAG). We show that a MAG is isomorphic to a directed graph, which is an important theoretical result because this allows the use of the isomorphic directed graph as a tool to analyze both the properties of a MAG and the behavior of dynamic processes over a MAG. In our proposal, the set of vertices, layers, time instants, or any other independent feature of the system being modelled is considered as an aspect of the MAG. For instance, a MAG is able to represent multilayer or time-varying networks, while both concepts can also be combined to represent a multilayer time-varying network. Since the MAG structure admits an arbitrary (finite) number of aspects, it hence introduces a powerful modelling abstraction for networked complex systems. Further, we present algebraic representations and basic algorithms for MAGs, constructed from well-known graph algorithms, such as degree computing, Breadth First Search (BFS), and Depth First Search (DFS). These algorithms adapted to the MAG context can be used as primitives for building other more sophisticated MAG algorithms. Building upon the basic MAG concept, we also present derived applications, such as a MAG-based unifying model for time-varying graphs as well as MAG-based centrality notions. / Recentemente, várias generalizações de grafos têm sido propostas para tratar problemas específicos envolvendo redes complexas variantes no tempo e redes complexas multi-camadas. Essas representações são propostas de maneira adequada para resolver problemas específicos, mas não são adequadas para uso geral e muitas vezes são incompatíveis entre si. Nesta tese apresentamos o conceito de Grafo Multi-Aspectos (MAG), que é uma generalização de grafos capaz de representar redes variantes no tempo, redes multi-camadas e redes simultaneamente multi-camadas e variantes no tempo. Mostramos que todo MAG é isomorfo a um grafo direcionado, o que é um importante resultado teórico. Com base nesse resultado é possível utilizar o conhecimento previamente obtido em teoria de grafos para problemas envolvendo MAGs. Dessa maneira, torna-se possível criar representações algébricas para MAGs com características semelhantes às encontradas nas representações para grafos orientados. Além disso, pode-se construir algoritmos básicos para MAGs através da adaptação de algoritmos conhecidos para grafos. Esses algoritmos básicos podem servir como modelo para criação de outros algoritmos para MAGs, bem como serem utilizados como primitivas para construção de novos algoritmos. Utilizando essas primitivas, introduzimos o conceito de centralidades em MAGs, bem como construimos algoritmos apropriadas para calcular essas centralidades.
|
6 |
Integração de dados estatísticos sociais no desenvolvimento de uma possível arquitetura para a internet das coisas. / Social data integration on a possible architecture development for internet of things.Diana Patricia Riaño Riaño 13 September 2016 (has links)
Os objetivos deste trabalho de mestrado consistem em determinar: (i) como modificar a arquitetura de referência de Internet das Coisas para identificar e priorizar as necessidades dos usuários em um determinado contexto; (ii) como transformar dados sociais subjetivos em uma medida objetiva de impacto social; (iii) como correlacionar informações sociais e dados digitais de forma a medir a satisfação dos usuários com os serviços de Internet das Coisas desenvolvidos; (iv) como validar o sistema total; e (v) se a arquitetura é reconfigurável e pode ser adotada e validada em diferentes casos de uso. O método de desenvolvimento começa de uma extensa investigação bibliográfica sobre projetos, arquiteturas e plataformas de Internet das Coisas desenvolvidas e em desenvolvimento, tecnologia social e teoria de grafos. É proposto um mapa conceitual que serve de base a todo o trabalho. A teoria de grafos fornece um conjunto de métricas que permite identificar as reais necessidades de usuários e comunidades e, então, especificar as aplicações e serviços de Internet das Coisas a serem desenvolvidos. ´E proposta uma função de fitness para avaliar a satisfação de requisitos de uma especificação. A validação do método é feita por meio de um estudo de caso. Para uma cidade hipotética são descritos os serviços educacionais, de saúde e de transporte disponíveis. É identificado o problema de oferecimento de serviços educacionais a comunidades distantes e a necessidade desses serviços se integrarem com as entidades culturais e de saúde. Com isso, ´e especificada a aplicação Aula Móvil. Essa aplicação é completamente descrita por meio dos modelos de domínio, de informação, funcional e de comunicação da arquitetura de referência IoT-A. Para o desenvolvimento do software, é feita uma descrição completa em UML: diagrama de classes e diagramas de sequência. Apesar de se ter adotado um estudo de caso simples, fica demonstrada a viabilidade de se integrar a avaliação de dados estatísticos sociais no ciclo de projeto de aplicações de Internet das Coisas. ´E mostrado também que as aplicações de Internet das Coisas geram impacto social a curto, médio e longo prazos. O método e arquitetura propostos neste trabalho são suficientemente genéricos para serem utilizados em outras aplicações relacionadas a uma cidade e também em outros domínios como os de M2M e da iniciativa Industry 4.0. / The objectives of this master thesis consist in determining: (i) how modify an IoT reference architecture to identify and prioritize end user\'s needs in a given context; (ii) how transform subjective social data in a objective measure of social impact; (iii) how correlate social data and digital data to measure the end users\' satisfaction with the developed IoT services; (iv) how validate the total system; and (v) if the architecture is reconfigurable and can be adopted and validated in di?erent use cases. The development method started with and extensive bibliographic research about IoT projects, architectures and platforms, already developed and under development, social technology and graphs theory. A conceptual map is proposed and is used as a basis for the entire work. The graphs theory provides a set of metrics that allow the identification of end users\' and communities\' needs and, then, to specify the IoT applications and services to be developed. A fitness function is proposed to evaluate the fulfillment of requirements of a specification. The whole method validation is made by means of a case study. To do so, the available educational, health and transport services of a hypothetical city are described. The problem of o?ering educational services to distant communities and the need to integrate such services to the cultural and health entities are identified. As a result, a Mobile Class application is specified. This application is completely described by the domain, informational, functional and communicational models of the IoT-A reference architecture. For the software development, a complete UML description is made: class diagrams and sequence diagrams. In spite of having adopted a simple case study, the feasibility of integrating the social statistical data evaluation in the design cycle of IoT applications is demonstrated. It is also shown that IoT applications generate social impact in the short, medium and large terms. The method and architecture proposed in this work are generic enough to be used in other applications related to a city as is other domains as M2M and from the Industry 4.0 Initiative.
|
7 |
Réseaux dynamiques de terrain : caractérisation et propriétés de diffusion en milieu hospitalier / Real Dynamic Networks : Characterisation and Diffusion Properties in Hospital ContextsMartinet, Lucie 18 September 2015 (has links)
Durant cette thèse, nous nous sommes intéressés aux outils permettant d'extraire les propriétés structurelles et temporelles de réseaux dynamiques ainsi que les caractéristiques de certains scénarios de diffusion pouvant s'opérer sur ces réseaux. Nous avons travaillé sur un jeu de données spécifiques, issu du projet MOSAR, qui comporte entre autre le réseau de proximité des personnes au cours du temps durant 6 mois à l'hôpital de Berk-sur-mer. Ce réseau est particulier dans le sens où il est constitué de trois dimensions: temporelle, structurelle par la répartition des personnes en services et fonctionnelle car chaque personne appartient à une catégorie socio-professionnelle. Pour chacune des dimensions, nous avons utilisé des outils existants en physique statistique ainsi qu'en théorie des graphes pour extraire des informations permettant de décrire certaines propriétés du réseau. Cela nous a permis de souligner le caractère très structuré de la répartition des contacts qui suit la répartition en services et mis en évidence les accointances entre certaines catégories professionnelles. Concernant la partie temporelle, nous avons mis en avant l'évolution périodique circadienne et hebdomadaire ainsi que les différences fondamentales entre l'évolution des interactions des patients et celle des personnels. Nous avons aussi présenté des outils permettant de comparer l'activité entre deux périodes données et de quantifier la similarité de ces périodes. Nous avons ensuite utilisé la technique de simulation pour extraire des propriétés de diffusion de ce réseau afin de donner quelques indices pour établir une politique de prévention. / In this thesis, we focus on tools whose aim is to extract structural and temporal properties of dynamic networks as well as diffusion characteristics which can occur on these networks. We work on specific data, from the European MOSAR project, including the network of individuals proximity from time to time during 6 months at the Brek-sur-Mer Hospital. The studied network is notable because of its three dimensions constitution : the structural one induced by the distribution of individuals into distinct services, the functional dimension due to the partition of individual into groups of socio-professional categories and the temporal dimension.For each dimension, we used tools well known from the areas of statistical physics as well as graphs theory in order to extract information which enable to describe the network properties. These methods underline the specific structure of the contacts distribution which follows the individuals distribution into services. We also highlight strong links within specific socio-professional categories. Regarding the temporal part, we extract circadian and weekly patterns and quantify the similarities of these activities. We also notice distinct behaviour within patients and staff evolution. In addition, we present tools to compare the network activity within two given periods. To finish, we use simulations techniques to extract diffusion properties of the network to find some clues in order to establish a prevention policy.
|
8 |
Casos especiais ótimos de algoritmos aproximativos para problemas de escalonamento com restrições de precedência em processadores paralelos idênticosLever, Elton Carlos Costa, 92 991210234 22 June 2017 (has links)
Submitted by Elton Lever (elton@icomp.ufam.edu.br) on 2018-08-23T20:26:01Z
No. of bitstreams: 1
DissertacaoMestradoElton Lever-ProfRosiane-PPGI-VF.pdf: 2475783 bytes, checksum: 57e9ed5c603736311bd6f477643ff425 (MD5) / Approved for entry into archive by Secretaria PPGI (secretariappgi@icomp.ufam.edu.br) on 2018-08-23T20:35:20Z (GMT) No. of bitstreams: 1
DissertacaoMestradoElton Lever-ProfRosiane-PPGI-VF.pdf: 2475783 bytes, checksum: 57e9ed5c603736311bd6f477643ff425 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2018-08-24T13:35:27Z (GMT) No. of bitstreams: 1
DissertacaoMestradoElton Lever-ProfRosiane-PPGI-VF.pdf: 2475783 bytes, checksum: 57e9ed5c603736311bd6f477643ff425 (MD5) / Made available in DSpace on 2018-08-24T13:35:28Z (GMT). No. of bitstreams: 1
DissertacaoMestradoElton Lever-ProfRosiane-PPGI-VF.pdf: 2475783 bytes, checksum: 57e9ed5c603736311bd6f477643ff425 (MD5)
Previous issue date: 2017-06-22 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This dissertation addresses the class of job scheduling problems with precedence
constraints and unit execution times, in identical parallel processors. Such a class of
problems is of great importance in computational complexity theory, since small varia-
tions in the conditions involved in scheduling make an easy problem very difficult. Two
major problems involve the condition of the number of processors, where, if the number
of processors is variable, given as input, such problem is proved to be NP-complete, but
if the number of processors is fixed, the problem is still open. In this context, the focus
of the research involves the problem already proven to be NP-complete, where for which
we investigated the main approximation algorithms in the literature and their proofs of
approximation ratio of the optimal, such as of the Garey & Jonhson’s 2-approximation
algorithm, of the Hu, of the Coffman & Graham, and of the Gangal & Ranade with
2 − (7/(3P + 1)), the best approximation ratio in the literature. The approximation ratio proofs
of such algorithms were detailed. As the main contribution of this research, were proved
the optimality for specific classes of acyclic directed graphs involving trees (prece-
dence trees, such as in-tree and out-tree) for the best approximation algorithms literature. / Esta dissertação aborda a classe de problemas de escalonamento de tarefas com
restrições de precedências e tempos unitários em processadores paralelos idênticos.
Tal classe de problemas tem uma grande importância em teoria da complexidade
computacional, uma vez que pequenas variações nas condições envolvidas no esca-
lonamento, fazem com que um problema fácil se torne muito difícil. Dois grandes
problemas envolvem a condição do número de processadores, onde, se o número de
processadores for variável, dado como entrada, tal problema é provado ser NP-completo,
mas, se o número de processadores for fixo, o problema ainda está em aberto. Neste
contexto, o foco da pesquisa envolve o problema já provado ser NP-completo, onde
para qual se investigou os principais algoritmos aproximativos existentes na literatura e
suas provas de razão de aproximação do ótimo, tais como o algoritmo 2-aproximativo
de Garey & Jonhson e as melhorias de Hu, Coffman & Graham e de Gangal &
Ranade (GR) com 2 −(7/(3P+1)), o de melhor razão de aproximação da literatura.
As provas de razão de aproximação de tais algoritmos foram detalhadas. Como principal
contribuição da pesquisa, foram determinados casos especiais ótimos, para classes
específicas de grafos direcionados acíclicos que envolvem arborescências (árvores de
precedência, como in-tree e out-tree) para o melhor algoritmos aproximativo da literatura. / Compreender o que querem em alguns momentos.
|
9 |
Teorie grafů - implementace vybraných problémů / Graph theory - implementation of selected problemsStráník, František January 2009 (has links)
This work is intended on identification with basic problems from the graphs theory area. There are the basic conceptions as well more complicated problems described. The one part of this work is specialized in working of individual types of graphs. It starts with single linked list through double linked list after as much as trees which represented the simplest graphs textures. The other part of this work devotes to the whole graph and describes more complicated problems and their resolution from the theory graphs area. Among these problems belongs to searching in graphs help by Depth First Search and Breadth First Search methods. Then searching the shortest way help by the specific algorithms as are: Dijkstra´s algorithm, Floyd-Warshall´s algorithm and Bellman-Ford´s algorithm. The last part is devoted to problems with searching minimal frames of graphs with usage Kruskal´s algorithm, Jarnik´s algorithm and Boruvka´s algorithm methods.
|
Page generated in 0.1578 seconds