Spelling suggestions: "subject:"eounting problems"" "subject:"aounting problems""
1 |
Instance compression of parametric problems and related hierarchiesChakraborty, Chiranjit January 2014 (has links)
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.
|
2 |
Elementos de análise combinatória no ensino fundamental : uma abordagem com mágicas e resolução de problemasBassan, Débora Regina 23 June 2016 (has links)
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.
|
3 |
Métodos de ContagemBezerra, Luis Rodrigo D'Andrada 01 August 2013 (has links)
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.
|
4 |
Problemas de contagem no ensino fundamental : uma experiência com tarefas exploratório-investigativas e registros de representação semióticaLara, Wanderson Mendes de 29 June 2017 (has links)
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.
|
5 |
Sparse instances of hard problemsDell, Holger 01 September 2011 (has links)
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.
|
6 |
Análise combinatória e proposta curricular paulista: um estudo dos problemas de contagemCampos, Carlos Eduardo de 09 November 2011 (has links)
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
|
Page generated in 0.0763 seconds