内容简介 数学建模与问题求解 什么是数学模型 、数学模型分类 问题建模示例 ●四、数学模型与数据结构问题求解 雷涛 张铭 五、小结 ●参考资源 2007-12-28 什么是数学模型 伟大的科学模型及实践 我们常见的模型 地球板模型 玩具、飞机模型、火箭模型 实物模型 水箱中的舰艇、风洞中的飞机…□物理模型 地图、电路图、分子结构图…仁符号模型 生物DNA旋模型 初级数学模型一“航行问题 航行问题建模基本步骤 甲乙两地相距750公里,船从甲到乙顺水航行需3小时, ·作出简化假设(船速、水速为常数) 从乙到甲逆水航行需50小时,问船的速度是多少? 用x表示船遠,表示水速,列出方程: ·用符号表示有关量(y示船速和水速); 用物理定律(匀速运动的距高等于速度乘以 (x+y)×30=750cx=20 时间)列出数学公式(二元一次方程) (x-y)×50=750求解y=5 求解得到数学解答〔x=20,y=5) 答:船遠每小时20千米 回答原问题(船速每小时20千米)
1 数学建模与问题求解 张铭 2007-12-28 X1 X2 ………… XT O1 O2 OT ………… 内容简介 z 一、什么是数学模型 z 二、数学模型分类 z 三、问题建模示例 z 四、数学模型与数据结构问题求解 z 雷涛 z 五、小结 z 参考资源 玩具、飞机模型、火箭模型… ~ 实物模型 水箱中的舰艇、风洞中的飞机… ~ 物理模型 地图、电路图、分子结构图… ~ 符号模型 我们常见的模型 一、什么是数学模型 生物DNA螺旋模型 夸克粒子 模 型 社会演化模型 伟大的科学模型及实践 地球板块模型 宇宙大爆炸 模型 用 x 表示船速，y 表示水速，列出方程： ( ) 50 750 ( ) 30 750 − × = + × = x y x y 答：船速每小时20千米. 甲乙两地相距750公里，船从甲到乙顺水航行需30小时， 从乙到甲逆水航行需50小时，问船的速度是多少? x =20 y =5 求解 初级数学模型—“航行问题” • 作出简化假设（船速、水速为常数）； • 用符号表示有关量（x, y表示船速和水速）； • 用物理定律（匀速运动的距离等于速度乘以 时间）列出数学公式（二元一次方程）； • 求解得到数学解答（x=20, y=5）； • 回答原问题（船速每小时20千米）。 航行问题建模基本步骤
数学模型和数学建模 数学模型 模型:实际原型主要特征的抽象和简化 个低代价近似 对于一个现实对象, 数学模型:通过抽象和简化,使用数学语言对 为了一个特定目的, 实际对象的一个刻画,以便于人们 根据其内在规律, 更简明更深刻地认识所研究的对象 作出必要的简化假设, 数学建模:根据要求,针对实际问题 运用适当的数学工具 组建数学模型的全过程 (包括建立、求解、分析、检验等) 得到的一个数学结构。 数学建模的重要意义二、数学模型的分类额 电子计算机的出现及飞速发展 应用领域」人口、交通、经济、生态 数学以空前的广度和深度向一切领域渗透 数学方法」初等数学、微分方程、规划、图、统计、 数学建模作为用数学方法解决实际问题的第一步, 表现特性确定和随机 静态和动态 越来越受到人们的重视 恍派翼 离散和连续 线性和非线性 敦些桃 计机术 建模目的描述、优化、预报、决策、 知识经济 了解程度]白箱灰箱黑箱 模型的数学分类 三、问题建模示例 微分方程模型 ·差分方程模型 ·1雨中行走问题—初等数学 层次分析模型 2生产计划问题—线性规划模型 ●规划模型 ·3.椅子能放平吗?一高等数学 统计模型 ·4. Buffon投针实验——一模拟 图论模型 5.马氏链模型——统计模型 6.坐船问题——图论
2 数学模型和数学建模 数学模型：通过抽象和简化，使用数学语言对 实际对象的一个刻画，以便于人们 更简明更深刻地认识所研究的对象 数学建模：根据要求，针对实际问题， 组建数学模型的全过程 （包括建立、求解、分析、检验等） 模型：实际原型主要特征的抽象和简化 一个低代价近似 对于一个现实对象， 为了一个特定目的， 根据其内在规律， 作出必要的简化假设， 运用适当的数学工具， 得到的一个数学结构。 数学模型 • 电子计算机的出现及飞速发展 • 数学以空前的广度和深度向一切领域渗透 数学建模作为用数学方法解决实际问题的第一步， 越来越受到人们的重视。 数学建模 计算机技术 如虎添翼 知识经济 数学建模的重要意义 应用领域 人口、交通、经济、生态、… 数学方法 初等数学、微分方程、规划、图、统计、… 表现特性 建模目的 描述、优化、预报、决策、… 了解程度 白箱 灰箱 黑箱 确定和随机 静态和动态 离散和连续 线性和非线性 二、数学模型的分类 模型的数学分类 z 微分方程模型 z 差分方程模型 z 层次分析模型 z 规划模型 z 统计模型 z 模拟 z 图论模型 z …… 三、问题建模示例 z 1. 雨中行走问题——初等数学 z 2. 生产计划问题——线性规划模型 z 3. 椅子能放平吗？——高等数学 z 4. Buffon投针实验——模拟 z 5. 马氏链模型——统计模型 z 6. 坐船问题——图论
1.雨中行问题 雨中行问题建模 ·行人速度:(u,0,0),定速沿直线 问题:外出行走遇雨, ·雨速:(vx,y,Vz) 行走的距离:d 走多快才会少淋雨呢? 前、侧、顶面积之比1:L:T 分析:这一问题的主要因素有 降雨的大小 单位时间淋雨量:|u-Wx|+|wylL+|vz|T 降雨的方向 总淋爾量;R{u)=du.(|uWx|+lwy|L+vz|n 路程的远近和跑的快慢 数学问题:已知d,Vx,Ⅵy,V,求u为何值时 u)最小? 雨中行问题结论 2线性规划模型 R(u)=du.(u-刈+ylL+ⅣVzT 应用最广泛的方法之 如果迎着雨走(雨迎面和垂直落下) 最基本的方法之一。网络规划, ·尽可能快跑 整数规划,目标规划和多目标规 如果雨是从背后落下 划都是以线性规划为基础的。 控制行走速度 解决稀缺资源最优分配的有效方 ·使刚好等于雨滴速度的水平分量 法,使付出的费用最小或获得的 收益最大。 生产计划问题 生产计划问题模型 AB|备用资源 ·设产品AB产量分别为变量x,y 煤12 x+2y≤30 劳动日32 2y≤60 仓库02 2y≤24 利润40 A,B各生产多少,可获最大利润? max z= 40x+50y
3 1. 雨中行问题 z 问题：外出行走遇雨， 走多快才会少淋雨呢？ z 分析：这一问题的主要因素有 z 降雨的大小 z 降雨的方向 z 路程的远近和跑的快慢 雨中行问题建模 z 行人速度：(u,0,0 ) ，定速沿直线 z 雨速：(Vx,Vy,Vz) z 行走的距离：d z 前、侧、顶面积 之比1:L:T 单位时间淋雨量：｜u-Vx｜+｜Vy｜L+ ｜Vz｜T 总淋雨量：R(u) = d/u . (｜u-Vx｜+｜Vy｜L+ ｜Vz｜T) 数学问题：已知d，Vx， Vy，Vz，求u为何值时 R(u)最小？ 雨中行问题结论 z 如果迎着雨走(雨迎面和垂直落下) z 尽可能快跑 z 如果雨是从背后落下 z 控制行走速度 z 使刚好等于雨滴速度的水平分量 R(u) = d/u . (|u-Vx| + |Vy| L + |Vz| T) 2. 线性规划模型 z 应用最广泛的方法之一。 z 最基本的方法之一。网络规划， 整数规划，目标规划和多目标规 划都是以线性规划为基础的。 z 解决稀缺资源最优分配的有效方 法，使付出的费用最小或获得的 收益最大。 生产计划问题 A B 备用资源 煤 1 2 30 劳动日 3 2 60 仓库 0 2 24 利润 40 50 A, B各生产多少, 可获最大利润? x + 2y ≤ 30 3x + 2y ≤ 60 2y ≤ 24 x，y ≥ 0 max Z= 40x +50y 生产计划问题模型 z设产品A, B产量分别为变量x, y
一般线性规划模型8 决策变量:X,X 2ys24 目标函数:Max(min)Z=CX+CN2+,+CX auX +anX,+.+a,,(, sbr x+ 2ys30 约束条件,1+a2N3+…+aN1(=,公9 3x+2ys60 X;≥0(=1,,n) 线性规划问题求解 3.椅子在不平地面的稳定性 max(minZ=>c,x 问题分析還常三只脚着地放稳-四只脚着地 anx≤(=,2)b( ·四条腿一样长,椅脚与地面点接触,四脚 模连线呈正方形; 地面高度连续变化,可视为数学上的连续 ·可行解:凸集 最优解:在顶点上达到 地面相对平坦,使椅子在任意位置至少三 ·求解方法:单纯形法 ·软件包http://www.lindo.com 只脚同时着地 模型构成 模型构成 用数学语言表示椅子位置和四只脚着地的关系 用数学语言把椅子位置和四只脚着地的关系表示出来 椅子位量」利用正方形椅脚连线的对称性 用G对角线与轴的夹角表示椅子位置A 地面为连续曲面d八6,g(0是连续函数 四只脚着地椅脚与地面距离为零 椅子在任意位置 对任意af(0,g(0 距离是的函数 至少三只脚着地 至少一个为0 两个距离 (四只脚)正方形 数学己知几(6,g(是连续函数 对称性 问题 对任意6,·g(0=0 BD两脚与地面距离之和~g(6绕0扁 AC两脚与地面距离之和-八(6正方形ABC 且g(0)=0,f(0)>0. 证明:存在,使八B)=g()=0
4 0 Y X A D C B 3x + 2y ≤ 60 x + 2y ≤ 30 2y ≤ 24 20 Max(min)Z=C1X1+ C2X2+…+CnXn a11X1+ a12X2+…+ a1nXn ≥(=, ≤)b1 a21X1+ a22X2+…+ a2nXn ≥(=, ≤)b2 ……… am1X1+ am2X2+…+ amnXn ≥(=, ≤)bm Xj ≥0(j=1,…,n) 一般线性规划模型 目标函数： 约束条件： 决策变量： X1，X2，…，Xn 线性规划问题求解 z 可行解：凸集 z 最优解：在顶点上达到 z 求解方法：单纯形法 z 软件包 http: //www.lindo.com ∑= = n j j j Z c x 1 max(min) ⎪ ⎩ ⎪ ⎨ ⎧ ≥ = ∑ ≤ = ≥ = = 0 ( 1,2, , ) ( , ) ( 1,2, , ) . 1 x j n a x b i m st j n j ij j i " " 问题分析 模 型 假 设 通常 ~ 三只脚着地 放稳 ~ 四只脚着地 • 四条腿一样长，椅脚与地面点接触，四脚 连线呈正方形; • 地面高度连续变化，可视为数学上的连续 曲面; • 地面相对平坦，使椅子在任意位置至少三 只脚同时着地。 3. 椅子在不平地面的稳定性 模型构成 用数学语言表示椅子位置和四只脚着地的关系 • 椅子位置 利用正方形(椅脚连线)的对称性 x B A D C O C D´ ´ B ´ 用θ(对角线与x轴的夹角)表示椅子位置 A ´ • 四只脚着地 距离是θ的函数 四个距离 (四只脚) A,C 两脚与地面距离之和 ~ f(θ) B,D 两脚与地面距离之和 ~ g(θ) 两个距离 θ 椅脚与地面距离为零 正方形ABCD 绕O点旋转 正方形 对称性 用数学语言把椅子位置和四只脚着地的关系表示出来 f(θ) , g(θ)是连续函数 对任意θ, f(θ), g(θ) 至少一个为0 数学 问题 已知： f(θ) , g(θ)是连续函数 ; 对任意θ， f(θ) • g(θ)=0 ; 且 g(0)=0， f(0) > 0. 证明：存在θ0，使f(θ0) = g(θ0) = 0. 模型构成 地面为连续曲面 椅子在任意位置 至少三只脚着地
模型求解 给出一种简单、粗糙的证明方法 4.Buon投针实验 将椅子旋转90,对角线AC和BD豆换 ·随机模拟方法,也称为 Monte carl方法 由g(0=0,f0) 令(6=f6-8(6,则h(0>=0和h(r2)<0. 人为地造出一种概率模型,使它的某些参数 由g的连续性知h为连续函数,据连续函数的基本性 恰好重合于所需计算的量 质必存在,使加=0,即B)=8(a) 通过实验,用统计方法求出这些参数的估 因为(6·8(6-0,所以a)=8(=0. 值;把这些估值作为要求的量的近似值 评注和思考」建模的关键~硎A(,{(的确定 ·18世纪下半叶的法国学者Bun提出用 假设条件的本质与非本质考察四脚呈长方形的椅子 投针试验的方法来确定圆周率r的值。 ● Monte Carlo方法的最早的尝试! Buffon投针实验Buon实验结果 祖冲之(公元429-公元500 设针与平行线的夹角为φ,针 介于31415926和31415927之间(公元464年) 的中点与最近的平行线的距 离为X,相交条件为 学者年代d总次数成功π的 x<Lsin d 次数估计 18500850002532315956 smh18550.63204121831554 P=Pr[X≤ Sino dz)do 188407510304893.1595 Lazzarini19070833340818083.14159292 5. Markov链 「0.80.10.1|8 Markov观测A=030403 Markov模型:=(A,) 状态集 0.20.20.6 转移率矩阵 初始状态薇率向量 ·第一天天气 sunny R -sun-rain -rain A=0.3040.3 S3: Cloudy ·观察序列o={s1,S1sS1S2S2,S1,S P(o I Moel)=P(S1, S1, S1, S2, S2, S1, S3, S1 I Model P[1].P[S1/S1]P[S1S1].PIS2 S1] p[s2S2]P[s1 S2]P[S3S1]P[S1S3 1·0.8·0.8·0.1·04·0.3·0.1·0.2 =1536×104
5 模型求解 给出一种简单、粗糙的证明方法 将椅子旋转900，对角线AC和BD互换。 由g(0)=0， f(0) > 0 ，知f(π/2)=0 , g(π/2)>0. 令h(θ)= f(θ)–g(θ), 则h(0)>0和h(π/2)<0. 由 f, g的连续性知 h为连续函数, 据连续函数的基本性 质, 必存在θ0 , 使h(θ0)=0, 即f(θ0) = g(θ0) . 因为f(θ) • g(θ)=0, 所以f(θ0) = g(θ0) = 0. 评注和思考 建模的关键 ~ 假设条件的本质与非本质 考察四脚呈长方形的椅子 θ和 f(θ), g(θ)的确定 4. Buffon投针实验 z 随机模拟方法，也称为Monte Carlo方法， z 人为地造出一种概率模型，使它的某些参数 恰好重合于所需计算的量 z 通过实验，用统计方法求出这些参数的估 值；把这些估值作为要求的量的近似值 z 18世纪下半叶的法国学者Buffon提出用 投针试验的方法来确定圆周率π的值。 z Monte Carlo方法的最早的尝试！ Buffon投针实验 d L 设针与平行线的夹角为φ，针 的中点与最近的平行线的距 离为X，相交条件为: Buffon实验结果 π 的 估计 成功 次数 学者 年代 l/d 总次数 Lazzarini 1907 0.833 3408 1808 3.14159292 Fox 1884 0.75 1030 489 3.1595 Smith 1855 0.6 3204 1218 3.1554 Wolf 1850 0.8 5000 2532 3.15956 祖冲之（公元429 –公元500） 介于3.1415926和3.1415927之间(公元464年) 5. Markov链 S1 S2 S3 S1: Sunny S2: Rainy S3: Cloudy 0.8 0.1 0.1 0.3 0.4 0.3 0.2 0.2 0.6 A ⎡ ⎤ ⎢ ⎥ = ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ 0.8 0.1 0.1 0.4 0.3 0.3 0.2 0.6 0.2 π = [100] Markov模型: μ = (,) A π 状态集: 转移概率矩阵： 初始状态概率向量: Markov观测 z 第一天天气sunny z 接下来7天天气为sun-sun-rain-rain-sun-cloudysun…的概率是多少？ z 观察序列O={S1,S1,S1,S2,S2,S1,S3,S1} z P(O | Moel) = P(S1,S1,S1,S2,S2,S1,S3,S1 | Model) = P[1]•P[S1|S1] •P[S1|S1] •P[S2|S1] •P[S2|S2] •P[S1|S2] •P[S3|S1] •P[S1|S3] = π1•a11•a11•a12•a22•a21•a13•a31 = 1 • 0.8 • 0.8 • 0.1 • 0.4 • 0.3 • 0.1 • 0.2 = 1.536 × 10 -4 0.8 0.1 0.1 0.3 0.4 0.3 0.2 0.2 0.6 A ⎡ ⎤ ⎢ ⎥ = ⎢ ⎥ ⎢ ⎥ ⎣ ⎦
扩展和应用 四、图论模型与数据结构问题求解 ·OMM的每个状态代表一个事件( event) 尘船闷题(改躺自嶼南省信息学省队选 对应一个观察符号 observation) 披赛试题 HMM( Hidden markov model的每个 ·北大有n个拳生去公圆划船; observation对应一个 event每个状态以 不同概率发射不同的 observation ·一只条录多尘2个人 线性序列相关的应用 ·出于乐司的,火隶决定同船的2个人要么 语音识别、基因分析…… 同姐要么同名; ·每个人都必须上嘉,且一人不能上多只嘉 ·闷录力需要几只 例1 例2 ·姚金字,李佥字,姚◆宏,陈◆宏 ·陈◆宏,囧峰宏,罗*昏,廖叶子 酿◆囹昏盒 罗 ◆ 酿◆姚 享叶子 建模—图模型 图论问题 ·将备一学视为一顶点 顶点之阄的美集为同名戴看网媪 一畚边代表一种坐船的搭配方式 ·2名問学罔名或着罔龀迹一条边 用录少的边覆盖图中的点 ·一般图的录小边覆盖问题 般图录大匹配闷题,算濟复杂 她金李 李金李 陈◆宏 ◆宏 她金 李金李 ◆宏 她◆宏 6
6 扩展和应用 z OMM的每个状态代表一个事件(event), 对应一个观察符号(observation) z HMM (Hidden Markov Model)的每个 observation对应一个event,每个状态以 不同概率发射不同的observation z 线性序列相关的应用 z 语音识别、基因分析…… 四、图论模型与数据结构问题求解 坐船问题（改编自湖南省信息学省队选 拔赛试题） z北大有n个学生去公园划船； z一只船最多坐2个人； z出于娱乐目的，大家决定同船的2个人要么 同姓要么同名； z每个人都必须上船，且一人不能上多只船 z问最少需要几只船 例1 z姚金宇，李金宇，姚峰宏，陈峰宏 姚金宇 姚峰宏 陈峰宏 李金宇 姚金宇 李金宇 陈峰宏 姚峰宏 例2 z陈峰宏，囧峰宏，罗睿辞，廖叶子 陈峰宏 囧峰宏 罗睿辞 廖叶子 陈峰宏 囧峰宏 罗睿辞 廖叶子 z将每一同学视为一顶点 z顶点之间的关系为同名或者同姓 z 2名同学同名或者同姓就连一条边 建模——图模型 姚金宇 李金宇 陈峰宏 姚峰宏 图论问题 z 一条边代表一种坐船的搭配方式 z 用最少的边覆盖图中的点 z 一般图的最小边覆盖问题 z 一般图最大匹配问题，算法复杂， 实现麻烦。 姚金宇 李金宇 陈峰宏 姚峰宏
图转换成二叉树 问题的解决 ·树中一个点的左孩子跟其罔姓 ·对于图: 个地点的右子跟其同名 ·单独考虑原图条个迹遁分量 ·对于原图中的条一个迹遁分量,一定可 以转换成一根二叉树 ·合有n个点的逢遁分量,少需要n+1) dV2只 睿 ·条个迹遁分量需要总和,是问题的下界 罗贫中 罗納尔多罗中享睿鲁 ·对于一二叉树: ·使問介心油,一定可以构造出一个只需 享睿 罗州尔多 (n+1)d2只船的解 罗睿哔 罗睿 贪心构造 罗贯中鲁 ·1、若叶子站点是父杂的独生子,则耐 享睿 去它们2个,树依然保持恒质 罗鲕尔多 享睿辞候然是罗 ·2、若父亦地点睿2个减子 罗纳尔多是罗 睿峰的独生子 中的独生子, 将它们分成一血 井他们2个,树 然迹道 罗贯中罗睿 将到了一盘 录优解 重复以上步直圣树为空或者只利 罗纳余多享睿 个站地点为止 贪心举例 贪心举例 万金曲 酷◆宏 陈◆宏
7 图转换成二叉树 z树中一个结点的左孩子跟其同姓； z一个结点的右孩子跟其同名 z对于原图中的每一个连通分量，一定可 以转换成一棵二叉树 罗睿辞 罗贯中 罗纳尔多 廖睿辞 罗睿辞 罗贯中 罗纳尔多 廖睿辞 问题的解决 z对于图： z单独考虑原图每个连通分量 z含有n个点的连通分量，至少需要(n+1) div 2只船 z每个连通分量需要船总和，是问题的下界 z对于一棵二叉树： z使用贪心法，一定可以构造出一个只需 (n+1) div 2只船的解 罗睿辞 罗贯中 罗纳尔多 廖睿辞 罗纳尔多是罗贯 中的独生子，去 掉他们2个，树依 然连通 罗睿辞 廖睿辞 廖睿辞依然是罗 睿辞的独生子， 将它们分成一组 罗贯中 罗纳尔多 罗睿辞 廖睿辞 得到了一组 最优解 贪心构造 z 1、若叶子结点是父亲的独生子，则删 去它们2个，树依然保持性质 z 2、若父亲结点有2个孩子 重复以上步骤直至树为空或者只剩 一个结点为止 贪心举例 陈峰宏 贾 由 陈 云 王 云 贾 云 万金由 贪心举例 陈峰宏 贾 由 陈 云 王 云 贾 云 万金由
贪心举例 贪心举例 万金 陈◆虫 万金 陈◆宏 贪心举例 贪心举例 万金山 陈蜂尘 万金 陈◆宏 问题求解小结 五、小结 ·建棋是一个去粗取精的过租, 要尽可能利用对我们有利的信 数学建模的一般步骤 息,而忽略些与我们目标无 ●建模策略 兵的信息 ●数据结构中的问题建模 ·根据需要转化棋型(LCA与 RMQ问题之间相互转化,就是 村与序列相互辅助的经典创 子)
8 贪心举例 陈峰宏 贾 由 陈 云 王 云 贾 云 万金由 陈峰宏 贾 由 陈 云 王 云 贾 云 万金由 贪心举例 贪心举例 陈峰宏 贾 由 陈 云 王 云 万金由 贾 云 贪心举例 陈峰宏 贾 由 陈 云 王 云 万金由 贾 云 问题求解小结 z建模是一个去粗取精的过程， 要尽可能利用对我们有利的信 息，而忽略那些与我们目标无 关的信息 z根据需要转化模型（LCA与 RMQ问题之间相互转化，就是 树与序列相互辅助的经典例 子） 五、小结 z数学建模的一般步骤 z建模策略 z数据结构中的问题建模
建模的步骤 数学建模的一般步骤 针对问题特点和建模目的 模型准备八模型假设模型建立 模型假 作出合理的、简化的假设 在合理与简化之间作出折中 模型应用↓份析检验←匮型求 用数学的语言、符号描述问题 型 构发挥想象力 使用类比法 数学建模 成 尽量采用简单的数学工具 社会实践 理论研究 程序实现 数学建模的一般步骤 建模策略 模型 求解各种数学方法、软件和计算机技术 自顶向下,问题分解 ●归纳策略 模型如结果的误差分析、统计分析、 得到一种高度抽象的解题模型 分析模型对数据的稳定性分析 化繁为简,变未知为已知 ·A问题→B问题 模型与实际现象、数据比较, 检验检验模型的合理性、适用性 ·模拟策略:改变参数,观察变化 机模拟 模型应用 过程模拟 设计算法时通常考虑的因素 程序设计过程 模型必须尽量多地体现问题的本质特征 问题抽象:分析问题、建立数学模型 并不意味着模型越复杂越好 ·数据抽象:选择数据结构 累赞的信息会影响算法的效率 ·算法抽象:设计算法 模型需要反复修改 检验、修改,在实践中不断完善 用计算机语言实现 数学模型是程序的基础 程序=数据结构+算法
9 社会实践 理论研究 数学建模 程序实现 模型准备 模型应用 分析检验 模型求解 模型假设 模型建立 反馈 建模的步骤 模 型 假 设 针对问题特点和建模目的 作出合理的、简化的假设 在合理与简化之间作出折中 模 型 构 成 用数学的语言、符号描述问题 发挥想象力 使用类比法 尽量采用简单的数学工具 数学建模的一般步骤 模型 求解 各种数学方法、软件和计算机技术 如结果的误差分析、统计分析、 模型对数据的稳定性分析 模型 分析 模型 检验 与实际现象、数据比较， 检验模型的合理性、适用性 模型应用 数学建模的一般步骤 建模策略 z 自顶向下，问题分解 z 归纳策略 z 得到一种高度抽象的解题模型 z 化繁为简，变未知为已知 z A问题ÅÆB问题 z 模拟策略：改变参数，观察变化 z 随机模拟 z 过程模拟 设计算法时通常考虑的因素 z 模型必须尽量多地体现问题的本质特征 z 并不意味着模型越复杂越好 z 累赘的信息会影响算法的效率 z 模型需要反复修改 z 检验、修改，在实践中不断完善 z 数学模型是程序的基础 程序设计过程 z 问题抽象：分析问题、建立数学模型 z 数据抽象：选择数据结构 z 算法抽象：设计算法 z 用计算机语言实现 程序 = 数据结构 + 算法
数据结构定义 常见的逻辑关系 线性结构 数据逻辑结构 ●树形结构 逻辑/数据存储 ●图结构 ●数据的存储结构 结构 文件结构 数据的运算 运算 图二树二二叉树线性表 数据的存储结构 典型算法 问题规模,n ●映射:逻辑→存储 问题空间 ●四种存储结构 ·搜索(DFs,BFS) ·穷举(百钱买百鸡) 顺序 贪心( Huffman树) ·链接 递归 索引 ·回溯(八皇后) ·分治(二分法检索) 散列 动态规划最佳二叉排序树) 数据结构与算法 总结 理论 ●问题求解 算法的数学基础 算法的时间和空间度量 理论、抽象和设计的三个层次 抽象 根据实际问题取舍数据结构和算法 排序、检索等重要问题类的有效算法 ●在时间和空间复杂度之间进行平衡 重要数据结构技术 ●软件开发、工程的规范性 设计 ·算法的选择、实现和测试 实践、自主学习、研究创新能力
10 数据结构定义 z 数据逻辑结构 z 数据的存储结构 z 数据的运算 数据 存储 结构 逻辑 运算 常见的逻辑关系 z线性结构 z树形结构 z图结构 z文件结构 图⊇树⊇二叉树⊇线性表 数据的存储结构 z映射：逻辑 → 存储 z四种存储结构： z顺序 z链接 z索引 z散列 典型算法 z 问题规模，n z 问题空间 z 搜索(DFS, BFS) z 穷举 (百钱买百鸡) z 贪心(Huffman树) z 递归 z 回溯(八皇后) z 分治(二分法检索) z 动态规划(最佳二叉排序树) 数据结构与算法 z 理论 z 算法的数学基础 z 算法的时间和空间度量 z 抽象 z 排序、检索等重要问题类的有效算法 z 重要数据结构技术 z 设计 z 算法的选择、实现和测试 总 结 z 问题求解 z 理论、抽象和设计的三个层次 z 根据实际问题取舍数据结构和算法 z 在时间和空间复杂度之间进行平衡 z 软件开发、工程的规范性 z 实践、自主学习、研究创新能力
