基于树状数组的逆序数计算方法

n个元素组成的置换a[1],a[2],…,a[n].若i＜j且a[i]＞a[j],则称(a[i],a[j])是一个逆序对.置换中逆序对的个数称为置换的逆序数.按定义,计算逆序数要通过n(n-1)/2此次比较,时间复杂度是O(n2).设计了一种新的方法,利用树状数组计算逆序数,时间复杂度降为O(nlog2(n)).主要思...     

全组合式键盘电路构造方法

在分析现有键盘电路的基础上，提出了一种全组合式键盘电路构造方法．这种键盘根据排列组合原理，用n条双向I／O口，最多可以实现2^n-1 n(2^n-1-1)个按键，数量远大于传统矩阵式键盘电路，而且可根据实际需要用其部分电路构成多种实用键盘电路。     

线性0—1规划模型的排序解法

针对0－1规划模型提出了一种新的解法,即排序法。它利用目标函数变量系数绝对值大小的相对关系,对无约束条件解进行排序,在最小解集中寻找最优解,以加快收敛速度。     

基于多点线圈联合数据的高速公路匝道影响范围识别

为准确识别高速公路匝道对主线车流的影响等级和范围，本文提出基于速度波动特性的高速公路匝道影响量化方法。通过建立改进加权速度排列熵指标以量化各服务水平下匝道对高速公路主线车流的影响，对建立的指标进行谱聚类分析来确定匝道的影响阈值。应用京昆高速及二广高速的99个平行式合流匝道和直接式分流匝道多点主线线圈检测器数据的分析结果表 明，所提出方法可识别高速公路主线车流受匝道的影响程度。合流匝道对主线最外侧车道的影响比次外侧车道高4%~69%；A~C级服务水平下，分流匝道对上游主线最外侧车道影响程度比次 外侧车道高6%~29%，D~F级服务水平下，最外侧车道受影响程度比次外侧车道低10%~13%。合流匝道的影响范围是合流点上游350m至下游550m；其中上游160m至下游100m和下游180~ 270m为核心影响范围。分流匝道影响范围为分流点至主线上游850m，其中750~850m、450~ 600m、100~300m为核心影响范围。研究成果可为高速公路匝道交通设计、管控策略和提升仿真可靠性提供依据，可有效降低设置匝道带来的影响。     

Improved Parallel Three-List Algorithm for the Knapsack Problem without Memory Conflicts

Based on the two-list algorithm and the parallel three-list algorithm, an improved parallel three-list algorithm for knapsack problem is proposed, in which the method of divide and conquer, and parallel merging without memory conflicts are adopted. To find a solution for the n-element knapsack problem, the proposed algorithm needs O（2^3n/8） time when O（2^3n/8） shared memory units and O（2^n/4） processors are available. The comparisons between the proposed algorithm and 10 existing algorithms show that the improved parallel three-fist algorithm is the first exclusive-read exclusive-write （EREW） parallel algorithm that can solve the knapsack instances in less than O（2^n/2） time when the available hardware resource is smaller than O（2^n/2） , and hence is an improved result over the past researches.     

An Optimal Parallel Algorithm for the Knapsack Problem Based on EREW

IntroductionGivenn positiveintegersW =(w1,w2 ,… ,wn)andapositiveintegerM ,theknapsack problem (alsocalledthesubsetsum problembysomeauthors)isthedecisionproblemoffindingasetI {1 ,2 ,… ,n},suchthat∑i∈I=M ,i∈I .ThisproblemwasprovedtobeNP complete[1] ;i     

奇数阶完全图的因子分解与对称群

F．Harary在[1]中提出如下一个未解决问题：那些有限置换群是完全图同构分解的因子对称群？对于n〉1。构造了2n＋1阶完全图G的／7,个不同的同构分解G^e=G1∪G2∪…∪Gn,其中G1是2n个点的路的第e对对称点和另1个点连接得到的图。证明了G的同构分解的因子对称群是n阶循环群。     

用置换群解决信息加密问题的探索

提出了用置换群来解决信息加密问题的观点 ;并对用置换群进行加密、解密算法进行了论证 ,对加密密钥和解密密钥作了一些说明 ;同时提出了用置换群解决信息加密问题时可能存在的一些问题 .     

完全图的路分解与因子对称群

F.Harary在[1]中提出如下一个未解决问题:那些有限置换群是完全图同构分解的因子对称群?本文证明了偶数阶完全图的路分解的因子对称群是循环群.     

关于连续正整数Diophantine方程的正整数解

连续正整数Diophantine方程xn+(x+1)n+…+(x+h)n=(x+h+1)n的正整数解问题,是一个迄今为止尚未彻底解决的数论难题。目前已知的结果是:①当6≤n≤33时;②当n>3且为奇数时;③当34≤n≤200且为偶数时,该方程均无正整数解。采用多种素数模筛法证明了:当200相似文献   

运输问题原设－对偶算法的一个改进

