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

IEEE TRANSACTIONS ON COMPUTERS 1985年第4期34卷 296-310页

作者： DEMUTH, HB Department of Electrical Engineering University of Tulsa Tulsa OK 7410 Abstract Authors References Cited By Keywords Metrics Similar Download Citation Email Print Request Permissions

This paper presents results of a study of the fundamentals of sorting. Emphasis is placed on understanding sorting and on minimizing the time required to sort with electronic equipment of reasonable cost. Sorting is viewed as a combination of information gathering and item moving activities. Shannon"s communication theory measure of information is applied to assess the difficulty of various sorting problems. Bounds on the number of comparisons required to sort are developed, and optimal or near-optimal sorting schemes are described and investigated. Three abstract sorting models based on cyclic, linear, and randomaccess memories are defined. Optimal or near-optimal sorting methods are developed for the models and their parallel-register extensions. A brief review of the origin of the work and some of its hypotheses is also presented.

关键词： Bounds communication theory comparisons complexity computational complexity information gathering information theory item moving model optimal parallel sorting

来源：评论

学校读者我要写书评

暂无评论

POLYNOMIAL-TIME COMPUTATION OF HOMOTOPY GROUPS AND POSTNIKOV SYSTEMS IN FIXED DIMENSION

引用

SIAM JOURNAL ON COMPUTING 2014年第5期43卷 1728-1780页

作者： Cadek, Martin Krcal, Marek Matousek, Jiri Vokrinek, Lukas Wagner, Uli Masaryk Univ Dept Math & Stat CS-61137 Brno Czech Republic Charles Univ Prague Dept Appl Math CR-11800 Prague 1 Czech Republic ETH Dept Comp Sci CH-8092 Zurich Switzerland EPFL SB MATHGEOM Ecole Polytech Fed Lausanne Inst Math Geometrie & Applicat CH-1015 Lausanne Switzerland

For several computational problems in homotopy theory, we obtain algorithms with running time polynomial in the input size. In particular, for every fixed k >= 2, there is a polynomial-time algorithm that, for a 1-connected topological space X given as a finite simplicial complex, or more generally, as a simplicial set with polynomial-time homology, computes the kth homotopy group pi(k)(X), as well as the first k stages of a Postnikov system of X. Combined with results of an earlier paper, this yields a polynomial-time computation of [X, Y], i.e., all homotopy classes of continuous mappings X -> Y, under the assumption that Y is (k - 1)-connected and dim X <= 2k - 2. We also obtain a polynomial-time solution of the extension problem, where the input consists of finite simplicial complexes X -> Y, where Y is (k - 1)-connected and dim X <= 2k - 1, plus a subspace A subset of X and a (simplicial) map f : A -> Y, and the question is the extendability of f to all of X. The algorithms are based on the notion of a simplicial set with polynomial-time homology, which is an enhancement of the notion of a simplicial set with effective homology developed earlier by Sergeraert and his coworkers. Our polynomial-time algorithms are obtained by showing that simplicial sets with polynomial-time homology are closed under various operations, most notably Cartesian products, twisted Cartesian products, and classifying space. One of the key components is also polynomial-time homology for the Eilenberg-MacLane space K(Z, 1), provided in another recent paper by Krcal, Matousek, and Sergeraert.

关键词： algebraic topology homotopy theory homotopy groups Postnikov systems computational complexity

来源：评论

学校读者我要写书评

暂无评论

ON CALCULATING THE CAPACITY OF AN INFINITE-INPUT FINITE (INFINITE) OUTPUT CHANNEL

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 1988年第5期34卷 1004-1010页

作者： CHANG, CI DAVISSON, LD UNIV MARYLAND DEPT ELECT ENGNCOLLEGE PKMD 20742

A version of the Arimoto-Blahut algorithm for continuous channels involves evaluating integrals over an entire input space and thus is not tractable. Two generalized discrete versions of the Arimoto-Blahut algorithm are presented for this purpose. Instead of calculating integrals, both algorithms require only the computation of a sequence of finite sums. This significantly reduces numerical computational complexity

关键词： Iterative algorithms Channel capacity Convergence Minimax techniques Integral equations computational complexity Information theory Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Distributed Convex Optimization Compressed Sensing Method for Sparse Planar Array Synthesis in 3-D Imaging Sonar Systems

引用

IEEE JOURNAL OF OCEANIC ENGINEERING 2020年第3期45卷 1022-1033页

作者： Gu, Boxuan Chen, Yaowu Liu, Xuesong Zhou, Fan Jiang, Rongxin Zhejiang Univ Inst Adv Digital Technol & Instrumentat Hangzhou 310027 Peoples R China Zhejiang Univ Zhejiang Prov Key Lab Network Multimedia Technol Hangzhou 310027 Peoples R China Zhejiang Univ State Key Lab Ind Control Technol Hangzhou 310027 Peoples R China

