资源描述：
《算法和算法复杂性(1)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、专题一:算法与复杂性基本概念1、可计算性与算法算法是用于求解严格确定的计算问题,能准确和全面理解的一系列指令。相应于算法的数学实体就是英国数学家图灵（Turing）1936年提出的图灵机。图灵机是一种抽象化的计算机，一种标准的计算模型。由三部分组成：无限长的带、在带上可以左右移动的读写头和控制读写头的控制器。图灵机中无限长的带被分成一个个小空格，每格容纳一个符号，对每一部图灵机而言，带上允许使用的符号是有限的；图灵机的输入是由符号组成的有限序列，称之为符号行，输入符号行不能含空格符B。读写头每次左或右移动一格，并根据控制器的指令阅读方格中的符号或抹去、重写方格中的符号
2、，其初始位置是输入符号行最左边符号。读写头带（B表示空格）B011000B控制器控制器有有限个状态，其中启始状态和终止状态是两个特殊的状态；状态可依转移函数δ进行，δ（q，a）=（p，b，v）意为：读写头看到符号a时，处于状态q的控制器命令其抹掉a，重写b，并向v（左或右）移动一格，状态改变为p；控制器开始处于启始状态，图灵机当且仅当控制器处于终止状态时停止，此时带上符号行为输出。显然，图灵计算机计算的是从符号行到符号行的函数，但并不太限制其应用范围,它的计算时间是指读写头的移动次数,计算占用的空间是指带上被访问过的方格数,当输入符号行是x时,图灵机M的计算时间(或占
3、用空间)记为TimeM(x)(或SpaceM(x))。对意义明确的数学问题是否会不存在算法呢？图灵精彩地论证了这样的不可判定问题确实存在！一个典型问题就是“停机问题”：给定一个带有输入的计算机程序，它会停机吗？图灵证明了，不存在一个算法能对该问题的一切例子给出正确的答案。对于给定的问题，如果存在一种算法，可以对该问题的一切例子给出正确的答案，那麽这个问题就是可以计算的。可重复性归根于因果关系的确定性，这种确定性也是当今世界上存在的各式各样计算机的共同特点。2、不确定型计算和算法复杂性（1）不确定型计算：一个不确定型图灵机M计算一函数f（x）时，必须假定M满足以下条件：
4、①若f(x)无定义,则对输入x,M的任何计算道路都是(时间)无限长的;②若f(x)有定义,则对输入x,M必有一有限长的道路；并且对任何有限长的计算道路，计算结果都是f(x)。对这种图灵机M，TimeM（x）表示输入x时，M可能使用的最短时间，SpaceM（x）表示输入x时，M可能使用的最少空间。可以在不确定型计算机上实施的计算称为不确定型计算。（Non-deterministiccomputation）&算法复杂性采用该算法得到最终答案时所用的时间。与此有关的因素有：·计算机本身的速度·问题的规模——一般指问题的输入长度（2）算法复杂性与算法分析为了衡量算法的效果所广
5、泛采用的标准是：注意：同一规模的例子用同一算法，同样的输入长度所需运算时间也可能相差很远！如，用单纯形法解LP，即使约束条件的系数矩阵阶数固定不变，所需的初等运算次数也会随着参数A、b、C的不同而有较大差别。当取C≤0的极端情况，不需要进行旋转运算，初始可行解就是最优解；但若选取不利的参数，达到最优解所需要的迭代步骤可能就非常多。为了避免由于不同输入而对算法行为产生巨大差别，考察所有规模为n的输入，对这些算法的不同行为中的最坏行为定义为该算法关于输入规模为n的复杂性。因此，算法复杂性是输入规模的函数，比如10n3,2n,nlog2n等。输入规模足够大时，在复杂性函数中
6、，增长速度较慢的项（如nlog2n+5n），终将被增长速度很快的项超过（该例中n>>1000时，nlog2n>5n）。在算法复杂性研究中，只有当输入规模很大时，研究其计算行为才有意义，因为：只有规模大的输入，才能确定算法可应用性的限制。比如复杂性为10n3与复杂性为9n3的算法间的差别可以忽略不计，因为这可以通过技术革新，使计算机速度提高10倍而得到补偿。(c)如果存在两个常数c,c'>0,使得当n足够大时有c'g(n)≤f(n)≤cg(n),则记f(n)=Θg(n)，用记号f(n)≌g(n)代替f(n)=Θ(g(n)),易见≌是一个等价关系，在该等价关系下，f(n)
7、的等价类（即f(n)=Θ(g(n))的所有g(n)的集合）称为f(n)的增长速度。定义设f(n),g(n)是定义在正整数上的正实值函数(a)如果存在一个常数c>0,使得当n足够大时,有f(n)≤cg(n),则记f(n)=O(g(n))；(b)如果存在一个常数c>0,使得当n足够大时有f(n)≥cg(n),则记f(n)=Ω(g(n))；求出一个算法所需时间比较好上界的过程称为算法分析。算法分析中常常使用初等运算——算术运算、比较、转移指令等的步数表示一个算法在假设的计算机上执行时所需的时间，即每做一次初等运算，需要一个单位时间。而用算法的输入规模的函数
