Orientador: Gabriela Stangenhaus / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-07-22T04:02:22Z (GMT). No. of bitstreams: 1 Machado_HelymardaCosta_M.pdf: 4843890 bytes, checksum: d92608cb421a49bc3a9b5850b381092c (MD5) Previous issue date: 1997 / Resumo: As técnicas de diagnóstico para detecção de dados atípicos comumente utilizadas na análise de regressão linear têm por base o método de estimação dos mínimos quadrados dos resíduos. No entanto, se no conjunto de dados houver observações atípicas, estas obsetVações influenciarão o ajuste, afetando o estimador obtido por esse método. Quando isto OCOITe, pode haver efeitos de maceramento (isto é, não se detectam as observações atipicas, ou seja, aquelas que se distanciam das demais) e/ou "swamping" (isto é, c1assifica se como atípica uma observação comum). Neste traba1ho são abordados métodos de estimação com alto ponto de ruptura, ou seja, métodos cujos esticadores não são afetados quando houver observações atípicas no conjunto de dados. Como alternativa para o método dos mínimos quadrados dos resíduos são abordados mais deta1hadamente o método da mínima mediana dos quadrados dos resíduos e o método dos quadrados aparados mínimos. As técnicas de diagnóstico baoadas em tais métodos são resistentes a dados atípicos, conseguindo identificá-los. Para obtenção de uma solução para os estimadores dos métodos de estimação resistentes às observações atípicas utilizam-se algoritmos que se baseiam nos chamado conjuntos elementares, que consistem de subconjuntos das observações do conjunto de dados. Assim, são apresentados vários algoritmos baseados nos conjuntos elementares, sendo que alguns algori1mos consistem na enumeração completa ou parcial (através de uma amostra aleatória) de todos os possíveis conjuntos elementares, enquanto que outros são resolvidos através de programação linear. / Abstract: Not informed. / Mestrado / Mestre em Estatística

Orientador: Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-22T19:24:02Z (GMT). No. of bitstreams: 1 Meneses_ClaudioNogueirade_M.pdf: 3238026 bytes, checksum: bd3af0337218ec84f17c26c345abf4f8 (MD5) Previous issue date: 1997 / Resumo: Dado um retângulo R e um conjunto finito não vazio P de pontos no interior de R, estudamos o problema de particionar R em retângulos menores tal que nenhum ponto em P está no interior de qualquer retângulo da partição. O objetivo é minimizar a soma dos comprimentos dos segmentos de reta definindo a partição. Este problema é NP-difícil e uma generalização deste tem aplicação em projeto de circuitos VLSI. Neste trabalho implementamos os principais algoritmos de aproximação que têm sido propostos para este problema e propomos dois diferentes modelos de programação linear inteira. No primeiro modelo, onde variáveis são associadas a segmentos de reta, fazemos uma investigação do poliedro associado ao problema. Inequações lineares definindo facets são apresentadas e resultados computacionais para um algoritmo Branch-and-Cut baseado nestas inequações são reportados. O segundo modelo é baseado em uma redução do problema em questão para o problema set partitioning. Um algoritmo Branch-and-Price para este modelo foi implementando e os resultados são comparados com aqueles obtidos pelo algoritmo Branch-and-Cut. Os experimentos computacionais realizados mostraram a viabilidade da resolução exata deste problema através de técnicas de programação linear inteira, pelo menos para instâncias de médio porte (|P| = 200). / Abstract: Given a rectangle R in the plane and a non empty finite set P of points in the interior of R, we study the problem of partitioning R into smaller rectangles such that no point in P is interior to any rectangle of the partition. The goal is to minimize the sum of the lengths of the straight line segments defining the partition. This problem is NP-hard and a generalization of it have application in VLSI design. In this work we implement the main approximation algorithms that have been proposed for this problem and propose two different integer programming models. In the first one, the variables are associated to line segments and we investigate the polyhedron associated to this model. Facet defining inequalities are presented and computational results obtained by a Branch-and-Cut algorithm based on these inequalities are reported. The second model is based on a Set Partitioning formulation. A Branch-and-Price algorithm for this model has been implemented and the results are compared with those obtained by the Branch-and-Cut algorithm. The computational results show that, at least for medium sized instances (IPI = 200), the problem can be solved exactly using Integer Programming techniques. / Mestrado / Mestre em Ciência da Computação

