abstract: Exhaustive testing is generally infeasible except in the smallest of systems. Research has shown that testing the interactions among fewer (up to 6) components is generally sufficient while retaining the capability to detect up to 99% of defects. This leads to a substantial decrease in the number of tests. Covering arrays are combinatorial objects that guarantee that every interaction is tested at least once. In the absence of direct constructions, forming small covering arrays is generally an expensive computational task. Algorithms to generate covering arrays have been extensively studied yet no single algorithm provides the smallest solution. More recently research has been directed towards a new technique called post-optimization. These algorithms take an existing covering array and attempt to reduce its size. This thesis presents a new idea for post-optimization by representing covering arrays as graphs. Some properties of these graphs are established and the results are contrasted with existing post-optimization algorithms. The idea is then generalized to close variants of covering arrays with surprising results which in some cases reduce the size by 30%. Applications of the method to generation and test prioritization are studied and some interesting results are reported. / Dissertation/Thesis / Masters Thesis Computer Science 2015

Neste trabalho desenvolve-se uma proposta de ensino para aprimorar o raciocínio combinatório, através da utilização de jogos no planejamento, na aplicação e avaliação de uma sequência didática inspirada nas orientações de Zabala, para subsidiar a prática docente no ensino de Análise Combinatória. A dissertação relata uma pesquisa que teve o intuito de explorar conceitos combinatórios por meio de atividades diversificadas, envolvendo recursos digitais, jogos e estudos orientados, a fim de fortalecer e diversificar o ensino e a aprendizagem deste conteúdo, procurando tornar as aulas mais atrativas e dinâmicas. Alguns dos jogos utilizados para a criação da sequência didática não são originais, outros já foram aplicados por pesquisadores ou professores, porém, aqui, foram reorganizados, ajustados ou adaptados de modo a adequar e potencializar a sua utilização, no contexto da prática elaborada. As várias atividades, promovidas para a realização dos jogos ou as de etapa posterior, foram planejadas de modo a explorar o raciocínio combinatório. A pesquisa é fundamentada na visão construtivista do fazer e compreender, de Piaget, e resultou como produto deste trabalho uma sequência didática denominada Dinâmica Combinatória, que integra as atividades dinamizadas numa sequência de ensino que envolve ações, direcionadas para a compreensão dos conceitos combinatórios. Juntamente com este processo de compreensão, construiu-se um espaço para os alunos explorarem, com orientação do professor, toda a simbologia que contempla o conteúdo de Análise Combinatória, a fim de que conhecessem as fórmulas que integram as técnicas de contagem. Por fim, faz-se uma avaliação da aprendizagem, com a utilização do Jogo Trilha Combinatória, criado especialmente para a aplicação dos conhecimentos construídos, por meio das ações que constituem as jogadas, verificando se ocorreu aprendizagem. A análise dos dados obtidos com a pesquisa foi qualitativa, e avaliou formulários, diários de anotações, registros fotográficos, entre outros e revelou aprendizagens e envolvimento dos estudantes para além das expectativas do pesquisador. Conclui-se que a Dinâmica Combinatória tornou-se um recurso didático potencial para a aprendizagem e o desenvolvimento do raciocínio combinatório, propiciando um processo de ensino e aprendizagem de Análise Combinatória dinâmico e atrativo. / Submitted by cmquadros@ucs.br (cmquadros@ucs.br) on 2018-02-15T13:28:13Z No. of bitstreams: 1 Dissertacao Luiz Ambrozi.pdf: 3064720 bytes, checksum: fe1edd8c7258cb7e11b71ceb23d3928c (MD5) / Made available in DSpace on 2018-02-15T13:28:13Z (GMT). No. of bitstreams: 1 Dissertacao Luiz Ambrozi.pdf: 3064720 bytes, checksum: fe1edd8c7258cb7e11b71ceb23d3928c (MD5) Previous issue date: 2018-02-15 / In this paper, a teaching proposal is developed to improve the combinatorial reasoning through the use of games in the planning, application and assessment of a didactic sequence, inspired by Zabala guidelines, to subsidize the teaching practice in Combinatorial Analysis teaching. The dissertation reports a research that aims to explore combinatorial concepts through diversified activities, involving digital resources, games and guided studies, in order to strengthen and diversify the teaching- learning process of this content, trying to make classes more attractive and dynamic. Some of the games used to create the didactic sequence are not original and some of them have already been applied by other researchers or teachers, but in this paper they have been reorganized, adapted and tailored to make them suitable and enhance their use in the practice context. The several activities, promoted for the accomplishment of the games or those of a later stage, were planned aiming to explore the combinatorial reasoning. The research is based on Piaget 's constructivist view of ” the doing and the understanding “ and resulted in a didactic sequence called Combinatorial Dynamics, which integrates the energized activities in a teaching sequence involving actions directed towards the understanding of the combinatorial concepts. Together with this process of comprehension, a space was built for students to explore, with the teacher's guidance, all the symbology that contemplates the content of Combinatorial Analysis, getting them to know the formulas which integrate the counting techniques. Finally, an evaluation of learning is made, using the Combination Track Game, created specially for the application of the constructed knowledge through games, verifying if the learning process was achieved. The research results are from a qualitative analysis that evaluated forms, journals, photographic records, among others and revealed students' learning and involvement beyond the researcher's expectations. It is concluded that Combinatorial Dynamics has become a potential didactic resource for the learning process and for the development of combinatorial reasoning, providing a dynamic and attractive Combinatorial Analysis Teaching and Learning process.

