O problema da árvore de suporte de custo mínimo com restrições de peso

Nesta tese abordam-se várias formulações e diferentes métodos para resolver o Problema da Árvore de Suporte de Custo Mínimo com Restrições de Peso (WMST – Weight-constrained Minimum Spanning Tree Problem). Este problema, com aplicações no desenho de redes de comunicações e telecomunicações, é um problema de Otimização Combinatória NP-difícil. O Problema WMST consiste em determinar, numa rede com custos e pesos associados às arestas, uma árvore de suporte de custo mínimo de tal forma que o seu peso total não exceda um dado limite especificado. Apresentam-se e comparam-se várias formulações para o problema. Uma delas é usada para desenvolver um procedimento com introdução de cortes baseado em separação e que se tornou bastante útil na obtenção de soluções para o problema. Tendo como propósito fortalecer as formulações apresentadas, introduzem-se novas classes de desigualdades válidas que foram adaptadas das conhecidas desigualdades de cobertura, desigualdades de cobertura estendida e desigualdades de cobertura levantada. As novas desigualdades incorporam a informação de dois conjuntos de soluções: o conjunto das árvores de suporte e o conjunto saco-mochila. Apresentam-se diversos algoritmos heurísticos de separação que nos permitem usar as desigualdades válidas propostas de forma eficiente. Com base na decomposição Lagrangeana, apresentam-se e comparam-se algoritmos simples, mas eficientes, que podem ser usados para calcular limites inferiores e superiores para o valor ótimo do WMST. Entre eles encontram-se dois novos algoritmos: um baseado na convexidade da função Lagrangeana e outro que faz uso da inclusão de desigualdades válidas. Com o objetivo de obter soluções aproximadas para o Problema WMST usam-se métodos heurísticos para encontrar uma solução inteira admissível. Os métodos heurísticos apresentados são baseados nas estratégias Feasibility Pump e Local Branching. Apresentam-se resultados computacionais usando todos os métodos apresentados. Os resultados mostram que os diferentes métodos apresentados são bastante eficientes para encontrar soluções para o Problema WMST.

Problems of minimal aerodynamic resistance

Nesta tese estamos preocupados com o problema da resistência mínima primeiro dirigida por I. Newton em seu Principia (1687): encontrar o corpo de resistência mínima que se desloca através de um médio. As partículas do médio não interagem entre si, bem como a interação das partículas com o corpo é perfeitamente elástica. Diferentes abordagens desse modelo foram feitas por vários matemáticos nos últimos 20 anos. Aqui damos uma visão geral sobre estes resultados que representa interesse independente, uma vez que os autores diferentes usam notações diferentes. Apresentamos uma solução do problema de minimização na classe de corpos de revolução geralmente não convexos e simplesmente conexos. Acontece que nessa classe existem corpos com resistência menor do que o mínimo da resistência na classe de corpos convexos de revolução. Encontramos o infimum da resistência nesta classe e construimos uma sequência regular de corpos que aproxima este infimum. Também apresentamos um corpo de resistência nula. Até agora ninguém sabia se tais corpos existem ou não, evidentemente o nosso corpo não pertence a nenhuma classe anteriormente analisado. Este corpo é não convexo e não simplesmente conexo; a forma topológica dele é um toro, parece um UFO extraterrestre. Apresentamos aqui várias famílias de tais corpos e estudamos as suas propriedades. Também apresentamos um corpo que é natural de chamar um corpo "invisíveis em uma direção", uma vez que a trajectória de cada partícula com a certa direcção coincide com a linha recta fora do invólucro convexo do corpo. ABSTRACT: In this thesis we are concerned with the problem of minimal resistance first addressed by I. Newton in his Principia (1687): find the body of minimal resistance moving through a medium. The medium particles do not mutually interact, and the interaction of particles with the body is perfectly elastic. Different approaches to that model have been tried by several mathematicians during the last 20 years. Here we give an overview of these results that represents interest in itself since all authors use different notations. We present a solution of the minimization problem in the class of generally non convex, simply connected bodies of revolution. It happens that in this class there are bodies with smaller resistance than the minimum in the class of convex bodies of revolution. We find the infimum of the resistance in this class, and construct a sequence of bodies which approximates this infimum. Also we present a body of zero resistance. Since earlier it was unknown if such bodies exists or not, evidently our body does not belong to any class previously examined. The zero resistance body found by us is non-convex and non-simply connected; topologically it is a torus, and it looks like an extraterrestrial UFO. We present here several families of such bodies and study their properties. We also present a body which is natural to call a body "invisible in one direction", since the trajectory of each particle with the given direction, outside the convex hull of the body, coincides with a straight line.

