2018-11-07
算法运用（读《智能科学技术导论》笔记）
学计算机玩的就是算法，算法之于程序员就如同菜谱之于厨师。人类通过编制算法，将智慧"植入"机器系统，算法越智慧，机器越智慧。
一、算法构造
算法：指解决一个（智能）计算问题具体步骤的集合。这个步骤需要通过一定的形式来呈现。
1、界定算法的性质
1）算法的性质
-
有序性
-
有限性：步骤有限
-
明确性
-
终止性：执行时间有限（but,也有例外，操作系统需永不终止）
2）算法内涵与算法表示之间的关系
-
算法内涵：指一个算法固有的功能本质，完成某一任务的具体步骤及其内在联系。
-
算法表示：具体给出的文本描述，可以有很多版本
-
它们两可以类比金庸的《神雕侠侣》：《神雕侠侣》只有一本书，但是却有很多版本的电视剧。
3）算法的效率
-
算法的效率：指执行一个算法程序所要花费的时空代价。
-
算法的计算复杂性（复杂性当量 O(f(n))）：一般情况下，我们仅仅从理论上来讨论算法的效率，即对于给定的输入数据规模(n)，一个算法需要动态执行多少个计算步骤（f(n)）。
-
问题本身的计算复杂性：期望能够找到问题的最低计算复杂性的算法。
4）算法的正确性
2、描述算法的伪代码
1）原语
-
原语：可以精确描述算法的形式语言就成为原语
-
原语=语法（规定原语中符号组合的规则）+语义（说明原语中符号及其组块的含义）
2）伪码
-
为了使描述算法的高级语言具有某种通用性，推出伪码作为原语。
-
伪码：是一种重在表达算法思想的非正式符号系统。
-
有时为了更直观表达算法的思想，常用流程图对伪码描述的算法作补充说明
3）具体规范
-
赋值语义结构：(变量)name<—expression(表达式)
-
条件语义结构：if(条件) then(活动1) else(活动2)
-
循环语义结构：
while(条件) do(活动)
repeat(活动) until(条件)
-
为了使得伪码更具可读性，一般规定语句之间用分号隔开，如果一个语句内部嵌有另一个语句，则采用缩进格式，相信会编程的同学都知道是怎么没一回事。
-
伪码还有一个类似于函数的定义——过程。一般过程的定义方式为：
**procedure** name(参量)
伪码段
引用之处直接用语句“ procedure name(参量）”
- 有时，为了使伪码可读性更高，在嵌套的语句中，每一层语句的结束都用明显的标识来醒目地加以标记，end while、end if
3、算法构造的过程
最重要的就是发现算法，本质上是一个理解、解决问题的过程
1）算法发现的四个阶段
参照美籍匈利亚数学家波利亚给出解决问题的一般原理，形成算法发现的如下四个阶段：
-
阶段一：理解问题
-
阶段二：寻找一个可能解决问题的算法过程（思路）
-
阶段三：阐明算法并且用伪码将其表达出来
-
阶段四：从准确度以及作为解决普适问题的一个工具的潜力这两个方面来评估这个算法。（这一步今天第一次见，值得深思）
2）想要增加解决问题的思路，可以去看美国科普作家加德纳所著的《啊哈，灵机一动》（这本书我也还没有看，是本书的作者老师推荐的，决定明年1月份之前读完）
3）能够解决复杂问题的逐步求精法
逐步求精：就是通过把复杂问题不断分解为子问题，直到分解的子问题能够给出解决思路，然后将子问题的解决思路一层层整合起来，最终给出总问题的解决思路。（从上而下，再从下而上。就像每次打包行李，先想好去哪带哪几类东西，再把要带的东西分块装好，最后把这些东西放到行李箱）
二、算法结构
推荐由美国学者纳希和希内德曼提出的N-S盒图来辅助分析算法的复杂结构
