数据流方程组的公式解法

数据流方程有许多解法,如J.Cocke和 F.E.Allen 等提出的区间法以及J.D.Ullman等提出的迭代法,这些方法的“对角线项”是求解中的主要困难。张鸣华证明了方程的最小解与“对角线项”无关,因此提出了一种直接解法。为了求解,要把数据流方程显式化,本文给出了求显式方程的算法,并且提出了一个公式,应用这个公式,可以直接把显式方程写出来。     

半格基础上的数据流分析

许多数据流的全局分析可以在布尔代数的基础上进行。为了解决更多的数据流问题,需要采用更为一般的代数系统。半格是一个合适的基础。但是,在这方面得到的结果还不多,原先在布尔代数基础上发展起来的一些算法,如区间方法、Ullman的方法等,如何扩充到半格的情况也不清楚。 本文把[10]的结果扩充到半格的情况,证明半格方程具有与布尔代数方程类似的性质。因此也可以引进半格方程的两种变换,并利用这些变换求解。通过这两种变换,也就可以把区间方法及Ullman的方法进行扩充。     

正则表达式方程组的最小解

网络安全检测中,正则表达式匹配是深度包检测的主要手段,匹配算法则是其关键技术。目前,正则表达式匹配算法可以大体分为转换压缩、状态压缩和字母表压缩三类。文章讨论正则表达式方程组最小解及其求解算法,证明了正则表达式方程组的最小解的存在性和基于Gauss消元法的求解算法的正确性,给出了最小解的构造,分析了求解算法的时间复杂度...     

软件工程(五) 软件开发方法——软件设计(2)

二、结构化设计技术结构化设计技术是以数据流图为基础设计系统的模块结构。我们从表达“需求分析”的数据流图找出一些简单的规律,从而便于导出初始的模块结构。先讨论一下数据流图的类型。1.数据流图的类型具有较明确的输入、变换(或称主加工)和输出界面的数据流图称为变换型数据流图。这类数据流图可以明显地分成输入、主加工和输出三个部分。如图9所示。在变换型数据流图中,主加工是系统的中心工作,主加工的输入数据流“合格的汇款单”是系统的“逻辑输入”;主加工的输出数据流“核准后的汇款单”是系     

基于布尔矩阵的初等行变换的知识约简算法

给出了布尔矩阵的初等行变换定义，建立了线性逻辑方程组形式的属性约简模型，用布尔矩阵的初等行变换把系数矩阵化为最简矩阵，给出了用系数矩阵和最简矩阵判定绝对必要属性、相对必要属性和绝对不必要属性的三个充分必要条件，并由此提出了一种知识约简的快速算法。     

基于数据流的概念聚类

分析二部图的二元组和概念聚类问题之间的关系，在此基础上结合数据流的特点，提出一种适用于对象属性为布尔型的数据流概念聚类算法。将数据流分段，对每一批到来的数据流，生成局部的近似极大ε二元组集合，对全局的近似极大ε二元组集合进行更新，从而有效地对整个数据流进行聚类。实验结果表明，该算法具有良好的时间效率和空间效率。     

流非敏感的跨过程的别名分析

数据流分析算法可以分类成流敏感和流非敏感两类。为了提高效率,流非敏感的跨过程分析没有利用与每个过程相关的过程内的控制流信息。文中,提出了一种流非敏感的数据流分析算法来计算指针引起的跨过程的别名问题。通过如下方法来提高了分析的精度:利用某些特定类型的注销(kill)信息,这些信息可以提前计算;计算每个过程内产生的别名信息,而不是只计算每个过程的出口点产生的别名信息。     

框图格式的等价问题(Ⅱ)

