Resumo: As árvores binárias são estruturas de dados utilizadas tradicionalmente para a realização de pesquisa de forma eficiente sobre um conjunto de dados. Uma árvore pode atingir grandes dimensões, bem como ser utilizada para armazenar dados em memória secundária ou distribuídos pelos nodos de uma rede de computadores. Nestes casos, é necessário definir uma estratégia eficiente para o acesso aos dados da árvore, que são organizados em páginas. Uma página é utilizada para a transferência de dados em blocos da memória secundária para a primária, além do acesso remoto em redes de computadores, por intermédio de pacotes que possuem tamanho máximo pré-fíxado. Este trabalho apresenta um algoritmo para a paginação de árvores binárias de pesquisa aplicável quando o conjunto de informações é estático, as freqüências de acesso não são conhecidas e o armazenamento é remoto ou secundário. O algoritmo visa reduzir o tempo de pesquisa aos dados armazenados na árvore binária em termos do número de páginas visitadas e do aumento da taxa de preenchimento das páginas utilizadas. Uma versão alternativa do algoritmo que visa reduzir a distância internodal nas páginas é apresentada. Observou-se que o algoritmo proposto constrói a paginação ótima quando possível, isto é, quando a árvore é completa e o número de nodos é múltiplo do tamanho da página. Além disso, propõe-se uma política eficiente para o preenchimento das páginas de uma árvore binária degenerada tendo por base a aplicação de empacotamento unidimensional na franja da árvore. A complexidade computacional do algoritmo, que depende do empacotamento unidimensional a ser utilizado, é discutida e apresentada. O algoritmo foi implementado e resultados experimentais quanto ao número de páginas visitadas e à taxa de preenchimento das páginas utilizadas, comparativos com a paginação seqüencial, valores ótimos teóricos e as árvores B, são descritos e analisados. Comparando o algoritmo proposto com as árvores B, enquanto o número de paginas visitadas por pesquisa é similar em ambas as abordagens, a taxa de preenchimento das páginas produzida pelo algoritmo proposto é mais de 30% superior à taxa obtida pelas árvores B.

Submitted by Etelvina Domingos (etelvina.domingos@ufpe.br) on 2015-03-13T18:57:23Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Dissertacao_Fernanda_Lopes_Sa_Barreto.pdf: 2018119 bytes, checksum: a91a2aab3def045fd37ec12c580ccd91 (MD5) / Made available in DSpace on 2015-03-13T18:57:23Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Dissertacao_Fernanda_Lopes_Sa_Barreto.pdf: 2018119 bytes, checksum: a91a2aab3def045fd37ec12c580ccd91 (MD5) Previous issue date: 2012 / CAPES / Neste estudo investigou-se a influência de diferentes tipos de representações simbólicas na resolução de problemas combinatórios por alunos da Educação de Jovens e Adultos. Participaram da pesquisa 24 alunos, que pertenciam a turmas com equivalência ao quarto e quinto anos do Ensino Fundamental regular. Os alunos foram separados em três grupos: Grupo 1 – resolveu metade dos problemas usando listagens e a outra metade usando árvores de possibilidades; Grupo 2 – resolveu todos os problemas com árvores de possibilidades; e Grupo 3 – resolveu todos os problemas usando listagens. Os procedimentos metodológicos realizados foram: pré-teste, intervenção e pós-teste. Ambos os testes foram compostos por oito situações-problema contendo os diferentes significados da Combinatória que estão presentes na organização proposta por Pessoa e Borba (2009). Na intervenção foram resolvidos os problemas do pré-teste, sendo que em cada grupo foram usadas formas de representação simbólica distintas. Na análise do pré-teste verificou-se que a maioria das respostas não apresentou relação combinatória, evidenciando dificuldades dos estudantes na resolução de problemas que envolvem o raciocínio combinatório. Entre as representações simbólicas, a listagem foi a mais utilizada. Durante a intervenção buscou-se, por intermédio de listagens e/ou árvores de possibilidades, chamar a atenção dos participantes para as propriedades invariantes do conceito, referentes à escolha de elementos, à ordenação dos mesmos e ao esgotamento de possibilidades. Os dados do pós-teste mostraram que houve avanço significativo no desempenho dos participantes e que os grupos progrediram de modo idêntico. Foram identificados tipos de resposta que apontaram um maior nível de compreensão dos estudantes. A listagem foi a representação simbólica mais usada no pós-teste em todos os grupos, inclusive naquele que não fez uso de tal representação na intervenção. O estudo ressalta a importância de trabalhos sistematizados que abordem as dimensões conceituais propostas por Vergnaud (1986): situações e seus significados, propriedades/relações invariantes e representações simbólicas. Representações simbólicas passam a ser mais bem estruturadas à medida que estudantes possuem uma melhor compreensão das propriedades dos conceitos, estabelecendo diferenças entre significados envolvidos nas situações.

