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

A Method of Estimating computational complexity Based on Input Conditions for N-vehicle Problem

Acta Mathematicae Applicatae Sinica 2010年第1期26卷 1-12页

作者： Xi Xia Jin-chuan Cui Academy of Mathematics and Systems Science Chinese Academy of Sciences Beijing 100190 China

This paper proposes a method of estimating computational complexity of problem through analyzing its input condition for N-vehicle exploration problem. The N-vehicle problem is firstly formulated to determine the optimal replacement in the set of permutations of 1 to N. The complexity of the problem is factorial of N （input scale of problem）. To balance accuracy and efficiency of general algorithms, this paper mentions a new systematic algorithm design and discusses correspondence between complexity of problem and its input condition, other than just putting forward a uniform approximation algorithm as usual. This is a new technique for analyzing computation of NP problems. The method of corresponding is then presented. We finally carry out a simulation to verify the advantages of the method： 1） to decrease computation in enumeration; 2） to efficiently obtain computational complexity for any N-vehicle case; 3） to guide an algorithm design for any N-vehicle case according to its complexity estimated by the method.

关键词： complexity of computation combinatorial optimization N-vehicle problem permutations inverse order

来源：评论

学校读者我要写书评

暂无评论

ON MALIGN INPUT DISTRIBUTIONS FOR ALGORITHMS

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 1993年第6期E76D卷 634-640页

作者： KOBAYASHI, K Tokyo Inst of Technology Tokyo Japan

By a measure we mean a function mu from {0, 1)* (the set of all binary sequences) to real numbers such that mu (x) greater-than-or-equal-to 0 and mu ({0, 1}*) < infinity. A malign measure is a measure such that if an input x in {0, 1}n (the set of all binary sequences of length n) is selected with the probability mu (x) /mu ({0, 1}n) then the worst-case computation time t(A)wo(n) and the average-case computation time t(A)av,mu (n) of an algorithm A for inputs of length n are functions of n of the same order for any algorithm A. Li and Vitanyi found that measures that are known as a priori measures are malign. We prove that ''a priori''-ness and malignness are different in one stron sense.

关键词： complexity of computation AVERAGE-CASE computation TIME INPUT DISTRIBUTIONS A PRIORI MEASURES MALIGN MEASURES KOLMOGOROV complexity

来源：评论

学校读者我要写书评

暂无评论

LOCALITY, COMMUNICATION, AND INTERCONNECT LENGTH IN MULTICOMPUTERS

引用

SIAM JOURNAL ON COMPUTING 1988年第4期17卷 659-672页

作者： VITANYI, PMB CTR WISKUNDE & INFORMAT 1098 SJ AMSTERDAMNETHERLANDS

We derive a lower bound on the average interconnect (edge) length in d-dimensional embeddings of arbitrary graphs, expressed in terms of diameter and symmetry. It is optimal for all graph topologies we have examined, including complete graph, star, binary n-cube, cube-connected cycles, complete binary tree, and mesh with wraparound (e.g., torus, ring). The lower bound is technology independent, and shows that many interconnection topologies of today’s multicomputers do not scale well in the physical world $(d = 3)$. The new proof technique is simple, geometrical, and works for wires with zero volume, e.g., for optical (fibre) or photonic (fibreless, laser) communication networks. Apparently, while getting rid of the “von Neumann” bottleneck in the shift from sequential to nonsequential computation, a new communication bottleneck arises because of the interplay between locality of computation, communication, and the number of dimensions of physical space. As a consequence, realistic models for nonsequential computation should charge extra for communication, in terms of time and space.

关键词： 68C05 68C25 68A05 68B20 94C99 multicomputers complexity of computation locality communication wire length general communication network edge-symmetric graph binary n-cube cube-connected cycles tree Euclidean embedding scalability optical computing

来源：评论

学校读者我要写书评

暂无评论

A new approach to construction of nearly uniform designs

引用

INTERNATIONAL JOURNAL OF MATERIALS & PRODUCT TECHNOLOGY 2004年第1-3期20卷 115-126页

作者： Ma, CX Fang, KT Hong Kong Baptist Univ Dept Math Kowloon Hong Kong Peoples R China Univ Florida Div Biostat Gainesville FL 32611 USA

The uniform design is one of space filling designs and has been widely used in computer and industrial experiments. Many methods for construction of uniform designs or nearly uniform designs, such as the glp method, optimisation method etc., have been proposed. A nearly uniform design is a design with low-discrepancy, where the discrepancy is a measure of uniformity. Various discrepancies have been suggested. To find a uniform design for n runs and s factors under a given discrepancy is a NP hard problem in the sense of computation complexity when n --> infinity and s > 1. In this paper we propose a new method, called the cutting method, for construction of nearly uniform designs. It shows that the computation load of the new method is light and designs obtained by the new approach have better uniformity.

关键词： complexity of computation computer experiments discrepancy uniform design

来源：评论

学校读者我要写书评

暂无评论

Efficient weighted expressions conversion

引用

RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS 2008年第2期42卷 285-307页

作者： Ouardi, Faissal Ziadi, Djelloul Univ Rouen LITIS F-76821 Mont St Aignan France

