第六讲数据与算法演示文稿

第六讲数据与算法演示文稿目前一页\总数四十九页\编于十八点优选第六讲数据与算法目前二页\总数四十九页\编于十八点目前三页\总数四十九页\编于十八点数据+算法=计算

计算是求解问题的过程

数据是计算的对象与产物，算法是计算过程的形式化描述

与理论与实践一样，计算也是探索自然规律与本质的重要形式

计算机作为计算的工具，古往今来无所不在，其本质大同小异目前四页\总数四十九页\编于十八点借助绳索的计算输入：任给直线l及其上一点A

输出：经过A做l的一条垂线算法 //2000B.C.，埃及人

取12段等长的绳索，首尾联接成环

任取一结，固定于点A//奴隶甲

将4段绳索沿l抻直至点B//奴隶乙

沿另一方向找到第3段绳索的端点C//奴隶丙

移动点C，直至其所有绳索抻直//奴隶丙

......这里的计算机是什么？lAlABC目前五页\总数四十九页\编于十八点使用尺规的计算输入： 平面上任一线段AB

输出： 将AB三等分算法

从A发出一条与AB不重合的射线

在上取AC'=C'D'=D'B'

联接B'B

经D'做B'B的平行线，交AB于D

经C'做B'B的平行线，交AB于C这里的计算机是什么？子程序：过直线外一点，做平行线ABC'D'B'DC目前六页\总数四十九页\编于十八点图灵机纸带读写头规则集字母表目前七页\总数四十九页\编于十八点数据

是客观事物的符号表示、信息的载体源自生产实践、社会实践、实验观测或模拟计算

dare → datum → data

(togive) → (somethinggiven) → (givens)目前八页\总数四十九页\编于十八点数据的形式多种多样目前九页\总数四十九页\编于十八点数据

究其本质，都可归结为数字..."Allthingsarenumbers.""Godmadetheintegers;allelseistheworkofman."目前十页\总数四十九页\编于十八点Gödel编号——凡物皆数K.Gödel： 任一逻辑系统的符号、表达式、公理、命题等

均可以自然数标识素数序列：p(k)=第k个素数 //2,3,5,7,11,13,17,19,23,...Gödelnumbering：长度有限的任一自然数向量，唯一对应于某自然数

<a1,a2,...,an>=p(1)a1xp(2)a2x...xp(n)an

<3,1,4,1,5,9,2,6,5>=23x31x54x71x115x139x172x196x235Gödelnumbering：长度有限的任一字符串，唯一对应于某自然数

{a,b,c,...,z,...}={1,2,3,...,26,...} //给定可数字母表

"godel"=27x315x54x75x1112=60549593208080007397378320000反之，由Gödel编号也可唯一确定原向量或字符串 //素因子分解！时间？

目前十一页\总数四十九页\编于十八点Cantor对角线——可数少于不可数Cantornumbering

cantor2(a1,a2)=((a1+a2)2+3a1+a2)/2

cantorn+1(a1,...,an,an+1)=cantorn(a1,...,an-1,cantor2(an,an+1))长度有限的任一符号串都可视作d进制自然数 //d=1+|∑|

"decade"=453145(10)

//d=1+|{'a'~'i'}|=10长度无限的符号串都可视作[0,1)内的d进制小数

Cantor： 集合是否可数，与其维度无关

有理数集与自然数集一样可数 //(分子,分母)，aleph0

无理数集不可数 //Cantor'sdiagonal,aleph1>aleph003412567891011121314目前十二页\总数四十九页\编于十八点数据只是符号的集合

经过计算之后，方成为指代特定事物的信息

"Computerscienceshouldbecalledcomputingscience,forthesamereasonwhysurgeryisnotcalledknifescience."计算——数据到信息的提炼过程

思维——信息到知识的提升过程

为此既要借助理性与智慧，也须付出必要的时空成本目前十三页\总数四十九页\编于十八点算法=计算过程的形式化描述

