Manufatura Aditiva, também conhecida por Impressão 3D, é um processo baseado na sobreposição de camadas para produzir um objeto físico. Os dados para a produção desse objeto vêm de um modelo geométrico tridimensional, geralmente representado por uma malha de triângulos. Um dos principais procedimentos no processo de produção é fatiar a malha triangular e gerar uma série de contornos, os quais representam as camadas do objeto. Há diversas estratégicas para fatiar malhas triangulares, porém, a maior parte dos trabalhos na literatura foca-se em problemas como a qualidade do modelo, melhorias específicas no processo de fatiamento e uso de memória; poucos trabalhos, no entanto, abordam o problema por uma perspectiva de complexidade algorítmica. Algoritmos propostos atualmente para este problema executam em tempo O(n² + k²) ou O(n² + nlognk); o algoritmo proposto nesta dissertação possui complexidade O(nk) para uma entrada com n triângulos e k planos e, com K é o número médio de planos que cortam cada triângulo nesta entrada específica. O algoritmo proposto, chamado de Fatiamento por Estocada (FE) é comparado teórica e experimentalmente com alguns dos métodos conhecidos na literatura e os resultados mostram melhora considerável em tempo de execução. / Additive Manufacturing, also known as 3D printing, is a process based on the addition of sucessive layers in order to build a physical object. The data for building this object come from geometric 3D model, usually represented by a triangle mesh. One of the main procedures in this process is to slice the triangle mesh and output a sequence of contours, representing each one of the layers of the object. There are many strategies for slicing meshes, however, most of the current literature is concerned with ad hoc issues such as the quality of the model, specific improvements in the slicing process and memory usage, whereas few of them address the problem from an algorithmic complecity perspective. While current algorithms for this problem ruin in O(n² + k²) or O(n² + nlognk), the proposed algorithm runs in O(nk), for a given input with n triangles, k planes and where k is the average number of slices cutting each triangle in this specific input. This is asymptotically the best that can be achieved under certain fairly common assumptions. The proposed algorithm, called here Slicing by Stabbing (SS), was compared both theoretically and experimentally against known methods in the literature and the results show considerable improvement in execution time.

A Inteligência de Enxame (Swarm Intelligence) é uma área de estudos que busca soluções para problemas de otimização utilizando-se de técnicas computacionais inspiradas no comportamento social emergente encontrado na biologia. A metaheurística Particle Swarm Optimization (PSO) é relativamente nova e foi inspirada no comportamento social de bandos de pássaros. PSO tem apresentado bons resultados em alguns trabalhos recentes de otimização discreta, apesar de ter sido concebido originalmente para a otimização de problemas contínuos. Este trabalho trata o Problema de Atribuição de Tarefas - Task Assignment Problem (TAP), e apresenta uma aplicação: o problema de alocação de táxis e clientes, cujo objetivo da otimização está em minimizar a distância percorrida pela frota. Primeiramente, o problema é resolvido em um cenário estático, com duas versões do PSO discreto: a primeira abordagem é baseada em codificação binária e a segunda utiliza permutações para codificar as soluções. Os resultados obtidos mostram que a segunda abordagem é superior à primeira em termos de qualidade das soluções e tempo computacional, e é capaz de encontrar as soluções ótimas para o problema nas instâncias para as quais os valores ótimos são conhecidos. A partir disto, o algoritmo é adaptado para a otimização do problema em um ambiente dinâmico, com a aplicação de diferentes estratégias de resposta às mudanças. Os novos resultados mostram que a combinação de algumas abordagens habilita o algoritmo PSO a obter boas soluções ao longo da ocorrência de mudanças nas variáveis de decisão problema, em todas as instâncias testadas, com diferentes tamanhos e escalas de mudança. / Swarm Intelligence searches for solutions to optimization problems using computational techniques inspired in the emerging social behavior found in biology. The metaheuristic Particle Swarm Optimization (PSO) is relatively new and can be considered a metaphor of bird flocks. PSO has shown good results in some recent works of discrete optimization, despite it has been originally designed for continuous optimization problems. This paper deals with the Task Assignment Problem (TAP), and presents an application: the optimization problem of allocation of taxis and customers, whose goal is to minimize the distance traveled by the fleet. The problem is solved in a static scenario with two versions of the discrete PSO: the first approach that is based on a binary codification and the second one which uses permutations to encode the solution. The obtained results show that the second approach is superior than the first one in terms of quality of the solutions and computational time, and it is capable of achieving the known optimal values in the tested instances of the problem. From this, the algorithm is adapted for the optimization of the problem in a dynamic environment, with the application of different strategies to respond to changes. The new results show that some combination of approaches enables the PSO algorithm to achieve good solutions along the occurrence of changes in decision variables problem, in all instances tested, with different sizes and scales of change.

