Made available in DSpace on 2016-06-02T20:02:57Z (GMT). No. of bitstreams: 1 6432.pdf: 3122043 bytes, checksum: 082819afaa3a0b58bb6c250635b34e25 (MD5) Previous issue date: 2014-11-10 / This research has as main objective making a manipulative material to work sequences of activities by introducing the notion of Combinatorial Analysis in an intuitive and natural way in elementary school final years. Without using formulas, it presents an encouragement to use the Multiplicative Principle, tree diagram and list of possibilities as an important tool for solving various problems. We started the research making a description of the current curriculum documents in the Department of Education of the State of São Paulo, followed by historical overview and theoretical foundation. The survey was developed with the implementation of three activities with students from the 5th grade - 6 year to 8th grade - 9th year of elementary school in a Public State School in the city of Sorocaba/SP. These activities were designed to find out the students difficulties in the development of problems involving Combinatorial reasoning and to propose manipulative materials at low cost and to help in the construction and understanding of that content, since a big part of students and teachers consider it difficult to understand. These manipulative materials represent the final product of this research and it is hoped that teachers use them in their classrooms to make their classes more dynamic, rich and arousing the interest of the students. / A presente pesquisa tem como objetivo principal a confecção de material manipulável para trabalhar sequências de atividades introduzindo de maneira intuitiva e natural a noção de Análise Combinatória no Ensino Fundamental Anos Finais sem a utilização de fórmulas, incentivando o uso do Princípio Multiplicativo, do diagrama de árvore e da enumeração das possibilidades como uma ferramenta importante para a resolução de vários problemas. Iniciamos a pesquisa fazendo uma descrição dos documentos curriculares vigentes na Secretaria da Educação do Estado de São de São Paulo, seguida por um panorama histórico e fundamentação teórica. A pesquisa foi desenvolvida com a aplicação de três atividades com alunos da 5ª série/6º ano a 8ª série/9º ano do Ensino Fundamental de uma Escola Pública Estadual da cidade de Sorocaba/SP. Essas atividades foram elaboradas com o objetivo de constatar as dificuldades dos alunos no desenvolvimento de problemas que envolvam o raciocínio combinatório e propor materiais manipulativos, de baixo custo, que auxiliem na construção e compreensão desse conteúdo, considerados de difícil entendimento por grande parte de alunos e professores. Esses materiais manipulativos representam o produto final dessa pesquisa e espera-se que os professores o utilizem em suas salas de aulas para tornar suas aulas mais ricas e dinâmicas despertando o interesse dos alunos.