Submitted by Fabio Sobreira Campos da Costa (fabio.sobreira@ufpe.br) on 2016-01-18T12:02:47Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) DEUSEFIEL712 (3).pdf: 2390362 bytes, checksum: b141346cf6fe21fbbc6f119bfe41bc4e (MD5) / Made available in DSpace on 2016-01-18T12:02:47Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) DEUSEFIEL712 (3).pdf: 2390362 bytes, checksum: b141346cf6fe21fbbc6f119bfe41bc4e (MD5) Previous issue date: 2015-05-21 / O presente estudo buscou analisar o domínio conceitual de professores sobre os invariantes de problemas combinatórios a partir da elaboração de problemas e teve como objetivos específicos: identificar dificuldades e possibilidades de professores ao elaborarem problemas envolvendo o raciocínio combinatório e verificar se os professores aplicam os invariantes presentes nos problemas de permutação, arranjo, combinação e produto cartesiano. Como aporte teórico utilizamos a Teoria dos Campos Conceituais, defendida por Vergnaud e o domínio dos conhecimentos necessários ao professor de Matemática, segundo Ball, Thames e Phelps. Participaram desse estudo sete professores licenciados em Matemática, que lecionam na rede Estadual de Pernambuco. Os professores responderam individualmente uma entrevista semiestruturada que foi audiogravada e durou em média 80 minutos. Na entrevista solicitamos informações para traçarmos o perfil dos professores, pedimos que os mesmos elaborassem problemas a partir das situações de cada tipo de problema combinatório e a partir dos invariantes do conceito. Buscamos, a partir dos problemas elaborados, informações sobre os conhecimentos dos professores em relação ao ensino, à aprendizagem, ao currículo e solicitamos que eles transformassem um tipo de problema em outro. Em relação à análise do perfil, foi evidenciado que todos participaram de cursos de formação continuada, tais como Especialização ou Mestrado, porém este aspecto não influenciou para que houvesse uma equivalência nos acertos, ou seja, as dificuldades e possibilidades apresentadas pelos docentes parecem não ter relação com o tipo de curso na formação continuada. Quanto ao processo de elaboração de problemas combinatórios, os professores elaboraram corretamente mais a partir das situações do que dos invariantes do conceito, exceto nos problemas de combinação. Parece-nos que os invariantes do conceito apresentados não foram suficientemente claros para a elaboração de problemas combinatórios, pois alguns professores fizeram relação com conceitos diferentes da Combinatória. Além disso, percebemos que os problemas elaborados são parecidos com os encontrados nos livros didáticos. Tiveram também dificuldade em diferenciar os invariantes de ordenação e escolha de elementos, de contextualizar e de estruturar os problemas combinatórios. Os problemas de permutação e arranjo foram o que os professores mais elaboraram corretamente, seguidos de combinação e produto cartesiano. Em relação aos conhecimentos dos professores sobre as semelhanças entre os problemas, constatamos que alguns indicaram serem problemas de contagem, conjuntos e subconjuntos, agrupamento e multiplicação. Sobre as diferenças, indicaram as particularidades, a forma de agrupar os elementos, de estrutura de cada tipo de problema e a ordenação e repetição de elementos. Quanto ao conhecimento relacionado ao currículo, a maioria dos professores reconheceu o 2º ano do Ensino Médio como ano oficial para trabalhar a Combinatória, mas também indicaram que o raciocínio combinatório pode ser trabalhado nos anos iniciais e finais do Ensino Fundamental. Indicaram que elaborar problemas combinatórios é mais difícil do que resolver, devido aos aspectos conceituais e pedagógicos, apenas um participante discordou. Evidenciaram que nos problemas combinatórios os alunos deveriam saber: interpretar, perceber as particularidades de cada tipo de problema e saber usar a fórmula adequada. Por fim, ao refletirmos sobre as transformações, ficou evidente que os professores que tiveram dificuldade de elaborar as transformações de problemas combinatórios foram os que não perceberam os invariantes do conceito e as particularidades de cada tipo de problema. Concluímos que o processo de elaboração de problemas combinatórios ajuda o professor a refletir sobre os conceitos envolvidos nas diferentes situações relacionadas à Combinatória, sobre os aspectos pedagógicos e a respeito do currículo. / The present study analyzed the conceptual domain of teachers about the invariants of combinatorial problems from the elaboration of problems and had as specific objectives: identify difficulties and possibilities of teachers when elaborating problems involving combinatory thinking and verify if the teachers apply the invariants present on the problems of permutation, arrangement, combination and cartesian product. We used the Theory of Conceptual Fields as a theoretical basis, defended by Vergnaud and the domain of the concepts needed by the Mathematics teacher, according to Ball, Thames and Phelps. Seven teachers with a degree in Mathematics who teach at the State School System of Pernambuco participated on this study. The teachers answered to an individual semi-structured interview that was audio recorded and lasted around 80 minutes. In the interview we requested informations to trace the profile of the teachers and asked them to elaborate problems from the situations of each combinatorial problem and from the invariants of the concept. We sought, from the elaborated problems, informations on the knowledge of the teachers regarding teaching, learning, curriculum, and asked them to transform a type of problem into another. When it comes to the analysis of the profiles, we noticed that all of them participated in continuous training courses, such as Specialization or Master’s, however, this feature did not influence for there to be an equivalence of the hits, that is, difficulties and possibilities presented by the teachers did not seem to be related to the course taken during the continuous training. Regarding the process of elaborating combinatorial problems, teachers elaborated more correctly from situations than from the invariants of the concept, except on the combinatorial problems. It seems that the invariants of the concept presented were not clear enough to elaborate combinatorial problems, because some teachers related it to different concepts of Combinatorics. Besides, we also noticed the elaborated problems look like those found in didactical books. They also found it difficult to differentiate the invariants from ordering and element choice, from contextualizing and structuring combinatorial problems. Permutation and arrangement problems were the ones the teachers elaborated more correctly, followed by combination and cartesian product. About the knowledge of the teachers regarding the similarities between the problems, we found that some indicated to be counting, sets and subsets, grouping and multiplication problems. About the differences, they pointed out the particularities, the way of grouping the elements, the structure of each type, the order and repetition of elements. When it comes to the knowledge related to the curriculum, most of the teachers recognized the 2nd year of the High School as the official year to work Combinatorics, but they also indicated that combinatorial thinking can be worked in the initial and final years of Elementary School. They also indicated that elaborating combinatorial problems is harder than solving them, due to the conceptual and pedagogical features; only a participant disagreed. They highlighted that on the combinatorial problems students must know: interpret, notice the particularities of each kind of problem and how to use the proper formula. Finally, when thinking about the changes, it became clear that teachers who had difficult in elaborating the transformations of combinatorial problems were those who did not notice the invariants of the concept and the particularities of each type of problem. We concluded that the elaboration process of combinatorial problems helps the teacher to think about the concepts involved in the different situations related to Combinatorics, about the pedagogical features and about the curriculum.

