Orientador: Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-22T11:40:25Z (GMT). No. of bitstreams: 1 Macambira_ElderMagalhaes_M.pdf: 3883760 bytes, checksum: 901048c885d22ea3a00674f4c248ef9b (MD5) Previous issue date: 1997 / Resumo: Esta dissertação dá ênfase à abordagem poliedral para a resolução exata do Problema da Clique .Máxima com Peso nas Arestas. Dado um grafo completo não-dirigido Kn = (Vn, En), onde |Vn|= n, com um peso Cij associado a cada aresta (i,j) ? En, e um inteiro b, onde b = n; procuramos uma clique C em Kn cuja sorna dos pesos das arestas em C seja máxima e |C| = b. São apresentadas e discutidas diferentes formulações de programação linear inteira para o problema. Investigamos ainda a estrutura facial do poliedro associado ao problema realizando urna revisão bibliográfica das desigualdades conhecidas e introduzindo novas famílias de facetas. Por último, descrevemos os experimentos computacionais realizados com um algoritmo branch-and-cut e com urna metaheurística, ambos propostos neste trabalho. As maiores instâncias resolvidas de forma exata para este problema na literatura referem-se a grafos completos com no máximo 30 vértices. Neste trabalho, resolvemos exatamente instâncias para grafos com até 48 vértices e mostramos a força computacional para as novas desigualdades que introduzimos. / Abstract: Given a complete non-directed graph Kn = (Vn, En) on n nodes with weights on the edges and an integer b = n, we look for a clique C in Kn whose sum of the weights of the edges in e is maximum and such that |C| = b. We discuss on different integer programming formulations and investigate the facial structure of the polyhedron associated to the problem. New families of facet defining inequalities are introduced. Finally we describe our computational experiments with a branch-and-cut algorithm and a metaheuristic that we have proposed. The largest instances that are solved exactly in the literature refer to complete graphs with at most 30 nodes. In this work we solve to optimality instances for graphs with up to 48 nodes and we show the computational strength of the new inequalities we have introduced. / Mestrado / Mestre em Ciência da Computação

Orientadores: Luis Gimeno Latre, Maria Teresa Moreira Rodrigues / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-27T13:12:34Z (GMT). No. of bitstreams: 1 Rodrigues_LuizCarlosdeAbreu_D.pdf: 13439549 bytes, checksum: d1bf6cf4e43207b899cd4a6e1a44b3d4 (MD5) Previous issue date: 2000 / Resumo: O problema tratado é o planejamento e programação (scheduling) da produção em plantas operando em batelada. Considera-se a situação em que são produzidos diversos produtos finais (planta multiproduto) através de vários estágios de produção (operações), e os processadores são multipropósito, podendo ser utilizados por diversas operações. O objetivo é o estudo de problemas da indústria de processos e, para tanto, são consideradas as restrições de armazenagem típicas desta área. O problema considerado é o chamado de curto prazo, no qual o objetivo do planejamento e scheduling da produção é o atendimento de demandas específicas de produtos finais em termos de quantidades e prazos de entrega. A abordagem proposta é de dois níveis. O nível de planejamento utiliza como dados de entrada a demanda de produtos finais, a disponibilidade de matérias primas e a atribuição de operações a processadores. Através de procedimentos de explosão, determinase a quantidade de bateladas de cada operação que serão produzidas e a janela de tempo onde deverá ocorrer o processamento de cada batelada. Utilizam-se técnicas de propagação de restrições para analisar o carregamento induzido aos processadores e a factibilidade do plano de produção. O caráter interativo do sistema permite ao usuário modificar os dados de entrada para obter uma situação factível. O resultado do planejamento, na forma de janelas de tempo, é utilizado no scheduling para reduzir a dimensão do problema. Utilizam-se duas abordagens: uma abordagem de programação linear inteira mista (MILP) utilizando discretização uniforme do tempo e a técnica de simulated annealing. A formulação MILP utiliza intensivamente a informação dada pelas janelas de tempo, reduzindo a quantidade de variáveis binárias envolvidas e propõe-se uma formulação reduzida que explora as informações de carregamento dos processadores. O algoritmo de simulated annealing é acrescido de um processo de filtragem dos candidatos que elimina os candidatos infactíveis, dadas as restrições de ordenamento induzidas pelas janelas de tempo / Abstract: The problem focused in this thesis is the short term planning and scheduling of multipurpose batch plants. This is an important problem in the process industry and, because of that, intermediate storage limitations are explicitly considered. The main objective is to fulfill specific demands of final products, distributed along the horizon. It is proposed a two level approach: planning and scheduling. Product' s demands, raw material availability plan and operation/equipment assignment are the inputs to the planning level. At this level an exploding procedure is performed in order to determine the number of batches of each operation as well as their processing time windows. Constraint propagation techniques are used to analyze the plant loading and the production plan feasibility. The interactive nature of the proposed approach allows the user to change input data in order to define a feasible scenario. At the end of the planning level, a set of operations' time windows is released to the scheduling level. Two approaches have been implemented to schedule the operations inside their time windows: a MILP approach based on a uniform time discretization and a simulated annealing approach. The information given by the time windows is intensively used in the MILP formulation, reducing the number of binary variables in the problem. It is also proposed a reduced MILP model exploiting plant loading information. The simulated annealing algorithm implemented also uses the time windows information to eliminate infeasible candidates through a filtering procedure / Doutorado / Doutor em Engenharia Elétrica