O ser humano tem uma grande estima pelo processo de raciocínio que desenvolveu durante a sua evolução. Uma das áreas da computação foi desenvolvida com o objetivo inicial de simular a inteligência humana dentro de programas computacionais. Esta área ficou conhecida como inteligência artificial. Nas últimas décadas a inteligência artificial tem se baseado nas mais diversas formas de organização que tenham padrões. Um desses métodos é o algoritmo de otimização por colônias de formigas, apresentado no início da década de 90, e que apresentou bons resultados para vários problemas que tiveram modelos implementados. A biologia molecular visa analisar as estruturas moleculares contidas nos seres vivos, dentre elas as seqüências de DNA, RNA e os aminoácidos das proteínas. Devido o grande número de informações envolvidas nessa análise torna-se inviável em termos de tempo de processamento uma busca em todo o espaço de soluções possíveis, o que torna interessante o uso de algoritmos que percorram este espaço de busca de forma eficiente. Um dos problemas da biologia molecular é a reconstrução de árvores filogenéticas. Ele visa relacionar de forma hereditária as diversas espécies através das informações contidas em suas seqüências. Desta forma é possível saber quais espécies são mais próximas em termos evolutivos. Outro problema é o dobramento de proteínas. Uma proteína é um polímero que pode desempenhar as mais diversas funções em um ser vivo. A função que uma proteína desempenha esta diretamente relaciona a sua forma tridimensional. Uma proteína é codificada no DNA, e sintetizada no ribossomo de uma forma linear, a partir desta forma ela se dobra sobre a sua estrutura obtendo a sua forma final. Com a compreensão deste processo, seria possível a identificação de proteínas mal formadas e até mesmo o desenvolvimento de novas proteínas com funções específicas. O presente trabalho visa descrever dos modelos, baseados na otimização por colônia de formigas, desenvolvidos para os problemas. Além disso, foram desenvolvidos recursos especiais que permitem percorrer o espaço de busca de forma mais efetiva obtendo melhores soluções. Os resultados obtidos com as metodologias propostas apresentaram resultados similares ou até melhores que métodos já conhecidos que utilizaram o algoritmo de otimização por colônia de formigas para os mesmos problemas. / The human being has great esteem for the reasoning process developed during its evolution. One of the areas of the computation was developed with the initial objective to simulate human intelligence inside computational programs. This area is known as artificial intelligence. In the last decades artificial intelligence has been basing on the most diverse forms of organization that have standards. One of these methods is the ant colony optimization algorithm, presented in the beginning of nineties, and that achieved good results for some problems that had had implemented models. Molecular biology aims to analyze the molecular structures present in living creatures, amongst them the sequences of DNA, RNA and protein aminoacids. Due to great number of information being confronted in this analysis it is impracticable in terms of processing time a search in the whole space of possible solutions, what makes interesting the use of algorithms that cover the search space efficiently. One of the problems of molecular biology is phylogenetic trees reconstruction. It aims to relate hereditarily the several species through information present in its sequences. In that manner, it is possible to know which species are more closely related to one another and which are more distantly related.