Micropropagation in elite corck oak trees: a tool for suber production improvement?

Dada a extrema importância económica e ambiental que o montado de sobro tem em Portugal, e dado o declínio deste devido a várias razões (e.g. doença, idade das plantas) é premente desenvolver estratégias de preservação de sobreiros elite e optimizar técnicas para a propagação destes genótipos. No primeiro Capítulo expõe-se uma breve introdução sobre o montado actual e as técnicas actuais de regeneração/propagação do sobreiro. Descreve-se ainda as principais técnicas de preservação e avaliação de estabilidade genética referidas na literatura para sobreiro e outras lenhosas. No Capítulo II é apresentado um estudo de melhoramento das condições actuais de maturação de embriões somáticos de sobreiro com vista a aperfeiçoar o processo de conversão em plantas. Neste capítulo é apresentado um protocolo melhorado em relação ao actual que permite um desenvolvimento dos embriões somáticos dum modo semelhante aos embriões zigóticos em termos de substâncias de reserva. O Capítulo III mostra um estudo efectuado com o objectivo principal de avaliar estabilidade genética durante todo o processo de embriogénese somática. Neste capítulo são apresentados resultados duma análise feita por RAPD em fases distintas da embriogénese somática de sobreiro. Neste estudo mostra-se que não existem diferenças significativas entre plantas de campo, embriões somáticos e plantas regeneradas. No Capítulo VI, pretende-se complementar o estudo anterior. Neste Capítulo descreve-se a dinâmica do ciclo celular durante as primeiras fases de embriogénese somática na presença de reguladores de crescimento. Este trabalho permitiu concluir a importância dos reguladores de crescimento na indução e perceber o peso do factor genótipo durante o processo. Considerando os resultados anteriores, a necessidade de um processo eficiente de preservação de genótipos elite torna-se fundamental. No Capítulo V descreve-se um protocolo de criopreservação eficiente sem recursos a substâncias tóxicas. Nesta secção é ainda feita uma análise de variabilidade genética após criopreservação através de FCM, AFLP e SSR. Todos os resultados obtidos anteriormente são postos a prova no Capítulo VI onde se faz uma monitorização extensiva de 10 genótipos elite, tendo em conta a sua capacidade de produção de cortiça, através do processo de embriogénese somática. Durante esta secção são utilizados os protocolos desenvolvidos anteriormente e avaliados na sua eficiência. Neste capítulo é descrita a integração de vários segmentos deste estudo num só protocolo eficiente de regeneração e preservação de sobreiros através de embriogénese somática. Finalmente, no Capítulo VI são apresentadas as conclusões da presente Tese de Doutoramento, com especial incidência para linhas de investigação futuras a serem tomadas. Discute-se a importância deste novo protocolo na optimização da produção da cortiça e traçam-se possíveis aplicações alternativas.

Minimal state-space realizations of 2D convolutional codes

In this thesis we consider two-dimensional (2D) convolutional codes. As happens in the one-dimensional (1D) case one of the major issues is obtaining minimal state-space realizations for these codes. It turns out that the problem of minimal realization of codes is not equivalent to the minimal realization of encoders. This is due to the fact that the same code may admit different encoders with different McMillan degrees. Here we focus on the study of minimality of the realizations of 2D convolutional codes by means of separable Roesser models. Such models can be regarded as a series connection between two 1D systems. As a first step we provide an algorithm to obtain a minimal realization of a 1D convolutional code starting from a minimal realization of an encoder of the code. Then, we restrict our study to two particular classes of 2D convolutional codes. The first class to be considered is the one of codes which admit encoders of type n 1. For these codes, minimal encoders (i.e., encoders for which a minimal realization is also minimal as a code realization) are characterized enabling the construction of minimal code realizations starting from such encoders. The second class of codes to be considered is the one constituted by what we have called composition codes. For a subclass of these codes, we propose a method to obtain minimal realizations by means of separable Roesser models.