Diante de um cenário de contradições do atual ensino da Matemática, no qual a prática tem se revelado insatisfatória para se alcançar os objetivos declarados para tal disciplina em documentos oficiais, sugerimos a situação adidática, um conceito da Teoria das Situações de Brousseau (1933-), como ferramenta para uma aprendizagem matemática mais autônoma, ou seja, uma aprendizagem que possibilite o desenvolvimento de habilidades investigativas, interpretativas, críticas e criativas. A Teoria das Situações, elaborada pelo pesquisador francês Brousseau, é uma ferramenta de análise. Desse modo, a situação adidática é um conceito que permite modelar determinadas situações de aprendizagem a serem analisadas. O objetivo do presente trabalho é mostrar que este conceito também serve como instrumento metodológico, à medida que o docente, de posse dele, pode planejar situações potencialmente adidáticas em sala de aula. Baseada nesta teoria e em outras da Didática Francesa, bem como nas concepções de aprendizagem e desenvolvimento de Vigotski (1896-1934), buscamos analisar a aplicação de uma Sequência Didática em três momentos diferentes, os quais revelam três cenários escolares também distintos e três passagens da minha experiência como pesquisadora e docente. A Sequência Didática, planejada visando potencializar uma situação adidática, aborda o tema Análise Combinatória através de uma narrativa ficcional com desafios voltados para o Ensino Médio. Ao longo desse estudo, pudemos alcançar muito mais do que pretendíamos: percebemos que há fatores presentes na escola (independente de ser pública ou privada) que favorecem e fatores que desfavorecem o surgimento de uma situação adidática. No entanto, prosseguimos acreditando que planejar as aulas visando promover situações adidáticas, com todas as limitações presentes em nossa realidade educacional, é o melhor caminho para se chegar aos objetivos pretendidos para o ensino de Matemática, levando-se em conta as concepções de aprendizagem por nós adotadas. / Facing a background of dramatic contradictions of the current mathematics teaching, in which the practice has been insufficient to achieve the stated objectives for such discipline in official documents, we suggest adidactic situation, a concept of Brousseaus (1933-)Theory of Situations, as a tool for learning mathematics more autonomous, ie, a learning that enables the development of investigative, interpretive, critical and creative skills. The Theory of Situations, prepared by the French researcher Brousseau, is an analysis tool. Thus, adidactic situation is a concept that allows to model certain learning situations to be analyzed. The objective of this paper is to show that this concept also serves as a methodological tool, as the teacher, holding it, can plan potentially adidactic situations in the classroom. Based on this theory and others of the French didactics, as well as in the conceptions of learning and development of Vygotsky (1896-1934), we analyze the application of a Teaching Sequence in three different moments, which also reveal three different school settings and three passes from my experience as a researcher and teacher. The Didactic Sequence, planned aiming at intensifying one adidactic situation, addresses the topic of Combinatorial Analysis through a fictional narrative with challenges facing High School. Throughout this study, we could achieve far more than we wanted: we realized that there are factors present in school (whether it be public or private) that favor and factors that disfavor the emergence of anadidactic situation. However, we continue to believe that planning lessons to promote adidactic situations, with all the limitations present in our educational reality is the best way to reach the objectives intended to mathematics teaching, taking into account the conceptions of learning we adopted.

