Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 45 for “"Counting problems"”.
-
The complexity of counting problems
… with the computational complexity of several counting problems occurring in graph theory, all of which are related directly to the Tutte polynomial. The Tutte polynomial contains as specialisations many fundamental quantities. Among these are the partition function of the Ising and Potts …
-
Complexity dichotomies of counting problems
Στην παρούσα διπλωματική εργασία μελετάμε θεωρήματα διχοτομίας που αφορούν κυρίως προβλήματα μέτρησης. Ένα θεώρημα διχοτομίας για μια κλάση προβλημάτων, στην υπολογιστική πολυπλοκότητα, είναι μια πλήρης ταξινόμηση των προβλημάτων της οικογένειας σε υπολογιστικά εύκολα και σε υπολογιστικά δύσκολα …
-
Complexity dichotomies for approximations of counting problems
Αυτή η διπλωματική αποτελεί μια επισκόπηση θεωρημάτων διχοτομίας για υπολογιστικά προβλήματα, και ειδικότερα προβλήματα μέτρησης. Θεώρημα διχοτομίας στην υπολογιστική πολυπλοκότητα είναι ένας πλήρης χαρασκτηρισμός των μελών μιας κλάσης προβλημάτων, σε υπολογιστικά δύσκολα και υπολογιστικά εύκολα, …
-
Realization and counting problems for planar structures
… linkages that avoid crossings of bars. We study problems related to self-touching frameworks, in which multiple edges converge to geometrically overlapping configurations. Chapter 2 is about the unfoldability of trees. We show that every monotone tree is unfoldable. A δ-perturbation of a …
-
Independence and counting problems in Combinatorics and Number theory
… become a very important tool for dealing with problems which can be phrased in the language of independent sets in hypergraphs. This method has applications to numerous problems in combinatorics and other areas. In this thesis we consider examples of such problems; in particular problems …
-
Clinical Studies of Counting Problems With Primary School Children
… analyzed to discover children's conceptions of counting. Using various complex counting tasks, the clinical interviews focused on place value, addition, subtraction, and multiplication. Five counting principles proposed by Gelman and Gallistel (1978) and three additional principles proposed by …
-
Parallel Algorithms for Counting Problems on Graphs Using Graphics Processing Units
… graphics processors for solving general purpose problems. Using GPUs for computation is a highly efficient and low-cost alternative as compared to currently available multicore Central Processing Units (CPUs). Also, in the past decade there has been tremendous growth in the World Wide Web and …
-
Extensions of the Pascal Triangle to Words, and Related Counting Problems
… that notably appear in combinatorics to tackle counting problems (for instance, they provide the number of possible ways to choose a given amount of elements from a set of elements). There exist multiple generalizations of those binomial coefficients. In this text, we focus on binomial …
-
On counting problems in nonstandard models of Peano arithmetic with applications to groups
… concerns \(M\) -finite abelian groups, and counting problems for \(M\)-finite groups. We define a notion of cardinality for non-\(M\) -finite sets via the suprema and infima of appropriate \(M\) -finite sets, if these agree we call the set \(M\) -countable. We investigate properties of \(M\) …
-
On structural and descriptive complexity of hard counting problems the decision version of which is easy
… class #P introduced by Valiant, contains the counting versions of NP problems. We focus on #PE, the class of #P functions the decision version of which is in P. In fact, we are mostly interested in a subclass of #PE, namely TotP, which contains all self-reducible #PE functions. TotP has …
-
Approximation algorithms and inapproximability of partition functions of spin systems
<p>Over the past 30 years, the study of counting problems has become an interesting and important work. The framework of counting problems can capture applications in diverse fields, such as graph colouring and homomorphism in graph theory, and the Ising and Potts model from statistical physics. In …
-
Rainbow Colorings in Graphs
… not with the rainbow connection number but with counting of rainbow colorings in graphs with k colors. We introduce the rainbow polynomial and prove some results for some special graph classes. Furthermore, we obtain bounds for the rainbow polynomial. In addition, we define some edge colorings …
-
Efficient Sampling and Counting of Graph Structures related to Chordal Graphs
Counting problems aim to count the number of solutions for a given input, for example, counting the number of variable assignments that satisfy a Boolean formula. Sampling problems aim to produce a random object from a desired distribution, for example, producing a variable assignment drawn …
-
Monte Carlo comparison of back-propagation, conjugate-gradient, and finite-difference training algorithms for multilayer perceptrons
… networks to solve pattern recognition and bit counting problems. Twelve individual simulations will be run for each training algorithm-test problem combination, resulting in an overall total of 72 simulations. The random elements in each Monte Carlo simulation are to be the individual synaptic …
-
On parameterized counting
… analyze the intrinsic hardness of parameterized counting problems. We have analyzed the parameterized complexity of #W(P)-complete problems. We proved that, (under some complexity theoretic hypothesis): <br>1. Any #W(P)-complete is harder than any problem in the A hierarchy. <br>2. Any …
-
On the complexity of counting homomorphisms under surjectivity constraints
… some of the most fundamental combinatorial problems studied in computer science and mathematics. One prominent example is the fact that homomorphisms from a graph G to a triangle (three vertices pairwise connected by edges) correspond to proper 3-colourings of G. </p> <p>Furthermore, …
-
Student Approaches to Combinatorial Enumeration: The Role of Set-Oriented Thinking
… of students' thinking as it relates to counting problems. I interviewed a number of post-secondary students as they solved a variety of combinatorial tasks, and through the analysis of this data I defined and elaborated a construct that I call set-oriented thinking. I describe and …
-
Topics in spectral theory of differential operators /
This dissertation is devoted to two eigenvalue counting problems: Determining the asymptotic behavior of large eigenvalues of self-adjoint extensions of partial differential operators, and computing the number of negative eigenvalues for bounded from below operators with compact resolvents. In the …
Page 1 of 3