Synthesis of sparse planar arrays can effectively reduce hardware costs and computational complexity in phased array 3-D imaging sonar systems. Traditional stochastic methods, such as simulated annealing, require multiple experiments and parameter adjustments to obtain optimal results. Methods based on compressed sensing (CS) can overcome this defect. However, when applied to large arrays, CS methods require vast computational complexity and may not obtain optimal sparse results because of violating the restricted isometry property. To make CS methods more practical, a distributed convex optimization CS method is proposed here for the sparse planar array synthesis in 3-D imaging sonar systems. This method is based on the CS theory, solving the minimum number of active elements under certain beam pattern constraints using the iterative reweighted l(1)-norm minimization algorithm. Then, a multistage distributed framework is proposed to decompose the array into multistage subarrays, and the array synthesis is performed sequentially for each stage subarray to reduce computational complexity and obtain higher sparsity rates. Some applications of sparse planar array synthesis are employed to evaluate the efficiency of the proposed method.

关键词： Planar arrays Convex functions Apertures computational complexity Iterative algorithms Minimization Transmission line matrix methods Compressed sensing (CS) convex optimization multistage distributed framework phased array 3-D imaging sonar system sparse planar array

来源：评论

学校读者我要写书评

暂无评论

Fast and efficient contrast-enhanced super-resolution without real-world data using concatenated recursive compressor-decompressor network

引用

IET IMAGE PROCESSING 2019年第5期13卷 817-824页

作者： Choi, Jun-Myung Kang, Dong-Joong Pusan Natl Univ Sch Mech Engn Busan 46241 South Korea

The authors propose a novel model called concatenated recursive compressor-decompressor network (CRCDNet) for contrast-enhanced super-resolution. The characteristics of authors' model can be summarised as follows. First, a compression-decompression process reduces the computational complexity compared with the general fully convolutional model. Second, an internal/external skip-connection is used to preserve information of the preceding layers. Finally, by employing a recursive module, authors' model has a small number of parameters, yet is a deep and robust network. The authors apply authors' proposed network to license plate images. As a real application, license plates can provide important evidence for investigation of crimes and for security, but it is very difficult to collect the vast amounts of license plates required for analysis based on a data-driven approach. To solve this problem, the authors generated virtual datasets to train authors' model, while analysing the performance with real license plate datasets. Authors' method achieves better performance than the state-of-the-art models on license plate images.

关键词： learning (artificial intelligence) image sensors traffic engineering computing parallel algorithms image resolution object recognition data compression image enhancement computational complexity license plate datasets state-of-the-art models license plate images fast contrast-enhanced super-resolution efficient contrast-enhanced super-resolution real-world data concatenated recursive compressor-decompressor network compression-decompression process general fully convolutional model recursive module deep network robust network license plates internal-external skip-connection CRCDNet

来源：评论

学校读者我要写书评

暂无评论

Fair allocation of utilities in multirate multicast networks: A framework for unifying diverse fairness objectives

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2002年第6期47卷 931-944页

作者： Sarkar, S Tassiulas, L Univ Penn Dept Elect Engn Philadelphia PA 19104 USA Univ Maryland Dept Elect & Comp Engn College Pk MD 20742 USA Univ Maryland Syst Res Inst College Pk MD 20742 USA

We study fairness in a multicast network. We assume that different receivers of the same session can receive information at different rates. We study fair allocation of utilities, where utility of a bandwidth is an arbitrary function of the bandwidth. The utility function is not strictly increasing, nor continuous in general. We discuss fairness issues in this general context. Fair allocation of utilities can be modeled as a nonlinear optimization problem. However, nonlinear optimization techniques do not terminate in a finite number of iterations in general. We present an algorithm for computing a fair utility allocation. Using specific fairness properties, we show that this algorithm attains global convergence and yields a fair allocation in polynomial number of iterations.

关键词： computational complexity decision theory iterative methods multicast communication optimisation resource allocation telecommunication congestion control congestion control fair utility allocation global convergence multicast communicati global convergence multicast communication telecommunication congestion control Resource utilization Decision Theory Public utilities complexity classes iterative methods

来源：评论

学校读者我要写书评

暂无评论

Robust fast PMU measurement recovery enhanced by randomized singular value and sequential Tucker decomposition

引用

IET GENERATION TRANSMISSION & DISTRIBUTION 2022年第16期16卷 3267-3281页

作者： Pei, Jianhua Wang, Ziyu Wang, Jingyu Shi, Dongyuan Huazhong Univ Sci & Technol Sch Elect & Elect Engn Minist Educ Engn Res Ctr Power Safety & EfficiencyState Key Wuhan 430074 Peoples R China