Orientador: João Carlos Setubal / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da ComputaçãO / Made available in DSpace on 2018-07-21T05:57:00Z (GMT). No. of bitstreams: 1 Cruz_CarlosFernandoBella_M.pdf: 2090300 bytes, checksum: c7ddb8099b731928143e26f66c270afc (MD5) Previous issue date: 1996 / Resumo: Abordamos os principais algoritmos para o problema de emparelhamento máximo em grafos genéricos e desenvolvemos uma implementação paralela eficiente na prática, baseada no algoritmo seqüencial de Edmonds. Por prática entendemos uma implementação eficiente num multiprocessador de memória com partilhada. A implementação consiste em permitir que cada processador procure caminhos aumentantes no grafo de forma assíncrona e independente dos demais. Embora a busca ocorra de forma paralela, o aumento do emparelhamento é feito por somente 1 processador por vez, o que garante a corretude do algoritmo sem incorrrer em atraso significativo no tempo de execução. O desenvolvimento da implementação teve como antecedente uma experiência negativa de paralelização baseada no algoritmo de Micali e Vazirani. / Abstract: In this work we present the most important matching algorithms for general graphs and develop an efficient parallel implementation in practice based on Edmonds'matching algorithm. By practice we mean an efficient implementation on a shared memory multiprocessor. The implementation allows each processor to find augmenting paths assinchronously and independently of each other. Each matching augmentation is done by only one processor, and this makes the algorithm correct without causing significant delay in the execution time, in practice. The development of this implementation was made after a nega tive experience of paralelization based on the sequential algorithm of Micali and Vazirani. / Mestrado / Mestre em Ciência da Computação