Made available in DSpace on 2015-03-26T13:39:57Z (GMT). No. of bitstreams: 1 texto completo.pdf: 1146337 bytes, checksum: 9edc6a735d40be51b2865d311e2d3f55 (MD5) Previous issue date: 2013-07-16 / Conselho Nacional de Desenvolvimento Científico e Tecnológico / The objective of this study was to evaluate the quality of the forage and the silage fermentation profile made exclusively from Luziânia, Sambaíba, Tucunaré and UFV 16 cultivars. This profile was also made from UFVS 2003 of 10 intersections obtained from these cultivars and from the lineages TMG 801, tolerant to rust, UFVTN 105 AP, with high protein, and Vx 05-3027, Vx 05-3166 and Vx 05-3600, which are resistant to the Glyphosate herbicide action. The crosses were obtained from a complete diallel design, with fixed models and with the inclusion of parents and Fn s (method 2), as well carried out to the current generation.Two experiments were assembled with plants of F7 and F8 generations, in the years 2011/12 and 2012/13, respectively. Each selected plant in generation F7 consisted of a F8 generation line. The harvest occurred when the plants achieved the R6 stage for their silage, with the opening of the silos 60 days later. Forage chemical analyses before the silage were made at the Animal Nutrition Laboratory, in the Animal Science Department of the Federal University in Viçosa. Plant high and fresh mass were measured in generation F7, and the productivity of the dry mass was calculated per hectare. Dry and organic matter, ash, ethereal extract, crude protein, soluble carbohydrates, fiber in neutral and in acid detergent, and lignin in samples before and after the silage, are some of the things that were analyzed by the study.Ammonia nitrogen, pH and organic acids were analyzed just at the silage. As done in the generation F7, plant high and fresh mass were also measured in generation F8. The productivity of the dry mass was as well calculated. The variables were submitted to variance and diallelical analyzes, besides of the phenotypic, genotypic and environmental correlations between them. It was possible to obtain the populations that were favorable to the silage production and, consequently, to probable soybean cultivars, which are appropriated for this silage development. An example is the crossing between Sambaíba X Tucunaré, which brought together the most favorable characteristics, and showed that it is capable of generating increases in the CHOS tenor, and also of reducing the LIG, pH, N-NH3/NTotal, ACE tenors. At the same time this crossing is capable of raising the LAT and the UFV 16 X UFVS 2003 crossing conciliated a reduced tenor of EE and N-NH3/NTotal, with elevated CHOS tenor.UFV-TN 105 and Vx 05-3166 lineages conciliated elevated MS, PB, CHOS tenor and reduced RR tenor, showing that they are capable of being included in breeding programs, aiming the selection of soybean forage. / Procurou-se avaliar a qualidade de forragem e o perfil fermentativo da silagem exclusiva feita a partir dos cultivares Luziânia, Sambaíba, Tucunaré, UFV 16, UFVS 2003 dos 10cruzamentos obtidos a partir desses cultivarese das linhagens TMG 801 (tolerante à ferrugem), UFVTN 105 AP (alta proteína), Vx 05-3027(RR),Vx 05-3166(RR) e Vx 05-3600(RR), estes últimos resistentes à ação do herbicida Glyphosate. Os cruzamentos foram obtidos a partir de dialelo completo, com modelos fixos e a inclusão dos genitores e F1s(método 2), e realizados até a atual geração. Foram montados dois experimentos, com plantasdas gerações F7 e F8,nos anos agrícolas 2011/12 e 2012/13, respectivamente. Cada planta selecionada na geração F7 consistiu em uma linha da geração F8. O delineamento experimental foi o de blocos casualizados com três repetições. Cada parcela foi constituída de duas fileiras de 5 m, distantes entre si 0,7 m. A colheita ocorreuno estádio R6, para realização da ensilagem das plantas e posterior abertura dos silos 60 dias após. As análises bromatológicas da forragem antes daensilagem e da silagem foram realizadas no Laboratório de Nutrição Animal do Departamento de Zootecnia da Universidade Federal de Viçosa. Na geração F7 foram medidas a altura de plantas e massa frescacalculada a produtividade de massa seca por hectare. Foram analisados teores de matéria seca, matéria orgânica, cinzas, extrato etéreo, proteína bruta, carboidratos solúveis, fibras em detergente neutro, fibras em detergente ácido e lignina, tanto na silagem quanto na forragem. Nitrogênio amoniacal, pH e ácidos orgânicos foram analisados apenas na silagem. Na geração F8 foram medidas a altura de plantas e a massa fresca e calculada a produtividade de massa seca.As variáveis foram submetidas às análises de variância e análise dialélica,além da análise de correlações fenotípica, genotípica e ambiental entre elas. Foi possível a obtenção de populações favoráveis à produção de silagem e, consequentemente, de prováveis cultivares de soja apropriadas à produção de silagem, a exemplo dos cruzamentos Sambaíba x Tucunaré, que reuniram maior número de características favoráveis, mostrando-se capazes de gerar incrementos no teor de CHOS e reduzir os teores de LIG, pH, N-NH3/ NTotal, ACE e, ao mesmo tempo, elevar o teor de LAT; e UFV 16 x UFVS 2003 conciliou reduzido teor de EE e N-NH3/ NTotal, com alto teor de CHOS. As linhagens UFV-TN 105 e Vx 05-3166 conciliaram elevado teor de MS, PB, CHOs e reduzido teor de EE, mostrando-se passíveis de serem incluídos em programas de melhoramento visando à seleção de soja forrageira.

