Submitted by Rafael Santana (rafael.silvasantana@ufpe.br) on 2017-05-17T19:18:31Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) ANA PAULA LIMA_DISSERTAÇÃO_VERSÃO FINAL.pdf: 3025939 bytes, checksum: 3cb2a6d555eaee3f9ae8cdf088962636 (MD5) / Made available in DSpace on 2017-05-17T19:18:31Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) ANA PAULA LIMA_DISSERTAÇÃO_VERSÃO FINAL.pdf: 3025939 bytes, checksum: 3cb2a6d555eaee3f9ae8cdf088962636 (MD5) Previous issue date: 25-02-15 / CAPES / No estudo propôs-se investigar os conhecimentos de professores da Educação Básica sobre como o Princípio Fundamental da Contagem (PFC), também conhecido como princípio multiplicativo, pode ser usado na resolução de variados problemas combinatórios e na construção das fórmulas da Análise Combinatória. Pesquisas anteriores evidenciam a importância deste princípio no ensino de Combinatória e como o mesmo facilita a resolução dos diferentes tipos de situações combinatórias. Foram realizados dois estudos, um com a finalidade de saber se professores e estudantes reconhecem o PFC em situações combinatórias; e o outro estudo tinha como objetivo investigar conhecimentos de professores de Matemática sobre a resolução e o ensino de problemas combinatórios com o uso do PFC. O primeiro estudo envolveu um teste de múltipla escolha e justificativas, de dados coletados junto a professores dos anos finais do Ensino Fundamental, professores do Ensino Médio e alunos deste último nível da Educação Básica. Para o segundo estudo, foi realizada uma entrevista semiestruturada com professores, baseada nos tipos de conhecimento sugeridos por Ball, Thames e Phelps (2008) (conhecimento comum do conteúdo, conhecimento especializado do conteúdo, conhecimento horizontal do conteúdo, conhecimento do conteúdo e alunos, conhecimento do conteúdo e ensino e conhecimento do conteúdo e currículo). Neste segundo estudo a coleta de dados foi realizada por meio de protocolos com situações combinatórias resolvidas por alunos. Estas situações envolveram os quatro tipos de problemas combinatórios (produto cartesiano, arranjo, permutação e combinação). A partir dos conhecimentos propostos por Ball, Thames e Phelps (2008), foram criadas seis categorias com foco no PFC para a análise dos conhecimentos dos professores sobre o uso do PFC na resolução de situações combinatórias: conhecimento comum do PFC, conhecimento especializado do PFC, conhecimento horizontal do PFC, conhecimento do PFC e alunos, conhecimento do PFC e ensino e conhecimento do PFC e currículo. Como principais resultados tem-se que, os professores do Ensino Médio melhor reconhecem o uso do PFC, quando comparados com os professores do Ensino Fundamental. O reconhecimento do PFC dos professores do Ensino Médio é muito superior ao dos alunos deste nível de ensino, o que pode indicar que os professores parecem não estar ressaltando este princípio no ensino junto a seus alunos. Os professores evidenciam conhecimentos comum e especializado do PFC, bem como horizontal, mas não indicam como relacionar o princípio multiplicativo com as fórmulas da Análise Combinatória. Evidenciam conhecimento do aluno, mas referente ao conhecimento do ensino não deixam claro como o uso de outras estratégias, tais como árvores de possibilidades e fórmulas, se relacionam com o PFC. Melhores conhecimentos do que é prescrito e apresentado em currículos também são necessários. Conclui-se que os conhecimentos docentes do PFC podem servir de base para um melhor desenvolvimento do ensino e da aprendizagem da Combinatória, mas há aspectos do conhecimento que os professores necessitam desenvolver melhor. Espera-se, assim, ter contribuído com o levantamento de conhecimentos docentes sobre a Combinatória e também ter trazido contribuições referentes ao papel do Princípio Fundamental da Contagem como eficiente estratégia de ensino, por possibilitar a resolução de diferentes tipos de problemas combinatórios. / The study aimed to investigate Middle and High School teachers' knowledge of how the Fundamental Counting Principle (FCP), also known as multiplicative principle, can be used in solving various combinatorial problems and in the construction of formulas of Combinatorial Analysis. Previous research showed the importance of this principle in teaching Combinatorics and how it facilitates the resolution of different types of combinatorial situations. Two studies were performed, one study with the purpose of knowing whether teachers and students recognize the FCP in combinatorial situations; and the other study was designed to investigate Mathematics teachers knowledge about the resolution and the teaching of combinatorial problems using the FCP. The first study involved a multiple choice test and justifications, of data collected with Middle School and High School teachers and students of the final level of basic education. For the second study semi structured interviews with teachers were performed, based on the types of knowledge suggested by Ball, Thames and Phelps (common content knowledge, specialized content knowledge, horizon content knowledge, content knowledge and students, content knowledge and teaching and content knowledge and curriculum). In this second study data collection was performed using protocols with combinatorial situations resolved by students. These situations involved the four types of combinatorial problems (Cartesian product, arrangement, permutation and combination). Based on the knowledge proposed by Ball, Thames and Phelps, six categories were created with a focus on the FCP to analyse teacher’s knowledge on the use of FCP in solving combinatorial situations: common FCP knowledge, specialized FCP knowledge, horizon FCP knowledge, FCP knowledge and students, FCP knowledge and teaching and FCP knowledge and curriculum. The main results show that High School teachers better recognize the use of FCP when compared to Middle School teachers. Recognition of the FCP by High School teachers is much higher than the students of this school level, which may indicate that teachers do not seem to be emphasizing this principle when teaching their students. Teachers show common and specialized knowledge of the FCP and also horizon knowledge, but do not indicate how to relate the multiplicative principle with the formulas of Combinatorial Analysis. They demonstrate knowledge of the student, but referring to knowledge of teaching they do not make clear how the use of other strategies, such as tree diagrams and formula, relates to the FCP. Better knowledge of what is prescribed and presented in curricula are also required. We conclude that FCP teachers’ knowledge can be the basis for a better development of the teaching and learning of Combinatorics, but there are aspects of knowledge that teachers need to develop better. It is expected, therefore, that the study contributes to the survey of teachers’ knowledge of Combinatorics and also to have brought contributions on the role of the Fundamental Counting Principle as an effective teaching strategy, allowing for the resolution of different types of combinatorial problems.