Orientador: Jose Carlos de Souza Kuhl / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Científica / Made available in DSpace on 2018-07-21T06:32:26Z (GMT). No. of bitstreams: 1 Mandolesi_AndreLuisGodinho_M.pdf: 916932 bytes, checksum: 4084536e3bb119fcc98ed699188e3f8e (MD5) Previous issue date: 1996 / Resumo: Não informado / Abstract: Not informed / Mestrado / Mestre em Matemática

Orientador: Marcus Vinicius S. Poggi de Aragão / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação / Made available in DSpace on 2018-07-21T10:33:41Z (GMT). No. of bitstreams: 1 Longo_HumbertoJose_M.pdf: 2296998 bytes, checksum: cb6cef9a3b19187ee26dc91e8fe15b17 (MD5) Previous issue date: 1995 / Resumo: Esta dissertação tem como tema central o Problema de Recobrimento de um Conjunto (SCP - Set Covering Problem). O objetivo principal é a proposta de uma nova abordagem para sua resolução, mais precisamente, este objetivo visa o desenvolvimento de um método heurístico, multi-algorítmico, baseado no paradigma de Times Assíncronos. Um segundo objetivo desta dissertação, e de grande importância na funda­mentação do método ora proposto, é um estudo das principais características estruturais do problema; de sua formulação como um problema de programação linear inteira 0-1 e dos principais métodos computacionais (heurísticos e exatos) atualmente disponíveis para sua resolução. Times Assíncronos são organizações de software que visam a interação efici­ente entre vários algoritmos, para a resolução de problemas adequados à aborda­gem multi-algorítmica. A arquitetura proposta utiliza métodos aproximados para a resolução do SCP e do dual da relaxação linear do mesmo. Esta abordagem primal-dual permite garantir que a melhor solução encontrada esteja a um certo percentual da solução ótima, ou mesmo, eventualmente, provar a otimalidade da solução. Segundo este enfoque, os principais componentes da arquitetura proposta são algoritmos gulosos e de consenso, procedimentos de busca tabu, métodos de otimização por subgradientes e geradores de planos de corte. Os principais métodos exatos para a resolução do SCP são baseados em metodologias enumerativas. A maioria desses métodos combina ao esquema de enumeração diversas das técnicas heurísticas utilizadas na arquitetura aqui proposta. Contudo, esses métodos apresentam desempenho insatisfatório para algu­mas classes de instâncias, por não obterem boas soluções em um limite razoável de tempo. A arquitetura proposta foi aplicada a instâncias dessas classes de difícil reso­lução. Os resultados obtidos mostraram que é possível alcançar, com um esforço computacional aceitável, resultados no mínimo comparáveis aos dos melhores algoritmos para o SCP / Abstract: The development of an Asynchronous Team Method for heuristic resolution of the Set Covering Problem (SCP) is the main focus of this dissertation. Asynch­ronous Teams are software organizations that aim to efficient interaction among several algorithms for the resolution of problems that fit in a multi-algorithm approach. Another goal of this work is an extensive study of the SCP which covers: the SCP structures its formulation as a 0-1 ILP; and the description of the main heuristic and exact methods currently available for its resolution. This study is most1y required since we are concerned with the development of a multi-algorithm method. The resulting software architecture makes use of approximate algorithms for the resolution of the se P and its continuous relaxation dual. This primal-dual approach guarantees the best found solution to be at a certain percentage of the optimal solution and, eventually, proves the solution optimality. The main components of the proposed architecture are greedy and consensus algorithms, tabu search procedures, subgradient methods and cutting plane generators. The main exact methods for the se P resolution are based on enumerative methodologies. Most of these methods deploys many of the heuristic technics used in the proposed architecture to the enumeration scheme. However, these methods have a poor performance in some instance classes, because they do not obtain good solutions in a reasonable time limit. The proposed architecture was applied to particularly hard instances. The obtained results show that it is possible to reach solutions, at an acceptable computational effort, that are at least comparable to the ones obtained by the best algorithms for the SCP / Mestrado / Mestre em Ciência da Computação

