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

第六讲数据与算法演示文稿现在是1页\一共有49页\编辑于星期五优选第六讲数据与算法现在是2页\一共有49页\编辑于星期五现在是3页\一共有49页\编辑于星期五数据+算法=计算

计算是求解问题的过程

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

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

计算机作为计算的工具，古往今来无所不在，其本质大同小异现在是4页\一共有49页\编辑于星期五借助绳索的计算输入：任给直线l及其上一点A

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

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

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

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

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

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

......这里的计算机是什么？lAlABC现在是5页\一共有49页\编辑于星期五使用尺规的计算输入： 平面上任一线段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现在是6页\一共有49页\编辑于星期五图灵机纸带读写头规则集字母表现在是7页\一共有49页\编辑于星期五数据

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

dare → datum → data

(togive) → (somethinggiven) → (givens)现在是8页\一共有49页\编辑于星期五数据的形式多种多样现在是9页\一共有49页\编辑于星期五数据

究其本质，都可归结为数字..."Allthingsarenumbers.""Godmadetheintegers;allelseistheworkofman."现在是10页\一共有49页\编辑于星期五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编号也可唯一确定原向量或字符串 //素因子分解！时间？

现在是11页\一共有49页\编辑于星期五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现在是12页\一共有49页\编辑于星期五数据只是符号的集合

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

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

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

为此既要借助理性与智慧，也须付出必要的时空成本现在是13页\一共有49页\编辑于星期五算法=计算过程的形式化描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

n=20时，共20!/20/2>6x10^16现在是19页\一共有49页\编辑于星期五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华盛顿特区现在是20页\一共有49页\编辑于星期五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华盛顿特区现在是21页\一共有49页\编辑于星期五计算，绝不要指望不劳而获信息，表现为数据集所处状态的特定性信息量，可（反比）度量为数据集状态的数目作为信息确定化的过程，计算必须付出必要的成本现在是22页\一共有49页\编辑于星期五重温：“信息故事”

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

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

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

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

E(S0)=log2(n!)=(nlogn)E(S1)=log21=012345677123456E(S0)=log2(n)=(logn)E(S1)=log21=0???????x超重鉴别排序现在是24页\一共有49页\编辑于星期五熵与下界Landauer原理：信息的减少或丢失必伴随着熵的增加，并发出相等的热量

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

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

前者的熵远大于后者，故从前者到后者需要付出巨大的努力现在是25页\一共有49页\编辑于星期五数据终将淹没它的创造者？数据爆炸现在是26页\一共有49页\编辑于星期五动力——急剧膨胀的客观需求今天典型的数据集，须以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现在是27页\一共有49页\编辑于星期五原因——日益降低的数据成本数据获取的速度，远远超过对其处理的速度科学仿真计算：

医药、生物、物理、化学、天文地理海洋、气象、…卫星遥感、人工地震：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块现在是28页\一共有49页\编辑于星期五算得快，更要传得快——超级计算现在是29页\一共有49页\编辑于星期五/,June20102010年10月29日改进后的TianHe-1A，荣登Top500

榜首现在是30页\一共有49页\编辑于星期五数据通道——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...现在是31页\一共有49页\编辑于星期五化零为整——数据结构不再如图灵机那样，简单地

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

...现在是32页\一共有49页\编辑于星期五抽象与封装——从物理结构到逻辑结构逻辑结构是数据内在而本质的联系

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

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

的排序priorityqueuedelMax()insert(x)24323231231423121431423421现在是33页\一共有49页\编辑于星期五“傳位于四子”

以小见大——MD5数字签名16^32=2^128=10^38正向易，逆向难现在是34页\一共有49页\编辑于星期五以终为始——动态规划以空间换时间现在是35页\一共有49页\编辑于星期五局面搜索——与计算机对弈Tic-Tac-Toe

至多8层

尽可穷举再复杂点

如国际象棋呢？现在是36页\一共有49页\编辑于星期五难以穷举！难以穷举？即便仅考虑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方法： 将所有可能的局面记录下来 //用空间换取时间

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

现在是37页\一共有49页\编辑于星期五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步的任何疏忽，都将立即成和现在是38页\一共有49页\编辑于星期五眼见为实——可视化数据并非多多益善尊重人的认知规律，通过图形、图像等形式

令我们更加直观、准确地洞悉隐藏于数据背后的信息科学计算+信息+程序开发现在是39页\一共有49页\编辑于星期五合久必分，分久必合

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

——T.

J.Watson,1943

"640Koughttobeenoughforanybody."

——B.Gates,1981现在是40页\一共有49页\编辑于星期五云计算——尽情计算好了，何必了解细节通常，台式计算机60%至85%的时间处于空闲状态充分利用这些闲置的计算能力，可以

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

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

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

Google由横跨约20个数