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

Optimal search procedure on coin-weighing problem

JOURNAL OF STATISTICAL PLANNING AND INFERENCE 2006年第12期136卷 4419-4435页

作者： Liu, Wen An Zhang, Qi Min Nie, Zan Kan Henan Normal Univ Coll Math & Informat Sci Xinxiang 453007 Peoples R China Ningxia Univ Fac Math & Comp Sci Yinchuan 750021 Peoples R China Xi An Jiao Tong Univ Fac Sci Xian 710049 Peoples R China

The following coin-weighing problem is considered: suppose among the given n coins there are two counterfeit coins, which are either heavier or lighter than other n - 2 good coins, this is not known beforehand. The aim is to find an optimal algorithm which identifies these two counterfeit coins using as few weighings as possible. It is proved that the minimal number of weighings is either equal to the information-theoretic lower bound, or exceeds it by 1. Moreover, the information-theoretic lower bound are achievable for even number of weighings;for odd number of weighings, our optimal interval is very close to the theoretic optimal interval. The ideas and techniques of this paper can be used to solve other search models. (c) 2005 Elsevier B.V. All rights reserved.

关键词： search coin-weighing problem sequential algorithm information-theoretic bound

来源：评论

学校读者我要写书评

暂无评论

An adaptive mesh refinement algorithm for compressible two-phase flow in porous media

引用

COMPUTATIONAL GEOSCIENCES 2012年第3期16卷 577-592页

作者： Pau, George Shu Heng Bell, John B. Almgren, Ann S. Fagnan, Kirsten M. Lijewski, Michael J. Univ Calif Berkeley Lawrence Berkeley Natl Lab Div Earth Sci Berkeley CA 94720 USA Univ Calif Berkeley Lawrence Berkeley Natl Lab Ctr Computat Sci & Engn Berkeley CA 94720 USA Univ Calif Berkeley Lawrence Berkeley Natl Lab Natl Energy Res Sci Comp Ctr Berkeley CA 94720 USA

We describe a second-order accurate sequential algorithm for solving two-phase multicomponent flow in porous media. The algorithm incorporates an unsplit second-order Godunov scheme that provides accurate resolution of sharp fronts. The method is implemented within a block structured adaptive mesh refinement (AMR) framework that allows grids to dynamically adapt to features of the flow and enables efficient parallelization of the algorithm. We demonstrate the second-order convergence rate of the algorithm and the accuracy of the AMR solutions compared to uniform fine-grid solutions. The algorithm is then used to simulate the leakage of gas from a Liquified Petroleum Gas (LPG) storage cavern, demonstrating its capability to capture complex behavior of the resulting flow. We further examine differences resulting from using different relative permeability functions.

关键词： Adaptive mesh refinement Compressible two-phase flow Porous media sequential algorithm

来源：评论

学校读者我要写书评

暂无评论

OPTIMAL MODAL CONTROLLER-DESIGN BY ENTIRE EIGENSTRUCTURE ASSIGNMENT

引用

IEE PROCEEDINGS-D CONTROL THEORY AND APPLICATIONS 1989年第6期136卷 341-344页

作者： SAIF, M School of Engineering Science Simon Fraser University Burnaby Canada

A computationally simple sequential algorithm for designing an optimal modal controller is presented. The approach is capable of systematically calculating a set of appropriate weighting matrices for the cost functional in the quadratic performance index, so that the resulting optimal control law would not only minimise the cost functional, but also place the eigenspectrum of the closed-loop system at some predefined locations.

关键词： eigenstructure assignment optimal control performance index eigenspectrum cost functional Optimal control control system synthesis closed-loop system closed loop systems optimal modal controller sequential algorithm weighting matrices Control system analysis and synthesis methods quadratic performance index

来源：评论

学校读者我要写书评

暂无评论

TWO-DIMENSIONAL CONVOLUTION ON A PYRAMID COMPUTER

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 1988年第4期10卷 590-593页

作者： CHANG, JH IBARRA, OH PONG, TC SOHN, SM UNIV MINNESOTA DEPT COMP SCIMINNEAPOLISMN 55455