Neste trabalho foi estudado um problema de dimensionamento de lotes em uma indústria química brasileira, cujo objetivo era determinar o tamanho dos lotes dos produtos para atender às demandas, minimizando os custos produtivos. Os itens podem ser produzidos em máquinas paralelas distintas, através de diferentes processos, e devem ser armazenados em taques cativos, exclusivos a um produto, ou multipropósitos, compartilhado entre produtos, desde que não simultaneamente. Foram propostos dois modelos matemáticos de programação inteira mista para representar o problema, o primeiro apresentava uma função objetivo compreendendo o preço das matérias-primas consumidas nas reações, os gastos com a estocagem de produtos e o custo de descarte de produtos quando os tanques de armazenamento não tiverem capacidade suficiente para armazená-los, já o segundo estendendo este modelo para considerar custos de preparação de máquina. Experimentos computacionais com os modelos propostos, utilizando instâncias geradas a partir dos dados fornecidos pela empresa, mostraram que o software de otimização empregado foi capaz de resolver poucas instâncias, após uma hora de processamento. Portanto, foram propostas heurísticas construtivas do tipo LP-and-fix e relax-and-fix, além de heurísticas de melhoria do tipo fix-and-optimize. Após serem realizados testes com essas heurísticas, constatou-se que algumas proporcionaram a obtenção de soluções factíveis de boa qualidade, quando comparadas às obtidas pelo software, sendo ainda capazes de resolver um maior número de instâncias / In this dissertation the lot sizing problem in a chemical Brazilian industry was studied, with the goal to determine the products lot size to satisfy the demands, minimizing the production costs. The items can be produced on distinct parallel machines through different processes and then must be stored in exclusive tanks, used by only one product, or multipurpose tanks, when more than one product can use the tank, but not simultaneously. Two models were proposed to represent the problem, the first one aiming to minimize the price of raw material consumed in the reactions, storage product spending and the cost of discarting products when the storage tanks do not have enough capacity to store them, and the second one considering setup cost either. Computational experiments using the proposed models, with instances were generated from the data provided by the company, showed that the used optimization software was able to solve only few instances after processing for one hour. In this dissertation we propose constructives heuristics such LP-and-fix and relax-and-fix, and improving heuristics like fix-and-optimize. After performing the tests with those heuristics, it was found that some of them provided feasible solutions with good quality, when compared to the ones obtained by the software, and they were also able to solve a larger number of instances

Visando avaliar o potencial de populações segregantes de trigo obtidas de parentais portadores de características agronômicas contrastantes, quanto ao comprimento da raiz primária, produção de grãos e caracteres agronômicos; estimar a herdabilidade no sentido amplo e restrito para populações F2 obtidas, além das associações das características em estudo; confirmar os genitores mais promissores para utilização em programas de melhoramento de trigo e estimar a capacidade geral e específica de combinação dos genótipos de trigo, foram efetuados cruzamentos, em forma dialélica, entre quatro genótipos de trigo: BH-1146, Anahuac M-1, IAC-287/IAC-24 M-1 e MONS/ALDS// IAC-24 M-3. Foram obtidos híbridos em geração F1 e F2 e os retrocruzamentos RC1 e RC2, que foram avaliados quanto ao comprimento da raiz em solução nutritiva, conforme Camargo e Ferreira Filho (2005a). Após a medição das raízes, as plântulas foram transplantadas para telado do Centro de Grãos e Fibras do IAC sob delineamento de blocos ao acaso, com 28 tratamentos (os 4 parentais, os 6 F1s, F2s, RC1s e RC2s), com 6 repetições. Avaliaram-se os caracteres comprimento da raiz primária, altura das plantas, comprimento da espiga, número de espiguetas por espiga, grãos por espiga, grãos por espigueta, massa de cem grãos, comprimento do internódio da raque, número de espigas por planta, produção de grãos por planta e florescimento. Para análise dialélica foi utilizado o Modelo de Griffing (1956) Os valores estimados para a herdabilidade em sentido amplo, para os seis cruzamentos, foram altas para altura de plantas; médios, na maioria dos cruzamentos, para comprimento da raiz, comprimento da espiga, números de espigas por planta e grãos por espiga, produção de grãos por planta e florescimento; de médios a altos para comprimento do internódio da raque e número de espiguetas por espiga e de médios a baixos para massa de cem grãos e número de grãos por espigueta. Esses valores indicaram que grande parte das variações encontradas foi de origem genética. As estimativas de herdabilidade no sentido restrito (h2r) mostraram grande variação de magnitude nos diferentes cruzamentos para todos os caracteres avaliados. Ressaltou-se o cruzamento P1/P4, com parentais divergentes, com elevados valores de herdabilidade no sentido restrito. Altos valores de h2r foram estimados para altura de plantas em todos os cruzamentos, indicando que a seleção será efetiva nas primeiras gerações segregantes. As correlações fenotípicas revelaram haver uma tendência da seleção de plantas com maior comprimento da raiz primária estar associada com maior produção de grãos por planta e maior precocidade para o florescimento. BH-1146 demonstrou ser fonte genética de tolerância à seca no estádio inicial da cultura do trigo. As análises dialélicas corroboraram os resultados dos ensaios de genótipos, destacando os genótipos P4 como fonte de redução de altura das plantas e o P1 como fonte de aumento do comprimento da raiz; para produção de grãos evidenciaram-se P1 e P2 com elevados valores de capacidade geral de combinação. Detectaram-se efeitos significativos da CEC e CGC, evidenciando a ação de genes preponderantemente aditiva e de dominância na manifestação dos na maioria dos caracteres estudados / Diallel crossing was made with four wheat genotypes: BH-1146, Anahuac M-1, IAC-287/IAC-24 M-1 and MONS/ALDS// IAC-24 M-3, bearing agronomically contrasting characteristics, to evaluate the potential of segregating populations of wheat obtained from parents bearing contrasting agronomic characteristics for primary root length, grain yield and agronomic characteristics; to estimate the herdability, in the broad and narrow senses, for F2 obtained populations in addition to the association of the traits under study; to confirm the more promising parents for use in wheat improvement programs and to estimate the general and specific combining abilities of wheat genotypes. Hybrid were obtained in F1 and F2 generation of RC1 and RC2 backcrossing, which were evaluated for their root length in nutrient solution, according to Camargos and Ferreira Filhos method (2005a). After root measuring, plantules were transplanted to screens of the IAC Center for Grain and Fibers in blocks at random, with 28 treatments (4 parents, the 6 F1s, the 6 F2s, the 6 RC1s and the 6 RC2s), with 6 repetitions. Characteristics such as primary root length, plant length, and spike length, number of spikelet per spike, grains per spike, grains per spikelet, 100 grain weight, length of the rachis internode heigth, number of spike per plant, grain yield per plant and flowering were evaluated. The Griffing Model (1956) was used for the diallel analysis. Herdability estimates were obtained. The herdability estimates in the broad sense for the six crossings were high for plant height in all of them; moderate, in most of the crossings for root growth, spike heigth, number of spikes per plant and grain per spike, grain yield per plant and flowering; were moderate to high for rachis internode height and the number of spikelet per spike and moderate to low for 100 grain weight per spikelet. These values indicated that a large part of the variability found was of genetic origin. Herdability estimates in the narrow sense showed large variability in magnitude in the different crossings for the studied traits. P1/P4 crossing with different parents showed high herdability in the narrow sense. High herdability values in the narrow sense were estimated for plant heigth in all crossings, indicating that the selection will be effective for the first segregating generations. Phenotype correlations showed a tendency for the selection of plants with larger heigth for the primary root being associated with a higher grain yield per plant and higher early flowering. BH-1146 proved to be a genetic source of tolerance to drought in the initial stage of the wheat breeding. Diallel analysis confirm the results of experiments with genotypes, showing high values in the combining ability of P4 genotypes as being the source of reduction of plant heigth, and P1 as source of the increase in root length; P1 and P2 were found with high values of gi for the production of grain. CEC and CGC, showed the action of genes of major aditive effects and prevalence of the traits studies

