算法和算法复杂性(1)-课件（PPT演示稿）.ppt

专题一专题一: : 算法与复杂性算法与复杂性基本概念 1 1、可计算性与算法、可计算性与算法算法算法是用于求解严格确定的计算问题,能准确和全面理解的一系列指令。相应于算法的数学实体就是英国数学家图灵( Turing )1936 年提出的图灵机。图灵机是一种抽象化的计算机,一种标准的计算模型。由三部分组成: 无限长的带、在带上可以左右移动的读写头和控制读写头的控制器。图灵机中无限长的带被分成一个个小空格,每格容纳一个符号,对每一部图灵机而言,带上允许使用的符号是有限的; 图灵机的输入是由符号组成的有限序列,称之为符号行,输入符号行不能含空格符 B。读写头每次左或右移动一格,并根据控制器的指令阅读方格中的符号或抹去、重写方格中的符号,其初始位置是输入符号行最左边符号。读写头带(B表示空格) B 0 1 1 0 0 0 B 控制器控制器有有限个状态,其中启始状态和终止状态是两个特殊的状态;状态可依转移函数δ进行, δ(q,a)=(p,b,v)意为:读写头看到符号 a时,处于状态 q的控制器命令其抹掉 a,重写 b,并向 v(左或右) 移动一格,状态改变为 p; 控制器开始处于启始状态,图灵机当且仅当控制器处于终止状态时停止,此时带上符号行为输出。显然,图灵计算机计算的是从符号行到符号行的函数,但并不太限制其应用范围,它的计算时间是指读写头的移动次数,计算占用的空间是指带上被访问过的方格数,当输入符号行是 x时,图灵机 M的计算时间(或占用空间)记为 Time M (x ) (或 Space M (x ))。对意义明确的数学问题是否会不存在算法对意义明确的数学问题是否会不存在算法呢? 呢? 图灵精彩地论证了这样的不可判定问题这样的不可判定问题确实存在! 确实存在! 一个典型问题就是““停机问题停机问题””: 给定一个带有输入的计算机程序,它会停机吗? 图灵证明了,不存在一个算法能对该问题的一切例子给出正确的答案。对于给定的问题,如果存在一种算法,可以对该问题的一切例子给出正确的答案,那麽这个问题就是可以计算可以计算的。可重复性归根于因果关系的确定性因果关系的确定性,这种确定性也是当今世界上存在的各式各样计算机的共同特点。 2 2、不确定型计算和算法复杂性、不确定型计算和算法复杂性( (1 1)不确定型计算: )不确定型计算: 一个不确定型图灵机一个不确定型图灵机 M M计算一函数计算一函数 f f( (x x) ) 时,必须假定时,必须假定 M M满足以下条件: 满足以下条件: ①若f(x )无定义,则对输入 x, M 的任何计算道路都是(时间)无限长的; ②若f(x )有定义,则对输入 x, M 必有一有限长的道路;并且对任何有限长的计算道路,计算结果都是 f(x )。对这种图灵机 M,Time M(x)表示输入 x时, M可能使用的最短时间,Space M(x) 表示输入 x时, M可能使用的最少空间。可以在不确定型计算机上实施的计算称为不确定不确定型计算型计算。(Non-putation ) & &算法复杂性算法复杂性采用该算法得到最终答案时所用的时间采用该算法得到最终答案时所用的时间。与此有关的因素有: ·计算机本身的速度计算机本身的速度·问题的规模问题的规模——一般指问题的输入长度( (2 2)算法复杂性与算法分析)算法复杂性与算法分析为了衡量算法的效果所广泛采用的标准标准是: 注意: 注意: 同一规模的例子用同一算法,同样的同一规模的例子用同一算法,同样的输入长度所需运算时间也可能相差很远! 输入长度所需运算时间也可能相差很远! 如,用单纯形法解如,用单纯形法解 LP LP ,即使约束条件,即使约束条件的系数矩阵阶数固定不变,所需的初等运算的系数矩阵阶数固定不变,所需的初等运算次数也会随着参数次数也会随着参数 A A、、b b、、C C 的不同而有较大的不同而有较大差别。当取差别。当取 C C≤≤0 0 的极端情况,不需要进行旋的极端情况,不需要进行旋转运算,初始可行解就是最优解;但若选取转运算,初始可行解就是最优解;但若选取不利的参数,达到最优解所需要的迭代步骤不利的参数,达到最优解所需要的迭代步骤可能就非常多。可能就非常多。为了避免由于不同输入而对算法行为产生巨大差别,考察所有规模为 n的输入, 对这些算法的不同行为中的对这些算法的不同行为中的最最坏行为坏行为定义为该算法定义为该算法关于输入规模为关于输入规模为 n n 的复杂性的复杂性。因此,算法复杂性是输入规模的函数,比如 10n 3,2 n,nlog 2n等。