Given a set of n points on a plane, in the Minimum Weight Triangulation problem, we wish to find a triangulation that minimizes the sum of Euclidean lengths of its edges. The problem has been studied for more than four decades and is known to be incredibly challenging. In fact, the complexity status of this problem remained open until recently when it was shown to be NP-Hard. We present a novel polynomial-time algorithm that computes a 16-approximation of the minimum weight triangulation---a constant that is significantly smaller than what has been previously known. To construct our candidate solution, our algorithm uses grids to partition edges into levels by increasing weights, so that edges with similar weights appear in the same level. We incrementally triangulate the point set by constructing a growing partial triangulation for each level, introducing edges in increasing order of level. At each level, we use a variant of the ring heuristic followed by a greedy heuristic to add edges, finally resulting in a complete triangulation of the point set. In our analysis, we reduce the problem of comparing the weight of the candidate and the optimal solutions to a comparison between the cardinality of the two underlying graphs. We develop a new technique to compare the cardinality of planar straight-line graphs, and in combination with properties due to the imposed grid structure, we bound the approximation ratio. / Master of Science / Given a set of n points on a plane P, a triangulation of P is a set of edges such that no two edges intersect at a point not in P, and the edges subdivide the convex hull of P into triangles. Triangulations have a variety of applications, including computer graphics, finite element analysis, and interpolation, which motivates the need for efficient algorithms to compute triangulations with desirable qualities. The Minimum Weight Triangulation problem is the problem of computing the triangulation T that minimizes the sum of Euclidean lengths of its edges and performs well in many of the above-mentioned applications. The problem has been studied for more than four decades and is known to be incredibly challenging. In fact, the complexity status of this problem remained open until recently when it was shown to be NP-Hard. We present a novel polynomial-time algorithm that computes a 16-approximation of the minimum weight triangulation—a constant that is significantly smaller than what has been previously known. The algorithm makes use of grids together with a variant of the ring and greedy heuristic adapted to apply in a new setting, resulting in an elegant, efficient algorithm.

In this thesis, we introduce a new class of problems, which we call Optimal Areal Positioning (OAP), and study a special form of these problems. OAPs have important applications in earth observation satellite management, tele-robotics, multi-camera control, and surveillance. In OAP, we would like to find the optimal position of a set of floating geometric objects (targets) on a two-dimensional plane to (partially) cover another set of fixed geometric objects (requests) in order to maximize the total reward obtained from covered parts of requests. In this thesis, we consider the special form of OAP in which targets and requests are parallel axes rectangles and targets are of equal size. A predetermined reward is associated with covering an area unit of each request. Based on the number of target rectangles, we classify rectangular OAP into two categories: Single Target Problem (STP) and Multi-Target Problem (MTP). The structure of MTP can be compared to the planar p-center which is NP-complete, if p is part of the input. In fact, we conjecture that MTP is NP-complete. The existing literature does not contain any work on MTP. The research contributions of this thesis are as follows: We develop new theoretical properties for the solution of STP and devised a new solution approach for it. This approach is based on a novel branch-and-bound (BB) algorithm devised over a reduced solution space. Branching is done using a clustering scheme. Our computational results show that in many cases our approach significantly outperforms the existing Plateau Vertex Traversal and brute force algorithms, especially for problems with many requests appearing in clusters over a large region. We perform a theoretical study of MTP for the first time and prove several theoretical properties for its solution. We have introduced a reduced solution space using these properties. We present the first exact algorithm to solve MTP. This algorithm has a branch-and-bound framework. The reduced solution space calls for a novel branching strategy for MTP. The algorithm has a main branch-and-bound tree with a special structure along with two trees (one for each axis) to store the information required for branching in the main tree in an efficient format. Branching is done using a clustering scheme. We perform computational experiments to evaluate the performance of our algorithm. Our algorithm solves relatively large instances of MTP in a short time.