在特定计算模型下，旨在解决特定问题的指令序列 输入 待处理的信息（问题）

输出 经处理的信息（答案）

正确性 的确可以解决指定的问题

确定性 可明确描述为基本操作的一个序列

可行性 每一基本操作都可实现，且在常数时间内完成

有穷性 任何输入经有穷次基本操作，都可以得到输出 //可计算性

... ...目前十四页\总数四十九页\编于十八点计算，但切勿轻信直觉目前十五页\总数四十九页\编于十八点计算，可不要指望一定有结果算法编写是一回事，算法运行又是另一回事目前十六页\总数四十九页\编于十八点停机与不可判定性冯·诺依曼：程序本身也是数据，可以按照某种语法理解为指令序列 //第5讲图灵机的各组成部分均可Gödel编号，总体亦然通用图灵机UTM：

以任一图灵机（的Gödel编号）及其输入为输入，忠实模仿其执行过程停机问题：可否借助图灵机本身来判断

UTM的任意一次计算能否在有限时间内终止？很遗憾，不存在这样的图灵机//构造Cantor对角线“为那些自己不理发的人理发的理发师，是否应给自己理发？”更遗憾，任何非平凡的形式系统，都存在类似的缺陷：三等分角、倍方，...TM的编号输出输入目前十七页\总数四十九页\编于十八点计算，更不能指望很快有结果能否停机是一回事，多快停机又是另一回事目前十八页\总数四十九页\编于十八点组合枚举与难解性难解？ 第3讲：“非真空环境中的Maxwell方程”

第5讲：P=IxCxT旅行商问题：

设计路程最短的旅行方案，访问n座城市各一次直观思路：

分别考察所有可能的方案，选择其中路程最短者很遗憾，计算量太大

n=15时，共15!/15/2>4x10^10

而且，随着n的增加，须对比的方案数将激增

n=20时，共20!/20/2>6x10^16目前十九页\总数四十九页\编于十八点2-Subset【问题描述】

S为一组共n个正整数，∑S=2m

是否有S的子集T满足∑T=m？【选举人制】

总统由各州议会选出的选举人团，

而不是由选民直接选举产生50个州加1个特区共538票

获270张选举人票即当选，但...若共有两位候选人

是否可能各得269票？22伊利诺伊3怀俄明8康涅狄格13弗吉尼亚4缅因12印第安纳4夏威夷8科罗拉多5西弗吉尼亚5犹他25佛罗里达3特拉华5新墨西哥5内布拉斯加3蒙大拿11田纳西6阿肯色9亚拉巴马9路易斯安那7俄勒冈10马里兰8肯塔基8亚利桑那8俄克拉何马4罗得岛12马萨诸塞4内华达3阿拉斯加4新罕布什尔11密苏里10明尼苏达7艾奥瓦3南达科他8南卡罗来纳21俄亥俄32得克萨斯6堪萨斯3北达科他14北卡罗来纳18密歇根11华盛顿4爱达荷7密西西比54加利福尼亚15新泽西13佐治亚3佛蒙特11威斯康星23宾夕法尼亚33纽约3华盛顿特区目前二十页\总数四十九页\编于十八点2-Subset直觉算法：逐一检查S的每一子集定理：|2S|=2|S|=2n也就是说，直觉算法需要迭代2n

轮还是直觉：应该有更好的办法吧？

//同意的举手定理： 2-Subset是NP-complete的意即：

就目前的计算模型而言

无法在多项式时间内回答此问题

