二元序列的赋权对换排序问题

提出了对换排序的赋权模型，定义一个长度为l的对换的费用是f(l)=l^α,α＞0；分别给出了当0＜α＜1和1＜α＜2时，二元序列赋权对换排序问题的近似算法；证明了当α≥2时，起泡排序算法是此问题的精确算法.     

二元序列的翻转与对换排序

序列的翻转与对换的排序问题因在基因组比较中的应用而受到关注．考虑二元序列的翻转与对换的排序问题，分别给出了二元序列的翻转排序与对换排序的近似算法．     

多人评判的不可能性

赋权评判法运用于实际问题时,往往遇到多人评判(或称群组评判)的情况,即先由个人按一定要求对指标集合中每一指标赋权,权值属于[0,l],通常令l=1.然后按一定法则综合各个评判者所赋的权,得出指标的综合排序,本文主要讨论了不可能存在综合个人“赋权”的函数,这是在引进信息可比性后(即考虑了各评判者对同一指标赋权大小这个因素),在更普遍的意义上证明了不可能性.     

基于对换门库的可逆逻辑电路综合算法

为了将可逆函数以较小的代价自动构造为对应的可逆逻辑电路,提出了一种基于对换门库的综合算法.首先,将可逆函数的输出作为快速排序算法的输入数据,在排序算法中按顺序保留所交换的元素对,并输出该元素对序列；其次,利用置换群规则对该序列进行优化处理,获得相似度最高的对换序列；然后,逆序排列该对换序列,并基于对换门库生成可逆函数的初始电路；最后,应用电路门优化规则,对初始电路进行优化,得到最终的可逆逻辑电路.相比于其他算法,所提算法明显提高了可逆逻辑综合效率,其思想的简洁性使得算法更易于理解和实现.     

任务长度可变的多机排序问题

把由Czumaj等人提出的用于网络信息搜索的任务长度可变的排列问题推广到任务长度可变的多机排序问题,证明该问题的判定形式是NP困难的,而且对任务最大完成数目的优化形式给出了一个近似比α小于4的近似算法．     

度分布为正态分布的复杂网络度序列长度的研究与分析

度分布是复杂网络模型的重要特征.针对度分布符合指数分布、幂律分布和扩展幂律分布的复杂网络模型,笔者所在课题组前期的研究结果表明节点度序列(1≤k_1k_2…k_l)长度l是log_2N级别的(N为网络节点数);在前期研究所得结论的基础上,文中针对度分布符合正态分布的复杂网络模型,从理论的角度证明了度序列长度l也是log2N级别的;并选取ER随机网络进行仿真实验,仿真实验表明,度序列的长度是级别的;最后对大量的现实网络模型进行了验证,结果表明现实网络的度序列长度l也是与log_2N同一级别.     

快速排序的改进算法

对快速排序算法进行了改进,根据在待排序列基本有序的情况下,插入排序有较好的性能特点,在改进算法中,只对长度k大于的子序列递归调用快速排序,最后再对整个序列用插入排序方法排序,我们得到了时间复杂性为1.386 nlog(n/k) nk/4 3(n 1)/(k 1) O(logn)的排序算法,当k取值为8左右时,改进算法的性能较隹.     

排序和时间表理论的进展

本文对排序和时间表理论给出了四种参数的分类标准。这四个参数为:工件个数,记为n;机器个数,记为m;多台机器(m>1)的排序问题的不同类型,记为l;最优性指标以k表示。此外,排序问题还可能有约束条件,记为λ,因此我们可用符号n|m|l,λ|k表示一个排序问题。参数和约束条件各种不同的组合就构成了不同类型的排序问题.指出研究排序问题的复杂性是排序问题的基本课题之一.文中对决定性的几种重要类型的排序问题所取得的成果进行了概述.     

有限域上方程α~2x+αtr_(e_1)~n(αx)+x+tr_(e_2)~n(x)=0的研究

低相关二元序列集在CDMA通信系统中有着重要的应用,由有限域上函数定义的序列集中的两条序列的相关值与有限域上方程的解数有关.设3个正整数e_1,e_2和n满足e_1|n,e_2|e_1,α∈F_2 n,研究方程α~2x+αtr_(e_1)~n(αx)+x+tr_(e_2)~n(x)=0在域F2 n上的解数.当e_1=e_2时,此方程的解数已被用于构造低相关二元序列集,本文中提出一种当e_1≠e_2时构造低相关二元序列集的方法.新序列集的数目很大,且相关值较低.     

有重叠的两抓钩周期性排序问题的启发式算法

抓钩排序问题不同于古典的排序问题,只有一个抓钩和一种产品,它仍然被证明为ＮＰ难题,对于有重叠区域的两抓钩周期性排序问题,迄今尚无法用数学模型直接求解。为了寻找出好的排序,提出了一种启发式算法以及求解有重叠两抓钩周期性排序问题。该方法把问题分解成相应序列的子问题,并对每个序列化建立和求解一个整体问题的线性规划模型,在序列空间中,通过寻找好的序列以得到最佳的排序。量化的示例表明所使用的方法是高效的。     

基于遗传算法的粉煤灰高性能混凝土配合比优化设计

采用遗传算法对粉煤灰高性能混凝土进行配合比优化设计,以经济成本为目标函数、以满足粉煤灰高性能混凝土各项性能指标为约束条件建立适应遗传算法的数学模型,用二进制编码表示个体的染色体位串,通过选择、交叉、变异等遗传算子作用进行全局性概率搜索,以优胜劣汰为原则,最终达到最优的群体和个体.将优化结果和工程实例的配合比进行对比,可见该方法可降低造价、节约能源,具有较好的工程使用价值.     

