前言：中文期刊网精心挑选了数学建模常用的算法范文供你参考和学习，希望我们的参考范文能激发你的文章创作灵感，欢迎阅读。
数学建模常用的算法范文1
中图分类号：G642.3 文献标志码：A 文章编号：1674-9324（2012）08-0106-03
运筹学应用分析、试验、量化的方法，对经济管理系统中人、财、物等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。该课程主要培养学生在掌握数学优化理论的基础上，具备建立数学模型和优化计算的能力。本文提出一种新的教学改革思路，将运筹学和数学建模两门课程合并为一门课程，即开设大容量交叉课程《运筹学与数学建模》来取代《运筹学》和《数学建模》两门课程，采用案例教学和传统教学相结合的教学方法，数学建模和优化算法理论并重的教学模式。这样既可以避免出现极端教学和随意选取教学内容的现象，又可以将新颖的教学方法与传统方法相结合，按照分析问题、数学建模、优化算法理论分析及其方案制定、实施等解决实际问题步骤展开教学。下面就该课程开设的必要性、意义、可行性、注意事项及其存在问题等方面进行分析。
一、开设《运筹学与数学建模》课程的必要性
1.一般院校的运筹学课程的教学课时大约为64或56（包含试验教学），所以教学中不能囊括运筹学的各个分支。一方面，由于课时量不足，教师选取教学内容时容易出现随意性和盲目性；另一方面，教学中为强化运筹学的应用，消弱理论教学，从而导致学生对知识的理解不透彻，在实际应用中心有余而力不足。
2.运筹学解决实际问题的步骤是：（1）提出和形成问题；（2）建立数学模型；（3）模型求解；（4）解的检验；（5）解的控制；（6）解的实施。大部分教学只涉及步骤（3），即建立简单数学模型，详细介绍运筹学的算法理论，与利用运筹学解决实际问题的相差甚远。因此，学生仍然不会应用运筹学解决实际问题，从而导致学生认为运筹学无用。
3.数学建模课程包含大量的运筹学模型；运筹学在解决实际问题的环节中包含建立数学模型步骤。目前两门课程分开教学，部分内容重复教学，浪费教学课时。
二、开设《运筹学与数学建模》课程的意义
1.激发学生的学习动机，培养学习兴趣。该课程包含数学建模和运筹学两门课程的内容，内容容量大，教学课时丰富，教学过程中能够以生产生活中的实际问题为案例，分析并完整解决这些问题，创造实际价值，使学生认识到该课程不但对未来的工作很重要，而且还有可以利用运筹学知识为企业或个人创造价值，改变运筹学“无用论”的观念。从而激发学生的学习动机，产生浓厚的学习兴趣。
2.合理处理教学内容。运筹学与数学建模的课时量相对充足，能够安排更多的内容，能够系统、完整地介绍相关知识，在一定程度上避免了运筹学内容安排的随意性和盲目性。
3.促进教学方法改革。运筹学与数学建模的教学不再是简单的数学建模和理论证明，教学内容丰富、信息量大，传统的一支笔一本教案一块黑板的模式不再适用，需寻找新的教学方法，促进了多种教学方法的融合。
4.培养学生综合能力。实际案例源于社会、经济或生产领域，需要用到多方面的知识，但学生不可能掌握很多专业知识。因而，在解决实际案例的过程中，需要查阅大量的相关文献资料，并针对性阅读和消化。而且，实际案例数据量大，需要运用计算机编程实现。因此，通过该课程的学习，可以提高学生多学科知识的综合运用能力和运用计算机解决实际问题的能力。
5.改变教学考核方式。教学改革后，教学内容已延伸到运用优化知识解决实际案例的整个过程。教学过程中既有对实际案例分析、建模，又有算法介绍、求结果的检验及其最终方案的实施。因而，传统的单一闭卷考试改为笔试和课后论文相结合的方式。
三、开设该课程的可行性
1.运筹学和数学建模互补性、递进性使得开设该课程在理论上可行。数学建模是利用数学思想去分析实际问题，建立数学模型；运筹学是利用定量方法解决实际问题，为决策者提供决策依据。由此可见，建立数学模型为运用运筹学解决实际问题的重要步骤。所以，运筹学可以认为是数学建模的进一步学习。同时，运筹学模型为数学建模课程介绍的模型中的一部分，并且运筹学处理实际问题的方法为数学建模提供了专业工具。因此，运筹学与数学建模在内容上是互补的。由此可知，开设该课程在理论上是可行的。
2.计算机的发展使得开设该课程在操作上可行。随着计算机的发展，能很快完成大数据量的计算，实际案例的数据分析、数学建模及其求解能快速实现，从而使得该课程的教学工作能顺利开展。
3.大学生的知识储备使得开设该课程在基础上可行。学习该课程的学生是高年级学生，通过公共基础课和专业基础课的系统学习，分析问题、解决问题的能力得到进一步提高。同时，运筹学和数学建模所需基础知识类似，学习该课程所需的线性代数、概率论与数理统计、高等数学及微分方程等课程也已经学习，运用运筹学与数学建模知识解决实际案例所需的基础知识已经具备。因此，开设该课程是可行的。
数学建模常用的算法范文2
【关键词】变量回归；灰色理论；神经网络；遗传算法
Comparative Study on Modeling Method of Book lending
CHEN Ying
（Henan Agricultural University，Zhengzhou Henan 450002，China）
【Abstract】This paper studies the predictive modeling principles and steps of multi variable regression， grey system theory， neural network and genetic algorithm， predict to law school of Henan Agricultural University library books borrowing model construction as an example， and the modeling process of four kinds of modeling methods were optimized and simplified analysis. With year lending books as sample data， forecast the loan amounts of two books in 2013， and compared with the recorded values， show that predictive genetic algorithm is more suitable for the library lending.
【Key words】Variable regression；Grey theory；Neural network；Genetic algorithm
0 前言
在信息社会，纸质图书的流通频率对构建学习型社会非常重要，一定周期内的不同类型的图书借阅量反映了该社会公民的整体素养。借阅趋势分析是图书管理员的日常工作之一，通过对借阅规律分析，管理员能够掌握师生的借阅兴趣和研究状况，各类图书和期刊的采购数量和质量，达到更好的为师生服务的目的。建立恰当的数学模型能够预测未来一定时间段内图书的借阅规律，常见的借阅规律预测模型建模方法有以下几种：多变量回归分析法、神经网络、灰色系统理论和遗传算法等[1]。在上述方法中，多变量回归分析方法是基础，其它几种方法都是基于该方法演变而来，是最通用的方法[2]。神经网络算法也是数学建模中常用算法，该算法有很强的非线性拟合能力，可映射任意复杂的非线性关系，学习规则简单，鲁棒性、记忆能力、能力和自学习能力强大，但该算法没能力来解释自己的推理过程和推理依据，训练模型的数据量庞大，计算过程容易造成信息的丢失；与神经网络建模方法相比，灰色系统理论建模过程清晰简单，模型稳定性比较好，但预测精度有待提高。遗传算法属于全局搜索算法，采用仿生学原理模拟自然进化过程择优搜索，该方法适用范围广，在一定域内总能找到目标解，但模型容易“早熟”，难以到达最优解，属于随机算法[3-4]。本文对上述四种建模方法的建模过程进行分析，对数学模型的优缺点进行评价，为图书管理员和图书管理科研工作者提供一定的参考。
1 多变量回归建模预测图书借阅量
1.1 建模原理
回归分析是一种分析变量之间关系的数理统计方法。对于待分析的数据和变量，虽然变量之间没有确定的数学关系，但可以找出最能代表它们之间关系的数学表达式：数学模型。在图书借阅规律研究方面，有两方面的应用，一是根据师生以往和现在的借阅状况，预测图书将来的借阅状况；二是对影响借阅状况的原因进行分析， 找出哪些是重要因素， 哪些是次要因素， 这些因素之间又有什么关系等等。
1.2 建模过程
使用多变量回归分析方法得到的图书预测模型通常表示为时间变量的多项式，并利用最小二乘原理求得多项式的系数，主要求解步骤如下：
（4）计算拟合残差，评估预测结果的可靠性。
2 神经网络建模预测图书借阅量
2.1 神经网络建模原理
神经网络建模的基本原理是：各种图书历年的借阅样本数据通过模型的中间层作用于输出层，经过非线形变换，产生输出的模拟值，模型训练的数据包括输入矩阵和期望矩阵。模型输出值和期望值之间的偏差量，通过调整输入层与隐层之间的加权值、隐层与输出层之间的加权值及阈值，使误差沿梯度方向下降，经过反复学习训练，确定与最小误差相对应的网络参数（加权值和阈值），训练即告停止。此时经过训练的神经网络即能对类似样本的输入数据，自行处理输出误差最小的经过非线形转换的信息。神经网络模型结果如图1所示。
图1 神经网络模型结构
Fig.1 The structure of a neural network model
2.2 神经网络建模过程
（1）模型初始化。给各节点间赋予一个初始权值，一般可以设为（-1，1），设定节点间误差函数e和计算精度ε，规定最大学习次数M。
（2）输入样本数据，计算各隐层神经节点的输入和输出数据值。
（3）利用模型的输出期望和实际输出，计算误差函数对模型节点的偏导数δm（k）；计算隐层和输出层对神经节点的偏导数δn（k）。
（4）利用神经节点的计算值修正节点间的连接权值。
（5）计算综合精度，并判断预测值是否符合要求。
3 灰色系统理论模型预测图书借阅量
3.1 灰色系统建模原理
灰色系统模型预测，是指对系统行为特征的发展变化进行预测，对既含有白信息又含有灰色信息的系统进行预测。很多情况下，样本数据中所显示的信息具有随机性，但随机的信息中也包含了时序的特征，灰色模型预测就是利用这种规律来进行预测。当前使用比较多的灰色预测模型是一阶微分的GM（1，1）模型。它是基于随机的原始时序，经累加后所形成的新的时序，该时序的规律用一阶线性微分方程的解来逼近。
3.2 预测模型建模过程
（3）预测方程精度评估。精度评估主要是对模型方程的预测值和样本数据进行比较，计算预测残差和数据间的相对误差。
（4）预测实现。
4 遗传算法预测图书借阅量
4.1 遗传算法建模原理
遗传算法是本质上是一种寻优方法，该方法借鉴生命学上的生物优胜劣汰原则，不断的择优搜索系统解。该方法直接对待优化的系统进行求解，不需要对系统进行连续性限定和对系统求偏导数，因此在应用上更加灵活，并且有较强的全局搜索能力。能对所有的样本数据进行优化处理，并且自适应的调整搜索的方向，在样本数据的渐次迭代中找到最优预测解，而且得到的这个解象生物界的生命体进化那样，有更强的适应性。
4.2 遗传算法用于图书预测建模过程
建模的过程参看流程图2。
图2 遗传算法预测模型基本建模过程
Fig.2 Prediction model of genetic algorithm
5 实例分析和预测结果比较
5.1 借阅样本数据
表1显示的是河南农业大学文法学院图书室2005～2012年间两种图书的借阅量。
表1 2005～2012年 两种图书借阅量
Tab.1 Lending condition among 2005-2012 years
5.2 不同建模方法预测结果比较
（1）表2显示的是2013年的两种图书预测结果
表2 回归分析法年借阅趋势预测结果
Tab.2 Forecast results of year of variable regression
（2）表3显示的两种图书的灰色模型预测结果
表3 灰色模型借阅趋势预测结果
Tab.3 Forecast results of year of grey system theory
（3）表4显示的两种图书的神经网络模型预测结果
表4 神经网络借阅趋势预测结果
Tab.4 Forecast results of year of neural network
（4）表5显示的两种图书的遗传模型预测结果
表5 遗传模型借阅趋势预测结果
Tab.5 Forecast results of year of genetic algorithm
5.3 预测结果分析比较
从预测结果可以看出，遗传算法模型的预测结果比较精确，绝对误差和相对误差都比较小，灰色系统理论模型的预测结果相对比较弱，神经网络模型和回归模型的预测结果介于二者之间。灰色系统理论是对数据进行逐次累加，找到数据间的线性规律，当原始数据间跳跃比较大时，这种叠加出的规律线性度并不明显，所以预测结果比较弱。遗传算法在每一步计算时，都要进行智能择优搜索，而且对数据间的跳跃不敏感，所以在对这类数据进行处理和预测时，结果相对精确。神经网络模型的精度和中间层的数量有很大的关系，对原始样本数据量的要求也比较大，在不满足上述条件时，预测精度比较弱，而回归分析对数据的间的线性度要求比较高。
6 结语
本文分析了多变量回归、灰色系统理论、神经网络和遗传算法在河南农业大学文法学院图书室图书借阅量预测模型构建方面的问题，对四种建模方法的建模过程和建模结果进行了分析。用部分图书的年借阅量作为样本数据，预测了2013年这两种图书的借阅量，并与记录值进行了比较。比较得出了遗传算法更适合于图书室借阅量预测的重要结论。
【参考文献】
[1]刘思峰，等.灰色系统理论及其应用[M].3版.科学出版社，2007.
[2]陈英，王秀山.基于灰色系统理论的农业院校院系纸质图书借阅管理研究[J].科技视界，2003（3）：114-116.
数学建模常用的算法范文3
一、创新能力、数学建模的概念
1.创新能力的概念。创新能力主要是指利用已有的知识和经验，在个性品质的支持下，新颖而独特的提出问题、解决问题，并由此产生有价值的新思想、新方法、新成果。创新能力是抽象的，必须通过具体的、生动的数学活动去培养，那么数学建模能力就成为培养创新能力的一个载体。
2.数学建模的概念。所谓数学模型，是指对实际问题进行分析，经过抽象、简化后所给出的数学描述，它是使用数学符号、数学表达式以及数量关系对实际问题简化而进行关系或规律的描述。一切数学概念、各种数学公式、各种方程、各种函数关系、各种定理及各种理论体系等，都可称为数学模型，因为他们都是从现实生活原型中抽象出来的。
二、数学建模的方法
创建一个数学模型的全过程称为数学建模，即用数学的语言、方法去近似地刻画该实际问题，并加以解决的全过程。数学建模的过程， 大致是用如下框图来说明：
数学教学中，要使学生初步学会建立数学模型的步骤，提高学生应用数学知识解决实际问题的能力。
三、创新能力培养中数学建模的应用
1.直觉思维的创新能力培养中建模的应用。众所周知，数学史上不少的数学发现来源于直觉思维，如笛卡尔坐标系、费尔马大定理、欧拉定理等，应该说它们不是任何逻辑思维的产物，而是数学家通过观察、比较、领悟、突发灵感发现的。通过建模，使学生有独到的见解和与众不同的思考方法，如善于发现问题，沟通各类知识之间的内在联系等。
例：科技馆里小明看见一台三角形的仪器，如图1所示，当一个小球从入口落下，它在依次碰到每层菱形挡块会等可能的向左或向右落下。
（1）试问小球通过第二层A位置的概率是多少？
（2）请用学过的数学方法模拟试验，并具体说明小球下落到第三层B位置和第四层C位置出的概率各是多少？
分析：有几位学生在讨论研究时，甲及丙生用画树状图的方法解决这一问题，结果算出来了，但太复杂；乙及丁生提出它的形状象杨辉三角，能否用它来类比的解决这个问题吗？他们共同研究发现小球所在的位置及它在下落时所经过这一位置的次数，这与杨辉三角的每一层的系数相吻合，总次数就是这一行的系数之和，很容易算出经过这三点的概率，如图2；他们几个又接着研究发现有一规律，并建立了新的概率三角，如图3。
2.归纳和类比思维的创新能力培养中建模的应用。归纳和类比思维是数学上的一种非常典型的创新思维，著名的数学家拉普拉斯说过“在数学里，发现真理的主要工具和手段是归纳和类比。”而大多数数学模型的建立、修改或改进，很多时侯都是依靠这种归纳与类比思维。在寻找模型求解的算法时，也常常用类比思维，利用相似的算法加以优化和改进而得到，有时甚至可以发现新的更好的算法。
分析：本题可以前几项归纳出一般式，利用互为相反数两数相加得0加以简化。
3.化归思维的创新能力培养中建模的应用。恩格思曾说过：“由一种形式转化为另一种形式不是无聊的游戏，而是数学的杠杆，如果没有它，就不能走远。”由于建模就是把实际问题化归成数学问题，因此，如果我们在数学教学中注重转化，用好这根有力的杠杆，对培养学生思维品质的灵活性、创造性，以及开发智力、培养能力、提高解题速度是十分有益的。
例：（2009年四川省内江市）如图，小陈从O点出发，前进5米后向右转200，再前进5米后又向右转200，……，这样一直走下去，他第一次回到出发点O时一共走了（ ）
A. 60米 B. 100米
C. 90米 D. 120米
分析：本题可以化归为构建多边形
外角和模型的应用问题。【答案】C
数学建模常用的算法范文4
关键词：数学建模；创新能力；大学数学主干课程
中图分类号：G642.4 文献标志码：A 文章编号：1674-9324（2012）07-0158-03
大学生数学建模竞赛不仅能培养出具有创新能力的学生，也能一定程度上提高教师的教学和科研水平，而且最重要的是它能直接推动大学数学的教学改革。教育部高教司对我国大学生数学建模竞赛活动的主要指导思想之一就是“扩大受益面、推动教育改革”。开展数学建模教育，可以推动大学数学教育改革。开展“在大学数学教学融入数学建模、数学实验的思想和方法，培养学生的创新能力”课题的研究和实践，就是扩大数学建模受益面的一个重要探索。本文研究对在大学数学教学融入数学建模、数学实验的思想和方法的必要性，相应的融入手段，以及在融入过程中可能遇到的困难和解决办法等进行了论述。
一、数学建模思想融入大学数学的教学中的必要性
1.数学建模几乎是一切应用科学的基础。数学在科学中的一个重要作用就是能够使人们对事实上是相当混乱的东西进行适当的理想化，抽象出概念与模型，从而解决实际问题。在解决复杂科学技术问题时，数学建模的方法能使人们设计出最佳和可行的新技术方法、手段，以及预测新的现象等。数学建模及相应的计算也正在成为工厂里常用的主要工具。Charlies R. Mischke指出：学生一般都并不确信大学所开设的所有课程是否真能培养他们的创新能力。他们对学习渐渐失去兴趣，原因之一就是缺乏让学生了解大学教育进程安排的合理性。工程专业课程强调的基本都是专业方面的问题。而实际用来进行教学、组织和应用的工具却是数学模型。但不幸的是，专业教师很少花时间来讲授不涉及专业方面的建模过程本身。所以将数学建模的思想和方法融入大学主干数学课程教学中是具有现实的必要性。
2.当前数学教学的问题。传统的数学教学和考试可以很好地检查学生对所学数学知识的概念、定理和方法等的掌握情况，但缺乏对学生的应用数学的能力和创新能力进行考察。因此，在大学数学教学和考试中融入数学建模思想和方法非常必要。传统的大学数学教育已不能有效地激发广大学生的求知欲和激情，不能有效地培养学生的创新意识和创新能力。在现实的大学数学教学活动中，学生常常陷入前所未有的困惑之中，投入大量的精力，做了大量的习题，却丝毫感受不到“数学”有何作用，老师也拿不出鲜活的例子来使学生信服数学的用处。一大半学生认为大学数学的教学内容是没意义的，并且认为无意义的最大原因是和实际没有联系，学生最常问老师的问题就是“高等数学有什么用？”“线性代数有什么用？”等问题。
二、数学建模思想融入大学数学的教学中的具体措施
在大学数学的教学中融入数学建模思想主要是要让学生明白大学教育进程安排的合理性，以及数学的重要性和广泛应用性。但还是必须明确要以数学主干课程为主，建模思想培养为辅的指导思想，最主要的目的还是促进学生更好地学习和掌握大学数学主要内容、思想和方法。要建立一套恰当的数学建模思想融入大学数学教学的具体措施。首先必须弄清楚数学建模的具体过程以及我们大学数学教学的内容和思想。数学建模过程一般分为下面几步：①对实际问题进行观察、分析，进行必要的抽象、简化（抓住要点），确定模型建立中的变量和参数；②根据已知的各学科中的定律，甚至是经验等建立变量和参数之间的数学关系，这实际上就得到了明确的数学问题；③求解该数学问题。大部分情况是没有办法得到解析解，而只能得到近似解。这往往涉及复杂的数学思想、理论和方法，以及近似方法和算法；④得到的数学结果是否能解释或预测实际问题中出现的现象，或用历史数据、实验数据或现场测试数据等来验证模型是否恰当；如果模型是恰当的，那么就可以试用；如果是否定的，那就要进行仔细分析，重复上述建模过程，不断调整、最终得到恰当的数学模型。大学数学的特点是的抽象的思想、严谨的逻辑推理和广泛的应用，也正是由于它的抽象和严谨，使得其成为我们将其他学科量化的一个有效的工具。它与许多其他学科的本质区别在于它抽象地反映了现实世界里各种对象及其变化在数量方面的一般规律，它能够把一个学科的思想经过抽象、推理和提炼得到的结果用到别的学科，从而具有广泛的应用性。将数学建模思想融入大学数学的教学的具体方法。
1.具体的切入点。①经验建模——在所收集数据中提炼事物发展的趋势；②讲授一些实际问题及相关数学模型：人口模型、管理模型、抵押贷款模型、传染病模型、减肥模型等等。在现有教材中已经讲解了所涉及的数学内容，但如果从分析具体问题到建立数学建模的过程来学习的话，不仅能激发学生的学习兴趣和积极性，而且还能使其能在学、做而后知不足，从而诱导学生进一步学习数学。
数学建模常用的算法范文5
由清华大学吴文虎、王建德编著的《世界大学生程序设计竞赛(ACM/ICPC)高级教程 第一册 程序设计中常用的计算思维方式》(以下简称《计算思维方式》)就是针对世界大学生程序设计竞赛(ACM/ICPC)而编写的参考书,该书面向参加ACM/ICPC的高等院校学生,也可作为程序设计爱好者的参考用书。同时,也向讲授程序设计及相关课程的教师推荐此书,建议认真一读。
1ACM/ICPC
ACM/ICPC是高等院校计算机教育成果的直接体现,是大学生展示水平与才华的大舞台,也是IT企业与世界顶尖计算机人才对话的最佳机会。因而,ACM/ICPC吸引了越来越多的高校参赛,使得参赛队伍的水平上升很快,赛题的难度也在不断提高。
每年度的ACM/ICPC赛事从当年9月份开始,先进行各大洲各地区的预选赛,从上千所高校的几千支队伍中挑选出几十支优胜队伍。让这些百里挑一的队伍在下一年春天参加总决赛,争夺金银铜奖和世界冠军的奖杯。参赛选手由三人组成,一队共用一台计算机。这项赛事与中学生的信息学奥林匹克竞赛既有联系又有较大区别,被称为大学生的信息学奥林匹克。以2008～2009年度的ACM/ICPC为例,这是第33届赛事,有1838所大学的7109支队伍参加分区赛。经过第一阶段的预选赛,共有100支队伍取得决赛资格,于2009年4月18日―22日在瑞典斯德哥尔摩举行全球总决赛。
参加ACM/ICPC的选手需要具备很强的数学建模功底、广博的算法知识、超强的编程能力以及团队的合作与协同能力。ACM/ICPC的胜负规则是:答对题目数量多者占优;在两个队解题数量相同的情况下,总用时最少者占优,因此解题速度非常关键。如果比赛一开始就能迅速找出竞赛中相对简单的题目并尽快加以解决,队伍的成绩排名就会占有优势,心理上的压力也会小些。相反,一开始就没有选好题,或者所写的程序总有这样或那样的错误,要花很多时间去调试排错,就会浪费宝贵的时间,处于下风。
在这种你追我赶的激烈赛场上,比的是谁做得又快又好。竞赛过程中第一个重要的环节是看题、审题和选题。一开始就选对题,一下子就切入主题是十分重要的。有时第一个环节遇到陷阱,“马失前蹄”,就会导致一筹莫展而步步落后。能否在第一环节占上优势取决于实践能力和洞察力,而实践能力与洞察力的提升需要实战,需要经验,需要学懂计算思维方式和解题策略。
参加ACM/ICPC活动,在与编程高手过招的过程中,可以把知识运用的综合性、灵活性和探索性发挥到极致,体验和感受数学思维与算法艺术之美,提升科学思维能力。
2“观察―联想―变换”思维方式
计算机解题的核心是算法设计,而算法设计需要具备良好的数学素养。数学具有运用抽象思维去把握实际的能力,应用数学知识去解决实际问题时的建模过程是一个突出主要因素的科学抽象过程。进行抽象和形式化需要学习和掌握常用的计算思维方式。
科学思维能力的提高是成就事业最重要的因素之一,本书作者希望能在这方面对读者起到帮助作用。
编程解题的一般思维方法或过程,可以概述为“观察―联想―变换”,即通过对问题的观察,认识和理解该问题;然后通过联想,寻找该问题同已有知识和经验之间的联系;最后通过变换,把该问题转化为另一个或几个易于解决的新问题,最终达到解决原问题的目的。
“观察”是人类认识客观事物的基本途径,就编程解题而言,“观察”是“联想”和“变换”的基础。一般地说,通过观察应当明确:求解的对象是什么;是枚举方案还是回答哪个存在性问题;已知的条件(包括隐含条件) 是什么;能否用递推公式、递归公式、约束规则或状态转移方程把问题的条件、结论和求解途径表示出来;问题所涉及的这些计算式子各有什么特点等。
“联想”是由某种对象而引出其他相关对象的思维形式。就编程解题而言,“联想”的目的在于为“变换”提供可能的方向或线索。一般地说,在“观察”的基础上,通过联想应当明确:以前是否解过这类试题;是否解答过与其类似而又稍有不同的试题;是否解答过与其有关的问题;能否利用解答这些问题时所使用的解题方法或所得到的结果;能否回忆出某个可能用得上的定理、公式或解题思路;为了能利用它,是否应当改变条件或结论的表现形式等。
“变换”是编程解题的基本手段。在“观察”和“联想”的基础上,有目的地对问题实施“变换”,把原问题转化为另一个或几个易于解决的新问题,这是编程解题成功的关键。为此,变换时,应当遵循如下三条基本的思考原则:熟悉化原则、简单化原则以及和谐化原则。
3程序设计的常用思维方式
为了使读者对“观察―联想―变换”的思维方法和过程有一个比较全面深入的了解,本书归纳了大赛程序设计中六种常用的思维方式,主要包括正确认识和处理整体与部分的关系、构造性思维、目标转化的思想、分类与分治思想、逆向思维、猜想与试验六个章节,旨在引导参赛学生学习并掌握编程解题的一般思维方法和过程,提高解题能力。
在“观察”上,提出了整体与部分的思想,包括:
(1) 整体实现的关键是准确地应用必要条件。
(2) 整体思考的一个重要角度是“守恒”,即寻找变化中的不变量。
(3) 提高整体实现效率的途径是“充分利用有效信息”和“压缩冗余信息”。
(4) 改善整体的性能状态的基础是处理好细节问题。
在“联想”上,提出了逆向思维和猜想与试验,分析了“执果索因型”的逆向思维和“由反及正型”的逆向思维;探讨了四种联想方式:相似联想、归纳联想、从数与形的结合上联想和“回到起点”重新联想。指出猜想是在深入分析问题的基础上,不懈探索、反复修正的过程。
在“变换”上,提出了构造性思维、目标转化思想、分类与分治思想。构造性思维包括建立模型的机理分析法和统计分析法;建模过程注意应用序关系;选择模型时必须权衡四个因素:“时间复杂度、空间复杂度、编程复杂度和思维复杂度”。目标转化思想包括缩小目标的“降维”思想和放大目标的“升维”思想;分类与分治思想包括应用于一般有序序列的“二分查找”;应用于退化了的有序序列的“二分枚举”;应用于无序序列的“二分搜索”;应用于多维情况的“多重二分”。
在实际编程解题时,“观察”、“联想”、“变换”等思想活动总是互相联系、互相影响、互相交织地进行着,形成了一个有机的整体。本书列举的六种思维方式是互相渗透的,章节划分主要是依据各种思维方式的主要特征进行分类,同时也是为了叙述的方便。当然这六种思维方式并没有、也不可能穷尽编程解题过程中的所有思维活动,它只不过是列举了常用的一些思维方式,为“观察―联想―变换”的思维活动勾勒出一个基本轮廓,为读者留下学习、探索和再创造的空间。
4本书的体例结构
本书介绍的内容丰富而深入,所采用的叙述结构大致如下:
思维方法1 (1～6)
知识点1
经典例题1
思路点拨
解题思路分析
算法1
算法分析
程序实例
算法2
……
经典例题2
……
小结
知识点2
……
思维方法2
……
书中选择了大量的经典例题,这些题目对于丰富程序设计课程教师的教学案例也很有帮助。所选取案例大都具有一定的趣味性,有助于提高读者的阅读和实践练习的兴趣,提高实践效果。因此,可以说,虽然本书的编写主要针对ACM/ICPC,但对于高等院校程序设计教学水平的提高,促进程序设计教学质量和教学改革发展具有积极的意义。
本书各个知识点的“小结”内容是很值得推荐阅读的部分,作者以精准的语言扼要地概括了本部分的知识内容,仔细阅读和认真思考,将起到事半功倍的效果。
5图书相关信息
书名:《世界大学生程序设计竞赛(ACM/ICPC) 高级教程(第一册) 程序设计中常用的计算思维方式》
作者:吴文虎王建德编著
ISBN:978-7-113-10134-3/ TP3344
页数:278
定价:42.0元
出版社:中国铁道出版社(计算机图书批销部)
北京市宣武区右安门西街8号
邮编:100054
责编:秦绪好
装帧:精装
出版年:2009-7
6主要内容(目录)
第1章正确认识和处理整体与部分的关系
1.1整体实现的关键是准确地应用必要条件
1.1.1选择有助于简化问题、变难为易的必要条件
1.1.2合成必要条件,从整体结构上优化
1.1.3必要条件与原有模型比较,更新算法
1.2整体思考的一个重要角度是“守恒”
1.2.1从具体问题中抽象出守恒量
1.2.2根据问题的本质构造守恒量
1.2.3在交互问题中构造变化中的不变量
1.3提高整体实现效率的基本途径是“充分利用有效信息”和“压缩冗余信息”
1.3.1计算过程中充分利用有效信息
1.3.2通过“压缩法”消除冗余的图形和数据信息
1.4改善整体性能状态的基础是处理好细节问题
1.4.1必须解决导致错误结果的细节问题
1.4.2争取降低算法时间复杂度的阶
1.4.3注意降低算法时间复杂度的系数
第2章构造性思维
2.1模型的基本概念
2.1.1模型的一般特点与功能
2.1.2模型的一般分类
2.1.3模型与信息原型间的关系
2.2建模的一般方法
2.2.1建模的机理分析方法
2.2.2建模的统计分析法
2.3建模的一般思维方式
2.3.1直接构造法
2.3.2分类构造法
2.3.3归纳构造法
2.4在建模过程中注意应用序关系
2.4.1在交互式问题中应用序
2.4.2利用典型的“序”关系简化问题
2.4.3寻找蕴涵在题意中的序关系
2.5模型选择
第3章目标转化的思想
3.1“降维”――缩小目标
3.1.1引入“降维思想”
3.1.2高维降为低维
3.1.3一般降为特殊
3.1.4抽象降为具体
3.1.5整体降为局部
3.1.6简化数据关系
3.2“升维”――放大目标
3.2.1让步假设
3.2.2倍增思想
第4章分类与分治思想
4.1应用于一般有序序列的二分法
4.1.1在给定的序列中“二分查找”
4.1.2在交互式问题中应用“二分插入”
4.2应用于退化了的有序序列的“二分枚举”
4.2.1用二分枚举求可行方案
4.2.2用二分枚举求最优性问题
4.3应用于无序序列的“二分搜索”
4.3.1在“二分搜索”的基础上构造可行解
4.3.2在“二分搜索”的基础上构造最优解
4.4应用于多维情况的“多重二分”
第5章逆向思维
5.1执果索因型逆向思维
5.1.1设置结果参数,逆向搜索
5.1.2从目标状态出发逆向规划
5.2由反及正型逆向思维
5.2.1割补法
5.2.2在统计问题中应用补集转化
第6章猜想与试验
6.1相似联想
6.1.1与熟悉的问题类比
6.1.2与特殊的问题类比
6.2归纳联想
6.2.1归纳联想的理论基础
6.2.2归纳联想的实际应用
6.3从数与形的结合上联想
6.3.1在数值计算中联想“以形助数”
6.3.2在几何计算中联想“以数助形”
6.4 “回到起点”重新联想
7推荐指数
推荐同行阅读指数: (注:以为最高。)
这是ACM/ICPC高级教程的第一册,我们期待着后续教程的尽早面世。
8作者简介
吴文虎,1955-1961年分别就读于清华大学电机工程系及自动控制系。清华大学计算机系教授、博士生导师,原国际信息学奥林匹克中国队总教练。主要研究方向包括语音识别及语言理解、语音合成、语音信号数字处理等。
吴教授学术水平精湛、教学水平高超、教学经验丰富。从1989年至今,吴教授作为总教练和领队,曾15次带领中国队参加国际信息学奥林匹克竞赛,中国队累计获金牌51块,届届名列前茅,2002年获信息学奥林匹克国际委员会颁发的“特别贡献奖”。1997年～2008年,吴教授连续13年指导清华大学的学生进入ACM世界大学生程序设计大赛总决赛,多次获金、银牌,并于2009年被大赛组委会授予“杰出教练奖”。
数学建模常用的算法范文6
关键词:数学建模 数学建模竞赛 大学综合素质
中图分类号: G642文献标识码:A 文章编号:1007-3973(2010)06-157-02
自从1995年我校首次组织学生参加全国大学生数学建模竞赛工作以来,不知不觉我在数学建模教学与竞赛工作已有16年。在校、教务处、理学院的领导下, 通过全体教练在教学上不断探索和共同努力, 取得了优异的成绩, 共获全国一等奖26项,全国二等奖49项,浙江省奖项多项,2006年至今共获美国特等奖1项,一等奖9项,二等奖16项。取得了省参赛高校与全国同类高校中的优异成绩。通过十几年来的教学与竞赛活动, 我感触很多, 现有如下一点认识与体会。
1数学建模教学及意义
数学建模是就是应用建立数学模型来解决各种实际问题的方法,即就是通过对实际问题的抽象、简化,确定变量和参数,应用某些“规律”建立起变量、参数间的确定的数学模型,并对数学模型求解,解释、验证所得到的结论,从而确定能否用于实际问题的多次验证、循环并不断深化的过程。它作为联系数学与实际问题的桥梁,是数学在各个领域广泛应用的媒介,是数学理论知识和应用能力共同提高的最佳结合点,在培养学生过程中,数学建模教学起到了启迪学生的创新意识和创新思维、培养综合素质和实践动手能力的作用,是培养创新型人才的一条重要途径。
2数学建模教学内容和方法
数学建模教学的根本宗旨是学生能力的培养和综合素质的提高, 而能力和素质的培养应以知识及教学活动为载体, 同时须辅之以相应的教学内容和方法。由于数学建模课程教学不同与其它数学类课程,其主要特点:(1)数学建模的主要“载体”是一个个的具体问题, 这些具体问题大多是各领域的实际问题或是它们的抽象和简化。(2)数学建模的问题涉及各个领域, 且均有一定的深度和广度, 并非单靠数学知识和某些专业知识就能完成, 但如果不具备数学知识和相关的专业知识是根本无法建立数学模型的; 而且即使已建立起的模型, 单靠某一学科的知识往往不可能得到满意的模型解。总而言之, 数学建模常常需要跨学科跨专业的多学科多专业知识的综合施用。因此,我们必须处理好书本知识与实际问题的关系,数学知识与其它相关知识的关系。
我校自1995年开设数学建模课程以来,根据实际需要,课程设置不断得到改革,目前课程组面向全校开设了多种不同课时不同程度要求的数学建模系列课程,包括数学实验以及课程设计等实践性环节。课程设置满足了不同专业学生的多样化需求和大量学生学习数学建模的大众化需求。根据我校特点,我们将数学建模课程的目标定位为“学习数学建模的常用基础知识和基本方法,培养学生综合素质、团队精神和实践能力,努力提高学生研究性学习和创新性应用能力”。 根据这样一个目标定位,在教学安排上注意基础知识的宽泛性,建模训练的应用性,教学方法的研究性。课程教学内容分为四大模块。(1)常用的数学方法讲解,如运筹学中的规划论、图论、组合优化、排队论等,概率统计与马尔可夫过程、层次分析,常微分方程,还有计算方法等等。当然我们不可能把这些内容面面俱到地细讲,只是择其要义,把最基本最有用的一些思想与方法展示给学生,让学生知道一些基本思想,同时知道何处可以找到何种方法用于解决何种问题。余下的问题则由学生自己去解决。本模块教学时数在各个不同层次分别为20到40学时;(2)建模分析,这一块除了历年竞赛模型外,还从教师自身的科研课题以及大量的科技杂志上精选加工了为数不少的建模案例,让学生初步明白用数学方法解决实际问题的一些基本方法。这里有的是老师讲解分析,有的则是让学生先读后讲,即让学生先去尝试着对所给问题建模并给以解决,然后向大家介绍他所用的方法,并让大家讨论,最后老师作简要总结或补充。这种教学方式是完全区别于传统的教学方式的,也是数学建模课程最具特色的内容之一(时)。(3)数学软件的使用以及计算机编程能力的培养,这一模块可以穿插在前两块的过程之中,也可以数学实验课的形式得以体现。若以实验课形式出现,则根据各个层次的不同,学时为17学时(课程配套的课内实验)到33学时(独立开设的数学实验选修课)。以上三块内容互相补充,互为依托,彼此间也没有一个明确界限,每一块内容,也没有明确的范围限制,尤其是第二大块,我们几年下来,可以说每年的教学内容都有较大的更新。而数学建模也正因为此而使得它对于师生两方面都是极具挑战性。(4)在前面三块的基础上,再配以实践性教学环节的设计,该环节中学生分成3人一组,要求学生根据教师提出的实际问题进行充分讨论,广泛查阅有关资料,提出各自的观点及模型雏形,写出对应的论文梗概,然后在班上进行讨论。
通过学习要让学生学会数学建模的思想,即在理解问题的基础上,将具体问题总结归纳提炼为一个数学问题,并设计出一整套求解方法来加以求解。难点是能够使用的数学方法涉及面太多太广,作为一个本科学生,尤其是我校这样地方性普通学校的学生难以在短期内接受。针对这个难题,我们采用基础知识和案例教学相结合,理论教学和上机实践相结合,教师讲课和学生自主练习相结合,教师引导和学生收集资料,探索讨论相结合,学生报告加教师点评相结合的方法,较好地解决了这个难题。十余年的教学实践证明,经过我们以这样一个模式培养的学生已经初步具备了从实际问题,到数学方法,到计算机编程实现并最终解决问题的基本能力,这一点不仅从我们的学生在历年的竞赛中均取得良好的成绩中可以得到验证,而且从毕业设计,指导“新苗人才计划”、“创新杯”等科研活动,学生就业,及研究生学习中充分体现。
3数学建模教学与竞赛关系
从我校数学建模活动实践说明,数学建模竞赛推进了数学建模教学课程化,数学建模课程教学为竞赛活动开展打下了基础,同时开设数学建模课程的目的也转向了竞赛与普及相结合,以提高大学生的综合素质和实践能力作为一个重要目标。我校最初开设选修课是因为参加数学建模竞赛的需要,选修的学生数较少,而且必须是往年成绩较优的学生才允许选修。经过几年探索,我们通过以竞赛为平台, 加强引导与指导, 充分激发学生的学习兴趣和热情。而且通过数学建模竞赛,促进了我校教学内容、教学方法、教学手段的创新,参加过训练和竞赛的学生们普遍感到,以往学多门课程的知识不如参加一次竞赛集训学得全面和扎实。因为数学建模竞赛需要全面掌握本领域相关知识, 在深入理解、领会前人智能精髓的基础上, 敢于提出自己的想法和观点。只有善于进行创造性地学习和运用知识, 善于对已知知识进行融会贯通, 注意知识积累的同时更注重对知识的处理和运用, 才能取得成功。随着数学建模竞赛在我校影响的增加,同时参加竞赛过的学生能力的提高,要求选修数学建模课程的学生逐年增加,使得开设数学建模必修课有了一定的群众基础,同时开设数学建模课程的目的也转向了竞赛与普及相结合,以提高大学生的综合素质和实践能力作为一个重要目标。目前,已在自动化、信息管理、统计、电子信息科学与技术、计算机、软件、通信等专业的学生开设不同层次的数学建模必修课与限选课,同时仍然在全校开设不同层次的数学建模选修课。对于不同层次,理论教学学时分别为34、50、66学时,并辅以上机实践训练,每年从当初几十名学生到目前每年近2000名学生修读此课。参加校数学建模竞赛学生近600人。数学建模教学已经形成了多个品种、多种层次、多种方式的教学格局。
4数学建模教学团队重要性
课程教学实施与建设离不开教学团队建设,这一点数学建模教学团队建设更显得重要。因为一切科学研究都需要建模,而建模会用到多方面的知识与技能,例如,通过数据处理分析,找出统计规律的能力、运用数学知识建立数学模型的能力、运用最优化方法与技术改进模型并设计出算法的能力等等。这些能力的培养单靠一门课程的努力是不够的。因此数学建模教学与竞赛离不开集体的力量,教学内容涉及面广、方法多、工作量大,必须组建一支知识面宽、业务素质高、解决实际问题能力强、热爱学生、具有团结协作和乐于奉献精神的新型教师队伍。我校课程小组利用这些年新进教师比较多的实际情况,每年动员吸收适量新教师加入到数学建模教师队伍。通过以老带新,请专家来我校讲学或让有一定潜力的教师外出观摩或参加相关交流活动等形式逐步提高青年教师的数学建模教学水平。通过努力,已经建设成功一支规模适当、水平较高、结构合理、相对稳定的数学建模师资队伍,教师队伍从最初的5名教师扩展为现在的15位教师。课程教师队伍在年龄结构、学历结构、知识结构各个方面得到了很大的改善。原先5位教师中仅有2名副教授和3名讲师,现有教师中有5位教授,7位副教授,博士学位获得者有8名,超过50%。课程组教师的教学科研水平较高。这为我校数学建模活动很好开展作了保障。
5数学建模教学促进了数学课程教学的改革
数学建模教学促进了我校数学课程教学的改革工作,这种促进既有内容上的也有教学方法上的。比如早在上世纪末,我们与电子分院部分教师一道组织讨论,在高等数学、线性代数以及概率统计教学中,找一些结合学生专业方向工程背景的实际问题,融入到课堂教学中,加强应用所学方法解决实际问题的例子,一方面可以使学生学到数学在本专业用处与数学建模知识,另一方面也可以使学生加深对数学思想本质的理解。这与以后将数学建模思想融入到本科公共课程数学中思想是一致的。另外,在第二学期,开设高等数学实验试验。并且在数学建模教学方法上探索得到经验,有目的应用到其他数学教学方法上,在教学中注意强调讨论式教学以及学生的自主学习尝试。激发学生的多种思维,增强其学习主动性,培养学生独立思考,积极思维的特性,这样有利于学生根据自己的特点把握所学知识,形成自己的学习机制,逐步培养很强的自学能力和分析、解决新问题的能力。
6数学建模教学活动对学生能力培养影响
通过数学建模教学、组织大学生数学建模竞赛,学生在数学应用能力、分析处理问题综合素质方面得到极大的提高,表现出很好的继续培养潜力。培养锻炼提高了教师的教学、科研能力;活跃了本科生的科技活动和学习氛围。正像我校参加过数学建模活动学生代表王教团感言那样,数学建模,它魅力无穷,能够很好地锻炼和考查一个人的综合素质,是培养创新能力的一个极好载体。它能充分体现参与者的洞察力、创造力、数学语言翻译能力、文字表达能力、综合应用分析能力、想象力、使用当代科技最新成果的能力等等;它能塑造参与者同舟共济的团队精神、自律精神和协调组织能力,提高自主学习的能力和主动寻求问题、思考问题、解决问题的能力。 正是这些能力的培养和锻炼,使我在后续的一些学习和研究工作中能够游刃有余。在大三大四阶段,我和团队的其余4位成员承担完成了07年省新苗人才计划项目,并最终顺利通过验收,撰写了一份调查报告以及发表了2篇学术论文。这让我第一次接触到了真实的研究型项目,通过这个项目,使我迅速成长起来。但是归根结底,没有数学建模期间积累的经验,我们是没法独立承担一个项目的。 在目前研究生阶段中,我同样非常得益于数学建模期间培养的能力。能让我在研究的过程中快速获取信息、接受新知识,充分发挥团队合作精神等等。我为我选择数学建模感到无比的荣幸,没有它,或许我还在布满荆棘的道路上摸索着。数学建模是一盏永不泯灭的明灯,指引着我找寻正确的方向,并为之不懈奋斗下去。 “一份耕耘,一份收获”、“天行健,君子以自强不息”成为我也是所有数模人共同的心得写照。
最后,数学建模教学活动开展除提高大学生的综合素质和实践能力以及推进大学数学课程内容与方法改革外,我感触最深的是开展数学建模教学与竞赛活动,推广了数学认知。这点好,而且非常重要。通过数学建模教学及校竞赛,让我校学生有机会知道将所学的数学知识运用到解决实际问题中,同时通过全国竞赛,扩展了影响,消除用人单位一些认识上的误区,让大家更加深刻地体会到数学的魅力,亲近数学。
参考文献:
[1]李大潜. 中国大学生数学建模竞赛[M]. 北京:高等教育出版社,2008.
[2]姜启源,谢金星,叶俊.数学模型[M].北京:高等教育出版社,2003.