Made available in DSpace on 2015-05-07T15:08:20Z (GMT). No. of bitstreams: 1 parte1.pdf: 2773821 bytes, checksum: fb76fff21676798c65b8f19a1378b235 (MD5) Previous issue date: 2011-10-31 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This work presents a strategy for teaching mathematics in a meaningful learning perspective, concerning the content of high school called Combinatorial Analysis, to understand the processes of counting from the understanding of the concepts involved. For the development of research, we used the assumptions of a teaching methodology based on the theory of David Ausubel and strategies of concept maps by Joseph Novak and Bob Gowin, as a mechanism for structuring the knowledge of students in the teaching and learning of the content mentioned. Ausubel tells us that knowledge is acquired and retained if the learner able to associate the relevant ideas in our pre-existing cognitive structure with the new information being offered. In this sense, Novak uses the concept maps for this relationship between existing and acquired knowledge is meaningful to the learner. Our study was an experiment, exposing Combinatorial Analysis content through the use of concept maps constructed and systematized by Bloom's Revised Taxonomy, so that we find meaningful learning in the apprentice. To check this, we apply a test before and after exposure of the content, using concept maps in the experimental class and without the use of concept maps in class Control. The results were evaluated on a quantitative and a qualitative analysis, proving that the use of concept maps in the study of mathematics, specifically in the content worked, favored meaningful learning. / Este trabalho apresenta uma estratégia de ensino de matemática numa perspectiva de aprendizagem significativa, referente ao conteúdo do Ensino Médio intitulado Análise Combinatória, a fim de que possamos entender os processos de contagem a partir da compreensão dos conceitos envolvidos. Para o desenvolvimento da pesquisa, utilizaram-se pressupostos de uma metodologia de ensino baseada na teoria de David Ausubel e nas estratégias dos mapas conceituais de Joseph Novak e Bob Gowin, como mecanismo de estruturação do conhecimento dos alunos no processo de ensino e aprendizagem do conteúdo mencionado. Ausubel nos fala que o conhecimento será adquirido e retido se o aprendiz conseguir associar as ideias relevantes pré existentes em sua estrutura cognitiva com as novas informações que estão sendo oferecidas. Nesta direção, Novak utiliza-se dos mapas conceituais para que essa relação entre o conhecimento existente e o adquirido tenha sentido para o aprendiz. Nosso trabalho foi de caráter experimental, expondo o conteúdo Análise Combinatória através do uso de mapas conceituais construídos e sistematizados pela Taxonomia de Bloom-Modificada, de maneira que verificamos a aprendizagem significativa no aprendiz. Para essa verificação, aplicamos um teste antes e depois da exposição do conteúdo, com uso de mapas conceituais na turma experimental e sem o uso de mapas conceituais na turma controle. Os resultados foram avaliados sobre um aspecto quantitativo e uma análise qualitativa, comprovando que o uso de mapas conceituais no estudo de matemática, especificamente no conteúdo trabalhado, favoreceu a aprendizagem significativa.

CAPES / O presente trabalho tem dois objetivos: o primeiro está relacionado ao ensino da análise combinatória nas séries do ensino fundamental 2 e ensino médio. O segundo objetivo e buscar aprofundar meus conhecimentos relacionados aos conceitos combinatoriais. Com relação ao primeiro objetivo, o ensino da análise combinatória, na minha trajetória como docente, tem sido uma das tarefas mais árduas que o professor de matemática da educação básica enfrenta. Diante disso, surgem algumas perguntas. Por que um assunto totalmente aplicável ao cotidiano tem gerado tanta dificuldade de compreensão? Um dos objetivos desse trabalho e buscar respostas para essa pergunta e propor sugestões que possam melhorar o entendimento desse conceito. Como segundo objetivo proposto, busquei compreender conceitos que até então, por mim, não dominados, aprofundando meu conhecimento combinatorial. Para tanto, esse trabalho possui uma parte dedicada ao estudo de conceitos combinatorias mais complexos, não o abordados junto aos alunos de ensino médio mas que permitem compreender situações combinatoriais mais complexas. / The present work has two major goals. The first one is related to the teaching of combinatorics in elementary school and high school. The second one is to seek further knowledge related to combinatorial concepts. Regarding the first goal, the teaching of combinatorics, in my trajectory as a teacher, has been one of the most arduous tasks that the math teacher of basic education faces. Therefore, some questions arise. Why a subject fully applicable to everyday, has generated so much trouble understanding? One of the goals of this work is to seek answers to this question and propose suggestions that can improve the understanding of this concept. As a second proposed goal, I sought to understand concepts that hitherto were not dominated, deepening my combinatorial knowledge. Therefore, this work has section devoted to the study of more complex combinatory concepts, not addressed to the students of high school but they allow us to understand more complex combinatorial situations.

