We define instance compressibility ([13, 17]) for parametric problems in the classes PH and PSPACE.We observe that the problem ƩiCIRCUITSAT of deciding satisfiability of a quantified Boolean circuit with i-1 alternations of quantifiers starting with an existential quantifier is complete for parametric problems in the class Ʃp/i with respect to w-reductions, and that analogously the problem QBCSAT (Quantified Boolean Circuit Satisfiability) is complete for parametric problems in PSPACE with respect to w-reductions. We show the following results about these problems: 1. If CIRCUITSAT is non-uniformly compressible within NP, then ƩiCIRCUITSAT is non-uniformly compressible within NP, for any i≥1. 2. If QBCSAT is non-uniformly compressible (or even if satisfiability of quantified Boolean CNF formulae is non-uniformly compressible), then PSPACE ⊆ NP/poly and PH collapses to the third level. Next, we define Succinct Interactive Proof (Succinct IP) and by adapting the proof of IP = PSPACE ([11, 6]) , we show that QBCNFSAT (Quantified Boolean Formula (in CNF) Satisfiability) is in Succinct IP. On the contrary if QBCNFSAT has Succinct PCPs ([32]) , Polynomial Hierarchy (PH) collapses. After extending the notion of instance compression to higher classes, we study the hierarchical structure of the parametric problems with respect to compressibility. For that purpose, we extend the existing definition of VC-hierarchy ([13]) to parametric problems. After that, we have considered a long list of natural NP problems and tried to classify them into some level of VC-hierarchy. We have shown some of the new w-reductions in this context and pointed out a few interesting results including the ones as follows. 1. CLIQUE is VC1-complete (using the results in [14]). 2. SET SPLITTING and NAE-SAT are VC2-complete. We have also introduced a new complexity class VCE in this context and showed some hardness and completeness results for this class. We have done a comparison of VC-hierarchy with other related hierarchies in parameterized complexity domain as well. Next, we define the compression of counting problems and the analogous classification of them with respect to the notion of instance compression. We define #VC-hierarchy for this purpose and similarly classify a large number of natural counting problems with respect to this hierarchy, by showing some interesting hardness and completeness results. We have considered some of the interesting practical problems as well other than popular NP problems (e.g., #MULTICOLOURED CLIQUE, #SELECTED DOMINATING SET etc.) and studied their complexity for both decision and counting version. We have also considered a large variety of circuit satisfiability problems (e.g., #MONOTONE WEIGHTED-CNFSAT, #EXACT DNF-SAT etc.) and proved some interesting results about them with respect to the theory of instance compressibility.