Orientador: Christiano Lyra Filho / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-21T19:37:43Z (GMT). No. of bitstreams: 1 VelezBenito_RafaelCarlos_D.pdf: 8351475 bytes, checksum: c7d4a0617510bde9ca9da88e7d103edb (MD5) Previous issue date: 1996 / Resumo: O presente trabalho faz um estudo cuidadoso dos métodos de pontos interiores para obter implementações eficientes na solução de problemas de fluxo de custo mínimo. Tendo em vista que a maior parte do esforço computacional dos algoritmos baseados nos métodos de pontos interiores é dedicado à solução de sistemas do tipo AD* ATY = b, é feita uma análise deste sistema, explorando-se as características da estrutura de redes. Implementa-se especializações dos métodos diretos e dos métodos iterativos. Os métodos diretos são especializações da decomposição de Choleski. Heurísticas do tipo grau mínimo e preenchimento local mínimo são usadas para reordenação das linhas e colunas, procurando conservar a esparsidade da matriz AD* AT. Para a família dos problemas de transportes e atribuição, desenvolve-se um método de ordenação ótima. Os métodos iterativos são do tipo gradiente conjugado pré-condicionado. A estrutura de rede permite agilizar o cálculo das direções, reduzir requisitos de memória e construir pré-condicionadores bem informados. Um pré-condicionador do tipo diagonal é usado nos primeiros passos dos métodos de pontos interiores. Quando a solução se aproxima da otimalidade, constrói-se um outro pré-condicionador, baseado em estimações sobre a base ótima. Desenvolve-se implementações especializadas à problemas de fluxo de custo mínimo dos métodos primal afim, dual afim, primal dual e preditor-corretor. Interpretações baseadas no método de Newton para solução de problemas não lineares levaram a inovações nas implementações dos métodos afins. Estuda-se o problema de falta de volume (ou falta de pontos interiores), aspecto frequente em problemas de fluxo de custo mínimo. Avalia-se suas conseqüências na utilização de métodos de pontos interiores. A partir dos experimentos computacionais com os códigos desenvolvidos, procura-se fazer uma sistematização dos problemas em classes, com indicação das melhores alternativas de solução para cada classe.Finalmente, faz-se extensões das idéias desenvolvidas para a resolução de problemas de fluxos generalizados, através de métodos de pontos interiores / Abstract: This work is a careful study of the interior point methods looking for eflicient implementations for network flow linear programs. Computational experiments are developed with the primal afline, dual afline, primal dual and predictor-corrector methods looking for the best alternatives for different classes of problems. We discuss Newton's method interpretations of these methods. Since most of the computational time of the interior point methods is spent solving systems of the type (AD* AT)y = b, for different diagonal matrices D* and the same incidence matrix A we take advantage of the structure of such systems for networks. We use the sparse Cholesky factorization with two heuristics: the minimum degree and local minimum fill-in. For the family transportation and assignment problems, it is developed an optimal ordering method. We also use the conjugate gradient method with diagonal and maximum spanning tree preconditioners. We give particular attention to the degenerescency phenomena mainly to the lack of primal and/or dual interior feasible points. We study their consequences to interior point methods. Finally proposes extensions of the main ideas to the generalized network problems / Doutorado / Doutor em Engenharia Elétrica

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

