Submitted by Etelvina Domingos (etelvina.domingos@ufpe.br) on 2015-03-10T17:15:17Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) dissertacao -Itacira Ataide Silva.pdf: 594325 bytes, checksum: a64733dd2d06f140c960cee9bf78c4bc (MD5) / Made available in DSpace on 2015-03-10T17:15:17Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) dissertacao -Itacira Ataide Silva.pdf: 594325 bytes, checksum: a64733dd2d06f140c960cee9bf78c4bc (MD5) Previous issue date: 2012 / Neste trabalho, faremos uma construção geométrica de soluções para o Problema de Apolônio e usaremos algumas ferramentas da Geometria Enumerativa para resolver o Problema de Steiner.

[pt] Nesta tese faz-se uma extensa revisão bibliográfica sobre o problema de Steiner na métrica retilínea, destacando-se a aplicação do mesmo no projeto de VLSI. São descritas em detalhes várias heurísticas existentes na literatura para as quais estudam-se a complexidade computacional e a qualidade das soluções obtidas. Além disso, são estabelecidos novos resultados relativos ao comportamento de pior caso destas heurísticas. Propõe-se, ainda, duas novas heurísticas para o problema de Steiner na métrica retilínea para as quais são estudadas a complexidade computacional e a qualidade da solução, inclusive com a análise do pior caso. Uma grande quantidade de testes computacionais permitiu a realização de uma comparação do desempenho das diversas heurísticas implementadas, concluindo-se que uma das novas heurísticas propostas fornece, em média, soluções melhores do que aquelas fornecidas pelas demais heurísticas conhecidas na literatura. / [en] In this dissertation we present a survey about the Steiner problem in the rectilinear metric, illustrating its applications to the VLSI desing. A large number of heurístics already described in literature is studied in details. Moreover, we study the complexity of these heuristics and the quality of their solutions. New results concerning their worst case behavior are stated. We also propose two new heuristics for thew Steiner problem in the rectilinear metric, for which we study the complexity and the quality of the solutions, including the worst case analysis. A large nember of computational experiments was conducted and allowed the comparison of the performances of the heuristics implemented. We conclude from these experiments that, in the average, the solutions obtained by one of the new heuristics are better than the solutions obtained by those alreafy available in the literature.

Submitted by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2017-02-01T19:31:46Z No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertação - Ricardo Santos Fonseca.pdf: 3884170 bytes, checksum: c7f03d9fc12e685aabc06b6b6794a61b (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2017-02-01T19:32:02Z (GMT) No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertação - Ricardo Santos Fonseca.pdf: 3884170 bytes, checksum: c7f03d9fc12e685aabc06b6b6794a61b (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2017-02-01T19:32:17Z (GMT) No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertação - Ricardo Santos Fonseca.pdf: 3884170 bytes, checksum: c7f03d9fc12e685aabc06b6b6794a61b (MD5) / Made available in DSpace on 2017-02-01T19:32:17Z (GMT). No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertação - Ricardo Santos Fonseca.pdf: 3884170 bytes, checksum: c7f03d9fc12e685aabc06b6b6794a61b (MD5) Previous issue date: 2016-08-04 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / In this work, lectures on Optimization Problems Applied Geometry. It presents initially a little history of some classic optimization problems in Euclidean Geometry Plana, as the Isoperimétrico Problem, the Heron Problem an the Steiner Problem. From there, he used that knowledge to build definitions, theorems and propositions regarding the Optimization of Geometry which provided grandiose tools for problem solving that can be applied in high school or in Mathematics Olympics. / Neste trabalho, disserta-se sobre Problemas de Otimização Aplicados à Geometria. Apresentase inicialmente um pouco da história de alguns problemas clássicos de otimização em Geometria Euclidiana Plana, como, o Problema Isoperimétrico, o Problema de Heron e o Problema de Steiner. A partir daí, usou-se esse conhecimento para construir definições, teoremas e proposições a respeito da Otimização em Geometria o que proporcionou grandiosas ferramentas para a resolução de problemas que podem ser aplicados no Ensino Médio ou em Olimpíadas de Matemática.

Made available in DSpace on 2015-04-22T22:16:13Z (GMT). No. of bitstreams: 1 Alcides de Castro Amorim Neto.pdf: 1160215 bytes, checksum: 9d45c01bd11518c19b4c0577a41c7455 (MD5) Previous issue date: 2007-05-26 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / An old problem and of great application in the Applied Mathematics is known as problem of Steiner, with consists of the determination of a point that minimizes certain distances, problem this that was studied by famous mathematical as Fermat and Torricelli. A fundamental result in biochemistry and molecular modelling is the determination of the configurations of minimum energy (MECs) for structures such macromoleculares like proteins and DNA. The Steiner minimal trees (SMT) are seen as a useful algorithm paradigm to model these structures. In this work, we will examine how SMTs and the value of the ratio Steiner (½) compared with the MSTs are correlated with the energies MECs in a way physically significant. We verified that carbon and nitrogen atoms are Steiner points in the proteins minimal Steiner trees. / Um problema antigo e de grande aplicação na Matemática Aplicada é conhecido como problema de Steiner, que consiste na determinação de um ponto que minimize certas distâncias, problema este que foi estudado por outros matemáticos renomados como Fermat e Torricelli. Um dos resultados fundamentais em bioquímica e modelagem molecular é a determinação das Configurações de Energia Mínima (MECs) para estruturas macromoleculares tais como proteínas e DNA. As árvores mínimas de Steiner (SMTs) servem de base para elaboração de algoritmos úteis para modelar estas estruturas. Nesta dissertação, faremos uma revisão bibliográfica sobre o problema de Steiner e verificaremos, através de resultados da literatura, como as SMTs e o valor da razão de Steiner (½) comparado com as árvores geradoras mínimas MSTs estão correlacionadas com as MECs de uma maneira fisicamente significativa. Uma das observações relevantes é que os átomos de carbono e nitrogênio atuam como pontos de Steiner nas árvores mínimas de Steiner das proteínas.