关键词： 均衡约束数学规划   SQP算法   线性互补约束   非线性互补约束   S-稳定点   全局收敛   超线性收敛  

摘要： 均衡约束数学规划是近年来数学规划领域发展起来的一个热点研究问题.它起源于对策论,并且在经济分析、自然科学和工程计算中有着广泛地应用.然而,这类问题的研究却非常复杂,最主要的困难在于它的可行域的复杂性,一些常用的约束规范条件对均衡约束数学规划问题来说一般都不成立,从而非线性规划一些经典的理论和算法一般不能直接应用到均衡问题上来.因此,如何将该类问题进行转化,给出研究该类问题的等价形式,并研究其最优性条件和算法就变得非常重要. 本文主要做了以下两方面工作: 首先基于逐步逼近心想,构造一个与原问题等价的光滑非线性规划.借助降维思想,在每步迭代时,主方向由定义在Rn+m上的QP子问题和一个方程组求得.为了克服Maratos效应,我们通过求解一个线性方和组得到二阶修正方向.在不需要上层严格互补的适当假设条件下,证明了算法的全局收敛性和超线性收敛性.当算法有限步终止时,当前迭代点为原问题的一个精确稳定点.数值实验表明算法的有效性. 其次利用归并函数,提出一个新的磨光方法,基于该方法,构造一个在求解意义上与原问题等价的磨光非线性规划.在每次迭代时,只需构造仅含等式约束的QP子问题来产生主方向,再通过一个显式公式来产生修正方向以克服Maratos效应,从而避免求解另一个QP子问题.在一些适当的假设条件下,提出的SQP算法全局收敛到原问题的S-稳定点,且算法的收敛速率是超线性的.数值实验验证了算法的有效性.

关键词： 有限元法   遗传算法   神经网络  

摘要： 数学算法在工程领域方面非常重要。介绍有限单元法,遗传算法和神经网络的研究现状,描述它的主要特点,基本原理和应用领域。

关键词： ontology   algebra of algorithms   designing and synthesis of programs   parallel programs  

摘要： An approach to formalized development of parallel programs using ontologies and algebraalgorithmic facilities is proposed. Ontology gives opportunity to describe the skeleton of the program representing main objects in the given subject domain, i.e. data, functions to process data and relations between functions. Once the skeleton of the program has been built, further development can be done in automated manner with the Integrated toolkit for Design and Synthesis (IDS) developed by the authors, which is based on using algorithmic algebras facilities. The application of the approach is illustrated with an example of developing parallel MPI program in the subject domain of sorting algorithms.

关键词： 数学形态学   去噪算法   结构元素   Contourlet变换   并行化  