Orientador : Paulo Sergio Franco Barbosa / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Civil / Made available in DSpace on 2018-07-29T03:59:27Z (GMT). No. of bitstreams: 1 Almeida_Rogeriode_M.pdf: 11863171 bytes, checksum: 98d35fba7240e5902936068a393d4e56 (MD5) Previous issue date: 2001 / Resumo: No presente trabalho foi proposto um modelo hidráulico de otimização em período extensivo, estruturado na forma clássica dos problemas de otimização determinística restrita. Este modelo é composto por duas partes essenciais: (a) função objetivo, que descreve o critério de performance do sistema; (b) conjunto de restrições composto por equações e/ou inequações matemáticas que definem a operação do sistema e de seus elementos. Devido à presença de variáveis binárias utilizadas para representar as condições operacionais das bombas, o modelo hidráulico de otimização é formulado como um problema de programação não-linear inteira mista. Para a solução do modelo proposto, foram utilizados dois algoritmos de programação nãolinear associados a um algoritmo de programação inteira. São eles: (a) o algoritmo do Gradiente Reduzido Generalizado (ABADIE e CARPENTIER, 1969) associado ao algoritmo Branch and Bound (Ramificação e Limite), através da interface do software GAMS com os solver CONOPT e SBB; (b) o algoritmo da Lagrangeana Projetada (MURTAGH e SAUNDERS, 1982) associado ao algoritmo Branch and Bound, através da interface do software GAMS com o solver MINOS 5.5 e SBB. O modelo inicialmente foi avaliado para a rede hipotética estudada por VENTURINI (1997), e depois para um sistema real, o Subsistema Adutor Metropolitano Alça Leste da cidade de São Paulo. Os resultados obtidos evidenciaram a viabilidade da utilização de tal metodologia como uma ferramenta valiosa de suporte para as tomadas de decisões operacionais em sistemas de abastecimento de água, permitindo um melhor entendimento das interações dos elementos que compõem o sistema e indicando a possibilitando de implementação para operações em tempo real / Mestrado / Recursos Hidricos / Mestre em Engenharia Civil

Orientador: Guido Costa Souza de Araujo / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-11T23:50:19Z (GMT). No. of bitstreams: 1 Rigo_Sandro_M.pdf: 11824282 bytes, checksum: ecebac4bbf8a89ce61520b66f5923a94 (MD5) Previous issue date: 2000 / Resumo: Gerenciamento de memória é uma tarefa muito importante para o bom desempenho de uma aplicação. Existem duas alternativas para a execução desta tarefa: gerenciamento explícito por parte do programador, ou a existência de um sistema dinâmico automático. O objetivo desse trabalho foi realizar experimentos de codificação e compactação do heap no sistema automático de gerenciamento de memória da máquina virtual Java, usando como plataforma a implementação desta conhecida como Kaffe. Na primeira parte deste trabalho, foi estudado um mecanismo alternativo de codificação dos objetos vivos, baseado em Binary Decision Diagrams (BDD). Na segunda etapa, foi projetado um coletor de lixo, cujo objetivo era avaliar o impacto da compactação do heap no desempenho da JVM. A implementação de nosso coletor se baseou no algoritmo conhecido como Mark-Compact. Obtivemos uma implementação híbrida para o sistema de recuperação de memória da máquina virtual Kaffe, capaz de realizar coletas utilizando ou não compactação. Esse sistema nos permite configurar a freqüência com que compactações são realizadas, permitindo ajustá-lo para diminuir o impacto causado por estas no desempenho do programa. Finalmente, mostramos nossas conclusões sobre os experimentos realizados e apontamos algumas possíveis melhorias a serem implementadas na máquina virtual kaffe, que visam aproveitar ao máximo os benefícios trazidos pela compactação. / Abstract: Memory management is an important task for good performance. There are two choices to accomplish this task: explicit management done by the programmer, or the presence of an automatic dynamic memory management system. The goal of this work was to perform experiments using codification and compaction on Java Virtual Machine's memory management system, using its implementation known as Kaffe. In the first part, we have studied an alternative system of live objects codification, based on Binary Decision Diagrams(BDD). In the second part, a garbage collector has been projected. Its main goal was to evaluate the impact on JVM's performance by adding a heap compaction system. The implementation of this collector was based on the Mark-Compact algorithm. We got a hybrid implementation for our garbage collection system, which is able to collect using or not using compaction. This system allows us to configure how often it performs heap compaction, adjusting it to minimize the impact on program performance. Finally, we show our conclusions about the experiments we have done and suggest some possible improvements to be implemented on Kaffe JVM, intending to take full advantage of the compaction benefits. / Mestrado / Mestre em Ciência da Computação

