Geometric optimization on visibility problems: metaheuristic and exact solutions

Os problemas de visibilidade têm diversas aplicações a situações reais. Entre os mais conhecidos, e exaustivamente estudados, estão os que envolvem os conceitos de vigilância e ocultação em estruturas geométricas (problemas de vigilância e ocultação). Neste trabalho são estudados problemas de visibilidade em estruturas geométricas conhecidas como polígonos, uma vez que estes podem representar, de forma apropriada, muitos dos objectos reais e são de fácil manipulação computacional. O objectivo dos problemas de vigilância é a determinação do número mínimo de posições para a colocação de dispositivos num dado polígono, de modo a que estes dispositivos consigam “ver” a totalidade do polígono. Por outro lado, o objectivo dos problemas de ocultação é a determinação do número máximo de posições num dado polígono, de modo a que quaisquer duas posições não se consigam “ver”. Infelizmente, a maior parte dos problemas de visibilidade em polígonos são NP-difíceis, o que dá origem a duas linhas de investigação: o desenvolvimento de algoritmos que estabelecem soluções aproximadas e a determinação de soluções exactas para classes especiais de polígonos. Atendendo a estas duas linhas de investigação, o trabalho é dividido em duas partes. Na primeira parte são propostos algoritmos aproximados, baseados essencialmente em metaheurísticas e metaheurísticas híbridas, para resolver alguns problemas de visibilidade, tanto em polígonos arbitrários como ortogonais. Os problemas estudados são os seguintes: “Maximum Hidden Vertex Set problem”, “Minimum Vertex Guard Set problem”, “Minimum Vertex Floodlight Set problem” e “Minimum Vertex k-Modem Set problem”. São também desenvolvidos métodos que permitem determinar a razão de aproximação dos algoritmos propostos. Para cada problema são implementados os algoritmos apresentados e é realizado um estudo estatístico para estabelecer qual o algoritmo que obtém as melhores soluções num tempo razoável. Este estudo permite concluir que as metaheurísticas híbridas são, em geral, as melhores estratégias para resolver os problemas de visibilidade estudados. Na segunda parte desta dissertação são abordados os problemas “Minimum Vertex Guard Set”, “Maximum Hidden Set” e “Maximum Hidden Vertex Set”, onde são identificadas e estudadas algumas classes de polígonos para as quais são determinadas soluções exactas e/ou limites combinatórios.

Assessment of higher plant species suitability for ecological restoration following major disturbance

O presente trabalho é constituído por uma revisão bibliográfica e uma série de estudos científicos experimentais visando a melhoria do conhecimento da ecologia de germinação e resposta ao estresse hídrico em arbustos autóctones. Estes estudos pretendem contribuir para o conhecimento da ecologia de espécies autóctones na fase de germinação e estabelecimento inicial das plântulas através da comparação da resposta de sementes de diferentes proveniências. Os primeiros três capítulos focam-se no estudo dos efeitos de pré-tratamentos na germinação de espécies arbustivas com diferentes estratégias de regeneração e dormência da semente, enquanto os dois últimos capítulos incidem sobre o efeito de diferentes condições de disponibilidade de água na germinação e estabelecimento inicial de plântulas com potencial para restauro ecológico. Este estudo procura abordar aspetos importantes para o estudo e validação do uso de espécies alvo para o restauro ecológico em zonas Mediterrânicas, contribuindo deste modo para a melhoria do conhecimento da ecologia destas espécies. A germinação foi estimulada por pré-tratamentos de calor em quatro das cinco espécies cuja época de dispersão da semente na primavera-verão. As sementes provenientes do sul tenderam a germinar melhor, sendo ao mesmo tempo mais pequenas. Por outro lado, a germinação em espécies cuja dispersão da semente ocorre no outono-inverno variou de acordo com o tipo de dormência da semente. A germinação foi em geral favorecida pela estratificação a frio na espécie apresentando dormência fisiológica mas foi negativamente afetada na espécie que não apresenta dormência. Esta resposta não foi, no entanto, inequívoca pois foi dependente da proveniência estudada. O efeito da estratificação a frio teve em geral um efeito mais positivo ou menos negativo nas sementes provenientes do norte em comparação com as outras proveniências. O stress-osmótico teve um efeito negativo consistente na germinação de Pistacia lentiscus e outro fator que também afetou significativamente a germinação foi a variabilidade intra-populacional entre plantas mãe. As duas proveniências apresentaram diferentes graus de associação entre a germinação e/ou caracteres morfológicos da semente ou planta mãe. Quanto à fase de estabelecimento inicial, o baixo conteúdo em água teve um claro efeito negativo no investimento relativo em biomassa acima do solo e um efeito positivo no investimento relativo em biomassa abaixo do solo em Arbutus unedo. Esta resposta não foi inequívoca, uma vez que as proveniências diferiram em adaptações morfológicas ao baixo conteúdo em água. As plântulas da proveniência mais húmida revelaram uma taxa de crescimento relativo superior mas, ao mesmo tempo, uma fraca adaptação às condições de baixa disponibilidade de água, quando comparadas com as outras proveniências. Ao contrário, as plântulas da proveniência seca com verão mais quente apresentaram semelhantes diâmetro do colo da raiz, peso seco de folhas e performance fisiológica sob os dois regimes de irrigação. Os resultados obtidos revelam diferenças significativas na germinação e desenvolvimento inicial entre as distintas proveniências que poderão estar relacionadas com adaptações ao clima dos locais de origem. Os desenvolvimentos futuros do estudo dos mecanismos subjacentes às adaptações observadas poderiam contribuir para a melhoria das previsões de sucesso do estabelecimento inicial em diferentes populações de plantas, permitindo aumentar a confiança e efetividade de custos nas decisões relacionadas com ações de restauro ecológico em cenários de alterações climáticas.

Geometric Hamiltonian formulation of a variational problem depending on the covariant acceleration

We consider a second-order variational problem depending on the covariant acceleration, which is related to the notion of Riemannian cubic polynomials. This problem and the corresponding optimal control problem are described in the context of higher order tangent bundles using geometric tools. The main tool, a presymplectic variant of Pontryagin’s maximum principle, allows us to study the dynamics of the control problem.