改进遗传算法及其在谷氨酸发酵过程建模中的应用

针对谷氨酸发酵过程建模中变量取值范围扩大时,二进制遗传算法存在收敛速度和精度的矛盾,研究了改进的浮点遗传算法．仿真结果表明：该改进算法能克服二进制遗传算法的缺点,不仅在收敛精度和速度上都有明显的改进,且效率很高．具有工程实际应用前景．     

一种快速近似模式匹配算法

为进一步提升传统的近似模式匹配问题解决方法——动态规划算法的性能,提出了一种新的过滤型近似模式匹配算法.该算法结合动态规划算法,切分模式串得到长度相等且更小的模式片;在此基础上将待匹配的文本串分割成子串,并建立相应的索引;同时设计了一个新的过滤策略来消除匹配检查中的冗余.通过实例将文中方法与现有方法进行对比,结果表明:文中方法的匹配时间较短,匹配性能优于现有方法;随着模式串长度的增加,文中算法的优越性更为明显,模式串长度大于45后,文中算法的匹配时间可比传统动态规划算法缩短一半以上.     

气体钻井中钻柱力学性能及冲蚀实验研究

由于在破岩过程中受到冲击,气体钻井中的钻柱产生了交变应力,而钻柱旋转加剧了交变应力的变化,同时气体携带岩屑对钻柱产生冲蚀,加速了钻柱的失效。钻柱主要失效形式为疲劳断裂,这跟钻柱所受应力大小及变化密不可分,因此,开展气体钻井过程中钻柱力学性能和冲蚀研究,掌握钻柱应力变化规律及岩屑对钻柱的冲蚀规律,是减小和防止钻柱失效的基础工作,对增加气体钻井过程中的安全性和降低钻井成本有十分重要的意义。通过使用一种已开发出的可同时模拟气体钻井钻具振动和冲蚀的装置,进行了不同钻具组合情况下,气体钻井钻柱同时受振动和冲蚀实验。实验结果表明,气体钻井过程中,配置扶正器将使钻柱所受交变应力值变化范围降低40% 以上,扶正器和减振器的配合使用将使交变应力值变化范围下降50%,因此,扶正器和减振器的配合使用,将大幅降低钻柱所受交变应力,并延长交变应力作用周期,从而降低钻柱失效的概率。     

曹妃甸油田浅层大位移井管柱作业极限分析与优化设计

在浅层大位移钻井中,井下管柱上产生高摩阻扭矩,管柱作业极限问题突出,急需开展大位移井管柱作业极限分析与优化设计的研究。基于管柱平衡微分方程,综合考虑接触力、摩阻力、管柱内外钻井液等因素影响,建立管柱摩阻扭矩计算模型;以井眼延伸长度为目标,考虑地面和井下各种约束因素的影响,建立管柱作业极限的预测模型。针对曹妃甸油田一口浅层大位移井,计算不同工况下管柱摩阻扭矩,预测管柱作业极限,并提出优化设计方案。结果表明,采用滑动钻进技术无法达到设计井深,采用旋转钻进技术可达到设计井深,但存在一定的风险。提升钻机性能后,采用旋转钻进技术可安全达到设计井深;优化井身结构后,采用滑动钻进技术并辅以减摩措施可达到设计井深。     

一种带有长度和位置约束的字符串索引方法

提出了一种基于BWT(Burrows-wheeler-transform)的字符串集合的索引方法,以解决带有匹配字符串长度和匹配子串位置约束的子串确切匹配查找问题.讨论了BWT和基于BWT索引进行确切子串查找的基本原理.分析了字符串集合、匹配字符串长度和匹配子串位置约束对原BWT索引的影响.重点解决了快速地从匹配后缀位置到字符串ID和匹配子串位置的计算问题.在3个真实的数据集上进行了比对实验,结果表明:所提出的基于BWT索引方法在没有增加原索引大小的情况下,大大提升了带有匹配字符串长度和匹配位置约束的确切子串的查找的性能,因此该算法更加适用于大规模的字符串集合的索引进行近似字符串匹配和连接.     

一般上下文无关文法的一个分析算法

本文给出一般上下文无关文法的一个分析算法。该算法可以看成是LR分析算法的推广,它既是自底向上,又是从左到右。理论分析表明本算法对一般文法具有时间界O(n~3)这里n是输入句子的长度);对有界歧义文法时间界为O(n~2),而对LR文法时间界为O(n)。由于本算法是先将文法转换成分析表,然后用分析表来指导对句子的分析。因而在实际应用中本算法一般要比Earley算法快,另外本算法输出中包含输入句子的所有可能的分析,并且仅需一简单枚举就可从此输出中找出句子的一个分析。     

一类极大算子与Cp权的关系

设Ｍｆ（ｘ，ｔ）＝ｓｕｐ１／Ｑ∫Ｑ（ｆ（ｙ）／ｄｙ，其中Ｑ为Ｒ＾ｎ中的方体，ｌ（Ｑ）为Ｑ的边长，本文考虑如上定义的极大算子与Ｃｐ权对的关系。     

液-固两相系中超声层析成像实验研究

基于几何声学原理,应用半柱面晶片超声换能器发射扇形束超声波,设计了环形超声换能器阵列,搭建了多通道同步数据采集系统,形成了一套透射式超声层析成像测试装置.研究了二值逻辑反投影图像重建算法,此算法和测试装置构成了透射式超声层析成像系统,对聚四氟乙烯隔板和圆柱体进行实验.图像重建结果表明,该系统能够定位成像物体的位置,确定其大小和形状.将单个圆柱体二值反投影算法的重建图像与设定值比较,成像误差小于6%.