Orientador: Flávio Keidi Miyazawa / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-19T18:16:55Z (GMT). No. of bitstreams: 1 Hokama_PedroHenriqueDelBianco_M.pdf: 1340789 bytes, checksum: b5cc3f26e41b90afabdfac5c7a33bf05 (MD5) Previous issue date: 2011 / Resumo: Nesta dissertação de mestrado apresentamos um método exato para o Problema do Caixeiro Viajante com Restrições de Empacotamento Tridimensional, que combina o Problema do Caixeiro Viajante o Problema de Empacotamento Tridimensional com Restrição de Ordem. Neste problema, um veículo deve partir carregado de um depósito e entregar caixas em pontos pré-definidos para seus clientes. Cada cliente tem um conjunto de caixas que deve receber e o objetivo é minimizar o custo de deslocamento do veículo. As caixas devem ser retiradas a partir da porta do contêiner do veículo e a remoção das caixas de um cliente não podem ser obstruídas pelas caixas a serem descarregadas posteriormente. Propomos uma abordagem exata baseada em branch-and-cut para buscar uma rota de custo mínimo. Apresentamos algumas adaptações de algoritmos da literatura e uma formulação em Programação por Restrições para encontrar um empacotamento que obedece restrições de ordem. Realizamos testes computacionais em instâncias geradas aleatoriamente e comparamos resultados com os algoritmos adaptados da literatura. Os resultados foram bastante satisfatórios resolvendo instâncias de tamanho médio em tempo computacional aceitável na prática / Abstract: We present an exact method for the Traveling Salesman Problem with Three-dimensional Loading Constraints. This problem combines the Traveling Salesman Problem, and the Three- Dimensional Packing Problem With Loading Constraints. In this problem, a vehicle must be loaded at the depot and deliver boxes to the customers. Every customer has a set of boxes that should receive and our goal is to minimize the travel cost of the vehicle. Unloading is done through a single side of the container and items from an unloading customer must not be blocked by items to be delivered later. We propose exact and heuristic branch-and-cut algorithm to find a minimum cost route. Adaptations of algorithms from the literature and a Constraint Programming formulation is presented to find a packing that consider unloading contraints. We performed computational tests on instances randomly generated and compared results with the algorithms adapted from literature. The results were quite satisfactory resolving several instances in reasonable computational time / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientador: Pedro José Catuogno / Dissertação (mestrado profissional) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-26T10:58:39Z (GMT). No. of bitstreams: 1 Fonte_CarlaCristina_M.pdf: 29679078 bytes, checksum: 0009a52938b1cb16c79bdc47af10d323 (MD5) Previous issue date: 2014 / Resumo: Neste trabalho, exploram-se os conceitos iniciais e aplicações importantes da teoria de grafos. Acentuam-se, nas aplicações, alguns problemas clássicos, como o das sete pontes de Königsberg, o do caixeiro viajante e o problema dos casamentos estáveis. Com o intuito de servir como material de apoio para a introdução de grafos ao ensino médio, expõe-se uma sugestão para plano de aula, cuja exploração sinaliza diversas propriedades matemáticas interessantes, além de estimular o raciocínio e o estudo / Abstract: This work focuses on the initial concepts and important applications of the graph theory. Detailing, in the applications, some classic problems such as the seven bridges of Königsberg problem, the travelling salesman problem and the stable marriage problem. In order to provide a supporting material for the introduction to graphs in high school, it is shown a suggestion to the lesson plan, which exploration indicates various interesting mathematical properties beyond stimulating the reasoning and the deep study in the field / Mestrado / Matemática em Rede Nacional / Mestra em Matemática em Rede Nacional