An algorithm for convolving a k*k window of weighting coefficients with an n*n image matrix on a pyramid computer of O(n/sup 2/) processors in time O(logn+k/sup 2/), excluding the time to load the image matrix, is presented. If k= Omega ( square root log n), which is typical in practice, the algorithm has a processor-time product O(n/sup 2/ k/sup 2/) which is optimal with respect to the usual sequential algorithm. A feature of the algorithm is that the mechanism for controlling the transmission and distribution of data in each processor is finite state, independent of the values of n and k. Thus, for convolving two (0, 1)-valued matrices using Boolean operations rather than the typical sum and product operations, the processors of the pyramid computer are finite-state.

关键词： PROCESSOR Computers transmission and distribution sequential algorithm image matrix Weighting coefficients algorithms data distribution Optimal Surgery

来源：评论

学校读者我要写书评

暂无评论

Size-invariant four-scan Euclidean distance transformation

引用

PATTERN RECOGNITION 1998年第11期31卷 1761-1766页

作者： Shih, FY Liu, JJ New Jersey Inst Technol Dept Comp & Informat Sci Comp Vis Lab Newark NJ 07102 USA

Distance transform (DT)((1)) is used to convert a binary image that consists of object (foreground) and nonobject (background) pixels into another image in which each object pixel has a value corresponding to the minimum distance from the background by a predefined distance function. The Euclidean distance is more accurate than the others, such as city-black, chessboard and chamfer, but it takes more computational time due to its nonlinearity. By using the relative X and Y coordinates computed from the object pixel to the source mapping pixel of its neighbors as well as correction of particular cases, the Euclidean distance transformation (EDT) can be correctly obtained in just four scans of an image. In other words, the new algorithm achieves the computational complexity of EDT to be linear to the size of an image. (C) 1998 Pattern Recognition Society. Published by Elsevier Science Ltd. All rights reserved.

关键词： distance transform Euclidean distance image processing recursive algorithm sequential algorithm skeletonization

来源：评论

学校读者我要写书评

暂无评论

Kernel reconstruction learning

引用

NEUROCOMPUTING 2023年第1期522卷 1-10页

作者： Wu, Yun Xiong, Shifeng Univ Chinese Acad Sci Sch Math Sci Beijing Peoples R China Chinese Acad Sci Acad Math & Syst Sci NCMIS KLSC Beijing Peoples R China

This paper proposes a class of kernel interpolation-based methods, called kernel reconstruction learning, for solving machine learning problems. Kernel reconstruction learning uses kernel interpolators to recon-struct the unknown functions, which are needed to estimate in the problem, with estimated function val-ues at selected knots. It can be applied to any learning problem that involves function estimation. We prove a reconstruction representer theorem, which indicates that conventional kernel methods, including kernel ridge regression, kernel support vector machine, and kernel logistic regression, can be viewed as special cases of kernel reconstruction learning. Furthermore, kernel reconstruction learning provides new algorithms for large datasets. The kernel reconstruction vector machine, kernel reconstruction logistic regression, and kernel reconstruction density estimation are discussed in detail. With appropriate imple-mentations, they are shown to have higher prediction/estimation accuracy and/or less computational cost than popular kernel methods.(c) 2022 Elsevier B.V. All rights reserved.

关键词： Kernel method Representer theorem Interpolation Classification Density estimation sequential algorithm

来源：评论

学校读者我要写书评

暂无评论

Variants of Partial Update Augmented CLMS algorithm and Their Performance Analysis

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2020年 68卷 3146-3157页

作者： Vahidpour, Vahid Rastegarnia, Amir Khalili, Azam Bazzi, Wael M. Sanei, Saeid Malayer Univ Dept Elect Engn Malayer *** Iran Amer Univ Dubai Dept Elect & Comp Engn Dubai 28282 U Arab Emirates Nottingham Trent Univ Sch Sci & Technol Nottingham NG11 8NS England

Naturally complex-valued information or those presented in complex domain are effectively processed by an augmented complex least-mean-square (ACLMS) algorithm. In some applications, the ACLMS algorithm may be too computationally- and memory-intensive to implement. In this paper, a new algorithm, termed partial-update ACLMS (PU-ACLMS) algorithm is proposed, where only a fraction of the coefficient set is selected to update at each iteration. Doing so, two types of partial-update schemes are presented referred to as the sequential and stochastic partial-updates, to reduce computational load and power consumption in the corresponding adaptive filter. The computational cost for full-update PU-ACLMS and its partial-update implementations are discussed. Next, the steady-state mean and mean-square performance of PU-ACLMS for non-circular complex signals are analyzed and closed-form expressions of the steady-state excess mean-square error (EMSE) and mean-square deviation (MSD) are given. Then, employing the weighted energy-conservation relation, the EMSE and MSD learning curves are derived. The simulation results are verified and compared with those of theoretical predictions through numerical examples.

