检索结果-内蒙古大学图书馆

On the Definitions of Sufficiency and Elegance in Systems Design

IEEE SYSTEMS JOURNAL 2019年第3期13卷 2077-2088页

作者： Efatmaneshnik, Mahmoud Ryan, Michael J. Univ New South Wales Canberra Australian Def Force Acad Sch Engn & Informat Technol Canberra ACT 2612 Australia

Despite elegance being universally recognized as a goal for system design, there is little guidance in the related research and literature that is relevant to the design, development, or evaluation of elegant systems. This paper begins by reviewing the rather loose usage of elegance as a property of a system and shows that there are both abstract and practical views. Further, from analysis of the practical views of elegance in systems, it is clear that most current definitions of elegance are focused on the sufficiency of the system as a solution to the stated problem, rather than on elegance, perse. This paper disambiguates the usage of sufficiency and elegance, offers a formal definition of the two terms, and then provides several simple examples by way of illustration. Elegance and sufficiency must he considered as separate properties of a system, if only because the essential act of validation is an examination of the sufficiency of a solution, not its elegance. Any system attribute desired by the customer must be included as part of the solution's sufficiency and designed into the solution, not be a serendipitous unintended outcome of that design. Sufficiency is shown to be binary-a solution is either sufficient or it is not-and there may be more than one sufficient solution. Elegance is then defined to be the least complex sufficient solution. Furthermore, an elegant solution must be sufficient, but a sufficient system does not have to be (and is not always desirable to be) elegant.

关键词： complexity measure elegance elegant design problem complexity solution complexity system design

来源：评论

学校读者我要写书评

暂无评论

On the power of randomized multicounter machines

引用

THEORETICAL COMPUTER SCIENCE 2005年第1期330卷 135-144页

作者： Hromkovic, J Schnitger, G Swiss Fed Inst Technol ETH Zentrum Dept Comp Sci CH-8092 Zurich Switzerland Goethe Univ Frankfurt Inst Informat D-60054 Frankfurt Germany

One-way two-counter machines represent a universal model of computation. Here we consider the polynomial-time classes of multicounter machines with a constant number of reversals and separate the computational power of nondeterminism, randomization and determinism. For instance. we show that polynomial-time one-way multicounter machines. with error probability tending to zero with growing input length, can recognize languages that cannot be accepted by polynomial-time nondeterministic two-way multicounter machines with a bounded number of reversals. A similar result holds for the comparison of determinism and one-sided-error randomization. and of determinism and Las Vegas randomization. (C) 2004 Elsevier B.V. All rights reserved.

关键词： problem complexity randomness determinism nondeterminism multicounter machines

来源：评论

学校读者我要写书评

暂无评论

Directionality-centric bus transit network segmentation for on-demand public transit

引用

IET INTELLIGENT TRANSPORT SYSTEMS 2020年第13期14卷 1871-1881页

作者： Perera, Thilina Wijesundera, Deshya Wijerathna, Lahiru Srikanthan, Thambipillai Nanyang Technol Univ Sch Comp Sci & Engn 50 Nanyang Ave Singapore Singapore Univ Moratuwa Dept Elect & Telecommun Engn Moratuwa Sri Lanka

The recent growth in real-time, high-capacity ride-sharing has made on-demand public transit (ODPT) a reality. ODPT systems serving passengers using a vehicle fleet that operates with flexible routes, strive to minimise fleet travel distance. Heuristic routing algorithms have been integrated in ODPT systems in order to improve responsiveness. However, route computation time in such algorithms depends on problem complexity and hence increases for large scale problems. Thus, network segmentation techniques that exploit parallel computing have been proposed in order to reduce route computation time. Even though computation time can be reduced using segmentation in existing techniques, it comes at the cost of degradation of route quality due to static demarcation of boundaries and disregarding real road network distances. Thus, this work proposes, a directionality-centric bus transit network segmentation technique that exploits parallel computation capable of computing routes in near real-time while providing high scalability. Additionally, a dynamic fleet allocation algorithm that exploits proximity and flexibility to minimise vehicle detours while maximising fleet utilisation is proposed. Experimental evaluations on a real road network confirm that the proposed method achieves notable speed-up in flexible route computation without compromising route quality compared to a widely used unsupervised learning technique.