O problema do caixeiro viajante (PCV) é um problema clássico de otimização que possui diversas variações, aplicações e instâncias. Encontrar a solução ótima para muitas instâncias desse problema é geralmente muito difícil devido o alto custo computacional. Vários métodos de otimização, conhecidos como meta-heurísticas (MHs), são capazes de encontrar boas soluções para o PCV. Muitos algoritmos baseados em diversas MHs têm sido propostos e investigados para diferentes variações do PCV. Como não existe um algoritmo universal que encontre a melhor solução para todas as instâncias de um problema, diferentes MHs podem prover a melhor solução para diferentes instâncias do PCV. Desse modo, a seleção a priori da MH que produza a melhor solução para uma dada instância é uma tarefa difícil. A pesquisa desenvolvida nesta tese investiga o uso de abordagens de meta-aprendizado para selecionar as MHs mais promissoras para novas instâncias de PCV. Essas abordagens induzem meta-modelos preditivos a partir do treinamento das técnicas de aprendizado de máquina em um conjunto de meta-dados. Cada meta-exemplo, em nosso conjunto de meta-dados, representa uma instância de PCV descrita por características (meta-atributos) do PCV e pelo desempenho das MHs (meta-atributo alvo) para essa instância. Os meta-modelos induzidos são usados para indicar os valores do meta-atributo alvo para novas instâncias do PCV. Vários experimentos foram realizados durante a investigação desta pesquisa e resultados importantes foram obtidos / The traveling salesman problem (TSP) is a classical optimization problem that has several variations, applications and instances. To find the optimal solution for many instances of this problem is usually a very hard task due to high computational cost. Various optimization methods, known as metaheuristics (MHs), are capable to generate good solutions for the TSP. Many algorithms based on different MHs have been proposed and investigated for different variations of the TSP. Different MHs can provide the best optimization solution for different TSP instances, since there is no a universal algorithm able to find the best solution for all instances. Thus, a priori selection of the MH that produces the best solution for a given instance is a hard task. The research developed in this thesis investigates the use of meta-learning approaches to select the most promising MHs for new TSP instances. These approaches induce predictive meta-models from the training of machine learning techniques on a set of meta-data. In our meta-data, each meta-example is a TSP instance described by problem characteristics (meta-features) and performance of MHs (target meta-features) for this instance. The induced meta-models are used to indicate the values of the target meta-feature for new TSP instances. During the investigation of this research, several experiments were performed and important results were obtained

Submitted by Nadir Basilio (nadirsb@uninove.br) on 2015-07-17T15:18:49Z No. of bitstreams: 1 Wilson da Silva Lourenco.pdf: 1321079 bytes, checksum: ea090b0df77d0c04ef1dde30e7b41558 (MD5) / Made available in DSpace on 2015-07-17T15:18:49Z (GMT). No. of bitstreams: 1 Wilson da Silva Lourenco.pdf: 1321079 bytes, checksum: ea090b0df77d0c04ef1dde30e7b41558 (MD5) Previous issue date: 2015-02-26 / The network optimization problems (NOP) are common to several areas such as engineering, transport and telecommunications, and have been objects of intense research and studies. Among the classical NOP are the problems of Shortest Path (SPP), Max Flow (MFP) and Traveling Salesman (TSP), which are usually studied in undergraduate and graduate courses such as Industrial Engineering, Computer Science, Information Systems and Logistics, with the use of resources such as chalk and blackboard that hinder the teacher's work, in the sense of showing the functioning of algorithms that solve these problems while maintaining students' motivation for learning. In this context, it is proposed in this research, a computational tool, characterized as a Learning Object (OA) and called TASNOP - Teaching Algorithms for Solving Network Optimization Problems, whose purpose is to contribute to students' understanding about concepts from NOP and, mainly, the functioning of algorithms A*, Greedy Search and Dijkstra used for resolution of SPP, Ford-Fulkerson employed in the resolution of MFP and the Nearest Neighbor to solve the TSP. It is important to highlight that the proposed OA can be accessed through web and also employed in distance learning environments (DLE). Experiments conducted in 2014 with 129 students of Computer Science, from which 51 performed an exercise using the TASNOP and 78 without this tool, confirm that students who used the TASNOP performed better in solving the proposed exercise, corroborating the idea that the OA helped to improve their understanding about the algorithms discussed in this research. In addition, the 51 students who employed the TASNOP answered a questionnaire about it use and, the answers indicated that the TASNOP shows a potential to be used as a learning support tool. / Os problemas de otimização em redes (POR) são comuns a diversas áreas como engenharia, transportes e telecomunicações, e têm sido objetos de intensas pesquisas e estudos. Entre os POR clássicos estão os problemas de Caminho Mínimo (PCM), Fluxo Máximo (PFM) e Caixeiro Viajante (PCV), os quais normalmente são estudados em cursos de graduação e pós-graduação tais como Engenharia de Produção, Ciência da Computação, Sistemas de Informação e Logística, com a utilização de recursos como giz e lousa, o que dificulta o trabalho do professor, no sentido de mostrar o funcionamento dos algoritmos que solucionam esses problemas, mantendo a motivação dos alunos para a aprendizagem. Neste contexto, propõe-se nesta pesquisa, uma ferramenta computacional, caracterizada como um Objeto de Aprendizagem (OA) denominado TASNOP - Teaching Algorithms for Solving Network Optimization Problems, cuja finalidade é contribuir para compreensão dos alunos sobre conceitos de POR e, principalmente, sobre o funcionamento dos algoritmos A*, Busca Gulosa, e Dijkstra, usados para resolução do PCM, Ford-Fulkerson empregado na resolução de PFM e o algoritmo Vizinho mais Próximo para resolução do PCV. É importante ressaltar que o OA proposto pode ser acessado via web e, inclusive, ser acoplado em ambientes de ensino a distância (EaD). Experimentos realizados no ano de 2014 envolvendo 129 alunos do curso de Ciência da Computação, dos quais 51 resolveram um exercício com o uso do TASNOP e 78 sem o seu uso, permitiram verificar que os alunos que utilizaram o TASNOP obtiveram melhor desempenho na resolução do exercício proposto, corroborando a ideia de que o OA contribuiu para melhorar suas compreensões acerca dos algoritmos abordados nesta pesquisa. Em adição, os 51 alunos que usaram o TASNOP responderam a um questionário sobre o seu uso e, com base nessas respostas, ficou evidente o potencial do TASNOP como uma ferramenta de apoio ao ensino.

