[pt] A determinação automática e ótima de uma topologia é um passo muito importante dentro do processo da otimização de estruturas. Normalmente, a busca da topologia ótima é o primeiro passo para a definição da configuração da estrutura, pois é nela que é encontrada uma distribuição ótima de material dentro de um domínio pré-estabelecido. Esta dissertação tem como objetivo apresentar uma metodologia simples de otimização topológica, dado um sistema estrutural, definido por suas condições de apoio, carregamento e um domínio de projeto. Tipicamente, um problema de otimização topológica procura obter uma conectividade ótima da estrutura em um domínio de projeto visando minimizar a flexibilidade (ou maximizar a rigidez) com restrição no volume total da estrutura. Desde a introdução dos métodos de homogeneização o campo de pesquisa na área de otimização topológica aumentou e novos critérios estão sendo desenvolvidos. Nesta dissertação é apresentada uma metodologia para a solução de problemas de otimização topológica de estruturas no meio contínuo. A parametrização do tensor constitutivo é feita através de materiais do tipo SIMP (Solid Isotropic Microstruture with Penalty). O problema matemático proposto é o de minimização do volume total da estrutura com restrição no trabalho externo, além de obedecer implicitamente às restrições de equilíbrio e conectividade da estrutura. A análise estática da estrutura é realizada pelo Métodos dos Elementos Finitos utilizando o programa FEMOOP (Finit Element Method - Object Oriented Program) desenvolvido pelo grupo de pesquisa em computação gráfica do DEC/PUC-Rio. Vários métodos são sugeridos para a resolução do problema matemático de otimização topológica. Entre eles encontram-se métodos puramente heurísticos e métodos amparados por uma base matemática sólida. Nesta dissertação, o problema de otimização topológica é resolvido através de técnicas de programação matemática e é resolvido através da técnica de programação seqüencial convexa, utilizando o algoritmo do Método das Assíntotas Móveis (MMA). O desenvolvimento de um programa de computador em otimização topológica, permitiu determinar de maneira automática uma topologia ótima, bem como o estudo de algoritmos de solução e critérios de otimização topológica foi de grande importância para uma maior compreensão de modelos estruturais. / [en] Automatic and optimal determination of a topology is a crucial step in the process of structural optimization. Usually, the search for an optimal topology is the first step for the definition of the structure layout, found as an optimal distribution of material inside of a pre- established domain. This dissertation has as an objective to present a simple methodology for topology optimization, given a structural system, defined by support conditions, load and a design domain.Typically, a problem of topology optimization tries to obtain an optimum connectivity of the structure in a design domain, seeking to minimize the compliance (or maximize the stiffness) with constraints over the total volume of the structure. Since the introduction of homogenization methods,the research field in the area of topology optimization increased and new criteria are being developed.In this dissertation a methodology is presented for the solution of problems of topology optimization of structures in a continuum medium. The parametrization of the constitutive tensor is made through materials of the type SIMP (Solid Isotropic Microstruture with Penalty). The proposed mathematical problem is of minimization of the total volume of the structure with constraint to the external work while obeying implicitly the equilibrium constraints and connectivity of the structure. The static analysis of the structure is accomplished by the Finite Elements Method using the program FEMOOP (Finite Element Method - Object Oriented Program) developed by the research group in computer graphics of DEC/PUC-Rio.Several methods are suggested for the resolution of the mathematical problem of topology optimization. Among them there are some purely heuristic and others aided by a solid mathematical base. In this dissertation, the problem of topology optimization is solved through techniques of mathematical programming, applying the technique of convex sequential programming, using the algorithm of the Method of Moving Asymptots (MMA).The development of a computer program in topology optimization allowed us to determine automatically an optimal topology, and the study of solution algorithms and criteria of topology optimization were of great importance to a larger understanding of structural models.

