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

Malign distributions for average case circuit complexity

INFORMATION AND COMPUTATION 1999年第2期150卷 187-208页

作者： Jakoby, A Reischuk, R Schindelhauer, C Univ Lubeck Inst Theoret Informat D-23560 Lubeck Germany

In contrast to machine models like Turing machines or random access machines, circuits are a static computational model. The internal information flow of a computation is fixed in advance, independent of the actual input. Therefore, size and depth are natural and simple measures for circuits and provide a worst-case analysis. We consider a new model in which an internal gate is evaluated as soon as its result has been determined by a partial assignment of its inputs. This way, a dynamic notion of delay is obtained which gives rise to an average case measure for the time complexity of circuits. In a previous paper we have obtained tight upper and lower bounds for the average case complexity of several basic Boolean functions. This paper examines the asymptotic average case complexity for the set of all n-ary Boolean functions. In contrast to worst case analysis a simple counting argument does not work. We prove that with respect to the uniform probability distribution almost all Boolean functions require at least n - log n - log log n expected time. On the other hand, there is a significantly large subset of functions that can be computed with a constant average delay. Finally, for an arbitrary Boolean function we compare its worst case and average case complexity. It is shown that for each function that requires circuit depth d, i.e. of worst case complexity d, the expected time complexity will be at least d - log n - log d with respect to an explicitly defined probability distribution. In addition, a nontrivial upper bound on the complexity of such a distribution will be obtained. (C) 1999 Academic Press.

关键词： average complexity circuit complexity Boolean functions asymptotic complexity malign distributions lower bounds

来源：评论

学校读者我要写书评

暂无评论

On the probabilistic complexity of finding an approximate solution for linear programming

引用

JOURNAL OF complexity 2008年第2期24卷 214-227页

作者： Ji, Jun Potra, Florian A. Univ Maryland Dept Math & Stat Baltimore MD 21250 USA Kennesaw State Univ Dept Math Kennesaw GA 30144 USA

We consider the problem of finding an c-optimal solution of a standard linear program with real data, i.e., of finding a feasible point at which the objective function value differs by at most epsilon from the optimal value. In the worst-case scenario the best complexity result to date guarantees that such a point is obtained in at most O(root n vertical bar ln epsilon vertical bar) steps of an interior-point method. We show that the expected value of the number of steps required to obtain an epsilon-optimal solution for a probabilistic linear programming model is at most O(min {n(1.5), m root n ln(n)}) + log(2)(vertical bar ln epsilon vertical bar). (C) 2007 Elsevier Inc. All rights reserved.

关键词： linear programming interior-point algorithm average complexity approximate solution

来源：评论

学校读者我要写书评

暂无评论

Low complexity dynamic scheduling algorithm for real-time tasks

引用

ELECTRONICS LETTERS 1999年第24期35卷 2106-2108页

作者： Jung, G Kim, T Park, S Choi, K Ajou Univ Sch EE Suwon 442749 South Korea ETRI Taejon 305350 South Korea Ajou Univ Sch IE & CE Suwon 442749 South Korea

It is shown that the problem of maximising the total reward of online tasks can be solved by finding the minimum of the maximum derivatives of the reward functions. Based on the modified approach and a close observati... 详细信息

关键词： real-time tasks processor scheduling average complexity maximum derivatives task arrival characteristics online tasks dynamic scheduling algorithm reward functions Computational complexity heuristic algorithm real-time systems computational complexity

来源：评论

学校读者我要写书评

暂无评论

Software complexity: A statistical case study through insertion sort

引用

APPLIED MATHEMATICS AND COMPUTATION 2007年第1期190卷 40-50页

作者： Kumari, Anchala Chakraborty, Soubhik TM Bhagalpur Univ Marwari Coll Dept Stat Bhagalpur 812007 India Univ Patna Dept Stat Patna 800005 Bihar India

The present paper makes use of factorial experiments to assess software complexity using insertion sort as an example. A new modeling for insertion sort is proposed. It might be of interest to implement the methodolog... 详细信息

关键词： insertion sort average complexity interchanges parameters of input distribution stochastic modeling of deterministic computer experiment software complexity

来源：评论

学校读者我要写书评

暂无评论

complexity information based analysis of pathological ECG rhythm for ventricular tachycardia and ventricular fibrillation

引用

INTERNATIONAL JOURNAL OF BIFURCATION AND CHAOS 2002年第10期12卷 2293-2303页

作者： Zhang, HX Zhu, YS Xu, YH Shanghai Jiao Tong Univ Dept Biomed Engn Shanghai 200030 Peoples R China

Based on surrogate data hypothesis testing method, this paper presents an improved nonlinear algorithm for analyzing deterministic chaotic signals, which can be applied to the analysis of abnormal rhythm electrocardiosignals. Ventricular tachycardia (VT) and ventricular fibrillation (VF) can be treated as nonlinear chaotic signals that are different from stochastic signals. On the basis of qualitative analysis theory in nonlinear dynamics, the authors forwarded a new definition of complexity rate and developed several relative detection methods for quantitative analysis of VT and VF. The results indicated that these qualitative analysis and quantitative analysis of VT and VF are objective and credible.

关键词： surrogate data test (SDT) complexity dispersity L-Z complexity complexity rate average complexity complexity saturation

来源：评论

学校读者我要写书评

暂无评论

FAST NEAREST-NEIGHBOR SEARCH IN DISSIMILARITY SPACES

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 1993年第9期15卷 957-962页

作者： FARAGO, A LINDER, T LUGOSI, G Tech. Univ. of Budapest Hungary

A fast nearest-neighbor algorithm is presented. It works in general spaces where the known cell (bucketing) techniques cannot be implemented for various reasons, such as the absence of coordinate structure and/or high dimensionality. The central idea has already appeared several times in the literature with extensive computer simulation results. This paper provides an exact probabilistic analysis or this family of algorithms, proving its O(1) asymptotic average complexity measured in the number of dissimilarity calculations.