Segundo o pensamento de Mario Praz, Umberto Eco, Anatol Rosenfeld e muitos outros, as estruturas da obra de arte refletem as estruturas epistemológicas de uma época, acompanhando a evolução das formas de organização sócio-históricas e revelando uma superestrutura de pensamento subjacente a tais formas de organização. No caso de Calvino e de Lins, embora haja inúmeras e enormes diferenças conceituais e estilísticas, é muito clara a passagem de uma visão de mundo (e consequentemente uma resultante forma estética) em que o presente (anos 40-50), embora complexo, é representável como continuidade histórica, a uma nova forma mentis em que a História do presente (anos 60-70), relativizada e desrealizada pelas mudanças técnicas, científicas, culturais, sócio-epistemológicas, é percebida como mosaico de eventos e discursos e, como tal, é representável esteticamente. Percebe-se que as estruturas convencionais (contos e romances), unitárias, íntegras até meados dos anos 60, dão lugar, a partir de 1965 (Calvino) e 1966 (Lins), a uma preferência pelas formas fragmentadas, modulares, recombináveis, hipertextuais, em que os módulos podem ser manipulados pelo leitor para multiplicar as narrativas. Nessa fase da literatura combinatória surgirão obras-primas como Le città invisibili ou Pentágono de Hahn. Essa forma modular combinatória dos anos sessenta evoluirá, nos anos setenta, para uma forma mais complexa: o hiper-romance, cuja estrutura será ainda fortemente amparada na matemática e na geometria. Mas o hiper-romance, além dos elementos combinatórios articuladores da arquitetura romanesca, traz em seu cerne outros elementos fundamentais: a metanarrativa, a busca de um sentido para a representação (do amor e da morte, dos conflitos) e como representação dessa busca; a configuração narrativa do conhecimento como multiplicidade de temas e discursos; a forma da representação como multiplicidade de narrativas realizadas, realizáveis e potenciais; a busca da unidade dos fragmentos na compreensão de uma única Unidade possível: a do mosaico como resposta possível ao labirinto. / According to many authors, especially Mario Praz, Umberto Eco and Anatol Rosenfeld, the structures of a work of art reflect the epistemological structures of a certain period in time, following the evolution of socio-historical organization and revealing a superstructure of thought that comes together with such ways of organization. As far as Calvino and Lins are concerned, notwithstanding the so many conceptual and stylistic differences, their texts of fiction show very clearly the passage from a point of view (and respective esthetic form) in which the present (1940s and 1950s), though complex, can be represented as a historical continuity, to a new point of view in which the History of the present (1960s and 1970s) is understood as relative and fragmented. It is clear that conventional, uniform, whole structures such as short stories and novels, had a unified structure until the mid-sixties, but after 1965 (Calvino) and 1966 (Lins), these structures give place to a fragmented hypertext structures divided into mobile parts that the reader can manipulate and recombine in order to multiply the stories. From this period are masterpieces such as Le città invisivili and Pentágono de Hahn. This combinatory fragmented form from the sixties will evolve, in the seventies, to a more complex form: the hypernovel. The structure of the hypernovel will be strongly based on mathematics and geometry, and it also emphasizes metanarrative, the search for a sense of representation (love and death, for example) and the representation of the search itself. It also seeks to represent knowledge as multiplicity of themes and discourses, combined in fictional stories written and potentially writable. Both authors consider the structure of the novel as important as the story itself, for the structure is their search for the only possible unity: a mosaic, as a possible answer to the labyrinth.