关键词： road vehicles road traffic resource allocation minimisation vehicle routing on-demand public transit ODPT systems vehicle fleet flexible routes fleet travel distance heuristic routing algorithms route computation time problem complexity network segmentation techniques parallel computing route quality road network distances directionality-centric bus transit network segmentation technique parallel computation dynamic fleet allocation algorithm fleet utilisation flexible route computation high-capacity ride-sharing

来源：评论

学校读者我要写书评

暂无评论

Parallel machine scheduling with maintenance activities

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2016年 101卷 361-371页

作者： Yoo, Jaewook Lee, Ik Sun Dong A Univ Sch Business Busan 602760 South Korea

This paper considers a problem of scheduling on parallel machines where each machine requires maintenance activity once over a given time window. The objective is to find a coordinated schedule for jobs and maintenance activities to minimize the scheduling cost represented by either one of several objective measures including makespan, (weighted) sum of completion times, maximum lateness and sum of lateness. The problem is proved to be NP-hard in the strong sense in each case of the objective measures. Some restricted cases of the problem are also characterized for their complexities, for which the associated dynamic programming algorithms are derived. (C) 2016 Elsevier Ltd. All rights reserved.

关键词： Scheduling Maintenance Parallel machine problem complexity

来源：评论

学校读者我要写书评

暂无评论

A vector-based approach to software size measurement and effort estimation

引用

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING 2001年第4期27卷 337-350页

作者： Hastings, TE Sajeev, ASM Monash Univ Sch Comp Sci & Software Engn Caulfield Vic 3145 Australia Univ Newcastle Dept Comp Sci & Software Engn Newcastle NSW 2308 Australia

Software size is a fundamental product measure that can be used for assessment, prediction, and improvement purposes. However, existing software size measures, such as Function Points, do not address the underlying problem complexity of software systems adequately. This can result in disproportional measures of software size for different types of systems. We propose a Vector Size Measure (VSM) that incorporates both functionality and problem complexity in a balanced and orthogonal manner. VSM is used as the input to a Vector Prediction Model (VPM) which can be used to estimate development effort early in the software life cycle. We theoretically validate the approach against a formal framework. We also empirically validate the approach with a pilot study. The results indicate that the approach provides a mechanism to measure the size of software systems, classify software systems, and estimate development effort early in the software life cycle to within +/-20 percent across a range of application types.

关键词： algebraic specification effort estimation functionality gradient magnitude problem complexity semantic properties software metrics software size software life cycle software specification syntactic properties validation vector

来源：评论

学校读者我要写书评

暂无评论

SINGLE PATH ROUTING WITH DELAY CONSIDERATIONS

COMPUTER NETWORKS AND ISDN SYSTEMS

引用

COMPUTER NETWORKS AND ISDN SYSTEMS 1992年第5期24卷 405-419页

作者： SIMHA, R NARAHARI, B COLL WILLIAM & MARY DEPT COMP SCIWILLIAMSBURGVA 23185 GEORGE WASHINGTON UNIV DEPT ELECT ENGN & COMP SCIWASHINGTONDC 20052

The importance of optimal routing arises in high traffic networks where the average delay across a link is sensitive to the assignment of routes to source-destination pairs. The current single path routing algorithms do not take into account the effects of routing multiple source-destination pairs over common links and, consequently, may not lead to a minimum delay allocation of routes. In this paper we formulate and study the problem of minimizing queueing delays by explicitly considering the impact of overlapping routes on links. The problem is shown to be NP-Complete. Specifically, we prove that the problem of finding a feasible solution is NP-Complete and thus no polynomial time approximation algorithms exist that provide solutions within a bounded distance from the optimum. Similar complexity results are shown when we consider the special case of a ring network and where it is desirable to minimize packet losses. We provide a polynomial time algorithm for constructing a minimum spanning tree within our routing model for the purpose of broadcasting. A new heuristic to minimize delays, the Sequential Minimum Costs algorithm is proposed for the case of a single source and multiple destinations.

关键词： ROUTING SINGLE PATH ROUTING SHORTEST PATHS problem complexity SPANNING TREES

来源：评论

学校读者我要写书评

暂无评论

Recovering signals from inner products involving prolate spheroidals in the presence of jitter

引用