在[1]中我们利用代数方程组来研究框图格式的等价问题。为了便于实际运算,本文引用另外一种方程,叫做算子方程。可以把算子方程看做[1]中框图方程的另一种表示形式。因此,[1]中关于方程组的变换及其与框图格式等价性的关系都可以转移到算子方程上来。 作为上述结果的应用,我们研究了框图格式的结构化问题。本文给出若干算法。根据这些算法,从任意一个给定的框图格式出发,利用变换总可以找到与它等价的D框图。从这个意义上说,我们引进的变换具有某种完备性。这些算法通过代数运算把等价的结构化框图计算出来,与现有的算法(例如[3,4]所给的)相比,这是本文算法的一个特点。     

数据流分析方法

数据流分析是一项编译时使用的技术,它能从程序代码中收集程序的语义信息,并通过代数的方法在编译时确定变量的定义和使用。该文对数据流、数据流框架及数据流算法进行了阐述;并简要地介绍了所提出的需求过程间数据流分析的方法。     

智能路灯控制系统缺失数据流关联修复仿真

为了避免智能路灯控制系统受缺失数据影响,研究了智能路灯控制系统缺失数据流关联修复仿真方法。选取嵌套窗口的流数据处理模型检测智能路灯控制系统的缺失数据流,嵌套窗口的流数据处理模型将滑动窗口分割为多个嵌套滑动窗口,滑动窗口过程中,利用Pearson相关系数确定智能路灯控制系统中相邻数据的相关性,依据获取的数据相关性重构相关图,利用相关图检测智能路灯控制系统缺失数据流。选取GMM算法划分存在缺失数据的智能路灯控制系统的数据集,选取EM插补算法关联修复完成初始数据集划分后的数据流。仿真测试结果表明,该方法可以有效修复智能路灯控制系统缺失数据流,不同数据缺失率情况下,均具有较高的缺失数据流关联修复精度。     

数据流分析的二进制程序理解方法

二进制程序数据流静态分析首先将被分析的程序转换成数据流描述标记,确定每个基本块的输入、输出定值集合,结合程序控制流图,建立模块内数据流方程组,通过迭代的方法解数据流方程并推导出函数输入与输出之间的联系,实现函数功能的静态理解。经过实验表明,在不需要额外提示的情况下,能够准确识别二进制形式的字符串拷贝函数。     

一种基于流图变换的代码迷惑算法

为了提高软件的安全性,常使攻击者难以理解专利软件系统内部的工作机制,代码迷惑技术因其代价低廉而越来越受到人们的重视。代码迷惑技术的提出对于软件保护具有非常重要的意义,代码迷惑技术的使用可以对程序代码及核心算法进行保护。简要概述了代码迷惑技术基本内容,阐述了基本块和流图的相关知识,给出了可归约流图变换为不可归约流图的迷惑变换具体的算法及实验结果,并对算法的有效性进行了分析。     

一种布尔多项式的高效计算机表示

布尔方程组求解技术对于密码分析具有重要的现实意义.然而,在众多求解算法的实际计算过程中,难以抑制的空间需求增长与计算机系统有限的存储能力之间的矛盾,正是当前制约布尔方程组求解技术取得更大成果的最主要瓶颈.针对基于消项的求解算法,分析了该矛盾的产生根源,提出了解决途径,进而设计了一种全新的布尔多项式计算机表示,称之为BanYan.BanYan适用于基于首项约化的求解算法,如F4,F5,XL等算法.通过记录中间结果的生成信息而非其本身,避免算法实现陷入项数规模高速膨胀带来的巨大存储负担.与BDD和系数矩阵等基于项的传统布尔多项式表示相比,平均情况以及最坏情况下,使用BanYan表示法所需要的空间约为项数表示法的1?l(l为计算过程中产生的多项式的平均项数),从而显著提升布尔方程组求解算法的现实求解能力.     

一种增量式数据流分析方法