Orientador : Luiz Eduardo Buzato / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-01T02:39:02Z (GMT). No. of bitstreams: 1 Senra_RodrigoDiasArruda_M.pdf: 5692776 bytes, checksum: 1742fa697ada7ad703a7f170be9c32f7 (MD5) Previous issue date: 2001 / Resumo: Esta dissertação traz contribuições teóricas e práticas. No plano teórico, apresentamos uma unificação da terminologia de Reflexão Computacional, onde introduzimos o termo para-objeto. Após a compilação de uma série de critérios para se classificar protocolos de meta-objetos (MOPs), analisamos comparativamente os MOPs mais expressivos até o ano 2000 utilizando a terminologia e os critérios propostos por nós. Enfatizamos os MOPs implementados sobre a Máquina Virtual Java. Na fronteira entre o plano teórico e prático, analisamos detalhadamente o MOP de Gua raná, utilizando a terminologia e critérios propostos. O MOP de Guaraná é um protocolo de meta-objetos (MOP), idealizado por Alexandre Oliva, Luiz Eduardo Buzato e Islene Calciolari Garcia, que almeja simplicidade, flexibilidade, reuso de código de meta-nível e independência de linguagem de programação. Nesta dissertação também propomos um modelo de programação para o meta-nível. Segundo este modelo, enunciamos os problemas típicos na programação de meta-nível, a partir dos quais numeramos técnicas para contorná-los. No plano prático é descrita a implementação de GDK: Guaraná Development Kit, constituído por um conjunto de ferramentas que implementam as técnicas propostas e que auxiliam a programação de meta-nível. Entre os componentes do GDK, existem utilitários para depuração e composição de meta-objetos / Abstract: This dissertation brings theoretical and practical contributions. In the theoretical sphere, we propose a unified terminology for Computational Reflection, introducing the term para-object. Moreover, we have compiled cri teria to classify meta-object protocols (MOPs), which is used in a comparative analysis of the most expressive MOPs published till the year 2000. We give emphasis on those implemented on top of a Java Virtual Machine. In the frontier of both theoretical and practical spheres, we make a detailed analysis of the Guaraná MOP, in which we apply the same terminology and criteria that we have previously defined. The Guaraná MOP is a language independent meta-object protocol that aims at simplicity, flexibility and code reuse. It was conceived by Alexandre Oliva, Luiz Eduardo Buzato and Islene Calciolari Garcia. Besides, we propose a meta-programming conceptual model, in which meta-leveI programming issues are raised, and followed by the techniques to tackle them. In the practical sphere, we describe the implementation of GDK: Guaraná Development Kit, which consists of a set of tools that implement the proposed techniques and aid metaleveI programming. Amongst GDK's components, there are tools to aid debugging and meta-object composition / Mestrado / Mestre em Ciência da Computação

Orientador: Secundino Soares Filho / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-03T19:02:39Z (GMT). No. of bitstreams: 1 Siqueira_ThaisGamade_M.pdf: 973812 bytes, checksum: a0b3bf30f1b89f22a18b2cffa293dc7a (MD5) Previous issue date: 2003 / Mestrado