Este trabalho trata de uma aplicação de programação estocástica para administração de passivos e ativos. Inicialmente, um modelo de administração de ativos e passivos utilizando valores de retorno de ativos determinísticos é formalizado, constatando-se as suas limitações, justificando-se a necessidade de abranger formalmente a incerteza inerente aos mercados financeiros. Para isso, um modelo para administração de ativos e passivos que utiliza otimização e programação estocástica baseado em uma árvore de cenários multiestágio balanceada é apresentado, descrito, e implementado. Os seus resultados determinam uma política de investimento de ativos para o instante inicial do período considerado, definindo-se também uma regra que possibilita, a partir do equilíbrio entre o patrimônio inicial e total de passivo a ser pago ao final do período considerado, estimar a probabilidade de insolvência do fundo de pensão. Além disso, realiza-se o estudo do impacto da redução de uma proxy da taxa de juros básico na composição do portfólio administrado por essas empresas. / This work discusses an application of stochastic programming for asset-liability management. Initially, a deterministic asset-liability model is formalized. Its limitations become clear which justify the need to include uncertainty in the model. Then, a stochastic programming model based on a balanced multistage scenario tree is presented, described and implemented for an asset-liability environment. The main results are: (i) an investment policy for the fund, and, (ii) the pension’s fund insolvency probability considering an initial relation between the current assets and the present value of the future liabilities. The impact of a possible reduction in interested rate on the pension’s fund optimal portfolio is also presented.

O empacotamento irregular de fita é um grupo de problemas na área de corte e empacotamento, cuja aplicação é observada nas indústrias têxtil, moveleira e construção naval. O problema consiste em definir uma configuração de itens irregulares de modo que o comprimento do contêiner retangular que contém o leiaute seja minimizado. A solução deve ser válida, isto é, não deve haver sobreposição entre os itens, que não devem extrapolar as paredes do contêiner. Devido a aspectos práticos, são admitidas até quatro orientações para o item. O volume de material desperdiçado está diretamente relacionado à qualidade do leiaute obtido e, por este motivo, uma solução eficiente pressupõe uma vantagem econômica e resulta em um menor impacto ambiental. O objetivo deste trabalho consiste na geração automática de leiautes de modo a obter níveis de compactação e tempo de processamento compatíveis com outras soluções na literatura. A fim de atingir este objetivo, são realizadas duas propostas de solução. A primeira consiste no posicionamento sequencial dos itens de modo a maximizar a ocorrência de posições de encaixe, que estão relacionadas à restrição de movimento de um item no leiaute. Em linhas gerais, várias sequências de posicionamentos são exploradas com o objetivo de encontrar a solução mais compacta. Na segunda abordagem, que consiste na principal proposta deste trabalho, métodos rasterizados são aplicados para movimentar itens de acordo com uma grade de posicionamento, admitindo sobreposição. O método é baseado na estratégia de minimização de sobreposição, cujo objetivo é a eliminação da sobreposição em um contêiner fechado. Ambos os algoritmos foram testados utilizando o mesmo conjunto de problemas de referência da literatura. Foi verificado que a primeira estratégia não foi capaz de obter soluções satisfatórias, apesar de fornecer informações importantes sobre as propriedades das posições de encaixe. Por outro lado, a segunda abordagem obteve resultados competitivos. O desempenho do algoritmo também foi compatível com outras soluções, inclusive em casos nos quais o volume de dados era alto. Ademais, como trabalho futuro, o algoritmo pode ser estendido de modo a possibilitar a entrada de itens de geometria genérica, o que pode se tornar o grande diferencial da proposta. / Irregular nesting belongs to the area of cutting and packing problems and are employed in the textile, wood and shipbuilding industries. The problem consists in determining a configuration for a set of irregular items which minimizes the length of the rectangular container in which the layout is located. The solution must be feasible, i.e., items must not overlap nor protrude the container walls. Due to practical reasons, up to four orientations are allowed for an item. The volume of wasted material is directly affected by the quality (density) of the layout. Thus, an efficient solution produces a positive economic and environmental impact. In this work, the objective is to automatically obtain layouts such that their density and the performance of the algorithm are competitive with other solutions in literature. So as to achieve this goal, two approaches are proposed. The first method uses a special sequential placement heuristic such that the algorithm maximizes exact placements, which consist of constrained positions for items. In general terms, a search is performed in the placement sequence in order to obtain a compact layout. In the second approach, which is the main subject of this work, raster methods are employed to guide the translation of items, which are free to move within the layout, and may overlap other items. The method is based on overlap minimization techniques, in which the objective is to eliminate the overlap in a fixed dimensions container. Both algorithms were tested using benchmark problems from the literature. The first strategy yielded unsatisfactory results, though it provided important information about the properties of exactly fitting placements. On the other hand, the main approach was able to produce competitive solutions. The performance was also compatible with other solutions, even in cases which the data volume was high. Moreover, as a future work, an extension for the algorithm can be developed such that items with generic geometry can be considered, which would be an important advance in research terms.

