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

Local Restrictions from the Furst-Saxe-Sipser Paper

THEORY OF COMPUTING SYSTEMS 2017年第1期60卷 20-32页

作者： Tamaki, Suguru Watanabe, Osamu Kyoto Univ Sakyo Ku Kyoto 6068501 Japan Tokyo Inst Technol Tokyo 1528552 Japan

In their celebrated paper (Furst et al., Math. Syst. Theory 17(1), 13-27 (12)), Furst, Saxe, and Sipser used random restrictions to reveal the weakness of Boolean circuits of bounded depth, establishing that constant-depth and polynomial-size circuits cannot compute the parity function. Such local restrictions have played important roles and have found many applications in complexity analysis and algorithm design over the past three decades. In this article, we give a brief overview of two intriguing applications of local restrictions: the first one is for the Isomorphism Conjecture and the second one is for moderately exponential time algorithms for the Boolean formula satisfiability problem.

关键词： Local restriction Random restriction Computational complexity theory algorithm design

来源：评论

学校读者我要写书评

暂无评论

Free Angular-Positioning Wireless Power Transfer Using a Spherical Joint

引用

ENERGIES 2018年第12期11卷 3488-3488页

作者： Abou Houran, Mohamad Yang, Xu Chen, Wenjie Xi An Jiao Tong Univ Sch Elect Engn Xian 710049 Shaanxi Peoples R China

Many studies have investigated resonator structures and winding methods. The aims of this paper are as follows. First, the paper proposes an optimized winding model for a bio-inspired joint for a wireless power transfer (WPT) system. The joint consists of a small spherical structure, which rotates inside a hemispherical structure. The transmitter coil (Tx) is wound on the hemisphere structure, and the receiver coil (Rx) is wound on the small sphere. The power is transferred while rotating Rx over a wide range of angular misalignment. In addition, the algorithm design of the proposed winding method is given to get an optimized model. Moreover, the circuit analysis of the WPT system is discussed. Second, the magnetic field density is investigated considering a safety issue, which is linked to human exposure to electromagnetic fields (EMFs). Moreover, EMF mitigation methods are proposed and discussed in detail. Finally, the simulation results are validated by experiments, which have confirmed that the proposed winding method allows the system to rotate up to 85 degrees and achieve an efficiency above 86%. The proposed winding method for the WPT system can be a good technique for some robotic applications or a future replacement of the human joint.

关键词： algorithm design electromagnetic fields (EMFs) EMF shielding spherical structure wireless power transfer

来源：评论

学校读者我要写书评

暂无评论

Scalable Verification of Networks With Packet Transformers Using Atomic Predicates

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2017年第5期25卷 2900-2915页

作者： Yang, Hongkun Lam, Simon S. Google Mountain View CA 94043 USA Univ Texas Austin Dept Comp Sci Austin TX 78712 USA

Packet transformers are widely used in ISPs, datacenter infrastructures, and layer-2 networks. Existing network verification tools do not scale to large networks with transformers (e.g., MPLS, IP-in-IP, and NAT). Toward scalable verification, we conceived a novel packet equivalence relation. For networks with packet transformers, we first present a formal definition of the packet equivalence relation. Our transformer model is general, including most transformers used in real networks. We also present a new definition of atomic predicates that specify the coarsest equivalence classes of packets in the packet space. We designed an algorithm for computing these atomic predicates. We built a verifier, named Atomic Predicates for Transformers, and evaluated its performance using four network data sets with MPLS tunnels, IP-in-IP tunnels, and NATs. For a provider cone data set with 11.6 million forwarding rules, 92 routers, 1920 duplex ports, and 40 MPLS tunnels which use 170 transformers, APT used only 0.065 s, on average, to compute the reachability tree from a source port to all other ports for all packets and perform loop detection as well. For the Stanford and Internet2 data sets with NATs, APT is faster than HSA (Hassel in C implementation) by two to three orders of magnitude. By working with atomic predicates instead of individual packets, APT achieves verification performance gains by orders of magnitude.

关键词： Network verification reachability analysis packet transformers formal methods algorithm design

来源：评论

学校读者我要写书评

暂无评论

Parametric Covariance Model for Horizon-Based Optical Navigation

引用

JOURNAL OF GUIDANCE CONTROL AND DYNAMICS 2017年第1期40卷 170-U233页

作者： Hikes, Jacob Liounis, Andrew J. Christian, John A. West Virginia Univ Benjamin M Statler Coll Engn & Mineral Resources Dept Mech & Aerosp Resources Morgantown WV 26506 USA NASA Goddard Space Flight Ctr Greenbelt MD 20771 USA