O presente trabalho utiliza o método Design Construtal para desenvolver o estudo numérico de uma configuração de caminhos de alta condutividade de geometria trifurcada que minimiza a resistência ao fluxo de calor, quando a área do caminho trifurcado é mantida constante. O objetivo deste trabalho é o estudo da influência da geometria sobre o desempenho térmico do sistema bem como a otimização do mesmo, assim obtendo uma configuração que minimiza a resistência térmica para cada condição imposta. São apresentadas as considerações e hipóteses utilizadas para a análise, obtendo a equação do calor regente e as condições de contorno do problema, bem como a função objetivo. Para a solução numérica da equação da condução do calor, é utilizado o software MATLAB ®, especificamente as ferramentas PDETOOL, Partial Differential Equations Tool, e GA, Algoritmo Genético. A resistência térmica é minimizada para cada grau de liberdade. A cada nível de otimização, a influência do grau de liberdade em questão é estudada, obtendo um mapeamento da importância de cada grau de liberdade sobre o sistema trifurcado. Também são obtidas as configurações ótimas para diferentes frações de área. Posteriormente, é estudado o comportamento da configuração ótima do sistema para diferentes temperaturas do final das bifurcações do sistema, mostrando que, para as temperaturas estudadas neste trabalho, a configuração ótima não se altera, apenas a resistência térmica, com a alteração na temperatura do sumidouro direito sendo mais influente sobre essa, seguida do sumidouro central e, por fim, do sumidouro esquerdo. Finalmente, este trabalho mostra, com esses resultados, que a geometria ótima é aquela que melhor distribui as imperfeições do sistema, de acordo com o princípio da ótima distribuição das imperfeições e, também, possui robustez quanto às pequenas imperfeições inseridas no sistema. / The present work employs Constructal Design method to develop a numerical study of a triforked high conductivity pathway that minimizes the heat flow resistance when the triforked pathway area is kept constant. The objective of this work is the study of the influence of the geometry over the thermal performance of the system as well as the optimization of the latter, thus obtaining a configuration that minimizes the thermal resistance for each imposed condition. The considerations and hypothesis for the analysis are shown, obtaining a reigning heat equation and boundary conditions for the system, as well as the objetctive function (minimization of the maximum temperature). For the numerical solution of the heat conduction equation, it is utilized MATLAB ® software, specifically the PDETOOL, Partial Differential Equations Tool, and GA, Genetic Algorithm, toolboxes. The thermal resistance is minimized for every degree of freedom. In each level of optimization, the influence of the degree of freedom in question is studied, obtaining a mapping of the importance of each degree of freedom over the performance of the triforked pathway. Optimal configurations are also obtained for different area fractions. Posteriorly, the behavior of the optimal geometry is studied for different temperatures of the branches of the system. Results show that, for the temperatures studied in this work, the optimal configuration does not change, only the thermal resistance, with the increase of temperature of the right sink being more influential over it, followed by the temperature of the middle sink and, at last, the temperature of the left sink. Finally, this work shows, with these results, that the optimal geometry is the one that better distributes the imperfections of the systems, which is in accordance to the principle of the optimal distribution of imperfections, while possessing a certain robustness over small imperfections inserted in the system.