Neste trabalho estudamos os homomorfismos entre anéis de polinômios do ponto de vista da teoria de bases de Groebner. Em particular, determinamos o núcleo de um tal homomorfismo e desenvolvemos um método para determinar quando este é sobrejetivo. Estes resultados são então generalizados para anéis quocientes. O estudo de tais homomorfismos nos permite determinar os polinômos minimais de elementos em extensões de corpos, bem como encontrar soluções para um problema de programação inteira. / In this work we study the homomorphisms between polynomial rings as an application of the Groebner basis theory. In particular, we determine generators for the kemel of such a homomorphism and we give a method to determine whether it is onto. We then generalize these results to the case of quocient rings. The study of these homomorphisms allows us to determine mini mal polynomials of elements in field extensions, as well as to find solutions to an integer programming problem.

No presente trabalho estudam-se diferentes técnicas explícitas, em diferenças finitas, no emprego de algoritmos do tipo velocidade-pressão para simulação de escoamentos incompressíveis. O método de resolução da pressão de maneira direta e explícita, introduzido por Bravo e Claeyssen [BRA 97a], é analisado. Faz-se uma aproximação para o erro causado por esta técnica, e verifica-se como isto afeta a equação da continuidade. As simulações são realizadas na cavidade quadrada, comparando-se os diferentes métodos e validando as aproximações realizadas no estudo do método de resolução da pressão. Além disso, simula-se o escoamento em cavidades profundas e rasas, observandose a formação de vórtices e distribuição de energia cinética. Simulações do escoamento na cavidade cúbica também são apresentadas. / In this work different explicit technics in finite defferences in the application of velocity-pressure algorithm to simulate incompressible flows have been studied. The direct and explicit method of pressure resolution, introduced by Bravo anel Claeyssen [BRA 97a] is analyzed. An approximation to the error caused by this method is made, anel how this affects the continuity equation is verified. The simulations are maele in a square cavity, comparing the differents methoels anel valielating the approximations maele in the study of the pressure resolution method. Besieles this, flow in eleep and shallow cavities is simulateel, observing the formation of vortices and kinetic energy distribution. Simulations of the flow in the cubical cavity are also considered.