Orientadores: Pedro Sergio de Souza, Marcus Vinicius Poggi de Aragão / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-22T21:33:18Z (GMT). No. of bitstreams: 1 Haddad_ElaineGaspareto_M.pdf: 1752527 bytes, checksum: 6ecf36f9a07b62f0718f185c0fd4ca43 (MD5) Previous issue date: 1997 / Resumo: Este trabalho aborda o problema de seqüenciamento de tarefas conhecido como Job Shop Scheduling Problem (JSP). O objetivo aqui é mostrar a adequação de uma técnica conhecida como Times Assíncronos (A-Teams), para resolver este problema de otimização combinatória, que é bastante freqüente em ambientes industriais. Esta abordagem tem sido aplicada com sucesso na resolução de outros problemas, como o Traveling Salesman Problem, o Flow-Shop Problem e até mesmo o próprio Job Shop Problem sob uma abordagem de heurísticas de construção. Esta técnica está baseada na cooperação de algoritmos heurísticos no sentido de obter soluções, possivelmente, melhores que aquelas obtidas quando os mesmos algoritmos são executados isoladamente. Neste trabalho, o enfoque é dado a heurísticas de melhoria. Outros tipos de algorit­mos foram desenvolvidos para compor os A-Teams. Estes A-Teams desenvolvidos foram acoplados a um outro já existente, baseado em heurísticas de construção. Algumas instâncias de JSP foram testadas e os resultados obtidos atestam a adequação desta técnica para a resolução deste problema. / Abstract: This work treats the sequencing of tasks problem known as Job Shop Scheduling Problem. The goal here is to show the adequability of a technique known as Assynchronous Teams (A-Teams) to solve this optimization problem which is used in industrial environments. This approach has been applied successfully in the solving of other problems such as the Traveling Salesman Problem, Flow Shop Problem and the Job Shop Problem itself using construction heuristics algorithms. This technique is based on the cooperation of some heuristics algorithms in order to obtain solutions, possibly better then ones obtained when same algorithms are working alone. In this work, the focus is on the development of improvement heuristics algorithms. Another type of algorithms were also developed to form the A-Teams. These A-Teams developed were joined to another one, based in construction heuristics. Some instances of the JSP were tested and the results obtained show the adequability oí this technique to solve this problem. / Mestrado / Mestre em Ciência da Computação

Orientador: Pedro Jussieu de Rezende / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-23T09:53:10Z (GMT). No. of bitstreams: 1 Pinto_GuilhermeAlbuquerque_M.pdf: 5255697 bytes, checksum: 2472502cd1a3a5e723109ff1ab4c7029 (MD5) Previous issue date: 1998 / Resumo: Esta dissertação discute diagramas de Voronoi no plano projetivo orientado, um espaço geométrico que propicia vantagens computacionais tanto na representação quanto na construção dos diagramas. Esses diagramas, resumidamente, agregam informação de proximidade para um conjunto de objetos no espaço e estão entre as estruturas mais estudadas na Geometria Computacional com aplicações em diversas ciências. Apresentamos um algoritmo incremental simples, baseado somente no conceito de orientação, para construir o diagrama de pontos e, também, o de pontos com peso aditivo. Esse último e algumas outras generalizações do diagrama de Voronoi possuem arcos de cônicas entre suas arestas. Para obter a visualização dos diagramas, estudamos as cônicas naquele espaço e propomos uma representação para arcos que unifica as três classes de cônicas afins no plano. O trabalho se. completa com a implementação do algoritmo e o aprimoramento de dois visualizadores para os modelos plano e esférico do plano projetivo orientado, com a inclusão de cônicas, que permite a completa visualização dos diagramas / Abstract: This dissertation discusses Voronoi diagrams on the oriented projective plane, a geometric space which gives computational advantages in the representation as well as in the construction of the diagrams. These diagrams, in short, aggregate proximity information for a set of objects in the space and are among the best studied structures in Computational Geometry with applications in several sciences. We present a simple incremental algorithm, based only on the concept of orientation, to construct the diagram of points and, also, the additively weighted diagram. The latter and some other generalizations of the Voronoi diagram include conic arcs among their edges. To achieve the visualization of the diagrams, we study the conics in that space and propose a representation for arcs that unifies the three classes of affine conics in the plane. The work also includes the implementation of the algorithm and the update of two visualizers for the planar and spherical models of the oriented projective 'plane, in order to include conics, that allow for the complete visualization of the diagrams and the advantages of this geometric space / Mestrado / Mestre em Ciência da Computação