Máquinas insersoras de componentes são utilizadas na indústria eletrônica moderna para a montagem automática de placas de circuito impresso. Com a competição acirrada, há necessidade de se buscar todas as oportunidades para diminuir custos e aumentar a produtividade na exploração desses equipamentos. Neste trabalho, foi proposto um procedimento de otimização do processo de inserção da máquina insersora AVK da Panasonic, implementado em um sistema baseado na técnica de times assíncronos (A-Teams). Foram realizados testes com exemplos de placas de circuito impresso empregadas por uma indústria do ramo e problemas sintéticos para avaliar o desempenho do sistema. / Component inserting machines are employed in the modern electronics industry for the automatic assembly of printed circuit boards. Due the fierce competition, there is a need to search for all opportunities to reduce costs and increase the productivity in the exploitation of these equipment. In this work we propose an optimization procedure for the insertion process of the AVK Panasonic inserting machine, implemented in a system based on asynchronous teams (A-Teams). Tests were conducted using as examples both printed circuit boards used by a particular industry of the realm and synthetic problems for the evaluation of the system.

Made available in DSpace on 2016-04-28T19:58:39Z (GMT). No. of bitstreams: 1 Cleide Aparecida de Souza Cazarotto.pdf: 2380624 bytes, checksum: bf19532fdaf7b47a89b501f2e67f4b4a (MD5) Previous issue date: 2011-02-15 / The overall objective of the study of the short story "O Recado do Morro," the writer João Guimarães Rosa (1908-1963), integrated into the Corpo de Baile anthology (1956), to elucidate the work of hybridization of form, structure and language of the tale Using data from the traveler's field notebooks author and reported in narrative creation process. The understanding of the work designed by us as fictional trans interested in with regard to how the empirical reality is translated by the books (and Boiada 1 Boiada 2) and transformed by the antics of the fictional narrator-traveler, reader, creator and witness simultaneously. The emergence of history, from the perspective of the author diplomat, pointed to the difference reflected in latu and strict sense - the movement of time and space travel through the memory in fable flow of images and maps of the rich nature of the Hinterland Miner. Scenarios and field trials of poetic language in the telling of stories in sync. In this deployment of meta-narratives, the dialogism is the method that implements the parallel tale books and field - between the last collection (Travel, 1952) and present the report (in constant update.) The major effect is marked by the journey of the invention (Seven Stories and seven Messegers), through the other, human and geographical otherness that are meant to represent and refract the author's intentions in terms of a universal message: "O Recado do Morro , o Morro da Garça in the region of Cordisburgo in trans poetry to" The Scrap of Earth. " In the dynamics of travel, the polyphonic narrative finds its dual core, the poetic and linguistic identity uniqueness Rosa, once degenerated by the memory flow, point to the utopia of this unfinished the work in virtual coexistence and current. These are the basic principles raised by the reading of discovery and invention, crossing, contemplation and interactivity, this dissertation / O objetivo geral do estudo do conto O Recado do Morro , do escritor João Guimarães Rosa (1908-1963), integrado à antologia Corpo de Baile (1956), é elucidar o trabalho de hibridação da forma, estrutura e linguagem do conto com os dados das Cadernetas de Campo do viajante autor e a narrativa relatada em processo de criação. A compreensão do trabalho concebido por nós como transcriação ficcional interessou-nos no tocante à maneira como a realidade empírica é traduzida pelas cadernetas (Boiada 1 e Boiada 2) e transformada pelas artimanhas ficcionais do narrador-viajante, leitor, testemunha e criador simultâneos. O emergir da história, sob o olhar do autor diplomata, apontou-nos a diferença refletida, em lato e stricto sensu o movimento do tempo e espaço da viagem pela via da memória em fluxo fabular de imagens e da cartografia da rica natureza do sertão mineiro. Cenários e campos de experimentação da linguagem poética em relato de histórias em sincronia. Neste desdobramento de meta-narrativas, a dialogia é o método que concretiza o paralelismo conto e cadernetas de campo entre o passado da recolha (Viagem de 1952) e o presente do relato (em permanente atualização). O grande efeito final é marcado pela viagem da invenção (sete histórias e sete recadeiros), por meio do Outro, humano e geográfico, alteridades que têm a função de representar e refratar as intenções do autor em função de um recado Universal: O Recado do Morro , o Morro da Garça na região de Cordisburgo, em transcriação poética para O Recado da Terra . Na dinâmica das viagens, a narrativa polifônica encontra seu duplo centro, a singularidade poética e a identidade lingüística rosiana que, uma vez degeneradas pelo fluxo da memória, apontam para a utopia do presente inacabado na obra, em coexistência virtual e atual. Estes são os princípios básicos levantados pela leitura de descoberta e invenção, travessia, contemplação e interatividade, nesta dissertação

