Este trabalho sugere um algoritmo para ambiente distribuído que determina as K-melhores soluções para o problema da mochila unidimensional. O algoritmo baseia-se no trabalho de Yanasse, Soma e Maculan (1995), que trata da mesma questão para ambiente serial. Entretanto, convém ressaltar que a versão distribuída do algoritmo possui profundas modificações em relação à versão serial. Primeiramente, o algoritmo serial foi estudado e totalmente implementado. A segunda etapa do trabalho foi o desenvolvimento do algoritmo distribuído. Parte desta tarefa tratou da escolha de uma abordagem de implementação no ambiente distribuído. Duas abordagens foram levadas em consideração e os respectivos algoritmos foram implementados e testados. O paradigma divide and conquer para algoritmos paralelos foi o que prevaleceu. Quanto ao ambiente operacional, o algoritmo serial foi desenvolvido, na sua fase inicial, sobre a plataforma 486/Windows e linguagem de programação C++. Posteriormente, portou-se a aplicação para o ambiente RISC/UNIX. O algoritmo distribuído foi desenvolvido em linguagem de programação C++ aliada às funções da biblioteca PVM, Parallel Virtual Machine (Máquina Paralela Virtual), em uma rede de estações UNIX. Resutaldos computacionais são apresentados.

O presente trabalho apresenta um algoritmo e procedimentos para a obtenção de parâmetros orbitais e determinação preliminar de órbitas, a partir de dados de posição fornecidos por radar. Utiliza-se um modelo simplificado, baseado no problema dos dois corpos, que envolve a resolução de um problema de valor de contorno em dois pontos através do método de Gauss. Uma propagação de órbita simplificada é efetuada considerando-se apenas as variações seculares devidas aos efeitos perturbadores do achatamento da Terra. Assim, as observações obtidas pelo radar são processadas seqüencialmente e a órbita determinada e/ou propagada através de soluções analíticas, evitando-se a integração numérica. Os resultados dos testes realizados sob condições simuladas, e por comparação com parâmetros previamente conhecidos, indicam a viabilidade da utilização do algoritmo proposto, em sistemas autônomos de determinação de órbita.

Esta tese melhora o upper bound de tempo e de espaço da resolução paralela do Subset-Sum Problem (SSP) - que é uma variante do Problema da Mochila - numa máquina PRAM SIMD CREW (Parallel Random Access Machine; Single Instruction/Multiple Data; Concurrent Read/Exclusive Write) nos dois paradigmas mais consagrados na literatura científica, isto é, tanto na abordagem através das listas como por programação dinâmica. Com relação ao primeiro paradigma, é apresentada uma paralelização ótima e adaptativa do conhecido algoritmo das duas listas de Horowitz e Sahni (JACM, 1974) numa PRAM SIMD CREW de p processadores: ela resolve o SSP de n objetos em tempo O(2n/2/p) e espaço O(2n/2), onde 1 p < 2n/2/n2. Como esse algoritmo seqüencial tem até hoje a melhor complexidade de tempo para a resolução do Problema da Mochila, então nosso algoritmo paralelo pode ser considerado, a partir de agora, como o melhor resultado teórico de toda a literatura. Além disso, são apresentados três algoritmos paralelos adaptativos baseados no paradigma da programação dinâmica, que são os primeiros a resolverem o SSP de n objetos e capacidade c em tempo o(nc/p) e espaço O(n+c) numa PRAM SIMD CREW de p processadores. Eles melhoram as complexidades de tempo e de espaço do algoritmo de Lin e Storer, (JPDC, 1991), que vinha sendo o mais eficiente até o momento.