Nesse trabalho, estudamos um problema de otimização combinatorial conhecido por Problema da Mochila Compartimentada, que é uma extensão do clássico Problema da Mochila. O problema consiste em determinar as capacidades adequadas de vários compartimentos que podem vir a ser alocados em uma mochila e como esses compartimentos devem ser carregados, respeitando as restrições de capacidades dos compartimentos e da mochila. Busca-se maximizar o valor de utilidade total. O problema é muito pouco estudado na literatura, apesar de surgir naturalmente em aplicações práticas. Nesse estudo, propomos uma modelagem matemática não linear para o problema e verificamos algumas heurísticas para sua resolução. / In this work, we studied a combinatorial optimization problem called the Clustered Knapsack Problem, that is an extension of the standard Knapsack Problem. The problem is to determine the right capacities of several clusters which can be allocated in a knapsack and how these clusters should be placed so as to respect the constraints on the capacities of the clusters and the knapsack. The objective is to maximize a total utility value. The problem has seldom been studied in the literature, even though it appears naturally in practical applications. In this study, we propose a non-linear model for the problem and we insert some heuristics for its resolution.

O problema de caminhos mínimos (SP shortest path problem) é frequentemente colo- cado em prática em uma grande variedade de aplicações em diversas áreas. Nessas aplicações geralmente se deseja realizar algum tipo de deslocamento ou transporte entre dois ou mais pontos específicos em uma rede. Tal ação deve ser executada de forma ótima em relação a algum critério, por exemplo o menor custo possível, ou o menor gasto de tempo ou o máximo de confiabilidade/segurança. Na prática, muitas vezes não desejamos apenas o menor custo ou o menor tempo, mas desejamos otimizar uma combinação de diferentes critérios, por exemplo, um caminho que seja rápido e barato. Como não é possível otimizar sobre todos os critérios de uma só vez, nós escolhemos um dos critérios para representar a função custo, que será minimizada, e para os demais critérios representamos como recursos e definimos os limites que julgamos aceitáveis para o consumo de cada um desses recursos. Esta variação é cha- mada de problema de caminhos mínimos com restrições por recursos, ou como preferimos chamar, problema de caminhos mínimos com recursos limitados (RCSP resource constrained shortest path problem), o qual será o objeto de estudo neste trabalho. A adição de restrições por recursos no SP, infelizmente torna o problema NP-difícil, mesmo em grafos acíclicos, com restrições sobre um único recurso, e com todos os consu- mos de recursos positivos. Temos reduções dos famosos problemas N P-difíceis Mochila e Partição para o nosso problema. Em contextos diversos são encontrados problemas de cunho teórico e prático que po- dem ser formulados como problemas de caminhos mínimos com recursos limitados, o que nos motivou a estudá-lo a fim de desenvolver um trabalho que resumisse informações sufi- cientes para auxiliar pesquisadores ou desenvolvedores que tenham interesse no problema. Nós apresentamos aqui, uma detalhada revisão bibliográfica do RCSP, tendo como foco o desenvolvimento de algoritmos exatos para o caso onde possuímos um único recurso e a im- plementação e comparação dos principais algoritmos conhecidos, observando-os em situações práticas. / The problem of choosing a route to a trip, where we want minimize the distance of the path is a major problem in computing. In this basic form, this is the shortest path problem. But sometimes, besides the length we need to consider more parameters for selecting a good path. A common parameters to consider is the consumption of resources in a limited budget. A shortest path with these additional constraints is called resource constrained shortest path - RCSP. This paper has two main objectives: to present a literature review of the problem RCSP, focusing on exact algorithms for the case where we have a single resource, and implement and compare some algorithms, observing them in practical situations. The Shortest Path (SP) problem is among the fundamental problems of computer sci- ence. Its been deeply studied and subject of many publications. Also, many efficient solutions (polynomial time algorithms) are known for this problem. The SP is widely applied in many fields of science, not only computer science. These situations usually need to transport a load between two or more specific spots of a network. This action must be taken optimally regarding to some criterion, for instance the least cost, or the least time or maximum relia- bility. While new solutions for SP were presented, new demands were issued too, with new variations for the problem. One of these variations comes from the fact that, in a real scenario, a combination of many criteria must be optimized, for instance a path with least cost and least time. This problem is known as Multiobjective Shortest Path. Since its not possible to optimize all criteria at once, one of them is chosen to represent the cost function to be minimized and the others to represent resources with defined boundary. This variation, known as Resource Constrained Shortest Path (RCSP), was the object of the present study. By adding resource constraints, the SPbecomes N P-hard, even in acyclic graphs with only one resource constrained and all resource consumption being positive. There are reduc- tions from the famous NP-hard problems Knapsack and Partition to our problem. In many fields, are found theoretical and practical problems that may be expressed as a Resource Constrained Shortest Path Problem, which motivated us to study this problem in order to summarize enough information to researchers and developers involved with this problem. This paper presents a detailed bibliographic revision to RCSP, focusing on the development of exact algorithms for the case when there is only only one resource and on the implementation and comparison of the main known algorithms in practical situations.

