Video在线视频

在没有接触计算机之前

或者

对计算机只有初步了解的时候

每一个人都对计算机

充满了好奇和惊异

感觉计算机什么事情都能做

比如科学计算

文字处理

网络游戏

算命

下棋

甚至网上追（捕）逃（犯）等等

简直太神奇了

果真如此吗

不 事实上

不是什么问题

计算机都能予以计算的

换句话说有些问题

计算机能计算

有些问题不能计算

有些问题虽然能计算

但算起来很困难

这就引出了

可计算性与计算复杂性问题

其实 计算机面对的难题很多

不妨看几个例子

实例一 梦想成诗人

传说某大学有一学生

姑且称之为张三

张三非常爱好古诗词

对唐代诗人更是仰慕不已

《唐诗三百首》中的名言佳句

经常挂在嘴边

张三一直梦想当一个诗人

为此做了不少努力

当他学习了计算机技术以后

突发奇想

常用汉字不过是4000个

如果输入这4000个汉字

并对它们进行全排列

那么所有的名言佳句

不都在其中了吗

然后

再从其全排列中

摘出这些名言佳句

不就是一个前无古人

后无来者的大诗人了吗

这一奇想使他欣喜若狂

于是

他写好求解4000个汉字

全排列的程序到计算机上去运行

然而 3天过去了

程序还没有结果

他沉住气又等了3天

程序仍在运行还是没有结果

他再等了3天依然如故

他百思不得其解

带着问题去向老师请教

老师告诉他当n很大时

该问题是现实不可计算的

比如当n等于26时

26个不同汉字的全排列数

是26的阶乘

26的阶乘约等于

4乘10的26次方

以每年365天计算

每年共有

365乘24乘3600秒

也就是3.1536乘10的7次方秒

假设计算机每秒能产生

10的7次方个排列

那么要产生26个汉字的全排列

共需要4乘10的26次方

除以3.1536乘以10的7次方

约等于1．2乘10的12次方年

再看第二个例子

汉诺塔问题

据说西方的传教士来到印度

在印度的寺庙里看到一些和尚

整天都在移动一些盘子

感到非常好奇

经打听

才知道有那么一个

古老的传说

这个传说

说的是印度教的天神

在创造地球这一世界时

建了一座神庙

神庙里竖有三根宝石柱子

柱子由一个铜座支撑

梵天将64个

直径大小不一的金盘子

按照从大到小的顺序依次

套放在第一根柱子上

形成一座金塔

即所谓的汉诺塔

天神让庙里的和尚

将第一根柱子上的64个盘子

借助第二根柱子

全部移到第三根柱子上

也就是将整个塔迁移

同时定下3条规则

一 每次只能移动一个盘子

二 盘子只能在三根柱子上

来回移动不能放在别的地方

三 在移动过程中

三根柱子上的盘子必须始终

保持大盘在下 小盘在上

天神说

当这64个盘子

全部移到第三根柱子上去

世界末日就要到了

这就是著名的汉诺塔问题

这个就是汉诺塔的示意图

那么 当n等于64时

也就是有64个盘子的时候

到底需要移动多少次盘子

耗费多少时间呢

从数学上来说

要完成汉诺塔的搬迁

需要移动盘子的次数是

2的64次方减1

这是一个非常巨大的数字

大家可以看到

假定每移动一个盘子需要1秒

一年按31536000秒来计算

则僧侣们一刻不停地

来回移动盘子

也需要花费5849亿年的时间

如果用计算机来求解这样的问题

假定计算机

每秒可移动1000万个盘子

那么也需要花费

大约58490年的时间

我们再看第三个例子

旅行商问题

与组合爆炸问题

旅行商问题

简称TSP

是19世纪初提出的一个

经典的数学问题

有若干个城市

城市之间的距离都是已知的

现有一旅行商

要从某城市出发到每个城市旅行

途中只能在每个城市逗留一次

最后回到出发地

问如何事先确定好一条最短的路径

使其旅行的费用最少

对于这个问题

人们想到的方法是

列出每一条可能的路线

也就是对给定的城市进行排列组合

然后计算出每条路线的总里程

最后从中选出一条最短的路线

为了简化问题

我们假定只有四个城市

分别用A B C D来表示

城市之间的距离如图所示

假定旅行商从城市A出发

最后回到A

对于这么一个简单的问题

我们不难找出所有可能的旅行路线

比如说像这样

不难看出

可供选择的路线共有6条

并且从中选出一条

距离最短的路线并不难

这仅仅是针对n等于4而言

城市数更多一些时

情况会怎么样呢

当n等于7

组合路径数就是6的阶乘

也就是720条

才增加了3个城市

组合数

就从6条路径增加到了720条

总共增加了120倍

当n等于20时

组合路径数则为19的阶乘

约等于1.216乘10的17次方

这是一个很大的数字

如果每秒钟计算1条路径

则需要3.84乘10的9次方年

才能完成这个计算任务

即使利用计算机

每秒钟计算出100万条路径

也得做3800多年才能找到答案

真可谓

生也有涯

知也无涯

这些问题就引出了

可计算性与计算复杂性

可计算性问题涉及复杂的理论

不便在这里深入介绍

这里只介绍几个重要的概念

一 问题的规模

客观世界的问题

有大有小 有难有易

问题的大小通常称之为

问题的规模

那么问题的规模

又是怎么定义的呢

假设给你10个不同的数据

要求你进行排序

也许你很快就可以给出答案

假设给你的不止10个数据

而是

100个

1000个

10000个

10000000个呢

你肯定会说这不是人干的事儿

显然在这里

数据的个数

不妨用变量n表示

意味着问题的复杂性

n越大

排序的难度越大

因此人们就用n来表示问题的规模

也就是问题的大小

当问题的规模很小很小的时候

很多问题借助于计算机很容易求解

甚至手工就可以计算

所以没有讨论的必要

当n很大很大的时候

问题的复杂性就很不一样了

也就有了研究与探讨的意义了

二 P问题和NP问题

在计算学科里

一般将问题分为可求解问题

和不可求解问题

不可求解问题

也可进一步分为两类

一类是不可能求解的

另一类虽然可求解

但时间复杂度很高

例如 一个问题需要好几个月

甚至好几年才能求解

那肯定不能被认为是有效的算法

可求解问题

也叫可计算问题

又分为多项式问题

简称P问题

和非确定性多项式问题

简称NP问题

P问题

如果一个问题的

求解过程的时间复杂度

是问题规模n的多项式

如O（n平方）

那么这个问题就可以

在多项式时间内解决

或者说这个问题有多项式的时间解

我们就说这个问题为P问题

NP问题

NP问题是指

问题求解的时间复杂度

不能使用确定的多项式来表示

通常它们的时间复杂度

都是指数形式

比如O（10的n次方）

O（n的阶乘）等等

前面给出的汉诺塔问题

旅行商问题

就是这类NP问题

好 这一节就介绍到这

谢谢大家