平行视觉:基于ACP的智能视觉计算方法

在视觉计算研究中,对复杂环境的适应能力通常决定了算法能否实际应用,已经成为该领域的研究焦点之一.由人工社会（Artificial societies）、计算实验（Computational experiments）、平行执行（Parallel execution）构成的ACP理论在复杂系统建模与调控中发挥着重要作用.本文将ACP理论引入智能视觉计算领域,提出平行视觉的基本框架与关键技术.平行视觉利用人工场景来模拟和表示复杂挑战的实际场景,通过计算实验进行各种视觉模型的训练与评估,最后借助平行执行来在线优化视觉系统,实现对复杂环境的智能感知与理解.这一虚实互动的视觉计算方法结合了计算机图形学、虚拟现实、机器学习、知识自动化等技术,是视觉系统走向应用的有效途径和自然选择.     

基于社会网络视角的交通仿真和计算实验研究文献分析

交通仿真和计算实验作为交通科学问题研究和工程应用实践中的重要方法和手段, 受到越来越多的关注.本文从社会网络角度, 分析了2000年～2012年来, ISI Web of Science (WoS) 收录的关于交通仿真及计算实验研究的文献. 本文工作分为三部分: 首先, 分析了近13年来该领域每年论文的发表趋势; 其次, 引入社会网络, 从论文数量、影响力、合作关系和知识传播度四个方面考察了关键学者, 并给出了其合作关系聚类图; 最后, 仍然从上述四个方面考察了本领域内关键的研究机构. 结果表明: 该领域的研究成果和研究机构增长迅速; 学者之间的合作关系非常广泛且极为复杂; 合作的广泛程度与知识传播度并无明显的相关性; 研究机构层面的合作呈现分散状态, 且合作单位数量较少.     

最大圈分解问题的研究进展

最大圈分解问题最早由Erds和Pósa提出,随后研究人员在图论领域和理论计算机科学领域中对其进行了广泛的探索。最近研究发现,该问题在计算生物学上特别是在构建进化树与分析基因组的研究方面有重要的应用。主要介绍了该问题的研究现状。首先讨论了该问题在图论方面的研究进展;随后对该问题的近似算法、参数算法、参数复杂性与不可近似性进行了分析和讨论;最后给出了该问题的进一步研究方向。     

形式化方法概貌

形式化方法是基于严格数学基础,对计算机硬件和软件系统进行描述、开发和验证的技术.其数学基础建立在形式语言、语义和推理证明三位一体的形式逻辑系统之上.形式化方法已经以不同程度和不同方式愈来愈多地应用在计算系统生命周期的各个阶段.介绍了形式化方法的发展历程和基本方法体系;以形式规约和形式验证为主线,综述了形式化方法的理论、方法、工具和应用的现状,展示了形式化方法与软件学科其他领域的交叉和融合;分析了形式化方法的启示,并展望了其面临的发展机遇和未来趋势.形式化方法的发展和研究现状表明：其应用已经取得了长足的进步,在提高计算系统的可靠性和安全性方面发挥了重要作用.在当今软件日益成为社会基础设施的时代,形式化方法将与人工智能、网络空间安全、量子计算、生物计算等领域和方向交叉融合,得到更加广阔的应用.研究和建立这种交叉融合的理论和方法不仅重要,而且具有挑战性.     

粒度计算研究综述

粒度计算GrC（Granular Computing）是信息处理的一种新的概念和计算范式,覆盖了所有有关粒度的理论、方法、技术和工具的研究.它是词计算理论、粗糙集理论、商空间理论、区间计算等的超集,也是软计算科学的一个分支,已成为模糊的、不完整的、不精确的及海量的信息处理的重要工具和人工智能研究领域的热点之一.本文综述了粒度计算的发展动机、研究现状及发展趋势,着重介绍了粒度计算的主要理论模型与方法及其在不同领域的应用,对存在的问题进行了分析,并提出了进一步研究的方向.     

蚁群算法及其在移动机器人路径规划中的应用

蚁群算法是优化领域中新出现并逐渐引起重视的一种仿生进化算法.首先介绍了蚁群算法基本原理和特点;然后回顾近年来国内外学者针对移动机器人路径规划的特点,对蚁群算法的进行改进,将其引入移动机器人中进行障碍规避和寻找最优路径,所提出的各种静态路径规划和动态路径规划方法的基本思想和特点.最后分析了蚁群算法在移动机器人路径规划应用中存在的问题,以及该学科未来研究方向.     

抽象解释理论框架及其应用