Made available in DSpace on 2016-04-28T19:59:22Z (GMT). No. of bitstreams: 1 Vanessa de Bello Lins da Rocha.pdf: 355855 bytes, checksum: c89c7b2cbd6af9b33b3b9a45284a72ce (MD5) Previous issue date: 2010-05-14 / Secretaria da Educação do Estado de São Paulo / This paper analyzes ten stories of 23 histórias de um viajante, Marina Colasanti, from the rescue and return of gender and the wonderful tradition held by the author to write his fictional worlds. By revisiting the wonderful tales, reinterpreted and violates some elements of tradition in the light of contemporary, among them the metamorphosis, the journey and the fairies. Note also through writing Colasantiana, especially in the book 23 histórias de um viajante, this attempt to rescue the traditional root, because the stories are connected to a frame story, which leads to the classic example of construction of the As Mil e uma Noites but that story frame is frequent dialogue with the reader, and it is as if the twenty-fourth story in the book, because it depends on the other 23 stories, moreover all the stories are interrelated, allowing the book to be read in sequence or random. The author also innovates to try to put the existential dilemma of his characters in the service of the dilemma of literary construction. The theoretical framework that supports the reading of the wonderful is Todorov, Marino, Chiampi, Rodrigues and Le Goff, and as for fairy tales has Propp and Jolles as main theoretical. The methodology used for the reading of the corpus is the descriptive and analytical / Este trabalho analisa dez contos do livro 23 histórias de um viajante, de Marina Colasanti, a partir do resgate e revisitação do gênero maravilhoso e da tradição realizados pela autora ao compor seus mundos ficcionais. Ao revisitar os contos maravilhosos, reinterpreta e transgride alguns elementos da tradição sob a luz da contemporaneidade, dentre eles a metamorfose, a viagem e a figura da fada. Nota-se também por meio da escritura Colasantiana, especialmente em 23 histórias de um viajante, o resgate da raiz tradicional realizado pela própria composição do livro: os contos são interligados por um conto moldura, o que remete ao exemplo clássico de construção das Mil e Uma Noites. Na obra analisada nesta dissertação, o conto moldura estabelece diálogos freqüentes com o leitor, configurando-se como a vigésima quarta história do livro. A autora inova ainda ao associar o dilema existencial de suas personagens ao da própria construção literária. O suporte teórico que respalda a leitura do maravilhoso é composto por autores como Todorov, Marinho, Chiampi, Rodrigues e Le Goff, e, quanto à reflexão sobre os contos maravilhosos, têm-se Propp e Jolles como principais suportes teóricos. A metodologia utilizada para a leitura do corpus é a descritivo-analítica