An entirely parametric version of the covariance for horizon-based optical navigation measurements is studied. The covariance can be written as a function of only the spacecraft position, two sensor design parameters, the illumination direction, the size of the observed planet, the size of the lit arc to be used, and the total number of observed horizon points. As a result, one may now more clearly understand the sensitivity of horizon-based optical navigation performance as a function of these key design parameters, which is insight that was obscured in previous (and nonparametric) versions of the covariance. Finally, the new parametric covariance is shown to agree with both the nonparametric analytic covariance and results from a Monte Carlo analysis.

关键词： Planets Cholesky Factorization Monte Carlo Simulation Navigation Performance algorithm design Flight Vehicle Star Tracker Asteroids

来源：评论

学校读者我要写书评

暂无评论

Generation of Particle Swarm Optimization algorithms: An experimental study using Grammar-Guided Genetic Programming

引用

APPLIED SOFT COMPUTING 2017年 60卷 281-296页

作者： Miranda, Pericles B. C. Prudencio, Ricardo B. C. Rural Fed Univ Pernambuco Dept Stat & Informat Recife PE Brazil Rural Fed Univ Pernambuco Ctr Informat Recife PE Brazil

Particle Swarm Optimization (PSO) is largely used to solve optimization problems effectively. Nonetheless, the PSO performance depends on the fine tuning of different parameters. To make the algorithm design process more independent from human intervention, some researchers have treated this task as an optimization problem. Grammar-Guided Genetic Programming (GGGP) algorithms, in particular, have been widely studied and applied in the context of algorithm optimization. GGGP algorithms produce customized designs based on a set of production rules defined in the grammar, differently from methods that simply select designs in a pre-defined limited search space. Although GGGP algorithms have been largely used in other contexts, they have not been deeply investigated in the generation of PSO algorithms. Thus, this work applies GGGP algorithms in the context of PSO algorithm design problem. Herein, we performed an experimental study comparing different GGGP approaches for the generation of PSO algorithms. The main goal is to perform a deep investigation aiming to identify pros and cons of each approach in the current task. In the experiments, a comparison between a tree-based GGGP approach and commonly used linear GGGP approaches for the generation of PSO algorithms was performed. The results showed that the tree-based GGGP produced better algorithms than the counterparts. We also compared the algorithms generated by the tree-based technique to state-of-the-art optimization algorithms, and it achieved competitive results. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Generation hyper-heuristics Grammar-Guided Genetic Programming algorithm design Particle Swarm Optimization

来源：评论

学校读者我要写书评

暂无评论

Model-based diagnosis through Structural Analysis and Causal Computation for automotive Polymer Electrolyte Membrane Fuel Cell systems

引用

JOURNAL OF POWER SOURCES 2017年 357卷 26-40页

作者： Polverino, Pierpaolo Frisk, Erik Jung, Daniel Krysander, Mattias Pianese, Cesare Univ Salerno Dept Ind Engn Via Giovanni Paolo 2 132 I-84084 Fisciano SA Italy Linkoping Univ Dept Elect Engn S-5183 Linkoping Sweden

The present paper proposes an advanced approach for Polymer Electrolyte Membrane Fuel Cell (PEMFC) systems fault detection and isolation through a model-based diagnostic algorithm. The considered algorithm is developed upon a lumped parameter model simulating a whole PEMFC system oriented towards automotive applications. This model is inspired by other models available in the literature, with further attention to stack thermal dynamics and water management. The developed model is analysed by means of Structural Analysis, to identify the correlations among involved physical variables, defined equations and a set of faults which may occur in the system (related to both auxiliary components malfunctions and stack degradation phenomena). Residual generators are designed by means of Causal Computation analysis and the maximum theoretical fault isolability, achievable with a minimal number of installed sensors, is investigated. The achieved results proved the capability of the algorithm to theoretically detect and isolate almost all faults with the only use of stack voltage and temperature sensors, with significant advantages from an industrial point of view. The effective fault isolability is proved through fault simulations at a specific fault magnitude with an advanced residual evaluation technique, to consider quantitative residual deviations from normal conditions and achieve univocal fault isolation. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Polymer Electrolyte Membrane Fuel Cell Model-based diagnosis Fault detection Fault isolation Residual generation algorithm design

来源：评论

学校读者我要写书评

暂无评论

Improve Service Chaining Performance with Optimized Middlebox Placement

引用

IEEE TRANSACTIONS ON SERVICES COMPUTING 2017年第4期10卷 560-573页

作者： Liu, Jiaqiang Li, Yong Zhang, Ying Su, Li Jin, Depeng Tsinghua Univ Dept Elect Engn Beijing 10084 Peoples R China HP Labs Networking & Mobil Lab Palo Alto CA USA