摘要： 图像去噪是图像处理中一种基本而重要的技术。图像在数字化的过程中不可避免地会引入一些噪声,这些噪声会妨碍人们对图像的理解,影响图像的质量。利用去噪技术可以从复杂的信号中提取出所需要的信号,并抑制干扰信号,使图像更加清晰,反映出的信息更准确。图像的清晰度主要决定于图像边缘、细线和小特征是否清晰,特征之间的区域变化是否平滑。传统的图像去噪方式,在去除噪声污染的同时会造成图像边缘的模糊,不能很好地保持轮廓信息。为了解决图像滤波时的轮廓保持问题,研究者们提出了一类新的非线性方法,即基于数学形态学的图像去噪方法。这种方法对图像形态特征进行分析,利用预先定义的结构元对信号进行匹配,以达到提取信号、抑制噪声的目的,具有并行性和快速性的特点,因而在国内外受到普遍关注。 本论文以数学形态学理论为基础,分别研究了二值图像、灰度图像、彩色图像的去噪算法,在传统的形态学去噪算法的基础上,进行改进和创新,进一步提高了图像的质量。 在二值图像去噪算法中,设计与实现了一种多结构元素的串行广义复合形态滤波器。由于传统的形态滤波只采用单一结构元素,致使滤波结果无法顾及图像在不同方向上的特征,不能完全滤除噪声,模糊了图像的细节特征。本文在二值图像去噪算法中采用了多尺度多方向的结构元素,不仅有效地抑制了图像中的噪声,而且较好地保持了图像的几何特征。同时利用广义复合形态滤波具有平移不变性、递增性、等幂性等重要特征进行图像降噪。在灰度图像去噪算法的设计上,采用了一种Contourlet变换结合Cycle Spinning技术、形态学HMT变换的去噪方法。Contourlet变换是一种真正的图像二维表示方法,具有多分辨性、局域性、方向性的优点,而Cycle Spinning技术能够有效抑制由于Contourlet变换缺乏平移不变性而引起的伪Gibbs现象,在以上两者结合的基础上,对于Contourlet分解后高频子带中的噪声,运用数学形态学中的HMT变换进行有针对性的提取和去除。与传统的小波变换阈值去噪方法相比,这种方法??的平滑了噪声,保持了更多的图像边缘和纹理细节,视觉效果也更好。 对于彩色图像去噪,采用了一种基于RGB彩色空间的改进的中值滤波,结合多结构元素的标量形态滤波算法。传统的中值滤波对所有的数据采用统一的处理方法,对每个像素都进行排序取中值,计算量巨大,时间复杂度高。而改进的中值滤波采用信噪分别处理的算法,排序时充分利用更新后的数据,克服了传统中值的不足,降低了时间复杂度,滤波效果也明显得到改善。同时根据人眼对三基色不同的敏感程度,选用不同大小的结构元素对三基色分别进行处理,与采用同样的结构元素对整个图像处理相比,在滤除噪声的同时,保留了更多的色彩信息,且不影响人眼对图像的视觉效果。本文在彩色图像去噪算法中,深入研究了改进的中值滤波算法并行化的可行性,实现了基于MPI的改进中值滤波的并行化算法,显著提高了改进的中值滤波算法的计算效率。 通过对各种改进算法的仿真实验效果和去噪算法性能指标(MAE、MSE、NMSE、PSNR)分析,表明本文各种改进算法比传统算法具有更大的灵活性,滤除噪声的能力显著增强,证实了算法的可行性和有效性。

关键词： nonbipartite matching   matroid intersection   algebraic algorithms   fast matrix multiplication  

摘要： We present new algebraic approaches for two well-known combinatorial problems: nonbipartite matching and matroid intersection. Our work yields new randomized algorithms that exceed or match the efficiency of existing algorithms. For nonbipartite matching, we obtain a simple, purely algebraic algorithm with running time O(n(omega)) where n is the number of vertices and omega is the matrix multiplication exponent. This resolves the central open problem of Mucha and Sankowski (2004). For matroid intersection, our algorithm has running time O(nr(omega-1)) for matroids with n elements and rank r that satisfy some natural conditions.

关键词： Algorithms   Hydrodynamics   Mathematical models   Ocean circulation   Ocean  

摘要： An algorithm for solution of the problems of the World Ocean dynamics with assimilation of hydrophysical fields is described. A mathematical model of the general ocean circulation and a numerical algorithm for its solution are formulated. Model equations are written in a generalized sigma-system of coordinates on a sphere with the North Pole displaced onto the continent. The model has a flexible hierarchical structure and consists of two parts: a forward prognostic model and its adjoint analogue. The forward and adjoint models supplemented with a cost functional minimization block may be joined into a variational observation data assimilation system. The numerical solution algorithm for the forward and adjoint models is constructed based on the method of multicomponent splitting. The method includes splitting with respect to physical processes and geometric coordinates. The algorithm is applied for Simulation of the large-scale circulation of the World Ocean. Results of integration of the forward model for the period of 300 years under climatic atmospheric forcing are presented. Experiments in solving the forward problem with inclusion of a variational procedure for temperature and salinity field initialization are described.

