计算机科学导论-思想和方法-第3版-第6章.ppt

例6.3 化学元素周期表 进入19世纪后，由于化学分析方法的改进，到1869年，人们已经发现了63种化学元素。 随着新元素发现的增加，以及对这些元素性质的更多了解，人们反而对眼前纷繁复杂的化学世界产生了一种迷惑：难道世界上的化学物质就是这样杂乱无章地凑到一起的吗？ 为了寻找化学元素之间的内在联系，许多科学家开始致力于这方面的探索。 1869年3月，俄国化学家门捷列夫发表了《元素属性和原子量的关系》的论文，首创了化学元素周期表，揭示了化学元素性质呈周期性变化的内在规律，并指明了发现新元素的方向。 例6.4 整数 当把整数看作是一个系统时，根据等价关系，可以将整数划分为若干互不相交的子集。 方案一：将整数划分为奇数和偶数。 方案一：以3为模，可将整数S划分为下面3类具有同余关系的集合S1、S2和S3。 余数为0： S1={…, -3n, …, -6, -3, 0, 3, 6, …, 3n, …}。 余数为1： S2={…, -3n+1, …, -5, -2, 1, 4, 7, …, 3n+1, …}。 余数为2： S3={…, -3n+2, …, -4, -1, 2, 5, 8, …, 3n+2, …}。 例6.5 计算机网络 为了解决复杂网络协议的设计问题，国际标准化组织(ISO)采用系统科学的思想，定义了现在被广泛使用的开放系统互连模型，该模型将整个网络协议划分为7个层次： 应用层 表示层 会话层 运输层 网络层 数据链路层 物理层 人固有能力的局限性以及使用工具后产生的力量 体力劳动 脑力劳动 体力 脑力(记忆、理解、想象等能力) 体力的局限性： 例如，目前跳高的世界纪录是2.45米(1993年，古巴人哈维尔·索托马约尔创造)；100-metre race, 9.58 seconds (August 16, 2009, Bolt); Marathon, 2 hours,?3?minutes and 59 seconds (2008, Gebrselassie, the length is prescribed is 42.195 km). 对于一个普通的成年人，要想跳过1米的高度并不困难；如果借鉴算法大小O的表示，那么，对于世界冠军和我们一般的成年人来说，体力处在同一个数量级。 使用工具后产生的力量： 例如，借助于飞机，人就可以飞得很高。 人固有能力的局限性以及使用工具后产生的力量 从现代运动历史上，100米竞赛首次出现是在1896年第一届现代奥运会希腊雅典奥运会上。美国的托马斯·伯克在预赛中以11秒8创造了第一个男子100米的奥运会纪录。此后100多年里，人类不断超越极限，将百米跑的世界纪录提升至9秒58。 人固有能力的局限性以及使用工具后产生的力量 100年的时间，百米跑的纪录才提升了1秒半。从图表中我们有理由相信这个纪录已经接近极限。更有一种说法是人类100米跑纪录的提升，各类先进运动装备功不可没。 人固有能力的局限性以及使用工具后产生的力量 脑力的局限性： 例如，计算1＋2＋3＋……＋20；规定必须逐步相加，即首先计算1＋2＝3，然后是3＋3＝6，依次类推；对该相加过程计时。 对于计算能力最快的同学以及一般的同学来说，所需要的时间相差不大，大致在一个数量级上。 从这个意义上来说，人的脑力处于同一个数量级。 使用工具后产生的力量： 例如，借助于数学工具，计算N(N+1)/2，其中N=20。 使用工具后产生的力量 牛顿是个天才！ 但是，他的才能并不在于他的大脑计算能力特别突出， 而在于懂得如何对问题做合理的简化和理想化，从而把复杂的问题转化为普通人的大脑可以处理的、相对简单的问题。 爱因斯坦也是这样！ 复杂性 如果将所考察的系统看作一个数字序列，那么，从可操作性的角度来看，可以将该系统的复杂性定义为： 寻找最小的程序或指令集来描述给定的“结构”，此时，这个程序的大小相对于数字序列的大小。 例6.6：序列aaaaaaa…… 相应的程序为：在每一个a后续写a。 称为亚（准）复杂性系统。 例6.7：序列aabaabaabaab…… 仍然可以很容易地写出程序：在两个a后续写b并重复这一操作。 与上一个例子相比，该例要稍微复杂一些。 复杂性 例. 0，1，1，2，3，5，8，13，21，34，… 同样可以用很短的程序来描述： F0=0，F1=1，Fn+2=Fn+1+Fn，n≥0 复杂性 例6.8：aabaababbaabaababb…… 同样可以用很短的程序来描述：在两个a后续写b并重复；并且，每当第三次重写b时，将第二个a替换为b。 上述三个例子中的序列都具有可定义的结构，存在对应的程序来进行表示。 例6.9：aababbababbbaba