Previous works have proposed various approaches to implement service chaining by routing traffic through the desired middleboxes according to pre-defined policies. However, no matter what routing scheme is used, the performance of service chaining depends on where these middleboxes are placed. Thus, in this paper, we study middlebox placement problem, i.e., given network information and policy specifications, we attempt to determine the optimal locations to place the middleboxes so that the performance is optimized. The performance metrics studied in this paper include the end-to-end delay and the bandwidth consumption, which cover both users' and network providers' interests. We first formulate it as 0-1 programming problem, and prove it is NP-hard. We then propose two heuristic algorithms to obtain the sub-optimal solutions. The first algorithm is a greedy algorithm, and the second algorithm is based on simulated annealing. Through extensive simulations, we show that in comparison with a baseline algorithm, the proposed algorithms can reduce 22 percent end-to-end delay and save 38 percent bandwidth consumption on average. The formulation and proposed algorithms have no special assumption on network topology or policy specifications, therefore, they have broad range of applications in various types of networks such as enterprise, data center and broadband access networks.

关键词： Service chaining middlebox placement performance optimization algorithm design

来源：评论

学校读者我要写书评

暂无评论

algorithmic Iteration for Computational Intelligence

引用

MINDS AND MACHINES 2017年第3期27卷 521-543页

作者： Primiero, Giuseppe Middlesex Univ Dept Comp Sci London NW4 4BT England

Machine awareness is a disputed research topic, in some circles considered a crucial step in realising Artificial General Intelligence. Understanding what that is, under which conditions such feature could arise and how it can be controlled is still a matter of speculation. A more concrete object of theoretical analysis is algorithmic iteration for computational intelligence, intended as the theoretical and practical ability of algorithms to design other algorithms for actions aimed at solving well-specified tasks. We know this ability is already shown by current AIs, and understanding its limits is an essential step in qualifying claims about machine awareness and Super-AI. We propose a formal translation of algorithmic iteration in a fragment of modal logic, formulate principles of transparency and faithfulness across human and machine intelligence, and consider the relevance to theoretical research on (Super)-AI as well as the practical import of our results.

关键词： Artificial intelligence Introspection Machine awareness algorithm design algorithm execution

来源：评论

学校读者我要写书评

暂无评论

Optimal Rate Schedules with Data Sharing in Energy Harvesting Communication Systems

引用

SENSORS 2017年第12期17卷 2958-2958页

作者： Wu, Weiwei Li, Huafan Shan, Feng Zhao, Yingchao Southeast Univ Sch Comp Sci & Engn Nanjing 210018 Jiangsu Peoples R China Caritas Inst Higher Educ Sch Comp & Informat Sci Hong Kong 999077 Hong Kong Peoples R China

Despite the abundant research on energy-efficient rate scheduling polices in energy harvesting communication systems, few works have exploited data sharing among multiple applications to further enhance the energy utilization efficiency, considering that the harvested energy from environments is limited and unstable. In this paper, to overcome the energy shortage of wireless devices at transmitting data to a platform running multiple applications/requesters, we design rate scheduling policies to respond to data requests as soon as possible by encouraging data sharing among data requests and reducing the redundancy. We formulate the problem as a transmission completion time minimization problem under constraints of dynamical data requests and energy arrivals. We develop offline and online algorithms to solve this problem. For the offline setting, we discover the relationship between two problems: the completion time minimization problem and the energy consumption minimization problem with a given completion time. We first derive the optimal algorithm for the min-energy problem and then adopt it as a building block to compute the optimal solution for the min-completion-time problem. For the online setting without future information, we develop an event-driven online algorithm to complete the transmission as soon as possible. Simulation results validate the efficiency of the proposed algorithm.

关键词： wireless data transmission rate schedule data sharing energy-efficiency energy harvesting algorithm design

来源：评论

学校读者我要写书评

暂无评论

Improved exact algorithms to economic lot-sizing with piecewise linear production costs

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2017年第3期256卷 777-784页

作者： Ou, Jinwen Jinan Univ Sch Business Dept Adm Management Guangzhou 510632 Guangdong Peoples R China

In this article we study a classical single-item economic lot-sizing problem, where production cost functions are assumed to be piecewise linear. The lot-sizing problem is fundamental in lot-sizing research, and it is applicable to a wide range of production planning models. The intractability of the problem is related to the value of m, the number of different breakpoints of the production cost functions. When m is arbitrary, the problem is known to be NP-hard (Florian, Lenstra & Rinnooy Kan, 1980). However, if m is fixed, then it can be solved in polynomial time (Koca, Yaman & Alcturk, 2014). So far, the most efficient algorithm to solve the problem has a complexity of O(T2m+3), where T is the number of periods in the planning horizon (Koca et al., 2014). In this article we present an improved exact algorithm for solving the problem, where the complexity is reduced to O(Tm+2 center dot log T). As such it also improves upon the computational efficiency of solving some existing lot-sizing problems which are important special cases of our model. In order to achieve a more efficient implementation, our algorithm makes use of a specific data structure, named range minimum query (RMQ). (C) 2016 Elsevier B.V. All rights reserved.

关键词： Dynamic programming Economic lot-sizing algorithm design Range minimum query

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：