本文对运输问题的原设－对偶算法运用推拉流思想进行改进,得到一个拟多项式时间算法。该算法使用的数据结构简单,运行时间界为Ｏ（Ｕ＿ｎ（ｍ＋ｎ）￣３）,其中ｍ为产地数目,ｎ为销地数口,Ｕ表示整体待运量。      

一类SPN结构密码设备的故障注入攻击技术

提出了一种有效的故障注入攻击技术,能够攻击一类使用特定结构SPN密码的设备．这种攻击方法基于字节错误模型,仅需要少量故障密文即可攻破一类具有特定置换层的SPN密码算法．分析给出了故障和特定置换层如何导致秘密信息泄露的原因．同时,对于具体的密码算法ARIA和PRESENT进行了攻击实例．     

MIMO双向中继网络的预编码设计与功控策略

为加强MIMO双向中继系统的空间复用增益,研究一种低复杂度的发送和接收预编码矩阵.利用子空间对齐方法,将双向MIMO信道分解为多路单入单出（SISO）的子信道形式,使得两个源用户能够使用网络编码获取更好的空间复用增益.同时通过矩阵计算和转化,给出了一种优化的功率分配方案.在确定优化矩阵后,该方案能够为每个子信道独立地进行优化功率分配,并且能够得到各节点间优化功率分配的闭合表达式,从而将算法复杂度从O（n3）降低为O（n）.仿真结果表明,在典型场景下,所提方案在具有更低复杂度的优势下,系统性能接近优化的梯度下降迭代方案,优于传统单纯前向放大转发方式（AF） ,有2.99 bit/（sHz）的性能增益.      

UET系统在m台处理机上的一种调度算法及其性能分析

本文介绍了一种UET系统中有效的调度算法,其时间复杂性函数为O(na(n)+e)。该算法对m=2台处理机的调度为最优,而对m≥3台处理机上的未确定调度子问题,其解与最优解之比的最小上界为2-2/m,它也是一个近似程度相当好的有效算法。     

Braess悖论及其对偶形式的博弈论分析

用博弈论的基本原理来分析Braess悖论及其对偶形式,提出了一种更直接更简洁的建模方法.首次提出了Braess悖论的对偶形式,通过建立Braess悖论的非合作博弈模型,可以得知:在车流量一定的情况下,增加路段有可能使路网中通行时间增加.同样,通过建立Braess悖论对偶形式的非合作博弈模型可知:在路网不变的情况下,增加车流量有可能使路网中通行时间减少,并详细分析了这种现象的特征及原因,提出了解决措施.     

Batch secret sharing for secure multi-party computation in asynchronous network

This paper proposes an efficient batch secret sharing protocol among n players resilient to t < n/4 players in asynchronous network. The construction of our protocol is along the line of Hirt's protocol which works in synchronous model. Compared with the method of using secret share protocol m times to share m secrets, our protocol is quite efficient. The protocol can be used to improve the efficiency of secure multi-party computation (MPC) greatly in asynchronous network.     

航路时空资源分配的多目标优化方法

为了提高航空公司与空管方之间的协同决策程度, 降低航班延误水平, 以航路飞行的航班为研究对象, 研究了航路时空资源的多目标分配; 考虑实际运行条件下航班的唯一性约束、时间顺序约束和可行性约束的影响, 以航班在流量受限区所分配的飞行航迹和进入时隙为决策变量, 以航班总延误成本最小和航空公司延误公平损失偏差系数最小为目标函数, 构建了多目标非线性0-1整数规划模型; 基于模型特点引用了非支配排序遗传算法(NSGA-Ⅱ), 并利用排列编码法设计了一种整数基因编码方式, 以最大限度保证基因产生可行解集; 为了验证模型与算法的有效性, 基于南中国海地区航班运行实例, 对算法搜寻最优解的性能进行了研究, 并将此算法与传统按时刻表分配(RBS)方法进行了对比。研究结果表明: 改进编码方式的NSGA-Ⅱ算法使解集种群在约50代后世代距离从600收敛至30并稳定, 具有良好的收敛性; 针对实例中的多目标优化模型共生成有6组解的帕累托解集, 结果有66.7%的概率完全支配RBS方法, 且优化结果中航班平均延误成本比RBS方法降低了8.5%, 平均公平损失偏差系数降低了70.6%。可见提出的航路时空资源多目标优化方法的执行效果显著, 可在降低总延误成本的基础上兼顾各航空公司的公平性, 是解决航路飞行航班航迹与时隙资源分配问题的一种有效方法。      

树的两类m—路中心

本文提出图的顶点和边不相交的k—支配路数的概念。并就树的情形对项点和边不相交的k—支配路数分别给出O(n~2logn)算法。从而解决了树的项点和边不相交的m—路中心问题。本文还解决了[2]中的一个未决问题。     

A Polynomial Time Algorithm for Checking Regularity of Totally Normed Process Algebra

A polynomial algorithm for the regularity problem of weak and branching bisimilarity on totally normed process algebra(PA) processes is given. Its time complexity is O(n3+ mn), where n is the number of transition rules and m is the maximal length of the rules. The algorithm works for totally normed basic process algebra(BPA) as well as basic parallel process(BPP).