基于区分对象对集的快速求核算法

为降低基于正区域求核算法的时间复杂度,首先给出了简化决策表和简化差别矩阵及其核的定义。然后给出了简化决策表中条件属性的区分对象对集的定义,并得出区分对象对集与决策表核属性的关系,证明了求决策表的核可以转化到求条件属性的区分对象对集上。再结合简化差别矩阵的核的性质,设计了一个基于区分对象对集的快速求核算法。该算法的时间复杂度优于同类算法的时间复杂度。最后用实例说明了新算法的有效性。     

一种基于吉布斯抽样的MUSIC频率-方位联合估计算法

将马尔可夫蒙特卡罗方法与MUSIC方法估计相结合,提出一种基于吉布斯抽样的频率-方位联合估计新方法(MUSIC FREQ-DOA joint Estimator Based on Gibbs Sampling,简称Gibbs-MUSIC).并用该方法联合估计多个目标的频率和方位.这种方法将MUSIC方法的谱函数作为频率和方位的联合概率密度函数,并采用马尔可夫蒙特卡罗(MCMC)吉布斯抽样方法对该联合概率密度函数进行采样.仿真实验显示在目标个数较少时,该方法不仅保持了常规MUSIC方法的高分辨能力,而且降低了计算量,减少了存储量.     

一类基于级联构造的二元周期序列的复杂度

线性复杂度是衡量流密码中密钥流序列的安全性的重要指标.利用F2上周期序列及其对偶序列构成一类倒序新序列,给出了其极小多项式及线性复杂度.并由此结论讨论了F2上由这类倒序新序列构成的多维序列的联合极小多项式及联合线性复杂度.     

轻量化的增量式集成学习算法设计

常规的分类与回归树算法(classification and regression tree, CART)只能通过重新训练来增加对新类别的认知, 导致样本类别数量较多时训练成本大幅增加。针对这一问题, 提出一种轻量化的增量式集成学习算法: 当新的类别进入到训练集中, 只需在原有集成学习算法中添加具有开集识别能力的CART基分类器, 就可以实现对新类别样本的分类, 而不需要重新训练, 从而降低计算复杂度, 简化学习过程。以辐射源分类为背景的仿真实验表明, 该算法在信噪比大于等于-4 dB的环境中, 可以保持90%以上的分类准确率; 在类别数量较多的情况下, 相比常规CART, 该算法可以大幅度降低新增分类类别所需的训练成本。     

Social Choice Meets Graph Drawing： How to Get Subexponential Time Algorithms for Ranking and Drawing Problems

We analyze a common feature of p-Kemeny AGGregation(p-KAGG) and p-One-Sided Crossing Minimization(p-OSCM) to provide new insights and findings of interest to both the graph drawing community and the social choice community. We obtain parameterized subexponential-time algorithms for p-KAGG—a problem in social choice theory—and for p-OSCM—a problem in graph drawing. These algorithms run in time O.2O.pk logk//,where k is the parameter, and significantly improve the previous best algorithms with running times O.1.403k/and O.1.4656k/, respectively. We also study natural "above-guarantee" versions of these problems and show them to be fixed parameter tractable. In fact, we show that the above-guarantee versions of these problems are equivalent to a weighted variant of p-directed feedback arc set. Our results for the above-guarantee version of p-KAGG reveal an interesting contrast. We show that when the number of "votes" in the input to p-KAGG is odd the above guarantee version can still be solved in time O.2O.pk logk//, while if it is even then the problem cannot have a subexponential time algorithm unless the exponential time hypothesis fails(equivalently, unless FPT D M[1]).     

Philosophy,history and sociology of science: Interdisciplinary relations and complex social identities

Sociology and philosophy of science have an uneasy relationship, while the marriage of history and philosophy of science has—on the surface at least—been more successful. I will take a sociological look at the history of the relationships between philosophy and history as well as philosophy and sociology of science. Interdisciplinary relations between these disciplines will be analysed through social identity complexity theory in order to draw out some conclusions on how the disciplines interact and how they might develop. I will use the relationships between the disciplines as a pointer for a more general social theory of interdisciplinarity which will then be used to sound a caution on how interdisciplinary relations between the three disciplines might be managed.     

Parameterized Algorithmics for Computational Social Choice：Nine Research Challenges

Computational Social Choice is an interdisciplinary research area involving Economics, Political Science,and Social Science on the one side, and Mathematics and Computer Science（including Artificial Intelligence and Multiagent Systems） on the other side. Typical computational problems studied in this field include the vulnerability of voting procedures against attacks, or preference aggregation in multi-agent systems. Parameterized Algorithmics is a subfield of Theoretical Computer Science seeking to exploit meaningful problem-specific parameters in order to identify tractable special cases of in general computationally hard problems. In this paper, we propose nine of our favorite research challenges concerning the parameterized complexity of problems appearing in this context. This work is dedicated to Jianer Chen, one of the strongest problem solvers in the history of parameterized algorithmics,on the occasion of his 60 th birthday.     

复杂性研究——转变思维模式的一个重要方向

复杂性研究针对以牛顿力学为代表的近代科学思维模式的简单化、绝对化、忽视时间作用等弊病,为思维模式的转变提供了一种新的思路和方向,本文从概念的多元化、质的多样性、视角多样性、层次多样性、时间的作用、信息的作用等6个方面切入,认识和理解复杂性。并以经济学为例,阐述了复杂性在实际工作中的运用。     

浅探战争系统复杂性概貌

结合系统论的观点,从战争系统的元素以及元素之间关系两方面讨论了战争系统的系统论模型.从组分复杂性、结构复杂性和功能复杂性三方面阐述了战争系统的复杂性本体论模型.分析了战争复杂系统不对称性、远离平衡态、自组织、不可逆不可重复性、记忆性和局域作用效应等特性表现.最后,从建模与仿真的角度对战争系统的复杂性能否被简化以及人的因...     

Inhomogeneity,dynamical symmetry,and complexity in high-temperature superconductors:Reconciling a universal phase diagram with rich local disorder

A model for high-temperature superconductors incorporating antiferromagnetism,d-wave superconductivity,and no double lattice-site occupancy can give energy surfaces delicately balanced between antiferromagnetic and superconducting order for specific ranges of doping and temperature. The resulting properties can reconcile a universal cuprate phase diagram with rich inhomogeneity,relate that inhomogeneity to pseudogaps,give a fundamental rationale for giant proximity eects and other emergent behavior,and provide an objective framework to separate essential from peripheral in the superconducting mechanism.