The Subset-sum Problem (SSP) consists of finding a subset of a set of integers whose sum is as close as possible to a target amount, without exceeding it. The problem is NP-complete, but there are dynamic programming-based algorithms which can solve many instances in reasonable time. Most of these algorithms attempt to minimize the time taken to find the solution for &quot;hard&quot; problem instances, but have sub-optimal performance when dealing with &quot;easy&quot; instances, either containing few items or with multiple equivalent solutions of which just one needs to be found. In this work, we analyze the characteristics of several well-known approaches, including standard dynamic-programming Bellman recursion, Horowitz-Sahni decomposition and core algorithms, and suggest variations which improve their average-case performance for easy instances, without harming their worst-case performance significantly. One variation improves the performance of the YS87 single state - multiple stages algorithm for sparse instances. Another minimizes the amount of work required by decomposition-based approaches before a solution is found, allowing the computation to be aborted earlier for dense instances with many exact solutions; this is achieved by using the programming concept of generators in order to compute partial solutions only when they are needed. We also examine the characteristics of several SSP test instance types which are commonly used to compare algorithm performances, analyzing how the distribution of partial solutions varies according to the type and size of the instances. The times taken by several algorithm implementations to solve each of the SSP instance types are measured and compared, and the variations in their behavior when dealing with each one are explained based on the instances'; characteristics.

Este trabalho compreende dois aspectos na abordagem do problema do decaimento D+ ? K ? ? + ? + , um experimental e outro teórico. No que tange a análise experimental, trabalhamos com dados simulados em Monte Carlo provenientes do detetor LHCb, para o decaimento mencionado. O desenvolvimento de um algoritmo numérico alternativo para o ajuste do gráfico de Dalitz foi feito, sendo este baseado em procedimentos executados por outras colaborações. O objetivo deste foi o de veri#car se este mesmo procedimento é viável nesta etapa de análise dos dados do LHCb. Este ajuste utilizou simulações de Monte Carlo para as ressonâncias presentes no decaimento, mas desconsiderou efeitos de fundo, e#ciência e cobertura angular do detector. Com relação aos aspectos teóricos, foi elaborado um modelo de re-espalhamento de três-corpos usando coordenadas na frente de luz para o estado final do D+ ? K ? ? + ? + . Neste modelo a amplitude off-shell é uma solução da equação de Bethe-Salpeter quadridimensional, decomposta na forma de Faddeev e projetada nas coordenadas de frente de luz através da expansão do quasi-potencial. O kernel da equação integral contem a amplitude de espalhamento K? na onda S nos estados de isospin, tanto 1/2 como 3/2, sendo essas ajustadas aos dados experimentais do experimento LASS. A solução das equações integrais tridimensionais na frente de luz para as amplitudes espectadoras, foram obtidas de forma perturbativa até segunda ordem, com uma contribuição em terceira ordem muito pequena. Os resultados numéricos para o módulo da magnitude e fase da amplitude deste decaimento foram comparados com os dados experimentais das colaborações E791 e FOCUS. Os dados experimentais sugerem uma pequena mistura entre o isospin total, 5/2, e o dominante, 3/2. O módulo da amplitude de decaimento não simetrizada, que apresenta um minímo profundo seguido de um crescimento para massas do sistema K? acima de 1.5 GeV, foi reproduzido de forma satisfatória. Podemos observar também que abaixo de 1 GeV o módulo é subestimado, ocorrendo o mesmo no do espaço de fase ao redor de 1.8 GeV.

Um dos maiores desafios para as agências espaciais é a utilização de fontes alternativas de energia que possibilitem missões espaciais de baixo custo no Sistema Solar. Neste contexto, a pressão de radiação solar tem sido apresentada como uma forma alternativa de propulsão para missões espaciais interplanetárias. Neste trabralho empregamos o modelo do Problema Restrito de Três Corpos Circular Espacial com a inclusão da força de pressão da radiação solar para investigar as estruturas dinâmicas mais essenciais no sistema Sol-Terra, isto é, as soluções de equilíbrio. Para um baixo valor do número de luminosidade, realizamos uma análise biparamétrica detalhada das famílias de soluções de equilíbrio que se relacionam às soluções clássicas do Problema Restrito. Através de um método de continuação numérica, calculamos os equilíbrios e suas localizações no espaço de fase e realizamos a análise de estabilidade linear dessas soluções, apresentando um estudo da classificação dos diferentes tipos de estabilidade no plano biparamétrico e suas bifurcações.