As abundâncias e identidades das espécies de qualquer comunidade biológica mudam tanto ao longo do espaço quanto do tempo. Não obstante, aspectos espaciais da biodiversidade têm sido muito mais explorados do que os temporais. Um dos motivos pelos quais padrões temporais têm recebido menos atenção é a escassez de estudos de longo prazo, especialmente na região neotropical, uma das mais biodiversas e ameaçadas do planeta. Estudar a dinâmica de populações e comunidades ao longo do tempo pode revelar processos ecológicos fundamentais, bem como descrever como pressões naturais e humanas afetam a biodiversidade. Entender a dinâmica das populações e comunidades envolve entender as histórias de vida dos organismos, como eles interagem com o ambiente, o papel de interações entre espécies, o papel de processos demográficos estocásticos, dentre outros fatores. Nesta tese investigamos a dinâmica temporal de populações e comunidades de borboletas e aves, e ao longo dos capítulos avaliamos o papel de diferentes processos na regulação dessas dinâmicas. No Capítulo 1 investigamos se um comportamento sazonal observado em borboletas Ithomiini (Nymphalidae, Danainae), supostamente adaptativo à seca - os \"bolsões de Ithomiini\"- seria uma simples resposta reativa à falta de chuvas ou se mecanismos endógenos (\"relógios biológicos\") estariam envolvidos. No Capítulo 2 realizamos um estudo de dinâmica populacional comparada de borboletas miméticas da tribo Ithomiini. Algumas evidências têm sugerido que além de convergir na morfologia, espécies co-miméticas tenderiam a convergir também no comportamento, no uso de microhabitats e possivelmente em suas dinâmicas populacionais. Testamos as hipóteses de que 1) pares de espécies co-miméticas (i.e., com a morfologia convergente) ou 2) pares de espécies mais próximas filogeneticamente teriam suas dinâmicas populacionais mais correlacionadas do que pares de espécies agrupados ao acaso. No Capítulo 3 descrevemos como a composição de espécies de assembleias de aves e borboletas de nove localidades tropicais e subtropicais na América do Sul e do Norte variou ao longo do tempo (anos a décadas), e se diferenças demográficas entre espécies (nicho) seriam importantes para explicar os padrões observados. No Capítulo 1 encontramos evidências de que a agregações seriam um comportamento endógeno sincronizado com o fotoperíodo, com plasticidade limitada para lidar com as alterações no regime de chuvas previstas para a região e para o continente. No Capítulo 2 encontramos que as dinâmicas populacionais de pares de espécies de Ithomiini de um mesmo anel mimético ou mais próximas filogeneticamente não tenderam a ser mais correlacionadas do que pares reunidos ao acaso, e que as espécies, anéis miméticos e subtribos estudadas tiveram suas dinâmicas temporais mais correlacionados do que seria esperado por acaso. Estes resultados e os do Capítulo 1 sugerem que na dinâmica desse sistema as pressões seletivas exercidas por fatores ambientais seriam mais importantes do que interações entre espécies. No Capítulo 3 mostramos que a composição de espécies de assembleias de aves na Amazônia, Cerrado, Mata Atlântica e Flórida se alterou ao longo dos anos, mesmo em assembleias de áreas bem preservadas. Sobreposta a essa rotatividade (turnover) interanual também encontramos rotatividade sazonal, previsível, na composição de espécies de assembleias de aves da Amazônia e da Mata Atlântica e na assembleia de borboletas Ithomiini. Padrões de rotatividade sazonal na composição de espécies podem ser mais comuns em comunidades neotropicais do que se imagina. As estratégias temporais dos organismos neotropicais, as quais parecem ser a base dos padrões sazonais observados nas comunidades, podem ser largamente determinadas por ritmos (\"relógios\") endógenos. Estudos sobre a regulação dos ritmos e estratégias temporais dos organismos, e dos efeitos das mudanças climáticas e do uso do solo sobre eles, são essenciais. Um importante passo nesse sentido é a disseminação de estudos de longo-prazo de populações e comunidades, contínuos, sistemáticos e com resolução para detectar padrões sazonais. Além disso, a interação das perspectivas, bases teóricas e abordagens da biologia molecular, fisiologia, cronobiologia e ecologia pode avançar nosso entendimento sobre os processos que moldam a dinâmica da biodiversidade e sobre as consequências das perturbações humanas sobre os ecossistemas / The species abundances and identities of any biological community change both over space and time. Nevertheless, Spatial biodiversity dimensions have been much more exploited than temporal ones. One of the reasons for which temporal patterns have received less attention is a scarcity of long-term studies, especially in the neotropical region, one of the most biodiverse and endangered on the planet. Studying the dynamics of populations and communities over time can reveal key ecological processes as well as describe how natural and human pressures affect biodiversity. Understanding the dynamics of populations and communities involves understanding organisms life histories, how they interact with the environment, the role of interactions among species, the role of stochastic demographic processes, and other factors. In this dissertation we investigated the temporal dynamics of butterflies and birds populations and assemblages, and throughout its chapters we evaluate the role of different processes in the regulation of dynamics. In Chapter 1 we investigated whether a seasonal behavior observed in butterflies Ithomiini (Nymphalidae, Danainae), supposedly adaptive to dissecation - the \"Ithomiini pockets \" - is a simple reactive response to drought or there is internal time-keeping mechanisms involved. In Chapter 2, we performed a comparative population dynamics study of mimetic butterflies of the Ithomiini tribe. Some evidence has suggested that besides the convergence in morphology, co-mimetic species would tend to converge also in behavior, in the use of microhabitats and possibly in their population dynamics. We hypothesized that (1) pairs of co-mimetic species or (2) pairs of species more phylogenetically related would have their population dynamics more correlated than pairs of species grouped at random. In Chapter 3 we described how species composition of bird and butterfly assemblages from nine tropical and subtropical locations in South and North America varied over time (years and decades), and if demographic differences between species (niche) are needed to explain observed patterns. In Chapter 1 we found evidence that Ithomiini pockets are regulated by internal time-keeping mechanisms synchronized to photoperiod, and that mechanism has limited plasticity to cope with rainfall regime changes predicted for the study region and for the continent as a whole. In Chapter 2 we found that the population dynamics of Ithomiini species pairs more phylogenetically related or belonging to the same mimetic ring did not tend to be more correlated than pairs assembled at random, and that the species, mimetic rings and subtribes had their temporal dynamics more correlated than would be expected By chance These results and those of Chapter 1 suggest that this system dynamics is more influenced by selective pressures exerted by environmental factors than by species interactions. In Chapter 3 we show that the composition of bird assemblages in the Amazon, Cerrado, Atlantic Rainforest, and Florida has changed over the years, even in assemblies of well-preserved areas. Superimposed to this interannual turnover we also found seasonal, predictable turnover in species composition of bird assemblages of the Amazon and Atlantic Forest and in the Ithomiini butterflies assembly. Patterns of seasonal turnover in species composition may be more common in neotropical communities than is imagined. The temporal strategies of neotropical organisms, which appear to be the basis of the seasonal patterns observed in communities, can be largely determined by endogenous rhythms (\"biological clocks\"). Studies on the regulation of organisms\' temporal rhythms and strategies, and the effects of climate change and land use on them, are essential. An important step in this direction is the dissemination of continuous, systematic, population and community long-term studies, with sampling resolution to detect seasonal patterns. In addition, the interaction of perspectives, theoretical basis, and approaches of molecular biology, physiology, chronobiology, and ecology can advance our understanding of the processes that shape biodiversity dynamics and the consequences of human disturbances on ecosystems