O presente trabalho utiliza o método Design Construtal para desenvolver o estudo numérico de uma configuração de caminhos de alta condutividade de geometria trifurcada que minimiza a resistência ao fluxo de calor, quando a área do caminho trifurcado é mantida constante. O objetivo deste trabalho é o estudo da influência da geometria sobre o desempenho térmico do sistema bem como a otimização do mesmo, assim obtendo uma configuração que minimiza a resistência térmica para cada condição imposta. São apresentadas as considerações e hipóteses utilizadas para a análise, obtendo a equação do calor regente e as condições de contorno do problema, bem como a função objetivo. Para a solução numérica da equação da condução do calor, é utilizado o software MATLAB ®, especificamente as ferramentas PDETOOL, Partial Differential Equations Tool, e GA, Algoritmo Genético. A resistência térmica é minimizada para cada grau de liberdade. A cada nível de otimização, a influência do grau de liberdade em questão é estudada, obtendo um mapeamento da importância de cada grau de liberdade sobre o sistema trifurcado. Também são obtidas as configurações ótimas para diferentes frações de área. Posteriormente, é estudado o comportamento da configuração ótima do sistema para diferentes temperaturas do final das bifurcações do sistema, mostrando que, para as temperaturas estudadas neste trabalho, a configuração ótima não se altera, apenas a resistência térmica, com a alteração na temperatura do sumidouro direito sendo mais influente sobre essa, seguida do sumidouro central e, por fim, do sumidouro esquerdo. Finalmente, este trabalho mostra, com esses resultados, que a geometria ótima é aquela que melhor distribui as imperfeições do sistema, de acordo com o princípio da ótima distribuição das imperfeições e, também, possui robustez quanto às pequenas imperfeições inseridas no sistema. / The present work employs Constructal Design method to develop a numerical study of a triforked high conductivity pathway that minimizes the heat flow resistance when the triforked pathway area is kept constant. The objective of this work is the study of the influence of the geometry over the thermal performance of the system as well as the optimization of the latter, thus obtaining a configuration that minimizes the thermal resistance for each imposed condition. The considerations and hypothesis for the analysis are shown, obtaining a reigning heat equation and boundary conditions for the system, as well as the objetctive function (minimization of the maximum temperature). For the numerical solution of the heat conduction equation, it is utilized MATLAB ® software, specifically the PDETOOL, Partial Differential Equations Tool, and GA, Genetic Algorithm, toolboxes. The thermal resistance is minimized for every degree of freedom. In each level of optimization, the influence of the degree of freedom in question is studied, obtaining a mapping of the importance of each degree of freedom over the performance of the triforked pathway. Optimal configurations are also obtained for different area fractions. Posteriorly, the behavior of the optimal geometry is studied for different temperatures of the branches of the system. Results show that, for the temperatures studied in this work, the optimal configuration does not change, only the thermal resistance, with the increase of temperature of the right sink being more influential over it, followed by the temperature of the middle sink and, at last, the temperature of the left sink. Finally, this work shows, with these results, that the optimal geometry is the one that better distributes the imperfections of the systems, which is in accordance to the principle of the optimal distribution of imperfections, while possessing a certain robustness over small imperfections inserted in the system.

O presente trabalho utiliza o método Design Construtal para desenvolver o estudo numérico de uma configuração de caminhos de alta condutividade de geometria trifurcada que minimiza a resistência ao fluxo de calor, quando a área do caminho trifurcado é mantida constante. O objetivo deste trabalho é o estudo da influência da geometria sobre o desempenho térmico do sistema bem como a otimização do mesmo, assim obtendo uma configuração que minimiza a resistência térmica para cada condição imposta. São apresentadas as considerações e hipóteses utilizadas para a análise, obtendo a equação do calor regente e as condições de contorno do problema, bem como a função objetivo. Para a solução numérica da equação da condução do calor, é utilizado o software MATLAB ®, especificamente as ferramentas PDETOOL, Partial Differential Equations Tool, e GA, Algoritmo Genético. A resistência térmica é minimizada para cada grau de liberdade. A cada nível de otimização, a influência do grau de liberdade em questão é estudada, obtendo um mapeamento da importância de cada grau de liberdade sobre o sistema trifurcado. Também são obtidas as configurações ótimas para diferentes frações de área. Posteriormente, é estudado o comportamento da configuração ótima do sistema para diferentes temperaturas do final das bifurcações do sistema, mostrando que, para as temperaturas estudadas neste trabalho, a configuração ótima não se altera, apenas a resistência térmica, com a alteração na temperatura do sumidouro direito sendo mais influente sobre essa, seguida do sumidouro central e, por fim, do sumidouro esquerdo. Finalmente, este trabalho mostra, com esses resultados, que a geometria ótima é aquela que melhor distribui as imperfeições do sistema, de acordo com o princípio da ótima distribuição das imperfeições e, também, possui robustez quanto às pequenas imperfeições inseridas no sistema. / The present work employs Constructal Design method to develop a numerical study of a triforked high conductivity pathway that minimizes the heat flow resistance when the triforked pathway area is kept constant. The objective of this work is the study of the influence of the geometry over the thermal performance of the system as well as the optimization of the latter, thus obtaining a configuration that minimizes the thermal resistance for each imposed condition. The considerations and hypothesis for the analysis are shown, obtaining a reigning heat equation and boundary conditions for the system, as well as the objetctive function (minimization of the maximum temperature). For the numerical solution of the heat conduction equation, it is utilized MATLAB ® software, specifically the PDETOOL, Partial Differential Equations Tool, and GA, Genetic Algorithm, toolboxes. The thermal resistance is minimized for every degree of freedom. In each level of optimization, the influence of the degree of freedom in question is studied, obtaining a mapping of the importance of each degree of freedom over the performance of the triforked pathway. Optimal configurations are also obtained for different area fractions. Posteriorly, the behavior of the optimal geometry is studied for different temperatures of the branches of the system. Results show that, for the temperatures studied in this work, the optimal configuration does not change, only the thermal resistance, with the increase of temperature of the right sink being more influential over it, followed by the temperature of the middle sink and, at last, the temperature of the left sink. Finally, this work shows, with these results, that the optimal geometry is the one that better distributes the imperfections of the systems, which is in accordance to the principle of the optimal distribution of imperfections, while possessing a certain robustness over small imperfections inserted in the system.