在高度依赖计算机的现代社会,软件（特别是大型实时安全攸关软件）的可靠性成为计算机界和整个社会都非常关注的问题。现有的形式化软件验证工具都不得不通过近似来处理复杂问题中的计算,P.Cousot和R.Cousot提出的抽象解释作为一种在数学模型间进行可靠近似的理论,为各类自动验证工具中不同的近似方法建立起一个统一的形式化框架。抽象解释理论在程序分析和验证研究领域得到了广泛的关注与应用,其应用范围涵盖了程序静态分析、程序变换、程序调试、程序水印等方面。描述了基于程序不动点语义的抽象解释理论框架,并对其近年来的应用现状进行了较为全面的介绍,最后给出了抽象解释理论中尚存在的一些问题及可能的研究方向。     

最长路径问题研究进展

最长路径问题是著名的NP难问题,在生物信息学等领域中有着重要的应用.参数计算理论产生后,参数化形式的k-Path问题成了研究的热点.介绍了现有求解最长路径问题的几种算法,包括近似算法、参数化算法和特殊图的多项式时间算法;着重分析和比较了参数化算法中利用着色、分治和代数法研究k-Path问题的最新结果.最后,提出了该问题的进一步研究方向.     

二维解析张量投票算法研究

针对传统张量投票(Tensor voting)算法计算过程复杂、算法效率低的问题, 本文提出了一种二维解析张量投票算法.首先, 深入分析张量投票理论的基本思想, 分析传统张量投票算法的不足及其根源; 其次, 设计了一种二维解析棒张量投票新机制, 实现了二维解析棒张量投票的直接求取; 在此基础上, 利用二维解析棒张量投票不依赖参考坐标系的特性, 设计并求解了二维解析球张量投票表达式, 解决了长期困扰张量投票理论中球张量投票无法解析求解, 仅能通过迭代数值计算, 计算过程复杂、算法效率低、算法精度与算法效率存在矛盾的难题.最后, 通过仿真分析和对比实验验证了本文算法在精度和计算效率方面的性能均优于传统张量投票算法.     

软计算融合技术研究

软计算是求近似而非精确解的有效计算方法,已经在众多领域得到应用,取得了很好的效果.然而,每个软计算方法具有鲜明的特色和迥异的侧重点,在实际应用中存在一些不足,将软计算方法进行融合,优势互补,是促进软计算发展的关键技术之一.文中简要介绍了软计算发展概况,结合粗糙集、神经网络、模糊逻辑、遗传算法、人工免疫算法等软计算方法,详细分析了软计算融合技术的现状及分类,指出了该领域面临的缺乏理论基础、设计原则、定量评价等主要问题及其发展趋势     

Manipulation can be hard in tractable voting systems even for constant-sized coalitions

Voting theory has become increasingly integrated with computational social choice and multiagent systems. Computational complexity has been extensively used as a shield against manipulation of voting systems, however for several voting schemes this complexity may cause calculating the winner to be computationally difficult. Of the many voting systems that have been studied with regard to election manipulation, a few have been found to have an unweighted coalitional manipulation problem that is NP-hard for a constant number of manipulators despite having a winner problem that is in P. We survey this interesting class of voting systems and the work that has analyzed their complexity.     

Computational complexity of manipulation: A survey

In situations when a group of people has to make a decision based on the set of individual preferences, they use a certain aggregation method, in particular, voting. One of the main problems for any non-dictatorial social choice rule is the possibility for the voters to achieve a more preferable outcome of the voting by misrepresenting their preferences. Such actions on behalf of the voters are called manipulation, or strategic voting. One approach used to compare social choice rules in terms of how hard they are to manipulate is to find the complexity classes of manipulation problems for a given aggregation method. In this work, we present a survey of the studies of complexity classes of manipulation problems under various model assumptions and constraints.     

Parameterized Computation and Complexity： A New Approach Dealing with NP-Hardness

The theory of parameterized computation and complexity is a recently developed subarea in theoretical computer science. The theory is aimed at practically solving a large number of computational problems that are theoretically intractable.The theory is based on the observation that many intractable computational problems in practice are associated with a parameter that varies within a small or moderate range. Therefore, by taking the advantages of the small parameters, many theoretically intractable problems can be solved effectively and practically. On the other hand, the theory of parameterized computation and complexity has also offered powerful techniques that enable us to derive strong computational lower bounds for many computational problems, thus explaining why certain theoretically tractable problems cannot be solved effectively and practically. The theory of parameterized computation and complexity has found wide applications in areas such as database systems, programming languages, networks, VLSI design, parallel and distributed computing, computational biology, and robotics. This survey gives an overview on the fundamentals, algorithms, techniques, and applications developed in the research of parameterized computation and complexity. We will also report the most recent advances and excitements, and discuss further research directions in the area.     

伦理智能体及其设计:现状和展望