Este trabalho trata de uma aplicação de programação estocástica para administração de passivos e ativos. Inicialmente, um modelo de administração de ativos e passivos utilizando valores de retorno de ativos determinísticos é formalizado, constatando-se as suas limitações, justificando-se a necessidade de abranger formalmente a incerteza inerente aos mercados financeiros. Para isso, um modelo para administração de ativos e passivos que utiliza otimização e programação estocástica baseado em uma árvore de cenários multiestágio balanceada é apresentado, descrito, e implementado. Os seus resultados determinam uma política de investimento de ativos para o instante inicial do período considerado, definindo-se também uma regra que possibilita, a partir do equilíbrio entre o patrimônio inicial e total de passivo a ser pago ao final do período considerado, estimar a probabilidade de insolvência do fundo de pensão. Além disso, realiza-se o estudo do impacto da redução de uma proxy da taxa de juros básico na composição do portfólio administrado por essas empresas. / This work discusses an application of stochastic programming for asset-liability management. Initially, a deterministic asset-liability model is formalized. Its limitations become clear which justify the need to include uncertainty in the model. Then, a stochastic programming model based on a balanced multistage scenario tree is presented, described and implemented for an asset-liability environment. The main results are: (i) an investment policy for the fund, and, (ii) the pension’s fund insolvency probability considering an initial relation between the current assets and the present value of the future liabilities. The impact of a possible reduction in interested rate on the pension’s fund optimal portfolio is also presented.