//就此意义而言，直觉算法已是最优22伊利诺伊3怀俄明8康涅狄格13弗吉尼亚4缅因12印第安纳4夏威夷8科罗拉多5西弗吉尼亚5犹他25佛罗里达3特拉华5新墨西哥5内布拉斯加3蒙大拿11田纳西6阿肯色9亚拉巴马9路易斯安那7俄勒冈10马里兰8肯塔基8亚利桑那8俄克拉何马4罗得岛12马萨诸塞4内华达3阿拉斯加4新罕布什尔11密苏里10明尼苏达7艾奥瓦3南达科他8南卡罗来纳21俄亥俄32得克萨斯6堪萨斯3北达科他14北卡罗来纳18密歇根11华盛顿4爱达荷7密西西比54加利福尼亚15新泽西13佐治亚3佛蒙特11威斯康星23宾夕法尼亚33纽约3华盛顿特区目前二十一页\总数四十九页\编于十八点计算，绝不要指望不劳而获信息，表现为数据集所处状态的特定性信息量，可（反比）度量为数据集状态的数目作为信息确定化的过程，计算必须付出必要的成本目前二十二页\总数四十九页\编于十八点重温：“信息故事”

第4讲第47页经3次称量，必可从至多

27个小球中确定超重者反之，为确定27个小球中的超重者，（最坏情况下）至少须做3次称量更一般地，最少称量次数与小球数呈对数关系——为什么？目前二十三页\总数四十九页\编于十八点熵与下界热力学第二定律：能量不会自动地从低温物体传向高温物体 //熵增加原理Shannon： 数据中所蕴含的信息量，可由信息熵度量

系统S的信息熵E可度量为其可能的状态总数N：E=log2N任一热系统的熵减少，都须付出至少相等的能量

计算使得信息熵减少，也须付出至少相等的“能量”，称作计算量下界

E(S0)=log2(n!)=(nlogn)E(S1)=log21=012345677123456E(S0)=log2(n)=(logn)E(S1)=log21=0???????x超重鉴别排序目前二十四页\总数四十九页\编于十八点熵与下界Landauer原理：信息的减少或丢失必伴随着熵的增加，并发出相等的热量

就最低功耗而言，AND和OR逻辑门必高于NOT门“幸福的人都是一样的，不幸福的人却各有各的不幸”

从计算的角度看，不幸者可能的状态要远多于幸福者

前者的熵远大于后者，故从前者到后者需要付出巨大的努力目前二十五页\总数四十九页\编于十八点数据终将淹没它的创造者？数据爆炸目前二十六页\总数四十九页\编于十八点动力——急剧膨胀的客观需求今天典型的数据集，须以TB为单位度量

345 Globalclimate

300 Nuclear

250 Turbulentcombustion

50 Parkinson'sdisease

10 ProteinfoldingWeb页面总数

2005年=1.210^10，2009年=3.010^10人类拥有的数字化数据，总量已达ZB

规模

0.28 0.5 0.8 1.2 ... 35

2007 2008 2009 2010 ... 20201doggabyte=2100=10301nonabyte=290=10271yottabyte=280=10241zettabyte=270=10211exabyte=260=10181petabyte=250=10151terabyte=240=10121gigabyte=230=1091megabyte=220=1061kilobyte=210=103目前二十七页\总数四十九页\编于十八点原因——日益降低的数据成本数据获取的速度，远远超过对其处理的速度科学仿真计算：

医药、生物、物理、化学、天文地理海洋、气象、…卫星遥感、人工地震：NCAR数据增长速度：2PB/month三维扫描仪，Navteq街景采集车：1.5M

个三维数据点全球每天email总量逾6x10^10

封Facebook每天的总访问时长逾8x10^9

分钟，上传图片逾10^8

张2010年全球Internet总带宽达到38Tbps

物联网+IPv6：可跟踪50~100x10^12

个物体数码单反全球每年销售1000万台，每次按下快门10MB数据硬盘全球年销售总量近2x10^9块目前二十八页\总数四十九页\编于十八点算得快，更要传得快——超级计算目前二十九页\总数四十九页\编于十八点/,June20102010年10月29日改进后的TianHe-1A，荣登Top500

榜首目前三十页\总数四十九页\编于十八点数据通道——TianHe-1A的制胜法宝一味提高计算速度本身并不足够