Orientador: Ricardo de Oliveira Anido / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-23T12:48:27Z (GMT). No. of bitstreams: 1 Alencar_JuceleFrancade_M.pdf: 2124677 bytes, checksum: c1e3777a3b380e70fde130d4c0a089d4 (MD5) Previous issue date: 1998 / Resumo: A principal característica de sistemas distribuídos é permitir que vários computadores, situados em diferentes localizações, trabalhem em conjunto para a realização de uma tarefa, possibilitando o compartilhamento de recursos e a distribuição dos serviços. No entanto, devido à dificuldade de se obter uma consistência global do sistema, o desenvolvimento de algoritmos distribuídos torna-se uma tarefa bastante complexa. Visando facilitar o controle, algoritmos distribuídos necessitam, muitas vezes, de um processador que exerça uma função diferenciada dos demais numa dada aplicação. Este processador é normalmente chamado de coordenador ou líder, e o problema de eleição de líder consiste em criar um algoritmo distribuído para uma dada rede de processadores tal que, ao terminar a execução deste algoritmo um, e apenas um, dos processadores seja designado líder. Esta dissertação apresenta um survey englobando as principais soluções para o problema de eleição de líder, analisando suas complexidades de mensagens e tempo e buscando uma classificação de modo a agrupar os algoritmos baseando-se no modelo do sistema e no princípio básico usado no desenvolvimento dos mesmos. / Abstract: The main feature of a distributed system is to allow many computers, at different locations, to work together performing a common task, making the sharing of resources and the distribution of services possible. However, due to the difficulty of acquiring a global view of the system, the development of distributed algorithms is very complex. Several distributed applications make use of a distinguished processor to execute some special task. This processor generally is called coordinator or leader; the leader election problem consists of finding a distributed algorithm for a given network such that, at the end of the execution, only one processor has been declared leader. This dissertation presents, a survey of the main algorithms for the leader election problem, analyzing their message and time complexities and attempting to classify the algorithms according to the system model and the basic principle used in their development. / Mestrado / Mestre em Ciência da Computação

Orientador: Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-23T12:26:09Z (GMT). No. of bitstreams: 1 Nunes_AminadabPereira_M.pdf: 3033083 bytes, checksum: 00558771e9828bf4eaf6bf7d04026453 (MD5) Previous issue date: 1997 / Resumo: Seja P um conjunto finito de pontos no plano e S(P) o conjunto de todos os segmentos de reta com extremos em P. Uma triangulação planar de P é um subconjunto maximal de S(P) tal que nenhum par de segmentos neste subconjunto se intercepta, exceto possivelmente nos extremos. Chamamos de triangulação de custo mínimo a triangulação planar cuja soma total dos comprimentos de seus segmentos de reta é mínimo dentre todas as triangulações planares de P. Não se conhece algoritmo polinomial que resolva o problema de determinar a triangulação de custo mínimo de um conjunto de pontos no caso geral, contudo, também não está provado tratar-se de um problema NP-difícil. Neste trabalho estamos interessados na resolução exata deste problema. Nossa abordagem é baseada em técnicas de programação inteira, em particular estudamos duas formulações distintas para o problema. A primeira formulação é baseada em uma equivalência entre o problema da triangulação de custo mínimo e uma versão restrita do problema do conjunto independente em um grafo. Além das desigualdades obtidas através da observação desta equivalência, mostramos como fortalecer a formulação através de certas propriedades geométricas do problema. Estudamos ainda uma outra formulação baseada principalmente no trabalho apresentado por Loera et. al em [dLHSS96]. Enquanto na primeira formulação as variáveis binárias estão associadas aos segmentos em S(P), nesta segunda formulação as variáveis binárias estão associadas aos triângulos com vértices em P. Os resultados computacionais que obtivemos mostram uma clara superioridade do segundo modelo. Para a primeira formulação implementamos um algoritmo branch-and-cut que nos permitiu resolver problemas de até 160 pontos (|P| = 160). Já para a segunda formulação a solução ótima da relaxação linear sempre foi inteira, o que nos permitiu resolver instâncias com até 1000 pontos (|P| = 1000) / Abstract: Let P be a finite set of points in the plane and S(P) be the set of all segments with both extreme points in P. A planar triangulation of P is a maxirnal subset of S(P) such that no pair of segments is this subset intercept each other, except possibly at their extremities. A minimum triangulation of P is a planar triangulation whose sum of the lengths of all its segments is minimum over all possible triangulations of P. No polynomial algorithm is known that solves this problem in the general case, however it is also not known if the problem is NP-hard. In this work we are interested in solving the problem exactly. Our approach is based on integer programming techniques and is particular we have studied two different formulations for the problem. The first formulation is based on an equivalence between the problem of finding a minimum weight triangulation of P and a restricted version of the maximum independent set of a graph. Besides the inequalities arising from this observation, we show how to strength the formulation by using geometric properties if the problem. We also have studied a second formulation mainly based on the work of Loera et. al [dLHSS96]. While in the first formulation the binary variables are associated to the segments in S(P), in this second formulation the binary variables are associated to the triangles with vertices lying in P. Our computational results have shown that the second model clearly outperforms the first one. For the first formulation, we have implemented a branch-and-cut algorithm which allowed us to solve instances with up to 160 points (IPI = 160). On the other hand, for the for second formulation, the optimal solution of the linear relaxation was integer for all tested instances, which has made possible the solution of instances with up to 1000 points (IPI = 1000] / Mestrado / Mestre em Ciência da Computação

