共查询到20条相似文献,搜索用时 31 毫秒
1.
The (2
w
)! reversible transformations on w wires, i.e. reversible logic circuits with w inputs and w outputs, together with the action of cascading, form a group, isomorphic to the symmetric group S
2
w
. Therefore, we investigate the group S
n
as well as one of its subgroups isomorphic to S
n/2 × S
n/2. We then consider the left cosets, the right cosets, and the double cosets generated by the subgroup. Each element of a coset
can function as the representative of the coset. The coset can then be considered as the set of all group elements that differ
from the representative by merely multiplying (either to the left or to the right or to both sides) by an arbitrary element
of the subgroup. Different choices of the coset space and different choices of the coset representatives lead to six different
syntheses for implementing an arbitrary reversible logic operation into hardware. Evaluation of all six methods, by means
of three different cost functions (gate cost, switch cost, and quantum cost), leads to a best choice. 相似文献
2.
The search for edge-disjoint Hamilton cycles in star graphs is important for the design of interconnection network topologies. We define automorphisms for star graphs St n of degree n?1, for every positive odd integer n, which yield permutations of labels for the edges of St n taken from the set of integers between 1 and ? n/2 ?. By decomposing these permutations into permutation cycles, we are able to identify edge-disjoint Hamilton cycles that are automorphic images of a known Hamilton cycle in St n . Our method produces a better than two-fold improvement from ? ? ( n)/10 ? to ? 2? ( n)/9 ?, where ? is the Euler function, for the known number of edge-disjoint Hamilton cycles in St n for all odd integers n. For prime n, the improvement is from ? n/8 ? to ? n/5 ?, and we can extend this result to the case when n is the power of a prime greater than 7. 相似文献
3.
A design procedure for complete substitution-permutation encryption networks is presented. The cryptographically important property of completeness is achieved after three iterations, the minimum possible number for all networks of size N = i · n2 ( i = 1,2,…, n), where n is the size of the substitution function used. The permutation stage is constructed by choosing a single member of a class of cryptographically equivalent permutations for all the network rounds, hence having the advantage of simplifying the network implementation. An algorithm for generating members of the class of cryptographically equivalent permutations is given. 相似文献
4.
Given k permutations of n elements, a k-tuple of intervals of these permutations consisting of the same set of elements is called a common interval. We present an algorithm that finds in a family of k permutations of n elements all z common intervals in optimal O( kn+ z) time and O( n) additional space. Additionally, we show how to adapt this algorithm to multichromosomal and circular permutations. 相似文献
5.
Currently, there is no enforcement of physical standards within Australian fire services post-recruitment, possibly leading to inappropriate fitness and body composition. This study evaluated the impacts of ageing on physical standards of Australian firefighters. Seventy-three firefighters from three different 10-year age groups [25–34 years ( n = 27), 35–44 years ( n = 27), 45–54 years ( n = 19)] volunteered for physical testing using dual-energy X-ray analysis and existing fitness tests used for recruitment by an Australian fire service. Older (45–54 years) participants demonstrated significantly poorer physical standards compared with younger participants including cardiovascular fitness ( p < 0.05), strength ( p = 0.001) and simulated operational power testing tasks ( p < 0.001). Age-related body composition changes were also observed independent of body mass index. Minimum recruitment standards and fitness programs need to account for age-related declines in physical capabilities to ensure that the minimum standard is maintained regardless of age. Practitioner Summary: Using dual-energy X-ray analysis and established fitness testing protocols, this study aimed to gain an appreciation of the current standards of body composition and fitness of Australian firefighters and the effects of ageing on their physical abilities post-recruitment. The study demonstrated a significant decline in physical standards due to age. 相似文献
6.
Post-quantum cryptography has drawn considerable attention from cryptologists on a global scale. At Asiacrypt 2017, Leander and May combined Grover’s and Simon’s quantum algorithms to break the FX-based block ciphers, which were introduced by Kilian and Rogaway to strengthen DES. In this study, we investigate the Feistel constructions using Grover’s and Simon’s algorithms to generate new quantum key-recovery attacks on different rounds of Feistel constructions. Our attacks require 2 0.25nr?0.75n quantum queries to break an r-round Feistel construction. The time complexity of our attacks is less than that observed for quantum brute-force search by a factor of 2 0.75n. When compared with the best classical attacks, i.e., Dinur et al.’s attacks at CRYPTO 2015, the time complexity is reduced by a factor of 2 0.5n without incurring any memory cost. 相似文献
7.
In (2 n−1)-stage rearrangeable networks, the routing time for any arbitrary permutation is Ω( n2) compared to its propagation delay O( n) only. Here, we attempt to identify the sets of permutations, which are routable in O( n) time in these networks. We define four classes of self-routable permutations for Benes network. An O( n) algorithm is presented here, that identifies if any permutation P belongs to one of the proposed self-routable classes, and if yes, it also generates the necessary control vectors for routing P. Therefore, the identification, as well as the switch setting, both problems are resolved in O( n) time by this algorithm. It covers all the permutations that are self-routable by anyone of the proposed techniques. Some interesting relationships are also explored among these four classes of permutations, by applying the concept of ‘ group-transformations’ [N. Das, B.B. Bhattacharya, J. Dattagupta, Hierarchical classification of permutation classes in multistage interconnection networks, IEEE Trans. Comput. (1993) 665–677] on these permutations. The concepts developed here for Benes network, can easily be extended to a class of (2 n−1)-stage networks, which are topologically equivalent to Benes network. As a result, the set of permutations routable in a (2 n−1)-stage rearrangeable network, in a time comparable to its propagation delay has been extended to a large extent. 相似文献
8.
Proposed was an approach enabling one to reduce studies of the properties of ordinal relations for criteria with an arbitrary (including finite) set of values to similar problems for relations defined over the entire n-dimensional real space R
n. It enabled one to prove that all main findings, methods, and algorithms obtained previously for the ordinal relations on R
n can be extended in arbitrary criterial spaces to the ordinal relations with the criterion scale cardinalities not less than three. 相似文献
9.
We find the maximal number of permutations on a set of n elements such that any pair of permutations has at least t common cycles. 相似文献
10.
Algorithms are presented for realizing permutations on a less restrictive hypercube model called the S-MIMD (synchronous MIMD), which allows at most one data transfer on a given communication link at a given time instant, and where data movements are not restricted to a single dimension at a given time. First, an optimal algorithm for bit-permute permutations is developed from a very simple realization of the shuffle on a 3-cube; this algorithm needs 2⌊ n/2⌋ routing steps on an n-dimensional hypercube. The technique is then extended to an optimal algorithm for bit-permute-complement permutations, one that needs n routing steps. Also, algorithms are sketched for routing permutations in the classes Ω and Ω −1 in 3⌈ n/2⌉ routing steps, yielding an off-line algorithm for routing arbitrary permutations in 3 n steps. 相似文献
11.
Feistel ciphers (balanced and unbalanced) represent the most popular symmetric cipher type in modern cryptography. The invention of Feistel ciphers is usually credited to IBM’s Horst Feistel, who co-created the first publicly known encryption algorithm of this type, Lucifer, in the early 1970s. In this publication, the authors will show that Feistel ciphers (or at least a very similar concept) played a surprisingly important role in East Germany in the last two decades of the communism era (i.e., between 1970 and 1990). They will introduce four Feistel ciphers developed by East German cryptologists during these two decades. This includes an unbalanced Feistel cipher that predated RC2, the oldest unbalanced Feistel cipher known in the crypto community (by over a decade), as well as an East German DES variant. 相似文献
12.
Motivated by the problem in computational biology of reconstructing the series of chromosome inversions by which one organism evolved from another, we consider the problem of computing the shortest series of reversals that transform one permutation to another. The permutations describe the order of genes on corresponding chromosomes, and a reversal takes an arbitrary substring of elements, and reverses their order.For this problem, we develop two algorithms: a greedy approximation algorithm, that finds a solution provably close to optimal in O( n
2) time and 0(n) space for n-element permutations, and a branch- and-bound exact algorithm, that finds an optimal solution in 0(mL(n, n)) time and 0( n
2) space, where m is the size of the branch- and-bound search tree, and L(n, n) is the time to solve a linear program of n variables and n constraints. The greedy algorithm is the first to come within a constant factor of the optimum; it guarantees a solution that uses no more than twice the minimum number of reversals. The lower and upper bounds of the branch- and-bound algorithm are a novel application of maximum-weight matchings, shortest paths, and linear programming.In a series of experiments, we study the performance of an implementation on random permutations, and permutations generated by random reversals. For permutations differing by k random reversals, we find that the average upper bound on reversal distance estimates k to within one reversal for k<1/2n and n<100. For the difficult case of random permutations, we find that the average difference between the upper and lower bounds is less than three reversals for n<50. Due to the tightness of these bounds, we can solve, to optimality, problems on 30 elements in a few minutes of computer time. This approaches the scale of mitochondrial genomes.This research was supported by a postdoctoral fellowship from the Program in Mathematics and Molecular Biology of the University of California at Berkeley under National Science Foundation Grant DMS-8720208, and by a fellowship from the Centre de recherches mathématiques of the Université de Montréal.This research was supported by grants from the Natural Sciences and Engineering Research Council of Canada, and the Fonds pour la formation de chercheurs et l'aide à la recherche (Québec). The author is a fellow of the Canadian Institute for Advanced Research. 相似文献
13.
This study compared three-dimensional trunk and pelvis range of motion (ROM) during a sustained asymmetric box lift/lower task between a group with a history of low back pain (HBP, n = 9) and a group with no history of low back pain (NBP, n = 9). Participants lifted an 11-kg box for 10 min at 12 cycles/min from ankle height in front to shelves 45 deg off-centre at waist height. Kinematic data were collected at the beginning (min1), middle (min5) and end of the bout (min9). Two-way analyses of variance were performed for all variables. Pelvis and trunk transverse ROM were similar at min1. By min9, HBP group did not change (31.9 ± 9 deg); however, ROM decreased in NBP group (21.6 ± 6 deg, p < 0.05). Therefore, despite no current pain, the HBP group demonstrated protective lifting mechanics compared to controls. Also discussed are implications for studying lifting paradigms at sub-maximal effort over longer periods of time. Practitioner summary: Differences between groups over time demonstrate residual consequences of low back pain (LBP) in a manual materials handling scenario. Individuals with a history of LBP (pain free for 6 months) demonstrated more conservative lifting mechanics towards the end of the bout compared to controls with no history of LBP. 相似文献
14.
Linear control systems governed by the vector matrix differential equation x = A x + B u have been considered. It has been shown how to find the optimum control u so that the system, starting from an initial position x(0), is steered to a state specifying the first p coordinates of the system in time t o fixed in advance, the values attained by the ( n— p) coordinates being immaterial, where n is the dimension of the system. The optimization considered here is with regard to the norm of u supposed to belong to L m E r space. 相似文献
15.
This study shows that a controllable system [xdot] = Ax + Bu, where x is an n-vector, can be driven from an arbitrary initial condition x(0) = x0 to an arbitrary final condition x(tf = xf by a polynomial control function of degree M = 2 r + 1, where r = n ? rank ( B), through a polynomial trajectory of degree M. A simple algorithm for finding u by solving a set of linear equations, the solution of which yields the polynomial coefficients, is given. 相似文献
16.
Reducing sitting time by means of sit–stand workstations is an emerging trend, but further evidence is needed regarding their health benefits. This cross-sectional study compared work time muscle activity patterns and spinal shrinkage between office workers (aged 24–62, 58.3% female) who used either a sit–stand workstation (Sit–Stand group, n = 10) or a traditional sit workstation (Sit group, n = 14) for at least the past three months. During one typical workday, muscle inactivity and activity from quadriceps and hamstrings were monitored using electromyography shorts, and spinal shrinkage was measured using stadiometry before and after the workday. Compared with the Sit group, the Sit–Stand group had less muscle inactivity time (66.2 ± 17.1% vs. 80.9 ± 6.4%, p = 0.014) and more light muscle activity time (26.1 ± 12.3% vs. 14.9 ± 6.3%, p = 0.019) with no significant difference in spinal shrinkage (5.62 ± 2.75 mm vs. 6.11 ± 2.44 mm). This study provides evidence that working with sit–stand workstations can promote more light muscle activity time and less inactivity without negative effects on spinal shrinkage. Practitioner Summary: This cross-sectional study compared the effects of using a sit–stand workstation to a sit workstation on muscle activity patterns and spinal shrinkage in office workers. It provides evidence that working with a sit–stand workstation can promote more light muscle activity time and less inactivity without negative effects on spinal shrinkage. 相似文献
17.
ABSTRACT This paper presents a symmetric cipher that is actually a variation of the Hill cipher. The new scheme makes use of “random” permutations of columns and rows of a matrix to form a “different” key for each data encryption. The cipher has matrix products and permutations as the only operations which may be performed “efficiently” by primitive operators, when the system parameters are carefully chosen. 相似文献
18.
This paper addresses the problem of the offline routing of arbitrary permutations on hypercubes under the MIMD queueless communication constraints which imposes that only one message can be located in each node of the hypercube right through the routing. According to e-cube routing, this kind of communication may require in the worst cases at least n exchanges steps on an n-dimensional hypercube. It has been conjectured that in the general case n steps suffice. The conjecture has been proved either by enumeration or by program for the particular cases of n??3. We revisit the problem through the k-partitioning paradigm based on maximum matching of bipartite graphs concept to take advantage of the recursive structure of the hypercube topology. The paradigm consists in looking for each message a transition node distant of at most say k< n hops from its current node such that all the messages can be routed to their transition nodes in k hops then finally routed to their final destination nodes in n? k hops on two disjoints hypercubes. In others words, the paradigm consists to determine an upstream permutation routable in k steps and which leads to two independent downstream permutations routable in n? k steps on two disjoint hypercubes. With this purpose, we give a characterization of the non-1-partitionable permutations from which the proof of the conjecture comes straightforwardly for n??2 and the non-1-partitionable permutations can be built whatever n may be. For n=3, we thus confirm the existence of exactly three classes of non-1-partitionable permutations and prove that there are two classes of upstream permutations to avoid when 2-partitioning any non-1-partitionable permutation. The process to avoid such upstream permutations is presented, and leads to a formal proof of the conjecture for n=3. For n>3, experiences gained in routing permutations on 4 D-hypercubes allow conjecturing that in these cases, too, any non-1-partitionable permutation is 2-partitionable. Indeed, the analysis carried out for the 3 D-hypercubes is repeatable to identify, certainly more laboriously given their combinatory, the upstream permutations to avoid when 2-partitioning a non-1-partitionable permutation on a 4 D-hypercube. The proof that resulting downstream permutations on a 3 D-hypercube can be routed in 2 steps is a consequence of the fact that for n=2 and 3 any permutation on a nD-hypercube can be routed in n steps. 相似文献
19.
Attention can be captured by distractors and can affect performance. To examine whether asymmetrical distractors, such as a wall, affect spatial attention, Experiment 1 required participants ( n = 20) to determine the relative length of pre-bisected lines when a temporary barrier was placed close to the left or right sides of the display. Post-hoc tests showed that attention was drawn towards left, but not right, walls. Experiment 2 ( n = 18) sought to increase this effect using a solid brick wall rather than a temporary barrier. Instead of strengthening the result, no effect of barrier was observed. A non-effect was also observed in Experiment 3 ( n = 18) when participants moved a cursor to the line's middle. Finally, Experiment 4 ( n = 26) showed that asymmetrical barriers had no effect on visual search. While the data showed some evidence that attention is distracted by walls placed to the left, this effect is weak and task-specific. Practitioner Summary: The ability to monitor critical information on displays can be affected by asymmetrical distractors. In many workplaces, a display may be placed alongside a wall. This study explored whether a wall placed to the left/right affects spatial attention. A weak, task-specific, attraction effect was observed for walls on the left. 相似文献
20.
In modern business environments, work and tasks have become more complex and require more interdisciplinary skills to complete, including collaborative and computing skills for website design. However, the computing education in Taiwan can hardly be recognised as effective in developing and transforming students into competitive employees. In this regard, the author adopted collaborative learning (CL) with initiation and self-regulated learning (SRL) with feedback to develop students' collaborative skills and regular learning habits and further contribute to practical computing skills for website design. This study comprised an experiment that included 279 second-year university students from five class sections, including four experimental groups (CISF group, n = 57; CIS group, n = 53; CI group, n = 68; C group, n = 68), and a control group (T group, n = 33). The results reveal that students who received the combined treatment of online CL with initiation and SRL with feedback attained the best grades for their computing skills for website design among the five groups. The author further discusses the implications for teachers, schools and educators who plan to design practical scenarios and online learning activities for their students. 相似文献
|