PPGCCM PÓS-GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO FUNDAÇÃO UNIVERSIDADE FEDERAL DO ABC Phone: 11 4996-8337 http://propg.ufabc.edu.br/ppgccm

Banca de DEFESA: HENRIQUE MARTINS BOTELHO

Uma banca de DEFESA de MESTRADO foi cadastrada pelo programa.
DISCENTE : HENRIQUE MARTINS BOTELHO
DATA : 23/09/2020
HORA: 10:00
LOCAL: virtual - Zoom
TÍTULO:

Programa Evolver para Árvores de Steiner Ponderadas


PÁGINAS: 55
RESUMO:

Apresentamos um algoritmo quase-ótimo inspirado em um experimento físico usando películas de sabão para o problema de Steiner ponderado no plano. Tal problema é NP-hard, mesmo em sua versão retilinear e devido a isso algoritmos heurísticos vêm sendo usados para encontrar árvores próximas da mínima. O algoritmo é implementado na linguagem de programação Evolver, que já contém muitas rotinas internas de minimização de energia. Algumas são chamadas pelo programa, o que permite que ele consista de 183 de código-fonte. Nosso algoritmo reproduz o experimento físico de uma película de sabão que se desprende de pinos conectados para chegar a uma configuração estável. Adicionalmente, no caso não-ponderado são feitas comparações com o GeoSteiner. Ao longo do texto, apresentamos diversos resultados de Geometria, Teoria dos Grafos e Física que modelam e nos d ̃ao uma visão do problema sob diferentes ângulos.


MEMBROS DA BANCA:
Membro Titular - Examinador(a) Interno ao Programa - 1722875 - DAVID CORREA MARTINS JUNIOR
Membro Titular - Examinador(a) Externo ao Programa - 1574074 - VALERIO RAMOS BATISTA
Presidente - Externo ao Programa - 254.009.018-40 - MARCELO ZANCHETTA DO NASCIMENTO - UFU
Membro Suplente - Examinador(a) Externo ao Programa - 1851117 - HARLEN COSTA BATAGELO
Membro Suplente - Examinador(a) Externo à Instituição - GUILLERMO ANTONIO LOBOS VILLAGRA - UFSCAR
Notícia cadastrada em: 10/08/2020 13:38
SIGAA | UFABC - Núcleo de Tecnologia da Informação - ||||| | Copyright © 2006-2024 - UFRN - sigaa-1.ufabc.int.br.sigaa-1-prod