当前课程知识点：电子信息科学与技术导引(1) > 第六讲：数据与算法 > 第四节：问题的抽象和建模 > 第四节：问题的抽象和建模
我们介绍过
算法通过一系列确定的步骤
来解决问题
这里面就反应了算法的
两个重要特点
一个是问题抽象化
一个是方法一般化
也就是说我们在处理
一个问题的时候
需要把它抽象为
一个和场景无关的问题
这是一个为问题
建立数学模型的过程
当我们为问题
设计了一个算法
解决的不仅仅是
某一个特定的问题
而是为一类问题
找到了一般性的解决方案
这就是方法一般化
图是一种描述能力很强的
结构模型
很多现实世界的问题
都可以用图的模型来描述
我们这里举几个例子
人们在出门旅行之前
都需要安排自己的行程
比如同学们离开家乡
到外地上大学
在学期开始之前就需要考虑
如何从家乡前往学校所在地
你们可能会选择
路径长度最短
或者旅行时间最少
或者票价最便宜等等
我们就可以
用图来描述这个问题
把距离时间和价格
作为边上的权重
就可以设计一个
寻找最短路径的算法
来求解这个问题
旅行商问题是算法中的
一个著名的例子
也称为货郎担问题
这个问题是说
有一个商人
要前往很多城市
希望设计一条线路
使他能够经过
所有的目标城市
并且只经过一次
旅行商问题在物流和交通领域
都有很多应用
生物界的一个例子就是蜜蜂
蜜蜂每天都要出去采蜜
需要在不同的花朵间飞行
为了提高效率
实际上蜜蜂每天都在解决
旅行商问题
旅行商问题
是一个很难的问题
也是所谓的NP问题中
一个经典案例
不同的国家都会
发行和使用不同的货币
人们在跨国旅行的时候
就需要去兑换货币
兑换需要按照汇率进行
那么不同货币之间的兑换关系
就能构成一张图
汇率就是这张图中
边上的权重
我们可以问这样一个问题
能否在这张图上
找到一条货币兑换的路径
使得通过货币兑换的过程
让一个人
所持有的货币增加了
比如我们可以
从100元人民币开始
先兑换成美元
然后是欧元英镑加元
澳元港币
最后回到人民币的时候
我们期望他的数量
会大于100
如果有这样的方法
我们就可以实现财富的增值
当然由于汇率
是时刻变化的
进行这样的操作
也有很大的可能性
不是财富的增值而是缩水
汉语书写上的一个特点
就是字和字之间没有空格
所以朗读和理解
一个汉语的句子
首先要断句
也就是把句子切成词
这就是汉语的分词问题
对一个句子可能存在
不同的分词方式
这是导致汉语句子
理解歧义的主要来源之一
比如说对这样一个句子
我们既可以把他读成
南京市长江大桥
也可以把他读成
南京市长江大桥
从语法的角度来看
这两种分词方法都是合理的
但从语义上理解
我们会更倾向于前者
因为至少到目前为止并没有
一个南京市长叫江大桥
这就是分词不同导致
句子含义的完全不同
这样的例子很多
比如这个句子
我们可以把它读为
这样的人才能经受住考验
也可以把它读为
这样的人才能
经受住考验
还有这个句子
我们既可以把它理解为
这苹果不大好吃
也可以把它理解为
这苹果不大好吃
这两种读法
对于苹果是否好吃的评价
是完全不同的
分词是自然语言处理的
基础性问题
它也可以用图的模型来描述
并寻找求解方法
接下来的一个例子
介绍的是四色定理
四色定理和费马大定理
哥德巴赫猜想并称
世界近代三大数学难题
1852年，毕业于伦敦大学的
弗兰西斯古色利
在进行地图着色工作的时候
首先提出了四色猜想
这个猜想说
在一个平面或者球面上
任何地图能够
只用4种颜色来着色
使得没有两个相邻的国家
有相同的颜色
那么这个命题有两个约束
第一每个国家必须
由一个单连通域构成
比如不允许非闭的存在
就像阿拉斯加
是美国的领土
但阿拉斯加和美国的
其他领土是分离的
这种情形
在这个问题里不考虑
另一个约束是
两个国家相邻
是指他们有一段公共的边界
而不仅有一个公共点
这看起来非常直观
并不困难的问题
却难倒了很多著名的数学家
到1872年英国当时
最著名的数学家凯利
正式向伦敦数学学会
提出了这个问题
于是四色猜想成为
世界学术界关注的问题
很多数学家
都尝试去解决这个问题
但都没有获得成功
一直到1976年
美国数学家阿佩尔和哈肯
在计算机上用了1200个小时
做了100亿次判断
终于完成了四色定理的证明
四色猜想的计算机证明
轰动了世界
因为它不仅解决了
一个历时100多年的难题
而且是第一个借助计算机
证明的定理
不过还有不少数学家
并不太满足于
用计算机去证明一个定理
他们继续在寻找
一种简洁明快的
书面证明方法
来证明四色定理
在这个地图着色的问题当中
如果我们把国家作为点
边境作为边
那么四色定理就转化为
在图上相邻节点都要用
不同的颜色着色的问题
从上面这些例子
我们可以看到
路径规划货币兑换
中文分词四色定理
都是完全不同的问题
但我们都可以
用图这样的结构模型
来描述这些问题
把它们从实际背景中
抽象出来
成为图结构上的问题
这就是我们所说的
问题抽象化
算法是由一系列
确定的步骤组成的
是问题的程序化解决方案
算法并没有给出问题的答案
但是精确定义了
问题的求解过程
大家在读书的时候
考试结束以后
可能会经常在一起对答案
如果答案对了就很高兴
答案错了就会有些沮丧
这时候老师可能会对大家说
方法比答案更重要
因为答案是对特定问题的
而掌握方法则让你具有了
解决这一类问题的能力
一个算法能够解决很多
看似毫无关系的问题
只要这些问题
能够被抽象成为
同样数学模型下的相同问题
这种一般化的特性
反映了算法的价值
我们现在所说的算法
一般来说指的都是
计算机算法
因为计算机已经成为
实现算法的最有效工具
程序语言
是描述和实现算法的载体
因此学习利用计算机
解决实际问题
掌握程序语言是基础
算法的实现能力才更为重要
-第一节 序言
--第一节 序言
-第二节 电磁学和分析数学发展史：磁学
-第三节 电磁学与分析数学发展史：静电
-第四节 电磁学和分析数学发展史：动电
-第五节 电子器件的发明及电子技术的发展
-第六节 电磁学的广泛应用
-第七节 电磁系统理论
-第八节 电子科学技术各学科间的关系
-第九节 电子科学技术的学科体系
-第一讲：电磁学与分析数学史概览--第一次作业
-第一节 序言
--第一节 序言
-第二节 电磁场（一）
-第三节 电磁场（二）
-第四节 物质
--第四节 物质
-第五节 电磁场与物质的相互作用：非共振作用
-第六节 电磁场与物质的相互作用：共振作用
-第七节 电磁场理论与电路理论
-第一节 空间离散化
-第二节 静场电路分析
-第三节 非静场电路抽象
-第三讲：电路抽象--电路抽象 练习题
-第四节 电路元件抽象
-第五节 非线性元件抽象
-第六节 电路抽象三原则
-第七节 分层抽象思想
-第八节 电路基本问题
-第九节 数字化抽象
-第三讲：电路抽象--Quiz 3
-第一节 序言
--第一节 序言
-第二节 什么是比特
-第三节 比特与编码
-第四节 比特与信息
-第五节 比特的用途示例
-第六节 什么是逻辑
-第七节 逻辑的用途示例
-第八节 与数字电路的关系
-第九节 小结
--第九节 小结
-第四讲：比特与逻辑--Quiz4
-第一节：从算盘到ENIAC
-第二节：通用计算机模型
-第三节：指令集体系结构
-第四节：程序和程序设计语言
-第五节：处理器的工作原理
-第六节：性能问题
--第六节：性能问题
-第七节：小结
--第七节：小结
-第一节：数据与数据处理技术的发展
-第二节：数据处理举例
-第三节：数据模型和算法的概念
-第四节：问题的抽象和建模
-第五节：数值分析问题研究
-第六节：数据和算法的关系I
-第七节：数据和算法的关系II
-第八节：大数据
--第八节：大数据
-第九节：数据挖掘技术和数据算法的展望
-第六讲：数据与算法--Quiz6
-第一节：基本内容简介
-第二节：信息的基本概念和传输的几种方式
-第三节：交换的概念和网络的几种形式
-第四节：模拟与数字通信
-第五节：调制和解调
-第六节：传输涉及的基本理论
-第七节：信息论和几种相关的编码方式
-第八节：多址方式
--第八节：多址方式
-第九节：交换的基本概念
-第十节：网络分层的基本概念
-第十一节：互联网的基本原理和有限状态机模型
-第七讲：通讯与网络--Quiz7
-第一讲：内容简介
--第一讲：内容简介
-第二讲：信息与媒体
-第三讲：人类感知与认知
-第四讲：智能信息处理
-第五讲：媒体与认知相互作用
-第六讲：媒体认知应用
-第七讲：总结
--第七讲：总结
-第八讲：媒体与认知--Quiz8
-期末考试--Final Exam