更重要的是，如何提高数据在不同计算层次、不同计算节点间的传递速度存储器基本规律：容量速度=价格（成本）

存储器不得不划分为不同层次，速度上有天壤之别 //第5讲：Cache

磁盘/内存=ms/ns=10^6

天/秒=246060<254000=10^5=三生三世/天应用数据体量的增长，远远快于存储系统的容量和速度增长

Jaguar内部网络InfiniBand速度达80Gbps，I/O带宽高达240GB/s

但面对动辄TB量级的数据，也只能望洋兴叹TianHe-1A

采用自主研发内部网络Arch，速度为InfiniBand的两倍CPURAMDISKARRAY...目前三十一页\总数四十九页\编于十八点化零为整——数据结构不再如图灵机那样，简单地

将所有数据，“平坦地”按单元格存放于一条纸带上

...目前三十二页\总数四十九页\编于十八点抽象与封装——从物理结构到逻辑结构逻辑结构是数据内在而本质的联系

是其跨越不同平台和环境的共性所在藉此可超脱于具体实现之上

通过外部接口，高效地组织并访问数据实例：借助PQ

的排序priorityqueuedelMax()insert(x)24323231231423121431423421目前三十三页\总数四十九页\编于十八点“傳位于四子”

以小见大——MD5数字签名16^32=2^128=10^38正向易，逆向难目前三十四页\总数四十九页\编于十八点以终为始——动态规划以空间换时间目前三十五页\总数四十九页\编于十八点局面搜索——与计算机对弈Tic-Tac-Toe

至多8层

尽可穷举再复杂点

如国际象棋呢？目前三十六页\总数四十九页\编于十八点难以穷举！难以穷举？即便仅考虑50步且每步仅4种可能，需搜索的局面总数也将超过

4^50=2^100=10^30 //1dogga即便每步搜索仅需10次浮点运算

即便是Jaguar

之1.8x10^15flops计算能力，也需要

5x10^15sec>150x10^6yr //1yr<3.2x10^7sec诀窍：棋子不多时，实际可能的局面要远...远少于上面的估计比如五子残局，即便不考虑合法性，可能的局面亦不过

64x63x62x61x60<64^5=2^30=10^9 //1giga方法： 将所有可能的局面记录下来 //用空间换取时间

将原先的搜索树，更换为搜索图

目前三十七页\总数四十九页\编于十八点K.Thompson的完美残局库——空间vs时间1981，穷尽四子残局，发现

KQ-KR=61步

共计1.9x10^6种合法局面

——50步限招并不合理1986，穷尽五子残局（通常合法局面数=2~3x10^8），发现

KQ>KBB——自1634起公认的官和——尽管可能需要71步六子残局？局面数太多，无法用CD保存

KRNvs.KNN

共1.8x10^10种合法局面，70%为白方必胜

某一局面须经262步方可取胜

——前14步的任何疏忽，都将立即成和目前三十八页\总数四十九页\编于十八点眼见为实——可视化数据并非多多益善尊重人的认知规律，通过图形、图像等形式

令我们更加直观、准确地洞悉隐藏于数据背后的信息科学计算+信息+程序开发目前三十九页\总数四十九页\编于十八点合久必分，分久必合

计算中心，桌面电脑，网格与云"Ithinkthereisaworldmarketforaboutfivecomputers."

——T.

J.Watson,1943

"640Koughttobeenoughforanybody."

——B.Gates,1981目前四十页\总数四十九页\编于十八点云计算——尽情计算好了，何必了解细节通常，台式计算机60%至85%的时间处于空闲状态充分利用这些闲置的计算能力，可以

破解绝症基因，搜寻地外生命，...，加入全球网格计算计算是一种公共资源

进行计算，应该像使用市政水电一样——只需直接打开龙头，或者接上插头“一千台电脑计算一小时，而非一台电脑计算一千小时”

——EdLazowska数据中心——“Datacenterisacomputer”

Google由横跨约20个