文档介绍：第2章程序算法与图灵机模型
第一页，共44页
算法
什么是算法？
指完成一个任务所需要的具体步骤和方法。
即给定初始状态或输入数据，经过计算机程序的有限次运算，能够得出所要求或期望的终止状态或输出数据。
第二页，共44页
算法的特点：
(1)有穷性
算法中每一条指令的执行次数有限，执行每条指令的时间有限。(对任何的合法输入，算法总能在运算有限步后终止)
(2)确定性
组成算法的每条指令是清晰的，无歧义的。
(3)输入
一个算法有零个或多个输入。
(4)输出
一个算法至少产生一个量作为输出。
(5) 可行性
算法中的运算是能够实现的基本运算，每一种运算可在有限的时间内完成。
第三页，共44页
一些经典的算法
思考：
求两个数的最大公约数如何实现？P27
排序之冒泡排序(在排序过程中总是小数往前放，大数往后放，相当于气泡往上升)
二分法之求函数的解
(对于函数f(x),如果存在实数c,当x=c时，若f(c)=0,那么把x=c叫做函数f(x)的零点。解方程即要求f(x)的所有零点。)
第四页，共44页
1365和3654 两数的最大公约数？
步骤：
3654÷1365 给出余数924
　　1365÷924 给出余数441
　　924÷441 给出余数42
　　441÷42 给出余数21
　　42÷21 给出余数0。
因此，用于做除数的21即是所需要的最大公
约数。
第五页，共44页
欧几里德算法逻辑运算的流程图
连续减法找到除法余数的流程图
第六页，共44页
图灵“机” 是一段“抽象数学”，是一种抽象计算模型（通用计算模型）而不是一个物理对象。
用来精确定义可计算函数——部分可计算函数与可计算函数。
其目的是为了解决称为判决问题的一个范围广阔的问题。
通过研究图灵机，来研究递归可枚举集（recursively enumerable）和部分递归函数（partial recursive function）
对算法和可计算性进行研究提供形式化描述工具。
图灵机模型
第七页，共44页
图灵机缘起
1900,德国数学家希尔伯特(D. Hilbert )在巴黎第二届数学家大会上提出"23个数学难题"中,
逻辑的完备性问题,即是否所有数学问题原则上都可解.
1936, 英国数学家图灵
“论可计算数及其在判定问题中的应用”(On Computable Numbers With an Application to the Entscheidungs Problem)
结论：
可解的问题是能够用"图灵机"的自动机理论模型表达的问题.
第八页，共44页
希尔伯特第十问题——
数学问题的一般算法步骤问题（原则上是否存在一般数学问题的解题步骤的判决问题
如何判定整系数多项式是否有整数根? 要求使用
“有限次运算的过程”
自由停机问题
存在某种完全自动地回答一般问题（停机问题）的算法步骤吗？
通过证明不存在决定图灵机停机问题的算法来证明不存在判定所有数学问题是否可解的问题。
1970 年证明不存在这样的判定算法, 即这个问题是
不可判定的, 或不可计算的.
第九页，共44页

图灵把人在计算时所作的工作分解成简单的动作。
机器计算需要：
(1) 存储器（存储计算结果）
(2) 一种语言（表示运算和数字）
(3) 扫描
(4) 计算意向（计算过程中知道下一步做什么）
(5) 执行下一步计算
第十页，共44页