数据流分析是编译器中重要部分，而增量式分析在程序开发环境和过程间优化编译器中有着相关实用的价值，当程序发生变化时，它可以增量式地维护数据流信息，而不致因程序的任何小改动都重新进行数据流分析，给出了一种增量式的消去数据流算法，它基于路径简化算法，具有和路径简化算法同样的复杂度，同样的通用性（适用于不可归约流图和流函数不完备的情况），而且能方便地在程序发生变化时维护现有的数据流信息。     

网络安全系统中的快速规则匹配

随着网络攻击的增多,各类安全系统被广泛应用,其关键和核心是规则匹配.加速规则匹配可以提高系统性能,使其适应更高速网络和更严格环境.介绍和分析了现有的两种主要规则匹配算法:布尔表达式树和有向无环控制流图,提出了一种快速规则匹配算法.该算法先对有向无环控制流图进行等价变换,再在此基础上进行概率优化和改进,通过调整规则内部的逻辑表示结构,使得规则的结构转换速度和计算速度都得到明显的提高.经过测试比较,该算法能有效缩短匹配时间,改善系统性能.     

基于二分图完善匹配的布尔匹配算法

提出了一种改进的基于二分图完善匹配的布尔匹配算法。该算法通过把布尔变量之间的匹配问题转换为二分图的完善匹配问题,避免了原算法中因乘积项过多而导致计算时间过长的缺点。对MCNC标准测试电路的实验结果表明;与原算法相比,改进后的算法可以减少21％左右的计算时间。同时,文中提出了布尔变量强匹配的概念,它是对传统布尔匹配概念的引申。     

基于改进布尔约减级数分层的大数据流滞后相关性挖掘方法*

为了提高大数据流滞后相关性序列挖掘效率,提出基于改进布尔约减级数分层的大数据流滞后相关性挖掘方法。该方法根据原数据流两段序列的序列均值对大数据流序列进行布尔变换,有效降低布尔约减计算开销。通过序列元素转换及还原,缩减序列元素的数目,克服传统算法在滞后相关性计算时需要计算所有数据流序列元素之间滞后相关性的弊端。实验表明,文中方法可有效减少运算时间,在保证精度的同时提高运算效率。     

一种实时挖掘数据流近似频繁项的算法

数据流的无限性和流动性使得传统的频繁项挖掘算法难以适用.针对数据流的特点,提出了一种实时的挖掘数据流近似频繁项的算法.在允许的偏差范围内,新算法只需扫描一次数据项,使用的存储空间远远小于数据流的规模,能动态地挖掘数据流中的所有频繁项.将数据项存储到一种新的数据结构中,利用该数据结构可以快速地删除非频繁项.最后,理论分析和实验表明这种方法的有效性.     

基于概率模型的数据流预测查询算法

挖掘在线数据流的变化趋势并预测未来时间窗口上的可能值,可以为许多时间敏感的应用提供重要决策支持.通过将数量可能无限的流数据元素映射到离散的且数量有限的流数据状态空间,不断变化的流数据变化趋势可以模拟成连续的流数据状态变化的过程,进而在很小的时间与空间代价下,数据流状态变迁的趋势动态存储在状态变迁图中.通过分析状态变迁图中的流数据变迁的统计规律,数据流上未来时刻的可能值可以应用马尔可夫模型在线连续预测.     

面向数据流的多粒度时变分形维数计算

在大数据时代,数据流是一种常见的数据模型,具有有序、海量、时变等特点.分形是许多复杂系统的重要特征,分形维数是度量系统分形特征的重要指标量.数据流作为动态的复杂系统,其上的分形维数应具有动态、时变、多粒度等特性.提出了多粒度时变分形维数的概念,并设计了基于小波变换技术的数据流多粒度时变分形维数算法.该算法通过对数据流进行离散小波变换,并利用多粒度小波变换树结构在内存中保存数据流的概要信息,可以同时在不同的时间粒度上实时地计算数据流时变分形维数.该方法具有较低的计算复杂度,实验结果表明:该方法可以有效地监控数据流分形维数在不同粒度上的时变特征,深刻地揭示数据流的演化规律.