“离散数学”课程教学实施方案

离散数学是计算机科学技术的基础,已经广泛地用于计算机系统的建模和分析。在教育部高等学校计算机科学与技术教学指导委员会统一组织下,作者对离散数学课程在专业课程体系中的定位与教学情况进行了调研,并针对课程的教学目标、教学内容、教学设计等提出了相应的教学实施方案。本方案的特点是:提供一个分层的、模块化的知识框架,教师可根据科学型、工程型、应用型的不同培养目标进行教学内容的灵活配置;在教学设计中强化离散数学课程与其他专业课程之间的联系,强化素质和能力培养。

面向软件工程学科的算法课程建设

算法不但是计算机科学与技术专业的核心课程,也是软件工程专业的核心课程。算法知识不仅广泛地用于软件系统的设计与分析中,同时对培养学生分析和解决实际问题的能力具有重要的作用。本文基于北京大学软件与微电子学院的教学实践,对软件工程专业硕士研究生算法课程的教学改革进行了总结,提出了相应的教学实施方案。本方案的特点是:以素质和能力培养为目标,构建面向不同教学要求的模块化的知识框架,并注重理论联系实际,在软件系统建模和分析中强化应用。

用变换型方法模拟开发电话交换系统

本文给出了用变换型软件开发方法（Ｓｐｅｃｉｆｉｃａｔｉｏｎ＋Ｔｒａｎｓｆｏｒｍａｔｉｏｎ＝Ｓｏｆｔｗａｒｅ）模拟开发电话交换系统的描述，由抽象的软件规范出发，通过一系列变换实现了数据的精化和操作的分解，最终得到可在机器上运行的程序。整个开发过程是用变换型语言Ｐｏｌｙａ写的。最后提出了对Ｐｏｌｙａ的改进建议。

黑人女性的凝聚之力——对《宠儿》中塞丝的女性主义解读

托尼.莫里森的长篇小说《宠儿》,叙述了在白人权威肆意践踏性别尊严、蔑视种族身份的文化语境中,黑人女性所进行的百折不挠的文化身份和生存价值的追求,并由此揭示了作家特有的黑人女性主义思想:要争取真正意义上的生存,黑人女性就必须首先结成一个有凝聚力的群体。

一个图增广问题的NC算法

随着并行计算和网络技术的广泛应用，图论中的ｋ－边连通性增广问题受到越来越多的注意。早期的研究已经证明一般性的增广问题是ＮＰ难的，但对它的某些子问题，即当ｋ＝２，Ｅ０（Ｇ的补图的边集）中所有边的权都相等时，存在着多项式时间的顺序算法。本文针对上述子问题，在ＳＩＭＤＰＲＡＭＣＲＣＷ并行计算模型上给出了一个Ｏ（ｌｏｇｎ）时间，Ｏ（ｎ＋ｍ）处理器的ＮＣ算法。

一个预测RNA二级结构的回溯算法

本文讨论了一个预测RNA二级结构的回溯算法。该算法根据极大基配对的原则按字典顺序产生所有可能的二级结构。它的时间复杂性是O(n^2),空间复杂性是O(n)。

基于Petri网的工作流模式——工作流模式分析研究

随着企业建模、工作流概念的出现以及相关技术的发展,Petri网因其既有严格的形式定义,又有直观的图形表示,既有丰富的系统描述手段和系统行为分析技术,又为计算机科学提供坚实的概念基础等诸多优点也被应用于这一新兴领域,对工作流理论基础进行研究。本文将利用Petri网来描述和分析工作流的各种模式,比较模式之间的异同,并对模式进行合并和重划分。

从河内塔的并行解到UNITY程序设计

从事并行程序设计实践的人往往把精力耗费在为变量分配内存，为循环体寻求并行上，却忽略对问题本身的分析．其实能否并行的决定因素是应用问题本身．人们往往急于得到能够运行的代码，一开始就把复杂的问题和复杂的并行环境掺和起来了．河内塔（HanoiTower）问题看似无法并行，实际上却允许极大的并行．它的并行解及求解过程对并行程序设计应有一定的启发．

无线自组织网络中构造2-连通k-支配虚拟主干网的近似算法