O presente trabalho consiste em uma extensão do sistema FreeFlow-2D para simular escoamentos de fluidos não newtonianos bidimensionais com superfí cies livres, onde o fluido é descrito pelos modelos de Cross ou o modelo ``power-law\'\'. O método numérico empregado é o método GENSMAC. As equações governantes são aproximadas pelo método de diferenças finitas em uma malha deslocada e partículas marcadoras são utilizadas para a visualização do escoamento e localização da superfície livre. Resultados numéricos são apresentados. Em particular, a presente implementação é validada comparando-se a solução numérica com uma solução analítica / This work presents an extention of the Freeflow-2D system to non-Newtonian free surface flows. The governing equations are solved by the finite difference method on a staggered grid. Marker particles are used to describe the fluid providing the location and the visualization of the free surface. The methodology employed is based on the GENSMAC method. The fluid is modelled by the Cross and power-law models. Numerical examples are presented. The code is validated by making a comparison between analytical and numerical solutions

Neste trabalho estudamos os homomorfismos entre anéis de polinômios do ponto de vista da teoria de bases de Groebner. Em particular, determinamos o núcleo de um tal homomorfismo e desenvolvemos um método para determinar quando este é sobrejetivo. Estes resultados são então generalizados para anéis quocientes. O estudo de tais homomorfismos nos permite determinar os polinômos minimais de elementos em extensões de corpos, bem como encontrar soluções para um problema de programação inteira. / In this work we study the homomorphisms between polynomial rings as an application of the Groebner basis theory. In particular, we determine generators for the kemel of such a homomorphism and we give a method to determine whether it is onto. We then generalize these results to the case of quocient rings. The study of these homomorphisms allows us to determine mini mal polynomials of elements in field extensions, as well as to find solutions to an integer programming problem.

