nÃo hà / Este trabalho foi motivado pela necessidade da exploraÃÃo do potencial do paralelismo distribuÃdo em aplicaÃÃes em OtimizaÃÃo CombinatÃria. Para tanto, propomos uma interface de programaÃÃo distribuÃda, na qual prezamos dois requisitos principais: eficiÃncia e reuso. O primeiro advÃm da necessidade de aplicaÃÃes de CAD exigirem mÃximo desempenho possÃvel. Assim sendo, especificamos esta interface como uma extensÃo da biblioteca MPI, a qual à assumida como eficiente para aplicaÃÃes distribuÃdas. O requisito reuso deve tornar compatÃveis duas caracterÃsticas importantes: assincronismo e operaÃÃes coletivas. O assincronismo deve estar presente na interface, uma vez que as aplicaÃÃes em OtimizaÃÃo CombinatÃria, em sua maioria, possuem uma natureza assÃncrona. OperaÃÃes coletivas sÃo funcionalidades que devem estar disponÃveis na interface, de modo que possam ser utilizadas por aplicaÃÃes em suas execuÃÃes. Tendo em vista atender o requisito reuso, baseamos esta interface nos Modelos de ComputaÃÃo DistribuÃda Dirigidos por Eventos e por Pulsos, pois os mesmos sÃo assÃncronos e permitem a incorporaÃÃo de operaÃÃes coletivas. Implementamos parcialmente a inteface definida neste trabalho. Tendo em vista validar uso desta inteface por aplicaÃÃes em OtimizaÃÃo CombinatÃria, selecionamos duas aplicaÃÃes e as implementamos utilizando a interface. SÃo elas a tÃcnica Branch-and-Bound e o Problema do Conjunto Independente MÃximo (CIM). Fornecemos tambÃm alguns resultados experimentais. / This work was motivated by the need of exploiting the potential of distributed paralelism in combinatorial optimization applications. propose a distributed programming interface, To achieve this goal, we in which we cherish two main requirements: eciency and reuse. The rst stems from the need of HPC (High applications require maximum possible performance. Performance Computing) Therefore, we specify our interface as an extension of the MPI library, which is assumed to be ecient for distributed applications. The reuse requirement must make compatible two important features: asynchronism and collective operations. Asynchronism must be present at our interface, once most of combinatorial optimization applications have an asynchronous nature. Collective operations are features that should be available in the interface, so that they can be used by applications in their execution. In order reach the reuse requirement, we based this interface on the Event- and Pulse-driven Models of Distributed Computing, once they are asynchronous and allow the incorporation of collective operations. We implemented partially the interface dened in this work. In order to validate the use of the inteface by combinatorial optimization applications, we selected two applications and implemented them using our interface. They are the Branch-and-Bound technique and the Maximum Stable Set Problem (MSSP). We also provide some experimental results.

