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

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

La théorie de la NP-complétude nous apprend que pour un certain nombre de problèmes d'optimisation, il est vain d'espérer un algorithme efficace calculant une solution optimale. Partant de ce constat, un moyen pour contourner cet obstacle est de réaliser un compromis sur chacun de ces critères, engendrant deux approches devenues classiques. La première, appelée approximation polynomiale, consiste à développer des algorithmes efficaces et retournant une solution proche d'une solution optimale. La seconde, appelée complexité paramétrée, consiste à développer des algorithmes retournant une solution optimale mais dont l'explosion combinatoire est capturée par un paramètre de l'entrée bien choisi. Cette thèse comporte deux objectifs. Dans un premier temps, nous proposons d'étudier et d'appliquer les méthodes classiques de ces deux domaines afin d'obtenir des résultats positifs et négatifs pour deux problèmes d'optimisation dans les graphes : un problème de partition appelé Sparsest k-Compaction, et un problème de recherche d'un sous-graphe avec une cardinalité fixée appelé Sparsest k-Subgraph. Dans un second temps, nous présentons comment les méthodes de ces deux domaines ont pu se combiner ces dernières années pour donner naissance au principe d'approximation paramétrée. En particulier, nous étudierons les liens entre approximation et algorithmes de noyaux. / The theory of NP-completeness tells us that for many optimization problems, there is no hope for finding an efficient algorithm computing an optimal solution. Based on this, two classical approaches have been developped to deal with these problems. The first one, called polynomial- time approximation, consists in designing efficient algorithms computing a solution that is close to an optimal one. The second one, called param- eterized complexity, consists in designing exact algorithms which com- binatorial explosion is captured by a carefully chosen parameter of the instance. The goal of this thesis is twofold. First, we study and apply classical methods from these two domains in order to obtain positive and negative results for two optimization problems in graphs: a partitioning problem called Sparsest k-Compaction, and a cardinality constraint subgraph problem called Sparsest k-Subgraph. Then, we present how the different methods from these two domains have been combined in recent years in a concept called parameterized approximation. In particular, we study the links between approximation and kernelization algorithms.

Dans cette thèse, nous proposons une approche combinatoire novatrice fondée sur les matroïdes orientés pour l'étude quantitative de la forme de structures anatomiques 3D. Nous nous basons sur des points de repère qui ont été préalablement localisés par des experts sur la structure anatomique étudiée. La nouveauté de cette méthode provient de l'utilisation de matroïdes orientés. Ces outils mathématiques nous permettent de coder la position relative des points de repère de façon purement combinatoire, c'est-à-dire sans utiliser de notions d'angles ou de distances, en associant un signe (0, + ou -) à chaque sous-ensemble de (d+1) points de repère où d est la dimension de l'espace (dans notre cas 2 ou 3). Dans une première partie, nous supposons qu'il existe des contraintes d'ordres sur chaque axe de coordonnée pour les points de repère. Nous obtenons alors une caractérisation (en dimension 2 et 3) des sous-ensembles de points de repère dont le signe associé est constant, quelles que soient les valeurs des coordonnées satisfaisant les contraintes d'ordre. Dans une deuxième partie, nous cherchons à classifier un ensemble de modèles 3D, en les codant au préalable par ces listes de signes. Nous analysons d'abord comment s'appliquent les algorithmes de clustering classiques, puis nous décrivons comment caractériser des classes de façon directe, à l'aide des signes associés à quelques sous-ensembles de points de repère. Dans une troisième partie, nous détaillons les algorithmes et l'implémentation en machine de cette nouvelle méthode de morphométrie afin de pouvoir l'appliquer à des données réelles. Dans la dernière partie, nous appliquons la méthode sur trois bases de données composées chacune de plusieurs dizaines de points de repères relevés sur plusieurs dizaines à plusieurs centaines de structures crâniennes pour des applications en anatomie comparée, en orthodontie et sur des cas cliniques d'enfants présentant des déformations cranio-faciales. / In this thesis, we propose an innovative combinatorial method based on oriented matroids for the quantitative study of the shape of 3D anatomical structures. We rely on landmarks which were previously defined by experts on the studied anatomical structure. The novelty of this method results from the use of oriented matroids. These mathematical tools allow us to encode the relative position of landmarks in a purely combinatorial way, that is without using concepts of angles or distances, by associating a sign (0, + or -) for each subset of (d+1) landmarks where d is the dimension of space (in our case 2 or 3). In the first part, we assume that there exist constraints of orders on each coordinate axis for the landmarks. We obtain a characterization (in dimension 2 and 3) of the subsets of landmarks of which the associated sign is constant, regardless of the values of the coordinates satisfying the constraints of order. In a second part, we try to classify a set of 3D models, encoding in advance by these lists of signs. We first analyze how to apply classic clustering algorithms, and then describe how to characterize the classes directly, using signs associated with some subsets of landmarks. In the third part, we explain the algorithms and the implementation of this new morphometry method in order to apply it to real data. In the last part, we apply the method to three databases each consisting of several dozens of points defined on several dozens to several hundreds of cranial structures for applications in comparative anatomy, in orthodontics and on clinical cases of children with craniofacial deformities.