Submitted by Jean Medeiros (jeanletras@uepb.edu.br) on 2016-12-09T12:17:44Z No. of bitstreams: 1 PDF - Adriano Alves de Silveira.pdf: 5754090 bytes, checksum: 3f1ff5d850c2e62808aa80d8184050a0 (MD5) / Approved for entry into archive by Secta BC (secta.csu.bc@uepb.edu.br) on 2017-02-02T18:18:37Z (GMT) No. of bitstreams: 1 PDF - Adriano Alves de Silveira.pdf: 5754090 bytes, checksum: 3f1ff5d850c2e62808aa80d8184050a0 (MD5) / Made available in DSpace on 2017-02-02T18:18:37Z (GMT). No. of bitstreams: 1 PDF - Adriano Alves de Silveira.pdf: 5754090 bytes, checksum: 3f1ff5d850c2e62808aa80d8184050a0 (MD5) Previous issue date: 2016-10-06 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This research analyses how an approach in the classroom via Problem Solving, Exploration and Posing can potentialize the teaching and learning of Combinatorial Analysis. A literature review was performed aiming to understand the contributions of other researchers on the researched theme, so that it could be possible to realize what is possible to deepen and add for the scientific community, regarding the teaching and learning process of the Combinatorial Analysis. Besides this, an interview with mathematics teachers was performed, aiming to know their ideas on teaching and learning of Combinatory Analysis and, afterwards, scrutinize until where they could help to plan a sequence of activities. The research was conducted according to a qualitative approach, aiming to search meanings, interpreting and comprehend the information obtained. The modality of research can be characterized as teacher research; according to which the professor is the researcher of his or her own classroom (LANKSHEAR AND KNOBEL, 2008). The teaching and learning Methodology chosen to work in the classroom was the one of the problem solving, exploration and posing, developed with a sequence of activities in a group of the 2nd year of Secondary School of a public school in the city of Alagoinha-PB, Brazil. During the intervention, this researcher acted as a researcher teacher, working in the classroom as a regent teacher, giving a utonomy to the students on the construction of the essential ideas of the Combinatory Analysis, in such a way that the author acted as a mediator and instigator. Data were collected during the lessons through observation and records of the materials used by the students, as well as sound recording. Twenty-one meetings were performed, totaling 25 lessons, each lesson lasting, at most, 45 minutes. The classroom was organized in groups of three students and, in some cases, in pairs, in order to carry out a cooperative and collaborative work, where it was considered important, in this process, the mutual respect among them, respecting the ideas arisen on the search of the problem solution. The results of the research highlighted that through the Mathematics teaching and learning approach via Problem Solving, Exploration and Posing it was possible to monitor the growth of the students, who created their own ideas to solve the problems, and, consequently, found multiple strategies for solution of them; posteriorly, justify their solutions, participating effectively of the construction of their knowledge. Besides this, the students engaged in activities of mathematical exploration, which enabled the comprehension of the essential ideas of Combinatorial Analysis, as well as assuming the role of investigators in the classroom, generalizing, formulating new problems and, afterwards, solving them. From which it follows that such methodology allows learning with more comprehension, strengthening the student to solve problems of Combinatorial Analysis with focus not only on the search of the problem solution, but also on the process of the solution and being able to go far beyond, like the performance of a work of problem posing and exploration. / A presente pesquisa analisa como uma abordagem em sala de aula via Resolução, Exploração e Proposição de problemas pode contribuir/potencializar com o ensino-aprendizagem de Análise Combinatória. Foi realizada uma revisão de literatura com o intuito de compreender as contribuições de outros pesquisadores acerca do tema pesquisado, para que se pudesse perceber o que é possível aprofundar e acrescentar para a comunidade científica, no que diz respeito ao processo de ensino-aprendizagem da Análise Combinatória. Além disso, foi realizada uma entrevista com professores de Matemática, com o intuito de conhecer as suas ideias acerca do ensino-aprendizagem de Combinatória e, posteriormente, perscrutar até que ponto elas poderiam colaborar a planejar uma sequência de atividades. A pesquisa foi empreendida segundo uma abordagem qualitativa, visando buscar significados, interpretar e compreender as informações obtidas. A modalidade de pesquisa pode ser caracterizada como pedagógica, segundo a qual o professor é o pesquisador de sua própria sala de aula (LANKSHEAR E KNOBEL, 2008). A Metodologia de ensino-aprendizagem escolhida para trabalhar em sala de aula foi a de resolução, exploração e proposição de problemas, desenvolvida com uma sequência de atividades em uma turma do 2ª ano do Ensino Médio de uma escola pública na cidade de Alagoinha-PB. Durante a intervenção, o presente pesquisador agiu como professor-pesquisador, trabalhando em sala de aula como professor regente, dando autonomia aos alunos na construção das ideias essenciais de Combinatória, de modo que o autor agiu como mediador e incentivador. Os dados foram levantados durante as aulas através das observações e registros dos materiais utilizados pelos alunos, bem como de gravação sonora. Foram realizados 21 encontros, totalizando 25 aulas, cada aula com duração de, no máximo, 45 minutos. A sala foi organizada em grupos de três alunos e, em alguns casos, em duplas, com o intuito de se realizar um trabalho cooperativo e colaborativo, onde se considerou importante, nesse processo, o respeito mútuo entre eles, respeitando as ideias levantadas na busca da solução dos problemas. Os resultados da pesquisa evidenciaram que através da abordagem via Resolução, Exploração e Proposição de problemas foi possível acompanhar o crescimento dos alunos, que criaram suas próprias ideias para resolver os problemas, e, consequentemente, encontraram múltiplas estratégias de resolução deles; posteriormente, justificam suas soluções, participando efetivamente da construção do seu conhecimento. Além disso, os alunos engajaram-se em atividades de exploração matemática que lhes possibilitaram a apreensão de ideias essenciais de Análise Combinatória, como também assumiram o papel de investigadores em sala de aula, fazendo generalizações, formulando novos problemas e, em seguida, os resolvendo. De onde se conclui que tal metodologia permitiu um aprendizado com mais compreensão, potencializando o aluno para resolver problemas de Análise Combinatória com foco não apenas na busca da solução do problema, mas no processo da resolução e podendo ir muito além, como a realização de um trabalho de proposição e exploração de problemas.