Neste trabalho desenvolve-se uma proposta de ensino para aprimorar o raciocínio combinatório, através da utilização de jogos no planejamento, na aplicação e avaliação de uma sequência didática inspirada nas orientações de Zabala, para subsidiar a prática docente no ensino de Análise Combinatória. A dissertação relata uma pesquisa que teve o intuito de explorar conceitos combinatórios por meio de atividades diversificadas, envolvendo recursos digitais, jogos e estudos orientados, a fim de fortalecer e diversificar o ensino e a aprendizagem deste conteúdo, procurando tornar as aulas mais atrativas e dinâmicas. Alguns dos jogos utilizados para a criação da sequência didática não são originais, outros já foram aplicados por pesquisadores ou professores, porém, aqui, foram reorganizados, ajustados ou adaptados de modo a adequar e potencializar a sua utilização, no contexto da prática elaborada. As várias atividades, promovidas para a realização dos jogos ou as de etapa posterior, foram planejadas de modo a explorar o raciocínio combinatório. A pesquisa é fundamentada na visão construtivista do fazer e compreender, de Piaget, e resultou como produto deste trabalho uma sequência didática denominada Dinâmica Combinatória, que integra as atividades dinamizadas numa sequência de ensino que envolve ações, direcionadas para a compreensão dos conceitos combinatórios. Juntamente com este processo de compreensão, construiu-se um espaço para os alunos explorarem, com orientação do professor, toda a simbologia que contempla o conteúdo de Análise Combinatória, a fim de que conhecessem as fórmulas que integram as técnicas de contagem. Por fim, faz-se uma avaliação da aprendizagem, com a utilização do Jogo Trilha Combinatória, criado especialmente para a aplicação dos conhecimentos construídos, por meio das ações que constituem as jogadas, verificando se ocorreu aprendizagem. A análise dos dados obtidos com a pesquisa foi qualitativa, e avaliou formulários, diários de anotações, registros fotográficos, entre outros e revelou aprendizagens e envolvimento dos estudantes para além das expectativas do pesquisador. Conclui-se que a Dinâmica Combinatória tornou-se um recurso didático potencial para a aprendizagem e o desenvolvimento do raciocínio combinatório, propiciando um processo de ensino e aprendizagem de Análise Combinatória dinâmico e atrativo. / In this paper, a teaching proposal is developed to improve the combinatorial reasoning through the use of games in the planning, application and assessment of a didactic sequence, inspired by Zabala guidelines, to subsidize the teaching practice in Combinatorial Analysis teaching. The dissertation reports a research that aims to explore combinatorial concepts through diversified activities, involving digital resources, games and guided studies, in order to strengthen and diversify the teaching- learning process of this content, trying to make classes more attractive and dynamic. Some of the games used to create the didactic sequence are not original and some of them have already been applied by other researchers or teachers, but in this paper they have been reorganized, adapted and tailored to make them suitable and enhance their use in the practice context. The several activities, promoted for the accomplishment of the games or those of a later stage, were planned aiming to explore the combinatorial reasoning. The research is based on Piaget 's constructivist view of ” the doing and the understanding “ and resulted in a didactic sequence called Combinatorial Dynamics, which integrates the energized activities in a teaching sequence involving actions directed towards the understanding of the combinatorial concepts. Together with this process of comprehension, a space was built for students to explore, with the teacher's guidance, all the symbology that contemplates the content of Combinatorial Analysis, getting them to know the formulas which integrate the counting techniques. Finally, an evaluation of learning is made, using the Combination Track Game, created specially for the application of the constructed knowledge through games, verifying if the learning process was achieved. The research results are from a qualitative analysis that evaluated forms, journals, photographic records, among others and revealed students' learning and involvement beyond the researcher's expectations. It is concluded that Combinatorial Dynamics has become a potential didactic resource for the learning process and for the development of combinatorial reasoning, providing a dynamic and attractive Combinatorial Analysis Teaching and Learning process.

Orientador: Vinicius Amaral Armentano / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-13T19:39:00Z (GMT). No. of bitstreams: 1 Takahata_AndreKazuo_M.pdf: 1113954 bytes, checksum: 18f4c96c943dced30f100b8a56c97258 (MD5) Previous issue date: 2009 / Resumo: Este trabalho trata do desenvolvimento de heurísticas de busca genéricas para obtenção de soluções de problemas de otimização combinatória formulados como modelos de programação linear inteira, com o uso do pacote de otimização XPRESS. Este é um tema recente, em que são conjugados a flexibilidade de heurísticas e os avanços dos solvers de otimização para a obtenção de soluções de alta qualidade em tempo reduzido. As heurísticas propostas são baseadas em arredondamentos gerados a partir de raios de um cone, cujo vértice é associado à solução ótima da relaxação de programação linear, e em trajetórias factíveis e infactíveis em relação à fronteira desta relaxação. A motivação para este enfoque é dada pelo apelo geométrico e no sucesso de estratégias similares em heurísticas para problemas combinatórios. O trabalho descreve a concepção e a implementação dessas heurísticas e apresenta resultados de testes em instâncias da literatura. / Abstract: In this work we develop a set of generic search heuristics for solving combinatorial optimization problems formulated as linear integer programming models, using the XPRESS optimization package. This is a recent theme, in which efforts have been made in order to combine the flexibility offered by heuristics and the expressive advances achieved in the development of optimization solvers so as to obtain high quality solutions in a short time. The proposed heuristics are based on rounding solutions located on the rays of a cone whose vertex is associated with the optimal solution of the linear programming relaxation, and in feasible and infeasible trajectories relative to the frontier of such relaxation. This approach is motivated by its geometric appeal and by the success of similar approaches in heuristics for solving combinatorial problems. This work describes the development and implementation of the heuristics and presents computational tests on instances from literature. / Mestrado / Automação / Mestre em Engenharia Elétrica