A partir da reestruturação dos serviços públicos de energia elétrica, foi criada uma série de novas ferramentas regulatórias, simulando e/ou criando um ambiente competitivo, para que as empresas busquem continuamente a evolução de seus indicadores e custos. Com a edição da Resolução nº 024, de 27 de janeiro de 2000, a Agência Nacional de Energia Elétrica (ANEEL) atualizou a regulamentação dos aspectos relativos à continuidade do fornecimento de energia elétrica. As metas de continuidade são definidas através do cluster ao qual cada conjunto de consumidores está vinculado. Os conjuntos são agrupados pelas suas características físicas: área, km de rede primária, número de consumidores, potência de transformadores instalada e consumo médio do conjunto. Um dos pontos focais desta resolução é a possibilidade de uma concessionária agrupar unidades consumidoras, considerando as características técnicas específicas de seu sistema elétrico. Desta forma, o agente regulador permite que as concessionárias modifiquem seus conjuntos de consumidores, desde que fiquem evidenciadas vantagens técnicas, econômicas e sociais da nova proposta em relação ao critério vigente de agrupamento. Visando aperfeiçoar a utilização dos recursos, direcionando as ações para modicidade tarifária e considerando a capacidade de prover condições de atendimento homogêneo, este trabalho busca combinar os consumidores de uma concessionária em conjuntos que minimizem o risco de multa e a necessidade de investimentos nas redes. Este é um problema semelhante ao de redistribuição de eleitores nos distritos de votação nos EUA, conhecido como Political Districting. Para resolver o problema de explosão combinatória resultante das possíveis combinações de áreas e minimizar as multas, o modelo proposto neste trabalho utiliza técnicas de computação evolutiva. A metodologia é ilustrada alterando os 419 conjuntos iniciais de uma concessionária por meio de um algoritmo genético (AG) e um algoritmo imunológico (AI) que otimiza o resultado proposto, minimizando o risco de multas pelo não cumprimento das metas de continuidade. / From the restructuring of the Public Electric Power Sector, new regulatory tools were devised to simulate and create a competitive environment for companies to continuously seek targets for their indicators and costs. With the issue of Resolution nº 024 of January 27, 2000, the National Agency of Electric Energy (ANEEL) updated the rules in dealing with electricity supply continuity. The goals related to the continuity of service are defined through the cluster in which each set of consumers is bound. Consumers are grouped by their physical characteristics: area, length (km) of primary network, the number of consumers, power transformers installed capacity and average consumption. ANEEL allows the utilities to modify their sets of consumers, whenever the technical advantages, economic and social implications of the new proposal in relation to the current criterion of grouping become evident. Considering the possibility of avoiding unnecessary investments in networks, burdening the distribution tariff, this paper attempts to combine the consumers of a utility in sets that minimize the risk of penalties and network investments. This problem is similar to the redistribution in voting districts in the U.S., known as Political Districting. In order to solve the combinatorial explosion problem resulting from the possible combinations of areas and minimization of penalties, the model proposed in this paper uses evolutionary computation techniques. The case study alters the initial 419 sets of consumers of a utility through a genetic algorithm and an artificial immune algorithm, which were proposed to optimize the outcome, minimizing the risk of penalties in not meeting the goals related to continuity of service.