Orientador: Ricardo de Oliveira Anido / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-23T17:02:31Z (GMT). No. of bitstreams: 1 Craveiro_GiseledaSilva_M.pdf: 4309633 bytes, checksum: 221da7db8cdd6ce3e8ae00b42aaad9cb (MD5) Previous issue date: 1998 / Resumo: Elaborar uma solução para um problema distribuído que atenda aos critérios de segurança e progresso está muito longe de ser uma tarefa trivial. Nem mesmo algoritmos publicados escaparam de contestação posterior, mostrando que são incorretos. Com o objetivo de encontrar uma modelagem mais adequada, alguns pesquisadores tomam a direção das derivações. Verificando comportamentos similares e características comuns, pretende-se desenvolver um método que facilite o projeto de algoritmos distribuídos para resolver problemas que apresentem algumas similaridades. Uma característica muito importante comum a certos problemas é a propriedade da estabilidade, isto é, se o problema ocorre, ele persistirá até que seja detectado e tratado. Assim acontece com deadlocks e quando uma computação distribuída alcança o término de sua atividade. Esta dissertação concentra-se nos seguintes pontos. Do estudo das áreas de deadlock e terminação distribuídos resulta a apresentação da modelagem de cada problema, uma visão em largura das abordagens propostas para a detecção do deadlock distribuído e para a detecção da terminação distribuída e a discussão mais detalhada de alguns algoritmos propostos para esses dois problemas. Às contribuições citadas soma-se a proposição de um método que derive soluções para o problema da terminação distribuída a partir de algoritmos para a detecção do deadlock, preservando as propriedades de segurança e progresso da solução base / Abstract: Devising a solution to a distributed problem, satisfying the requirements of progress and safety is clearly not an easy task. Several published algorithms have been shown incorrect, despite having been "proven" correct at time of publication. An interesting approach to devise a new solution to a problem is to use a known solution to a different problem that has similar requirements and characteristics. In this dissertation we present a methodology to derive solutions to the problem of detecting the termination of a distributed computation based on solutions to the deadlock problem. A common characteristic of these problems is that both are persistent: once attained the condition of deadlock or termination, the condition will hold thereafter, until some external action is taken. Besides presenting the derivation methodology, this dissertation presents a broad study of the more interesting solutions to the deadlock and termination problems found in the literature / Mestrado / Mestre em Ciência da Computação

Orientador: João Meidanis / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-26T09:21:57Z (GMT). No. of bitstreams: 1 Walter_MariaEmiliaMachadoTelles_D.pdf: 18591224 bytes, checksum: ee2c0868f8c73b0bd0e5a28a8cdc1faa (MD5) Previous issue date: 1999 / Resumo: Não informado. / Abstract: Not informed. / Doutorado / Doutor em Ciência da Computação

Orientador: Pedro J. de Rezende / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-27T11:37:24Z (GMT). No. of bitstreams: 1 Harada_MarioMassato_D.pdf: 3022260 bytes, checksum: d986f7b618ffda2df880a2454f96cc07 (MD5) Previous issue date: 2000 / Doutorado / Doutor em Ciência da Computação

Orientador: Fernando Jose Von Zuben / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-27T14:40:22Z (GMT). No. of bitstreams: 1 Concilio_Ricardo_M.pdf: 737536 bytes, checksum: 5441616b9c4ae6811ba5702168cd2c7e (MD5) Previous issue date: 2000 / Mestrado