在无线自组织网络中,经常选取一些节点形成虚拟主干网,用以支持路由和区域监视等任务。由于无线网络自身存在误码率高、易受干扰等弱点,虚拟主干网需要具有一定的容错性。已经有研究者提出使用k-连通k-支配集合在无线自组织网络中构造容错虚拟主干网,并通过模拟实验评估了算法的性能。近年来,WangFeng等人设计了常数近似算法用来构造2-连通虚拟主干网。本文将设计一个常数近似算法用以在无线自组织网络中构造一个2-连通k-支配虚拟主干网。

程序属性的UniNet描述

在传统建模方法中,程序操作和程序自我控制相脱离,使得程序的计算与并行特性不能形成完整的一致性的描述,因此形成的规范都只是从某一个角度来刻画了程序。为克服这些不足,本文在揭示程序状态与操作,操作与控制共存的事实的基础上,采用UniNet独特的描述方法来完整而全面地刻画程序。

工作流分层模型的PNML表示

PNML是一种基于XML的Petri网交换格式,在工作流引擎内部使用PNML表示业务流程的模型,可以使得引擎和其他支持PNML表示的工具之间具有很强的互操作性.为此需要先定义新的标签,然后给出新的Petri网类型定义,最后通过例子阐明了如何用扩展后的PNML表示工作流分层模型.借助PNML表示,实现的工作流引擎工具具有很强的扩展性,能够和其他支持PNML的工具进行数据交换.

库所组合有色网-一种新型的有色网

为了解决用Petri网描述复杂系统时出现的"节点爆炸"问题,本文提出了四种特殊的弧:约束弧、柔性弧、组合弧和因果弧.库所组合有色网就是在有色网的基础上添加这四种特殊的弧得到的,这种网系统并没有增加描述能力,但在描述具有组合效果的系统时具有强大的先天优势.本文通过为电梯控制系统建模示例了这四种弧为简化模型带来的便捷之处.

一种新的时段演算及其验证

在Pandya提出的CTL*[DC]逻辑的基础上,对其语法和语义进行扩展,并对路径长度进行限制,定义了一个新的逻辑CTL*[k-QDDC],它可应用于实时系统的描述和验证.给出了在Kripke结构中直接验证CTL*[k-QDDC]逻辑公式在某状态是否成真的基本算法.在某些假设下,也证明了CTL*[k-QDDC]中的某个逻辑运算符的验证问题是NP完全的,这就说明CTL*[k-QDDC]的验证问题至少是NP难的.

基于同步网的BPEL建模和验证

Web服务组合是面向服务架构的一个应用,是指将已有的Web服务组合成为新的服务。业务流程执行语言BPEL(Business Process Execution Language)是一种描述Web服务组合的语言。为了保证BPEL描述的Web服务组合的正确性,提出了分层建模和验证的思想,将BPEL流程分为逻辑层和语义层,并分别建立形式化模型和验证方法。这样不仅能保证对流程正确地建模,而且能降低建模和验证的复杂度。在逻辑层,BPEL元素映射为基于同步网的WSL_net模型。畅通性和无冗余变迁性质保证了BPEL流程基本控制流的正确性并避免了资源的浪费。语义层的建模和验证将另文给出。

死路删除语义下的WS-BPEL流程的建模

提出一种新的模型——DPE网,用于描述死路删除语义下的WS-BPEL流程。DPE网中引入了颜色集CTRL和STAT以表示活动执行的状态和并发活动内链接的状态。这在一定程度上降低了模型的规模,从而得到更为直观的模型。基于DPE网,不仅描述了WS-BPEL流程的基本控制流,包括基本活动和各种结构化活动,而且描述了WS-BPEL流程的死路删除语义和较完整的link语义,包括join condition和transition condition。最后,通过一个实例说明了使用DPE网建模WS-BPEL流程,有助于得到更为准确的分析结果。

小度数循环图的计数

循环图已被用于平行计算，网络等方面．循环图研究的一个基本问题是对互不同构的循环图进行计数．对于给定的一个正整数ｎ，用Ｃ（ｎ，ｋ）表示互不同构的具有几个顶点，度数为ｋ的连通循环图的个数．文中给出了度数为 ４和５的循环图的一般结构，并对ｎ＝ｐａｑｂ（ｐ，ｑ皆为素数，ａ，ｂ＞０），给出了Ｃ（ｎ，４）的计算公式．