关键词： 遗传算法   约束满足   排课问题  

摘要： 排课问题是一个有约束、多目标的组合优化问题,并且已经被证明是一个NP完全问题。针对高校排课过程中存在诸多约束因素的问题,提出将遗传算法与约束条件算法相结合的排课算法,由约束条件算法确定排课任务的优先次序,遗传算法解决单个排课任务时间片分配的优化问题。实验结果表明,该算法能够改进算法性能,提高排课效率。

关键词： Disjoint triangular decomposition   Simple systems   Polynomial systems   Differential systems   Involutivity  

摘要： In this paper, we consider systems of algebraic and non-linear partial differential equations and inequations. We decompose these systems into so-called simple subsystems and thereby partition the set of solutions. For algebraic systems, simplicity means triangularity, square-freeness and non-vanishing initials. Differential simplicity extends algebraic simplicity with involutivity. We build upon the constructive ideas of J. M. Thomas and develop them into a new algorithm for disjoint decomposition. The present paper is a revised version of Bachler et al. (2010) and includes the proofs of correctness and termination of our decomposition algorithm. In addition, we illustrate the algorithm with further instructive examples and describe its Maple implementation together with an experimental comparison to some other triangular decomposition algorithms. (C) 2011 Elsevier Ltd. All rights reserved.

关键词： 指纹识别预处理   数学形态学   细化  

摘要： 重点研究了二值化后指纹图像细化算法.首先简介了改进的OPTA细化算法.在总结上述算法的优缺点基础上,提出更有效的基于数学形态学的查表细化算法.实验表明后一种细化算法效率更高、处理后几乎没有毛刺、效果更理想,为后续的工作奠定了良好的基础.所进行的算法高效化研究对于提升识别的准确度具有非常明显的积极作用,在论文的最后通过实证手段进行了证明.同时,该文最后采用Visual C++编程实现指纹图像预处理过程中的所有算法,算法效率较高,从实际需求角度为我国的指纹图像识别的细化处理提供了必要的理论依据,实践证明,该文所研究的数学形态学视角下的指纹图像细化算法高效研究具有一定的现实意义,应用于指纹图像识别工作中将会取得较好的效果.

关键词： 时序优化   假设后验证   位并行随机模拟   寄存器共享   推测化简模型  

摘要： 为了在时序逻辑综合中使电路面积和关键路径延迟同时得到快速优化,提出一种改进的基于假设后验证的时序优化算法.在位并行随机模拟提取候选属性不变量之前,利用寄存器共享来降低初始候选不变量数目,以减少SAT程序的频繁调用;然后利用推测化简模型和改进的数学归纳法将基本条件和归纳步骤合并处理,有效地降低了电路规模和关键路径延迟,同时提高了算法运行速度.实验数据表明,文中算法使寄存器和节点规模平均下降41%和48%,关键路径延迟减小30%;与同类方法相比,该算法运行时间平均下降17%.

关键词： 学习算法   数学课程   普通高中   人民教育出版社   解析   实验教科书   高中数学   课程标准  

摘要： 在普通高中数学新课程中，算法是首次引入的新内容，很多教师在此之前没有接触过这部分内容．面对算法，有些教师存在畏难心理．为此，教师需要认真钻研教材，加深对算法知识的理解．此外，教师还需要考虑如何引导学生学习算法，这就涉及到PCK（Pedagogical ContentKnowledge）．下面以人民教育出版社《普通高中课程标准实验教科书数学必修3》（A版）为例，来剖析“算法概念”的PCK内涵，以望为教师提供教学参考．

关键词： Lot streaming   Hybrid flexible flowshop   Genetic algorithm   Parallel computing  

摘要： Lot streaming is the technique of splitting a given job into sublots to allow the overlapping of successive operations in multi-stage manufacturing systems thereby reducing production makespan. Several research articles appeared in literature to solve this problem and most of these studies are limited to pure flowshop environments where there is only a single machine in each stage. On the other hand, because of the applicability of hybrid flowshops in different manufacturing settings, the scheduling of these types of shops is also extensively studied by several authors. However, the issue of lot streaming in hybrid flowshop environment is not well studied. In this paper, we aim to contribute in bridging the gap between the research efforts in flowshop lot streaming and hybrid flowshop scheduling. We propose a mathematical model and a genetic algorithm for the lot streaming problem of several jobs in multi-stage flowshops where at each stage there are unrelated parallel machines. The jobs may skip some of the stages, and therefore, the considered system is a complex generalized flowshop. The proposed genetic algorithm is executed on both sequential and parallel computing platforms. Numerical examples showed that the parallel implementation greatly improved the computational performance of the developed heuristic.

关键词： Combinatories on words   partial words   pattern avoidance   subword complexity   algorithms  

摘要： Algorithmic combinatorics on partial words, or sequences of symbols over a finite alphabet that may have some do-not-know symbols or holes, has been developing in the past few years. Applications can be found;for instance, in molecular biology for the sequencing and analysis of DNA, in bio-inspired computing where partial words have been considered for identifying good encodings for DNA computations, and in data compression. In this paper, we focus on two areas of algorithmic combinatorics on partial words, namely, pattern avoidance and subword complexity. We discuss recent contributions as well as a number of open problems. In relation to pattern avoidance, we classify all binary patterns with respect to partial word avoidability, we classify all unary patterns with respect to hole sparsity, and we discuss avoiding abelian powers in partial words. In relation to subword complexity, we generate and count minimal Sturmian partial words, we construct de Bruijn partial words, and we construct partial words with subword complexities not achievable by full words (those without holes).

关键词： Dense linear algebra libraries   Graphics processors   Runtime systems   High performance computing  

摘要： Parallel accelerators are playing an increasingly important role in scientific computing. However, it is perceived that their weakness nowadays is their reduced "programmability" in comparison with traditional general-purpose CPUs. For the domain of dense linear algebra, we demonstrate that this is not necessarily the case. We show how the libflame library carefully layers routines and abstracts details related to storage and computation, so that extending it to take advantage of multiple accelerators is achievable without introducing platform specific complexity into the library code base. We focus on the experience of the library developer as he develops a library routine for a new operation, reduction of a generalized Hermitian positive definite eigenvalue problem to a standard Hermitian form, and configures the library to target a multi-GPU platform. It becomes obvious that the library developer does not need to know about the parallelization or the details of the multi-accelerator platform. Excellent performance on a system with four NVIDIA Tesla C2050 GPUs is reported. This makes libflame the first library to be released that incorporates multi-GPU functionality for dense matrix computations, setting a new standard for performance. (C) 2011 Elsevier Inc. All rights reserved.

关键词： Host mobility   network mobility   quality of service   delay-sensitive algorithm   mobile networks  

摘要： The mobile networks play a vital role in the information and communication technology. There are two kinds of mobility supported by mobile networks such as host mobility and network mobility. The enhancement of Quality of Service (QoS) in NEtwork MObility (NEMO) environment is more complex than host mobility environment. One of the complexities in NEMO environment is routing of packets. The routing algorithms play a significant role in enhancing QoS. This necessitates looking into the weaknesses of existing routing algorithms. Based on the weaknesses, we have already proposed a Delay-Sensitive Routing for NEMO (DSRNEMO) to enhance the QoS in NEMO environment with respect to delay parameter. The objectives of this paper are to derive a mathematical model for DSRNEMO and to simulate the operations of DSRNEMO. The outcome of the mathematical model and simulation results show that the DSRNEMO gives better results than the existing algorithm, NEMO. Ultimately, this paper contributes to enhance the QoS in mobile networks.