Máquinas insersoras de componentes são utilizadas na indústria eletrônica moderna para a montagem automática de placas de circuito impresso. Com a competição acirrada, há necessidade de se buscar todas as oportunidades para diminuir custos e aumentar a produtividade na exploração desses equipamentos. Neste trabalho, foi proposto um procedimento de otimização do processo de inserção da máquina insersora AVK da Panasonic, implementado em um sistema baseado na técnica de times assíncronos (A-Teams). Foram realizados testes com exemplos de placas de circuito impresso empregadas por uma indústria do ramo e problemas sintéticos para avaliar o desempenho do sistema. / Component inserting machines are employed in the modern electronics industry for the automatic assembly of printed circuit boards. Due the fierce competition, there is a need to search for all opportunities to reduce costs and increase the productivity in the exploitation of these equipment. In this work we propose an optimization procedure for the insertion process of the AVK Panasonic inserting machine, implemented in a system based on asynchronous teams (A-Teams). Tests were conducted using as examples both printed circuit boards used by a particular industry of the realm and synthetic problems for the evaluation of the system.

O presente trabalho propõe resolver o clássico problema combinatorial conhecido como problema do caixeiro viajante. Foi usado no sistema de otimização de busca do menor caminho uma rede neural recorrente. A topologia de estrutura de ligação das realimentações da rede adotada aqui é conhecida por rede recorrente de Wang. Como regra de treinamento de seus pesos sinápticos foi adotada a técnica de perturbação simultânea com aproximação estocástica. Foi elaborado ainda uma minuciosa revisão bibliográfica sobre todos os temas abordados com detalhes sobre a otimização multivariável com perturbação simultânea. Comparar-se-á também os resultados obtidos aqui com outras diferentes técnicas aplicadas no problema do caixeiro viajante visando propósitos de validação. / This work proposes to solve the classic combinatorial optimization problem known as traveling salesman problem. A recurrent neural network was used in the system of optimization to search the shorter path. The structural topology linking the feedbacks of the network adopted here is known by Wang recurrent network. As learning rule to find the appropriate values of the weights was used the simultaneous perturbation with stochastic approximation. A detailed bibliographical revision on multivariable optimization with simultaneous perturbation is also described. Comparative results with other different techniques applied to the traveling salesman are still presented for validation purposes.

O presente trabalho propõe resolver o clássico problema combinatorial conhecido como problema do caixeiro viajante. Foi usado no sistema de otimização de busca do menor caminho uma rede neural recorrente. A topologia de estrutura de ligação das realimentações da rede adotada aqui é conhecida por rede recorrente de Wang. Como regra de treinamento de seus pesos sinápticos foi adotada a técnica de perturbação simultânea com aproximação estocástica. Foi elaborado ainda uma minuciosa revisão bibliográfica sobre todos os temas abordados com detalhes sobre a otimização multivariável com perturbação simultânea. Comparar-se-á também os resultados obtidos aqui com outras diferentes técnicas aplicadas no problema do caixeiro viajante visando propósitos de validação. / This work proposes to solve the classic combinatorial optimization problem known as traveling salesman problem. A recurrent neural network was used in the system of optimization to search the shorter path. The structural topology linking the feedbacks of the network adopted here is known by Wang recurrent network. As learning rule to find the appropriate values of the weights was used the simultaneous perturbation with stochastic approximation. A detailed bibliographical revision on multivariable optimization with simultaneous perturbation is also described. Comparative results with other different techniques applied to the traveling salesman are still presented for validation purposes.