Orientador: Takaaki Ohishi / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-03T23:41:14Z (GMT). No. of bitstreams: 1 CumpaAurich_MariellaRenata_M.pdf: 3055727 bytes, checksum: 236b09429db6f95966e88ae62e642074 (MD5) Previous issue date: 2004 / Mestrado / Engenharia Eletrica / Mestre em Engenharia Elétrica

Orientador: Elnathan Chagas Ferreira / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica / Made available in DSpace on 2018-07-20T19:53:26Z (GMT). No. of bitstreams: 1 Sousa_AntonioHeronaldode_M.pdf: 6755137 bytes, checksum: c0c534a5d717e88561ed87d82d76898f (MD5) Previous issue date: 1995 / Resumo: o ONAGROéum sistema tradutor que reconhece uma linguagem gráfica de descrição de algoritmos e possibilita a geração de código em Assembly para microcontroladores. Além do tradutor propriamente dito, ele incorpora um editor gráfico para a entrada do programa-fonte, que se assemelha a um algoritmo descrito em linguagem de fluxogramas. Ele também possui um editor de identificadores que permite a descrição dos símbolos identificadores usados no programa. O sistema ONAGRO opera em ambiente Microsoft Windows, oferecendo uma interface amigável com o usuário. Esta interface baseia-se em estruturas gráficas: ícones, janelas, menus e diálogos que o usuário pode ativar através da utilização do mal/se ou, se preferir, do próprio teclado. O sistema foi desenvolvido para trabalhar em computadores compatíveis com o IBM-PC AT e foi implementado em linguagem Visual C++, usando metodologia orientada ao objeto. Diferentemente dos compiladores tradicionais, ele interage com o usuário através de diálogos logo na entrada das instruções, a fim de diminuir erros posteriores de compilação. Além disso, o ONAGRO permite uma maior rapidez na entrada do programa, pois ele é orientado a ícones e não a textos, como nas linguagens convencionais. A programação em ONAGRO é feita com um elevado nível de abstração dos detalhes de hardware. Entretanto, há mecanismos disponíveis para total controle das características fisicas das aplicações. Os testes realizados mostraram que o ambiente proposto é bastante intuitivo e amigável. A documentação dos programas é feita em tempo-real, visto que o próprio programa-fonte se constitui em uma ótima ferramenta de inspeção. Outro aspecto importante, observado nos testes, foi que o código gerado se mostrou relativamente compacto / Abstract: ONAGRO is a translation system that recognizes an algorithm description graphical language and allows the code generation in Assembly for microcontrollers. Besides, it incorporates a graphic editor for the source-program input that is similar to an algorithm described in flowchart language. ONAGRO has also an identifier editor that allows the identifier symboldescription used on the programo ONAGRO is a fully Microsoft Windows compatible software offering a friendly interface with user. This interface is based on graphical structures: icons, windows, menus and dialogues that the user might activate through the mouse or, if he wishes, through the keyboard. ONAGRO was developed to work on IBM-PC AT compatible computers. It was implementedin Visual C++ language by using object oriented methodology. Differently from the traditional compilers, it interacts with the user through the dialogues immediately in the instructions input to reduce later compiler errors. Besides, ONAGRO allows a major quickness in the program input since it is icon oriented and not text oriented like in the conventional languages. The ONAGRO programming is made with high level abstraction of the hardware details. However, there are available mechanisms for full control of physical characteristics applications. The accomplished tests showed that the proposed environment is very intuitive and friendly. The program documentation is made in real-time since the proper source-program is a good inspection too1. Another important aspect observed in the tests was that the generated code proved to be relatively compact / Mestrado / Mestre em Engenharia Elétrica