Made available in DSpace on 2018-06-27T19:13:28Z (GMT). No. of bitstreams: 2 Ana Paula Goncalves da Fonte.pdf: 3610212 bytes, checksum: 6f01dc19dac3d3b4759b3ef10be9c017 (MD5) Ana Paula Goncalves da Fonte.pdf.jpg: 3402 bytes, checksum: 82d9444711460fe1d0705b7e124f8eb3 (MD5) Previous issue date: 2009-05-15 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This paper features, as its central investigation focus the contributions that Problem Resolution methodology, allied to the building of Image and Definition Concepts, offer to the learning and teaching process of concepts of Combinative Analysis, through a qualitative research, adopting the following methodological procedures: interactive observation in the classroom and work field diary of the teacher-researcher. The research has been developed with 35 students of the sixth semester Math full licentiate course at Pontifícia Universidade Católica, Rio Grande do Sul state, (PUCRS), Uruguaiana campus, on the second semester of 2008. The activities in the classroom followed the steps of problem resolution suggested by Onuchic (1999): Set groups, reading and teacher questions about the problems, taking notes of the results on the chalk board, plenary, consensus and concept formalization. The analysis of the resolutions presented by the students proved the contributions of this teaching strategy choice, for the growing of the Math thought can be proved. That means, the merge of the resolution problem methodology to the building of the concept image and definition give the teacher a more realistic view of the knowledge acquiring process by the student, allowing the teacher to know where there should be the readjustment of the activities adopted and the beginning of new topics. / Este trabalho apresenta como foco central de investigação as contribuições que a metodologia de resolução de problemas, aliada a construção dos conceitos imagem e definição oferecem ao processo de ensino e aprendizagem de conceitos de Análise Combinatória, por meio de uma pesquisa qualitativa, adotando os seguintes procedimentos metodológicos: observação participante em sala de aula e diário de campo da professora-pesquisadora. A pesquisa foi desenvolvida com 35 alunos do sexto semestre do curso de licenciatura plena em matemática da PUCRS-Câmpus de Uruguaiana, no segundo semestre de 2008. As atividades em sala de aula seguiram os passos da resolução de problemas., sugeridos por Onuchic (1999): Formar grupos, leitura e questionamentos do professor sobre o problema, anotação dos resultados no quadro de giz, plenária, consenso e formalização do conceito. A análise das resoluções apresentadas pelos alunos comprovaram as contribuições desta escolha de estratégia de ensino, pois o crescimento do pensar matemático pode ser comprovado. Ou seja, a união da metodologia de resolução de problemas a construção de conceito imagem e definição propiciam a professora uma visão mais real do processo aquisição do conhecimento do aluno, possibilitando ao professor saber onde deveria haver a reestruturação das atividades adotadas e o início de novos assuntos. Palavras-chave: Resolu