MATHEMATICS OF COMPUTATION 2005年第249期74卷 279-290页

作者： Dabrowska, D Cardinal Stefan Wyszynski Univ Warsaw Fac Math & Sci PL-01815 Warsaw Poland

The paper deals with recovering band- and energy-limited signals from a finite set of perturbed inner products involving the prolate spheroidal wavefunctions. The measurement noise ( bounded by delta) and jitter meant as perturbation of the ends of the integration interval ( bounded by gamma) are considered. The upper and lower bounds on the radius of information are established. We show how the error of the best algorithms depends on gamma and delta. We prove that jitter causes error of order Omega 3/2 gamma, where [-Omega, Omega] is a bandwidth, which is similar to the error caused by jitter in the case of recovering signals from samples.

关键词： problem complexity signal theory application of orthogonal functions communication

来源：评论

学校读者我要写书评

暂无评论

ON THE ORDERS OF THE SUBSEMIGROUPS OF THE SYMMETRICAL SEMIGROUP TAU-N

引用

SEMIGROUP FORUM 1980年第4期21卷 329-335页

作者： TODOROV, K Department of Mathematics Bul. “A. Ivanov” 5 1126 Sofia

来源：评论

学校读者我要写书评

暂无评论

On Isomorphism Testing of Groups with Normal Hall Subgroups

引用

Journal of Computer Science & Technology 2012年第4期27卷 687-701页

作者：乔友明 Jayalal Sarma M.N 唐邦晟 Institute for Theoretical Computer Science Tsinghua University Department of Computer Science and Engineering Indian Institute of Technology Madras

A normal Hall subgroup N of a group G is a normal subgroup with its order coprime with its index. Schur- Zassenhaus theorem states that every normal Hall subgroup has a complement subgroup, that is a set of coset representatives H which also forms a subgroup of G. In this paper, we present a framework to test isomorphism of groups with at least one normal Hall subgroup, when groups are given as multiplication tables. To establish the framework, we first observe that a proof of Schur-Zassenhaus theorem is constructive, and formulate a necessary and sufficient condition for testing isomorphism in terms of the associated actions of the semidirect products, and isomorphisms of the normal parts and complement parts. We then focus on the case when the normal subgroup is abelian. Utilizing basic facts of representation theory of finite groups and a technique by Le Gall （STACS 2009）, we first get an efficient isomorphism testing algorithm when the complement has bounded number of generators. For the case when the complement subgroup is elementary abelian, which does not necessarily have bounded number of generators, we obtain a polynomial time isomorphism testing algorithm by reducing to generalized code isomorphism problem, which asks whether two linear subspaces are the same up to permutation of coordinates. A solution to the latter can be obtained by a mild extension of the singly exponential （in the number of coordinates） time algorithm for code isomorphism problem developed recently by Babai et al. （SODA 2011）. Enroute to obtaining the above reduction, we study the following computational problem in representation theory of finite groups： given two representations ρandτ- of a group H over Zp^d, a prime, determine if there exists an automorphism ： ФH→ H, such that the induced representation p Ф= ρ o Ф and τ are equivalent, in time poly（｜H｜, p^d）.

关键词： group isomorphism normal Hall subgroup isomorphism testing problem complexity

来源：评论

学校读者我要写书评

暂无评论

General techniques for analyzing recursive algorithms with applications

引用

SIAM JOURNAL ON COMPUTING 1997年第2期26卷 568-581页

作者： Verma, RM UNIV HOUSTON DEPT COMP SCI HOUSTON TX 77004 USA

The complexity of divide-and-conquer algorithms is often described by recurrences of various forms. In this paper, we develop general techniques and master theorems for solving several kinds of recurrences, and we give several applications of our results. In particular, almost ail of the earlier work on solving the recurrences considered here is subsumed by our work. In the process of solving such recurrences, we establish interesting connections between some elegant mathematics and analysis of recurrences. Using our results and improved bipartite matching algorithms, we also improve existing bounds in the literature for several problems, viz, associative-commutative (AC) matching of linear terms, associative matching of linear terms, rooted subtree isomorphism, and rooted subgraph homeomorphism for trees.

关键词： analysis of algorithms divide-and-conquer recurrences problem complexity subtree isomorphism associative-commutative (AC) matching graph algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：