当前课程知识点：电子信息科学与技术导引(1) > 第六讲：数据与算法 > 第五节：数值分析问题研究 > 第五节：数值分析问题研究
我们可以把算法分为两大类
数值算法和非数值算法
我们前面讨论的
可以采用图模型描述的
路径规划货币兑换
汉语分词四色定理
这些都属于非数值问题
解决他们的方法
属于非数值算法
另一大类算法是数值算法
也被成为数值分析
或者说科学计算
这些算法用于解决
科学和工程领域中
大量的数学问题
典型的问题有
线性方程组非线性方程
拟合和插值
数值积分和微分
矩阵的相乘求逆和分解
以及函数极值和最优化问题
我们也来看一个例子
如果知道因变量y和自变量x
是线性关系
那么就可以通过
实验中多次观测值
来求解这个线性系数
这被称为线性拟合
在很多物理实验当中
比如测定
匀变速运动的加速度
力和弹簧长度的关系
测定金属的电阻率等等
都会用到线性拟合这个方法
假设我们有5个数据点
（x1，y1）（x2，y2）
一直到（x5，y5）
拟合问题的数学模型为
y = a × x + b
我们就是要用
这5个数据点的值
来拟合这个线性表达式中的
斜率a和截距b
因此这是一个
线性方程组求解的问题
我们可以看到
这个线性方程组中
有五个方程
但是只有两个变量
这就是所谓的超定方程
超定方程在一般情况下
不存在解
因此我们可以利用
最小二乘法拟合得到
最优的斜率和截距
数值问题有自己的特点
在数值问题中
变量取值是连续的
我们满足于得到一个
符合精度要求的近似解
尽管这样的近似解
可能有无穷多个
在数值问题中
我们更关心的是接的可靠性
和精确性
数值算法面对很多来自
科学和工程领域的实际问题
具有很长的历史
数值算法的很多概念和方法
在20世纪之前就被提出了
在计算机出现之前
我们主要依靠手工计算
因此远远不能满足
实际工作的需要
而正是求解数值问题的
巨大需求
推动了计算机的诞生
第二次世界大战期间
美国陆军军械部
在马里兰州阿伯丁
设立了一个
弹道研究实验室
来开展导弹
这种新武器的研究
这个实验室
每天需要提供6张火力表
来对导弹的研制
进行技术鉴定
每张火力表
都需要计算几百条弹道
弹道的数学模型
是一组复杂的非线性方程组
按照当时的能力
200多名计算员
加班加点的工作
也大约需要
二个多月的时间
才能算完一张火力表
因此我们可以清楚的看到
能力和需要之间
存在着巨大的差距
因此有一项新的研究计划
得到了美国政府的支持
1942在宾夕法尼亚大学启动了
电子计算机的研制工作
经过将近4年的努力
到1946年的2月15日
世界上第一台可以实际运行的
电子计算机ENIAC宣告诞生
虽然相比于我们今天的计算机
ENIAC体积庞大耗电惊人
而它的运算速度不过
每秒几千次
但是比起当时已有的计算装置
ENIAC已经要快1000倍
而且它还能按照
事先编好的程序
自动执行算数运算
逻辑运算和数据存储的功能
ENIAC宣告了
一个时代的开始
从此科学计算的大门
也被打开了
正是数值分析的需求
推动了计算机的诞生
而计算机不断增长的
计算和存储能力
也促进了数值分析的发展
和向更多的领域渗透
人们后来发现
计算机同样适于处理
数值计算以外的问题
这就是我们前面介绍的
非数值问题和非数值算法
到今天
非数值算法的重要性
甚至超过了数值算法
现在世界上计算机的
大部分时间
都是被用来处理非数值问题
那么有哪些是非数值问题呢
有我们前面已经介绍过的
在图结构模型上定义的
旅行商问题地图着色问题
也有最基础的
排序和查找问题
大家每天使用的搜索引擎
就是以排序和查找
这两种算法作为基础的
当然还有大量的
组合优化问题
非数值算法的特点是
尽管解空间可能很庞大
但是他的解都是离散的
我们对于非数值问题
我们关心的是
解的存在性
唯一性和最优性
我们怎么评价一个算法呢
主要有三个标准
第一个是算法的正确性
也就是算法得到的结果
是否是正确的
这是对算法最基本的要求
在这里我们需要注意一点
有的时候我们会设计一些
近似的算法
这些近似算法所得到的算法
可能并不是严格正确的
但这是算法设计的时候
考虑各种因素得到的结果
因此符合预期的结果
仍然是正确的
第二是解的最优性
在一些场合
得到最优解的代价太大
我们也会满足于
得到一个次优解
这是收益和代价的折中
这就是所谓的
天下没有免费的午餐
第三是算法的效率
包括算法的时间复杂度
和空间复杂度
我们这里也可以给一个例子
就是所谓的字节的比特逆序
一个字节有8个比特位
比特逆序就是把他的比特位
逆序排列
比如我们输入的字节是
11100101
我们希望得到的输出
是他的逆序也就是
10100111
那么我们要求设计一个算法
能够以最高的效率
实现对任意输入的字节
进行逆序
那么怎么来做呢
我们当然可以用
程序语言中的比特操作
但这样的一些位操作
会是算法很复杂
我们可以换一种思路
因为一个字节
只有8个比特位
所以例举所有的字节
一共也只有256个
因此我们可以采用一个
长度为256的一维数组
来实现这个逆序算法
数组的每个元素
取值恰好是下标的逆序
当一个新的字节输入的时候
我们就可以通过查表操作
直接得到逆序的结果
经过前人在这个领域的
长期努力
我们现在已经逐步形成了
算法设计的主要思想
包括蛮力法分治法
和变治法
动态规划和贪心算法
搜索算法还有随机算法
常见的算法优化技术包括
预构造时空平衡
和输入增强
在面对实际问题的时候
这些算法设计的思想
对我们思考和设计
具体的算法
具有重要的指导意义
-第一节 序言
--第一节 序言
-第二节 电磁学和分析数学发展史：磁学
-第三节 电磁学与分析数学发展史：静电
-第四节 电磁学和分析数学发展史：动电
-第五节 电子器件的发明及电子技术的发展
-第六节 电磁学的广泛应用
-第七节 电磁系统理论
-第八节 电子科学技术各学科间的关系
-第九节 电子科学技术的学科体系
-第一讲：电磁学与分析数学史概览--第一次作业
-第一节 序言
--第一节 序言
-第二节 电磁场（一）
-第三节 电磁场（二）
-第四节 物质
--第四节 物质
-第五节 电磁场与物质的相互作用：非共振作用
-第六节 电磁场与物质的相互作用：共振作用
-第七节 电磁场理论与电路理论
-第一节 空间离散化
-第二节 静场电路分析
-第三节 非静场电路抽象
-第三讲：电路抽象--电路抽象 练习题
-第四节 电路元件抽象
-第五节 非线性元件抽象
-第六节 电路抽象三原则
-第七节 分层抽象思想
-第八节 电路基本问题
-第九节 数字化抽象
-第三讲：电路抽象--Quiz 3
-第一节 序言
--第一节 序言
-第二节 什么是比特
-第三节 比特与编码
-第四节 比特与信息
-第五节 比特的用途示例
-第六节 什么是逻辑
-第七节 逻辑的用途示例
-第八节 与数字电路的关系
-第九节 小结
--第九节 小结
-第四讲：比特与逻辑--Quiz4
-第一节：从算盘到ENIAC
-第二节：通用计算机模型
-第三节：指令集体系结构
-第四节：程序和程序设计语言
-第五节：处理器的工作原理
-第六节：性能问题
--第六节：性能问题
-第七节：小结
--第七节：小结
-第一节：数据与数据处理技术的发展
-第二节：数据处理举例
-第三节：数据模型和算法的概念
-第四节：问题的抽象和建模
-第五节：数值分析问题研究
-第六节：数据和算法的关系I
-第七节：数据和算法的关系II
-第八节：大数据
--第八节：大数据
-第九节：数据挖掘技术和数据算法的展望
-第六讲：数据与算法--Quiz6
-第一节：基本内容简介
-第二节：信息的基本概念和传输的几种方式
-第三节：交换的概念和网络的几种形式
-第四节：模拟与数字通信
-第五节：调制和解调
-第六节：传输涉及的基本理论
-第七节：信息论和几种相关的编码方式
-第八节：多址方式
--第八节：多址方式
-第九节：交换的基本概念
-第十节：网络分层的基本概念
-第十一节：互联网的基本原理和有限状态机模型
-第七讲：通讯与网络--Quiz7
-第一讲：内容简介
--第一讲：内容简介
-第二讲：信息与媒体
-第三讲：人类感知与认知
-第四讲：智能信息处理
-第五讲：媒体与认知相互作用
-第六讲：媒体认知应用
-第七讲：总结
--第七讲：总结
-第八讲：媒体与认知--Quiz8
-期末考试--Final Exam