Au cours de la thèse, nous nous sommes intéressés aux problèmes d'empilement de wafers. Ces problèmes apparaissent lors de la fabrication de processeurs en 3 dimensions. Au cours du processus de fabrication, les puces électroniques doivent être empilées les unes sur les autres. Jusqu'à peu, ces dernières, une fois gravées sur des plaques de silicium appelées wafers, étaient découpées, puis triées afin d'écarter les puces défectueuses et enfin assemblées les unes entre elles.Cependant empiler les wafers plutôt que les puces présente de nombreux avantages techniques et financiers. Naturellement, étant impossible d'écarter les puces défectueuses sans découper la plaque de silice, le problème de la superposition d'une puce viable avec une puce défectueuse se pose. Une pile de puces, étant considérées comme défectueuse si elle contient ne serait-ce qu'une puce défectueuse, la superposition non réfléchie des wafers entre eux mènerait à un rendement désastreux.Afin de générer un nombre minimum de piles défectueuses, une "cartographie" de chaque wafer candidat à la superposition est réalisée lors d'une phase de test, permettant de situer les puces défectueuses sur le wafer. Une fois cette cartographie réalisée, l'objectif est de sélectionner les wafers qui seront assemblés ensembles de manière à faire correspondre les défauts de chacun des wafers.Ce problème peut être modélisé à l'aide d'un problème d'affectation multidimensionnelle. Chaque wafer est représenté par un vecteur comportant autant de composantes que de puces sur le wafer qu'il représente. Une composante égale à zéro matérialise une puce défectueuse tandis qu'un un matérialise une puce viable. Chaque lot de wafers est représenté par un lot de vecteurs. Formellement, une instance d'empilement de wafers est représenté par m ensembles de n vecteurs binaires p-dimensionnels. L'objectif est alors de réaliser n m-uplets disjoints contenant exactement un vecteur par ensemble. Ces m-uplets représenteront les piles. Chaque m-uplet peut être représenté par un vecteur binaire p-dimensionnels, chaque composante étant calculée en réalisant le ET binaire des composantes correspondantes des vecteurs qui composent le m-uplet. Autrement dit, une composante du vecteur représentant le m-uplet est égale à un si et seulement si tous les vecteurs ont cette composante égale à un. Et donc une pile de puces est viables si toutes les puces qui la composent sont viables. L'objectif est alors de minimiser le nombre de zéros ou de maximiser le nombre de un.La thèse comporte deux grandes parties. Une partie théorique abordant la complexité des différentes versions du problèmes en fonction de certains paramètres tels que m, n, p ou encore le nombre maximum de zéros par vecteurs. Nous montrons entre autre que ces problèmes peuvent être utilisés pour modéliser des problèmes plus classiques tels que Maximum Clique, Minimum Vertex Cover ou encore k-Dimensional Matching, permettant de prouver un certain nombre de résultats négatifs que ce soit d'un point de vue de la complexité classique, l'approximabilité ou la complexité paramétrée. Nous fournissons également des résultats positifs pour des cas particuliers du problème.Dans un second temps, nous nous intéressons à la résolution pratique du problème en fournissant et comparant un certain nombre de formulations en Programmation Linéaire en Nombres Entiers. Mais nous nous intéressons également aux performances en pratique de certaines heuristiques à garantie de performances détaillées dans la partie théorique. / In this thesis, we focused in the Wafer-to-Wafer integration problems. These problems come from IC manufacturing. During the production of three-dimensional processors, dies have to be superimposed. Until recent, the dies were engraved on a silicon disk called wafer, then were cut, tested and sorted to suppress faulty dies and lastly superimposed one to each other.However superimposing wafers instead of dies presents several technical and financial advantages. Since faulty dies can only be dismissed when cutting the wafer, superimpose two wafers can lead to superimpose a faulty die with a viable one. In this case, the resulting stack of dies is considered as faulty. It follows that a bad assignment between the wafers can lead to a disastrous yield.In order to minimize the number of faulty dies stacks, a "failure map" of each wafer is generated during a test phase. This map gives location of the faulty dies on the wafers. The objective is then to take advantage of this map to define an assignment of the wafers to each other in order to match as many failures as possible.This problem can be modelized with Multidimensional Assignment problems. Each wafer can be seen as a vector with as many dimensions as the number of dies engraved on it. A coordinate set to zero marks a faulty die while a coordinate set to one indicates a viable one. Each seat of wafers is represented by a set of vector. Formally, an instance of a Wafer-to-Wafer integration problem is represented by m sets of n p-dimensional vectors. The objective is then to partition the vectors into n disjoint m-tuples, each tuple containing exactly one vector per set. An m-tuple represents a stack of wafers. Every m-tuple can be represented by a p-dimensional vector. Each coordinate is computed by performing the bitwise AND between the corresponding coordinates of the vectors that compose the m-tuple. In other words, a coordinate of the representative vector is equal to one if and only if this coordinate is equal to one in every vector composing the tuple. It follows that a dies stack is viable if and only if all the dies composing the stack are viable. The objective is then to maximize the overall number of ones of to minimize the overall number of zeros.The first part of the thesis is a theoretical one. We study the complexity of the considered versions of the problem with regards to natural parameters such as m, n, p or the number of zeros per vector. We show that these problems can encode more classical problems such as Maximum Clique, Minimum Vertex Cover or k-Dimensional Matching. This leads to several negative results from computational complexity, approximability or even parameterized complexity point of view. We also provide several positive results for some specific cases of the problem.In a second part, we focus on the practical solving of the problem. We provide and compare several Integer Linear Programming formulations. We also focus on performances of some approximation algorithms that we detailed in the theoretical part.

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.