Cette recherche visait à étudier le potentiel des transformations de représentation sémiotique d´enregistrements dans une analyse combinatoire de la proposition de l´enseignement intégré sur la résolution pour les étudiants de 2e année de l´école secondaire problème. Le cadre théorique de cette recherche a été liée à l´enseignement et l´apprentissage des cours de mathématiques en utilisant la Représentation Sémiotique registres, les niveaux de connaissance attendus des étudiants et de dépannage. Pour le développement de cette étude ont été utilisés aspects méthodologiques de génie didactique. L´analyse a été développé à partir d´un point de vue qualitatif. Participé à cette étude, les élèves de la deuxième année de l´école secondaire de la State College Victoire de Santa Maria à Aracaju / SE. Il a été prouvé dans l´application de la séquence d´enseignement que l´enseignement basé sur les leçons de l´expérience qui stimule la mobilisation des dossiers sémiotiques et les activités liées à la quotidienne de l´étudiant a contribué efficacement à l´enseignement et l´apprentissage de l´analyse combinatoire. / A presente pesquisa teve como objetivo geral investigar o potencial das transformações dos registros de representação semiótica em uma proposta de ensino de Análise Combinatória construída com base na resolução de problemas para alunos da 2º série do ensino médio. O referencial teórico desta investigação esteve relacionado com o processo de ensino e aprendizagem da disciplina matemática, utilizando os Registros de Representação Semiótica, Níveis de conhecimento esperados dos estudantes e Resolução de Problemas. Para o desenvolvimento desse estudo foram utilizados aspectos metodológicos da Engenharia Didática. A análise se desenvolveu numa perspectiva qualitativa. Participaram dessa pesquisa os alunos da segunda série do ensino médio do Colégio Estadual Vitória de Santa Maria em Aracaju/SE. Ficou comprovado na aplicação da sequência didática que o ensino baseado em experiências de aulas que estimule a mobilização dos registros semióticos e com atividades relacionadas ao cotidiano do discente contribuiu de forma efetiva para o ensino e a aprendizagem de Análise Combinatória.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / Counting techniques studied in basic education aim at the resolutions os simplest combinatorial problems. In this work, we present the generating functions, a powerful tool to solving more complex problems of counting. In this way, we discuss the contents of combinatorial analysis through the study of generating functions, proposing a didactic sequence on the subject for teachers of basic education can expand and diversify their teaching strategies, by means of this counting method. / As t ecnicas de contagem estudadas na educação b ásica visam as resolu ções de problemas combinat órios mais simples. Neste trabalho, apresentaremos as funções geradoras, uma poderosa ferramenta para solucionar problemas mais complexos de contagem. Destaforma, abordaremos o conte udo de an alise combinat ória atrav és do estudo de funções sgeradoras, propondo uma sequência did ática sobre o tema para que os professores da educação b ásica possam ampliar e diversi car as suas estrat égias de ensino, a a partir deste novo método de contagem.