NP search problems and reductions among them Renáta Ševčíková In the thesis we study the class of Total NP search problems. More attention is devoted to study the subclasses of Total NP search problems and reductions among them. We combine some known methods: the search trees and their relation to re- ductions, the Nullstellensatz refutation and the degree lower bound based on design to show that two classes of relativized NP search problems based on Mod-p counting principle and Mod-q counting principle, where p and q are different primes, are not reducible to each other. This thesis is finished by a new separation result for p = 2 and q = 3.

In 1972, professor Grigore Moisil, the most famous Romanian academician for Mathematics, said about Combinatorics, that it is “an opportunity of a renewed gladness”, because “each problem in the domain asks for its solving, an expenditure without any economy of the human intelligence”. More, the research methods, used in Combinatorics, are different from a problem to the other! This is the explanation for the existence of my actual paper, in which I propose to teach Combinatorics, using selected problems. MS classification: 05A05, 97D50.

In 1972, professor Grigore Moisil, the most famous Romanian academician for Mathematics, said about Combinatorics, that it is “an opportunity of a renewed gladness”, because “each problem in the domain asks for its solving, an expenditure without any economy of the human intelligence”. More, the research methods, used in Combinatorics, are different from a problem to the other! This is the explanation for the existence of my actual paper, in which I propose to teach Combinatorics, using selected problems. MS classification: 05A05, 97D50.

This thesis was designed as a self study unit for middle school aged students with special needs. The unit is broken in to sub-units that specifically cater to each number base. Also included in this plan is a brief history of counting and practical uses for the mathematics of different number bases. This has been designed to be a "fun" unit to study after taking S.O.L. tests or other state standard testing. Included in each unit are worksheets for assessment of understanding.