Orientadores: Mario Jino, Jose Carlos Maldonato / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica / Made available in DSpace on 2018-07-15T22:24:11Z (GMT). No. of bitstreams: 1 LeitaoJunior_PliniodeSa_M.pdf: 8961188 bytes, checksum: faab8704e2ed32132f9fc88097241a4f (MD5) Previous issue date: 1992 / Resumo: Neste trabalho são discutidos os aspectos de aplicação de teste estrutural baseado em análise de fluxo de dados em programas COBOL. Com esse propósito, uma ferramenta denominada POKE-TOOL [MAL89,CHA91b], que apóia a utilização dos critérios Potenciais Usos [MAL88, MAL91], foi configurada para a linguagem COBOL. São abordados: a caracterização de unidade em programas COBOL; a abstração das estruturas de controle que compõem essa linguagem; o fluxo de dados presente em programas COBOL; e aspectos referentes à Instrumentação de programas COBOL. A discussão ressalta a não trivialidade dessas tarefas: por exemplo, a inexistência de estrutura de bloco na linguagem COBOL dificulta a atividade de Instrumentação de código fonte. Como produto principal desta dissertação, a versão operacional da POKE-TOOL para a linguagem COBOL constitui uma contribuição importante no sentido de apoiar o teste estrutural de unidades escritas em linguagem COBOL / Abstract: This work explores the issues involved in applying data flow based structural testing in COBOL programs; a tool named POKE-TOOL [MAL89,CHA91b] that supports Potential Uses Criteria appllcation [MAL88, MAL91] was configured for the COBOL programming language. The following topics are discussed: characterization of units in COBOL; abstraction of control flow structures; data flow in COBOL and program instrumentation. The presentation points out that these tasks are non-trivial: for example, the lack of block structuring in COBOL makes difficult the instrumentation of source code. As the main product of this thesis, the operational version of the POKE-TOOL for COBOL language constitute an important contribution to structural testing of units implemented in COBOL / Mestrado / Mestre em Engenharia Elétrica

Orientador : Wagner C. Amaral / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica / Made available in DSpace on 2018-07-16T01:51:41Z (GMT). No. of bitstreams: 1 Ludwig_Artemio_D.pdf: 9026847 bytes, checksum: bf0003b28c02857c43931feb4b9729d1 (MD5) Previous issue date: 1992 / Resumo: A implementação de interpretadores para a linguagem da Lógica de Ordem Superior (LOS) constitui-se num desafio ainda não vencido. Pode-se dividi-Io em duas partes: (a) tornar a linguagem mais amigável permitindo estimular sua adoção e (b) dotar as implementações com um desempenho que não sacrifique sua usabilidade. A linguagem de programação para a LOS utiliza os conceitos do À-cálculo e os recursos de tipificação de Russel. Sua sintaxe é portanto mais complexa do que aquela da Lógica de Primeira Ordem (LPO). A técnica de derivação de algum conhecimento em uma base de conhecimento, formalizada conforme suas regras, assemelha-se com aquela da LPO que é chamada de resolução. Qualquer sistema de provas em LOS deve atender a restrições de uma linguagem fortemente tipada e a unificação, que apresenta problemas de incompletude, pode gerar mais do que um unificador. Isto torna a pesquisa nâ.o-determinística e faz com que a derivação contenha mais uma fonte de retroencadeamento, quando comparada com modelo de programação em LPO. Este trabalho expõe e analisa a implementação de um interpretador para a LOS sujeita a sentenças definidas positivas as quais contêm propriedades adequadas à mecanização semelhantes àquelas das cláusulas de HORN da LPO. Problemas de indecidibilidade são contornados e os vários aspectos computacionais são descritos como a formação da base de conhecimento, sua gramática e a P-derivação, que é o método de obtenção de provas sobre a base. Central a estes procedimentos encontra-se a unificação que apresenta complexidade elevada e cujo processamento é razão de depauperação na qualidade do sistema. Uma proposta de enfoque alternativa é oferecida com o propósito de atenuar os efeitos sobre a lentidão do sistema. O algoritmo resultante indica ganhos no desempenho e apresenta uma interpretação mais facilitada do mecanismo da unificação / Abstract: Efficient Interpreter implementations for Righer Order Logic (ROL) programming language still remain as a challenge that can be splitted into two classes: (a) to make the language friendlier in order to stimulate the user to adopt it, and (b) to provi de the interpreter with a performance that does not damage its usability. This paper resulted from an ROL interpreter prototypation, called À-PROLOG. Only the positive definite sentençes are used in the language. They are similar to those of the First Order Logic (FOL) programing language and present some apropriate mechanization properties. One kind of implementation is discribed and its computational aspects are analysed. They include the knowledgernent base formation, the grarnrnar of the sentences and the P-derivation, which is the method of deriving proofs over the base. The unification is the most important interpreter procedure and has high complexity. Its processing is one of the reazons for the depaupering of system quality. In this paper the analisies of the MATCR and SIMPL algorithms that were developed for this purpose are used to supply a new unification algorithm which, in contrast to MATCR, shows initial performance gains and an easier procedural interpretation oí the unification mechanism / Doutorado / Automação / Doutor em Engenharia Elétrica