No presente trabalho estudam-se diferentes técnicas explícitas, em diferenças finitas, no emprego de algoritmos do tipo velocidade-pressão para simulação de escoamentos incompressíveis. O método de resolução da pressão de maneira direta e explícita, introduzido por Bravo e Claeyssen [BRA 97a], é analisado. Faz-se uma aproximação para o erro causado por esta técnica, e verifica-se como isto afeta a equação da continuidade. As simulações são realizadas na cavidade quadrada, comparando-se os diferentes métodos e validando as aproximações realizadas no estudo do método de resolução da pressão. Além disso, simula-se o escoamento em cavidades profundas e rasas, observandose a formação de vórtices e distribuição de energia cinética. Simulações do escoamento na cavidade cúbica também são apresentadas. / In this work different explicit technics in finite defferences in the application of velocity-pressure algorithm to simulate incompressible flows have been studied. The direct and explicit method of pressure resolution, introduced by Bravo anel Claeyssen [BRA 97a] is analyzed. An approximation to the error caused by this method is made, anel how this affects the continuity equation is verified. The simulations are maele in a square cavity, comparing the differents methoels anel valielating the approximations maele in the study of the pressure resolution method. Besieles this, flow in eleep and shallow cavities is simulateel, observing the formation of vortices and kinetic energy distribution. Simulations of the flow in the cubical cavity are also considered.