Orientador: Paulo Morelato França / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-14T08:51:37Z (GMT). No. of bitstreams: 1 Assis_LauraSilvade_M.pdf: 1632808 bytes, checksum: dfd28dc2bbd2bb5fe453a2fb1c2b7b6e (MD5) Previous issue date: 2009 / Resumo: O objetivo desta dissertação é desenvolver uma metodologia eficiente para solucionar o problema de agrupamento capacitado multicritério (PACM), no qual objetos com pesos associados são dados, os quais devem ser particionados em agrupamentos com capacidade limitada. Neste trabalho, o PACM está ambientado em um problema de reagrupamento de lotes urbanos, nos quais devem ser realizadas as leituras dos medidores de energia elétrica por concessionárias de distribuição de energia. A operação de leitura dos medidores é realizada sobre lotes geograficamente definidos e é desempenhada sobre rotas percorridas uma vez por mês pelos leituristas. A motivação deste trabalho é atribuída ao fato de que, com o passar do tempo, o tamanho e o formato dos lotes vão ficando obsoletos, devido a modificações introduzidas na conformação atual, desarranjando o equilíbrio entre os lotes e desatualizando as rotas. Por esse motivo é importante realizar um reagrupamento dos lotes buscando a diminuição dos custos operacionais de leitura, assim como a minimização dos custos e transtornos causados pelas modificações. O método proposto para resolver o problema abordado nesta dissertação é um algoritmo baseado na metaheurística GRASP (Greedy randomized adaptive search procedure). A eficiência do método proposto é testada sobre uma série de instâncias geradas e sobre uma rede real. Os experimentos computacionais demonstram a eficiência do método. / Abstract: The aim of this dissertation is to develop an eficient methodology to solve the multicriteria redistricting capacitated problem (PACM), in which objects with associated weights are given, which must be partitioned into groups with limited capacity. In this work, the PACM is inserted in to a reassignment problem of urban clusters of clients, in which the readings of the eletric energy measurement must be performed by the company of energy distribution. The reading operation is performed over lots geographically defined is performed once a month by the readers. The motivation of this work is due to the fact that the size and shape of the lots become obsolete after some time, due to modifications introduced in the current conformation, desarranging the balance between the lots and outdating the routes. For this reason it is important to achieve a reassignment of the lots trying to decrease the operational costs of reading, as well as minimizing the costs and inconvenience caused by the changes. The proposed method to solve the problem addressed in this dissertation is a algorithm based on GRASP (Greedy randomized adaptive search procedure) metaheuristic. The efectiveness of the proposed method is tested on a large number of generated instances and on a real network. Computational experiments demonstrate the efectiveness of the proposed approach. / Mestrado / Automação / Mestre em Engenharia Elétrica

Orientador: Andreia Cristina Ribeiro / Dissertação (mestrado profissional) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-11T11:28:46Z (GMT). No. of bitstreams: 1 Assis_LucianaMafaldaEliasde_M.pdf: 10126493 bytes, checksum: bb2628e76f90df6deb24a9011e535714 (MD5) Previous issue date: 2008 / Resumo: Neste trabalho são apresentados vários resultados importantes da Análise Combinatória com destaque para o Princípio da Inclusão e Exclusão. Relevantes aplicações deste princípio são abordadas / Abstract: In this work we present important results from enumerative combinatorics, with an emphasis on the Principle of Inclusion and Exclusion. Relevant applications of this principle are presented to illustrate its use / Mestrado / Mestre em Matemática