关键词： Signal processing algorithms Computational complexity Approximation algorithms Performance analysis Power demand Computational efficiency Steady-state Augmented CLMS energy-conservation non-circular partial-update sequential algorithm stochastic-algorithm widely linear model

来源：评论

学校读者我要写书评

暂无评论

Minimum average-case queries of q+1-ary search game with small sets

引用

DISCRETE APPLIED MATHEMATICS 2012年第4-5期160卷 618-627页

作者： Meng, Kun Lin, Chuang Liu, Wen An Yang, Yang Katona, Gyula O. H. Univ Sci & Technol Beijing Sch Comp & Commun Engn Beijing 100083 Peoples R China Tsinghua Univ Dept Comp Sci & Technol Beijing 100084 Peoples R China Henan Normal Univ Coll Math & Informat Sci Xinxiang Peoples R China Renyi Inst Budapest Budapest Hungary

Given a search space S = {1,2,..., n}, an unknown element x* is an element of S and fixed integers l >= 1 and q >= 1, a q + 1-ary l-restricted query is of the following form: which one of the set {A(0), A(1),..., A(q)} is the x* in?, where (A(0), A(1), ..., A(q)) is a partition of S and vertical bar A(i)vertical bar <= e for i = 1, 2,...,q. The problem of finding x. from S with q + 1-ary size-restricted queries is called as a q + 1-ary search game with small sets. In this paper, we consider sequential algorithms for the above problem, and establish the minimum number of average-case sequential queries when x*. satisfies the uniform distribution on S. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Search game sequential algorithm Average-cost Huffman tree

来源：评论

学校读者我要写书评

暂无评论

Partial update LMS algorithms

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2005年第7期53卷 2382-2399页

作者： Godavarti, M Hero, AO Ditech Commun Inc Mountain View CA 94043 USA Univ Michigan Dept Elect Engn & Comp Sci Ann Arbor MI 48109 USA

Partial updating of LMS filter coefficients is an effective method for reducing computational load and power consumption in adaptive filter implementations. This paper presents an analysis of convergence of the class of sequential Partial Update LMS algorithms (S-LMS) under various assumptions and shows that divergence can be prevented by scheduling coefficient updates at random, which we call the Stochastic Partial Update LMS algorithm (SPU-LMS). Specifically, under the standard independence assumptions, for wide sense stationary signals, the S-LMS algorithm converges in the mean if the step-size parameter mu is in the convergent range of ordinary LMS. Relaxing the independence assumption, it is shown that S-LMS and LMS algorithms have the same sufficient conditions for exponential stability. However, there exist nonstationary signals for which the existing algorithms, S-LMS included, are unstable and do not converge for any value of mu. On the other hand, under broad conditions, the SPU-LMS algorithm remains stable for nonstationary signals. Expressions for convergence rate and steady-state mean-square error of SPU-LMS are derived. The theoretical results of this paper are validated and compared by simulation through numerical examples.

关键词： exponential stability max partial update partial update LMS algorithms periodic algorithm random updates sequential algorithm set-membership

来源：评论

学校读者我要写书评

暂无评论

FINDING THE CLOSED PARTITION OF A PLANAR GRAPH

引用

algorithmICA 1994年第5期11卷 443-468页

作者： RAMACHANDRAN, V YANG, H 1. Department of Computer Sciences The University of Texas at Austin 78712 Austin TX USA

In this paper we consider the problem of finding a closed partition in a directed graph. This problem has applications in concurrent probabilistic program verification. The best sequential algorithm known for this problem runs in O(mn) time where m is the number of directed edges and n is the number of vertices in the given digraph. In this paper we present a linear-time sequential algorithm to solve the closed partition problem for planar digraphs that are compact. We then build on this algorithm to obtain an O(n1.5)-time sequential algorithm to solve the closed partition problem for a general planar digraph.

关键词： CLOSED PARTITION COMPACT DIIGRAPH DIRECTED GRAPH DUAL GRAPH PLANAR GRAPH sequential algorithm STRONGLY CONNECTED COMPONENT

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：