Esta dissertação trata do planejamento do abastecimento de última milha em centros urbanos, propondo métodos para agrupar pedidos de clientes em programação de entregas. Neste estudo, é considerado que o frete pago ao transportador em uma rota é definido pela distância direta do ponto de entrega mais distante do depósito em contraposição à distância total da rota que é usual na literatura sobre problemas de roteirização de veículos. Além disso, também são consideradas categorias, conjunto de produtos similares, que não podem ser transportadas juntas por não serem compatíveis entre si. O objetivo do problema proposto é determinar o agrupamento e sequenciamento de pedidos em roteiros de veículos de acordo com as características operacionais descritas acima, utilizando uma frota homogênea de veículos capacitados que parte de um depósito, de tal forma que toda a demanda seja atendida com o menor frete possível. Para resolução desse problema são propostas uma formulação matemática para obtenção de soluções exatas e a implementação da heurística \"Multi Start Perturbation Tabu\" (MSPT) que é composta das metaheurísticas \"Greedy Randomized Adaptive Search Procedure\" (GRASP), \"Tabu Search\" (TS) e \"Iterated Local Search\" (ILS) para obtenção de soluções heurísticas. Os resultados experimentais indicam que a MSPT é competitiva com os resultados do método exato com até 5 horas de processamento utilizando os recursos computacionais de alto desempenho do Laboratório de Computação Científica Avançada (LCCA) da Universidade de São Paulo. / This dissertation addresses the planning of the last mile supply in urban centers and proposes methods to group customer orders into shipments. In this study, freight paid to the carrier on a route is defined as the direct distance from the point of delivery that is furthest from the depot as opposed to be defined as the total distance of the route which is commonly found in the literature on vehicle routing problems. In addition, it is also considered categories, a set of similar products, which cannot be transported together because they are not compatible with each other. The objective of the proposed problem is to determine the grouping and sequencing of orders into vehicle shipments according to the operational characteristics described above, using a homogeneous fleet of capacitated vehicles that is located in a depot, in such a way that all the demand is delivered with the lowest freight possible. To solve this problem, it is proposed a mathematical formulation to obtain exact solutions and the implementation of the Multi Start Perturbation Tabu (MSPT) heuristic that is composed of the Greedy Randomized Adaptive Search Procedure (GRASP), Tabu Search (TS) and \"Iterated Local Search\" (ILS) for heuristic solutions. Finally, the experimental results indicate that the MSPT is competitive with the outcomes of the exact method with up to 5 hours of processing using the high performance computational resources of the Advanced Scientific Computation Laboratory (LCCA) of the University of São Paulo (USP).