Orientador: José Plínio de Oliveira Santos / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica / Made available in DSpace on 2018-08-25T04:32:08Z (GMT). No. of bitstreams: 1 BrasilJunior_NelsonGomes_M.pdf: 980636 bytes, checksum: dd8d61baeb633d5f598abc3523def800 (MD5) Previous issue date: 2014 / Resumo: Neste trabalho, estudamos a sequência dos Números de Catalan, uma sequência que aparece como solução de vários problemas de contagem envolvendo árvores, palavras, grafos e outras estruturas combinatórias. Atualmente, são conhecidas cerca de 200 interpretações combinatórias distintas para os Números de Catalan, o que motiva o estudo de relações entre estas interpretações, isto é, entre conjuntos cuja cardinalidade é dada pelos termos desta sequência. O principal objetivo do nosso trabalho é, portanto, mostrar bijeções entre esses conjuntos. No início do texto fazemos uma pequena introdução histórica aos números de Catalan, assim como definimos algumas formas de representar a sequência estudada. Depois mostramos algumas bijeções clássicas entre conjuntos contados pela sequência de Catalan. Além disso, apresentamos outras bijeções entre conjuntos envolvendo diversos objetos combinatórios. No total, são exibidas 29 bijeções / Abstract: In this work, we study the sequence of Catalan Numbers, which appears as a solution of many counting problems involving trees, words, graphs and other combinatorial structures. Nowadays, about 200 different combinatorial interpretations of the Catalan Numbers are known and that motivates the study between them, i. e., the study between sets whose cardinality is given by the terms of this sequence. The main objective of our work is therefore to show bijections between these sets. In the beginning, we make a short historical introduction of the Catalan Numbers and define some ways to represent the sequence. After that, we show some classical bijections between sets counted by the Catalan Numbers. Additionally, we exhibit other bijections between sets involving several combinatorial objects. Altogether, 29 bijections are presented / Mestrado / Matematica Aplicada / Mestre em Matemática Aplicada

Orientador: Jacques Wainer / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-24T00:42:33Z (GMT). No. of bitstreams: 1 Passos_AlexandreTachard_D.pdf: 2615030 bytes, checksum: 93841a46120b968f6da6c9aea28953b7 (MD5) Previous issue date: 2013 / Resumo: Em processamento de linguagem natural, e em aprendizado de máquina em geral, é comum o uso de modelos gráficos probabilísticos (probabilistic graphical models). Embora estes modelos sejam muito convenientes, possibilitando a expressão de relações complexas entre várias variáveis que se deseja prever dado uma sentença ou um documento, algoritmos comuns de aprendizado e de previsão utilizando estes modelos são frequentemente ineficientes. Por isso têm-se explorado recentemente o uso de relaxações usando programação linear deste problema de inferência. Esta tese apresenta duas contribuições para a teoria e prática de relaxações de programação linear para inferência em modelos probabilísticos gráficos. Primeiro, apresentamos um novo algoritmo, baseado na técnica de geração de colunas (dual à técnica dos planos de corte) que acelera a execução do algoritmo de Viterbi, a técnica mais utilizada para inferência em modelos lineares. O algoritmo apresentado também se aplica em modelos que são árvores e em hipergrafos. Em segundo mostramos uma nova relaxação linear para o problema de inferência conjunta, quando se quer acoplar vários modelos, em cada qual inferência é eficiente, mas em cuja junção inferência é NP-completa. Esta tese propõe uma extensão à técnica de decomposição dual (dual decomposition) que permite além de juntar vários modelos a adição de fatores que tocam mais de um submodelo eficientemente / Abstract: In natural language processing, and in general machine learning, probabilistic graphical models (and more generally structured linear models) are commonly used. Although these models are convenient, allowing the expression of complex relationships between many random variables one wants to predict given a document or sentence, most learning and prediction algorithms for general models are inefficient. Hence there has recently been interest in using linear programming relaxations for the inference tasks necessary when learning or applying these models. This thesis presents two contributions to the theory and practice of linear programming relaxations for inference in structured linear models. First we present a new algorithm, based on column generation (a technique which is dual to the cutting planes method) to accelerate the Viterbi algorithm, the most popular exact inference technique for linear-chain graphical models. The method is also applicable to tree graphical models and hypergraph models. Then we present a new linear programming relaxation for the problem of joint inference, when one has many submodels and wants to predict using all of them at once. In general joint inference is NP-complete, but algorithms based on dual decomposition have proven to be efficiently applicable for the case when the joint model can be expressed as many separate models plus linear equality constraints. This thesis proposes an extension to dual decomposition which allows also the presence of factors which score parts that belong in different submodels, improving the expressivity of dual decomposition at no extra computational cost / Doutorado / Ciência da Computação / Doutor em Ciência da Computação