Submitted by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2017-02-13T14:54:34Z
No. of bitstreams: 2
Dissertação - Jhones C. Coelho.pdf: 3503211 bytes, checksum: 4de205e9176e97055216984a347c55ef (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2017-02-13T14:55:02Z (GMT) No. of bitstreams: 2
Dissertação - Jhones C. Coelho.pdf: 3503211 bytes, checksum: 4de205e9176e97055216984a347c55ef (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2017-09-21T18:18:45Z (GMT) No. of bitstreams: 2
Dissertação - Jhones C. Coelho.pdf: 3503211 bytes, checksum: 4de205e9176e97055216984a347c55ef (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2017-09-21T18:18:45Z (GMT). No. of bitstreams: 2
Dissertação - Jhones C. Coelho.pdf: 3503211 bytes, checksum: 4de205e9176e97055216984a347c55ef (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Previous issue date: 2016-12-15 / Given a set of points on the plane, we call terminals or regular points, it proves that there is
always a minimum tree that connects called "Steiner tree". The terminals may represent hubs
to routes, circuit elements, or different networks. That is, the problem in question is to optimize
to communication between terminals, if this is represented by a tree of shortest length possible.
Not always the "shorter"is optimization. Steiner problem has variations, for example, the tree
can only follow the edges of the horizontal and vertical directions, as in the case of electrical
circuits. Another variation is when each Steiner point is very expensive, and it is intended to
obtain such a tree with the lowest number of such points. It will be "local minimum"for length,
but not necessarily globally. A physical and quite simple model for "Steiner tree"is that it can
also be performed by soap films, and therefore share minimum surface properties. As an example,
consider a soap solution. Getting closer and withdraw two parallel plates connected by
pins, a film will connect them. This represents a minimum length graph that interconnects the
pins. As is known, the soap films perform the Minimal Surfaces. To view a "Steiner tree"refers
to Numerical Algorithms and Graphical Programming, methods are mainly based on the implementation
of the algorithms. This present work is divided into three parts: a brief history of
optimization problems, highlighted the Steiner problem; theory of the Minimum Tre or Steiner
tree and algorithm Melzak; some examples of real cases. / Dado um conjunto de pontos no plano, que denominamos terminais ou pontos regulares, provase
que sempre existe uma árvore mínima que os conecta, chamado "árvore de Steiner". Os
terminais podem representar centros de conexão para rotas, elementos de circuito elétrico, ou
de redes diversas. Ou seja, o problema em questão é otimizar a comunicação entre os terminais,
caso isto seja representado por uma árvore de menor comprimento possível. Nem sempre o
"menor comprimento"representa a otimização. O Problema de Steiner possui variações, por
exemplo, em que as arestas da árvore só podem seguir direções horizontal e vertical, como
no caso de circuitos elétricos. Outra variação é quando cada ponto Steiner tem custo muito
alto, e pretende-se obter uma tal árvore com o menor número de tais pontos. Ela será "mínimo
local"para comprimento, mas não necessariamente global. Um modelo físico e bastante simples
para "árvore de Steiner"é que ela pode ser também realizada por películas de sabão, e por isso
compartilham propriedades de Superfícies Mínimas. Como exemplo, considere uma solução de
sabão. Ao mergulharmos e retirarmos duas placas paralelas ligadas por pinos, uma película irá
conectá-los. Esta representa um grafo de comprimento mínimo que interliga os pinos. Como
é sabido, as películas de sabão realizam as Superfícies Mínimas. Para visualizar uma "Árvore
de Steiner", recorre-se a Algoritmos Numéricos e Programação Gráfica, os métodos baseiam-se
principalmente na implementação dos algoritmos. Este presente trabalho está dividido em três
partes: breve história dos problemas de otimização, em destaque o problema de Steiner; teoria
sobre a Árvore Mínima ou Árvore de Steiner e o Algoritmo de Melzak; alguns exemplos de casos
reais.
| Identifer | oai:union.ndltd.org:IBICT/oai:http://localhost:tede/5923 |
| Date | 15 December 2016 |
| Creators | Coelho, Jhones Carvalho |
| Contributors | Oliveira, Nilomar Vieira de, Oliveira, Disney Douglas de Lima, Lira, Antonio da Fonseca de |
| Publisher | Universidade Federal do Amazonas, Programa de Pós-graduação em Matemática, UFAM, Brasil, Instituto de Ciências Exatas |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFAM, instname:Universidade Federal do Amazonas, instacron:UFAM |
| Rights | http://creativecommons.org/licenses/by-nc-nd/4.0/, info:eu-repo/semantics/openAccess |
| Relation | 3062048892926319528, 500 |
Page generated in 0.0018 seconds