Submitted by Erika Demachki (erikademachki@gmail.com) on 2014-08-28T17:57:43Z No. of bitstreams: 2 FINALTCC_Karina 2.pdf: 867852 bytes, checksum: 5d14f3376d96066f3e7ef54c93d60d6b (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2014-08-28T17:57:43Z (GMT). No. of bitstreams: 2 FINALTCC_Karina 2.pdf: 867852 bytes, checksum: 5d14f3376d96066f3e7ef54c93d60d6b (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2013-03-01 / The objective of this work is to address the Combinatorial Analysis as a theme that can be treated in the classroom, without the utilization of mathematical formulas in problem solving. For this it will presented a method of reasoning that, basing on logic and languages, underscores the importance of: To read, interpret and analyze texts that are presented in the mother tongue; Formulate conjectures, make choices and seek strategies of count; and Make the correct translation between languages maternal and mathematics. Expected to show from this approach that the Combinatorial Analysis, besides its importance in various elds of knowledge, may also be seen by students and teachers as a challenging and stimulating content. / O objetivo deste trabalho é abordar a Análise Combinatória como um tema que pode ser tratado, em sala de aula, sem a utilização de fórmulas matemáticas na resolução de problemas. Será apresentado um método de raciocínio que, baseando-se em Lógica e Linguagens, destaca a importância de: Ler, interpretar e analisar textos que se apresentam em língua materna; Formular conjecturas, fazer escolhas e buscar estratégias de contagem; e Fazer a tradução correta entre as linguagens materna e matemática. Espera-se mostrar, a partir desta abordagem, que a Análise Combinatória, além da sua importância em vários campos do conhecimento, também pode ser encarada, por estudantes e professores, como um conteúdo desa ador e estimulante.

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.

Submitted by Rosivalda Pereira (mrs.pereira@ufma.br) on 2017-09-12T20:25:13Z No. of bitstreams: 1 PabloImperio.pdf: 1334880 bytes, checksum: 04f05e0c6089e9173666f70f591bba35 (MD5) / Made available in DSpace on 2017-09-12T20:25:13Z (GMT). No. of bitstreams: 1 PabloImperio.pdf: 1334880 bytes, checksum: 04f05e0c6089e9173666f70f591bba35 (MD5) Previous issue date: 2017-03-04 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This work uses GeoGebra software (version 5.0.328.0-3D) as a tool to solve counting problems. Some elements of combinatorial analysis and insertion of objects in the software are presented, motivating its use in solving counting problems and including practical classroom applications in classroom. In order to obtain data about problem solving, classes were taught with and without the use of GeoGebra in two different classes and also the results were compared. It was verified that the use of the software helps to understand the concepts, since it works the dynamicity, allowing the student to modify the results and draw conclusions. / Este trabalho utiliza o software GeoGebra (versão 5.0.328.0-3D) como ferramenta na resolução de problemas de contagem. São apresentados alguns elementos de análise combinatória e inserção de objetos no software, motivando sua utilização na resolução de problemas de contagem e incluindo aplicações prática em sala de aula. Para obtenção de dados sobre a resolução de problemas, foram ministradas aulas com e sem o uso do GeoGebra em duas turmas distintas e comparados os resultados. Verificou-se que a utilização do aplicativo ajuda a compreender os conceitos, visto que trabalha a dinamicidade, possibilitando ao aluno modificar os resultados e tirar conclusões.

Submitted by Daniella Santos (daniella.santos@ufma.br) on 2017-11-23T11:57:53Z No. of bitstreams: 1 MAKEBENIGNO.pdf: 503602 bytes, checksum: 341b1fad0eebf1c68b8ab490776354c0 (MD5) / Made available in DSpace on 2017-11-23T11:57:53Z (GMT). No. of bitstreams: 1 MAKEBENIGNO.pdf: 503602 bytes, checksum: 341b1fad0eebf1c68b8ab490776354c0 (MD5) Previous issue date: 2017-03-06 / This work will present the importance of combinatorial analysis, both in middle school and elementary school. We will list several exemples of problems involving combinatorial analysis and we will see how the subject and matter is charged in Enem and mathematics Olympics. Basic, we present some of the main difficulties of some students and combinatoy, shows how the teacher can teach through the solution of the problems, basic that we will present the situation of mathematical education in Brazil and its packaging of basic education. / Este trabalho tem como objetivo apresentar a importância da análise combinatória, tanto no Ensino Médio como no Ensino Fundamental. Listaremos vários exemplos de problemas envolvendo análise combinatória e veremos como esse assunto é cobrado no ENEM e em olimpíadas de matemática. Além disso, apresentamos algumas das principais dificuldades dos alunos em combinatória, e como o professor poderá ensinar por meio da resolução de problemas, além disso apresentaremos a situação da educação matemática no Brasil e seus impactos no ensino básico.

We study the relationship between geometric properties of toric varieties and combinatorial properties of the corresponding lattice polytopes. In particular, we give a bound for a very ample lattice polytope to be k-normal. Equivalently, we give a new combinatorial bound for the Castelnuovo-Mumford regularity of normal projective toric varieties. We also give a new combinatorial proof for a special case of Reider's Theorem for smooth toric surfaces.

The main goal of a scheduling process is to decide when and how to execute each of the project's activities. Despite large variety of researched scheduling problems, the majority of them can be described as generalisations of the resource-constrained project scheduling problem (RCPSP). Because of wide applicability and challenging difficulty, RCPSP has attracted vast amount of attention in the research community and great variety of heuristics have been adapted for solving it. Even though these heuristics are structurally different and operate according to diverse principles, they are designed to obtain only one solution at a time. In the recent researches on RCPSPs, it was proven that these kind of problems have complex multimodal fitness landscapes, which are characterised by a wide solution search spaces and presence of multiple local and global optima. The main goal of this thesis is twofold. Firstly, it presents a variation of the RCPSP that considers optimisation of projects in an uncertain environment where resources are modelled to adapt to their environment and, as the result of this, improve their efficiency. Secondly, modification of a novel evolutionary computation method Cuckoo Search (CS) is proposed, which has been adapted for solving combinatorial optimisation problems and modified to obtain multiple solutions. To test the proposed methodology, two sets of experiments are carried out. Firstly, the developed algorithm is applied to a real-life software development project. Secondly, the performance of the algorithm is tested on universal benchmark instances for scheduling problems which were modified to take into account specifics of the proposed optimisation model. The results of both experiments demonstrate that the proposed methodology achieves competitive level of performance and is capable of finding multiple global solutions, as well as prove its applicability in real-life projects.

In the present thesis we provide compact extended formulations for a wide range of polytopes associated with the constraint satisfaction problem (CSP), monadic second order logic (MSO) on graphs, and extensions of MSO, when the given instances have bounded treewidth. We show that our extended formulations have additional useful properties, and we uncover connections between MSO and CSP. We conclude that a combination of the MSO logic, CSP and geometry provides an extensible framework for the design of compact extended formulations and parameterized algorithms for graphs of bounded treewidth. Putting our framework to use, we settle the parameterized complexity landscape for various extensions of MSO when parameterized by two important graph width parameters, namely treewidth and neighborhood diversity. We discover that the (non)linearity of the MSO extension determines the difference between fixedparameter tractability and intractability when parameterized by neighborhood diversity. Finally, we study shifted combinatorial optimization, a new nonlinear optimization framework generalizing standard combinatorial optimization, and provide initial findings from the perspective of parameterized complexity

Remote sensors and unmanned aerial vehicles (UAVs) have the potential to dramatically improve infrastructure health monitoring in terms of accuracy of the information and frequency of data collection. UAV automation has made significant progress but that automation is also creating vast amounts of data that needs to be processed into actionable information. A key aspect of this work is the optimization (not just automation) of data collection from UAVs for targeted planning of mission objectives. This work investigates the use of camera planning for Structure from Motion for 3D modeling of infrastructure. Included in this thesis is a novel multi-scale view-planning algorithm for autonomous targeted inspection. The method presented reduced the number of photos needed and therefore reduced the processing time while maintaining desired accuracies across the test site. A second focus in this work investigates various set covering problem algorithms to use for selecting the optimal camera set. The trade-offs between solve time and quality of results are explored. The Carousel Greedy algorithm is found to be the best method for solving the problem due to its relatively fast solve speeds and the high quality of the solutions found. Finally, physical flight tests are used to demonstrate the quality of the method for determining coverage. Each of the set covering problem algorithms are used to create a camera set that achieves 95% coverage. The models from the different camera sets are comparable despite having a large amount of variability in the camera sets chosen. While this study focuses on multi-scale view planning for optical sensors, the methods could be extended to other remote sensors, such as aerial LiDAR.

Remote sensors and unmanned aerial vehicles (UAVs) have the potential to dramatically improve infrastructure health monitoring in terms of accuracy of the information and frequency of data collection. UAV automation has made significant progress but that automation is also creating vast amounts of data that needs to be processed into actionable information. A key aspect of this work is the optimization (not just automation) of data collection from UAVs for targeted planning of mission objectives. This work investigates the use of camera planning for Structure from Motion for 3D modeling of infrastructure. Included in this thesis is a novel multi-scale view-planning algorithm for autonomous targeted inspection. The method presented reduced the number of photos needed and therefore reduced the processing time while maintaining desired accuracies across the test site. A second focus in this work investigates various set covering problem algorithms to use for selecting the optimal camera set. The trade-offs between solve time and quality of results are explored. The Carousel Greedy algorithm is found to be the best method for solving the problem due to its relatively fast solve speeds and the high quality of the solutions found. Finally, physical flight tests are used to demonstrate the quality of the method for determining coverage. Each of the set covering problem algorithms are used to create a camera set that achieves 95% coverage. The models from the different camera sets are comparable despite having a large amount of variability in the camera sets chosen. While this study focuses on multi-scale view planning for optical sensors, the methods could be extended to other remote sensors, such as aerial LiDAR.