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