Em mecânica dos fluidos, especificamente em processos turbulentos, o problema de fechamento representa um dos maiores desafios para qualquer pessoa interessada nesta área. Durante décadas, cientistas vêm usando abordagens estatísticas com o objetivo de \"fechar\" o problema ou, pelo menos, diminuir as dificuldades inerentes. Assim, o presente trabalho apresenta uma criteriosa análise com base em ferramentas estatísticas em que ondas quadradas aleatórias, aliadas a um número fixo de parâmetros, foram utilizadas para criar equações paramétricas para representar um fluxo turbulento unidimensional com uma abordagem a priori, diferenciando de outras abordagens aplicadas amplamente na área, que utilizam uma abordagem a posteriori. Em seguida, simulações foram realizadas, a fim de avaliar o comportamento do modelo. Nas simulações pôde-se reproduzir o comportamento observado na literatura e estipular a abrangência do método. Além disso, uma importante discussão acerca das condições de contorno foi desenvolvida. / In fluid mechanics, specifically in turbulent processes, the closure problem represents one of the biggest challenges for anyone interested in this area. For decades, scientists have been using statistical approaches aiming to close the problem or, at least, decrease the inherent difficulties. So, the present project presents a judicious analyze based on statistical tools in which random square waves, allied with a fixed numbers of parameters, were used to create parametric equations to represent a turbulent flow with an a priori approach, differentiating from other approaches broadly applied in the area, which use an a posteriori approach. Then simulations were done, in order to evaluate the behavior of the model. In the simulations, the behavior of some data from the literature could be followed and the scope of the method was stipulated. Besides this, an important discussion about boundary conditions was developed.

Um dos mais investigados problemas na teoria qualitativa dos sistemas dinâmicos no plano é o XVI problema de Hilbert que investiga uma cota superior para o número de ciclos limites em sistemas diferenciais polinomiais e suas posições relativas. Por outro lado, os sistemas diferenciais suaves por partes tem despertado o interesse de muitos pesquisadores recentemente devido a sua estreita relação com outras áreas das ciências como física, biologia, economia e engenharias. Portanto é natural a busca pela extensão das técnicas e ferramentas da teoria qualitativa para essa classe de sistemas. Nessa dissertação apresentamos uma generalização da técnica do averaging para uma classe especial dos sistemas de Filippov, conhecida como sistemas diferenciais contínuos por partes, desenvolvida por Llibre-Novaes-Teixeira e, aplicamos essa técnica na investigação de uma classe particular de sistemas, que chamamos do tipo Kukles generalizado. / One of the most investigated problems in the qualitative theory of dynamical systems in the plane is the XVI Hilbert\'s problem which asks for the maximum number and position of limity cycles for all planar polynomial differential systems of degree n. On the other hand, recently piecewise continuous differential systems have attracting the interest of many researches specially because of their close relation with other sciences for instance physics, biology, economy and engineering. These relations motivate extensions of the qualitative tools for this class of systems. In this work we present a generalization of the averaging theory for a class of Filippov systems, namely piecewise continuous differential systems, developed by Llibre-Novaes-Teixeira and, we apply this theory to a particular class of differential systems, which we nominate generalized Kukles type.

Empresas estão procurando reduzir seus custos e aumentar seu desempenho e competitividade. Neste cenário de redução de custos, a logística colaborativa pode ser uma aliada. Numa rede complexa, onde embarcadores muitas vezes nem sabem da existência de outros embarcadores com demandas complementares, existe um potencial de sinergia e redução de custos através da diminuição de deslocamentos de veículos sem carga, ou seja, deslocamentos para reposicionar os veículos. Visando essa redução, o Problema de Cobertura de Rotas (PCR), que tem como objetivo cobrir rotas no mínimo custo, une as demandas de frete de vários embarcadores e tenta minimizar os deslocamentos sem cargas (reposicionamentos), reduzindo assim o custo total de toda a rede dos embarcadores envolvidos. Esta pesquisa propõe um modelo e uma heurística para resolver, em grande escala através de programação paralela, uma expansão do PCR. / Companies are looking to reduce costs and improve performance and competitiveness. In this cost-cutting scenario, collaborative logistics can be an ally. In a complex network where shippers often do not know of the existence of other shippers with complementary demands, there is potential for synergy and cost savings by reducing unloaded travelling of vehicles, i.e, the distance and time to reposition the vehicles\'. Towards that reduction, the Lane Covering Problem (LCP), which aims to cover at least cost routeslinks the various shippers\' demands of freight and tries to minimize operations without loads (repositioning), thus reducing the total cost of the entire network for involved shippers. This research proposes a model and an heuristic to solve, in large-scale through parallel programming, an expansion of the PCR.