关键词： average complexity DISSIMILARITY SPACES FAST NEAREST-NEIGHBOR SEARCH PATTERN RECOGNITION PROBABILISTIC ANALYSIS OF ALGORITHMS

来源：评论

学校读者我要写书评

暂无评论

Replacement sort revisited: The "gold standard" unearthed!

引用

APPLIED MATHEMATICS AND COMPUTATION 2007年第1期189卷 384-394页

作者： Chakraborty, Soubhik Sourabh, Suman Kumar Bose, Mausumi Sushant, Kumar Bhagalpur Univ Univ Dept Stat & Comp Appl Bhagalpur 812007 India Indian Stat Inst Appl Stat Unit Kolkata 700108 India BIT Mesra Dept Appl Phys Ranchi 835215 Bihar India

The present paper shows that for certain algorithms such as sorting, the parameters of the input distribution must also be taken into account, apart from the input size, for a more precise evaluation of computational and time complexity (average case only) of the algorithm in question (the so-called "gold standard"). Some concrete results are presented to warrant a new and improved model for replacement sort (also called selection sort) as [GRAPHICS] where the LHS gives the average case time complexity, n is the input size, pi's the parameters of the input distribution characterizing the sorting elements, i is the average number of interchanges which is a function of both the input size and the parameters, the rest of the terms arising due to linear regression and have usual meanings. The error term E arises as we have fixed only the input size n in the model but varying the specific input elements and their relative positions in the array, for a particular distribution [H. Mahmoud, Sorting: A Distribution Theory, John Wiley and Sons, 2000]. The term n(n - 1)/2 represents the number of comparisons. We claim this to be an improvement over the conventional model, namely, [GRAPHICS] which stems from the O(n(2)) complexity for this algorithm. We argue that the new model in our opinion can be a guiding factor in distinguishing this algorithm from other sorting algorithms of similar order of average complexity such as bubble sort and insertion sort. Note carefully that the dependence of the number of interchanges on the parameters is more prominent for discrete distributions rather than continuous ones and we suspect this to be because the probability of a tie is zero in a continuous case. However, presence of ties and their relative positions in the array is crucial for discrete cases. And this is precisely where the parameters of the input distribution come into play. Those algorithms where ties have a greater influence on some of the computations will have greater infl

关键词： replacement sort parameters of input distribution average complexity interchanges stochastic realization of a deterministic computer experiment

来源：评论

学校读者我要写书评

暂无评论

average case behavior of random search for the maximum

引用

JOURNAL OF APPLIED PROBABILITY 1997年第3期34卷 632-642页

作者： Calvin, JM Glynn, PW STANFORD UNIV DEPT OPERAT RESSTANFORDCA 94305

This paper is a study of the error in approximating the global maximum of a Brownian motion on the unit interval by observing the value at randomly chosen points. One point of view is to look at the error from random sampling for a given fixed Brownian sample path;another is to look at the error with both the path and observations random. In the first case we show that for almost all Brownian paths the error, normalized by multiplying by the square root of the number of observations, does not converge in distribution, while in the second case the normalized error does converge in distribution. We derive the limiting distribution of the normalized error averaged over all paths.

关键词： Brownian motion global optimization average complexity

来源：评论

学校读者我要写书评

暂无评论

ON LINEAR-PROGRAMS WITH RANDOM COSTS

引用

MATHEMATICAL PROGRAMMING 1986年第1期35卷 3-16页

作者： DYER, ME FRIEZE, AM MCDIARMID, CJH UNIV LONDON QUEEN MARY COLL DEPT COMP SCI & STATLONDON E1 4NSENGLAND UNIV OXFORD INST ECON & STATOXFORDENGLAND

We consider linear programs in which the objective function (cost) coefficients are independent non-negative random variables, and give upper bounds for the random minimum cost. One application shows that for quadrati... 详细信息

关键词： Random linear program probabilistic analysis of algorithms average complexity quadratic assignment problem branch-and-bound

来源：评论

学校读者我要写书评

暂无评论

On the average condition number of tensor rank decompositions

引用

IMA JOURNAL OF NUMERICAL ANALYSIS 2020年第3期40卷 1908-1936页

作者： Breiding, Paul Vannieuwenhoven, Nick Max Planck Inst Math Sci Inselstr 22-26 D-04103 Leipzig Germany Katholieke Univ Leuven Dept Comp Sci Celestijnenlaan 200A B-3001 Heverlee Belgium

We compute the expected value of powers of the geometric condition number of random tensor rank decompositions. It is shown in particular that the expected value of the condition number of n(1) x n(2) x 2 tensors with a random rank-r decomposition, given by factor matrices with independent and identically distributed standard normal entries, is infinite. This entails that it is expected and probable that such a rank-r decomposition is sensitive to perturbations of the tensor. Moreover, it provides concrete further evidence that tensor decomposition can be a challenging problem, also from the numerical point of view. On the other hand, we provide strong theoretical and empirical evidence that tensors of size n(1) x n(2) x n(3) with all (n)1, n(2), n(3) >= 3 have a finite average condition number. This suggests that there exists a gap in the expected sensitivity of tensors between those of format n(1) x n(2) x 2 and other order-3 tensors. To establish these results we show that a natural weighted distance from a tensor rank decomposition to the locus of ill-posed decompositions with an infinite geometric condition number is bounded from below by the inverse of this condition number. That is, we prove one inequality towards a so-called condition number theorem for the tensor rank decomposition.

关键词： tensor rank decomposition CPD condition number ill-posed problems inverse distance to ill-posedness average complexity condition number theorem

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：