A presente dissertação desenvolve um estudo numérico em duas direções espaciais com o objetivo de encontrar a configuração de geometrias acopladas a aletas de alta condutividade térmica em forma de “T” que resultam na menor resistência ao fluxo de calor utilizando o método Design Construtal. Como restrição as áreas de ambos os componentes, o corpo sólido onde há geração de calor e a aleta, são mantidas constantes. A equação diferencial da difusão do calor bidimensional, em regime permanente e propriedades constantes, com as condições de contorno, foram solucionadas pelo método dos elementos finitos utilizando o programa MATLAB ®, mais precisamente a ferramenta PDETOOL, Partial Differential Equations Tool. Em outras palavras, minimizar a resistência térmica ao fluxo de calor gerado para uma melhora na refrigeração, variando somente os comprimentos e larguras que formam o sólido de baixa condutividade térmica e a aleta composta por material de alta condutividade térmica. Para cada geometria proposta foram avaliadas todas as possibilidades geométricas dentro do domínio estabelecido Três geometrias foram propostas para os sólidos geradores de calor: retangular, trapezoidal e semicircular, todas acopladas com a aleta na forma de T. Além dos graus de liberdade, também foram avaliados o efeito dos seguintes parâmetros adimensionais: (condutividade térmica da aleta), (fração de área), (fração de área auxiliar) e ℎ . O melhor design encontrado é aquele que distribui melhor as imperfeições, ou seja, a geometria que distribui melhor os pontos de temperatura máxima. Os resultados reforçam, ainda, o entendimento de que sistemas multicomponentes devem ser estudados globalmente e não cada componente individualmente. Para a geometria retangular houve uma melhora de 66% no desempenho quando comparados os desempenhos da primeira para a última otimização. O melhor desempenho obtido para a geometria trapezoidal superou em aproximadamente 3,5% o desempenho da geometria retangular. Por fim a geometria semicircular atingiu o melhor desempenho entre as geometrias estudadas, superando em 40% o resultado atingido pela geometria trapezoidal. / This work used the method Construtal Design to develop a numerical study trying to find out the best configuration of geometries coupled to T-shaped materials of high thermal conductivity to improve the heat transfer between the heat generating body, which is a low heat conductor, and the environment. As a restriction, both areas are kept constant. The differential equations of heat diffusion, steady state and constant properties, and their boundary conditions were solved numerically using the MATLAB ® software, specifically the PDETOOL tool. The objective of this work is to improve the flux of heat through the Tshaped materials of high thermal conductivity, in other words, minimize the thermal resistance to improve the refrigeration, changing only the values of the lengths and widths that setup the solid of low thermal conductivity and the T-shaped materials of high thermal conductivity. All geometric possibilities were evaluated, respecting the domain. The optimal geometry was that which resulted in lower thermal resistance. Three geometries have been proposed for solid heat generators: rectangular, trapezoidal and semicircular. All coupled with the T-shaped materials of high thermal conductivity Besides the degrees of freedom were also evaluated the effect of the following dimensionless parameters: (thermal conductivity), (area fraction), (auxiliary area fraction) and ℎ . The best design found is that better distributes the imperfections, in other words, it is the geometry that better distributes the points of maximum temperature. The results reinforce also the understanding that multicomponent systems should be studied globally rather than each component individually. For the rectangular geometry there was an improvement of 66% in performance when comparing the performances of the first to the last optimization. The best performance obtained for the trapezoidal geometry exceeded by approximately 3.5% performance of the rectangular geometry. Finally the semicircular geometry achieved the best performance among the studied geometry, exceeding by 40% the result achieved by the trapezoidal geometry.