Orientador: Marcus Vinicius S. Poggi de Aragão / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-22T19:24:13Z (GMT). No. of bitstreams: 1 Barboza_EduardoUchoa_M.pdf: 2477337 bytes, checksum: a3047f5638be88ee13e8e89477e4f570 (MD5) Previous issue date: 1997 / Resumo: A classificação de dados consiste em separar um conjunto de objetos, descritos por um conjunto de dados, em classes, de forma a que objetos na mesma classe sejam semelhantes entre si. A classificação freqüentemente é usada como uma ferramenta de pesquisa científica. Os objetivos de uma classificação podem diferir de acordo com as necessidades e com a origem dos dados sobre os objetos a classificar. Em alguns contextos existe interesse em associar os objetos aos vértices de um grafo, de forma que a semelhança entre os objetos esteja relacionada a proximidade nesse grafo. Os métodos existentes, para aplicações nestes contextos~ obrigam cada classe a formar um único componente conexo dentro do grafo. Chamamos essa abordagem de conexidade estrita e propomos a idéia de classificação com conexidade flexibilizada, ou seja a concepção de métodos que permitam a um usuário especificar o número de componentes de cada classe no grafo e mostramos porque essa flexibilização é desejável. Em seguida, estudamos a resolução de um problema computacional resultante da flexibilização da conexidade, o Problema da Atribuição ?-Conexa (PAgC). Demonstramos a NP-completude desse problema e apontamos alguns casos polinomiais. Então, concentramo-nos no estudo de diferentes formas para modelar matematicamente a conexidade flexibilizada. Os resultados obtidos podem ser naturalmente aplicados a outros problemas onde tal conexidade é necessária. Finalmente, propomos dois algoritmos para resolver (PAgC). Um baseado na técnica de branch-and-bound e outro na de branch-and-price. Uma comparação dos resultados obtidos por cada técnica é apresentada na seqüência. em estudo de classes de desigualdades válidas, capazes de melhorar substancialmente ambos os algoritmos, conclui a dissertação. / Abstract: Classification of objects amounts to defining, say, K clusters on a set of N objects such that object in a same cluster are alike. Classification is often used as a tool for scientific research. Some important contexts of objects classification use enhanced methods where the objects are associated to vertices of a graph. Proximity between two objects in this graph usually means that the dissimilarity between them is small. The methods applied in such contexts require each cluster to define a single connected component on this graph. We call this strict connectivity approach and we propose the idea of flexible connectivity. This suggests the development of methods where the user may specify the number of connected components each cluster may form on the graph. We present reasons for this flexibilization. Next, we study the computational problem derived from the flexible connectivity, the y-Connected Assignment Problem (PAgC). We show this problem to be NP-complete and we point out some polynomial cases. Then, we concentrate our effort on deriving formulations for considering this flexible connectivity. Clearly, the conceived models can be applied to other problems where connectivity constraints are to be considered. Finally, we propose two algorithms to solve PAgC. One based on the branch-and-cut technique and other on the branch-and-price technique. A comparison between the results obtained with each technique is presented. We conclude this work studying classes of valid inequalities capable of improving the efficiency of both algorithms. / 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