Submitted by Livia Mello (liviacmello@yahoo.com.br) on 2016-10-10T18:56:26Z No. of bitstreams: 1 DissDRB.pdf: 4725235 bytes, checksum: 58c4238ba8671000419655dab60c75f8 (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-10-20T19:54:33Z (GMT) No. of bitstreams: 1 DissDRB.pdf: 4725235 bytes, checksum: 58c4238ba8671000419655dab60c75f8 (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-10-20T19:54:39Z (GMT) No. of bitstreams: 1 DissDRB.pdf: 4725235 bytes, checksum: 58c4238ba8671000419655dab60c75f8 (MD5) / Made available in DSpace on 2016-10-20T19:54:47Z (GMT). No. of bitstreams: 1 DissDRB.pdf: 4725235 bytes, checksum: 58c4238ba8671000419655dab60c75f8 (MD5) Previous issue date: 2016-06-23 / Não recebi financiamento / This work AIMS to Develop the content of combinatorial analysis in the class of 6th and 7th grade of elementary school II in a school in the state of São Paulo. For this, there was the use of contextualized activities using leaves, activities and resources Involving magic, aiming to arouse curiosity and interest in learning Combinatorial through problem solving. The theme was chosen because of the difficulty of students in solving counting problems and is being explored little in basic education, although it appears in documents oficiais- National Curriculum Parameters and Curriculum of the State of São Paulo. We opted for the mathematical magic feature to make more meaningful and enjoyable learning Combinatorics, seeking the motivation of students to Actively Participate in class, joining the pleasure the act of learning. During the performance of activities, it was Noted que the students felt motivated, Relating the content of combinatorial analysis with a fun practice by magic. They Showed great enthusiasm in carrying out the activities, Especially in the days que had the magic. The didactic proposal with the use of leaf-activities Reached most of the students, who Were Involved and were very active During class, Resulting in collegues learning Combinatorial Analysis content. All activities Reached The proposed objectives, validating the Proposed teacher. After the completion of the activities, students felt more confident to expose Their reasoning, presenting solving strategies and explore the problem in search of a suitable solution. / Esse trabalho tem por objetivo desenvolver o conteúdo de Análise Combinatória em uma turma do 6o e do 7o ano do Ensino Fundamental II, em uma escola do interior do Estado de São Paulo. Para isso, fez-se o uso de atividades contextualizadas utilizando folhas-atividades e recursos envolvendo mágicas, visando despertar a curiosidade e o interesse em aprender Combinatória por meio de resolução de problemas. O tema foi escolhido devido à dificuldade dos alunos em resolver problemas de contagem e por ser pouco explorado no Ensino Básico, apesar de constar nos documentos oficiais- Parâmetros Curriculares Nacionais e Currículo do Estado de São Paulo. Optou-se pelo recurso das mágicas matemáticas para tornar mais significativa e prazerosa a aprendizagem de Combinatória, buscando-se a motivação dos alunos a participar ativamente das aulas, unindo o prazer ao ato de aprender. Durante a realização das atividades, notou-se que os alunos se sentiram motivados, relacionando o conteúdo de Análise Combinatória com uma prática divertida através da mágica. Eles demonstraram bastante entusiasmo na realização das atividades, principalmente nos dias que tinha a mágica. A proposta didática com o uso das folhas-atividades alcançou a maioria dos alunos, que se empenharam e foram bastante ativos durante as aulas, resultando na aprendizagem de fato do conteúdo de Análise Combinatória. Todas as atividades atingiram os objetivos propostos, validando as propostas do professor. Após a realização das atividades, os alunos se sentiram mais confiantes para expor seu raciocínio, apresentar estratégias de resolução e explorar o problema em busca de uma solução adequada.

Submitted by Viviane Lima da Cunha (viviane@biblioteca.ufpb.br) on 2015-10-16T11:57:04Z No. of bitstreams: 1 arquivototal.pdf: 4711783 bytes, checksum: ef1f22acd23a66ff022013741e6cd635 (MD5) / Rejected by Viviane Lima da Cunha (viviane@biblioteca.ufpb.br), reason: corrigir referencia on 2015-10-16T11:59:43Z (GMT) / Submitted by Viviane Lima da Cunha (viviane@biblioteca.ufpb.br) on 2015-10-16T12:10:40Z No. of bitstreams: 1 arquivototal.pdf: 4711783 bytes, checksum: ef1f22acd23a66ff022013741e6cd635 (MD5) / Approved for entry into archive by Viviane Lima da Cunha (viviane@biblioteca.ufpb.br) on 2015-10-16T12:11:49Z (GMT) No. of bitstreams: 1 arquivototal.pdf: 4711783 bytes, checksum: ef1f22acd23a66ff022013741e6cd635 (MD5) / Made available in DSpace on 2015-10-16T12:11:49Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 4711783 bytes, checksum: ef1f22acd23a66ff022013741e6cd635 (MD5) Previous issue date: 2013-08-01 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This paper presents an introduction to the study of counting problems, not just through the concepts traditionally covered in Combinatorial Analysis courses, such as the basic principles, permutations, arrangements, combinations, linear equations with unitary coe cients, among others, but also using sophisticated tools, such as the use of graphs. / O presente trabalho apresenta uma introdução ao estudo de problemas de contagem, não apenas através dos conceitos tradicionalmente abordados em cursos de Análise Combinatória, tais como os princípios básicos, as permutações, os arranjos, as combinações, as equações lineares com coe cientes unitários e outros, mas também, ferramentas so sticadas de contagem, tal como o uso de grafos.

Submitted by Alison Vanceto (alison-vanceto@hotmail.com) on 2017-09-13T18:23:58Z No. of bitstreams: 1 DissWML.pdf: 4207155 bytes, checksum: 5811f047e7b65dbd43f52f60e16255ba (MD5) / Approved for entry into archive by Ronildo Prado (ronisp@ufscar.br) on 2017-09-20T13:58:00Z (GMT) No. of bitstreams: 1 DissWML.pdf: 4207155 bytes, checksum: 5811f047e7b65dbd43f52f60e16255ba (MD5) / Approved for entry into archive by Ronildo Prado (ronisp@ufscar.br) on 2017-09-20T13:58:07Z (GMT) No. of bitstreams: 1 DissWML.pdf: 4207155 bytes, checksum: 5811f047e7b65dbd43f52f60e16255ba (MD5) / Made available in DSpace on 2017-09-20T14:05:26Z (GMT). No. of bitstreams: 1 DissWML.pdf: 4207155 bytes, checksum: 5811f047e7b65dbd43f52f60e16255ba (MD5) Previous issue date: 2017-06-29 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / This research was started because of concerns regarding the teaching and learning of Counting Problems in Elementary School. With the intent of contributing to the construction of basic Combinatorial concepts, we elaborated exploratory-investigative tasks and we tried through these tasks, to analyze the answers that were made by students of an 8th grade of Elementary School, in order to answer the following investigative question: what learning occurs with the mobilization of registers of semiotic representation theory to do counting in a scenario of exploratory- investigative tasks in an 8th grade of Elementary School? The theoretical and methodological reference is constituted by the registers of semiotic representation theory propounded by Duval; by the theory of Mathematical Investigations, Ponte et al. Besides that the research also had the collaboration of Pessoa and Borba. We present a brief historical retrospective on the subject, besides a previous analysis of other works in the area and official documents aimed at teaching and learning of Mathematics subject regarding to contents of Counting Problems in Elementary School. The research was developed with a group of 25 students of the 8th grade Elementary School in a public school in São Paulo state, in the year 2016. The data collection was done through field notes (logbook), and from the records written by the students during the development of the sequence of tasks. Through this investigation, we could verify that the study of Counting Problems through exploratory-investigative tasks allows the articulation of different registers of semiotic representation, leading to a better understanding of this topic. / Esta pesquisa originou-se a partir de inquietações relacionadas ao ensino e aprendizagem de Problemas de Contagem no Ensino Fundamental. Com a intenção de contribuir para a construção de conceitos básicos de Combinatória, elaboramos tarefas de natureza exploratório-investigativas e procuramos por meio destas, analisar as respostas produzidas por estudantes de um 8o ano do Ensino Fundamental, com o intuito de responder a seguinte questão de investigação: que aprendizagem ocorre com a mobilização de registros de representação semiótica para a realização de contagens em um cenário de tarefas exploratório-investigativas num 8o ano do Ensino Fundamental? O referencial teórico e metodológico é constituído pela teoria dos registros de representação semiótica proposta por Duval e pela teoria das Investigações Matemáticas, proposta Ponte et al. Além disso o trabalho também contou com a colaboração de Pessoa e Borba. Realizamos um breve retrospecto histórico sobre o tema, além de uma análise previa de outros trabalhos na área, e documentos oficiais voltados para o ensino e aprendizagem da Matemática no que diz respeito a conteúdos relacionados a Problemas de Contagem no Ensino Fundamental. A pesquisa foi desenvolvida em uma turma de 25 alunos do 8o ano Ensino Fundamental de uma escola da rede pública de ensino do estado de São Paulo, no ano de 2016. A coleta de dados se deu por meio de notas de campo (diário de bordo), e dos registros produzidos pelos estudantes ao logo do desenvolvimento da sequência de tarefas. Através desta investigação, pudemos verificar que o estudo de Problemas de Contagem por meio de tarefas exploratório- investigativas possibilita a articulação entre diferentes registros de representação semiótica, o que leva a um melhor entendimento desse tema.

Diese Arbeit nutzt und verfeinert Methoden der Komplexitätstheorie, um mit diesen die Komplexität dünner Instanzen zu untersuchen. Dazu gehören etwa Graphen mit wenigen Kanten oder Formeln mit wenigen Bedingungen beschränkter Weite. Dabei ergeben sich zwei natürliche Fragestellungen: (a) Gibt es einen effizienten Algorithmus, der beliebige Instanzen eines NP-schweren Problems auf äquivalente, dünne Instanzen reduziert? (b) Gibt es einen Algorithmus, der dünne Instanzen NP-schwerer Probleme bedeutend schneller löst als allgemeine Instanzen gelöst werden können? Wir formalisieren diese Fragen für verschiedene Probleme und zeigen, dass positive Antworten jeweils zu komplexitätstheoretischen Konsequenzen führen, die als unwahrscheinlich gelten. Frage (a) wird als Kommunikation modelliert, in der zwei Akteure kooperativ eine NP-schwere Sprache entscheiden möchten und dabei möglichst wenig kommunizieren. Unter der komplexitätstheoretischen Annahme, dass coNP keine Teilmenge von NP/poly ist, erhalten wir aus unseren Ergebnissen erstaunlich scharfe untere Schranken für interessante Parameter aus verschiedenen Teilgebieten der theoretischen Informatik. Im Speziellen betrifft das die Ausdünnung von Formeln, die Kernelisierung aus der parameterisierten Komplexitätstheorie, die verlustbehaftete Kompression von Entscheidungsproblemen, und die Theorie der probabilistisch verifizierbaren Beweise. Wir untersuchen Fragestellung (b) anhand der Exponentialzeitkomplexität von Zählproblemen. Unter (Varianten) der bekannten Exponentialzeithypothese (ETH) erhalten wir exponentielle untere Schranken für wichtige #P-schwere Probleme: das Berechnen der Zahl der erfüllenden Belegungen einer 2-KNF Formel, das Berechnen der Zahl aller unabhängigen Mengen in einem Graphen, das Berechnen der Permanente einer Matrix mit Einträgen 0 und 1, das Auswerten des Tuttepolynoms an festen Punkten. / In this thesis, we use and refine methods of computational complexity theory to analyze the complexity of sparse instances, such as graphs with few edges or formulas with few constraints of bounded width. Two natural questions arise in this context: (a) Is there an efficient algorithm that reduces arbitrary instances of an NP-hard problem to equivalent, sparse instances? (b) Is there an algorithm that solves sparse instances of an NP-hard problem significantly faster than general instances can be solved? We formalize these questions for different problems and show that positive answers for these formalizations would lead to consequences in complexity theory that are considered unlikely. Question (a) is modeled by a communication process, in which two players want to cooperatively decide an NP-hard language and at the same time communicate as few as possible. Under the complexity-theoretic hypothesis that coNP is not in NP/poly, our results imply surprisingly tight lower bounds for parameters of interest in several areas, namely sparsification, kernelization in parameterized complexity, lossy compression, and probabilistically checkable proofs. We study the question (b) for counting problems in the exponential time setting. Assuming (variants of) the exponential time hypothesis (ETH), we obtain asymptotically tight, exponential lower bounds for well-studied #P-hard problems: Computing the number of satisfying assignments of a 2-CNF formula, computing the number of all independent sets in a graph, computing the permanent of a matrix with entries 0 and 1, evaluating the Tutte polynomial at fixed evaluation points.

Made available in DSpace on 2016-04-27T16:57:13Z (GMT). No. of bitstreams: 1 Carlos Eduardo de Campos.pdf: 1683164 bytes, checksum: 1dd97a1301e188ce53dd5d495c3b2f0e (MD5) Previous issue date: 2011-11-09 / Secretaria da Educação do Estado de São Paulo / This dissertation is focused on the teaching and learning of the Combinatorial Analysis, specifically mentioning, Counting Problems. The report is about a documentary research, as a result of the analysis of the coursebook, thus the methodological procedures are the most appropriate to this kind of investigation. The aim of this research is to evaluate the types of Counting Problems, which are included in the student s book, Secondary school second grade third term from the Department of Education of the state of São Paulo, in the view of the combinatorial research, taking into account that is the presupposition of the Curriculum of the state of São Paulo, the resolution of the problems in a teaching approach for the combinatorial concepts. The studied problems are the simple ones, in other words, those which could be solved by using only one combinatorial operation. The yardsticks of the content analysis accomplished in the book are the task variables used by Batanero, Navarro-Pelayo, implicit combinatorial model, combinatorial operation, the nature of the elements to be combined and the values of the parameter m and n. They are supported by the theory of the conceptual fields developed by Vergnaud, in which those concepts couldn t be learnt with the approach of a single type of problem. Our investigation led us to the conclusion that, even working with an important list of issues, many of them involved similar situations. It is because not all the considered variables were found in this list / Esta dissertação tem por foco o ensino e a aprendizagem da Análise Combinatória ou, mais especificamente, dos Problemas de Contagem. Trata-se do relatório minucioso de pesquisa documental de análise de material didático e, sobretudo, os procedimentos metodológicos são os adequados a essa modalidade de investigação. O objetivo da investigação é avaliar os tipos de Problemas de Contagem, que figuram no Caderno do Aluno do 3º bimestre do 2º ano do Ensino Médio, da Rede Estadual Paulista de Ensino, com vistas à formação do raciocínio combinatório, levando em conta o pressuposto da Proposta Curricular em questão que entende a resolução de problemas como uma abordagem de ensino eficaz para os conceitos combinatórios. Os problemas estudados são entendidos e classificados como simples, ou seja, aqueles que podem ser resolvidos usando somente uma operação combinatória. Os balizadores da análise de conteúdo realizada no Caderno são as variáveis de tarefa usadas por Batanero e Navarro-Pelayo: modelo combinatório implícito, operação combinatória, natureza dos elementos que se combinam e valores dados aos parâmetros m e n. Os mesmos são respaldados na Teoria dos Campos Conceituais de Verganaud, para a qual conceitos não podem ser apreendidos com a abordagem de um único tipo de problema. Nossa investigação nos levou a constatar que, mesmo com um elenco importante de problemas, muitos deles envolviam situações semelhantes. Isso se deu porque nem todas as variáveis consideradas foram encontradas nesse rol