智能体一直是人工智能的主要研究领域之一,任何独立的能够同环境交互并自主决策的实体都可以抽象为智能体.随着人工智能从计算智能到感知智能,再到认知智能的发展,智能体已逐步渗透到无人驾驶、服务机器人、智能家居、智慧医疗、战争武器等人类生活密切相关的领域.这些应用中,智能体与环境、尤其是与人类和社会的交互愈来愈突出,其中的伦理和道德问题日益凸显.人工智能应用的伦理风险和挑战引起了人们的普遍关注,伦理智能体是人工智能伦理的重要研究内容.本文从人工智能伦理的工程设计与实现角度,对伦理智能体及图灵测试、伦理智能体的设计范式、伦理智能体的逻辑程序设计、伦理智能体的形式化验证、伦理困境及分析等进行了介绍和讨论.同时,对伦理智能体及设计所面临的挑战和进一步研究方向进行了述评和展望.     

Manipulation Complexity of Same-System Runoff Elections

Do runoff elections, using the same voting rule as the initial election but just on the winning candidates, increase or decrease the complexity of manipulation? Does allowing revoting in the runoff increase or decrease the complexity relative to just having a runoff without revoting? For both weighted and unweighted voting, we show that even for election systems with simple winner problems the complexity of manipulation, manipulation with runoffs, and manipulation with revoting runoffs are independent. On the other hand, for some important, well-known election systems we determine what holds for each of these cases. For no such systems do we find runoffs lowering complexity, and for some we find that runoffs raise complexity. Ours is the first paper to show that for natural, unweighted election systems, runoffs can increase the manipulation complexity.     

Survey of clustering algorithms

Data analysis plays an indispensable role for understanding various phenomena. Cluster analysis, primitive exploration with little or no prior knowledge, consists of research developed across a wide variety of communities. The diversity, on one hand, equips us with many tools. On the other hand, the profusion of options causes confusion. We survey clustering algorithms for data sets appearing in statistics, computer science, and machine learning, and illustrate their applications in some benchmark data sets, the traveling salesman problem, and bioinformatics, a new field attracting intensive efforts. Several tightly related topics, proximity measure, and cluster validation, are also discussed.     

Java Based Distributed Learning Platform

This paper introduces the principle and method of a java based distributed learning platform. Java plays two roles in this project. On one hand, the learning platform bases on java; on the other hand, the platform can provide a lot of examples of programs and demos in java language for some courses of computer science specialty. A distributed learning environment is offered to the students in computer science specialty, which can improve the teaching effect.     

Basic research in computer science and software engineering at SKLCS

The State Key Laboratory of Computer Science (SKLCS) is committed to basic research in computer science and software engineering. The research topics of the laboratory include: concurrency theory, theory and algorithms for real-time systems, formal specifications based on context-free grammars, semantics of programming languages, model checking, automated reasoning, logic programming, software testing, software process improvement, middleware technology, parallel algorithms and parallel software, computer graphics and human-computer interaction. This paper describes these topics in some detail and summarizes some results obtained in recent years.     

Basic research in computer science and software engineering at SKLCS

The State Key Laboratory of Computer Science (SKLCS) is committed to basic research in computer science and software engineering. The research topics of the laboratory include: concurrency theory, theory and algorithms for real-time systems, formal specifications based on context-free grammars, semantics of programming languages, model checking, automated reasoning, logic programming, software testing, software process improvement, middleware technology, parallel algorithms and parallel software, computer graphics and human-computer interaction. This paper describes these topics in some detail and summarizes some results obtained in recent years.     

From risk factors to detection and intervention: a practical proposal for future work on cyberbullying

While there is an increasing flow of media stories reporting cases of cyberbullying, particularly within online social media, research efforts in the academic community are scattered over different topics across the social science and computer science academic disciplines. In this work, we explored research pertaining to cyberbullying, conducted across disciplines. We mainly sought to understand scholarly activity on intelligence techniques for the detection of cyberbullying when it occurs. Our findings suggest that the vast majority of academic contributions on cyberbullying focus on understanding the phenomenon, risk factors, and threats, with the prospect of suggesting possible protection strategies. There is less work on intelligence techniques for the detection of cyberbullying when it occurs, while currently deployed algorithms seem to detect the problem only up to some degree of success. The article summarises the current trends aiming to encourage discussion and research with a new scope; we call for more research tackling the problem by leveraging statistical models and computational mechanisms geared to detect, intervene, and prevent cyberbullying. Coupling intelligence techniques with specific web technology problems can help combat this social menace. We argue that a multidisciplinary approach is needed, with expertise from human–computer interaction, psychology, computer science, and sociology, for current challenges to be addressed and significant progress to be made.