The development of cyber-physical power systems raises concerns about the data quality issue of phasor measurement units (PMUs). Low signal-to-noise ratios (SNRs) and data losses caused by malicious electromagnetic interference, false data injections, and equipment malfunctioning may jeopardize the data integrity and availability necessary for power system monitoring, protection, and control. To ensure grid resiliency, this paper proposes a robust fast PMU measurement recovery (RFMR) algorithm based on improved singular spectrum analysis (SSA) of Hankel structures. It utilizes single or multiple channels of PMU time-series to restore the problematic phasor measurements with low-SNR noises and data losses. Additionally, the traditional singular value decomposition (SVD) and Tucker decomposition (TD) in RFMR are replaced by randomized SVD (RSVD) and sequential TD (STD) to reduce the computational complexity in single-channel and multi-channel RFMR, respectively. Numerical case studies demonstrate that the proposed algorithm can recover the noise-contaminated measurements with higher accuracy than existing methods, such as matrix/tensor decomposition approaches and robust principal component analysis (RPCA), and effectively complement the missing data with the observed measurements corrupted by low SNRs. Moreover, the latency margins of various power system synchrophasor application scenarios can be satisfied with the reduced computational complexity.

关键词： data quality issue missing data computational complexity observed measurements decomposition approaches randomized singular value cyber-physical systems data losses power system monitoring noise-contaminated measurements power system synchrophasor application scenarios PMU time-series grid resiliency improved singular spectrum analysis singular value decomposition principal component analysis equipment malfunctioning robust fast PMU measurement recovery algorithm problematic phasor measurements multichannel RFMR electromagnetic interference cyber-physical power systems phasor measurement tensors robust principal component analysis time series data integrity power system measurement false data injections low SNRs phasor measurement units power engineering computing malicious electromagnetic interference

来源：评论

学校读者我要写书评

暂无评论

INTERACTIVE PROOF SYSTEMS AND ALTERNATING TIME-SPACE complexity

引用

THEORETICAL COMPUTER SCIENCE 1993年第1期113卷 55-73页

作者： FORTNOW, L LUND, C Department of Computer Science University of Chicago 1100 E. 58th Street Chicago IL 60637 USA

We show a rough equivalence between alternating time-space complexity and a public-coin interactive proof system with the verifier having a polynomial-related time-space complexity. Special cases include the following: All of NC has interactive proofs, with a log-space polynomial-time public-coin verifier vastly improving the best previous lower bound of LOGCFL for this model (Fortnow and Sipser, 1988). All languages in P have interactive proofs with a polynomial-time public-coin verifier using o(log2 n) space. All exponential-time languages have interactive proof systems with public-coin polynomial-space exponential-time verifiers. To achieve better bounds, we show how to reduce a k-tape alternating Turing machine to a 1-tape alternating Turing machine with only a constant factor increase in time and space.

关键词： computational complexity

来源：评论

学校读者我要写书评

暂无评论

ML Performance Achieving Algorithm With the Zero-Forcing complexity at High SNR Regime

引用

IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS 2016年第7期15卷 4651-4659页

作者： Neinavaie, Mohammad Derakhtian, Mostafa Shiraz Univ Dept Elect & Comp Engn Shiraz *** Iran

Although zero-forcing ( ZF) detection is well-known for its low computational complexity in multiple-input multiple-output ( MIMO) communication systems, it suffers from significantly poor performance. The sphere decoder ( SD) method, on the other hand, achieves the maximum likelihood ( ML) performance yet imposes a high computational complexity. We propose a low-complexity detection scheme, concatenated with the SD method, which verifies the reliability of the ZF equalized observations via some predefined regions and thresholds obtained by the channel realization. We design the threshold analytically, such that the method achieves the ML performance. With the designed threshold, we prove that the method achieves the ML performance and the ZF computational complexity at the same time with probability one, at high signal-to-noise ratio ( SNR). The theoretical analysis is corroborated with numerical simulations. The simulation results also show that the proposed method achieves the ML performance very rapidly as the SNR increases.

关键词： MIMO detection Sphere decoding Reduced sphere decoding Diversity computational complexity

来源：评论

学校读者我要写书评

暂无评论

Refined memorization for vertex cover

引用

INFORMATION PROCESSING LETTERS 2005年第3期93卷 125-131页

作者： Chandran, LS Grandoni, F Univ Roma Tor Vergata Dipartimento Informat Sistemi & Produz I-00133 Rome Italy Max Planck Inst Informat D-66123 Saarbrucken Germany

Memorization is a technique which allows to speed up exponential recursive algorithms at the cost of an exponential space complexity. This technique already leads to the currently fastest algorithm for fixed-parameter vertex cover, whose time complexity is O(1.2832(k)k(1.5) + kn), where it is the number of nodes and k is the size of the vertex cover. Via a refined use of memorization, we obtain an C(1.2759(k)k(1.5) + kn) algorithm for the same problem. We moreover Show how to further reduce the complexity to O(1.2745(k)k(4) + kn). 2004 Elsevier B.V. All rights reserved.

关键词： memorization vertex cover computational complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：