A presente dissertação desenvolve um estudo numérico em duas direções espaciais com o objetivo de encontrar a configuração de geometrias acopladas a aletas de alta condutividade térmica em forma de “T” que resultam na menor resistência ao fluxo de calor utilizando o método Design Construtal. Como restrição as áreas de ambos os componentes, o corpo sólido onde há geração de calor e a aleta, são mantidas constantes. A equação diferencial da difusão do calor bidimensional, em regime permanente e propriedades constantes, com as condições de contorno, foram solucionadas pelo método dos elementos finitos utilizando o programa MATLAB ®, mais precisamente a ferramenta PDETOOL, Partial Differential Equations Tool. Em outras palavras, minimizar a resistência térmica ao fluxo de calor gerado para uma melhora na refrigeração, variando somente os comprimentos e larguras que formam o sólido de baixa condutividade térmica e a aleta composta por material de alta condutividade térmica. Para cada geometria proposta foram avaliadas todas as possibilidades geométricas dentro do domínio estabelecido Três geometrias foram propostas para os sólidos geradores de calor: retangular, trapezoidal e semicircular, todas acopladas com a aleta na forma de T. Além dos graus de liberdade, também foram avaliados o efeito dos seguintes parâmetros adimensionais: (condutividade térmica da aleta), (fração de área), (fração de área auxiliar) e ℎ . O melhor design encontrado é aquele que distribui melhor as imperfeições, ou seja, a geometria que distribui melhor os pontos de temperatura máxima. Os resultados reforçam, ainda, o entendimento de que sistemas multicomponentes devem ser estudados globalmente e não cada componente individualmente. Para a geometria retangular houve uma melhora de 66% no desempenho quando comparados os desempenhos da primeira para a última otimização. O melhor desempenho obtido para a geometria trapezoidal superou em aproximadamente 3,5% o desempenho da geometria retangular. Por fim a geometria semicircular atingiu o melhor desempenho entre as geometrias estudadas, superando em 40% o resultado atingido pela geometria trapezoidal. / This work used the method Construtal Design to develop a numerical study trying to find out the best configuration of geometries coupled to T-shaped materials of high thermal conductivity to improve the heat transfer between the heat generating body, which is a low heat conductor, and the environment. As a restriction, both areas are kept constant. The differential equations of heat diffusion, steady state and constant properties, and their boundary conditions were solved numerically using the MATLAB ® software, specifically the PDETOOL tool. The objective of this work is to improve the flux of heat through the Tshaped materials of high thermal conductivity, in other words, minimize the thermal resistance to improve the refrigeration, changing only the values of the lengths and widths that setup the solid of low thermal conductivity and the T-shaped materials of high thermal conductivity. All geometric possibilities were evaluated, respecting the domain. The optimal geometry was that which resulted in lower thermal resistance. Three geometries have been proposed for solid heat generators: rectangular, trapezoidal and semicircular. All coupled with the T-shaped materials of high thermal conductivity Besides the degrees of freedom were also evaluated the effect of the following dimensionless parameters: (thermal conductivity), (area fraction), (auxiliary area fraction) and ℎ . The best design found is that better distributes the imperfections, in other words, it is the geometry that better distributes the points of maximum temperature. The results reinforce also the understanding that multicomponent systems should be studied globally rather than each component individually. For the rectangular geometry there was an improvement of 66% in performance when comparing the performances of the first to the last optimization. The best performance obtained for the trapezoidal geometry exceeded by approximately 3.5% performance of the rectangular geometry. Finally the semicircular geometry achieved the best performance among the studied geometry, exceeding by 40% the result achieved by the trapezoidal geometry.

