网络涌现现象对网络安全的影响研究

网络安全是网络管理中的一个至关重要问题,随着计算机网络在连结信息能力、流通能力快速提高的同时,基于网络连接的安全问题也日益突出,因此认清网络的脆弱性和潜在威胁,采取强有力的安全策略,对于保障网络的安全性将变得十分重要。Internet作为一个复杂的网络自适应系统,它所涌现出的突现行为对网络安全构成了一定影响。该文首先探讨了Internet网络拓扑结构呈现出Power-law这一网络涌现现象的生成机制,对这种涌现现象的受限生成过程进行了数学描述,然后讨论了该网络涌现现象对网络安全的影响,最后对网络安全的防范措施提出了建议。     

基于程序生成的软件过程模型

随着计算机技术的发展,瀑布式软件开发模型日显不足,探索研究新的软件过程模型势在必然,CASE环境EASYCODE对此作了有益的尝试。本文在对传统的生命期模型作了简析后,讨论EASYCODE软件过程模型的特点,并阐述支撑该模型的基于知识的程序生成。     

AER模型中的智能涌现

本文从复杂自适应理论和人工生命基本观点出发,研究一个具有简单性、局部性、全局性、内聚力、动态性的复杂自适应系统,并创建包含智能体、环境、交互规则三个主要概念以及适者生存的淘汰规则的AER多主体模型.该模型中具有局部目标和行为的自主体能通过动态环境达到整体的全局目标,这种涌现的智能能够高效求解问题.实验证明该模型对传统的大规模约束满足问题的测试集,包括n-皇后问题(n=7 000)和一些大规模染色问题,均能在较快的时间内找到精确解,同时能在3个时间片内找到精确度(≥94%)很高的近似解.     

过程模型的测试用例自动生成研究

在软件测试中,测试用例的自动生成问题近来是一个研究的热点,基于代码的测试用例的自动生成技术目前已很成熟,但基于过程模型的测试用例的自动生成技术却没有起步。为了解决这一问题,本文提出了双向过程切片的概念并使用该技术,在北航软件工程研究所开发的企事业建模系统EPMS（Enferprise Process ModeIing System）中的过程模型建造环境PMBE（Process Building Environment）基础上,实现了过程模型的测试用例的自动生成技术,并通过了数个实际项目的验证。     

半图厄过程字问题的计算复杂性

本文研究了几种加限制的半圈厄过程的字问题的计算复杂性。主要结果是：１．字母表只含一个符号的半圈厄过程的字问题是ＮＰ完全的；２．对于任一固定的字母表只含一个符号的半图厄过程，它的字问题属于Ｐ；３．单调的半图厄过程的字问题是ＰＳＰＡＣＥ完全的；４．限制派生长度的字问题是ＮＥＸＰＴＩＭＥ完全的。     

交互计算模型概述

由于计算机技术的发展日新月异,以算法为核心,以图灵机和Church论题等为理论依据的计算模型已无力继续成为今天计算科学的理论范式,介绍了一个崭新的计算模型－－交互计算模型的基本思想,它是对算法的扩展,并比算法具有更强的描述能力,一系列基本概念被扩展到交互。     

基于复杂性科学基本概念的MAS涌现性量化研究

在MAS(Multi-Agent System)领域,面向涌现的MAS研究将MAS看成一类特殊的复杂系统,其关注点是MAS宏观层面的涌现性问题.这类研究需要借用复杂性科学研究中的一些基本概念描述、阐述MAS涌现性研究中的问题.文中着重对几个常用的基本概念及其量化研究做一概览,以深化对它们的认识,并结合这些概念及其量化研究在MAS涌现性研究中的应用特点,阐明它们对面向涌现的MAS研究的作用,以促进进一步的研究.这些概念包括复杂性、混沌边缘、自组织、涌现、适应和进化等.     

计算资源受限的移动边缘计算服务器收益优化策略

移动边缘计算（MEC）服务器通过向用户提供计算资源获得收益。对MEC服务器而言,如何在计算资源受限的情况下提高自身收益至关重要,为此提出一种通过优化计算任务执行次序提高MEC服务器收益的策略。首先,将MEC服务器收益最大化问题建模为以任务执行次序为优化变量的优化问题;然后提出了一种基于分支定界法的算法求解任务执行次序。仿真结果表明,采用所提算法获得的MEC服务器平均收益分别比大任务优先（LTF）算法、低延迟任务优先（LLTF）算法和先到先服务（FCFS）算法提高了11%、14%和21%。在保证卸载用户服务质量（QoS）同时,所提策略可以显著提高服务器的收益。     

IPM——一种增量计算的自动生成模型

