Search results for " algorithms"
showing 10 items of 612 documents
A loopless algorithm for generating the permutations of a multiset
2003
AbstractMany combinatorial structures can be constructed from simpler components. For example, a permutation can be constructed from cycles, or a Motzkin word from a Dyck word and a combination. In this paper we present a constructor for combinatorial structures, called shuffle on trajectories (defined previously in a non-combinatorial context), and we show how this constructor enables us to obtain a new loopless generating algorithm for multiset permutations from similar results for simpler objects.
A note on Sturmian words
2012
International audience; We describe an algorithm which, given a factor of a Sturmian word, computes the next factor of the same length in the lexicographic order in linear time. It is based on a combinatorial property of Sturmian words which is related with the Burrows-Wheeler transformation.
Improved constructions of mixed state quantum automata
2009
Quantum finite automata with mixed states are proved to be super-exponentially more concise rather than quantum finite automata with pure states. It was proved earlier by A. Ambainis and R. Freivalds that quantum finite automata with pure states can have an exponentially smaller number of states than deterministic finite automata recognizing the same language. There was an unpublished ''folk theorem'' proving that quantum finite automata with mixed states are no more super-exponentially more concise than deterministic finite automata. It was not known whether the super-exponential advantage of quantum automata is really achievable. We prove that there is an infinite sequence of distinct int…
Discrete Mathematics in Lower School Grades? Situation and Possibilities in Italy
2017
This paper presents an overview of the Italian situation in teaching discrete mathematics in primary and middle school, taking into account the national teaching guidelines and their connection with the subject. We describe research conducted with about 150 teachers, interviewed in a preliminary questionnaire. The data collected shows, for all teaching grades, interest in having more discrete mathematics in the school curriculum even if there are some difficulties in teaching it and in inserting it in the usual mathematical activities at school, mostly related to teachers’ knowledge and self-confidence about the subject. We also discuss results and future plans for a continuing research pro…
On the longest common factor problem
2008
The Longest Common Factor (LCF) of a set of strings is a well studied problem having a wide range of applications in Bioinformatics: from microarrays to DNA sequences analysis. This problem has been solved by Hui (2000) who uses a famous constant-time solution to the Lowest Common Ancestor (LCA) problem in trees coupled with use of suffix trees. A data structure for the LCA problem, although linear in space and construction time, introduces a multiplicative constant in both space and time that reduces the range of applications in many biological applications. In this article we present a new method for solving the LCF problem using the suffix tree structure with an auxiliary array that take…
Online Scheduling of Task Graphs on Heterogeneous Platforms
2020
Modern computing platforms commonly include accelerators. We target the problem of scheduling applications modeled as task graphs on hybrid platforms made of two types of resources, such as CPUs and GPUs. We consider that task graphs are uncovered dynamically, and that the scheduler has information only on the available tasks, i.e., tasks whose predecessors have all been completed. Each task can be processed by either a CPU or a GPU, and the corresponding processing times are known. Our study extends a previous $4\sqrt{m/k}$ 4 m / k -competitive online algorithm by Amaris et al. [1] , where $m$ m is the number of CPUs and $k$ k the number of GPUs ( $m\geq k$ m ≥ k ). We prove that no online…
New Encodings of Pseudo-Boolean Constraints into CNF
2009
International audience; This paper answers affirmatively the open question of the existence of a polynomial size CNF encoding of pseudo-Boolean (PB) constraints such that generalized arc consistency (GAC) is maintained through unit propagation (UP). All previous encodings of PB constraints either did not allow UP to maintain GAC, or were of exponential size in the worst case. This paper presents an encoding that realizes both of the desired properties. From a theoretical point of view, this narrows the gap between the expressive power of clauses and the one of pseudo-Boolean constraints.
A genetic system based on simulated crossover of sequences of two-bit genes
2006
AbstractWe introduce a genetic model based on simulated crossover of fixed sequences of two-bit genes. Results are(1)a lower bound on population size is exhibited such that a transition takes the stochastic finite population genetic system near the next state of the deterministic infinite population genetic system (provided both begin in the same state);(2)states and dynamics of the deterministic infinite population genetic system are derived for arbitrary (finite) fitness functions (expressed in terms of multivariate polynomials);(3)in the case of quadratic fitness defined by weight matrices with m nonnull entries it is shown that each state transition can be implemented in time O(m+l), wh…
A Probabilistic Approach to the Count-To-Infinity Problem in Distance-Vector Routing Algorithms
2013
Count-to-infinity problem is characteristic for routing algorithms based on the distributed implementation of the classical Bellman-Ford algorithm. In this paper a probabilistic solution to this problem is proposed. It is argued that by the use of a Bloom Filter added to the routing message the routing loops will with high probability not form. An experimental analysis of this solution for use in Wireless Sensor Networks in practice is also included.
Production Planning in Production Networks: Models for Medium and Short-term Planning
2008
Distributed production networks are structures which are considered able to provide the organisational agility and efficiency necessary to compete in the global market. The performance of such organisations heavily depends on the ability of those involved in the network to coordinate their activities. Two approaches are available for managing complex distributed production networks: a centralised approach, where a unique entity (the planner, for instance) has all the necessary information to make planning decisions for the entire network; or a decentralised approach where each entity in the network has the necessary information and knowledge to make autonomous planning decisions, while the …