A Física tem uma maneira própria de olhar a natureza e de estudar seus fenômenos. Por essa razão, o ensino-aprendizagem de Física não pode estar centrado na transmissão de informações, mas sim na construção do conhecimento em um contexto amplo que envolva conteúdos, novas metodologias e novos instrumentos adequados à realidade da escola, que venham a contribuir para uma aprendizagem significativa. Dentro dessa concepção, apresenta-se uma proposta de ensino de ótica, com ênfase no estudo através de módulos didáticos. Para tal, foram elaboradas atividades didáticas incluindo simulações de eventos com o uso de novas tecnologias e, também, em laboratório convencional, exploradas em uma visão construtivista fundamentada nas teorias de Vygotsky e de Ausubel. No desenvolvimento dessas atividades procurou-se propiciar o compartilhamento de significados através de diagramas fundamentados no V de Gowin, na busca de uma aprendizagem significativa. A composição dos módulos didáticos apresenta uma motivação inicial através de exposição oral questionada, com o objetivo de despertar no aluno seus conhecimentos prévios. Em cada um dos módulos didáticos são sugeridas uma ou mais atividades a serem trabalhadas em grupos de 3 a 4 alunos, constando de experimento virtual (applets, simulações) ou real, acompanhado de guia simplificado. Essa dinâmica de trabalho gerou uma maior interação social entre os alunos; ao professor, coube o papel de mediador da atividade. Paralelamente a cada atividade, cada grupo de alunos construiu um diagrama V, que era apresentado à turma posteriormente, com o objetivo de promover discussões. A aplicação da proposta foi realizada no quarto bimestre letivo do ano de 2006, em uma turma de terceira série de Ensino Médio, noturna, da Escola Estadual de Ensino Médio Dr. Araby Augusto Nácul, em Lagoa Vermelha, RS. O material instrucional elaborado, na forma de página da Web, contém as atividades propostas nos módulos didáticos e também os correspondentes diagramas V a serem construídos pelos alunos. Também são incluídos na página da Web, como links, um material de apoio, com os conteúdos desenvolvidos nos vários módulos, e uma seção contendo exercícios de fixação. Com os alunos trabalhando em um determinado módulo didático, o material era disponibilizado nos computadores da Escola, gradualmente, para evitar que avançassem para os módulos seguintes antes de refletir sobre o conteúdo da atividade em andamento. O produto educacional, contendo o material instrucional e orientações para o seu uso, será divulgado na série Hipermídias de Apoio ao Professor de Física para que outros professores da rede de ensino possam adaptá-lo a sua realidade escolar. / Physics has its own way of looking at nature and its phenomena. For this reason the Physics’ teaching must not only be centered in lecturing information, but must also construct the knowledge in a wide context involving new technologies and tools fitted to the schools' reality. This, together with physics concepts, is to build a meaningful learning. To accomplish these goals we propose an approach to Optics teaching, structured in six didactic modules based on the meaningful learning’s theory by D. Ausubel and the social interaction’s theory by L. Vygotsky. Each didactic module starts with an oral exposition presenting the motivation through challenging questions, in order to instigate the students’ previous knowledges. We then suggest one or more activities based on virtual (e.g., simulations, applets) or real experiments, with a schematic activities guide, to be worked out by groups of three or four students, with the teacher mediation, in order to deepen social interaction. Besides each experimental activity, they construct an adapted Gowin V diagram, intended to promote a meaningful learning, and finally they discuss with the rest of the class, encouraging an exchange of views about the proposed issue. This methodological proposal has been applied to 18 third high school year students, of the nightclass at "Escola Estadual de Ensino Médio Dr. Araby Augusto Nácul" at Lagoa Vermelha, RS, during the fourth bimester of the school year of 2006. The instructional material was developed as a webpage, including the proposed experimental activities and the related V diagrams. Among the webpage links, we also included additional material with the physics contents of the didactic units and exercises. The whole instructional material has gradually been made available on the School’s computers to prevent the students from going to a forthcoming activity before having made deep reflections on the lectures/subjects that were being worked out at each moment. This work is to be published in the series Hipermídias de Apoio ao Professor de Física, of Instituto de Física of UFRGS, so that other teachers can access this material and use it in their school's context.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / The increase in linear and non-linear loads experienced by Brazil in recent years has changed the way distribution networks are planned and Operated. In addition, the competitiveness of the market and the demand for the improvement in power quality indexes mean that current e orts are increasingly focused on areas such as voltage profile control and voltage harmonic distortion control. This work deals, exactly, with the Integrated control of voltage and harmonic voltage distortion (volt/thd) in distribution systems, within the scope of planning, through the insertion of passive harmonics filters and voltage regulators. To solve the problem in question, a multiobjective algorithm, the NSGA-II, is applied, since the presented problem can be treated as a combinatorial optimization problem. The power summation method is used as an alternative for the resolution of the load flow. While the current injection method is used as a calculation of the harmonic flow. The mathematical models of the network components were presented, taking into account the influence of frequency, in a detailed way. The proposed algorithm was applied in benchmark systems, a 34-bus and a 104-bus, the systems were simulated with and without the presence of the devices for comparison and validation of the results. / O aumento de cargas, lineares e não-lineares, vivenciado pelo Brasil nos últimos anos, tem alterado a maneira com as redes de distribuição são planejadas e operadas. Além disso, a competitividade do mercado e exigência pela melhoria nos índices de qualidade da energia fazem com que os esforços atuais sejam cada vez mais direcionados para áreas como o controle do perfil de tensão e o controle das distorções harmônicas de tensão. Esta dissertação trata, exatamente, do controle integrado de tensão e distorção harmônica de tensão (volt/dht) em sistemas de distribuição, no âmbito do planejamento, através da inserção de filtros harmônicos passivos e reguladores de tensão. Para resolver o problema em questão, um algoritmo multiobjetivo, o NSGA-II, é aplicado, uma vez que o problema apresentado é tratado como um problema de otimização combinatória. O método da soma de potências é utilizado como alternativa para a resolução do fluxo de carga. Enquanto que o método da injeção de correntes é utilizado como cálculo do fluxo de harmônicos. Os modelos matemáticos dos componentes da rede foram apresentados, levando-se em consideração a influência da frequência, de forma detalhada. O algoritmo proposto foi aplicado em sistemas teste de 34 e 104 barras e os sistemas foram simulados com e sem a presença dos dispositivos para efeito de comparação e validação dos resultados.