[pt] Esta dissertação apresenta um estudo de caso em seqüenciamento da produção de bobinas de aço em um laminador de tiras a quente com enfornamento a frio das placas de aço. O laminador em questão é o da Companhia Siderúrgica de Tubarão, uma grande usina siderúrgica integrada localizada no estado do Espírito Santo, Brasil. Seu start up está previsto para o segundo semestre de 2002. Num primeiro momento, o problema parece ser de tratamento complexo, comportando-se como um grande problema combinatorial com restrições difíceis de serem representadas. Algumas considerações para um bom seqüenciamento são comuns tanto no forno de reaquecimento quanto no laminador desbastador. Isto permite que as placas possam ser seqüenciadas como se esses dois equipamentos fossem um único estágio (equipamento) para alguns agrupamentos de produtos. Assim, o foco pode ser deslocado para o seqüenciamento no estágio final do laminador, isto é no trem acabador. Inicialmente, a idéia era resolver um modelo da mochila compartimentada para a seleção das placas de aço a serem processadas entre duas trocas consecutivas de cilindros de trabalho do trem acabador e usar algumas heurísticas para seqüenciá-las dentro de cada compartimento (faixa de largura). Um estudo do mix de produção planejado mostrou que, devido à grande variedade e quantidade de ordens, a fase de seleção não era crítica e o seqüenciamento poderia ser feito semimanualmente com ajuda do computador. Para aumentar a vida útil dos cilindros de trabalho, assim como atender a qualidade desejada e a data de entrega prometida, no decorrer de uma boa seqüência de laminação deve ocorrer decréscimo nas larguras e na qualidade superficial, trocas suaves de espessuras e de dureza. O sistema computacional proposto implementa um algoritmo simples que seqüencia lexicograficamente o grupo de produtos a ser laminado de acordo com as prioridades dadas a cada critério de seqüenciamento pelo próprio programador da produção, que pode interagir e trocá-las de acordo com as condições prevalecentes. / [en] This thesis reports a case study on scheduling the cold charged production of coils in a hot strip mill with start- up planned for the second semester of 2002 at Companhia Siderúrgica de Tubarão, a large integrated steel plant in Espírito Santo, Brazil. At first glance, the problem seems intractably complex, being essentially a very large-scale combinatorial problem with ill-defined and difficult to represent constraints. Considerations on the requirements for good sequencing at the reheating and roughing stages showed that they could be scheduled as a single stage for some groups of products, and in doing so, the focus could be on sequencing the finishing stage. Initially, the idea was to solve a compartmented knapsack model for selecting the slabs to be processed between two consecutive changes of working rolls, and using some heuristics for sequencing within each compartment (width range). Examination of the projected product mix showed that, due to the large number and variety of orders, the selection phase was not critical, and the scheduling could be performed semi-manually with a simple computer aid. For extending the life of the working rolls, as well as attaining the desirable quality and promised dates, a good sequence must present decreasing width and surface quality, increasing promised dates, and smooth changes of thickness and hardness. The proposed computer system implements a simple algorithm that lexicographically sorts the set of products to be rolled according to priorities given to these criteria by the scheduler who can interactively change them according to the prevailing conditions.