O presente trabalho consiste em uma pesquisa sobre como adolescentes jogam e resolvem situações-problemas relativas ao Sudoku. O objetivo foi analisar o raciocínio de escolares por meio de seu desempenho nesse jogo. Poucas são as pesquisas com jogos de regras para o desenvolvimento e aprendizagem de alunos de 9º ano do Ensino Fundamental II e, por isso, o desejo em pesquisar sobre o desenvolvimento do raciocínio por meio do jogo Sudoku com essa parcela da população escolar. O ponto diferenciador de nosso trabalho é a questão da dificuldade dos alunos em justificar suas respostas às situações- problema propostas. Para tanto, a professora-pesquisadora elaborou partidas de jogo Sudoku e situações-problema relativas ao mesmo jogo e as desenvolveu com 21 alunos de 9º ano do Ensino Fundamental II de uma escola pública do município de São Paulo. A coleta de dados foi realizada durante 15 aulas por meio de protocolos elaborados pela professora-pesquisadora. Na análise desses dados coletados, investigamos o desenvolvimento do raciocínio dos alunos ao longo dos encontros por meio de suas resoluções e da linguagem que utilizaram para justificar suas respostas aos jogos e aos Enigmas Sudoku propostos. A discussão dos resultados foi orientada principalmente pelos estudos de Jean Piaget quanto ao desenvolvimento e à aprendizagem e pelo estudo de Philippe Meirieu sobre como aprender por meio de situações-problema. Os alunos avançaram consideravelmente do primeiro encontro para o último em relação aos conceitos e procedimentos relativos aos jogos e às situações-problema e, além disso, desenvolveram sua justificação lógica, permitindo concluir que as experiências por que passaram ofereceram a oportunidade de tomarem consciência dos motivos que os orientaram em suas escolhas. Consideramos essa pesquisa relevante para o campo da Psicologia do Desenvolvimento e da Aprendizagem, pois, por meio de um jogo, aprendemos a trabalhar o raciocínio e uma forma de pensar, útil para a escola e para a vida / This work is a research about how teenagers play and solve problem situations related to Sudoku. The aim was to analyze the logic of students through their performance in that game. There are not so many researches on rule games for development and learning of students in 9th grade from Elementary School and, because of this, there was the desire to research the development of logic through Sudoku game with this part of the school population. The differentiator point of this work is the question of the students difficulty to justify their answers to the proposed problem situations. For that, the teacher-researcher elaborated Sudoku matches and problem situations related to the same game and developed them with 21 students in the 9th grade of the Elementary School in a public school in São Paulo city. The data collection was done during 15 classes by protocols elaborated by the teacher-researcher. In the analysis of the collected data, we investigated the development of the students´ logic during the encounters with the solutions and the language used to justify their answers in the proposed games and puzzles. The discussion of the results was oriented by the studies of Jean Piaget on development and learning and by the studies of Philippe Meirieu on how to learn with problem situations. The students had a considerable progress from the first encounter to the last one in relation to concepts and procedures related to the game and to the problem situations and, beyond that, they developed their logical justification, allowing us to conclude that the experiences that they had endured offered them an opportunity to be conscious of the reasons that oriented them on their choices. We consider this research relevant to the Developmental and Educational Psychology field because through a game we learned to work with logic and a way of thinking, useful for school and life