增量计算在排版系统、编译系统和各种软件工具中有着广泛的应用,而实现一个增量式软件系统往往需要采用复杂的算法设计和艰苦的程序调试.近年来,随着部分求值技术的发展,人们开始研究用于增量计算的通用的程序生成方法,以求从根本上消除使用增量计算实现算法的需求。 有关增量计算自动生成的研究工作,大致可分为两类一类以耶鲁大学的Hudak研究组为代表[lJ,力图建立一种完成增量计算的程序执行环境。在这种环境中,应用程序的每次执行将能够利用上次执行的部分计算结果。另一类以康乃尔大学的Teitel-baum研究组为代表,试图将应用程序变换成采用增     

基于受限行为约束策略的桌面计算系统交互性能测量方法

测量桌面计算系统的交互性能是分析和改进系统性能的重要基础.方便地获得准确测量结果的难点是如何确定输入事件和其直接触发的输出事件之间的对应关系.为此,提出一种采用受限行为约束策略的交互性能测量方法,首先分析了确定输入、输出事件的对应关系需要满足的约束条件,通过会话录制辅助机制合理转化难以满足约束条件的事件,通过用户行为检验机制进一步确认所有事件已经满足约束条件,从而保证可以获得更准确的测量结果.基于该方法,实现了一个支持Windows和Linux等主流桌面计算系统的测量工具VNC-IPA.实验以"慢动作"基准测量A-法获得的测量结果为真值,结果表明,相比其他交互性能测量工具VNCplay,使用VNC-IPA获得的测量结果的相对误差平均降低了35.4%.     

A note on alternating one-pebble Turing machines with sublogarithmic space

Inoue et al. [A. Inoue, A. Ito, K. Inoue, T. Okazaki, Some properties of one-pebble Turing machines with sublogarithmic space, Theoret. Comput. Sci. 341 (2005) 138-149] conjectured that the language {ww|w∈⁺{a,b}} is not accepted by any alternating one-pebble Turing machine with sublogarithmic space. In this paper we disprove the conjecture by showing that there exists an alternating one-pebble Turing machine accepting the language in loglogn space.     

Three-dimensional parallel Turing machines

Informally, the parallel Turing machine (PTM) proposed by Wiedermann is a set of identical usual sequential Turing machines (STMs) cooperating on two common tapes: storage tape and input tape. Moreover, STMs which represent the individual processors of a parallel computer can multiply themselves in the course of computation. On the other hand, during the past 25 years or so, automata on a three-dimensional tape have been proposed as computational models of three-dimensional pattern processing, and several properties of such automata have been obtained. We proposed a three-dimensional parallel Turing machine (3-PTM), and dealt with a hardware-bounded 3-PTM whose inputs are restricted to cubic ones. We believe that this machine is useful in measuring the parallel computational complexity of three-dimensional images. In this article, we continue the study of 3-PTM, whose inputs are restricted to cubic ones, and investigate some of its accepting powers. This work was presented in part at the 12th International Symposium on Artificial Life and Robotics, Oita, Japan, January 25–27, 2007     

Some accepting powers of three-dimensional parallel Turing machines

Informally, the parallel Turing machine (PTM) proposed by Wiedermann is a set of identical usual sequential Turing machines (STMs) cooperating on two common tapes: storage tape and input tape. Moreover, STMs which represent the individual processors of a parallel computer can multiply themselves in the course of computation. On the other hand, during the past 25 years or so, automata on a three-dimensional tape have been proposed as computational models of three-dimensional pattern processing, and several properties of such automata have been obtained. We proposed a three-dimensional parallel Turing machine (3-PTM),¹ and dealt with a hardware-bounded 3-PTM whose inputs are restricted to cubic ones. We believe that this machine is useful in measuring the parallel computational complexity of three-dimensional images. Here, we continue the study of 3-PTM, whose inputs are restricted to cubic ones, and investigate some of its accepting powers. This work was presented in part at the First European Workshop on Artificial Life and Robotics, Vienna, Austria, July 12–13, 2007     

Space-bounded simulation of multitape turing machines

A new proof of a theorem of Hopcroft, Paul, and Valiant is presented: Every deterministic multitape Turing machine of time complexityT(n) can be simulated by a deterministic Turing machine of space complexityT(n)/logT(n). The proof includes an overlap argument.Supported by National Science Foundation Grant No. MCS-78-04343.Supported by National Science Foundation Grant No. MCS-77-19754 and the Fannie and John Hertz Foundation.     

Matching upper and lower bounds for simulations of several linear tapes on one multidimensional tape

We prove an O(t(n) ^d (t(n)) ^? / log t(n)) time bound for the sim-ulation of t(n) steps of a Turing machine using several one-dimensional work tapes on a Turing machine using one d-dimensional work tape, . We prove a matching lower bound which holds for the problem of recognizing languages on machines with a separate one-way input tape. Received: March 1995.     

Tax evasion behavior using finite automata: Experiments in Chile and Italy

In this paper, we use a Moore Automata with Binary Stochastic Output Function in order to capture the extensive decision regarding tax evasion made by subjects in experiments run in Chile and Italy. Firstly, we show how an hypothesis about subject behavior is converted into an automaton, and how we compute the probabilities of evading for every state of an automaton. We use this procedure in order to look for the automaton which is able to anticipate the highest number of decisions made by the subjects during the experiments. Finally, we show that automata with few states perform better than automata with many states, and that the bomb-crater effect described in Mittone (2006) is a well identified pattern of behavior in a subset of subjects.     

逼近于BPP和PP的概率复杂性语言类的多项式有界线路复杂性研究

本文通过图灵机多项式?输出有界和多项式错误输出有界概念的引入,研究了逼近于BPP和PP的一些概率复杂性语言类的多项式有界线路复杂性。