A presente dissertação desenvolve um estudo numérico em duas direções espaciais com o objetivo de encontrar a configuração de geometrias acopladas a aletas de alta condutividade térmica em forma de “T” que resultam na menor resistência ao fluxo de calor utilizando o método Design Construtal. Como restrição as áreas de ambos os componentes, o corpo sólido onde há geração de calor e a aleta, são mantidas constantes. A equação diferencial da difusão do calor bidimensional, em regime permanente e propriedades constantes, com as condições de contorno, foram solucionadas pelo método dos elementos finitos utilizando o programa MATLAB ®, mais precisamente a ferramenta PDETOOL, Partial Differential Equations Tool. Em outras palavras, minimizar a resistência térmica ao fluxo de calor gerado para uma melhora na refrigeração, variando somente os comprimentos e larguras que formam o sólido de baixa condutividade térmica e a aleta composta por material de alta condutividade térmica. Para cada geometria proposta foram avaliadas todas as possibilidades geométricas dentro do domínio estabelecido Três geometrias foram propostas para os sólidos geradores de calor: retangular, trapezoidal e semicircular, todas acopladas com a aleta na forma de T. Além dos graus de liberdade, também foram avaliados o efeito dos seguintes parâmetros adimensionais: (condutividade térmica da aleta), (fração de área), (fração de área auxiliar) e ℎ . O melhor design encontrado é aquele que distribui melhor as imperfeições, ou seja, a geometria que distribui melhor os pontos de temperatura máxima. Os resultados reforçam, ainda, o entendimento de que sistemas multicomponentes devem ser estudados globalmente e não cada componente individualmente. Para a geometria retangular houve uma melhora de 66% no desempenho quando comparados os desempenhos da primeira para a última otimização. O melhor desempenho obtido para a geometria trapezoidal superou em aproximadamente 3,5% o desempenho da geometria retangular. Por fim a geometria semicircular atingiu o melhor desempenho entre as geometrias estudadas, superando em 40% o resultado atingido pela geometria trapezoidal. / This work used the method Construtal Design to develop a numerical study trying to find out the best configuration of geometries coupled to T-shaped materials of high thermal conductivity to improve the heat transfer between the heat generating body, which is a low heat conductor, and the environment. As a restriction, both areas are kept constant. The differential equations of heat diffusion, steady state and constant properties, and their boundary conditions were solved numerically using the MATLAB ® software, specifically the PDETOOL tool. The objective of this work is to improve the flux of heat through the Tshaped materials of high thermal conductivity, in other words, minimize the thermal resistance to improve the refrigeration, changing only the values of the lengths and widths that setup the solid of low thermal conductivity and the T-shaped materials of high thermal conductivity. All geometric possibilities were evaluated, respecting the domain. The optimal geometry was that which resulted in lower thermal resistance. Three geometries have been proposed for solid heat generators: rectangular, trapezoidal and semicircular. All coupled with the T-shaped materials of high thermal conductivity Besides the degrees of freedom were also evaluated the effect of the following dimensionless parameters: (thermal conductivity), (area fraction), (auxiliary area fraction) and ℎ . The best design found is that better distributes the imperfections, in other words, it is the geometry that better distributes the points of maximum temperature. The results reinforce also the understanding that multicomponent systems should be studied globally rather than each component individually. For the rectangular geometry there was an improvement of 66% in performance when comparing the performances of the first to the last optimization. The best performance obtained for the trapezoidal geometry exceeded by approximately 3.5% performance of the rectangular geometry. Finally the semicircular geometry achieved the best performance among the studied geometry, exceeding by 40% the result achieved by the trapezoidal geometry.

