电路板布线问题的改进算法

本文针对电路板布线问题的动态规划解法进行了讨论,在给出一般常见的时间和空间复杂度均为o(n2)的算法描述后,进一步讨论了在时间和空间复杂度上都有显著提高的算法(其时间复杂度为o(n*log(k)),空间复杂度为o(n).     

N-体仿真中的分层树形算法

考虑两种情况：在3维空间中给出n个质点，计算每一粒子施加在其它粒子上的力，成对的相互作用可能有万有引力或者Lennard—Jones．上述两种情况的力，当两粒子间的距离达到无限大时消失．既然n个质点，两两相互作用共有[n(n—1)]／2对，直接算法对力的估算所需时间为0(n^2)．这对天文中的仿真所用时间是非常大的．该文提出了一种O(log n)算法，使用n／log n处理器CREW　PRAM来计算n体仿真中的场．这种最优并行算法的关键是利用一个相同的非递归自上而下的过程来代替一个递归的自上而下的计算过程．这种相似的算法对力场计算也产生了一个新的O(n)时间序列算法．     

基于Grover算法的量子多用户检测

经典的多用户检测技术，其求解最优解的时间复杂度为0(2n)，这是一个NP难解问题．在Pauli算子的基础上建立量子多用户信道模型，给出利用Grover算法的多用户检测解决方法．该算法的时间复杂度为O(√2n)，并且当2n足够大时，其错误的概率趋近于0．     

具有交货时间的单机作业调度问题的最优解

基于回溯思想的算法通过系统地搜索解空间可以得到具有交货时间的n个作业的单机作业调度问题的最优解.给出一种改进算法,使得算法的时间复杂度由O(n!)降低到O(nlgn).     

基于可靠率的改进的LDPC码BF译码算法

相对于低密度奇偶校验(LDPC)码置信传播(BP)译码o(n2)数量级的计算复杂度,比特翻转(BF)译码算法的计算复杂度只有o(n),然而其译码性能却有很大降级.为此,该文提出了一种改进的BF算法.该方法使用了可靠率来衡量所有参与同一校验的信息节点对校验没有满足的贡献,以较低的计算量增加为代价在译码中引入软信息的使用,从而使BF的性能有了较大提升.理论分析表明其复杂度为o(n),仿真结果表明,与加权的比特翻转译码算法比较,新算法在信噪比为7 dB时,误码率由10-3数量级改善为10-4.     

有限期作业调度问题的最优化算法

本文讨论了有限期作业调度问题,用计数排序、分离森林中的有效路径压缩、按秩合并方法,得到了有限期作业调度最优化算法,其时间复杂性为O(na(m,n)),m=O(n),在实际应用中是一个线性时间复杂性算法,是渐近性能最佳的算法.     

无平方因子的判定与算法

给出一个新的算法．算法可在O(log^4n)时间内判断给定整数n是否无平方因子,本算法在判断给定整数n是否无平方因子方面优于Kagal和Sanexa给出的算法。     

双机系统上的一个作业调度算法

本文在双机系统环境下对具有资源约束且执行时间为任意的独立作业提出了一个o(n~3)“几乎最优”的调度算法。在1≤T_(max)/T_(min)≤2时证明了其最坏性能边界小于3/2。     

一类基于顺序表的数据移动

研究了顺序表中一种数据移动L(m,n)介绍了几种实现L(m,n)的算法，并给出了实现L(m,n)的一个新算法。     

一类基于顺序表的数据移动

研究了顺序表中一种数据移动L(m.n)，介绍了几种实现L(m.n)的算法.并给出了实现L(m.n)的一个新算法。     

基于已知移动站点数的分布式初始化算法

初始化是建立一个Ad Hoc网络的基本任务之一，其涉及了分布式地为n个移动站点分配从1到n不同的ID，提出了用于初始化的一个具有载波侦听能力的Ad Hoc网络的算法，提出了一个在初始化过程中，通报一个处于传输状态的移动站点传输是否成功的新确认方案，叙述了在网络中用户数已知的假定条件下的分布式初始化算法，该算法通过优化关键参数以最小化完成初始化过程的时间，通过仿真验证，并与已知移动站点数随机初始化算法相比较，表明该算法优于随机初始化算法。     

改进的端到端实时CORBA调度模型可调度性分析算法

端到端实时CORBA系统调度模型的可调度性分析算法存在着一些缺陷和局限．针对其局限性，提出了改进的可调度性分析算法，采用时间需求分析方法，增加考虑了同一处理器上兄弟子任务对时间需求的影响，以及一个端到端任务在同一处理器上存在着2个以上子任务的情形。通过计算任务影响函数，分别推导出2类子任务的时间需求函数。新的可调度性分析算法不仅具有良好的通用性，而且提高了原有算法的判定能力。可适用于含有递归调用的实时CORBA任务集的可调度性分析和判定。     

并行加工的完工时间

 p台机器完成加工n项任务所需要的时间称为这n项任务的完工时间.首先引入一种参数,即膨胀系数,并设计出一种加工n项任务的算法,然后分别讨论n项任务全都平均分成p份或者全都不分时被p台机器按所设计算法加工的完工时间.     

容错模式下TTCAN系统矩阵的实时调度

TTCAN协议是一种CAN总线高层协议,在现行CAN协议的基础上引入了时间触发机制.由于消息组中的消息具有多样性,各个消息的周期可能相差很大.针对这一问题,采用最大公约数(GCD)方法来加以解决;利用遗传算法对调度表进行优化,提高了网络利用率,并且提高了事件触发任务的实时性能.对调度表的容错性能进行了分析,并提出了基于后面优先原则的仲裁窗方法.实验结果表明,该算法优化系统网络调度,保证了传输的实时性.     

保证轻轨司机双休日的"双齿轮"轮班模型及其均衡算法研究

分析了轻轨司乘人员的工作特点,日工作时间在6～10 h不等,早班从5时左右开始,晚班到夜里23时左右结束.根据轮班的目标函数和约束函数,作者提出了基于"双齿轮"的均衡轮班模型,推导出了均衡轮班的数学公式,在每人有n天休息、m天需要工作的循环轮班条件下,满足了n m个司乘人员在n m天内各自轮完n m个不同任务的要求,同时保证享有的n/2个双休日均匀地分布在各自的m个工作任务之间,通过系统仿真验证了轮班模型及其算法的正确性.     

基于多通道观测量精确定时的算法及实现

为了提高卫星导航系统中的定时精度,在研究利用伪距方程解算来获得钟差以进行接收机时间调整的传统定时方法的基础上,提出了利用多通道信息在最大似然准则下,进行最佳估计接收机时钟钟差的算法,并在时间调整过程中实现了闭环调整接收机秒脉冲(1 PPS)的输出.对算法及闭环调整方式在ARM FPGA的硬件平台上进行了初步实现,对算法的性能进行了仿真.仿真结果表明,最大似然估计算法对进一步提高卫星导航系统中的定时精度有明显的改善.针对开环和闭环调整两种情况,也进行了仿真分析,得出闭环调整能够有效克服接收机时钟向同一方向漂移的问题.     

网格中流水式计算的一种任务指派算法

为取得网格中流水式计算的高吞吐率,提出一种任务指派算法X max min.在一个流水线中,任务彼此是并行的,且每个任务本身是可并行化的.当多个任务被指派到同一个并行系统时,通过最小化任务计算成本的最大值确定每个任务分得处理机的个数.任务用于收发数据集的通信成本依赖其他任务的指派,故当相关任务的指派未完成时,需要在任务通信成本中引入均值估计.任务响应时间是计算成本和通信成本之和,它是任务指派的函数.用max min算法确定任务指派,可有效降低任务响应时间的最大值,从而使流水线的吞吐率得到提高.仿真实验表明,X max min算法使流水线取得的吞吐率与复杂的Taura算法相当.     

基于遗传算法PID控制器在张力控制中的应用

采用遗传算法进行PID参数的优化设计．根据控制任务的要求建立综合优化指标，在此基础上提出采用遗传算法进行PID参数优化的基本步骤，并具体以数字控制系统PID参数的优化为例进行了仿真计算．研究表明，对比传统的优化方法，遗传算法是一种十分有效的优化方法，遗传算法不要求优化对象的数学模型连续，而具有更宽的适用范围，同时遗传算法还具有较好的鲁棒性和稳定性．     

RM算法中减少抢占开销的任务微调算法

在基于嵌入式实时操作系统的实时应用中,由于任务抢占导致的切换开销对于整个系统是不可忽略的.提出了一种减少抢占发生的RM任务微调算法,通过对固定优先级调度抢占行为可推迟时间的量化分析,推导出受低优先级任务阻塞而造成的受阻任务集,以及在任意抢占时刻,推迟高优先级实时任务执行避免抢占发生的判定条件.仿真实验表明该算法在保证可调度任务集中所有任务满足时限约束的前提下,延迟高优先级任务的执行,减少抢占发生次数,通过减少抢占开销提高RM算法在实际应用中的可调度利用率.