Funções submodulares aparecem naturalmente em diversas áreas, tais como probabilidade, geometria e otimização combinatória. Pode-se dizer que o papel desempenhado por essas funções em otimização discreta é similar ao desempenhado por convexidade em otimização contínua. Com efeito, muitos problemas em otimização combinatória podem ser formulados como um problema de minimizar uma função submodular sobre um conjunto apropriado. Além disso, submodularidade está presente em vários teoremas ou problemas combinatórios e freqüentemente desempenha um papel essencial em uma demonstração ou na eficiência de um algoritmo. Nesta dissertação, estudamos aspectos estruturais e algorítmicos de funções submodulares, com ênfase nos recentes avanços em algoritmos combinatórios para minimização dessas funções. Descrevemos com detalhes os primeiros algoritmos combinatórios e fortemente polinomiais para esse propósito, devidos a Schrijver e Iwata, Fleischer e Fujishige, além de algumas outras extensões. Aplicações de submodularidade em otimização combinatória também estão presentes neste trabalho. / Submodular functions arise naturally in various fields, including probability, geometry and combinatorial optimization. The role assumed by these functions in discrete optimization is similar to that played by convexity in continuous optimization. Indeed, we can state many problems in combinatorial optimization as a problem of minimizing a submodular function over an appropriate set. Moreover, submodularity appears in many combinatorial theorems or problems and frequently plays an essencial role in a proof or an algorithm. In this dissertation, we study structural and algorithmic aspects of submodular functions. In particular, we focus on the recent advances in combinatorial algorithms for submodular function minimization. We describe in detail the first combinatorial strongly polynomial-time algorithms for this purpose, due to Schrijver and Iwata, Fleischer, and Fujishige, as well as some extensions. Some applications of submodularity in combinatorial optimization are also included in this work.

Made available in DSpace on 2011-03-23T21:19:33Z (GMT). No. of bitstreams: 0 / Item created via OAI harvest from source: http://www.bdtd.ufpa.br/tde_oai/oai2.php on 2011-03-23T21:19:33Z (GMT). Item's OAI Record identifier: oai:bdtd.ufpa.br:243 / We discussed, in this work, a proposal of use of the history of the mathematics, as previous organizer, for the teaching of the combination analysis and of the probability. That use of the history of the mathematics has as objective to develop the knowledge subsumers, presents in the students' cognitive structure, so that it can happen, in a significant way, the learning of the concepts of those topics of the mathematics, and that they will be taught, in a more detailed way, later on, through the conceptual maps. It is worth to stand out that, the previous organizers' of the content use, as well as the theory of the conceptual maps, they have theoretical justification in the works on significant learning, of the educational psychologist David P. Ausubel. / Discutimos, neste trabalho, uma proposta de utilização da história da matemática, como organizador prévio, para o ensino da análise combinatória e da probabilidade. Esse uso da história da matemática tem como objetivo desenvolver os conhecimentos subsunçores, presentes na estrutura cognitiva dos alunos, para que possa ocorrer, de forma significativa, a aprendizagem dos conceitos desses tópicos da matemática, e que serão ensinados, de modo mais detalhado, posteriormente, através dos mapas conceituais. Vale ressaltar que, a utilização dos organizadores prévios do conteúdo, assim como a teoria dos mapas conceituais, têm fundamentação teórica nos trabalhos sobre aprendizagem significativa, do psicólogo educacional David P. Ausubel.

Orientador: Karla Vittori / Dissertação (mestrado) - Universidade Federal do ABC. Programa de Pós-Graduação em Ciência da Computação, 2013

