Computing in Finite Time

If a message can have n different values and all values are equally probable, then the entropy of the message is log(n). In the present paper, we discuss the expectation value of the entropy, for an arbitrary probability distribution. We introduce a mixture of all possible probability distributions. We assume that the mixing function is uniform

Computing the Cover Array in Linear Time

Abstract. Let x denote a given nonempty string of length n = |x| . A proper substring u of x is a proper cover of x if and only if every position of x lies within an occurrence of u within x . This paper introduces an array γ = γ[1..n] called the cover array in which each element γ[i] , 1 ≤ i ≤ n , is the length of the longest proper cover of x[1..i] or zero if no such cover exists. In fact it turns out that γ describes all the covers of every prefix of x . Several interesting properties of γ are established, and a simple algorithm is presented that computes γ on-line in Θ(n) time using Θ(n) additional space. Thus the new algorithm computes for all prefixes of x information that previous cover algorithms could compute only for x itself, and does so with no increase in space or time complexity.     

Computing the Cover Array in Linear Time

Let x denote a given nonempty string of length n = |x| . A proper substring u of x is a proper cover of x if and only if every position of x lies within an occurrence of u within x . This paper introduces an array γ = γ[1..n] called the cover array in which each element γ[i] , 1 ≤ i ≤ n , is the length of the longest proper cover of x[1..i] or zero if no such cover exists. In fact it turns out that γ describes all the covers of every prefix of x . Several interesting properties of γ are established, and a simple algorithm is presented that computes γ on-line in Θ(n) time using Θ(n) additional space. Thus the new algorithm computes for all prefixes of x information that previous cover algorithms could compute only for x itself, and does so with no increase in space or time complexity.     

组合时间模式与贪婪准则的排课方法

排课问题是一个具有多因素的优化决策问题,是组合规划中的典型问题,属于NP完全类问题。为了能够有效地抑制排课中的"组合爆炸"现象,提高排课速度,根据高校课表的特点,本文针对周课时的离散化分布提出了时间模式概念,设计了时间贪婪准则和教室贪婪准则。测试结果表明,本文算法不但能简化排课过程,提高排课效率,同时也提高了排课的满意度。     

Restrictions of Minimum Spanner Problems

At-spanner of a graphGis a spanning subgraphHsuch that the distance between any two vertices inHis at mostttimes their distance inG. Spanners arise in the context of approximating the original graph with a sparse subgraph (Peleg, D., and Schäffer, A. A. (1989),J. Graph. Theory13(1), 99–116). The MINIMUMt-SPANNER problem seeks to find at-spanner with the minimum number of edges for the given graph. In this paper, we completely settle the complexity status of this problem for various values oft, on chordal graphs, split graphs, bipartite graphs and convex bipartite graphs. Our results settle an open question raised by L. Cai (1994,Discrete Appl. Math.48, 187–194) and also greatly simplify some of the proofs presented by Cai and by L. Cai and M. Keil (1994,Networks24, 233–249). We also give a factor 2 approximation algorithm for the MINIMUM 2-SPANNER problem on interval graphs. Finally, we provide approximation algorithms for the bandwidth minimization problem on convex bipartite graphs and split graphs using the notion of tree spanners.     

无线网络拓扑控制中支撑图构造算法

支撑图(spanner)在无线(自主、传感器)网络拓扑控制中起着重要作用,不但能保证最终的拓扑图链路减少,保持连通性,而且保证任意一对通信节点之间所需费用是最少可能费用的常数因子倍.针对无线网络拓扑控制问题,大量支撑图构造算法被提出,以尽可能高效地满足网络设计需要的各种拓扑特性,如局部性、稀疏性、小权值、有界度及容错性等.对支撑图的研究成果进行了详细讨论,依据支撑图的定义和不同的分类原则给出了支撑图分类,分析了各种支撑图的典型集中式和局部算法、满足某一或多个拓扑特性的算法,并提出了需要进一步研究的问题.与无线网络中新出现、更实用的模型结合,寻找更简单、性能更好的算法将是未来支撑图构造算法的主要研究方向.     

移动计算环境中数据广播访问时间优化算法

移动计算是近年来新兴的一个研究热点，具有极大的市场潜力和需求，数据广播是提高移动计算系统可伸缩性的一项重要技术，本文对无线移动计算环境中数据广播的平均访问时间优化进行了研究和实验，首先分析了平均访问时间的理论最小值，然后提出了向理论最小值逼近的NASA 算法，实验表明NASA算法具有良好的性能，优于MDS等其他调度方法。     

基于GPU实现叠前时间偏移走时计算的并行算法

走时计算是叠前时间偏移计算中最耗时的部分,通过分析传统的串行走时算法,发现静态8点插值算法非常适合在GPU上运行。首先利用CUDA技术对静态8点插值算法进行并行化改造,设计静态8点并行插值算法,然后测试其正确性,统计其相对误差情况。实验表明此算法比工业生产上的动态插值算法更准确,最后我们利用体偏作性能测试。试验结果表明,运行在GPU上的静态8点并行插值算法内核性能是运行在CPU上的动态插值算法内核的22．76倍。这说明,静态8点并行插值算法适合进行走时计算,并且可以应用于工业生产上。     