Utiliza-se recombinação de soluções em diversas estratégias de otimização, principalmente aquelas relacionadas a meta-heurísticas populacionais. Operadores de recombinação por decomposição particionam as variáveis de decisão do problema de modo a permitir a decomposição da função de avaliação. Assim, encontra-se, com custo computacional proporcional ao custo de se avaliar uma solução do problema, a melhor solução entre um número de soluções descendentes que cresce exponencialmente com o número de partições encontradas. Recombinação por decomposição foi até aqui utilizada apenas em problemas em que as informações sobre o relacionamento entre as variáveis de decisão são conhecidas a priori. O objetivo principal desta pesquisa de mestrado foi o desenvolvimento de um novo operador de recombinação por decomposição para todos os problemas de otimização pseudo-Booleana. Para isso, foi necessário estimar as ligações entre as variáveis de decisão por meio de procedimentos utilizados em algoritmos de estimação de distribuição e avaliar as partições encontradas pelo novo operador de recombinação. Os resultados encontrados demonstram que o novo operador desenvolvido obteve resultados relevantes para os problemas abordados em relação a geração de novas soluções candidatas por recombinação, em comparação aos demais operadores de recombinação utilizados / The recombination of solutions is important for most of the population meta- heuristics. Recombination by decomposition partitions the decision variables of the problem in order to allow the decomposition of the evaluation function. In this way, it allows to find, with computational cost proportional to the cost of evaluating one solution of the problem, the best solution among a number of offspring solutions that grows exponentially with the number of partitions found by the recombination operator. Recombination by decomposition has been so far used only in problems where the information about the linkage between the decision variables is known. The main objective of this project was the development of new operators of recombination by decomposition for all pseudo-Boolean optimization problems. For this purpose, was necessary to estimate the linkage between the decision variables by using procedures generally employed in estimation of distribution algorithms. Our results show that the new recombination operator obtained significant results for the problems chosen relate to the generation of new solutions by recombination, in comparison to the other recombination operators used

Teorias de campo discretas euclideanas invariantes por transformações que preservam a topologia e o volume dos espaços são estudadas em três dimensões. Teorias com tal simetria são chamadas de quasetopológicas. Os modelos são definidos em diagramas de Heegard, interpretados como uma generalização das triangulações e redes cúbicas. Quando um diagrama descreve uma triangulação, o seu gênero g corresponde ao número de tetraedros. Uma função de partição Z () é atribuída a cada diagrama . Nas teorias quase topológicas, Z() depende apenas de g e da topologia de . Ou seja, as operações de simetria são homeomorfismos que preservam o gênero. Nas triangulações, tem-se invariância por homeomorfismos que preservam o número de tetraedros. Provou-se que tais operações sempre podem ser escritas como composições de três operações elementares, batizadas de moves quase topológicos. Impondo-se invariância de Z pela ação dos moves, chegou-se a um sistema de equações que caracteriza as teorias quasetopológicas. Mostrou-se que a cada álgebra de Hopf corresponde uma solução simples do sistema. Uma nova generalização das álgebras de Hopf foi proposta como ansatz para uma solução mais geral, mas as condições de simetria a reduziram a uma álgebra de Hopf. Nesta generalização, a relação de biálgebra foi substituída por uma relação modificada mais fraca. Identidades tradicionais das álgebras de Hopf deixam de ser verificadas, mas uma série de relações semelhantes foi obtida. A generalização estudada sugere uma família de outras generalizações, com modificações diversas da relação de biálgebra, as quais podem ser usadas na busca de novos exemplos de teorias quasetopológicas. / Euclidean discrete field theories invariant under topology and volume preserving transformations are studied in three-dimensions. Theories with such symmetry are called quasitopological. The models are defined in Heegard diagrams, which are interpreted as a generalization of triangulations and cubic lattices. When a diagram describes a triangulation, its genus g corresponds to the number of tetrahedra. A partition function Z() is assigned to each diagram . In quasitopologica theories, Z() depends only on 9 and on the topology of V. In other words, the symmetry operations are genus preserving homeomorphisms. In the case of triangulations, there is invariance under homeomorphisms which preserve the number of tetrahedra. It was proved that such operatíons can always be written as compositions of three elementary operations, denoted quasitopological moves. Imposing invariance of Z under the action of the moves, a system of equations was found which characterizes quasitopological theories. It was shown that to each Hopf algebra corresponds a simple solution of the equations. A new generalization of Hopf algebras was proposed as an ansatz for a more general solution, but the symmetry conditions reduced it to a Hopf algebra. In this generalization, the bialgebra relation was replaced by an weaker modified one. Traditional identities of Hopf algebras are not verified, but a series of similar relations was obtained. The generalization considered suggests a fami1y of other generalizations, with varied modifications of the bialgebra relatiol1, which can be used in the search for new examples of quasitopological theories.