Weighted automata are efficient data structures for manipulating regular series. They are used in a lot of practical and theoretical applications such as computer algebra, image encoding, speech recognition or text processing. Regular series are also encoded by regular weighted expressions. The equivalence between these two representations, weighted regular expressions and finite automata has been proved in 1961 by Schutzenberger [16]. For the conversion of weighted regular expressions into weighted automata there are principally three algorithms. The first one is due to Caron and Flouret [4]. Their algorithm works recursively on a subset of weighted regular expressions and produces the position automaton. Champarnaud et al. [7] have given an efficient algorithm that converts a weighted regular expression into its position automaton in quadratic time w.r.t. the size of the expression. Their algorithm is mainly based on the use of the KZPC-structure for weighted expressions. The position automaton is a particular one (see [5]) that can have a quadratic number of transitions and (n + 1) states where n is the alphabetic width of the expression. The algorithm of Lombardy and Sakarovitch [14] constructs a weighted automaton that turns out to be the generalization of Antimirov automaton for the Boolean case. The Antimirov automaton [1] has

关键词： formal languages and automata complexity of computation

来源：评论

学校读者我要写书评

暂无评论

A NONCOMMUTATIVE ALGORITHM FOR MULTIPLYING 5X5 MATRICES USING 102 MULTIPLICATIONS

引用

INFORMATION PROCESSING LETTERS 1986年第3期23卷 115-117页

作者： MAKAROV, OM Institute of Biology of South Seas 2 Nahimov Street Sevastopol 335000 U.S.S.R.

A noncommutative algorithm for multiplying 5 multiplied by 5 matrices using 102 multiplications is presented. Previously, the best algorithm required 38 multiplications.

关键词： Matrix multiplication complexity of computation

来源：评论

学校读者我要写书评

暂无评论

Ulrich complexity

引用

DIFFERENTIAL GEOMETRY AND ITS APPLICATIONS 2017年 55卷 128-145页

作者： Blaeser, Markus Eisenbud, David Schreyer, Frank-Olaf Univ Saarland Math & Informat Campus E1 3 D-66123 Saarbrucken Germany Univ Calif Berkeley Dept Math Berkeley CA 94720 USA Univ Saarland Math & Informat Campus E2 4 D-66123 Saarbrucken Germany

In this note we suggest a new measure of the complexity of polynomials, the Ulrich complexity. Valiant's conjecture on the exponential complexity of the permanent would imply exponential behavior of the Ulrich complexity as well, and this may be easier to prove. We compute some families of examples, one of which has provably exponential behavior. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Ulrich modules complexity of computation Permanents

来源：评论

学校读者我要写书评

暂无评论

Regular subgraphs in graphs and rooted graphs and definability in monadic second-order logic

引用

MATHEMATICAL LOGIC QUARTERLY 1997年第1期43卷 1-21页

作者： Stewart, IA UNIV LEICESTER DEPT MATH & COMP SCILEICESTER LE1 7RHLEICSENGLAND UNIV COLL SWANSEA DEPT COMP SCISWANSEAW GLAMWALES

We investigate the definability in monadic Sigma(1)(1) and monadic Pi(1)(1) of the problems REG(k), of whether there is a regular subgraph of degree k in some given graph, and XREG(k), of whether, for a given rooted graph, there is a regular subgraph of degree k in which the root has degree k, and their restrictions to graphs in which every vertex has degree at most k, namely REG(k)(k), and XREG(k)(k), respectively, for k greater than or equal to 2 (all our graphs are undirected). Our motivation partly stems from the fact (which we prove here) that REG(k)(k) and XRE(k)(k) are logspace equivalent to CONN and REACH, respectively, for k greater than or equal to 3, where CONN is the problem of whether a given graph is connected and REACH is the problem of whether a given graph has a path joining two given vertices. We use monadic first-order reductions, monadic Sigma(1)(1) games and a recent technique due to Fagin, Stockmeyer and Vardi to almost completely classify whether these problems are definable in monadic Sigma(1)(1) and monadic Pi(1)(1), and we compare the definability of these problems (in monadic Sigma(1)(1) and monadic Pi(1)(1)) with their computational complexity (which varies from solvable using logspace to NP-complete).

关键词： descriptive complexity theory definability in second order logic complexity of computation monadic Sigma(1)(1) monadic Pi(1)(1) Ehrenfeucht-Fraisse game Ajtai-Fagin game

来源：评论

学校读者我要写书评

暂无评论

The Inverse of Ackermann Function is Computable in Linear Time

引用

FUNDAMENTA INFORMATICAE 2021年第3期182卷 345-361页

作者： Sureson, Claude Univ Paris 07 5 Rue Thomas Mann F-75013 Paris France

We propose a detailed proof of the fact that the inverse of Ackermann function is computable in linear time.

关键词： Recursive functions complexity of computation

来源：评论

学校读者我要写书评

暂无评论

NEW FAST ALGORITHMS FOR MATRIX OPERATIONS

引用

SIAM JOURNAL ON COMPUTING 1980年第2期9卷 321-342页

作者： PAN, VY

A new technique of trilinear operations of aggregating, uniting and canceling is introduced and applied to constructing fast linear noncommutative algorithms for matrix multiplication. The result is an asymptotic impr... 详细信息

关键词： Fast algorithms complexity of computation arithmetic complexity linear algebraic problems matrix multiplication bilinear forms trilinear form

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：