Submitted by Raquel Vergara Gondran (raquelvergara38@yahoo.com.br) on 2016-04-11T17:52:57Z No. of bitstreams: 1 tese_daniele.pdf: 1693586 bytes, checksum: a89420a4bb70aea354ae5524f20ac563 (MD5) / Approved for entry into archive by cleuza maria medina dos santos (cleuzamai@yahoo.com.br) on 2016-05-04T20:39:58Z (GMT) No. of bitstreams: 1 tese_daniele.pdf: 1693586 bytes, checksum: a89420a4bb70aea354ae5524f20ac563 (MD5) / Made available in DSpace on 2016-05-04T20:39:58Z (GMT). No. of bitstreams: 1 tese_daniele.pdf: 1693586 bytes, checksum: a89420a4bb70aea354ae5524f20ac563 (MD5) Previous issue date: 2009 / Ao contrário dos bioprocessos submersos, que são amplamente utilizados e estudados, bioprocessos em estado sólido (BES) ainda são carentes de estudos de modelagem e simulação, o que aponta para o grande potencial de otimização. A dificuldade no aperfeiçoamento de BES está associada a problemas com a dissipação do calor gerado pelas atividades metabólicas do microrganismo durante o crescimento. Esta dificuldade na transferência de calor dentro do biorreator pode levar a zonas de altas temperaturas, que afetam adversamente a produtividade. A modelagem matemática é uma ferramenta essencial para otimizar bioprocessos. Através de modelos matemáticos é possível otimizar as variáveis operacionais para controle do bioprocesso e também analisar o design do biorreator. A otimização geométrica, de acordo com a Teoria Constructal, visa melhorar o desempenho do biorreator através, por exemplo, de minimizar a temperatura no interior do leito a níveis ótimos para o cultivo. O presente trabalho apresenta projetos de biorreatores para BES, todos com geometria otimizada, obtidos a partir de experimentação numérica, através de um software de computational fluid dynamics (CFD). O modelo matemático utilizado era preditivo e significativo ao nível de confiança de 95%. A otimização geométrica foi apresentada em função das condições operacionais do cultivo. Para o biorreator de coluna e leito fixo com paredes isoladas, foram apresentadas as geometrias ótimas em função da velocidade, da vazão e da temperatura do ar de admissão. Para uma temperatura do ar de admissão de 29,5 ºC, as configurações ótimas ((D/L)opt) variaram entre 1,0 e 2,4 para uma faixa de velocidade de admissão do ar entre 0,003 e 0,006 m s-1 . Relacionando com vazão, as razões mostraram-se ótimas entre 2,2 ≤ (D/L) ≤ 2,6 quando operando sob 3,3 a 3,5 10-5 m3 s-1 . Outro biorreator estudado foi o biorreator modular, composto de módulos elementares com geometria otimizada, sendo adaptável a diferentes escalas de produção e de fácil montagem. As configurações ótimas dos módulos de geometria retangular e seção quadrada foram apresentadas para diferentes volumes de módulos, em função da temperatura e da velocidade do ar de admissão. Foi observado que o volume máximo do módulo sem resfriamento externo é 5 L, para uma velocidade do ar de admissão acima de 0,0045 m s-1 e temperatura inferior ou igual 29,0 ºC O último biorreator proposto foi o biorreator hollow, semelhante a um biorreator de coluna e leito fixo, porém com um duto oco inserido nele. O duto interno tem inúmeros furos perpendiculares às suas paredes, mas sua saída é isolada, permitindo que o ar penetre no meio poroso. A geometria otimizada do biorreator hollow foi apresentada em função da fração de volume do duto interno, da razão entre os diâmetros de entrada e saída do duto interno, da vazão e da temperatura do ar de admissão. Em comparação com o biorreator de coluna convencional de mesmas dimensões e sob mesmas condições operacionais, o biorreator hollow apresentou temperatura máxima mais baixa, demonstrando que o projeto é eficiente para resfriar o meio poroso. Concluiu-se, enfim, no presente trabalho, que a geometria é um parâmetro importante e a sua otimização pode beneficiar o desempenho do biorreator. / Unlike the submerged bioprocesses, that was wildly used and studied, solid state bioprocess (SSB) are still poorly studied with respect to modeling and simulation, what indicates a big potential for optimization. The difficulty in the BES improvement is associated to problems with the dissipation of heat generated by metabolic activities of microorganisms during growth. This difficulty in transferring heat from the bioreactor could lead to areas with high temperature, which usually affect the productivity adversely. The mathematical modeling is an essential tool for optimizing bioprocesses. Using mathematical models it is possible to optimize operational variables to control the bioprocess and also explore the design of the bioreactor. The geometric optimization, according Constructal Theory, aims to improve the performance of the bioreactor through, for example, minimizing the temperature inside the bed to optimum levels for the bioprocess. The present work presents designs of bioreactors to SSB, all with optimized geometry, obtained from numerical experiments, by computational fluid dynamics (CFD) software. The mathematical model used has been predictive and significant at .95 level of confidence. The geometric optimization was presented as function of operational conditions of the cultivation. For the column fixed bed bioreactor with isolated wall, the optimal configurations are shown as function of flow, velocity and temperature of inlet air. For a inlet air temperature of 29.5 ºC, the optimal configurations ((D/L)opt) varied between 1.0 e 2.4 to a range of inlet velocity between 0.003 e 0.006 m s-1 . Relating with the volumetric flow, the optimal ratios presented between 2.2 ≤ (D/L) ≤ 2.6 when operating under 3.3 a 3.5 10-5 m3 s-1 . Other studied bioreactor was the modular bioreactor, consisting of elementary modules with optimized geometry, being adaptable to different scales of production and easy assembly. The optimal configurations of the modules with rectangular geometry and square section were shown depending on the volume of modules and the temperature and velocity of inlet air. It was observed that the maximum volume of the module without external cooling was 5 L, for a inlet velocity upper 0.0045 m s-1 and temperature smaller or equal to 29.0 ºC. The last proposed bioreactor was the hollow bioreactor, similar to a column fixed bed bioreactor, but with an empty duct inserted on it. The internal duct has innumerable holes perpendicular to its wall (the inlet port), but its end is insulated, allowing the air penetrates into the porous medium. The optimized geometry of hollow bioreactor was presented in function of the volume fraction of internal duct, the ratio between the diameters of inlet and outlet of the internal duct, the flow rate and temperature of the inlet air. Comparing with the conventional column bioreactor with the same configuration and same operational conditions, the hollow bioreactor showed a lower maximum temperature. This demonstrates that the project is efficient at cooling the porous medium. Finally, it was concluded that the geometry is an important parameter and its optimization can benefit the performance of the bioreactor.