Optimal Spot-checking for Computation Time Minimization in Volunteer Computing

This paper proposes an optimization technique for spot-checking to minimize the computation time in volunteer computing (VC) systems with non-reliable participants. Credibility-based voting with spot-checking is a promising approach to the high-performance and reliable VC systems. In this approach, spot-check rate has a significant impact on the performance, which must be set before the computation. Therefore, the estimation of the optimal spot-check rate is the major concern to minimize the computation time. The key idea for the estimation is to represent the mathematical expectation of the computation time as a function of spot-check rate. Extensive simulation has shown that the proposed technique always obtains an approximate estimate of the optimal spot-check rate and minimizes the computation time with an uncertainty of 1%.     

网格计算中费用约束的最优时间调度算法

在网格资源处理速度和资源价格异构的网格环境下,讨论基于用户费用约束的最优时间调度问题,提出一种相应的调度算法,将该任务调度问题转化为线性规划问题,采用单纯形算法获得近似最优解,从而获得费用约束下资源的最优执行时间以及该任务的最小完成时间。仿真结果表明,该算法的性能优于其他同类算法。     

分布式实时计算系统的一种调试方法

利用DRTDebug的设计和调度原理，提出分布式实时计算中的不确定性等问题的解决方法，并得到分布式实时程序运行信息的收集模型。     

并行计算时间模型研究

本文系统地总结和探讨了共享和分布式存储环境下的并行计算时间模型。微观上，结合并行机结构特征和通信机制，揭示了延长算法运行时间的关键因素，并据此提出一些优化原则和效率评价准则，能辅助用户修改并行算法达到最优性能；宏观上，给出了基本消息传递的常用通信原语类型和部分原语操作时间经验公式，能辅助用户选择最优通信原语和问题粒度，正确预测程序的运行时间和性能。     

异构计算中的时间和能耗优化执行方法

计算环境的异构性以及应用任务的复杂多样性导致异构计算的必要性.异构计算的目的是重视并行处理系统和计算任务的差异,寻求系统和任务的有效匹配,从而获得并行任务在系统上执行的最佳效果.当前,异构计算中的时间优化执行方法较成熟,但同时将时间和能耗联合起来作为异构计算优化执行目标方面的研究很少.以高性能计算和绿色计算为总目标,针...     

异构计算中的时间和能耗优化执行方法

计算环境的异构性以及应用任务的复杂多样性导致异构计算的必要性。异构计算的目的是重视并行处理系 统和计算任务的差异,寻求系统和任务的有效匹配,从而获得并行任务在系统上执行的最佳效果。当前,异构计算中 的时间优化执行方法较成熟,但同时将时间和能耗联合起来作为异构计算优化执行目标方面的研究很少。以高性能 计算和绿色计算为总目标,针对异构计算环境中并行任务分配调度执行问题,提出了异构任务模型、异构计算速率矩 阵、异构计算功率矩阵,利用能耗时间归一思想,给出并行任务在异构处理机上时间与能耗启发式优化执行算法,并通 过实例分析证实算法的可行性和有效性。     

贪心算法在医院信息系统中的应用

贪心算法是很常见的算法，贪心策略是最接近人的日常思维的一种解题策略。本文具体分析了医院信息系统中药品发放问题所具备的贪心选择与最优子结构性质，并给出了采用贪心算法解决药品发放问题的具体代码。     

求解简单多边形间最小距离的一个线性时间算法

计算简单多边形间的最小距离,在所有与几何图形计算有关的领域中,一直以来都是一个基本问题。为了更快地求解简单多边形的最小距离,提出了一个基于关联多边形三角化分割的简单多边形间最小距离的求解算法。该算法的主要思想是:首先构造一个关联多边形把两个多边形联系起来,其目的是把最小距离限制在这个关联多边形内;然后根据两个多边形的最小边界矩形包围框间的不同位置关系,详细阐述了关联多边形的构造过程,同时论述了关联多边形是一个简单多边形。为了计算最小距离,首先要对关联多边形进行三角化分割,并使最小距离位于三角化分割结果中某一个三角形区域内,或者至多位于两个相邻三角形区域内;之后通过对所有三角形进行遍历来找出最小距离及其所在的位置。该算法的时间复杂度是线性的。     

贪婪缺省逻辑

提出一种贪婪缺省逻辑,旨在构造扩展的过程中尽可能的保留缺省规则当中的信息.给出了贪婪缺省逻辑的推演系统-GD系统和贪婪缺省的GD-扩展的定义.并且证明了对于缺省理论 的一个扩展,必定存在一个贪婪缺省理论的GD-扩展使得缺省逻辑的扩展是贪婪缺省逻辑扩展的子集.并且存在贪婪缺省理论 的某一GD-扩展,该GD-扩展不包含缺省理论的任一扩展.因此缺省逻辑和贪婪缺省逻辑是两种不同的逻辑.     

Is Cloud Computing Really Ready for Prime Time?

Even though the technology faces several significant challenges, many vendors and industry observers predict a bright future for cloud computing.