[pt] Consideramos o Problema Quadrático da Mochila 0-1 (QKP), que consiste em maximizar uma função booleana quadrática sujeito a uma restrição de capacidade linear. O problema possui aplicações em várias áreas, como por exemplo, telecomunicações. engenharia financeira, problemas de localização e teoria dos grafos (clique máximo). Propomos um algoritmo de Branch-and-Bound para resolver exatamente QKP, baseado em Relaxação Lagrangeana. Inicialmente, linearizamos a formulação do problema acima, e em seguida, aplicamos a técnica de relax-and-cut dinamicamente à relaxação contínua do problema, utilizando algumas classes de desigualdades válidas. O método do subgradiente é usado neste processo. Propomos também uma nova heurística primal para QKP, que obtém soluções melhores do que heurísticas propostas anteriormente, encontrando a solução ótima em todas as instâncias que consideramos. A boa qualidade dos limites superior e inferior é traduzida em gap`s pequenos no nó raiz da árvore de enumeração (em geral, menor do que 1%, inclusive para instâncias difíceis). Isto, aliado a testes de fixação de variáveis, permite resolver exatamente QKP em poucos nós da árvore de enumeração. Introduzimos uma maneira de gerar instâncias aleatórias mais difíceis do que as instâncias na literatura. Apresentamos resultados computacionais para instâncias geradas aleatoriamente (instâncias da literatura, e as novas instâncias mais difíceis) para QKP de tamanhos e densidades diferentes; e também para instâncias conhecidas do problema de clique máxima. / [en] We consider the 0-1 Quadratic Knapsack Problem (QKP), which consists of maximizing a quadratic Boolean function subject to a linear capacity constraint. The problem has applications in several areas such as telecommunications, financial engineering, location problems, graph theory (Max Clique). We propose a Branch-and-Bound algorithm to solve the QKP to optimality based on lagrangian Relaxation. Initially, we linearize the formulation of the problem given above and then we relax-and-cut dinamicaly its continous relaxation using a few classes of valid inequalities. In the process the Subgradient Method is applied. We also propose a new primal heuristic for the QKP that has improved upon previous approaches, and finds an optimal solution for all of the instances we considered. The good quality of our upper and lower bounds is translated into small gaps at the root node of the enumeration tree (usually below 1%, even for difficult instances). That, coupled with tests for fixing variables, allowed optimality to be proven within only a few nodes of the enumeration tree. We provide a way to randomly generate instances of the QKP harder than those in the literature. We report computational results for randomly generated instances (the ones in the literature and the new harder ones) of QKP with different densities and sizes; and also for Known instances of Max Clique problems.

[pt] Problemas de Programação de Horários (PPHs) tem sido amplamente estudados, dada a sua importância prática e teórica. A maioria das variações do problema pertence µa classe NP-Difícil. Em geral, trata-se da alocação de recursos materiais e humanos no espaço e no tempo, visando a otimização de um conjunto de objetivos definidos. Na Programação de Horários de Cursos Universitários, por exemplo, o objetivo pode ser a satisfação do corpo docente e o desempenho acadêmico dos alunos. Nos últimos anos, as formulações de PPHs propostas pela International Timetabling Competition (ITC) tem sido bastante utilizadas, sendo notável a predominância de métodos baseados em busca local e metaeurísticas entre as abordagens propostas recentemente. Este trabalho tem como objetivo propor algoritmos para o Problema de Programação de Horários Pós-Matrícula da ITC, focando principalmente em métodos heurísticos baseados em Programação Matemática. Entre os modelos de Programação Linear Inteira Mista que propomos para este problema, destaca-se o modelo baseado na Formulação de Representantes Assimétricos para o Problema de Coloração de Grafos. Abordamos a aplicação da heurística de Local Branching e propomos um esquema de resolução por Geração de Colunas, como forma de viabilizar o tratamento dos modelos propostos, uma vez que a complexidade de tais modelos representa um desafio para os resolvedores de Programação Linear Inteira Mista atualmente disponíveis. / [en] Timetabling Problems have been widely studied, given its practical and theorical relevance. Most of its variations belong to the NP-Hard class of problems. In general, it is about allocation of material and human resources in time and space, aiming to optimize some set of defined objetives. In University Course Timetabling, for example, the objective might be the satisfaction of professors and the academic performance of students. In the last years, the formulations for timetabling problems proposed by the In- ternational Timetabling Competition (ITC) have been widely adopted. The predominance of meta-heuristics and local search-based methods is remark- able among the recently proposed approaches. The objetive of this thesis is to propose algorithms for the Post Enrolment-based Course Timetabling Problem of the ITC, focusing on Mathematical Programming-based heuris- tic methods. Among the Mixed Integer Linear Programming models that we propose for this problem, we highlight the one based on the Asymetric Representatives Formulation for the Graph Coloring Problem. We explore the application of the Local Branching heuristic and we propose a Column Generation solution procedure, as an attempt to handle the proposed models, given that the complexity of such models poses a challenge for currently available Mixed Integer Linear Programming solvers.

[pt] Esta dissertação apresenta uma integração entre a programação funcional e a programação em lógica, obtida pela definição e implementação da Linguagem LispLog. Nesta nova linguagem, o resultado de uma resolução pode ser utilizado como argumento de uma função (pelo operador metalisp) e o resultado da avaliação de uma função pode ser ligado a uma variável lógica (pelo operador avalia). A construção desta linguagem foi realizada a partir da simulação, em microcomputador similar ao IBM-PC, de uma máquina com arquitetura de pilhas, chamada Máquina LispLog, e de seu compilador. A utilização desta linguagem é possível através do Sistema LispLog, que fornece um ambiente de programação orientado por menus. / [en] This dissertation shows an integration between the function programming and logic programming, achieved through LispLog Language’s definition and implementation. In this new language the resultant of a resolution may be used as an argument of a function (through metalisp operator) and the result of a function’s avaliation may be linked to a logic variable (through avalia operator). The LispLog Language was constructed by a simulation of stack architecture machine, named LispLog Machine, and its compiler, in a microcomputer similar similar to IBM-PC. The LispLog System provides a programming environment oriented by menus, wich makes possible the use of this language

[pt] O transporte de materiais perigosos tem recebido atenção considerável nos últimos anos, despertando assim o interesse de pesquisadores em se aprofundar e desenvolver modelos matemáticos de roteirização que minimizem o risco associado a esta operação. O presente trabalho baseia-se em estudos focados em encontrar rotas que minimizam a distância total, a probabilidade de acidentes, a população potencialmente exposta, as conseqüências associadas aos acidentes ou uma combinação desses fatores. No entanto, ainda que uma rota possa ter uma probabilidade muito baixa de acidente, ou estar associada a uma baixa conseqüência esperada (custo), pode não ser correto escolher essa rota se a conseqüência potencial ao ocorrer um acidente seja alta. Percebe-se então, que os diferentes interesses ligados à otimização do transporte de Materiais Perigosos (MP) podem ser conflitantes entre si, obtendo assim um problema com múltiplos objetivos, no qual nem sempre é possível identificar a melhor solução, ou seja, uma alternativa que se desempenha melhor que outras, em todos os critérios. Nesse contexto, o estudo que segue apresenta um modelo multiobjetivo para a roteirização de MP, além de uma metodologia específica de resolução que permita determinar rotas que minimizam o risco de acidentes com baixas probabilidades de ocorrência, mas com altas conseqüências, que podem dar lugar a altos custos, tanto ao meio ambiente como à população exposta. Ao final do trabalho são feitas indicações de questões e extensões para futuras pesquisas. / [en] Hazardous materials transportation has received considerable attention in the last years. Many researchers have been developing mathematical models that minimize the risk associated to this operation. The present work is based on studies that focus routing techniques that minimize either the total distance, the expected number of accidents (fatal or not fatal), the accident probability, the residential population within a given distance from a route, or a mixture of these parameters. They work with the assumption that a route should not be chosen if the potential consequence incurred given that an accident occurs is high, even if the route has a very low probability of an accident, or a low associated expected consequence. For this reason, it is possible to observe that an important characteristic of the hazardous materials routing problem is the existence of multiple conflicting objectives. This means that a route that minimizes risk may not coincide with a route that minimizes the truck operating cost, or with a route that minimizes the risk imposed to special population categories. In this context, this research presents a multiobjective model to the Hazardous Materials Routing and also a specific solution methodology that determines routes that minimize the accident risk with low probabilities, but with high consequences, including the high cost affecting the environment and the population exposed. A number of extensions and open issues are indicated for future research.

[pt] A investigação aqui relatada trata da concepção de elementos estruturantes para ampliar as oportunidades de intervenção pelo professor em um contexto de aprendizagem de programação em grupo. A partir de uma série de estudos de caso com turmas de calouros em cursos de computação, foi desenvolvida a sistematização de práticas, metodologias e tecnologias em uma abordagem para apoiar a aprendizagem de programação em grupo, baseada em três frentes de investigação: pressupostos pedagógicos, ferramentas LMS e métodos de colaboração. O eixo teórico referente à aprendizagem é a teoria de desenvolvimento cognitivo de Piaget, aliada a técnicas conhecidas de programação em grupo utilizadas no ensino de graduação em disciplinas introdutórias de programação. As ferramentas computacionais são utilizadas para monitorar e intervir durante o processo de aprendizagem. Nesse contexto, ambientes CSCL incentivam a colaboração e regulam as práticas desejadas. Nesta tese, outras tecnologias, como linguagens para representação de agentes e identificação de padrões são agregadas a eles para melhorar o acompanhamento e facilitar a intervenção. Por fim, como método de colaboração, é proposto um esquema progressivo de aprendizagem de programação em grupo, que auxilia os alunos a gradativamente adotarem práticas colaborativas na resolução de exercícios e que pode ser formalizado para incorporação a plataformas automatizadas. / [en] The research reported here deals with devising structuring elements that may broaden intervention opportunities from the teacher in a context of group programming learning. Based on a set of case studies with freshmen in computing courses a systematization for practices, methods and technologies was developed producing an approach for supporting group programming based in three investigation paths: pedagogical assumptions, CSCL environments and collaboration methods. The main learning rationale is Jean Piaget’s Cognitive Development Theory, used alongside group programming techniques commonly applied in undergraduate introductory programming courses. Computational tools are used to monitor and intervene during learning process and in such context, CSCL environments encourage collaboration and regulate expected practices. In this thesis other technologies like languages for agent representation and patterning identification are also exploited for improving control and facilitate interventions. Finally, as collaboration method, it is proposed a Programming Progressive Learning Scheme that helps students to adopt collaborative practices when solving exercises and that can be formalized to be used with automated platforms.

[pt] A representação de formas é um problema fundamental em Computação Gráfica. Dentre as representações conhecidas para objetos tridimensionais, os campos de distância amostrados adaptativamente (ADFs) destacam-se por sua versatilidade. ADFs combinam os conceitos de geometria com dados volumétricos, permitem representar objetos com precisão arbitrária, e consolidam diversas operações como visualização, modelagem de níveis de detalhe, detecção de colisão, testes de proximidade, metamorfose e operações booleanas em uma única representação. Este trabalho propõe métodos para acelerar a reconstrução de ADFs estáticas, melhorar a qualidade dos campos reconstruídos, e visualizar iso-superfícies das ADFs, valendo-se do enorme poder computacional encontrado nas placas gráficas modernas (GPUs). Para que as ADFs sejam representadas de forma eficiente em placas gráficas, propõe-se o uso de uma estrutura hierárquica baseada em dispersão espacial perfeita. A renderização de ADFs é feita integralmente pela GPU, utilizando uma técnica de lançamento de raios baseada em traçado por esferas. Uma maneira de tratar as descontinuidades C0 e C1 inerentes às ADFs é sugerida para que o sombreamento das superfícies seja suave. Finalmente, o trabalho propõe um novo método de reconstrução para ADFs, capaz de representar melhor superfícies curvas. Os resultados são apresentados através de aplicações simples de visualização interativa, com ADFs geradas a partir de malhas de triângulos e sólidos primitivos. / [en] Shape representation is a fundamental problem in Computer Graphics. Among known representations for three-dimensional objects, adaptively sampled distance fields (ADFs) are noted for their versatility. ADFs combine the concepts of geometry with volume data, allow objects to be represented with arbitrary precision, and consolidate several operations - such as visualization, level-of-detail modeling, collision detection, proximity tests, morphing and boolean operations | into a single representation. This work proposes methods to accelerate the reconstruction of static ADFs, to improve the quality of reconstructed fields, and to visualize ADF isosurfaces, making use of the massive computational power found in modern graphics hardware (GPUs). In order to effciently represent ADFs on graphics cards, a hierarchical structure based on perfect spatial hashing is proposed. Rendering of ADFs is done completely on GPUs, using a ray casting technique based on sphere tracing. Means to overcome the C0 and C1 discontinuities inherent to ADFs are suggested in order to attain smoothly shaded iso-surfaces. Finally, a new reconstruction method for ADFs, which can better represent curved surfaces, is proposed. Results are presented through simple interactive visualization applications, with ADFs generated from both triangle meshes and primitive solids.

[pt] Haeusler e Pequeno desenvolveram um método de prova de teoremas baseado em jogos semânticos introduzidos por Hintikka. Posteriormente Rios desenvolveu o programa PROGRAME que implementa este método. Este trabalho descreve um ambiente de programação lógica desenvolvido com a finalidade de oferecer ao usuário facilidades de programação lógica suportada pelo provador PROGRAME. O ambiente foi idealizado o mais próximo possível nos ambientes PROLOG, com a facilidade adicional de permitir que no código do programa a ele submetido sejam utilizados indiferentemente goals a serem provados neste ambiente ou PROGRAME. / [en] Haeusler and Pequeno developed a theorem proving method based on semântica games introduced by Hintikka. Later, Rios developed the program PROGRAME witch implements this method. Our work describes a logic programming environment developed with the aim of offering the user logic programming facilities supported by the PROGRAME prover. The programming environment was chosen to be PROLOG-like with additional facility of permiting that a given goal can b proved both by or environment and by the PROGRAME prover

[pt] A gerência de redes telefônicas nas modernas concessionáras do chamado Primeiro Mundo têm se apoiado, cada vez mais, sobre sistemas baseados em conhecimento. Esses sistemas inteligentes são apresentados como solução capaz de fazer face às exigências de qualidade e confiabilidade feitas pelos usuários ligados a redes, as quais crescem em dimensão e complexidade, num ritmo jamais visto. Este trabalho incursiona nesse campo e apresenta o projeto, seu desenvolvimento e a implementação, baseada na Programação em Lógica, de um sistema para auxílio à emissão de telecomandos sobre a Rede Nacional de Telefonia, operada pela EMBRATEL. Adicionalmente, apresentamos um levantamento das principais técnicas de obtenção e representação de conhecimento para fins de utilização em computadores eletrônicos. / [en] The management of telephone networks in developed countries hás been based, in a ever-growing scale, on knowledge-based systems. Those intelligent systems have been presented as a means to face the demands in quality and reliability posed by users of those networks, which have been expanding at an uncredibly fast pace. This paper tries to explore this area and presents the project, its development and implement based on Logic Programming, of a system for aiding the sending commands upon the National Telephone Network, operated by EMBRATEL. Additionally we have done a survey of the main techniques for the acquisition and representation of knowledge related to electronic computing