This thesis addresses the multi-body assembly (MBA) problem in the context of protein assemblies. [...] In this thesis, we chose the protein assembly domain because accurate and reliable computational modeling, simulation and prediction of such assemblies would clearly accelerate discoveries in understanding of the complexities of metabolic pathways, identifying the molecular basis for normal health and diseases, and in the designing of new drugs and other therapeutics. [...] [We developed] F²Dock (Fast Fourier Docking) which includes a multi-term function which includes both a statistical thermodynamic approximation of molecular free energy as well as several of knowledge-based terms. Parameters of the scoring model were learned based on a large set of positive/negative examples, and when tested on 176 protein complexes of various types, showed excellent accuracy in ranking correct configurations higher (F² Dock ranks the correcti solution as the top ranked one in 22/176 cases, which is better than other unsupervised prediction software on the same benchmark). Most of the protein-protein interaction scoring terms can be expressed as integrals over the occupied volume, boundary, or a set of discrete points (atom locations), of distance dependent decaying kernels. We developed a dynamic adaptive grid (DAG) data structure which computes smooth surface and volumetric representations of a protein complex in O(m log m) time, where m is the number of atoms assuming that the smallest feature size h is [theta](r[subscript max]) where r[subscript max] is the radius of the largest atom; updates in O(log m) time; and uses O(m)memory. We also developed the dynamic packing grids (DPG) data structure which supports quasi-constant time updates (O(log w)) and spherical neighborhood queries (O(log log w)), where w is the word-size in the RAM. DPG and DAG together results in O(k) time approximation of scoring terms where k << m is the size of the contact region between proteins. [...] [W]e consider the symmetric spherical shell assembly case, where multiple copies of identical proteins tile the surface of a sphere. Though this is a restricted subclass of MBA, it is an important one since it would accelerate development of drugs and antibodies to prevent viruses from forming capsids, which have such spherical symmetry in nature. We proved that it is possible to characterize the space of possible symmetric spherical layouts using a small number of representative local arrangements (called tiles), and their global configurations (tiling). We further show that the tilings, and the mapping of proteins to tilings on arbitrary sized shells is parameterized by 3 discrete parameters and 6 continuous degrees of freedom; and the 3 discrete DOF can be restricted to a constant number of cases if the size of the shell is known (in terms of the number of protein n). We also consider the case where a coarse model of the whole complex of proteins are available. We show that even when such coarse models do not show atomic positions, they can be sufficient to identify a general location for each protein and its neighbors, and thereby restricts the configurational space. We developed an iterative refinement search protocol that leverages such multi-resolution structural data to predict accurate high resolution model of protein complexes, and successfully applied the protocol to model gp120, a protein on the spike of HIV and currently the most feasible target for anti-HIV drug design. / text