Submitted by Jean Medeiros (jeanletras@uepb.edu.br) on 2016-05-11T13:46:12Z No. of bitstreams: 1 PDF - Ubieli Alves Araújo Vasconcelos.pdf: 1747559 bytes, checksum: 9c92c8208f13fd0636cc2431631976dc (MD5) / Approved for entry into archive by Secta BC (secta.csu.bc@uepb.edu.br) on 2016-07-21T20:46:01Z (GMT) No. of bitstreams: 1 PDF - Ubieli Alves Araújo Vasconcelos.pdf: 1747559 bytes, checksum: 9c92c8208f13fd0636cc2431631976dc (MD5) / Approved for entry into archive by Secta BC (secta.csu.bc@uepb.edu.br) on 2016-07-21T20:46:10Z (GMT) No. of bitstreams: 1 PDF - Ubieli Alves Araújo Vasconcelos.pdf: 1747559 bytes, checksum: 9c92c8208f13fd0636cc2431631976dc (MD5) / Made available in DSpace on 2016-07-21T20:46:10Z (GMT). No. of bitstreams: 1 PDF - Ubieli Alves Araújo Vasconcelos.pdf: 1747559 bytes, checksum: 9c92c8208f13fd0636cc2431631976dc (MD5) Previous issue date: 2016-02-24 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / Cotton is a crop of large economic value at worldwide. The Brazilian production is around 1.5 million tons, coming mainly from the Mid West, Southeast and Northeast region, specially Cerrado areas. Despite to importance of crop to Brazil, there is a broad demand to investment in breeding area focusing on selection of promising genotypes as to yield and regional adaptation. In order to attend this demand, breeding programs have focused on generation of different lines by hybridization, using robust genitors, aiming broaden the genetic background of the lines and to favor the selection procedures. In this study we used 20 cotton lines, obtained through diallel crosses with parents of Moco and herbaceous types, aiming to estimate the GCC and SCC in materials tolerant to drought, based on agronomic traits. The study was carried out in semiarid environment, at Barbalha Station, CE, in dry season, using water supplementation. After the appearance of the first buds, plants were subjected to 23 days of water suppression, and re-established watering thereafter. The experimental design was randomized blocks, with 20 treatments and factorial scheme (20 x 2), and three replications. The variables evaluated were: plant height, Productivity, fiber percentage, Boll weight, Rising of first flower and Rising of first boll. Additionally, total chlorophyll content in leaves was determined. The statistical analysis wasperformed by GENE program. Analyses of combinatorial capacities were performed according to the method adapted by Griffing (1956), which estimates the effects of GCC of each parent and the effects of SCC. There was wide variation between the parents for the analyzed variables. The follow parents showed best estimates of GCA, and therefore, have more favorable alleles, based on traits studied: BRS 286, CNPA 5M and CNPA 7MH. To SCC, the hybrids BRS 286 X CNPA 5M, BRS RUBI X CNPA 5M and BRS 286 X BRS Serido demonstrated complementarity Plant hight and porductivity. The estimates of GCC and SCC presented in this paper provided valuable inputs to cotton improvement, as to both parents and hybrid selections. / O algodão é uma cultura de grande importância econômica mundialmente. No Brasil a produção encontra-se na faixa de 1,5 milhões de toneladas, oriundas principalmente das regiões Centro - Oeste, Sudeste e Nordeste, com maior área situada nos Cerrados. Apesar do crescimento da cultura em nível nacional, há necessidade de investimento na área de melhoramento genético com fins de selecionar genótipos promissores para produção e adaptação regional. Para tanto, os programas de melhoramento têm focalizado na geração de linhagens divergentes, por meio de hibridações com progenitores robustos, de modo a ampliar a base genética das linhagens e favorecer os procedimentos de seleção. Nesse trabalho utilizou-se uma população composta de 20 híbridos de algodão, obtida via cruzamentos dialelicos com genitores dos tipos arbóreo e herbáceo, objetivando estimar as CGC e CEC dos materiais tolerantes a seca, focalizando em caracteres agronômicos. O trabalho foi conduzido em ambiente semiárido, em Barbalha, CE, em regime de sequeiro com complementação hídrica.Após o surgimento dos primeiros botões florais, as plantas foram submetidas a 23 dias de supressão hídrica, sendo restabelecidas as regas após esse período. O delineamento experimental adotado foi de blocos ao acaso, com 20 tratamentos, com esquema fatorial 20 x 2, e três repetições. As variáveis avaliadas foram: Altura de planta, Produtividade, Percentagem de fibras, Peso de um capulho, Surgimento da primeira flor e Surgimento da primeira maçã. Adicionalmente, determinou-se o teor de Clorofila total nas folhas. As analises estatísticas foram realizadas pelo programa GENES. As análises das capacidades combinatórias foram realizadas de acordo com o modelo adaptado por Griffing (1956), que estima os efeitos da capacidade geral de combinação CGC de cada parental e os efeitos da capacidade específica de combinação CEC. Verificou-se ampla variabilidade entre os genitores para as variáveis analisadas. Os genitores que apresentaram as melhores estimativas de CGC e com maior número de alelos favoraveis para as principais características estudadas foram BRS 286, CNPA 5M e CNPA 7MH, enquanto que para CEC, os híbridos BRS 286 X CNPA 5M, BRS RUBI X CNPA 5M e BRS 286 X BRS SERIDO destacaram-se por demonstrar melhores estimativas de CEC e complementaridade para ALT e PROD em condições de estresse hídrico. As estimativas de CGC e CEC ofereceram contribuições valiosas no processo de seleção no melhoramento genético, tanto de genitores como de combinações hibridas.

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.

Estudamos o comportamento da familia aresta-triangulo de grafos aleatorios exponenciais (ERG) usando metodos de Monte Carlo baseados em Cadeias de Markov. Comparamos contagens de subgrafos e correlacoes entre arestas de ergs as de Grafos Aleatorios Binomiais (BRG, tambem chamados de Erdos-Renyi). E um resultado teorico conhecido que para algumas parametrizacoes os limites das contagens de subgrafos de ERGs convergem para os de BRGs, assintoticamente no numero de vertices [BBS11, CD11]. Observamos esse fenomeno em grafos com poucos (20) vertices em nossas simulacoes. / We study the behavior of the edge-triangle family of exponential random graphs (ERG) using the Markov Chain Monte Carlo method. We compare ERG subgraph counts and edge correlations to those of the classic Binomial Random Graph (BRG, also called Erdos-Renyi model). It is a known theoretical result that for some parameterizations the limit ERG subgraph counts converge to those of BRGs, as the number of vertices grows [BBS11, CD11]. We observe this phenomenon on graphs with few (20) vertices in our simulations.

No description available.