摘要： We present a comprehensive survey of combinatorial algorithms and theorems about lattice protein folding models obtained in the almost 15 years since the publication in 1995 of the first protein folding approximation algorithm with mathematically guaranteed error bounds [60]. The results presented here are mainly about the HP-protein folding model introduced by Ken Dill in 1985 [37]. The main topics of this survey include: approximation algorithms for linear-chain and side-chain lattice models, as well as off-lattice models, NP-completeness theorems about a variety of protein folding models, contact map structure of self-avoiding walks and HP-folds, combinatorics and algorithmics for side-chain models, bi-sphere packing and the Kepler conjecture, and the protein side-chain self-assembly conjecture. As an appealing bridge between the hybrid of continuous mathematics and discrete mathematics, a cornerstone of the mathematical difficulty of the protein folding problem, we show how work on 2D self-avoiding walks contact-map decomposition [56] can build upon the exact RNA contacts counting formula by Mike Waterman and collaborators [96] leading to renewed hope for analytical closed-form approximations for statistical mechanics of protein folding in lattice models. We also include in this paper a few new results, research directions within reach of rigorous results, and a set of open problems that merit future exploration.

关键词： 高考命题   算法思想   教学启示  

摘要： 算法初步作为普通高中数学新课程中的重要新增内容,已引起社会广泛关注,成为高考必考的重要知识点.但具体如何命制试题,比如内容的选择,题型的选择等等,才可以使试题在难度、信度以及效度等等都能更科学合理?同时高考中算法初步的命题研究对教学将会产生怎样的启示作用? 本研究尝试用试题调研、问卷调查和命题评析相结合的方式,对算法命题的实际问题做一些初步的探讨,希望能对以后教学及其研究有一定的启示作用. 全文分为五大章,主要简述了课程标准及其教科书中有关算法内容的目标要求；什么是算法；概述了重要的算法思想和方法；详细论述高中数学新课程中算法的高考命题,说明算法思想的体会、领悟和贯穿相关数学内容的重要性；在命题的编制上要注意：内容与题型的选择,内容范围与结构比例的安排,内容或题型要有具体的测量目标,并且命题要有利于学校课堂教学方式和学生学习方式的改善,题型要反映高质量的教学活动和学习活动;最后,通过高考命题研究对算法教学的启示作出小结.

ISBN: (纸本)9787302197621

关键词： 数学符号识别   特征融合   数字图像处理   人工神经网络   小生境遗传算法   智能信息处理技术  

摘要： 手写体符号识别是利用计算机自动辨认手写体符号的一种技术,是光学字符识别技术的一个分支。手写体符号识别在财务报表、银行票据、各种凭证以及调查表格的识别等等方面有着重要应用,并且手写符号的识别直接关系到手写公式的识别,而在公式识别这一领域,至今为止尚没有取得让人满意的效果,所以研究手写符号识别技术具有重要的理论意义和实用价值。 手写体符号识别分为联机识别和脱机识别。其中,最为困难的就是脱机手写字符的识别。主要是因为脱机手写体识别过程无法获得字符书写时的一些动态信息,因此脱机手写体数学符号识别更具挑战性。 针对传统手写体数学符号识别方法的复杂性和局限性,本文研究了基于小生境遗传算法和人工神经网络的手写体数学符号识别方法,该方法提取字符互补性强的粗网格特征、投影特征、交截特征和结构特征,并将这四个特征构成的特征向量输入BP神经网络进行融合分类,使用遗传算法对人工神经网络权值和阈值进行优化,然后使用训练好的NGA-BP网络对数学符号进行识别。 实验结果表明:本文使用的小生境遗传算法与人工神经网络相结合的数学符号识别方法,识别率达到90.2%。该方法不仅具有较高的识别率和良好的可靠性,而且使用了较少的特征值,简化了算法的复杂度。